[swift-dev] [Proposal] RangeReplaceableCollection should inherits from MutableCollection

[Ben Cohen]

> On Dec 5, 2017, at 2:48 PM, Jordan Rose via swift-dev <swift-dev at swift.org> wrote:
> 
> 
> 
>> On Dec 4, 2017, at 18:48, Brent Royal-Gordon via swift-dev <swift-dev at swift.org> wrote:
>> 
>>> On Dec 2, 2017, at 12:31 PM, Cao, Jiannan via swift-dev <swift-dev at swift.org> wrote:
>>> 
>>> I'd like to discuss the relation between RangeReplaceableCollection and MutableCollection
>>> 
>>> MutableCollection is a Collection type that can { set } any element with subscript(position: Index). (and also { set } for subscript(range: Range<Index>))
>>> 
>>> RangeReplaceableCollection requires a function replaceRange(_:with:)
>>> 
>>> If a type conforms to RangeReplaceableCollection, it means any of its range can be replaced, that includes the situation to replace only one element.
>>> So if some type conforms to RangeReplaceableCollection, it is sufficient to be a MutableCollection.
>>> So I think the RangeReplaceableCollection should conforms to MutableCollection should inherits from MutableCollection.
>> 
>> 
>> I thought this too a couple years ago, but it's not really true. `MutableCollection` requires not only that you be able to set elements, but also that when you do so, it doesn't change any of the indices in the collection. Some collections can't guarantee that. For example, `String` can't conform to `MutableCollection` because if you set some character in the middle of the string to a character that's a different size, it might move characters later in the string to different indices. So Swift lets you say `myString.replaceSubrange(myRange, with: newCharacters)`, but it doesn't let you say `myString[myRange] = newCharacters`.
>> 
>> `MutableCollection` and `RangeReplaceableCollection` are very similar in that they both involve changing a collection. But they are different *kinds* of changes to a collection, so it makes sense for a collection to support either one of them without supporting the other.
> 
> MutableCollection's subscript setter is also expected to take constant time (well, proportional to the size of a single element). That may not be the case for a range replacement implementation, even if it turns out the other elements in the collection don't have to move.
> 

The most common example a not-constant-time-element-updatable-but-still-range-replaceable-collection being String, since graphemes can vary in width in the underlying buffer.

For an example of why this is important, see this optimization for removing elements from a RangeReplaceableCollection:

https://github.com/apple/swift/pull/11576/files#diff-6290705036ea8e99c92cd1a8afc9494bR1095

When the collection is both range-replaceable and mutable, it can save time by not re-allocating the whole buffer, and just shuffling elements down in-place. But it needs to know that swapping two elements takes constant time for this to be an improvement and not an accidentally-quadratic disaster.


> Jordan
> _______________________________________________
> swift-dev mailing list
> swift-dev at swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev