RFC: Conform IdentifiedArray to Mutable/RangeReplaceableCollection

[stephencelis]

We'd like to propose a couple changes to a data type that comes from one of the Composable Architecture's dependencies, and wanted to run those changes by the community to see if anyone finds any problems with them.

IdentifiedArray (from Identified Collections) is a data type that the Composable Architecture uses to embed child features in collections of elements of parent domains. The type can be employed in any application, though, and is a great tool to reach for when working with collections in SwiftUI state that render in ForEach views. It can even be handy to reach for in UIKit.

This data type is a defined as a wrapper around one of Apple's Swift Collections, in particular its OrderedDictionary. We leverage all of Apple's work to make the collection as efficient and performant to use as possible.

One decision Apple has made with OrderedDictionary is to withhold direct conformances to MutableCollection and RangeReplaceableCollection, offering "partial" conformances instead, which simply define a subset of functionality.

Because ordered dictionaries need to maintain unique keys, neither OrderedDictionary nor its elements view can conform to the full MutableCollection or RangeReplaceableCollection protocols. However, they are able to partially implement requirements: they support mutations that merely change the order of elements, or just remove a subset of existing members

—https://github.com/apple/swift-collections/blob/main/Documentation/OrderedDictionary.md#sequence-and-collection-operations

We've conservatively preserved this behavior on IdentifiedArray: it does not currently conform to MutableCollection or RangeReplaceableCollection, and instead provides "partial" conformances to the underlying ordered dictionary methods.

We'd like to relax this constraint. IdentifiedArray is not semantically an ordered dictionary, despite wrapping one under the hood. It leverages this data type for performance in accessing and modifying particular elements by their identifiers (by keying each element by its identifier), and maintains pre-/postconditions that the key and identifier are always identical. We expect IdentifiedArray to be treated more or less as an array with preconditions, and think it should benefit from all the same algorithms that Array does via these conformances.

For example, we really do think IdentifiedArray is a great data type for use in vanilla SwiftUI, but because it does not conform to MutableCollection and RangeReplaceableCollection, it already misses out on some great uses.

For one, MutableCollection will allow us to pass a binding of an identified array to a ForEach view:

ForEach($model.identifiedPeople) { $identifiedPerson in
  TextField("Name", text: $identifiedPerson.name)
  Toggle("Administrator?", isOn: $identifiedPerson.isAdmin)
}

And RangeReplaceableCollection will allow us to pass a binding of an identified array to a NavigationStack:

NavigationStack(path: $model.identifiedDestinations) {
  // ...
}

Can anyone think of any issues with supporting these conformances? Are there guarantees that MutableCollection and RangeReplaceableCollection provide that we are skirting, and even if there are, is it pragmatic to skirt them with preconditions?

We've opened a pull request with this functionality for those that want to take it for a spin and try to break it.

[tgrapperon]

I think this is a good change. IdentifiedArray is currently maybe too close to OrderedDictionary in terms of functionalities, and this will bring it closer to an Array of Identifiable elements, which it is semantically. Furthermore, if OrderedDictionary are supported as a first party collection type for features at some point, it will allow to better differentiate uses-cases.

I feel that the risk of inserting already existing ids is the same as accessing an Array out of bounds, or defining a Range with lowerbound > upperbound, and is something that the developer should check, as this is the contract for using the type.

While we're at IdentifiedArray features, one thing I'm currently missing in IdentifiedArray is a flat map operation that would produce an IdentifiedArray of other elements, in the same spirit as Dictionary.mapValues, and this RFC's safety enforcement. Something like:

extension IdentifiedArray where Element: Identifiable, ID == Element.ID {
  public func mapElements<T: Identifiable>(transform: (Element) -> T)
  -> IdentifiedArrayOf<T> where T.ID == ID {
    IdentifiedArray<ID, T>(uncheckedUniqueElements: self.map {
      let element = transform($0)
      precondition(element.id == $0.id, "…")
      return element
    })
  }
}

and maybe another version not restricted to Identifiable types (albeit I don't know about the performance of the precondition using the id KeyPaths). And maybe a lazy version. I'm using the less performant public APIs here, but we can probably do better if built-in.

I think this kind of transform would help to map domains in TCA, which can sometimes be cumbersome when you already have an IdentifiedArray but of the wrong type. Maybe some similar API already exists and I've missed it though.

[tgrapperon]

Also tangentially (and already evoked in the past), Identified should probably be expanded and relocated in swift-identified-collections when the navigation update is released.