Support `Equatable` or `HashableStruct` subtypes

[sisyphusSmiling]

Issue to be solved

Dictionary values must be hashable and equatable. With Cadence 1.0, there was the introduction of the HashableStruct super type, however the implementation of HashableStruct is limited to a subset of primitive types.

It would be very helpful for anyone to be able to define a type that conforms to HashableStruct or at least EquatableStruct if it existed. One such use case is the EVMAddress type. In both Solidity and Cadence, it's a common pattern to index mappings on addresses. With the introduction of Flow EVM, it would be very useful to also index mappings on EVMAddress but this is not possible at the moment as the type is not hashable or equatable.

More broadly, it would be even more useful to leverage the implementation of HashableStruct to define custom comparators, but that might be too broad of a scope for this single issue.

Suggested Solution

Perhaps HashableStruct could be a native interface or an FVM contract (like Crypto) could be introduced to house similar interfaces which a type could implement with a single method, such as:

access(all) fun equals(_ other: {HashableStruct}): Bool

In the concrete use case mentioned above of EVMAddress, this would look like:

access(all) struct EVMAddress : HashableStruct {
  // ...
  access(all) fun equals(_ other: {HashableStruct}): Bool {
    if self.getType() != other.getType() {
      return false
    }
    let otherAddress = other as! EVMAddress
    return self.bytes == otherAddress.bytes
  }
}

[turbolent]

This was a previously proposed feature: https://github.com/onflow/cadence/commit/d3191a3529c8faf33dc3dbb4a335569ae70c784d#diff-75060942f377544ff403d04b6d3691f7cfeca9f76fea62c8b5c8b1a858a6f555L555-L707

Adding EquatableStruct should be fairly easy.

Exposing HashableStruct as an interface that user-defined types can implement is a bit more complicated, as the hash of a value also needs to include a unique type indicator. For example, internally, HashableValue's HashInput generates the input for the hasher. We might want to have a similar API in Cadence. For example, in Swift, the function is func hash(into hasher: inout Hasher)

[bluesign]

exposing HashableStruct as an interface that user-defined types can implement is a bit more complicated

I think this is very very hard, if not impossible.

[turbolent]

One other aspect I can think of is the type changing / being updated

[turbolent]

exposing HashableStruct as an interface that user-defined types can implement is a bit more complicated

I think this is very very hard, if not impossible.

@bluesign How so? Because of the type input requirement I noted above, or because of something else?

[bluesign]

@bluesign How so? Because of the type input requirement I noted above, or because of something else?

hash should be something that cannot change over time in my opinion. Imagine I have some HashableStruct, I wrote a hash function returns 42. Put it into a dictionary, then I changed hash function to return 0.

same problem stays if we give some data as hashInput on Cadence side too, what happens if I change the hashInput function.

[sisyphusSmiling]

@bluesign good point, this isn't possible with any of the current features of Cadence. What if we had a function modifier called immutable which denotes that the function and its contents cannot be changed in future updates and can only reference deterministic actions or other immutable functions and values. In the case of struct fields, let would be implicitly immutable since it cannot change or be removed.

Returning to the concrete case of the EVMAddress, it would look something like

access(all) struct EVMAddress: Addressable, HashableStruct {
  access(all) let bytes: [UInt8; 20]
  // ...
  access(all) immutable fun hash(): String {
    return self.bytes.toVariableSizedArray().encodeHex()
  }  
}

I don't know if the effort required to implement the immutable modifier, but I would think something like this would avoid the problem you raised.