Add `iter_first_keys()` to `StorageDoubleMap`

[shawntabrizi]

The StorageDoubleMapin substrate does not currently allow you to iterate over the first set of keys of the storage item.

It would be nice if in addition to iter_prefix() it also had the function iter() so that a user in the runtime would be able to access all elements through iteration.

cc @thiolliere

[gui1117]

I guess iter function name is already used to iterate on all values, but introducing iter_first_keys seems good indeed.

implementation could look like:

• first get first key by calling next_key(module_prefix++storage_prefix)
• then get next key by calling next_key(previous_key+0xFFFFFFFF..size_of_hasher+1) (note that it might return the key previous_key+0xFFFFF.., in this case we call again with this corresponding key.)

[shawntabrizi]

If you name it iter_first_keys() we should maybe name iter_prefix() -> iter_second_keys()

[gui1117]

I unassign for now as I have other priority, I can mentor though

[gui1117]

this can be generalized for storage-n-map also

[real-felix]

@thiolliere Hello, I'd like to develop this. I work at Totem Accounting, and we need to use this feature. We have this huge multimap, and we'd like to iterate over a set of subkeys, as in this function signature.

If you can provide me some mentoring, that'd be cool ;) I'm availble on the matrix chat as well if it's easier for you.

[gui1117]

@thiolliere Hello, I'd like to develop this. I work at Totem Accounting, and we need to use this feature. We have this huge multimap, and we'd like to iterate over a set of subkeys, as in this function signature.

If you can provide me some mentoring, that'd be cool ;) I'm availble on the matrix chat as well if it's easier for you.

In your case you want to iterate on all the second keys associated to a first key, in the storage n map.

So to get the first second keys you will need to call sp_io::storage::next_key with the key being: storage_prefix concatenated with the first key hashed. So twox128(Pallet name)++twox128(storage name) ++ blake2_128_concat(account_id.encode()) (++ mean concatenation).

So calling next_key(twox128(Pallet name)++twox128(storage name) ++ blake2_128_concat(account_id.encode())) will give you the first key in the map with this account id. Let's call it K1. From K1 you can extract the ledger, let's call it L1 To get the next ledger. you want to skip all PostingIndex associated to the ledger. So you would call next_key(twox128(Pallet name)++twox128(storage name) ++ blake2_128_concat(account_id.encode())++blake2_128(L1.encode())++0xFFFF_FFFF_FF)

I used a key of size 10 bytes: 0xFFFF_FFFF_FF but to be more efficient in the general case we should probably make it more than 32 bytes.

Because PostingIndex is before 0xFFFF_FFFF_FF. the next key will be for the next ledger. This way you can retrieve to get L2, the next ledger and so on, until the next key no longer start with next_key(twox128(Pallet name)++twox128(storage name) ++ blake2_128_concat(account_id.encode()). In case a hashed PostingIndex starts with 0xFFFF_FFFF_FF then we need to iterate until we get the next ledger by calling next_key again and again.

So this was the example for your usecase, now what we can implement in the general case in storage n map is:

/// Iter the keys after the partial prefix.
/// But iter for the keys in only one level
/// Like for the map (k1, k2, k3), the call iter_prefix_values(k1)
/// will return all the k2 keys associated to k1.
fn iter_prefix_values<KP>(partial_key: KP) -> PrefixIterator<V>
where
    K: HasKeyPrefix<KP>,
{

And the implementation should be a generalisation of the example above.

About the file you will touch. you can implement this function in the generator trait: frame/support/src/storage/generator/nmap.rs And then implement the method directly on the type StorageNMap at: frame/support/src/storage/types/nmap.rs by calling the generator implementation.