storage-plus: Need better docs and examples for IndexedMap

[orkunkl]

I am testing out IndexedMap as workshop and article content.
I found Index and prefixes under documented and not enough tests to understand as a noobie.

For example here is a sample code I written to show an CompositeKey example.

Tokens are secondary indexed by (admin, ticker) composite key.

pub const TOKEN_COUNT: Item<u64> = Item::new("num_tokens");

pub fn num_tokens(storage: &dyn Storage) -> StdResult<u64> {
    Ok(TOKEN_COUNT.may_load(storage)?.unwrap_or_default())
}

pub fn increment_tokens(storage: &mut dyn Storage) -> StdResult<u64> {
    let val = num_tokens(storage)? + 1;
    TOKEN_COUNT.save(storage, &val)?;
    Ok(val)
}

#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, JsonSchema)]
pub struct Token {
    pub admin: Addr,
    pub ticker: String
}

pub struct TokenIndexes<'a> {
    // indexed by admin_ticker composite key
    // last U64Key is the primary key which is auto incremented token counter
    pub admin_ticker: MultiIndex<'a, (Vec<u8>, Vec<u8>, Vec<u8>), Token>,
}

// this may become macro, not important just boilerplate, builds the list of indexes for later use
impl<'a> IndexList<Token> for TokenIndexes<'a> {
    fn get_indexes(&'_ self) -> Box<dyn Iterator<Item = &'_ dyn Index<Token>> + '_> {
        let v: Vec<&dyn Index<Token>> = vec![&self.admin_ticker];
        Box::new(v.into_iter())
    }
}

const TOKEN_NAMESPACE: &str = "tokens";

pub fn tokens<'a>() -> IndexedMap<'a, &'a [u8], Token, TokenIndexes<'a>> {
    let indexes = TokenIndexes {
        admin_ticker: MultiIndex::new(
            |d, k| (index_string(d.admin.as_ref()), index_string(&d.ticker), k),
            TOKEN_NAMESPACE,
            "tokens__admin_ticker",
        )
    };
    IndexedMap::new(TOKEN_NAMESPACE, indexes)
}

Here are some tests to show what I want to achieve.

    #[test]
    fn test_tokens() {
        let mut store = MockStorage::new();

        let admin1 = Addr::unchecked("addr1");
        let ticker1 = "TOKEN1".to_string();
        let token1 = Token {
            admin: admin1,
            ticker: ticker1
        };

        let token_id = increment_tokens(store.borrow_mut()).unwrap();
        tokens().save(store.borrow_mut(), &U64Key::from(token_id).joined_key(), &token1).unwrap();

        // want to load token using admin1 and ticker1
        tokens().idx.admin_ticker.?
    }

Can you help me understand this case with few examples maybe?

[ethanfrey]

Yes, this is quite confusing. I need to look at examples to remember how to create them myself.
Once they work, they are amazing. But let's get some better docs.

[ethanfrey]

The composite key secondary indexes are the most complex use-case we have.

I would start with a single-key composite index.
You also are forcing U64Key into Vec. Better to leave it as U64Key everywhere.

It would be much easier to comment on code in a PR. Ideally we have some simple examples as test cases which serve as documentation (and always guaranteed to be up-to-date).

Maybe @maurolacy can help on this?

[maurolacy]

I will link here to some specific examples, and document them a bit.

[maurolacy]

In cosmwasm-plus, there's currently one example of IndexedMap usage, in the cw721-base contract:

https://github.com/CosmWasm/cosmwasm-plus/blob/9c37cca15bd341d44e3e855f92fcf61b5a125b1e/contracts/cw721-base/src/state.rs#L54-L75

Let's discuss this piece by piece:
https://github.com/CosmWasm/cosmwasm-plus/blob/9c37cca15bd341d44e3e855f92fcf61b5a125b1e/contracts/cw721-base/src/state.rs#L54-L57

These are the index definitions. Here there's only one index, called owner. But there could be more, as public members of the TokenIndexes struct.

We see that the owner index is a MultiIndex. A multi-index can have repeated values as keys. That's why the primary key is added as the last element of the multi-index key.
Like the name implies, this is an index over tokens, by owner. Given that an owner can have multiple tokens, we need a MultiIndex to be able to list / iterate over all the tokens a given owner has.

