i’m a -1 on adding RigidArray and UniqueArray to the standard library.
i think that the problem they are trying to solve is a big one, i appreciate that there is an effort being made to solve it. i have some questions about how this might unfold in practice, when these types, as proposed, collide with real-world use cases.
i. you can’t do much without Sequence.
of all the concerns i have, this is the most minor. because i think it has been well-communicated what the vision and the roadmap here is, and that people will just need to accept writing a little more boilerplate in the short term to do basic operations on UniqueArray. still, i feel that it will make a bad first impression on a lot of folks if UniqueArray ships with the standard library in “half-baked” form, even if there has been adequate communication with respect to its limitations.
for-in loops get a lot of attention because they are fascinating from a language design perspective, but i think the long tail of Sequence API, like reduce, joined, etc. is going to be the thing that is really going to kill the mood for a lot of users.
the “obvious” remedy here is to just vend all that stuff as concrete API until the Sequence support gets fleshed out, but standard libraries are forever, so that’s only gonna fly if UniqueArray stays in a package, like swift-collections, where it lives right now.
but that’s more of a customer-relations thing, it doesn’t really affect how i would use UniqueArray in my own work.
ii. UniqueArray just doesn’t compose, and it’s not really clear what the right patterns here are.
i think one of the most serious points where developers are going to struggle with UniqueArray is with upcasting of array elements. it’s easiest to illustrate this with an example using Optional promotion:
struct UniqueArena<Object>: ~Copyable where Object: ~Copyable & UniqueObject {
var keys: OrderedSet<Object.ID>
var values: UniqueArray<Object>
}
see if you have that, you’re definitely going try writing an API like this:
extension UniqueArena where Object: ~Copyable {
subscript(id: Object.ID) -> Object? {
_read {
if let i: Int = self.keys.firstIndex(of: id) {
yield self.values[i]
} else {
yield nil
}
}
}
and you’ll quickly realize that doesn’t work at all. and unlike the missing Sequence API problem, there’s really no good answer to what the additional code you need to write actually is.
one thing you could try is swapping the value to the end (which i don’t like, more on that later), popping it off, yielding the value, and then re-appending it and swapping it back in a defer block. but those are all mutating operations, which means _read becomes mutating _read, which is a really weird API, because now you’re doing operations on the UniqueArray that are semantically reads, but look to the compiler like writes. this is going to collide headfirst with Swift’s system of immutable-by-default value semantics.
or you could fatalError on missing keys, that would handwave away the problem, but that would basically mean there is no way to vend a “friendly” (ordered) dictionary type, any such type is going to be a “hard” dictionary that crashes on invalid key access.
or you just give up on the idea of storing the buffer pointer(s?) inline, and kick the whole thing into a class that you wrap in a COW struct so that reads look like reads and not writes. you end up with a thing that looks a lot like Array, but with the Element: Copyable restriction lifted, which is what i suspect many users are actually looking for when they reach for UniqueArray.
iii. UniqueArray might lead people down the wrong path, and teach lessons that will be hard to unlearn
it helps to organize (blame!) potential solutions by who needs to change and who gets to stay put.
one thing you could single out for blame here is yield. a lot of these problems become significantly less daunting if we say that yield can hop through closure boundaries, and we just classify it as “unsafe” if that closure never actually gets called. yes that would be a Separate Feature from UniqueArray, but if we presume that yield is the thing that needs to change, then that implies that generalized yield is a prerequisite for UniqueArray to be viable, in the same way that RBI was a prerequisite for Concurrency to be viable.
alternatively, you could say the developer’s patterns are at fault, that copyless Swift code necessitates a different way of laying out data structures than we are used to. for example, we might condemn UniqueArray<T> as an antipattern, and say that UniqueArray<T?> should be everyone’s starting point, since UniqueArray<T?> is considerably easier for the compiler to swallow than UniqueArray<T>.
similarly, we might accept that moving, i.e. swapping, is a necessity when writing copyless code, that developers need to get used to the paradigm of swap-pop-push-swap and that this is a skill that people need to level up in. but that’s a tall commitment, a lot of tasks like “remove the k elements from this UniqueArray at these indices in O(n) time” become extremely complex under the swapping paradigm, and like UniqueArray<T?>, it locks you into patterns that are really hard to climb down from if they later turn out to be local minima. this is qualitatively different from just adding local polyfills for Sequence API.
the bottom line here is that there are a lot of unanswered questions as to how we’re actually expecting users to derive net value from UniqueArray, which is a signal that we haven’t accumulated the necessary experience to inform what API it should have, what yet-to-be-shipped language features it depends on, and what responsibilities belong to the developer when using that API. so i just don’t think that UniqueArray is ready to graduate from swift-collections yet.