Alternative implementation of MutableCollection conformance for OrderedDictionary.Values

[JonathanStorey]

As currently implemented (and documented!) when sorting or swapping the OrderedDictionary.Values, the keys do not change positions. For most use cases, I suspect that this is not the desired (or expected) outcome. For example if the key is a unique identifier for a user (a UUID perhaps) and the value is the user's name, sorting based on the name disassociates the user names from their prior identifiers. I am struggling to come up with a situation where this kind of sorting would be desirable.

Potential Fix #1:

• remove MutableCollection support from OrderedDictionary.Values
• could still support a subscript setter allowing for changing of the value while not supporting sort(by:) or swapAt()
• (positive) would avoid potentially unexpected key value dissociation
• (positive) would still allow for updating of value within Values collection
• (negative) would lose support for mutable values in SwiftUI ForEach

Potentional Fix #2:

• support conditional conformance to MutableCollection only when values conform to Identifiable
• (positive) sorting and swapping would preserve keys... it would be equivalent to sorting based on the dictionary elements
• (negative) in the case of Identifiable conformance, sorting if there were multiple matching IDs it would result in "unexpected behavior" (just as it does in SwiftUI ForEach). Throw an error; or decline to perform update?
• (negative) what is the point of the hashable key in dictionary if your value is already guaranteed to be unique based on a hashable identifier?
• (positive) despite the above negatives, SwiftUI already mandates id support to use in Lists.

Additional Thoughts: The current implementation of MutableCollection includes support for sorting and swapping which can lead to unclear behavior in this scenario and others that I have encountered. I wish that Mutable Collection was restricted to using the subscript setter without support for swapping. In an alternate universe, I would have favored a separate protocol perhaps called SwappableCollection that supported swapAt() and sorting. SwiftUI adds to the MutableCollection confusion in that it malfunctions if the included identifier changes or is not unique. It seems to me that we are missing a collection type that would provide first class support in SwiftUI... IdentifiableCollection?.

[lorentey]

Modifying the semantics of (or removing) the MutableCollection conformance would be a (severely) source breaking change. This package is source stable -- such changes simply aren't an option.

The current behavior of OrderedDictionary.Values matches that of Dictionary.Values -- I think it would be highly undesirable to change one but not the other.

Additionally, the Values view is intentionally designed so that mutations of it can never(*) affect the keys of the dictionary -- they are strictly isolated to the values themselves. Its mutations are especially not allowed to mutate the hash table, as would be necessary to implement key swapping.

(*: Except for wholesale assignments such as d1.values = d2.values, which replace the entire underlying dictionary. This is an undesirable wrinkle (originating from the stdlib) that we now have to live with.)

That said, we could certainly add a separate view for this purpose, with a different name.

Highly relevant prior work is @stephencelis and @mbrandonw's swift-identified-collections package, which implements this view as a top-level type.

Additional Thoughts: The current implementation of MutableCollection includes support for sorting and swapping which can lead to unclear behavior in this scenario and others that I have encountered. I wish that Mutable Collection was restricted to using the subscript setter without support for swapping.

This restriction is not implementable in practice. If a collection type implements a subscript setter that does not invalidate indices, then that means that it also inherently supports swapping/sorting/reversing/shuffling/etc. operations. These operations can be (and often are) trivially implemented in terms of subscript assignments.

On the other hand, I do strongly wish we had a separate standard protocol that specifically modeled reorderable collections -- ones that can implement swapAt, but can't support arbitrary subscript assignments. This would be a weaker form of MutableCollection, and it would sit between that and Collection in the protocol hierarchy:

MutableCollection → PermutableCollection → Collection

