Chapel: How will `map` support values of type non-nilable class?

[dlongnecke-cray]

This issue is made in the spirit of #14367 and #13602, which discuss the issue of supporting non-nilable value types for associative arrays and arrays, respectively.

Currently, the map type cannot support values of type non-nilable class. This is because (as far as I can see) of two reasons:

• It uses an associative array as its implementation
• It has a this routine proc ref this(k: keyType) ref; which will implicitly insert the key to access into the map if it is not found, and then default initialize the value associated with the key

I think we ought to handle the second issue before we handle the first.

Originally, when designing the map API, @e-kayrakli suggested we have all overloads of this halt if the key to be accessed was not present in the map. Originally, I was against this because I thought it made use of a map less intuitive. However, clearly I did not have non-nilable classes in mind at the time.

If we adopt the "halt if key not present" semantics for the ref overload of map.this now, then we can adjust the implementation of map to support non-nilable class values. Specifically:

use Map;

class Foo { var x: int = 0; }
var m: map(string, Foo);

// This line should halt because "key" is not a key present inside this map.
m["key"] = new Foo();

Following this map can safely support values of type non-nilable class, because key/value pairs may only be inserted together via a call to map.add.

Thoughts?

[dlongnecke-cray]

Another option that just occurred to me is that we could keep the code as is and provide another overload for non-nilable classes:

proc ref this(key: keyType) ref where isNonNilableClass(valType) {
     compilerError("Non nilable class types cannot be default initialized. Use map.add instead");
}

EDIT: Nope, no, this definitely wouldn't work...Didn't think that one through.

But if there is a solution along those lines it might be better than just changing the semantics of map.this entirely!

[bradcray]

Taking a bit more time to stew on this, I'm remembering that an approach I proposed awhile back is to have the associative array store nilable C when it's asked to store non-nilable C and then to take care of any casts from nilable to non-nilable in its implementation.

[mppf]

But if there is a solution along those lines it might be better than just changing the semantics of map.this entirely!

It could (say) make this throw if it accessed an element that didn't exist and no default initializer was available.

I'm remembering that an approach I proposed awhile back is to have the associative array store nilable C when it's asked to store non-nilable C and then to take care of any casts from nilable to non-nilable in its implementation.

We still have to answer the question for what behavior we expect for the program @dlongnecke-cray showed above:

use Map;

class Foo { var x: int = 0; }
var m: map(string, owned Foo);

m["key"] = new Foo();

So far it's been brought up that it could halt or throw. But there are completely different options available.

Issue #14474 discusses changing map to not have any functions that return values by reference. While it's not quite the same question, if we decided not to support the reference pattern above, the code would instead be written something like m.update("key", new Foo()) which doesn't need to default-initialize anything.

[dlongnecke-cray]

So as @mppf and later @bradcray suggested (offline during lunch), I feel confident that judicious use of a where clause is the solution.

proc ref this(k: keyType) ref where !isDefaultInitializable(valType) {
    // Halt if the key is not in the map, else retrieve a ref to the value.
}

