CollectionDifference.inferringMoves either behaves incorrectly or ambiguously

[braker1nine]

Description

Calling inferringMoves for types which have differences between Equatable value and Hashable value does not give the expected behavior. The inferringMoves function only detects moves for items which are both EQUAL and have the same hashValue. Which seems incorrect to me. It should detect moves for items where the hash value remains the same even if the two items are not equal

Reproduction

import Foundation

struct Item: Equatable, Hashable {
    let id: Int
    var title: String
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(self.id)
    }
}

/// We have two sets of items here. Both contain the "same" 2 items, with ids 1 and 2
/// But they are sorted by title. In the second array, item 1 has had it's title updated
/// and thus is sorted after item 2
var items: [Item] = [
    Item(id: 1, title: "A Title"),
    Item(id: 2, title: "B Title")
]

var updatedItems: [Item] = [
    Item(id: 2, title: "B Title"),
    Item(id: 1, title: "Z Title")
]


/// Here you will see we have two changes from the initial array
/// 1. A removal from offset: 0 for { id: 1, title: "A Title" }
/// 2. An insert at offset: 1 for { id: 1, title: "Z Title" }
let difference = updatedItems.difference(from: items)

/// In my opinion here is where the bug lies. It fails to recognize
/// that the item with id 1 in the second array is the "same" item (with the same
/// hash value) with id 1 in the first array. And create the associations in the result
let changes = difference.inferringMoves()

Expected behavior

I would expect unique inserts & deletes for items with the same hashValue to be associated with each other and treated as moves. Regardless of whether they are equal to each other.

Environment

swift-driver version: 1.87.3 Apple Swift version 5.9.2 (swiftlang-5.9.2.2.56 clang-1500.1.0.2.5)
Target: arm64-apple-macosx14.0

Additional information

I certainly understand that this may be debatable. That it is not an inferred move if the items are not equal. But I think we should err on the side of flexibility and leave it on the consumer to decide whether their type's Hashable and Equatable changes are that interchangeable.

The main reason this happens is in inferringMoves, there are two Dictionary objects created using ChangeElement (i.e. the type of item in the array I'm diffing) as the key. The problem is that while my objects have the same hash value, they are not equal and that key lookup only succeeds if the keys have the same hash value AND are equal.

I'm more than willing to take that change on. But I don't want to waste the time if this is truly by design

[braker1nine]

I was afraid of this. I'm guessing based on this from the Hashable docs, that this is by design...

Hashing a value means feeding its essential components into a hash function, represented by the Hasher type. Essential components are those that contribute to the type’s implementation of Equatable. Two instances that are equal must feed the same values to Hasher in hash(into:), in the same order.

So TLDR, Hashable is just a shortcut to Equatable, not a means of identification? And 2 items of a type having equal hash values while not being equal to each other is "incorrect" behavior?

Still it would be nice if there was a way in the inferringMoves step for me to define what sameness means so I can more flexibly decide what a move is. But I have the tools to do that myself.

[tbkka]

So TLDR, Hashable is just a shortcut to Equatable, not a means of identification?

In essence, yes.

And 2 items of a type having equal hash values while not being equal to each other is "incorrect" behavior?

No. You can think of a hash value as a "lossy summary." If two items are equal, their hashes must be equal. But having the same summary does not imply they are the same item.

If the id field fully determines whether these are "the same object," then you should override the == implementation as well. But in practice, that rarely turns out to be the correct approach.

I think what you are really asking for is that the CollectionDifference tools allow you to provide a separate equality check different from ==, perhaps as a closure value?

[braker1nine]

If the id field fully determines whether these are "the same object," then you should override the == implementation as well. But in practice, that rarely turns out to be the correct approach.

Yeah I definitely try to steer clear of that sort of override

I think what you are really asking for is that the CollectionDifference tools allow you to provide a separate equality check different from ==, perhaps as a closure value?

Yeah I think that would better suit what I'm after. Similar to how the Array.difference provides a closure for checking equality when generating a CollectionDifference for types that don't conform to Equatable

[tbkka]

You could also create new arrays that only have the ID values:

let summary = items.map {$0.id}
let updatedSummary = items.map {$0.id}

and then compute the difference with those arrays instead. That will tell you what IDs have moved, which seems to be what you're actually interested in.

[braker1nine]

Oh yeah, I hadn't even thought of that 🤦

It does seem like a general solution without a Hashable value loses a lot of efficiency. That makes me think a better general strategy than a closure would be a parameter something like KeyPath<ChangeElement, some Hashable> or (ChangeElement) -> some Hashable where the caller gets a little more control over the hash value that's used to determine sameness

Or an inferringMoves only for Identifiable types. Although I think that could pretty easily be derived from a solution where the caller specifies the Hashable value

[tbkka]

You never use a "hash value" to determine sameness. That's not what a hash value is for.

I think the word you're looking for is "identifier". And yes, having a version for Identifiable types would be an answer.

In practice, creating new arrays like this is not necessarily a performance problem. It depends on how the differencing algorithm works -- differencing arrays of simple integers may be enough faster to outweigh the other costs. You should always measure stuff like this.

[braker1nine]

Yeah sorry that was poorly described. Honestly I'm leaning a little more on Hashable as a guide than necessary because the current implementation requires it. My guess was for performance reasons, but I'm not certain of that.