Remove the `key` field from `KeyedTypeABI::Tuple` and `KeyedTypeABI::Map`

[mohammadfawaz]

They are not necessary. Only primitive types should get keys... All other keys can be inferred from them.

[mitchmindtree]

@mohammadfawaz we could potentially remove the key from the ABI output altogether if we standardise and document how storage type nesting maps to key construction. E.g.

• Top-level storage "fields" are prefixed by a single word field index.
• Array elements are prefixed by a single word array index.
• Tuple elements are prefixed by a single word tuple index.
• Map entries are prefixed by the map key encoded as words.

So far, the compiler adheres to the above already, besides for tuples. It seems tuples are currently "flattened", so the keys for foo: (i64, (i64, i64)) become [0, 0], [0, 1], [0, 2], rather than [0, 0], [0, 1, 0], [0, 1, 1].

If we were to stop flattening tuples, the key could be constructed entirely in abi-gen by maintaining a stack of key elements following the rules above during traversal of the KeyedTypeABI without the need for any key fields at all.

This might also make it a bit easier to support dynamically sized keys (e.g. strings or byte arrays) in the future, as the current key representation in the ABI output (Vec<Option<Key>> with Nones for map keys) can't support unknown sized keys.

[mohammadfawaz]

Even arrays are flattened btw.. Maps are special because we never need to read a "whole map" So the reason why tuples are flattened is the following. In the example, above { int, { int, int } }, where the keys are [0, 0], [0, 0, 0], and [0, 0, 1] respectively, how would we read the full tuple? We would have to read from [0, 0] with len 1, then from [0, 0, 0] with len 2 (to get both keys). If the tuple is flattened, all we have to do is read from [0, 0, 0] with len 3 (so a single opcode). Now, this may end up being the exact same cost in the VM in CPU cycles, but it's a bit more cumbersome to deal with.

[mohammadfawaz]

Can we standardize while keeping tuples and arrays flattened? We would still remove the keys from the ABI... Once we standardize, dynamically sized keys should be fine.

[mitchmindtree]

In the example, above { int, { int, int } }, where the keys are [0, 0], [0, 1, 0], and [0, 1, 1] respectively, how would we read the full tuple?

Do you mean how would pint generate ASM to read the full nested tuple?

I guess not having them flattened would mean that multiple separate Access::StateRange ops would be needed to read the full tuple, i.e. one for each set of consecutive leaves with a unique parent.

E.g. if we modify our example above to something like {int, int, { int, int }, int, int }, this would need three separate StateRange ops.

Maybe this would bloat the code a little more which may affect bandwidth :thinking:

Can we standardize while keeping tuples and arrays flattened?

True, it should be possible to standardise while having tuples and arrays flattened - just a little more finicky for downstream consumers of the ABI when working with tuples arrays.

I have the following PoC locally for visiting all nested keyed types and constructing the key:

/// Represents how a pub var or storage field's key is constructed.
pub(crate) enum KeyElem {
    /// A fixed word element, e.g. for a top-level field or tuple field.
    Word(Word),
    /// A key element provided by a map key. If the map key size is fixed, `len
    MapKey {
        /// The type of the key.
        ty: TypeABI,
    },
    /// A key element provided by an array index.
    ArrayIx {
        /// The total length of the array if it's known.
        array_len: Option<usize>,
    },
}

/// Represents a visited keyed var or nested type alongside it's key.
pub(crate) struct Keyed<'a> {
    /// The name of the var if it is named.
    pub(crate) name: Option<&'a str>,
    /// The type of the var.
    pub(crate) ty: &'a KeyedTypeABI,
    /// A description of the key construction.
    pub(crate) key: &'a [KeyElem],
}

/// Visit all keyed vars in `storage` or `pub_vars` alongside their associated key.
pub(crate) fn keyed_vars(vars: &[KeyedVarABI], mut visit: impl FnMut(Keyed)) {
    /// Call `visit` with the given `var` and `key`, then recurse nested vars.
    fn visit_and_recurse(
        name: Option<&str>,
        ty: &KeyedTypeABI,
        key_elems: &mut Vec<KeyElem>,
        visit: &mut impl FnMut(Keyed),
    ) {
        visit(Keyed {
            name,
            ty,
            key: &key_elems[..],
        });
        match ty {
            KeyedTypeABI::Bool(_key)
            | KeyedTypeABI::Int(_key)
            | KeyedTypeABI::Real(_key)
            | KeyedTypeABI::String(_key)
            | KeyedTypeABI::B256(_key) => {}

            // Recurse for nested tuple types.
            KeyedTypeABI::Tuple { fields, key: _ } => {
                for (i, field) in fields.iter().enumerate() {
                    let ix_word = Word::try_from(i).expect("index out of range");
                    let key_elem = KeyElem::Word(ix_word);
                    let name = field.name.as_deref();
                    key_elems.push(key_elem);
                    visit_and_recurse(name, &field.ty, key_elems, visit);
                    key_elems.pop();
                }
            }

            // Recurse for nested array element types.
            KeyedTypeABI::Array { ty, size } => {
                let array_len = Some(usize::try_from(*size).expect("size out of range"));
                let key_elem = KeyElem::ArrayIx { array_len };
                key_elems.push(key_elem);
                visit_and_recurse(None, &ty, key_elems, visit);
                key_elems.pop();
            }

            // Recurse for nested map element types.
            KeyedTypeABI::Map {
                ty_from,
                ty_to,
                key: _,
            } => {
                let ty = ty_from.clone();
                let key_elem = KeyElem::MapKey { ty };
                key_elems.push(key_elem);
                visit_and_recurse(None, &ty_to, key_elems, visit);
                key_elems.pop();
            }
        }
    }

    let mut key = vec![];
    for (i, var) in vars.iter().enumerate() {
        let ix_word = Word::try_from(i).expect("index out of range");
        let key_elem = KeyElem::Word(ix_word);
        key.push(key_elem);
        visit_and_recurse(Some(var.name.as_str()), &var.ty, &mut key, &mut visit);
        key.pop();
    }
}

This needs to be updated so that tuples construct keys for nested elements one-by-one in a depth-first visit order, but that shouldn't be too tricky.

Once implemented, we could share something like this visitor fn as a part of the pint-abi crate so that when (Rust) users need to do a traversal, they don't have to think about how to construct the keys. Edit: to clarify most apps wouldn't need it, but in case some other tool is being built with the ABI it could be handy.

[mitchmindtree]

@mohammadfawaz are arrays of tuples also flattened? E.g.

storage {
    foo: { int, int }[3],
}

for each element, does this result in the following keys:

• [0]
• [1]
• [2]
• [3]
• [4]
• [5]

or these:

• [0, 0]
• [0, 1]
• [1, 0]
• [1, 1]
• [2, 0]
• [2, 1]

And is the behaviour the same for a tuple of arrays? E.g. { int[2], int[2], int[2] }.

just checking as this does complicate abi-gen key construction a bit further still, but might be doable... will report back.

[mohammadfawaz]

Yup! Arrays of tuples are flattened all the way.

[mitchmindtree]

Yup! Arrays of tuples are flattened all the way.

And just double-checking, is the case the same for tuples containing arrays?

[mohammadfawaz]

Yup! Arrays of tuples are flattened all the way.

And just double-checking, is the case the same for tuples containing arrays?

Absolutely. We think of everything as a pile of data, except for maps, and likely other dynamic containers in the future.

[mitchmindtree]

Closed via #779.