Chapel: Supported types in collections

[ben-albrecht]

This is an issue for tracking currently supported types in collections based on tests checked into the repository.

Master

✅ = currently works
❌ = currently does not work
🔹 = not expected to work
| | list | map | set | fixed array | resized array | assoc array | sparse | tuple |
|------------------------ |------ |----- |----- |---------------|---------------|------------- |-------- |------- |
| owned t | ✅ | ✅ | ✅ | ✅ | 🔹 | 🔹 | 🔹 | ✅ |
| shared t | ✅ | ✅ | ✅ | ✅ | 🔹 | 🔹 | 🔹 | ✅ |
| borrowed t | ✅ | ✅ | ✅ | ✅ | 🔹 | 🔹 | 🔹 | ✅ |
| unmanaged t | ✅ | ✅ | ✅ | ✅ | 🔹 | 🔹 | 🔹 | ✅ |
| (shared t, shared t) | ✅ | ✅ | ✅ | ❌ | 🔹 | 🔹 | 🔹 | ✅ |
| owned t? | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| shared t? | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| borrowed t? | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| unmanaged t? | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| (shared t?, shared t?) | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| record | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |

Changes since 1.22:

• [x] list(borrowed T) and list(borrowed T?) are ✅ as of #15575
• [x] set(borrowed *), set(unmanaged *), and set(shared T?) are ✅ as of #15592
• [x] list((shared T, shared T)) is ✅ as of #15618
• [x] set((shared T?, shared T?)) is ✅ as of #15592.
• [x] map(?t, owned T), and map(?t, borrowed *) will be ✅ as of #15659
• many others... (stopped updating this list)

1.22

✅ = currently works
❌ = currently does not work
🔹 = not expected to work
| | list | map | set | fixed array | resized array | assoc array | sparse | tuple |
|------------------------ |------ |----- |----- |---------------|---------------|------------- |-------- |------- |
| owned t | ✅ | ❌ | ❌ | ✅ | 🔹 | 🔹 | 🔹 | ✅ |
| shared t | ✅ | ✅ | ❌ | ✅ | 🔹 | 🔹 | 🔹 | ✅ |
| borrowed t | ❌ | ❌ | ✅ | ✅ | 🔹 | 🔹 | 🔹 | ✅ |
| unmanaged t | ✅ | ✅ | ❌ | ✅ | 🔹 | 🔹 | 🔹 | ✅ |
| (shared t, shared t) | ❌ | ❌ | ❌ | ❌ | 🔹 | 🔹 | 🔹 | ✅ |
| owned t? | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
| shared t? | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
| borrowed t? | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
| unmanaged t? | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
| (shared t?, shared t?) | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
| record | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |

Notes & Caveats

1. This table assumes a failing case should eventually work unless a reason for not supporting it has been identified. Not all failing cases have been thoroughly diagnosed yet, so there are likely some missing 🔹s in the table.

2. (shared T, shared T) and (shared T?, shared T?) were chosen to represent support for tuples in general to keep the size of this matrix manageable. Future work could explore the larger matrix of combinations including all managed types and possibly combinations of types as tuples.

3. "fixed-size array" really means "fixed-size, initialized array", since uninitialized arrays require a default value for their elements.

Tests

These results are based on the following tests:

• test/arrays/types/
• test/associative/types/
• test/sparse/types/
• test/types/tuple/types/
• test/library/standard/List/types/
• test/library/standard/Map/types/
• test/library/standard/Set/types/

Error messages

See the corresponding .bad files in the above directories for current error messages. Also see this gist for all error messages as of 1.22 release.

🔹 cases:

• non-nilable sparse element types provide a better error message in 1.23 pre-release ( #15571)
• owned T for map provides a good error message in 1.22

[dlongnecke-cray]

I would tentatively mark tuples of borrowed C? as A-OK, because the following version of your tuple test compiles just fine:

class C { var x: int = 0; }

proc main() {
  var tup = (new borrowed C?(128), new borrowed C?(256));
  writeln(tup);
  return;
}

It is only your specific version that does param folding on the if expression which fails:

class C { var x: int = 0; }

proc test(type T) {
  var a = if isTuple(T) then 128 else (new T(1), new T(2));
  writeln(a);
  return;
}

proc main() {
  type T = borrowed C?;
  test(T);
  return;
}

test.chpl:3: In function 'test':
test.chpl:4: error: non-lvalue actual is passed to a 'ref' formal of chpl__initCopy()
test.chpl:11: Function 'test' instantiated as: test(type T = borrowed C?)

I'll go ahead and open an issue specifically for this bug.

---

The upside is that for tuples at least, we only have to worry about owned C and owned C?.

[dlongnecke-cray]

Testing to see if the same holds true for tuples of owned C and owned C?...

[dlongnecke-cray]

Can confirm that the same bug exists for tuples of owned C? and owned C. So tuple should be all clear 👍 .

[dlongnecke-cray]

@ben-albrecht https://github.com/chapel-lang/chapel/pull/15541 Adjusts all tests in test/types/tuple/types so that they pass, and adds a future for the bug in test/param.

[ben-albrecht]

Thanks @dlongnecke-cray -- I have updated the table in the issue to reflect this.

[bradcray]

Nice @dlongnecke-cray!

I took a quick look at the buggy case hoping it would have an easy explanation, but failed to come up with anything quickly other than new ways to make the compiler segfault.

[dlongnecke-cray]

Quick update about the status of classes and list:

1) List of borrowed T and borrowed T?

