Why does `RandomAccessCollection` demand `index(after:)` and `index(before:)`, but not `index(_:offsetBy:)`?

i am implementing a custom RandomAccessCollection with an Index type of UInt32.

struct SubSequence:RandomAccessCollection 
{
    typealias Index = Element.Offset 
    typealias SubSequence = Self 

    let indices:Range<Element.Offset>
    private 
    let storage:[Element]
    
    var startIndex:Element.Offset
    {
        self.indices.lowerBound
    }
    var endIndex:Element.Offset
    {
        self.indices.upperBound
    }
    subscript(offset:Element.Offset) -> Element 
    {
        _read 
        {
            yield  self.storage[.init(offset - self.startIndex)]
        }
    }
    subscript(range:Range<Element.Offset>) -> Self
    {
        .init(storage: self.storage, indices: range)
    }

    func index(before base:Element.Offset) -> Element.Offset
    {
        base - 1
    }
    func index(after base:Element.Offset) -> Element.Offset
    {
        base + 1
    }
    // func index(_ base:Element.Offset, offsetBy distance:Int) -> Element.Offset
    // {
    //     Element.Offset.init(Int.init(base) + distance)
    // }

somehow i am allowed to inherit the index(_:offsetBy:) implementation, but not the index(before:) or index(after:) requirements.

error: type 'Branch.Buffer<Element>.SubSequence' does not conform to protocol 'Collection'
    struct SubSequence:RandomAccessCollection 
           ^
Swift.RandomAccessCollection:3:28: note: candidate would match if 'DefaultIndices<Branch.Buffer<Element>.SubSequence>' was the same type as 'Range<Branch.Buffer<Element>.SubSequence.Index>' (aka 'Range<Element.Offset>')
    @inlinable public func index(after i: Self.Index) -> Self.Index
                           ^
Swift.RandomAccessCollection:11:19: note: protocol requires function 'index(before:)' with type '(Branch.Buffer<Element>.SubSequence.Index) -> Branch.Buffer<Element>.SubSequence.Index' (aka '(Element.Offset) -> Element.Offset')
    override func index(before i: Self.Index) -> Self.Index
                  ^
Swift.RandomAccessCollection:13:19: note: protocol requires function 'index(after:)' with type '(Branch.Buffer<Element>.SubSequence.Index) -> Branch.Buffer<Element>.SubSequence.Index' (aka '(Element.Offset) -> Element.Offset')
    override func index(after i: Self.Index) -> Self.Index
                  ^
Swift.Collection:27:10: note: protocol requires function 'index(after:)' with type '(Branch.Buffer<Element>.SubSequence.Index) -> Branch.Buffer<Element>.SubSequence.Index' (aka '(Element.Offset) -> Element.Offset')
    func index(after i: Self.Index) -> Self.Index

why? i would have assumed index(_:offsetBy:) is more important than index(before:) or index(after:).

It's very hard to get a clear idea of the problem here because of the fact that your code is a little underspecified: for example, what is Element.Offset?

In general, however, you shouldn't need index(after:) or index(before:) either, so long as you meet the constraints here: Index: Strideable, Index.Stride == Int, Indices == Range<Index>. If you don't meet those criteria you need to implement distance(from start: Index, to end: Index) and index(_:offsetBy:) as well as index(after:) and index(before:). If you find you truly don't need index(_:offsetBy:) and distance(from:to:) but you do need index(before:) and index(after:) then I'd consider jumping into your implementation of index(_:offsetBy:) in a debugger to see where it's actually coming from.

This is a specific case of a significant unsolved problem: how to avoid overlapping default implementations that are convenient, but end up not providing correct behavior when you don’t implement some of them in some cases.

In this case, Collection provides a default conformance for index(_:offetBy:) that does an O(n) walk using index(after:). This makes total sense for a non-random access collection, where you want that implementation. But it’s a disaster for a random-access collection, where implementing O(1) index(_:offetBy:) is the very thing that makes it random access. But you just have to know this – the compiler won’t require it of you.

Other examples include the accidentally recursive implementations you get when there are two requirements, both of which can be implemented in terms of the other, but when you implement neither end up being mutually recursive.

10 Likes

Element.Offset is some UnsignedInteger.

which RandomAccessCollection requirements are safe to default, and which need to be implemented explicitly? not gonna lie, this has me quite scared

Does this solution not work in general to 'undefault' inherited default implementations?

protocol P {
    func f()
}

extension P {
    func f() {
        print("P")
    }
}

protocol Q: P {
    func f()
}

extension Q {
    @available(*, unavailable)
    func f() {}
}

struct S: Q {} // error: unavailable instance method 'f()' was used to satisfy a requirement of protocol 'Q'

Sure, the author of RandomAccessCollection still has to remember to do this, but that seems much more of a reasonable ask than to require that conformers audit the behavior of every default implementation they might be inheriting.

It's explicitly spelled out in the docs:

The RandomAccessCollection protocol adds further constraints on the associated Indices and SubSequence types, but otherwise imposes no additional requirements over the BidirectionalCollection protocol. However, in order to meet the complexity guarantees of a random-access collection, either the index for your custom type must conform to the Strideable protocol or you must implement the index(_:offsetBy:) and distance(from:to:) methods with O(1) efficiency.


Yes, there are (and there have been implemented in the standard library) a number of interventions to improve diagnostics in simple cases, but overall expressivity is lacking in the language to encode complex logical expressions like "either you must have some associated type that conforms to some other protocol and/or implement one of a set of n related requirements (in which case the other n – 1 requirements are defaulted using that implementation) or else you must implement two of a set of m related requirements or else you may conform this type to some refining protocol, in which case a set of p requirements unique to that more refined protocol which you are required to implement can be safely called from the default implementations vended in extensions of that protocol for the requirements declared in this protocol which in turn call the m and n default implementations here which we'd otherwise have you not use—but in that case please don't write your own implementations of the m and n requirements which in turn rely on our default implementations of certain requirements in the refined protocol because that would cause infinite recursion."

(Conforming to the integer protocol hierarchy is super fun this way, speaking from experience...)

9 Likes

well UnsignedInteger implies Strideable, so why is inheriting index(_:offsetBy:) safe, but not index(before:) or index(after:)?

i guess my question is, usually when i use Index == Int, i don’t have to implement any of the RAC requirements besides the startIndex, endIndex, and subscript. when i use other index types with less and less similarity to Int, some of the defaults decay away, but i would have expected index(after:) to survive longer than index(_:offsetBy:).

In your code, the index type is Element.Offset, and whether that type is Strideable or conforms to UnsignedInteger is not inspectable from the code you’ve posted. My hunch is you’ve underspecified a constraint, or the constraint is conditional in some way, or you’ve hit the ineffable limits of associated type inference in some way. If you have a reduced example where you’re getting the same error with a concrete index type of UInt32, I would be surprised but please do share.

On re-reading, you’re asking about the index(before:) requirement, which isn’t specific to RandomAccessCollection. The default implementation constrains the stride type as outlined by @lukasa above.

1 Like

here is a self-contained example:

struct ExampleSubSequence<Element, Index>:RandomAccessCollection 
    where Element:Identifiable, Index:UnsignedInteger
{
    typealias SubSequence = Self 

    let indices:Range<Index>
    private 
    let storage:[Element]
    
    var startIndex:Index
    {
        self.indices.lowerBound
    }
    var endIndex:Index
    {
        self.indices.upperBound
    }
    subscript(offset:Index) -> Element 
    {
        _read 
        {
            yield  self.storage[.init(offset - self.startIndex)]
        }
    }
    subscript(range:Range<Index>) -> Self
    {
        .init(storage: self.storage, indices: range)
    }

    // func index(before base:Index) -> Index
    // {
    //     base - 1
    // }
    // func index(after base:Index) -> Index
    // {
    //     base + 1
    // }
    func index(_ base:Index, offsetBy distance:Int) -> Index
    {
        Index.init(Int.init(base) + distance)
    }
    
    init(storage:[Element], indices:Range<Index>)
    {
        self.storage = storage 
        self.indices = indices
    }
}

As I wrote before, your first post in this thread is inaccurate because you're not using a concrete Index type of UInt32, which works just fine: make Index non-generic in the reduced example you've just posted and instead write typealias Index = UInt32 inside the body of your type, and you'll see that the code now compiles without a hitch.

This indicates, as I said, that there is something under-constrained about your index type with respect to the constraints specified in the relevant default implementations. Specifically, one can also make your example compile (while still keeping Index generic) by additionally specifying Index.Stride == Int.

While all fixed-width unsigned integer types vended by the standard library conform to Strideable with Stride == Int, this is not a requirement of UnsignedInteger. However, many useful operations generic over Strideable need to specify the Stride type in order to do the work.

In the case of these default implementations for index(before:) and index(after:) specifically, I'd presume this constraint is specified because the distance between collection indices is always a value of type Int:

The default implementation of these index methods make use of a one-to-one correspondence between how distance between two indices is reckoned by the collection type and how distance is reckoned by the underlying strideable index type; that is to say, index(after:) advances the strideable value by 1 and index(before:) advances the strideable value by -1.

(A custom implementation doesn't have to do this: there is nothing that says a collection type can't choose to use indices that are only even numbers of some non-numeric strideable type with DoubleWidth<Int> stride.)

However, for the default implementations that advance the strideable type by 1 or -1 as appropriate to move from one index to the next, the requirement for Stride == Int fixes the representable range of distances for the underlying stride type to be identical to the representable range of distances for collection indices so that overflow isn't an issue, thus greatly simplifying matters.

1 Like

Shouldn't this be sort of optional "opt-in", like this (pseudo code):

protocol SlowOffsetByImplementation {}

extension SlowOffsetByImplementation {
    func index(_:offetBy:) {
        // implements index(_:offetBy:) in terms of index(after:)
    }
}

// whoever wants to use it:

extension MyCollection: SlowOffsetByImplementation {}

// everyone else:

protocol OtherCollection {...} // Error: index(_:offetBy:) is needed

this was the crucial thing i needed, thanks!

1 Like