Thursday, February 16, 2017

Being a Mutable Collection is not Sufficient to be a MutableCollection

Ole Begemann:

A MutableCollection supports in-place element mutation. The single new API requirement it adds to Collection is that the subscript now must also have a setter.

[…]

MutableCollection allows changing the values of a collection’s elements, but the protocolʼs documentation stipulates that the mutation must neither change the length of the collection nor the order of the elements. Set canʼt satisfy either of these requirements.

[…]

All Dictionary would gain from conforming to MutableCollection and/or RangeReplaceableCollection would be methods that operate on Index values and (Key, Value) pairs, which is probably not compelling enough to invest anything in the conformance even if it were compatible with the typeʼs implementation.

Ole Begemann:

CharacterView does conform to RangeReplaceableCollection but not to MutableCollection. Why? A string is clearly mutable; it seems logical that it should adopt this protocol. Again, we need to consider the protocolʼs semantics.

[…]

However, the Characterʼs size in the underlying storage is not the same for all characters, so replacing a single Character can potentially make it necessary to move the subsequent text forward or backward in memory by a few bytes to make room for the replacement. This would make the simple subscript assignment potentially an O(n) operation, and subscripting is supposed to be O(1).

[…]

The final potential issue for CharacterViewʼs hypothetical MutableCollection conformance is Unicode and the complexities it brings. The existence of combining characters means that replacing a single Character can actually change the stringʼs length (measured in Characters) if the new character combines with its preceding character.

Previously: Swift 4 String Manifesto.

Comments RSS · Twitter

Leave a Comment