Implement StorageTripleMap

[shawntabrizi]

The assets pallet could use a StorageTripleMap to be event slightly more ergonomic:

#8220 (comment)

This should be implemented, and the assets pallet should be updated to use it.

cc @thiolliere

[bkchr]

Maybe we should redesign the maps completely and add support for arbitrary number of keys for maps?

[KiChjang]

Any consensus yet on whether or not to simply implement StorageTripleMap or redesign it to be a StorageNMap? Wonder if we can use const generics to support N keys...

[gui1117]

the thing is that all keys are of different types. We can't make an array of different types. Maybe we can make use of Any but I'm a bit clueless how to do it.

One idea I have is:

struct StorageNMap<Prefix, Key, Value, QueryKind = OptionQuery, OnEmpty = GetDefault> {
	//phantomdata
}

struct Key<Hasher, KeyType, NextKeyGenerator = FinalKey> {
	//phantomdata
}

struct FinalKey;

type MyMap = StorageNMap<_, Key<Blake2_128Concat, u32>, u64>;
type MyDoubleMap = StorageNMap<
	_,
	Key<Blake2_128Concat, u32, Key<Twox128Concat, u32>>,
	u64
>;
type MyTripleMap = StorageNMap<
	_,
	Key<Blake2_128Concat, u32,
		Key<Twox128Concat, u32,
			Key<Blake2_128Concat, u64>
		>
	>,
	u64
>;

//////// First solution to implement the methods on the StorageNMap //////////

trait KeyTypes {
	type Types;
	fn final_key(k: Self::Types) -> Vec<u8>;
}

impl KeyTypes for Key<Hasher, KeyType> {
	type Types = KeyType;
	fn final_key(k: Self::Types) -> Vec<u8> {
		// Do hash of k
		todo!()
	}
}

impl KeyTypes for Key<Hasher, KeyType, Key<Hasher2, KeyType2>> {
	type Types = (KeyType, KeyType2);
	fn final_key(k: Self::Types) -> Vec<u8> {
		// Do hash of k1 and k2
		todo!()
	}
}

impl KeyTypes for Key<Hasher, KeyType, Key<Hasher2, KeyType2, Key<Hasher3, KeyType3>>> {
	type Types = (KeyType, KeyType2, KeyType3);
	fn final_key(k: Self::Types) -> Vec<u8> {
		// Do hash of k1 and k2 and k3
		todo!()
	}
}

// derive more with a macro.

impl StorageNMap<P, K, V, Q, O> {
	// Maybe we should take reference of types instead of value
	// But better if we could use EncodeLike here.
	fn get(key: impl Into<K::KeyTypes>) {}

}

//////// Second solution to implement the methods on the StorageNMap //////////

// Make use of EncodeLike

trait GenerateFinalKey<K> {
	fn final_key(k: K) -> Vec<u8> {}
}

impl<Hasher, KArg: EnocdeLike<K>> GenerateFinalKey<KArg> for Key<Hasher, K> {
	fn final_key(k: KArg) -> Vec<u8> {
		todo!()
	}
}

impl<Hasher, K, K2, KArg: EncodeLike<K>, KArg2: EncodeLike<K2>> GenerateFinalKey<(KArg, KArg2)> for Key<Hasher, K, Key<Hasher, K2>> {
	fn final_key(k: (KArg, KArg2)) -> Vec<u8> {
		todo!()
	}
}

impl StorageNMap<P, K, V, Q, O> {
	fn get<KArg>(key: KArg) where K: GenerateFinalKey<KArg> {}
}

But at some point I think it would be easier to just write a macro which generates StorageMap, StorageDoubleMap, StorageTripleMap etc...
By implementing them individually with a macro we can make a more understandable API I think. And use less generics stuff.

[shawntabrizi]

@KiChjang You can def take this issue if you have an idea on what to do. I would be pretty happy to accept a PR which does a simple implementation of Triple Map or some kind of arbitrary support.

[bkchr]

struct StorageNMap<Prefix, Key, Value, QueryKind = OptionQuery, OnEmpty = GetDefault> {
	//phantomdata
}

struct Key<Hasher, KeyType, NextKeyGenerator = FinalKey> {
	//phantomdata
}

struct FinalKey;

type MyMap = StorageNMap<_, Key<Blake2_128Concat, u32>, u64>;
type MyDoubleMap = StorageNMap<
	_,
	Key<Blake2_128Concat, u32, Key<Twox128Concat, u32>>,
	u64
>;
type MyTripleMap = StorageNMap<
	_,
	Key<Blake2_128Concat, u32,
		Key<Twox128Concat, u32,
			Key<Blake2_128Concat, u64>
		>
	>,
	u64
>;

Yeah I had a similar idea. I think we should go in this direction and check if that works.

But at some point I think it would be easier to just write a macro which generates StorageMap, StorageDoubleMap, StorageTripleMap etc...
By implementing them individually with a macro we can make a more understandable API I think. And use less generics stuff.

We can always write a macro to make the type declaration less complicated. However, we should try as much as possible to go for some generic solution, because that can be checked by the compiler etc.

[KiChjang]

We can't make an array of different types

I just thought of an idea using trait objects:

struct StorageKey<const N: usize> {
    children: [(Box<dyn FullEncode>, Box<dyn StorageHasher>); N],
}

// or

struct StorageKey<const N: usize> {
    child_keys: [Box<dyn FullEncode>; N],
    hashers: [Box<dyn StorageHasher>; N],
}

impl<const N: usize> StorageKey {
    fn final_key(&self) -> Vec<u8> {
        // use the hashers on the child keys and concat them together
    }
}

The downside I see from this implementation is that we'll need to box the keys and hasher during storage key construction, which means we'd go through a pointer indirection every time we access the child keys or the hashers, not to mention that boxing does store the child keys on the heap (there shouldn't be any problems with the hashers since they're just ZSTs and can simply be treated as function tables). There might be performance constraints here but I'm not sure if they're big enough to cause concerns.

[KiChjang]

Shucks, using trait objects doesn't work because FullEncode can't be made into trait objects due to Encode having an associated const and having methods that have generic type params... but this can be fixed by adding where Self: Sized clause in those methods (encode_to and using_encoded). The associated constant (TYPE_INFO) however will have to be removed, and I see that it's currently used for specialization, so when Rust finally supports specialization, we can revisit this approach.

[bkchr]

If you want to work on this, please try the generic approach. Using trait objects sounds like a bad idea in general here.