Unexpected behaviour when implementing RangeReplaceableCollection in a class

Using Swift
1

I have the following UndoableArray class which acts like a normal Array but also has undo support:

public final class UndoableArray<Element>: RandomAccessCollection, RangeReplaceableCollection {

    public typealias Index = Array<Element>.Index
    
    private(set) var elements: [Element]

    public init() {
        self.elements = []
    }
    
    public init<S>(_ elements: S) where S: Sequence, Element == S.Element {
        self.elements = Array(elements)
    }

    public var startIndex: Index {
        return elements.startIndex
    }
    
    public var endIndex: Index {
        return elements.endIndex
    }
    
    public subscript(position: Index) -> Element {
        get {
            return elements[position]
        }
        set {
            let oldValue = elements[position]
            elements[position] = newValue
            recordUndo { [self] in
                self[position] = oldValue
            }
        }
    }
    
    public func replaceSubrange<C>(_ subrange: Range<Array<Element>.Index>, with newElements: C) where C: Collection, Element == C.Element {
        let oldElements = Array(elements[subrange])
        elements.replaceSubrange(subrange, with: newElements)
        let subrange = subrange.lowerBound..<(subrange.lowerBound + newElements.count)
        
        recordUndo { [self] in
            replaceSubrange(subrange, with: oldElements)
        }
    }

}

func recordUndo(_ block: () -> Void) {}

The problem is that RangeReplaceableCollection seems to assume that the implementing type is a struct, while I have a class. For example the + operator is documented as

Creates a new collection by concatenating the elements of a collection and a sequence.

but the following code shows that the left collection is mutated instead of creating a new one:

let a = UndoableArray([0])
let b = UndoableArray([1])
let _ = a + b
print(a.elements, b.elements) // output: [0, 1] [1]

Some time ago I added the following code because apparently filter was acting weird, but at the moment I'm unable to reproduce any unexpected behaviour:

public func filter(_ isIncluded: (Element) throws -> Bool) rethrows -> [Element] {
    return try elements.filter(isIncluded)
}

I would change final class to struct, but then I get compiler errors like

recordUndo { [self] in
    self[position] = oldValue // error: Cannot assign through subscript: 'self' is an immutable capture
}

What would be the best way to solve these issues? I'm afraid that a custom implementation of + would not be enough, and one day I'll use another method of RangeReplaceableCollection without noticing soon enough that it behaves incorrectly.

2 Likes
2

Is there a reason not to make UndoableArray a struct?

It is the responsibility of a conformer to implement the intended semantics, as well as the syntax, of the adopted protocol. If UndoableArray conforms to RangeReplaceableCollection, it is your responsibility to ensure it implements every method of the protocol with the intended semantics.

Protocols are not just bags of syntax has practically been Swift's tagline since v1.

1 Like
3

If RangeReplaceableCollection.+ is implemented as

extension RangeReplaceableCollection {
  public static func + <Other: Sequence<Element>>(lhs: Self, rhs: Other) -> Self {
    var result = lhs
    result += rhs
    return result
  }
}

then a class can never correctly implement the protocol, and that should be documented. The documentation currently doesn't mention this fact, as far as I can tell.

4

... then you need to implement it yourself when the conformer is a class. The + methods are protocol requirements, which means that a conformer can, and must, override them when the default implementations are not correct.

1 Like
5

I don't think there's a generally-good solution here (for conformers to somehow know they need to override default implementations), but just chiming in with the current implementation of RangeReplaceableCollection.+:

@inlinable
public static func + <
  Other: Sequence
>(lhs: Self, rhs: Other) -> Self
where Element == Other.Element {
  var lhs = lhs
  // FIXME: what if lhs is a reference type?  This will mutate it.
  lhs.append(contentsOf: rhs)
  return lhs
}

So, yes, this will require an overload for now.

In theory, since RangeReplaceableCollection does require init(), the implementation could be updated to something like

@inlinable
public static func + <
  Other: Sequence
>(lhs: Self, rhs: Other) -> Self
where Element == Other.Element {
  if self is AnyObject.Type {
    let res = self.init()
    res.append(contentsOf: lhs)
    res.append(contentsOf: rhs)
    return res
  } else {
    var lhs = lhs
    lhs.append(contentsOf: rhs)
    return lhs
  }
}

but I don't know whether this would have a significant performance impact or not.

6

Unfortunately, the + methods are not dynamicallly dispatched protocol requirements but statically dispatched protocol extension methods that can only be shadowed but not overridden. So indeed, as @itaiferber shows, the fix has to come from the stdlib but there could be performance impacts.

1 Like
7

As @itaiferber points out, this is definitely a known issue within the + implementation. The primary thing that you're running into is that the RangeReplaceableCollection protocol implementations largely have an assumption of value semantics, though I don't know if that's really documented anywhere.

That said, it would be worth exploring whether the current implementation still has a performance win associated with it over one that creates the result from scratch. The Array case is the performance-critical one, so we may be able to provide a concrete overload that handles that directly if needed.

8

Like I mentioned, I would like to make it a struct, but then I don't know how I would implement the undo support which needs to capture and modify the object itself.

9

I'm not sure I understand why recordUndo is a global function in this case. I guess the idea is that you're building up a global list of operations across multiple types that some undo manager can invoke later to unwind the state?

I think that kind of design is fundamentally incompatible with value types, because it relies on the fact that anyone else who has a reference to the array in the program has the exact same array identity and not a copy that was made implicitly by the language.

10

In my code there is a shared undo manager which has a method like recordUndo, but in the sample code I made it a global function to try to simplify things. I also assumed that a class is necessary in this case, but not knowing which methods of RangeReplaceableCollection have a default implementation that assume it's a struct worries me. I think making it a struct would simplify things overall (because currently I always have to think whether the array I'm dealing with is a value or class type), but I don't know if that's possible. In my code every instance of UndoableArrary is always guaranteed to exist as long as the undo manager exists, so perhaps recordUndo could do some unsafe pointer magic that converts self to a mutable object... but I know too little of low-level stuff to come up with a feasible solution.