Preparing the iteration ABI for move-only types

Development Compiler
11

We've come up with some other design problems that could impede forward compatibility between Collection and future move-only types. There are a number of operations that produce wrapper collections, like indices and lazy, and some of these are protocol requirements. For example, the default implementation of indices in its current form needs to take a copy of the collection in order to be able to manipulate the collection's indices, something like this:

extension Collection {
    var indices: IndicesCollection<Self> {
         return IndicesCollection(base: self) // need to copy or consume self here
    }
}

struct IndicesCollection<Base: Collection>: Collection {
    var base: Base
}

But this implementation would not be valid for a move-only collection without consuming the original collection. However, it wouldn't be particularly useful for indices to be the final thing you can do with a collection, since you need the original collection to do anything with the index values you get from indices. Property implementations can now yield borrowed values using accessor coroutines, which are naturally scoped to the parent value, so we could conceivably have a different default implementation of indices for move-only types:

extension Collection where Self: !Copyable { // strawman syntax
    var indices: IndicesCollectionMoveOnly<Self> {
        withUnsafePointer(to: self) {
            yield IndicesCollectionMoveOnly(base: $0) // we can safely vend the pointer here, since it's moveonly and borrowed so can't escape
        }
    }
}
struct IndicesCollectionMoveOnly<Base: Collection & !Copyable>: Collection & !Copyable {
    var base: UnsafePointer<Base>
}

which would mean that collection types supporting both move-only and copyable elements need to conform two different ways for move-only and copyable collections, which is not great for generic code that would want to work over all instances of such a type. This problem affects every wrapper collection to some degree, but it's a forward compatibility concern specifically for indices and subscript(Range<Index>) -> SubSequence because these are requirements of the Collection protocol. Protocols can introduce new requirements with default implementations in new library versions, so there are a couple of ways we could deal with the existing requirement in the present time:

  • Leave the protocol requirements as-is, and in the future, make them a "conditional requirement" only for copyable types. @Douglas_Gregor has some philosophical objections to any kind of "conditional requirement" feature, but because copyability is a fundamental property of types and not a general protocol conformance that can be added post-hoc, I think that at least makes the feature easier to introduce in this limited case.
  • Make theses requirements __consuming for now. Like I said, this would make them effectively useless for move-only types, but they would at least be unconditionally implementable, so we would be less likely to be blocked by implementing other language features in order to implement move-only types.

In either situation, we ought to still be able to introduce new, more general requirements that work with all types in a future Swift that supported move-only types, once that feature is designed and implemented.

There's another thorny issue having to do with the mutating subscript(Range<Index>) -> SubSequence requirement that MutableCollection and RangeReplaceableCollection introduce. Ideally, mutation through a slice like this would be done in-place when possible, but because Slice and other typical implementations of SubSequence must wrap the original collection's buffer, copy-on-write triggers because there are two independent references. Even with move-only types, this is tricky, because an exclusive, mutating borrow could allow the borrowed slice to be swapped with another move-only slice value unrelated to the original value, unless we had some way of marking mutating borrows as "noescape" or explicitly lifetime-scoped to their parent values. Beyond just basic support for move-only types, It is likely that providing a good experience with strong performance guarantees for divide-and-conquer sorts of mutating algorithms on collections at all may need a new protocol design, perhaps taking advantage of move-only types to enforce safe partitioning in the manner of Rust's Rayon library.

If we were to try to make in-place modification through slices possible at least in limited situations today, @John_McCall has proposed a number of possible solutions. We could say that the Slice that you receive from a range subscript operation starts out with a non-owning reference, but that any copy or move of that initial slice causes the reference to become strong. A similar technique might in theory also address the borrow/consume issue with nonmutating wrappers like indices; if the indices wrapper type could start out with a non-owning reference to its parent collection, but upgrade that to an independent copy if the wrapper is copied, then one implementation using that one type might be sharable among move-only and copyable types (since you would only ever be in the borrowed state with a move-only type, whereas the promotion from borrow to independent copy when copying or moving the value provides the necessary generalization for copyable values).

Although an interesting theoretical design, this would be a fairly big fundamental change to Swift's implementation model, in which copies currently do not alter the state of copied values in any but very controlled ways (like reference counting), so it's unlikely that we'd be able to implement this in the time we have remaining for Swift 5. Furthermore, even with all that work, we could still end up with an unsatisfying answer to the in-place slicing problem, since the in-place performance guarantee would still come with many caveats: resizing, copying, or other operations on a slice could force the reference to become strong unexpectedly and defeat in-place modification, leaving users still wanting a stricter in-place modification interface with stronger guarantees, which we would only be able to deliver in the future with the support of move-only types. It therefore isn't clear that it's worth expending large effort now for a design that'd still be a compromise. Our best short-term effort might best be spent only ensuring that our existing protocol designs don't actively impede move-only types from conforming in the future.

5 Likes