Owned key type

[larry0x]

Currently the Key type takes either a ref, or a fixed-length byte slice:

pub enum Key<'a> {
    Ref(&'a [u8]),
    Val8([u8; 1]),
    Val16([u8; 2]),
    Val32([u8; 4]),
    Val64([u8; 8]),
    Val128([u8; 16]),
}

The drawback of this is that when implementing the PrimaryKey trait, we can't use any custom serialization method of which the output is of variable length.

Example

Here is an actual use case I've worked on. Consider the following type:

enum AssetInfo {
    // bank module native coin
    Native { denom: String },
    // cw20 token
    Cw20 { contract_address: String },
}

We want to create a Map<&AssetInfo, Uint128> to record a user's asset balances. To do this we need to implement PrimaryKey on &AssetInfo. Specifically we want to serialize it the following way:

impl AssetInfo {
    pub fn serialize(&self) -> Vec<u8> {
        let mut bytes = vec![];

        // for native coins, we prefix the denom with a zero-byte (0x00)
        // for cw20s, we prefix the contract address with a one-byte (0x01)
        match self {
            AssetInfo::Native { denom } => {
                bytes.push(0);
                bytes.extend(denom.as_bytes());
            } 
            AssetInfo::Cw20 { contract_address } => {
                bytes.push(1);
                bytes.extend(contract_address.as_bytes());
            }
        }

        bytes
    }
}

And we implement PrimaryKey as follows:

impl<'a> PrimaryKey<'a> for &'a AssetInfo {
    type Prefix = ();
    type SubPrefix = ();
    type Suffix = Self;
    type SuperSuffix = Self;

    fn key(&self) -> Vec<Key> {
        let bytes = self.serialize();
        vec![Key::Ref(&bytes)] // compile error!
    }
}

But this doesn't work! The bytes variable goes out of scope at the end of the function, so the returned &bytes becomes a dangling pointer!

Alternatively, we can do something like this:

impl<'a> PrimaryKey<'a> for &'a AssetInfo {
   type Prefix = ();
   type SubPrefix = ();
   type Suffix = Self;
   type SuperSuffix = Self;

   fn key(&self) -> Vec<Key> {
       let mut keys = vec![];

       match self {
           AssetInfo::Native { denom } => {
               keys.push(Key::Val8([0]));
               keys.push(Key::Ref(denom.as_ref()));
           }
           AssetInfo::Cw20 { contract_addr } => {
               keys.push(Key::Val8([1]));
               keys.push(Key::Ref(contract_addr.as_ref()));
           }
       }

       keys
   }
}

But this this is inefficient, as the first key (the Val8) is going to be prefixed by its length. The resulting key is two bytes longer (you get an extra 0x00 0x08).

Potential solution

Add a enum variant to Key which takes an owned, variable-length byte array:

pub enum Key<'a> {
+   Owned(Vec<u8>)
    Ref(&'a [u8]),
    Val8([u8; 1]),
    Val16([u8; 2]),
    Val32([u8; 4]),
    Val64([u8; 8]),
    Val128([u8; 16]),
}

This way, when implementing PrimaryKey we can simply do:

impl<'a> PrimaryKey<'a> for &'a AssetInfo {
    type Prefix = ();
    type SubPrefix = ();
    type Suffix = Self;
    type SuperSuffix = Self;

    fn key(&self) -> Vec<Key> {
        let bytes = self.serialize();
        vec![Key::Owned(bytes)]
    }
}

[chipshort]

Yes, I had the same problem before. Adding an owned variant seems like a straightforward solution to me.

[maurolacy]

The fixed size value types are there to avoid creating arbitrarily sized keys in the first place.

Now, I see the reason for your change. And, we never really measured the performance impact of using a large key by value.

So, I'm OK with introducing this change. It would be good to benchmark the overhead of using a large key value instead of a reference. It's probably negligible, but it would be good to confirm it.