Two examples for collection types that would want to be permutable but not fully mutable are, of course, OrderedSet and OrderedDictionary themselves. (One problem is that there just aren't many more examples in practice, which would make this protocol an underutilized complication.)

[JonathanStorey]

@lorentey Thank you for the explanation and background. Unsurprisingly, the choices made for OrderedDictionary.Values are well thought out and are indeed well documented. I now better understand those choices.

I must admit that I'm still somewhat hung up on the semantics of "swap" and "sort" for dictionary values and even more so for an "ordered dictionary". If my son told me he was swapping the definitions in a dictionary, perhaps I would think he was switching the definitions for two words with each other. If he told me he was swapping definitions in an indexed list of word/definition pairs, it would be even less clear. If he told me that he was sorting the dictionary definitions, I would never expect all of the definitions to not match the original words. I have no doubt that my definition of "sort" is not the mathematically rigorous definition that Swift intends. However, in a collection that is both ordered and keyed, there remains ambiguity in my mind.

I think the functionality that I am envisioning is perhaps more collection and less dictionary. After my initial post, I began working on a KeyableCollection (in progress) which has some overlap with OrderedDictionary and IdentifiedCollection (but uses an underlying array.) It has a dedicated failable replace function. The main consideration in such a collection type is whether to conform to MutableCollection with the heavy cost of needing to throw errors or failing to update if there is a duplication of keys.

+1 for PermutableCollection

[lorentey]

We do have the option of adding a new view (or top-level wrapper) that has IdentifiedArray semantics; doing that will be an obvious thing to consider when we get closer to integrating this code into the stdlib.

[JonathanStorey]

Yes, but... every potential solution that I can think of suffers from the same underlying problem: Enforcing a unique Element.ID is fundamentally incompatible with MutableCollection. For example, IdentifiedArray fails if the Element.ID is mutated, despite the fact that this is not prohibited by the Identifiable protocol. I can not imagine a first-class collection or view, where such failures would be reasonable.

Are there other alternative approaches that I am missing?

I think I am beginning to prefer a KeyableCollection protocol that does NOT conform to MutableCollection and borrows semantics from the OrderedDictionary library. MutableCollection conformance could be added for Collections where the Element is guaranteed to have a stable ID.

protocol KeyableCollection : Collection {

    associatedtype Key: Hashable
    associatedtype Element
    func key(at index: Int) -> Key
    
    // removes element at the supplied index
    @discardableResult mutating func remove(at index: Int) -> Element
    
    // Updates element if matching element with the same key is present.  If no
    // matching key, it inserts the element at the included index.
    @discardableResult mutating update(_ element: Element, insertingAt index: Int) -> Element?
    
    // Replaces element at the included index.  The new Element must either match keys with
    // the item being replaced OR have a distinct key.  If operation is successful, it
    // will return the old element.
    @discardableResult mutating replace(elementAt index: Int, with newElement) -> Element?
}

Thinking more broadly, I've been experimenting with other options to address this seeming incompatability between MutableCollection and Element.ID? For example:

protocol ManagedIdentifiable : Identifiable  { // the collection would manage the id

    var id: UUID? { get set } // includes mandated set

}

struct ManagedArray<Element: Managed> {}

extension ManagedArray: MutableCollection where Element: ManagedIdentifiable {
    // stable ID enforced on all subscript mutations // set operations
    // IDs move on swapAt and sort using // _modify operations
    // ID removed (set to nil) on removals
}

extension ManagedArray: RangeReplaceableCollection where Element: ManagedIdentifiable {
    // ensure distinct IDs on insert operations
}

Comments welcome.

[lorentey]

Such a view cannot conform to MutableCollection. (IdentifiedArray did not get this right.)

[stephencelis]

Such a view cannot conform to MutableCollection. (IdentifiedArray did not get this right.)

@lorentey Ha, well we originally omitted this conformance from IdentifiedArray, so we got it "right" for some time, but we recently decided to add it. Our reasoning is IdentifiedArray's primary use case is SwiftUI lists (ForEach), which requires a MutableCollection conformance for binding-related functionality. Omitting the MutableCollection conformance prevents IdentifiedArray from being used in many common SwiftUI scenarios.

So even though IdentifiedArray leverages OrderedDictionary under the hood, we do not consider it a "view" into an ordered dictionary. We consider identified array as its own data structure with its own semantics and we think that folks should reasonably be able to interact with it like a plain array (with MutableCollection and even RangeReplaceableCollection semantics), so long as you maintain the invariants: an element's identity should not change in place, and each element must have a unique identity. Violating these properties already leads to runtime issues in SwiftUI when using plain arrays.

We're always open to ideas on how to improve things, though, so feedback is welcome!

[lorentey]

I think the problem here might be in the stdlib & SwiftUI -- if SwiftUI only needs to reorder elements, then it ought to be able to require just that, and no more. MutableCollection requires too much; we might need to consider adding a new protocol.

(A new PermutableCollection protocol wouldn't be easy to wedge into the protocol hierarchy at its correct logical position, which does complicate things a bit.)