So once again, these futures fail due to something the test code does that actually has nothing to do with list. This time though, I don't actually think it's a bug.

The code that fails boils down to this (I should mention that this is _after_ you've removed the fancy compilerWarning in the list module that bans borrowed classes):

var x: borrowed C?;
if false {
  x = new borrowed C(128);
} else {
  x = new borrowed C(256);
}
writeln(x);

splitInitBorrowedInBlock.chpl:3: In function 'test':
splitInitBorrowedInBlock.chpl:8: error: Scoped variable x would outlive the value it is set to

This error makes a bit more sense if you were to imagine x being assigned a borrow from an owned C declared in the branch blocks instead of a new borrowed C. Just one of those weird quirks of new borrowed I think.

Anyhow, removing those allows the testBorrowed.chpl and testNilableBorrowed.chpl for lists to pass, but I don't think that's enough for us to safely say that lists of borrowed _work_.

I'm working on writing a few more tests.

---

1. List of (shared T, shared T)

As for lists of (shared T, shared T), this test fails because pragma "no init" isn't working properly on a tuple (from the logs it looks like elements are still being default initialized).

I'm working on it. Realistically, I think it is a task that can be done in a single sprint (I'd even be so bold as to give it a "2").

[bradcray]

The following is a bit subtle for the current table format, but:

The first four rows of the array column currently work as long as you don't resize the array. If you do resize the array, you currently get a(n intentional) user-facing execution-time error because the non-nilable types don't have default values. So, for example, if I change ArrayTest.chpl to read:

var D = {1..1};
var a: [D] t = ...same initializer as it currently has...;

assert(a.size == 1);
D = {1..2};
assert(a.size == 2);

then I get the execution-time error for those four cases because there's no obvious legal value to store in a[2]. We'd like to change this into a compile-time error as noted in https://github.com/chapel-lang/chapel/issues/15094.

If we wanted to reflect this, we could split the array column into two and have fixed-size array and resized array and put blue diamonds into the first four rows for the latter case.

With a quick look, the remaining problem in the array column would be the (shared T, shared T) case, which looks to be more of an issue with (shared T, shared T) then arrays themselves given the rest of that row (?). That said, it ultimately would have the same check/diamond behavior as other non-nilables with respect to whether the array was resized or not.

[bradcray]

Following onto my previous comment, in the sparse column:

• I think the first green check entry is a mistake? (because test/sparse/types/testOwned.bad exists)
• I believe the first five entries should not be expected to work at present (and quite possibly not ever) for reasons similar to the previous comment on arrays: sparse arrays are implemented by storing dense domains and arrays under the covers, where the dense domains are resized as new elements are added to the sparse domain and would require default values to fill in.
• That said, the error messages we're generating in these cases could certainly be cleaned up (not sure if that's required to get a blue diamond or not).

I think assoc. arrays are pretty much in the same boat, but would want @dlongnecke-cray and/or @daviditen to confirm since they spent a lot of time with them in the past release cycle.

[bradcray]

I think that DavidL's completely correct that the row of borrowed T? X's is misleading based on how the test is written and suspect that the types work better with borrowed T? than suggested. Specifically, given this line in SparseTest.chpl:

  A[1] = if isTuple(t) then (new t[0](1), new t[1](2))
          else new t(1);

imagine for a moment that it had been written like this:

  A[1] = if isTuple(t) { (new borrowed C?[0](1), new borrowed C?[1](2)) }
          else { new borrowed C?(1); }

The problem is that the then and else branches of conditionals introduce their own lexical scopes, so the new objects allocated within that scope are de-allocated when the conditional expression ends. So the compiler's error message is correct, the reference to the object is outliving the object. The preferable way to test that a collection can store a nilable borrowed would be to do something like:

