# Index Invalidation in subscript

**URL:** <https://forums.swift.org/t/index-invalidation-in-subscript/27961>\
**Category:** Using Swift\
**Created:** [August 16, 2019, 5:14pm UTC](https://forums.swift.org/t/index-invalidation-in-subscript/27961 "2019-08-16T17:14:41Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![lukasa](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lukasa/32/1232_2.png) [@lukasa](https://forums.swift.org/u/lukasa)\
**Post date:** [August 16, 2019, 5:14pm UTC](https://forums.swift.org/t/index-invalidation-in-subscript/27961/1 "2019-08-16T17:14:41Z")

</div>

On this forum we have previously discussed the rules around index invalidation: see [NSString Indices invalidated potentially after it has been bridged to String and manipulated](https://forums.swift.org/t/nsstring-indices-invalidated-potentially-after-it-has-been-bridged-to-string-and-manipulated/26799) for at least one example.

I want to ask a clarifying question: is it acceptable to invalidate indices when assigning to a `MutableCollection` subscript?

As a hypothetical, if I was rebuilding `Array`, would it be acceptable for me to use the following implementation?

```swift
extension MyCollectionStorage {
    private var backingStore: UnsafeMutableRawPointer

    struct Index {
        fileprivate var backingPointer: UnsafeMutableRawPointer
    }

    subscript(_ index: Index) -> UInt8 {
        get {
            precondition(self.isValidIndex(index)) // Pointer is in bounds
            return index.backingPointer.load(as: UInt8.self)
        }
        set {
            precondition(self.isValidIndex(index)) // Pointer is in bounds
            // This isn't quite right, but I want it for the example
            if !isKnownUniquelyReferenced(self) {
                let oldBaseAddress = self.backingStore
                let pointerOffset = index.backingPointer - oldBaseAddress
                self.backingStore = self.copyBackingStore() // Left to the reader
                let newPointer = self.backingStore + pointerOffset
                newPointer.store(newValue)
            }
            index.backingPointer.store(newValue)
        }
    }
}

```

The point of this example is to note that, in the `!isKnownUniquelyReferenced` case, we invalidate the indices. There is no data structure in the standard library so far as I know that does this today, but the `MutableCollection` documentation is silent on whether a `MutableCollection` is _allowed_ to do this.

What's the guidance here? May this kind of index invalidation occur, or are indices required to be stable across subscript `set`?

---

<div class="post-metadata">

**Author:** ![SDGGiesbrecht](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/sdggiesbrecht/32/4768_2.png) [@SDGGiesbrecht](https://forums.swift.org/u/SDGGiesbrecht)\
**Post date:** [August 16, 2019, 6:10pm UTC](https://forums.swift.org/t/index-invalidation-in-subscript/27961/2 "2019-08-16T18:10:46Z")

</div>

I think (albeit hesitantly) that `MutableCollection` semantically requires indices to remain valid.

1. Without it, [`swapAt(Index, Index)`](https://developer.apple.com/documentation/swift/mutablecollection/3018230-swapat) doesn’t even make sense. How would you perform two separate insertions without the first invalidating the second?

2. The documentation seems to imply it under “[Conforming to the MutableCollection Protocol](https://developer.apple.com/documentation/swift/mutablecollection#2846000)”:

3. See the following tangent in another thread, interspersed with other stuff, but starting about here:

> [@Implementing a Collection.removingIndices(\_:)](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/24):
>
> Does the constraint “MutableCollection & RangeReplaceableCollection” provide sufficient guarantees of index stability for this?

I agree it would be helpful if the documentation stated it plainly one way or the other.

---

<div class="post-metadata">

**Author:** ![lukasa](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lukasa/32/1232_2.png) [@lukasa](https://forums.swift.org/u/lukasa)\
**Post date:** [August 17, 2019, 8:50am UTC](https://forums.swift.org/t/index-invalidation-in-subscript/27961/3 "2019-08-17T08:50:59Z")

</div>

> [@SDGGiesbrecht](#):
>
> Without it, [`swapAt(Index, Index)`](https://developer.apple.com/documentation/swift/mutablecollection/3018230-swapat) doesn’t even make sense. How would you perform two separate insertions without the first invalidating the second?

This seems like the most compelling argument to me, but we should definitely have a better documentation story.

---

<div class="post-metadata">

**Author:** ![johannesweiss](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/johannesweiss/32/38183_2.png) [@johannesweiss](https://forums.swift.org/u/johannesweiss)\
**Post date:** [August 17, 2019, 10:30am UTC](https://forums.swift.org/t/index-invalidation-in-subscript/27961/4 "2019-08-17T10:30:44Z")

</div>

> [@lukasa](#):
>
> > Without it, [`swapAt(Index, Index)`](https://developer.apple.com/documentation/swift/mutablecollection/3018230-swapat) doesn’t even make sense. How would you perform two separate insertions without the first invalidating the second?
> 
> This seems like the most compelling argument to me, but we should definitely have a better documentation story.

I agree the `swapAt` argument is compelling, however _it is_ a [customisation point](https://github.com/apple/swift/blob/ad50a39b120343f4827edb0a5a7013bb586306a6/stdlib/public/core/MutableCollection.swift#L168) so the underlying `MutableCollection` can make that work.

Furthermore, I think that for a self-slicing byte containers like `Data` using an opaque version of the underlying pointers as @lukasa outlined above would indeed be a very compelling design. It would probably be slightly more efficient and also would correctly prevent the accidental use of indices of one `Data` instance to index another. As @lukasa says that does (for CoWing value types ) however require that indices may be invalidated on every mutating operation.

In any case, this is something that crucially needs to be documented. I would also argue that we should have some sort of 'collection compatibility test' which verifies some basic assumptions about `(Mutable)Collection`s.

(_edit below_)

> [@SDGGiesbrecht](#):
>
> The documentation seems to imply it under “[Conforming to the MutableCollection Protocol](https://developer.apple.com/documentation/swift/mutablecollection#2846000)”:
> 
> > A value stored into a subscript of a `MutableCollection` instance must subsequently be accessible at that same position. That is, for a mutable collection instance `a` , index `i` , and value `x` , the two sets of assignments in the following code sample must be equivalent:
> > 
> > ```swift
> > a[i] = x
> > 
> > ```
> 
> let y = a[i]
> 
> // Must be equivalent to:  
> a[i] = x  
> let y = x
> 
> > ```swift
> > 
> > ```

Re-reading this, I think this is the documentation I was looking for and it seems to explicitly forbid using an opaque version of the underlying pointers as indices ☹. Because this

```swift
a[i] = x

```

could trigger a CoW which would then invalidate `i` for the value `a` so the following `a[i]` would no longer work.

CC @lorentey/@ben-cohen

---

<div class="post-metadata">

**Author:** ![sveinhal](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/sveinhal/32/3992_2.png) [@sveinhal](https://forums.swift.org/u/sveinhal)\
**Post date:** [August 17, 2019, 12:05pm UTC](https://forums.swift.org/t/index-invalidation-in-subscript/27961/5 "2019-08-17T12:05:32Z")

</div>

> [@johannesweiss](#):
>
> I would also argue that we should have some sort of 'collection compatibility test' which verifies some basic assumptions about `(Mutable)Collection` s.

+1