So, to recap, the TokenInfo data will originally be stored by token_id (which is a string value). You can see this in the token creation code:
https://github.com/CosmWasm/cosmwasm-plus/blob/9c37cca15bd341d44e3e855f92fcf61b5a125b1e/contracts/cw721-base/src/contract.rs#L98-L101

Then, it will be indexed by token owner (which is an Addr), so that we can list all the tokens an owner has. That's why the owner index key is (Vec<u8>, Vec<u8>). The first owned element is the owner data (converted to Vec<u8>), whereas the second one is the token_id (also converted to Vec<u8>).

The important thing here is that the key (and its components, in the case of a combined key) must implement the PrimaryKey trait. You can see that both the 2-tuple (_, _) and Vec<u8> do implement PrimaryKey:

https://github.com/CosmWasm/cosmwasm-plus/blob/9c37cca15bd341d44e3e855f92fcf61b5a125b1e/packages/storage-plus/src/keys.rs#L44-L53

https://github.com/CosmWasm/cosmwasm-plus/blob/9c37cca15bd341d44e3e855f92fcf61b5a125b1e/packages/storage-plus/src/keys.rs#L121-L128

---

We can now see how it all works taking a look at the remaining code:

https://github.com/CosmWasm/cosmwasm-plus/blob/9c37cca15bd341d44e3e855f92fcf61b5a125b1e/contracts/cw721-base/src/state.rs#L59-L64

This implements the IndexList trait for TokenIndexes. This kind of serves two purposes (which are really one and the same): it allows the indexes to be queries through get_indexes, and, it allows TokenIndexes to be treated as an IndexList. So that it can be passed as a parameter during IndexedMap construction, below:

https://github.com/CosmWasm/cosmwasm-plus/blob/9c37cca15bd341d44e3e855f92fcf61b5a125b1e/contracts/cw721-base/src/state.rs#L66-L75

Here tokens() is just a helper function, that simplifies the IndexedMap construction for us. First the index(es) is(are) created, and then, the IndexedMap is created (using IndexedMap::new), and returned.

During index creation, we must supply an index function per index

https://github.com/CosmWasm/cosmwasm-plus/blob/9c37cca15bd341d44e3e855f92fcf61b5a125b1e/contracts/cw721-base/src/state.rs#L68-L69

, which is the one that will take the value and the primary key (always in Vec<u8> form) of the original map, and create the index key from them. Of course, this requires that the elements required for the index key are present in the value (which makes sense).

Besides the index function, we must also supply the namespace of the pk, and the one for the new index.

---

After that, we just create (and return) the IndexedMap:

https://github.com/CosmWasm/cosmwasm-plus/blob/9c37cca15bd341d44e3e855f92fcf61b5a125b1e/contracts/cw721-base/src/state.rs#L74

Here of course, the namespace of the pk must match the one used during index(es) creation. And, we pass our TokenIndexes (as a IndexList-type parameter) as second argument. Connecting in this way the underlying Map for the pk, with the defined indexes.

So, IndexedMap (and the other Indexed* types) is just a wrapper / extension around Map, that provides a number of index functions and namespaces to create indexes over the original Map data. It also implements calling these index functions during value storage / modification / removal, so that you can forget about it and just use the indexed data.

[maurolacy]

Added a detailed description for an IndexedMap using one MultiIndex. Let me know if that's clear, and I can explain more / answer further questions if you have them.

The other index type is UniqueIndex, which is simpler in that it doesn't require using the pk for disambiguation. I'll add an example use case / detailed explanation for it too.

[ethanfrey]

That's an awesome comment.

Did you add it to some docs in the repo as well?

[maurolacy]

Thanks!

No, but I'll do it.

[orkunkl]

Great documentation thanks!
This covers single secondary non unique keys example very well, but what about multi composite indexes? https://github.com/CosmWasm/cosmwasm-plus/blob/main/packages/storage-plus/src/indexed_map.rs#L198-L202
Mainly I found composite keys difficult to understand and operate on.

[maurolacy]

Yes, those are a little more complex. I'll do the same, and document them with some code walk-through.

[maurolacy]

Composite indexed map example

Imagine the following situation: we have a number of batches, each stored by its (numeric) batch id, than can change status from Pending to Promoted, depending on interactions over them.