var coll: myCollection(borrowed C?);
var myC = new C();
var b: C? = myC.borrow();
coll.addToCollection(b);

to ensure that the object doesn't get reclaimed before the borrow of it or the collection leave scope. For example, this example shows that sparse of borrowed? work:

https://tio.run/##NcyxCoMwAITh3ae4MUKRRjoZStHkDRzFIWqggiaS2NoiPnuaart@93PtXU5q8L4dpHPgWPGUFq8MvZ4Ztqg12s0QuGKlSULPG/tRKTK4SVqn4B5NZ0bZayLiPTwhDd33KM9QlaJGY6w1i@rAb8cwvnlItVrAySWN/1gEDFNy9CR4XtF6x4JFi@1nNWiSx8z7Dw

[ben-albrecht]

Thanks @bradcray, I plan to do the following:

• [x] Update the table to 🔹 for non-nilable sparse cases
• [x] Update the borrowed T? test cases, and update our results (#15574)
  
  
  
  • [x] Updated sparse and assoc borrowed T? cases to ✅
  
  
• [x] Split array columns into fixed-size array and resized array and add the results
  
  
  
  • tests added in #15574
  
  

[ben-albrecht]

@bradcray - I think I have addressed all your comments in the table (which still reflects the status as of 1.22). Let me know if you see anything I missed.

[dlongnecke-cray]

Found the bug for lists of borrowed, so now only figuring out the pragma "no init" bug for tuples of shared remains...

PR addressing lists of borrowed will be up soon.

[dlongnecke-cray]

PR is here https://github.com/chapel-lang/chapel/pull/15575, but I have some more cleanup before it is ready for review. I'll want Michael to take a look at it regardless.

[ben-albrecht]

I think assoc. arrays are pretty much in the same boat, but would want @dlongnecke-cray and/or @daviditen to confirm since they spent a lot of time with them in the past release cycle.

@dlongnecke-cray || @daviditen - can you confirm non-nilable types are not expected to work for associative arrays (🔹 for first 5 rows of assoc array)?

[daviditen]

I agree that associative is in the same boat as sparse for non-nilable types.

I'm not sure why they would be different from map though. We made non-nilable map work by faking it with nilable. Shouldn't we do the same with sparse and associative?

[ben-albrecht]

@daviditen - thanks. I'll update the assoc array column.

I'm not sure why they would be different from map though. We made non-nilable map work by faking it with nilable. Shouldn't we do the same with sparse and associative?

I'm not sure myself. It does seem like they ought to be consistent. @bradcray - do you have an opinion on it?

[bradcray]

Let me know if you see anything I missed.

I know the table columns don't really cry out for longer titles, but the more precise label for the fixed-size array case would be "fixed-size, initialized arrays" (since uninitialized arrays require a default value for their elements).

[bradcray]

We made non-nilable map work by faking it with nilable. Shouldn't we do the same with sparse and associative?

I thought you and/or @dlongnecke-cray attempted this during this past release cycle and came back saying that it couldn't be done? (where I thought the challenge related to map being a complete data type where arrays have domains, requiring a two-stage change: "First I need to add the new index to the domain; that requires a new array element to be allocated and default initialized. Then I can assign the array element.")

Meanwhile, what's up with set?

[ben-albrecht]

I know the table columns don't really cry out for longer titles, but the more precise label for the fixed-size array case would be "fixed-size, initialized arrays" (since uninitialized arrays require a default value for their elements).

Added a note for this. Thanks.

[dlongnecke-cray]

I will take a look at set today.

A set is basically just a thin wrapper over an associative domain at this point, so you can view it as having the same limitations as an associative domain w.r.t. to which non-nilable classes it supports.

I thought you and/or @dlongnecke-cray attempted this during this past release cycle and came back saying that it couldn't be done?

I believe @daviditen had to add several different unconventional accessor methods to the map API in order to make things work. Simply implementing map of non-nilable using nilable was not enough.

[bradcray]

so you can view it as having the same limitations as an associative domain w.r.t. to which non-nilable classes it supports.

I do view them that way, but thought that the challenges with associative only (mostly?) came up with associative arrays, not associative domains. Oh wait, no that's probably not right since we store arrays of idxType in the associative domain. OK, so I can see how that would cause problems for the non-nilable types. But I'm not clear why all of the nilable cases wouldn't simply work. (And I'm surprised that borrowed C would get a green check where all the other non-nilable types don't).

[dlongnecke-cray]

so you can view it as having the same limitations as an associative domain w.r.t. to which non-nilable classes it supports.

I do view them that way, but thought that the challenges with associative only (mostly?) came up with associative arrays, not associative domains. Oh wait, no that's probably not right since we store arrays of idxType in the associative domain. OK, so I can see how that would cause problems for the non-nilable types. But I'm not clear why all of the nilable cases wouldn't simply work. (And I'm surprised that borrowed C would get a green check where all the other non-nilable types don't).

The non-nilable cases fail with a variety of different errors, as you guessed. All the nilable cases fail because they were unable to resolve a call to chpl__defaultHash. Fixing it should enable all nilable tests for set to pass.

[dlongnecke-cray]

It seems like even back since 1.19 we've only had a chpl__defaultHash overload for borrowed object.

This is ostensibly why borrowed C gets a green check while others do not.

---

If we can hash a borrowed object, it seems reasonable to me to be able to hash any other kind of object.

I was going to (naively) try adding overloads for other class flavors. For nilable objects, I would emit some form of a halt if a nil value was passed to a routine (though I should probably learn how the object2int primitive works first).

[bradcray]

This is ostensibly why borrowed C gets a green check while others do not.

I agree with your analysis that this is why the nilable types fail. I'm still unclear why a non-nilable borrowed would pass because doesn't the associative domain that underlies the set allocate an array of idxType? (in which case, what would it store as the default value for any non-nilable type?

Getting back to @daviditen's point above about "couldn't we do the same fake-out that we do for maps?", I think we could for default associative domains (and therefore sets) since they're sort of a standalone type. I think where things get tricky are when it's a domain, array pair (or worse, domain x arrays family) when it's harder because there are essentially 2 (n) things that you have to update simultaneously if you don't have a default value (and our current domain/array interfaces don't tend to have "update the domain and array(s) simultaneously" interfaces).

I was going to (naively) try adding overloads for other class flavors.

This sounds good to me.

For nilable objects, I would emit some form of a halt if a nil value was passed to a routine (though I should probably learn how the object2int primitive works first).

It's not obvious to me that it should be incorrect to be able to hash a nil value into an associative domain of nilable... Can't we simply treat it as a 0x000000 value from the hash function's perspective?

[dlongnecke-cray]

It's not obvious to me that it should be incorrect to be able to hash a nil value into an associative domain of nilable... Can't we simply treat it as a 0x000000 value from the hash function's perspective?

I agree. That was just my naivety speaking. I think I've got a good grasp of how the internals of chpl__defaultHash and object2int work. The hardest part should just be adding tests...

[dlongnecke-cray]

So owned sets of any form will have to wait, as the code in the bowels of DefaultAssociative is having problems with them.

I think unmanaged and borrowed can both be supported, but I'm having/experiencing a really strange bug right now, which is that when the type borrowed T is passed to BenA's set test code, the instance is instantiated as owned T...

I'm working on coming up with a reproducer.

[dlongnecke-cray]

Try compiling this when you have time...

class T { var x: int = 0; }

proc test(type t) {
  var x = new t(128);
  compilerWarning(x.type:string);
  return;
}
type t = borrowed T?;
test(t);

Bug? Weird...

[bradcray]

That does look like a bug to me. Tagging @mppf in case I'm missing something obvious.

[dlongnecke-cray]

Yeah. I'll open an issue, but I'm struggling to think of what to title it.

For now, I've just rewritten the test relying on that code to work around it.

[mppf]

Yeah. I'll open an issue, but I'm struggling to think of what to title it.

"Weird Problem with borrowed nilable type argument" would be fine

[dlongnecke-cray]

Brilliant! I was overthinking it.

[mppf]

BTW I think that it's reasonable that it behaves that way, because 'new' defaults to meaning 'new owned'.

[bradcray]

I was thinking "Hey, you got your owned in my borrowed!?!"

[bradcray]

I think that it's reasonable that it behaves that way, because 'new' defaults to meaning 'new owned'.

But doesn't that go against our recent "memory management flavors can't be stacked / won't simply be ignored" philosophy? And, if I literally replace t with borrowed T? then the behavior is different which seems inconsistent with how type aliases are supposed to work (at least in my mind):

class T { var x: int = 0; }

proc test(type t) {
  var x = new borrowed T?(128);
  compilerWarning(x.type:string);
  return;
}
type t = borrowed T?;
test(t);

[dlongnecke-cray]

Agk, Brad beat me to it. I can feel a "why don't we move this discussion to the issue", so I'll go make that real quick.

---

It's clear that the decorator is there and then is being ignored, though...

class C { var x: int = 0; }

proc test(type t) {
  var x = new borrowed t(128);
  compilerWarning(x.type:string);
  return;
}
type T = borrowed C?;
test(T);

TestPassedBorrow.chpl:3: In function 'test':
TestPassedBorrow.chpl:4: error: duplicate decorators - borrowed borrowed C?
TestPassedBorrow.chpl:9: Function 'test' instantiated as: test(type t = borrowed C?)
TestPassedBorrow.chpl:9: warning: borrowed C?

If the class didn't have a decorator attached to it I would expect an implicit owned. But when it already has a borrowed, seems weird to just discard it.

[dlongnecke-cray]

Hi @ben-albrecht, here is the state of passing/failing tests for set on my local branch as of today. I think we can say that these will work on 1.23 pre-release.

owned T = 🔷
shared T = ❌
borrowed T = ✅
unmanaged T = ✅
(shared T, shared T) = ❌
owned T? = 🔷
shared T? = ✅
borrowed T? = ✅
unmanaged T? = ✅
(shared T?, shared T?) = ❌

Apologies for the lack of fancy formatting.

[bradcray]

Thanks @dlongnecke-cray!

I think in addition to saying where we expect it to land, it's important to say a bit in the slides about what didn't work in 1.22 that arguably should have.

[dlongnecke-cray]

Branch for set changes is here https://github.com/chapel-lang/chapel/pull/15592.

[dlongnecke-cray]

Branch supporting lists of tuples of non-nilable classes is here: https://github.com/chapel-lang/chapel/pull/15618

[dlongnecke-cray]

Alright, it's merged. List is in the green!

[dlongnecke-cray]

@bradcray

So in order to get associative domains of owned classes to work, I would need to add the in intent to domain.add and make some internal methods have the ref intent. I tried doing the following for BaseDomain in ChapelArray....

proc add(in i) where isOwnedClass(i.type) && isAssociativeDom(this) {
    _value.dsiAdd(i);
}

But get a compiler error deep in the bowels of functionResolution.cpp that I don't readily understand.

Beyond that, I'm actually confused as to why associative domains of _any_ non-nilable class (such as borrowed, currently) are even working at all (I understand what you were mentioning before, now)...The associative array has a default rectangular array for backing store that it apparently just...default initializes?

I'm investigating why associative domains of i.e. borrow are even working right now, but my gut feeling is that this just boils down to the default initialization problem all over again...

I feel confident that I could get sets of owned (and all non-nilable classes) to work if I used the same workarounds that @daviditen has employed for map.

[dlongnecke-cray]

Ah, I had no idea that the entire DefaultAssociative module has pragma "unsafe" attached to it. Apparently this has the effect of suppressing warnings about default initializing non-nilable objects?

The problems with owned requiring in intent to take ownership still stand, but...

[mppf]

I'm working on cleaning up the initialization issues in #15239 but I have more work to do before we can merge that PR. I don't personally think we should do more workarounds right now and instead I think we should move towards:

1. Fixing initialization for arrays and associative domains (which I am working on)
2. Figuring out what exactly we want the API to be for associative domains, sets, and maps. In particular - which of these allow returning references? How will a user indicate ownership transfer in to it and out of it? (which others could work on)

[bradcray]

Beyond that, I'm actually confused as to why associative domains of any non-nilable class (such as borrowed, currently) are even working at all (I understand what you were mentioning before, now)...The associative array has a default rectangular array for backing store that it apparently just...default initializes?

I agree that associative domains of non-nilable can't / shouldn't be expected to work, at least given the current implementation strategy and don't think that's worth pushing on.

I feel confident that I could get sets of owned (and all non-nilable classes) to work if I used the same workarounds that @daviditen has employed for map.

This is what I'd expect us to need to do. Whether or not it's worth it, I'm less certain of. But I think the more we can say "our main high-level collection types support our default class flavor", the better (and, the more we can be consistent across those collection types, also the better).

[dlongnecke-cray]

I don't want to tread on the toes of @mppf, so I'm going to delegate to him [w.r.t. to his array-coerce branch] and just focus on getting sets of all nilable class types to work first. I'll play around with API additions for associative domains, sets, and maps, as Michael suggested, with the hopes that they will help...

I'm unsure about whether I should get sets of owned to work by fixing associative domains of owned, or if I should use workarounds like @daviditen did for map.

[dlongnecke-cray]

Just a heads up that set((shared T?, shared T?)) also works as of #15592. Only tuples containing a non-nilable class trigger an error.

[dlongnecke-cray]

Note that map(?t, owned T), map(?t, borrowed T) and map(?t, borrowed T?) will work as of #15659 thanks to changes made by @daviditen.

[ben-albrecht]

In offline discussions with @dlongnecke-cray @daviditen @mppf (and separately with @bradcray), we have concluded that map and set should eventually support all types - so I am updating all 🔹 elements to ❌ for both the master and 1.22 tables.