Can a group of weak references conform to Collection?

Using Swift
,
1

I have a type that collects weak references, which you can iterate over and append to. I want it to conform to RangeReplaceableCollection, but I don't think I can do anything more specific than Sequence.

The type itself is a classic pointer-length-capacity triplet, where the pointer is to a buffer of weak references. Once length == capacity, before trying to realloc, it scans the buffer for nils that it can drop out. It only performs a reallocation if it can't remove enough nils to make room for the new elements.

The problem with conforming it to Collection is, of all things, subscript(_:). If the index type is just the index into the buffer, other threads could cause the weak reference to drop out from under you, and so indices could become invalid without apparent mutations to the collection.

I can think of two ways to fix this, neither of which is satisfying.

The first is to make the index type also hold a strong reference to the object. I guess this works, but I'm worried it's liable to produce footguns, when users don't realize they're holding a strong reference through the index.

The second is to make the element type T? instead of T. This is misleading since the Iterator skips nils, but it would make the subscript implementable.

The third option, I suppose, is to implement many (but not all) of the collection operations without actually conforming to the protocol. I'm worried this is what I'll have to do, unless I can justify one of the other two behaviors. Is there a way I can implement the protocol without changing the semantics of the type?

1 Like
2

Not being a Collection seems like an inherent property of the data structure you're offering, not an implementation limitation. If the nth item in the sequence can change from x to y because x (or some other object earlier in the sequence) has been collected, then the sequence doesn't have stable indices.

3 Likes
3

I'd do your 2 or 3, so the indices are stable, but the elements could be nil. Or the 4th option, which will work similarly:

struct WeakObjectHolder {
    weak var object: AnyObject?
}
var elements: [WeakObjectHolder] = []

I wonder what is the intended use of this data structure?

4

I wanted something similar to what you’ve described, but that would reuse the space left behind by nils rather than constantly growing and having to filter out the nils manually. I don’t have a practical application yet, this was mostly just a self-imposed exercise. In part because I’ve had to reimplement common data structures in C++ for class before, I figured it would be easier to reimplement the vector from scratch instead of anticipating when a standard Array would try to resize.

5

If you are using this structure, then on insert you'd need to scan the elements, find the first entry with nil and replace it with the new element, if there are no nils then append a new entry.

The reason I asked, if for example that was to implement a cache - that'd be the wrong approach.

I'd only do this once there's a practical need - the particular application might heavily influence the design of this data structure.