The batches also have an associated expiration, after which they must be automatically promoted.

Now imagine that we want to process all the pending batches at any given time. Of course, we are only interested in the pending ones that have already expired (so that we can promote them). So, we can build an index over the batches, with a composite key composed of the batch status, and their expiration timestamp.

Using the composite key, we'll be discarding both, the already promoted batches, and the pending but not yet expired ones.

So, we build the index, generate the composite key, and iterate over all pending batches that have an expiration timestamp that is less than the current time.

Here's a code example on how to do this:

Batch struct:

/// A Batch is a group of members who got voted in together. We need this to
/// calculate moving from *Paid, Pending Voter* to *Voter*
#[derive(Serialize, Deserialize, Clone, PartialEq, JsonSchema, Debug)]
pub struct Batch {
    /// Timestamp (seconds) when all members are no longer pending
    pub grace_ends_at: u64,
    /// How many must still pay in their escrow before the batch is early authorized
    pub waiting_escrow: u32,
    /// All paid members promoted. We do this once when grace ends or waiting escrow hits 0.
    /// Store this one done so we don't loop through that anymore.
    pub batch_promoted: bool,
    /// List of all members that are part of this batch (look up ESCROWS with these keys)
    pub members: Vec<Addr>,
}

IndexedMap definitions:

// We need a secondary index for batches, such that we can look up batches that have
// not been promoted, ordered by expiration (ascending) from now.
// Index: (U8Key/bool: batch_promoted, U64Key: grace_ends_at) -> U64Key: pk
pub struct BatchIndexes<'a> {
    pub promotion_time: MultiIndex<'a, (U8Key, U64Key, U64Key), Batch>,
}

impl<'a> IndexList<Batch> for BatchIndexes<'a> {
    fn get_indexes(&'_ self) -> Box<dyn Iterator<Item = &'_ dyn Index<Batch>> + '_> {
        let v: Vec<&dyn Index<Batch>> = vec![&self.promotion_time];
        Box::new(v.into_iter())
    }
}

pub fn batches<'a>() -> IndexedMap<'a, U64Key, Batch, BatchIndexes<'a>> {
    let indexes = BatchIndexes {
        promotion_time: MultiIndex::new(
            |b: &Batch, pk: Vec<u8>| {
                let promoted = if b.batch_promoted { 1u8 } else { 0u8 };
                (promoted.into(), b.grace_ends_at.into(), pk.into())
            },
            "batch",
            "batch__promotion",
        ),
    };
    IndexedMap::new("batch", indexes)
}

This example is similar to the previous one, above. The only differences are:

• The composite key now has three elements: the batch status, the expiration timestamp, and the batch id (which is the primary key for the Batch data).
• We're using a U64Key for the batch id / pk. This is just for convenience. We could as well have used a plain Vec<u8> for it.

---

Now, here's how to use the indexed data:

    let batch_map = batches();

    // Limit to batches that have not yet been promoted (0), using sub_prefix.
    // Iterate which have expired at or less than the current time (now), using a bound.
    // These are all eligible for timeout-based promotion
    let now = block.time.nanos() / 1_000_000_000;
    // as we want to keep the last item (pk) unbounded, we increment time by 1 and use exclusive (below the next tick)
    let max_key = (U64Key::from(now + 1), U64Key::from(0)).joined_key();
    let bound = Bound::Exclusive(max_key);

    let ready = batch_map
        .idx
        .promotion_time
        .sub_prefix(0u8.into())
        .range(storage, None, Some(bound), Order::Ascending)
        .collect::<StdResult<Vec<_>>>()?;

A couple of comments:

• joined_key() is being used to create the range key. This helper function transforms the (partial) composite key composed of batch expiration timestamp and batch id, into a Vec<u8> with the proper format. That is then used to create a range bound.
• sub_prefix() is used to fix the first element of the composite key (the batch status). This is required, because prefix() in this case (a 3-tuple), implies fixing the first two elements of the key, and we don't want / need that here.
• The iteration proceeds from None to the bound key created from the current timestamp. So that we effectively list only the still pending but already expired batches.

That's it. After that, we can iterate ovet the results and change their status from Pending to Promoted, or whatever we need to do.

[orkunkl]

Great documentation!