[TreeDictionary][Keys] Add Equatable and Hashable Conformance to TreeDictionary.Keys

[vanvoorden]

Background

Unlike Swift.Dictionary.Keys^1, TreeDictionary.Keys does not currently conform to Equatable. Achieving more parity with the standard library dictionary could lower friction for more engineers to migrate to TreeDictionary in their own repos.

Changes

We can copy the approach from TreeSet:

public static func == (left: Self, right: Self) -> Bool {
  left._base._root.isEqualSet(to: right._base._root, by: { _, _ in true })
}

Since we don't care if values are equal (only the keys), we can hardcode the equality closure to always return true.

Similar to our equality check on TreeDictionary, we expect to return true in constant-time if two values are identical by reference (no need for a linear-time check).

Test Plan

We add TreeDictionaryKeysTests.test_isEqual_exhaustive. We can expand on these tests if necessary.

Benchmarks

swift run -c release benchmark run results.json --cycles 5 --tasks "TreeDictionary<Int, Int> equality, unique" "TreeDictionary<Int, Int> equality, shared"

swift run -c release benchmark render results.json tree-dictionary.png --amortized false --tasks "TreeDictionary<Int, Int> equality, unique" "TreeDictionary<Int, Int> equality, shared"

swift run -c release benchmark run results.json --cycles 5 --tasks "TreeDictionary<Int, Int>.Keys equality, unique" "TreeDictionary<Int, Int>.Keys equality, shared"

swift run -c release benchmark render results.json tree-dictionary-keys.png --amortized false --tasks "TreeDictionary<Int, Int>.Keys equality, unique" "TreeDictionary<Int, Int>.Keys equality, shared"

Checklist

• [x] I've read the Contribution Guidelines
• [x] My contributions are licensed under the Swift license.
• [x] I've followed the coding style of the rest of the project.
• [x] I've added tests covering all new code paths my change adds to the project (if appropriate).
• [x] I've added benchmarks covering new functionality (if appropriate).
• [x] I've verified that my change does not break any existing tests or introduce unexplained benchmark regressions.
• [ ] I've updated the documentation if necessary.

[vanvoorden]

Generally, it's good practice for Equatable types to also conform to Hashable

https://developer.apple.com/documentation/swift/dictionary/keys-swift.struct#conforms-to

@lorentey Hmm… it looks like Swift.Dictionary.Keys actually does not conform to Hashable (but does conform to Equatable). There might be some interesting use cases enabled when an engineer can assume TreeDictionary.Keys was Hashable… but it looks like the precedent from the Standard Library Dictionary is that just Equatable might be good enough for now.

[lorentey]

Unfortunately the Standard Library does not set a good example here, as we cannot easily add missing conformances there that we forgot to ship in the initial release. (They are potentially ABI breaking.)

[vanvoorden]

we cannot easily add missing conformances there that we forgot to ship in the initial release

https://github.com/apple/swift-collections/blob/release/1.1/Sources/HashTreeCollections/TreeSet/TreeSet%2BHashable.swift

@lorentey Hmm… something like what we do for TreeSet might work here? Want me to give it a try and post a diff?

[lorentey]

Yes, that's precisely the pattern! 👍

[vanvoorden]

Yes, that's precisely the pattern!

@lorentey Sounds good. I can try that. Would it be ok to add a new commit here to this diff for another review to save us the merge conflict from trying to land both?

[lorentey]

For sure! Adding a commit here is best.

[lorentey]

@swift-ci test linux platform