proc ref this(k: keyType ref {
    // If the key is not present in the map, default initialize a value and add (key, value)...
    // Else retrieve a ref to an existing value.
}

This way we can get the best of both worlds.

I didn't grasp what Michael was saying earlier, but I am really happy with this potential solution.

[bradcray]

I wonder if the first overload should throw rather than halt if it's not in the map. Is it too weird to have one overload throw and the other not depending on the valType? I know most of our this() functions on rectangular arrays don't throw for performance reasons, but maps/associative arrays aren't quite as cheap and bare bones as rectangular ones anyway...?

[dlongnecke-cray]

What is the motivation for wanting the overload of this to throw?

When I was originally discussing API design for containers we settled on a fairly hard "containers should halt instead of throw" stance. While I was originally against the idea and wanted this to throw, I now think that having to put use of this in a try block makes any use of the this operation feel very cumbersome.

Edit: I can't quite recall if some were motivated on ensuring that this halts for performance reasons, but at least for me, I ended up preferring halt from an "ease of use" standpoint.

---

I guess it is true that you could always give routines calling map.this the throws tag, but that seems like a lot of throws tags...

Regardless, the option is on the table if people feel strongly about it.

[bradcray]

I was thinking that it seems unfortunate that all ref-based accesses to this() are guaranteed to be halt-free and imagining that in a case where multiple tasks were accessing and modifying the map simultaneously, it might be easy to think something was in the set, and then have it disappear out from under you, bringing your program down. But now that you've given some more of the history of the design, I'm guessing that it's the case that this already is already the case for the non-ref overloads, suggesting that we probably shouldn't revisit it here.

[mppf]

I didn't grasp what Michael was saying earlier, but I am really happy with this potential solution.

I was saying that we could change map to not have any this function that returns a reference to an element. (I.e. you wouldn't write m["key"] = new Foo(); and instead something like m.set("key", new Foo()). If we did that, we wouldn't have this problem.

[dlongnecke-cray]

Update!

I'm having trouble casting a ref SomeClass? to a ref SomeClass and then returning that reference. I'm not even sure if it's possible.

    pragma "no doc"
    proc const _getVal(key: keyType) ref: valType
    where isNonNilableClass(valType) {
      try! {
        return vals[key];
      }
    }

If I try to compile this I will get the following error:

$CHPL_HOME/modules/standard/Map.chpl:100: error: Scoped variable cannot be returned

Which is probably because the _cast returns a value which I'm then taking the reference of.

If I attach pragma "unsafe" then the routine will segfault because the result reference never aliases anything (it is NULL).

---

If this is not possible then it means that this for non-nilable classes will have to return a value instead of a reference, which is not consistent with the semantics for other types (and which begs us to address #14474 all the more).

I feel like this should be possible but am not sure of how to achieve it.

Ideas?

[bradcray]

@mppf / @vasslitvinov: Any thoughts?

[mppf]

It's not possible today. This is related to #14307 and #8489. I don't think it would be easy to do. (It might make sense longer term, though). Also, my draft PR #14835 contains many Errors changes that are motivated by this issue (in subclass form, anyway).

A similar question is - given a ref ParentClass that has dynamic type ref ChildClass, can it be explicitly cast and retuned as a ref ChildClass?

[dlongnecke-cray]

Ok, then. Back to the drawing board!

What I need to figure out is an alternative way to use an associative array of non-nilable to implement Map, while preserving the compiler errors for associative arrays in any other context.

[mppf]

I don't think that map should be implemented with associative arrays at all because of issue #8339 - the preferred solution I have to that issue is to implement associative arrays on top of map. I view the current strategy of implementing map with an associative array as a stopgap.

[dlongnecke-cray]

I view it as a stopgap as well, but w.r.t. to the current release schedule I think it is the only viable strategy short of continuing to ban maps of non-nilable classes.

[vasslitvinov]

Since we currently do not support non-nilable associative arrays, it is reasonable to not support other resizable data structures with non-nilable elements.

[bradcray]

@vasslitvinov: The proposal here was that since (a) most operations on map take keys and values simultaneously (unlike domains/arrays which handle the two things distinctly) and (b) map seems more likely to be used by end-users than associative domains and arrays that if we could get a version of Map working with non-nilable classes, that would be valuable for those who wanted to live in a non-nilable world.

Personally, I'd prefer a map that supported non-nilable classes and didn't have a ref based accessor over not having any map that supported non-nilable at all.

@dlongnecke-cray: I'm not seeing the _getVal() routine you pasted above in Map. What's the context for that code snippet?

[dlongnecke-cray]

@bradcray, The _getVal routine is what I'm trying to write to solve my current problem. The context for it is the following:

• The value type of the map is shared SomeClass (some non-nilable class), and the value type of the associative array is shared SomeClass?.
• The map.this routine, in its current incarnation, returns a _reference_ to a value in the map when given a key
• I am trying to write a routine that, when given a key, will fetch a ref shared SomeClass? from the associative array and return a ref shared SomeClass. Same reference (points to the same thing), just no longer nilable.

[mppf]

Earlier I said:

It's not possible today. This is related to #14307 and #8489. I don't think it would be easy to do. (It might make sense longer term, though). Also, my draft PR #14835 contains many Errors changes that are motivated by this issue (in subclass form, anyway).

A similar question is - given a ref ParentClass that has dynamic type ref ChildClass, can it be explicitly cast and retuned as a ref ChildClass?

We now have issues #14937 and #14834 about the nilability and subclass downcast cases. However the result is the same - I think both of these features would break the type system and are totally unworkable.

Responding to Brad's earlier comment:

Personally, I'd prefer a map that supported non-nilable classes and didn't have a ref based accessor over not having any map that supported non-nilable at all.

This is what I think we should do. I think we should discuss it over in issue #14474. I think the main open question here is whether or not we need to change "the map" to not return references or whether we need to make multiple map implementations with different constraints.

[bradcray]

I think the main open question here is whether or not we need to change "the map" to not return references or whether we need to make multiple map implementations with different constraints.

A third option is to just not support the ref variant for eltTypes for which it doesn't make sense. This is what I'd do for this release.

A fourth idea would be to look into what Rust does (reportedly, they have a "slot" concept that's returned by such accessors that can be used to lazily insert something into the data structure?)

[bradcray]

@daviditen / @dlongnecke-cray: This can be closed now, right?

[dlongnecke-cray]

Closing in favor of the discussion in #14474.