How to create an iterator for a child storage trie?

Question

I have a Storage Map which I am using to to store structs and a Storage Value to use for indexing this:

#[pallet::storage]
#[pallet::getter(fn consequences)]
/// Storage map holding basic Consequence information
pub(super) type Consequences<T: Config> = StorageMap<_, Twox64Concat, ConsequenceIndex, ConsequenceInfoOf<T>, OptionQuery>;

#[pallet::storage]
#[pallet::getter(fn consequence_count)]
/// Storage value holding the number of existing Consequences (including the Purpose)
pub(super) type ConsequenceCount<T: Config> = StorageValue<_, ConsequenceIndex, ValueQuery>;

So far so good.

Now I need to create child-parent relationships between my Consequences. To do this I am using a pair of child tries for each Consequence, one to hold the parents of the Consequence and another to hold the children of the Consequence. The idea being that I can then search either way. I've created some helper functions to achieve this:

/// Find the ID of the child trie containing a Consequence's Children
///
/// Each Consequence stores its Children in a child trie
/// This helper function calculates the id of the associated child trie.
fn children_trie_id_from_index(index: ConsequenceIndex) -> child::ChildInfo {
    let mut buf = Vec::new();
    buf.extend_from_slice(b"consequencechildren");
    buf.extend_from_slice(&index.to_le_bytes()[..]);

    child::ChildInfo::new_default(T::Hashing::hash(&buf[..]).as_ref())
}

/// Find the ID of the child trie containing a Consequence's Parents
///
/// Each Consequence stores its Parents in a child trie
/// This helper function calculates the id of the associated child trie.
fn parents_trie_id_from_index(index: ConsequenceIndex) -> child::ChildInfo {
    let mut buf = Vec::new();
    buf.extend_from_slice(b"consequenceparents");
    buf.extend_from_slice(&index.to_le_bytes()[..]);

    child::ChildInfo::new_default(T::Hashing::hash(&buf[..]).as_ref())
}

/// Add a parent-child relationship between two Consequences
///
/// All relationships should be added by this function to avoid corruption of data
fn add_consequence_relationship(parent_consequence: ConsequenceIndex,
    child_consequence: ConsequenceIndex,
) {
    // Add the child to the Parent's list of Children 
    let parent_children = Self::children_trie_id_from_index(parent_consequence);
    child_consequence.using_encoded(|b| child::put(&parent_children, b, &true));
    // Add the parent to the Child's list of Children 
    let child_parents = Self::parents_trie_id_from_index(child_consequence);
    parent_consequence.using_encoded(|b| child::put(&child_parents, b, &true));
}

Again, so far so good.

Now I need to iterate over my child tries and can't work out how to do it. Can anybody show me how to set up an iterator to go through each key of a child tier?

I notice that for existing storage iterators I need to know the first key. I would not, by default, know that at the time of creating my iterator.

P.S. If anybody has any smarter ideas for managing the child-parent relationships between my Consequences, they would also be greatly received.

Answer 1

You can take a look at the crowdloan pallet in Polkadot to see an example of manipulating and using a child-trie.

https://github.com/paritytech/polkadot/blob/master/runtime/common/src/crowdloan/mod.rs

To create a iterator, you can do something like this:

use frame_support::storage::{child, ChildTriePrefixIterator};

pub fn contribution_iterator(
    index: FundIndex,
) -> ChildTriePrefixIterator<(T::AccountId, (BalanceOf<T>, Vec<u8>))> {
    ChildTriePrefixIterator::<_>::with_prefix_over_key::<Identity>(
        &Self::id_from_index(index),
        &[],
    )
}

Note that in this iterator, we are specifying the known types of the key and values stored in the child-trie. For your child-trie, it may be different than the example above. After that, you can simply use the iterator as you would expect.