A new way of offsetting

The "Safe Random Access Collection Element" thread is yet another why-can't-we-get-to-another-collection-element-safely thread. I came up with sample methods to do that in two posts. Maybe we should pull the trigger and finally add them.

Basically, the problem is the need for custom boilerplate code to safely traverse amongst indices. The index part of the Collection API mostly does not use the usual way to confirm failure: nil returns. The one method that does is too complicated for general use. Outside of Collection wrappers, I've only used index(_: offsetBy: limitedBy) with a limit that isn't either endIndex or startIndex a few times. And you have to explicitly mention which limit to use based on the sign of the offset amount. The new "elementIndex" API always gives you either an Index value that can be dereferenced to a Element, or nil. There's versions for a general offset, one step forward, and one step backward from a known-good index value.

There's a fourth version that is a general offset from startIndex. It can be used instead of providing an oft-requested I-want-to-subscript-from-0..<count member. The advantage of easing Index-to-offset conversion is Index-dereferencing is O(1) while direct offset subscripting is linear for collections that are not random-access.

That last capability could be considered a counter to the (fortunately?) suspended SE-0265 proposal. The new methods may lessen the "holding it wrong" foot-gun the current indexing API has, without going to the accidentally quadratic... accidentally quadratic everywhere leg-shotgun of SE-0265. (And SE-0265 has correctness issues of what happens if at least one coordinate of an offset range isn't valid.)

On a separate related note, maybe we could add a single-element replacement API:

extension RangeReplaceableCollection {

    /// Replaces the element at the given index for one with the given value.
    ///
    /// Calling this method may invalidate any existing indices for use with
    /// this collection.
    ///
    /// - Parameters:
    ///    - i: A valid index of the collection.  Must be less than `endIndex`.
    ///    - other: The new element to add to the collection.
    /// - Returns: The element value that was originally at `i`.
    /// - Postcondition: Consider *d* to be `distance(from: startIndex, to: i)`
    ///   before the call to this method.  Now consider *j* to be
    ///   `index(startIndex, offsetBy: d)` after the call to this method.  Then
    ///   `self[j]` is the same as `other`.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the collection.
    @inlinable
    @discardableResult
    public mutating func replaceElement(at i: Index, with other: Element)
        -> Element {
        defer {
            replaceSubrange(i..<index(after: i), with: CollectionOfOne(other))
        }
        return self[i]
    }

}

This could "work around" String not having a direct element-level setter.

This seems semantically risky to me. In particular, it would be reasonable to assume this holds: collection.replaceElement(at: idx, with: e); assert(collection[idx] == e), but it won’t in general with strings because a Character may merge with one or both of its neighbours.

1 Like

It may be problematic, but for a different reason. In your analogy, you can't actually use idx for the second part. Calling a RangeReplaceableCollection method that adds/removes/replaces at least one element voids all outstanding Index values. It works for Array, since it uses the offsets as its index values, but probably won't work for any other collection.

Yes, it’s a huge problem with the design of RRC. It basically means you cannot write a correct, generic replaceAll function which repeatedly calls replaceSubrange for every appropriate range of elements.

There’s a bug for it: [SR-12810] `RangeReplaceableCollection` methods should return index ranges. · Issue #55257 · apple/swift · GitHub and I remember mentioning the problem in another bug report all the way back in 2016: [SR-2689] String.CharacterView does not shift endIndex correctly · Issue #45294 · apple/swift · GitHub (although back then, the thing that would have worked best for my use-case was some kind of IndexDisplacement associated type that could be used to adjust any previously-obtained Indexes and make them valid for the collection’s state post-mutation).

Whatever we do, we badly need to fix/replace RRC.

It’s more appropriate to be in MutableCollection (which String does not conform to).

Besides returning the old value, replaceElement(at: with:) is a rip-off of MutableCollection's single-element subscript. Its point is it's supposed to be similar functionality for RangeReplaceableCollection types.