Implement MaxEncodedLen for all types that don't implement it and return 0

[StackOverflowExcept1on]

Сoncept

For example, we have some type of data that can be encoded. We also have a function in the smart contract to send the encoded value to some other address.

#[derive(Debug, Encode, Decode, TypeInfo/*, MaxEncodedLen*/)]
#[codec(crate = gstd::codec)]
#[scale_info(crate = gstd::scale_info)]
pub enum FTEvent {
    Transfer {
        from: ActorId,
        to: ActorId,
        amount: u128,
    },
    // ...
    Balance(u128),
}

pub fn send<E: Encode>(program: ActorId, payload: E, value: u128) -> Result<MessageId> { ... }

If we add an implementation of MaxEncodedLen for all types that do not implement and return 0 in the max_encoded_len() method, then in this case the send(...) function will have the opportunity to choose where to encode the data type. If max_encoded_len() == 0 then encoding is done on the heap, otherwise on the stack.

pub fn send<E: Encode + MaxEncodedLen>(program: ActorId, payload: E, value: u128) -> Result<MessageId> {
    let max_encoded_len = E::max_encoded_len();
    match () {
        () if max_encoded_len == 0 => {
            //payload.encode() on the heap when max_encoded_len is not specified
            super::send_bytes(program, payload.encode(), value)
        }
        () if size <= 0x1 => {
            //use 0x1 stack size to encode
            let buf = [0u8; 0x1];
            payload.encode_to(&mut buf);
            //send_bytes(...)
        },
        () if size <= 0x2 => {
            //use 0x2 stack size to encode
            let buf = [0u8; 0x2];
            payload.encode_to(&mut buf);
            //send_bytes(...)
        },
        // ...
        () if size <= 0x4000 => {
            //use 0x4000 stack size to encode
            let buf = [0u8; 0x4000];
            payload.encode_to(&mut buf);
            //send_bytes(...)
        },
        _ => {
            //payload.encoded() on the heap when there is not enough space on the stack
            super::send_bytes(program, payload.encode(), value)
        }
    }
}

[StackOverflowExcept1on]

Encode::encoded_size() is not suitable because the documentation says that custom implementations can allocate memory.

parity-scale-codec/src/codec.rs

Lines 251 to 258 in 86e5162

	/// Calculates the encoded size.
	///
	/// Should be used when the encoded data isn't required.
	///
	/// # Note
	///
	/// This works by using a special [`Output`] that only tracks the size. So, there are no allocations inside the
	/// output. However, this can not prevent allocations that some types are doing inside their own encoding.

[ggwpez]

Implement MaxEncodedLen for all types that don't implement it and return 0

You want to implement the trait incorrectly since you rely on an implementation detail of another trait function?

Are you trying to optimize memory usage or what? Maybe rather add a MaybeMaxEncodedLen that returns Options<u32>.

[StackOverflowExcept1on]

@ggwpez yes, I just described the problem that you can't get the amount of memory to pre-allocate on the stack. Your suggestion like adding such an API is fine too:

trait MaybeMaxEncodedLen: Encode {
    fn max_encoded_len() -> Option<usize> { None }
}

#[derive(Encode)]
struct S;

// derive macro expands to:

impl MaybeMaxEncodedLen for S {} //when MaxEncodedLen is not present in the derive

impl MaybeMaxEncodedLen for S { //when MaxEncodedLen is present in the derive
    fn max_encoded_len() -> Option<usize> { Some(42) }
}

[koute]

Yeah, making MaxEncodedLen return a magic value of 0 is not going to be acceptable, and we can't just add a blanket impl for it anyway due to trait coherence issues. We'd need either another trait for this.

Maybe something like this would be better? (I'm not convinced myself; just throwing out the idea.)

pub trait EncodedLenBounds {
    const ENCODED_LEN_BOUNDS: (usize, usize);
}

1. It specifies the minimum amount of space that a type will take, and a maximum that it can. Both can be useful in certain circumstances.
2. It's a const, so there can be no funny business going on.
3. The maximum could be used to exactly allocate the necessary number of bytes on the stack to hold the encoded form without the match song and dance from @StackOverflowExcept1on's code snippet, e.g. this works:

#[inline(never)] // <- Necessary to prevent stack overflow.
fn encode_on_stack<T: EncodedLenBounds>(value: T) {
    let mut buffer = [0; T::ENCODED_LEN_BOUNDS.1];
    todo!()
}

fn encode<T: EncodedLenBounds>(value: T) {
    if T::ENCODED_LEN_BOUNDS.1 < 0x4000 {
        encode_on_stack(value)
    } else {
        todo!();
    }
}

[StackOverflowExcept1on]

@koute why then do we need a minimum in this case? Also now we don't have const fn for max_encoded_len(). This will probably take a lot of work to implement.

[koute]

why then do we need a minimum in this case?

1. You can check whether the type is variable length or not (if it's constant length then min == max).
2. When reading you can preallocate some memory even if the type's size is unbounded.

Also now we don't have const fn for max_encoded_len()

Making MaxEncodedLen::max_encoded_len non-const was a mistake. That said, const fns in traits are still unstable, so for the value to be usable in a const context and be part of a trait it cannot be a function.

This will probably take a lot of work to implement.

Well, it's not going to be easy, but it should be possible.

[StackOverflowExcept1on]

@koute btw, I'm not sure about const ENCODED_LEN_BOUNDS: (usize, usize);

Why does min have the type usize?As I said above, we want to be able to get Option<usize>. Therefore, we probably need a type (Option<usize>, Option<usize>)

#[derive(Encode)]
struct S { s: String, }

// in this case we have owned String type inside struct
// therefore, we cannot calculate the minimum and maximum size, since the string type is allocated on the heap

[koute]

Why does min have the type usize?

Because there's always going to be a minimum.

As I said above, we want to be able to get Option<usize>. Therefore, we probably need a type (Option<usize>, Option<usize>)

The problem with Option<usize> is that to use it in const contexts (to e.g. preallocate an array with the exact size you need) you need to use an expression to unwrap it, and those are currently not stable.

therefore, we cannot calculate the minimum and maximum size, since the string type is allocated on the heap

You can. The minimum's going to be 1, and the maximum's going to be 4294967300 (assuming usize is 64-bit).

[StackOverflowExcept1on]

@koute currently you cannot do #[derive(MaxEncodedLen)] on data types like String, Vec<T>. So, we need to return None to save compatibility with the current API.