RFC: Deque: should it have an opaque index?

Related Projects Collections
2

Deque's initial implementation had opaque indices, and I tried very hard to make it work.

Unfortunately, it felt pointlessly pedantic, and it actually interfered with the understandability of the API -- because it obscured how deque indices actually work. I've eventually come to the conclusion that unless there is some strong reason not to do so, random access collections should always just use array-style integer offsets as their index. It's to the point that I consider it a bug that RandomAccessCollection doesn't have an Index == Int requirement.

(Conversely, I feel equally strongly that non-random-access collections that use integer indices should be abolished. Especially if the indices aren't even consecutive integers -- looking at you, LazyFilterCollection. ಠ_ಠ)

RandomAccessCollection effectively requires Index to be equivalent to integers, anyway.

That's super cool because you can detect (in debug mode) very common misuses such as:

var d = CircularBuffer()
d.append(1)
d.append(2)

let startIndex = d.startIndex
d.popFirst() // <- index mutation!

print(d[startIndex]) // used an index that has been invalidated by mutation

In my view, there is no misuse here. Using integer indices makes it abundantly clear that the only index that is actually invalidated here is the original endIndex. The original startIndex may now be pointing to a different element, but it is still a perfectly valid index. Wrapping the integer offsets into a custom type doesn't change this, it merely obscures how this works. (The general-purpose Deque shouldn't artificially force-invalidate its indices -- the way array-style indices work is a feature, not a bug. This isn't the same situation as Set and Dictionary, where bucket indices may or may not accidentally end up pointing to a valid element even after invalidation: in Array/Deque/OrderedSet/OrderedDictionary, indices are guaranteed to follow a very straightforward logic, and people using such types generally write their code to rely on this.)

I think that artificially forcing people to regenerate their indices after every mutation is, in general(!), the wrong approach. Of course, in specific use cases, one may want to encourage more careful indexing, and in those specific cases it is certainly still possible to wrap Deque in a custom collection type that adds its own index validation logic. (Why even provide indices though?)

FWIW, if I was given a random-access collection that insisted on me spelling foo[n] as foo[foo.index(foo.startIndex, offsetBy: n)], I'd either go look for a different implementation, or I'd just set up something to work around the unhelpful design, like this extension:

extension RandomAccessCollection {
  /// Complexity: O(1)
  internal subscript(_offset offset: Int) -> Element {
    self[self.index(self.startIndex, offsetBy: offset)]
  }
}

(I'm pretty sure I'd have argued for the same Deque design even if we were able to conveniently access elements at integer offsets from the start of any collection. SE-0265 was returned for revision 17 months ago -- we have some ideas on how to incorporate the review recommendations, but nothing that is obviously the right approach, and frankly adding complicated language sugar to simplify indexing isn't a top priority for anyone right now.)

5 Likes