1

Hello ! I would like to have some clarifications about why Set does not interact properly with a Hashable struct declared in a function.

Here I have a struct Hello that conforms to hashable and only needs its id for the hashValue. Because structs need to have Equatable custom conformance to have custom hash behavior, so a == function is declared. 23
I first declare a Set with an identifier 123 and the I try to insert another struct having the same identifier with different "value". It does not insert the new element because it is considered as the same by the equality.

struct Hello: Hashable {

    let id: Int
    let value: String

    var hashValue: Int {
        return id.hashValue
    }

    init(id: Int, value: String) {
        self.id = id
        self.value = value
    }

    static func == (lhs: Hello, rhs: Hello) -> Bool {
        return lhs.id == rhs.id
    }
}

func testFunc() {
    var set = Set<Hello>([Hello(id: 123, value: "Hello")])
    // Set is now `[Hello #1 in __lldb_expr_104.testFunc() -> ()(id: 123, value: "Hello")]`
    set.insert(Hello(id: 123, value: "World"))
    // Set is still `[Hello #1 in __lldb_expr_104.testFunc() -> ()(id: 123, value: "Hello")]`.
}

testFunc()

Here I have a struct Hello that conforms to hashable and only needs its id for the hashValue and it is declared in a function. The struct is the same as the previous example but it does not work, the set keep inserting it while the id is the same. The custom comparison operand is not used so I suspect that the default implementation is called instead.

func testFunc() {

    struct Hello: Hashable {

        let id: Int
        let value: String

        var hashValue: Int {
            return id.hashValue
        }

        init(id: Int, value: String) {
            self.id = id
            self.value = value
        }

        static func == (lhs: Hello, rhs: Hello) -> Bool {
            return lhs.id == rhs.id
        }
    }

    var set = Set<Hello>([Hello(id: 123, value: "Hello")])
    // Set is now `[Hello #1 in __lldb_expr_104.testFunc() -> ()(id: 123, value: "Hello")]`
    set.insert(Hello(id: 123, value: "World"))
    // Set is now [Hello #1 in __lldb_expr_115.testFunc() -> ()(id: 123, value: "Hello"), Hello #1 in __lldb_expr_115.testFunc() -> ()(id: 123, value: "World")]

}

testFunc()
2 Likes
2

Sounds like a bug! (And reproduces for me on master too.) Can you file this at https://bugs.swift.org?

3

Sure, thanks for the answer @jrose

4

A tangential note of caution: it's likely your implementation of Equatable (via Hashable) is invalid and could lead to other problems. Equatability implies substitutability, so any generic algorithm that relies on Equatable is free to substitute one value for another if == returns true. This means, for example, that if you had two entries in an array with the same id but different value, it would be free to throw away one of them and replace it with another. This might not be what you expect, and could lead to really hard to track down bugs.

3 Likes
5

is this something the compiler assumes when doing optimizations?

6

This is not about the compiler, it's about assumptions that can be made in Swift code (including the standard library).

For example (different case, but similar situation):

struct BustedEquatable: Equatable {
  // not a valid implementation of Equatable: breaks requirement
  // of reflexivity (x == x)
  static func ==(lhs: BustedEquatable, rhs: BustedEquatable) -> Bool {
    return false
  }
}

var a = [BustedEquatable()]
let b = a
print(b==a)  // true
a.reserveCapacity(10)
print(b==a)  // false
4 Likes
7

Ben, I'm not sure what you're getting at here, since there's clearly nothing wrong with the == operator in the example and yet it misbehaves.

8

There is definitely something wrong with the == operator in the example. It doesn't fulfill the contract for Equatable (that == be reflexive), which Array.== relies on to skip actually doing element-wise comparisons when two arrays share a buffer – it just returns true if lhs._buffer === rhs._buffer.

I don't think there's an example in the std lib for a type that violates the substitutability rule, but I can imagine, say, a partitioning algorithm that did comparisons and potentially optimized to not copy elements around when they were "equal", resulting in objects that weren't "truly" equal being substituted for each other.

1 Like
9

I mean Maxime's example, Ben, which is what this thread is about.

10

It's less clear cut than the reflexive example, but it's still likely to be invalid depending on what value represents. Is it OK if two Hello objects have the same id to substitute one for the other even if their value is different? It seems likely that if that ever happened, silently, within an algorithm, that this would be unexpected and lead to a bug.

1 Like
11

I think that's fair to point out, but just to clarify, (1) this is absolutely a compiler bug and (2) there are definitely legitimate ways to use types with a partial equality operator even if some algorithms might make unexpected decisions.

4 Likes