[Pitch] Default implementation of Hashable for AnyObject

Evolution Pitches
, ,
1

Hello friends,

I'd like to pitch a very small, but IMHO a very useful change when it comes to conforming AnyObjects to Hashable.

Motivation

Nowadays it is common to conform classes to Hashable when building SwiftUI apps, so that they can be used as elements inside navigation paths. This is generally done either by always implementing the conformance, or by creating a separate protocol and providing the implementation there (much more common). This pattern is so common that it found its way to open-source projects, such as swift-navigation by Point-Free.

Proposed solution

I believe it would make sense to have this functionality covered by the stdlib itself. This change would follow the steps of Identifiable, which also provides implementation for AnyObject by leveraging its ObjectIdentifier. You can check my proposed solution on this commit.

Looking forward to any input you may have and hope you have a great day!

11 Likes
Nondeterministic behaviour when hashing a class
2

IMHO this is false convenience. You do need to implement the conformance (no default here) for a reason. You need to hash meaningful data, e.g. if a class contains an Int variable (only), you need to hash it. Many instances of this class with different identifiers can have the same Int value, and so the same hash, and so == to each other. If you forget to implement the conformance, the proposed default will give you wrong results, and the compiler will not catch this error (as it does now).

3 Likes
3

This is actually only true if the class is immutable and without long-living/async behavior, a required design pattern in object-oriented languages, but pretty unheard of in Swift because we have something better: value types.

Generally the only meaningful data in a Swift class that can be hashed is its identity, which is the argument for this pitch's default implementation.

11 Likes
4

Why?

Please correct me if I'm wrong, but we are talking about the == (equality) operator? Which is used to compare two objects to find out if they are equal, that is contain equal data? And which is implemented by hashing object's data and comparing the hash value?

The object's identity is unique for every object. So you even don't need the identity to find out if two objects are identical. You just use the === operator for that, which compares reference pointers. We are talking here about equality, not identity. The original poster just suggests to use identity by default for checking equality, which is wrong.

This is unrelated. value types are compared by value, and do not need to be hashed for that. The original poster talks about AnyObject, which is not a value type as far as I understand.

5

Non-nominal types cannot conform to protocols in a general way in Swift (with a few hardcoded special cases such as Sendable, Copyable, etc.)

However, ObjectIdentifier already has the ability to wrap an AnyObject and conform it to Hashable, so you could just do that instead.

4 Likes
6

Technically you can, and it will allow you to write less code - at the cost of logically incorrect code.

7

I’m not sure what you mean. I would be extremely surprised if ObjectIdentifier’s implementation of Equatable and Hashable had any correctness issues, and presumably a hard-coded conformance on AnyObject would have the same behavior. Otherwise what could it do?

1 Like
8

If you forget to implement the conformance to Hashable, the proposed "solution" will do it for you, leading to logically incorrect code.

class MyObject {
    var i: Int
}

You need to hash the i variable to correctly compare two objects of this class. Currently if the class conforms to Hashable, the compiler will force you to implement the conformance (which is right), but the proposed solution will allow you to skip this, leading to use identifier instead of i for comparing two instances of the class (which is wrong).

9

The Hashable implementation that incorporates i is the one that is wrong to use. It allows you to change an object's hash value without changing its identity, which can lead to crashes:

class MyObject: Hashable {
  var i: Int
  init(i: Int) {
    self.i = i
  }
  static func == (lhs: MyObject, rhs: MyObject) -> Bool { lhs.i == rhs.i }
  func hash(into hasher: inout Hasher) {
    hasher.combine(i)
  }
}
@Test func `incorrect Hashable implementation`() {
  var dictionary: [MyObject: Bool] = [:]
  let object = MyObject(i: 0)
  dictionary[object] = true
  object.i = 1
  dictionary[object] = false  
  // 🛑 Fatal error: Duplicate keys of type 'MyObject' were found in a Dictionary.
}

Almost all classes should use their object identity for Hashable and leave data hashing to value types.

7 Likes
10

It looks like I'm understanding all of this wrong :frowning:

But I cannot stop myself of expressing my point of view.

IMO the object's identity should never been changed during its lifetime.

Its hash however can and should. The hash is what is used to compare two instances of the class for equality (the == operator). IMO this is the whole point of Hashable.

11

This is an excellent example of incorrect program logic. If the hashes of two instances of a class are equal, this means that the == operator will return true, and not in any way means that the Hashable implementation is wrong.

12

Which part do you think is incorrect? Set's implementation or MyObject's implementation?

That is the opposite condition of what Hashable needs to satisfy. If two instances are equal then their hashes are equal, not the converse.

2 Likes
13

Your code implies that if two hashes are equal, then there is an error.

14

Isn't this work in both directions?

How do you define "equal" if not using hash?

15

If this were true, a type with more than 1 << 64 possible values, like String, could not conform to Hashable.

2 Likes
16

Well, I am a bit surprised that you cannot calculate a hash of a string.

17

Again, we are not talking about arbitrary types that cannot be hashed, we are talking about the (correct) implementation of the == operator for reference types.

And about the proposed default that can ruin the app logic.

18

No, the rule works in just one direction. If two objects are equal (as defined by ==), then their hashes must be equal. It can't possibly work the other direction.

This is what lets Dictionary efficiently look up elements by key because it can finely bucket values by the key's hash and then it only ever has to linearly search for a key if two keys have the same hash.

And this is what the crash that I demonstrated above is about. We first insert an object with one hash value (say it's 1), so it goes in the 1 bucket. Then we insert the exact same object but now with a new hash value (say it's 2), and so the dictionary wants to put it in the 2 bucket. But that would mean the same object needs to exist in two different buckets. That would cause a whole host of problems (for one thing, what is dictionary.count? Is it 1 or 2?).

"Equal" is if x == y is true.

Can you demonstrate concretely how the proposed default can "ruin" app logic? I have demonstrated how hashing a class by its data can be disastrous, in that you can't reliably use them in dictionaries, or really any algorithm or data structure that depends on hashing.

1 Like
19

How the == operator is implemented? Especially for reference types? Especially in the light of the OP's proposal? (Spoiler: The OP's implementation is inherently incorrect).

I already done that twice in this thread. Please don't force me to do that third time.

20

For reference types == should be implemented using object identity:

extension MyObject {
  static func == (lhs: MyObject, rhs: MyObject) -> Bool {
    lhs === rhs
  }
}

That is the correct implementation 99% of the time, and that is why I am in strong support for this proposal. This default implementation is the safest one for classes.

One situation where it would be ok to use the data in a class for equality and hashing would be if you you have a final class with all let fields and the types of those fields are also fully immutable. But such a class is basically a value type at that point, for all intents and purposes.

I haven't seen any code samples with as clear as an example as what I did with the crash in Dictionary. I think an actual compiling code snippet that demonstrates the problems you envision would help make your point.

2 Likes