Dictionaries key'd by type are order-dependent

[austinkline]

Current Behavior

If I have a dictionary key'd by Type, the order of their interface conformance matters:

import FungibleToken from 0x1

pub fun main(): String {
  let t1 = Type<&{FungibleToken.Provider, FungibleToken.Balance}>()
  let t2 = Type<&{FungibleToken.Balance, FungibleToken.Provider}>()

  let dict: {Type: Bool} = {}
  dict[t1] = true

  assert(dict[t2] != nil, message: "key not found!")
  return "Done"
}

However, if I compare the two types, they are equal:

import FungibleToken from 0x1

pub fun main(): String {
  let t1 = Type<&{FungibleToken.Provider, FungibleToken.Balance}>()
  let t2 = Type<&{FungibleToken.Balance, FungibleToken.Provider}>()

  assert(t1 == t2, message: "types are not equal")

  return "Done"
}

Expected Behavior

I expect that two types which are equal should match to the same key in a dictionary

If I have a type &{A, B} and it is equivalent to &{B, A}, then my expectation is that a dictionary key'd on types should match regardless of their order

Steps To Reproduce

Run this script on the flow emulator:

import FungibleToken from 0xee82856bf20e2aa6

pub fun main(): String {
  let t1 = Type<&{FungibleToken.Provider, FungibleToken.Balance}>()
  let t2 = Type<&{FungibleToken.Balance, FungibleToken.Provider}>()

  // this will pass
  assert(t1 == t2, message: "types are not equal")

  let dict: {Type: Bool} = {}
  dict[t1] = true

  // this will fail
  assert(dict[t2] != nil, message: "key not found!")

  return "done"
}

Environment

- Cadence version: v1.3.2 (flow cli version)
- Network: Emulator

[dsainati1]

In general it would be nice to enforce that for any two types T and U such that T = U, Type<T>() = Type<U>() at runtime.

[turbolent]

To fix this, we need to:

• Fix the encoding and hashing of type sets (e.g. currently, restricted types; in Stable Cadence, interface sets) of interpreter static types to produce a canonical representation, i.e. fixed order. Like in CCF, we can probably use bytewise lexicographic order.
• Migrate existing data, which involves re-hashing of dictionary keys

[austinkline]

To fix this, we need to:

• Fix the encoding and hashing of type sets (e.g. currently, restricted types; in Stable Cadence, interface sets) of interpreter static types to produce a canonical representation, i.e. fixed order. Like in CCF, we can probably use bytewise lexicographic order.
• Migrate existing data, which involves re-hashing of dictionary keys

Thanks for looking into this! Makes sense that a fix would be split into two parts. Is this something that makes more sense to bundle with stable cadence since migrations are already needed? Or it is able to be done at the next spork after encoding is "fixed" (whenever that may be)?

[dsainati1]

This would (I believe) be a breaking change, since any existing code that relies on these two type keys being different would have different behavior after we change them to be the same.

[austinkline]

This would (I believe) be a breaking change, since any existing code that relies on these two type keys being different would have different behavior after we change them to be the same.

Definitely, yeah. Does how this gets handled change with Entitlements anyway? How is that migration being planned? Maybe this has some overlap

[dsainati1]

onflow/flips#95 has the discussion of the entitlements migration

[j1010001]

Fix requires migration as part of Stable Cadence

[turbolent]

@dsainati1 It just occurred to me that authorizations of reference types should also be ordered. Could you please open an issue for this?

[j1010001]

Med effort incl. migration

[turbolent]

Add a test case which stores/loads (lookup) across multiple transactions, so encoding. equality comparison, hash value generation, etc. is tested