Add HashableStruct type

[turbolent]

Issue to be solved

Currently there is no type exposed to Cadence programs which represents the type that can be used as a Dictionary key type.

Suggested Solution

Tasks

Preview Give feedback

1. Add a HashableStruct interface, subtype of AnyStruct
2. Have all types mentioned in IsValidDictionaryKeyType conform to HashableStruct
3. Replace IsValidDictionaryKeyType with a subtype check for HashableStruct

[PratikDhanave]

@turbolent is this issue is resolved ? if yes humble request please can we mark it as closed ?

[turbolent]

No, this feature has not been added yet, contributions are very welcome

[PratikDhanave]

@turbolent please assign this to me. I will start looking into it.

[PratikDhanave]

@turbolent thank you I can see in pratt parser core logic where operator precedence get checked is used for parsing is there any developer documentation available please share it with me ?

[turbolent]

@PratikDhanave Sorry, I'm not quite understanding what you are asking for. Are you asking for general developer documentation, or specifically for the operator precedence logic in the parser?

BTW, for this issue, there is no work in the parser necessary, just in the type checker and interpreter.

[PratikDhanave]

hi @turbolent thank you for info I am working on it

[PratikDhanave]

hi @turbolent is this correct ?

// HashableStruct
type HashableStruct AnyStructType

var TheHashableStructType = HashableStruct{}

func NewTheHashableStruct() HashableStruct {
return TheHashableStructType
}

func (HashableStruct) isType() {}

func (HashableStruct) ID() string {
return "HashableStruct"
}

func (t HashableStruct) Equal(other Type) bool {
return t == other
}

[turbolent]

@PratikDhanave That should be it for the cadence package, yeah. type HashableStruct AnyStructType should be type HashableStructType struct{} though and all uses of HashableStruct should be HashableStructType (you're trying to define a Go value representing the Cadence type).

Note that the former does not introduce a Cadence subtyping relationship as you might think, that needs to be implemented in the sema package.

[PratikDhanave]

@turbolent thank you for your feedback I will work on it and raise PR.

[darkdrag00nv2]

I'll pick this up unless @PratikDhanave is actively working on it.

[darkdrag00nv2]

@turbolent What should be the interface definition? I have the following in mind.

pub struct interface HashableStruct {
    pub fun hash(): [UInt8]
}

Since the sema generator doesn't support interface, I'll model it in Go.

[turbolent]

Eventually, a type similar to this would be nice to have, as it would allow developers to make their types hashable / usable as dictionary keys.

As a start, it would be nice to just have a type HashableStruct, and only the currently built-in types that are hashable are "hardcoded" to be subtypes of HashableStruct.

Later, this type could become an interface, and thus implementable by developers for their types. However, that requires some more work. Unlike in other languages, which require an implementation of a function like fun hash(): [UInt8], there is an additional requirement for the hash value: The hash value is prefixed with a type indicator. For example, if you look at the implementations of interpreter.HashableValue, the implementations of the HashInput function prefix the result with a HashInputType. This would need to be made user-extendable.

(@fxamacker can you remind me why we want the type prefix/indicator? Unfortunately, I don't seem to have documented it and don't remember either)

[fxamacker]

(@fxamacker can you remind me why we want the type prefix/indicator? Unfortunately, I don't seem to have documented it and don't remember either)

@turbolent

Having a type prefix/indicator in hash input is to reduce hash collisions.

Different types can have same hash input value if we don't include the type prefix. For example, UInt8(0) and UInt64(0)) would produce same hash digest if we don't include type prefix as hash input. Same with other bit patterns of same length (e.g. 4-byte string can match any other 4-byte hash input of different type).

If users are allowed to provide entire hash input, would that make it easier for users to intentionally or accidentally cause numerous hash collisions?

[turbolent]

@fxamacker I see, thanks for the reminder, great explanation! I guess if we let user types to become hashable, we neither want to burden developers with having to manually include type information to avoid collisions, nor want to let user code intentionally omit them so they can cause many collisions.