Cannot find chained trait impl in macros

[nventuro]

Aim

I'm running into issues with macros when dealing with relatively involved handling of traits and structs. Sorry for the bad title, I don't really know what might be going on and that's my best guess.

Expected Behavior

Ultimately what I want to do is have some types that implement Serialize, put those inside generic that also implement serialize if their fields do, and then wrap all of that in a container that can reason about the serialization lenght of whatever is inside of it. I'll try to illustrate with code (the impls are left empty as they are not relevant):

trait Serialize<let N: u32> {
    fn serialize(self) -> [Field; N];
}

trait Deserialize<let N: u32> {
    fn deserialize(value: [Field; N]) -> Self;
}

struct MyStruct {
    x: Field,
    y: Field,
}

impl Serialize<2> for MyStruct {
    fn serialize(self) -> [Field; 2] {
        std::mem::zeroed()
    }
}

impl Deserialize<2> for MyStruct {
    fn deserialize(value: [Field; 2]) -> Self {
        Self { x: 0, y: 0 }
    }
}

So far it's all quite standard. Now I'll put this inside a struct that takes a generic, and derive Serialize using arithmetic over generics:

struct MyGenericStruct<T> {
    x: T,
    y: T,
}

impl<T, let N: u32> Serialize<N + N> for MyGenericStruct<T> where T: Serialize<N> {
    fn serialize(self) -> [Field; N + N] {
        std::mem::zeroed()
    }
}

impl<T, let N: u32> Deserialize<N + N> for MyGenericStruct<T> where T: Deserialize<N> {
    fn deserialize(serialized: [Field; N + N]) -> Self {
        Self {
            x: T::deserialize(std::mem::zeroed()),
            y: T::deserialize(std::mem::zeroed()),
        }
    }
}

Lovely stuff. Now I'll define a new marker trait (because of reasons) that will be tied to the serialization length:

trait Storage<let N: u32> {}

impl<T, let N: u32> Storage<N + N> for MyGenericStruct<T> where T: Serialize<N> + Deserialize<N> { }

We expect MyGenericStruct<MyStruct> to implement Storage<4>, since T: MyStruct, which has a serialization length of 2. Note that in this example we're sort of reimplementing the notion that MyGenericStruct contains two T's by doing N+N (we'll get back to this).

I know want to find this 4 value via macros:

comptime fn storage(s: StructDefinition) -> Quoted {
    let mut result = 0;

    for field in s.fields() {
        let (_, typ) = field; 
        result = get_size(typ); // ignore the loop + reassign, I'll only call this on a single field anway
    }

    quote {
        fn storage_result() -> u32 {
            $result
        }
    }
}

comptime fn get_size(typ: Type) -> u32 {
    let storage_size = std::meta::typ::fresh_type_variable();
    assert(
        typ.implements(quote { crate::Storage<$storage_size> }.as_trait_constraint()),
        f"Attempted to fetch storage size, but {typ} does not implement the Storage trait",
    );

    storage_size.as_constant().unwrap()
}

and indeed it works!

#[test]
fn test_size() {
    assert_eq(storage_result(), 4);
}

Bug

Now I want to not have to repeat the N+N bit from above, so I change the Storage impl slightly:

impl<T, let N: u32> Storage<N> for MyGenericStruct<T> where MyGenericStruct<T>: Serialize<N> + Deserialize<N> { }

but I run into errors:

error: Attempted to fetch storage size, but MyGenericStruct<MyStruct> does not implement the Storage trait
   ┌─ src/main.nr:87:9
   │
87 │         typ.implements(quote { crate::Storage<$storage_size> }.as_trait_constraint()),
   │         ----------------------------------------------------------------------------- Assertion failed
   │
   = Call stack:
     1. src/main.nr:57:1
     2. src/main.nr:74:18

This seems wrong: MyGenericStruct definitely implements Storage as it definitely implements Serialize and Deserialize as well. Maybe the issue is that this implementation is 'derived' and hinges on arithmetic with generics?

I get the same behavior if I put MyGenericStruct on a container struct and attempt to access its Serialize impl:

struct Container<T> {
    t: T,
}

impl<T, let N: u32> Storage<N> for Container<T> where T: Serialize<N> + Deserialize<N> { }

#[storage]
struct Foo {
    my_container: Container<MyGenericStruct<MyStruct>>
}

error: Attempted to fetch storage size, but Container<MyGenericStruct<MyStruct>> does not implement the Storage trait
   ┌─ src/main.nr:81:9
   │
81 │         typ.implements(quote { crate::Storage<$storage_size> }.as_trait_constraint()),
   │         ----------------------------------------------------------------------------- Assertion failed
   │
   = Call stack:
     1. src/main.nr:58:1
     2. src/main.nr:68:18

To Reproduce

Here's a file with the above, where the two failing cases are commented out (remember to uncomment the passing case):

trait Serialize<let N: u32> {
    fn serialize(self) -> [Field; N];
}

trait Deserialize<let N: u32> {
    fn deserialize(value: [Field; N]) -> Self;
}

struct MyStruct {
    x: Field,
    y: Field,
}

impl Serialize<2> for MyStruct {
    fn serialize(self) -> [Field; 2] {
        std::mem::zeroed()
    }
}

impl Deserialize<2> for MyStruct {
    fn deserialize(value: [Field; 2]) -> Self {
        Self {
            x: 0,
            y: 0,
        }
    }
}

struct MyGenericStruct<T> {
    x: T,
    y: T,
}

impl<T, let N: u32> Serialize<N + N> for MyGenericStruct<T> where T: Serialize<N> {
    fn serialize(self) -> [Field; N + N] {
        std::mem::zeroed()
    }
}

impl<T, let N: u32> Deserialize<N + N> for MyGenericStruct<T> where T: Deserialize<N> {
    fn deserialize(serialized: [Field; N + N]) -> Self {
        Self {
            x: T::deserialize(std::mem::zeroed()),
            y: T::deserialize(std::mem::zeroed()),
        }
    }
}

trait Storage<let N: u32> {}


// This works
impl<T, let N: u32> Storage<N + N> for MyGenericStruct<T> where T: Serialize<N> + Deserialize<N> { }

#[storage]
struct Foo {
    my_container: MyGenericStruct<MyStruct>
}

// // This doesn't work
// impl<T, let N: u32> Storage<N> for MyGenericStruct<T> where MyGenericStruct<T>: Serialize<N> + Deserialize<N> { }

// #[storage]
// struct Foo {
//     my_container: MyGenericStruct<MyStruct>
// }


// // This doesn't work either
// struct Container<T> {
//     t: T,
// }

// impl<T, let N: u32> Storage<N> for Container<T> where T: Serialize<N> + Deserialize<N> { }

// #[storage]
// struct Foo {
//     my_container: Container<MyGenericStruct<MyStruct>>
// }

comptime fn storage(s: StructDefinition) -> Quoted {
    let mut result = 0;

    for field in s.fields() {
        let (_, typ) = field; 
        result = get_size(typ);
    }

    quote {
        fn storage_result() -> u32 {
            $result
        }
    }
}

comptime fn get_size(typ: Type) -> u32 {
    let storage_size = std::meta::typ::fresh_type_variable();
    assert(
        typ.implements(quote { crate::Storage<$storage_size> }.as_trait_constraint()),
        f"Attempted to fetch storage size, but {typ} does not implement the Storage trait",
    );

    storage_size.as_constant().unwrap()
}

#[test]
fn test_size() {
    assert_eq(storage_result(), 4);
}

[asterite]

Maybe there's something with N + N that doesn't work well. If you do N * 2 it seems to work fine (I think).

I'm trying to reduce the code or find simpler code to start working on fixing this. For now I found this code doesn't compiler either:

trait Serialize<let N: u32> {}

pub struct MyStruct {}

impl Serialize<1> for MyStruct {}

pub struct MyGenericStruct<T> {}

trait Storage<let N: u32> {}

impl<T, let N: u32> Storage<N + N> for MyGenericStruct<T>
where
    T: Serialize<N>,
{}

pub struct Foo {
    my_container: MyGenericStruct<MyStruct>,
}

fn foo<T>()
where
    T: Storage<2>,
{}

fn main() {
    foo::<MyGenericStruct<MyStruct>>();
}

It does compile if N + N is changed to N * 2 so I'm going to see why one works while the other doesn't.

[asterite]

So it seems we have some rules in the compiler to compute the value of a numeric generic value. For example if we need to match 4 against N * 2, so solve 4 = N * 2 we do N = 4 / 2 to get 2. We also have similar rules for N + C, N - C, etc., where C is a constant.

We could add a new rule to solve N + N = C where C is a constant to be N = C / 2. But I'm wondering if we'll eventually stop being able to solve these equations because what if you have three fields and do N + N + N = C, you'd expect to get N = C / 3 but I don't think this scales...

@jfecher What do you think?

[jfecher]

@asterite I haven't investigated this issue yet but it is true that we don't perform the transformation of N + N to 2 * N. For one, it isn't always desired. Consider if we're matching against the serialize pair impl which requires Serialize<A + B> with nested constraints Serialize<A> and Serialize<B>. If we matched Serialize<N + N> but translated that to Serialize<2 * N> then we may no longer be able to solve 2 * N = A + B. That being said, I say "may" because we could still try to solve it to A = 2 * N - B and B = 2 * N - A which we already rely on doing during monomorphization.

If the handling of N + N is the issue though this doesn't sound like a macro issue, just a limitation of arithmetic generics. In the general case there are infinitely many representations of the same number that we don't handle (e.g. we don't apply the distributive law), so the compiler can't reason about these equalities in the general case. What I'd suggest instead as a workaround when you know you have some Foo<A> that you know should be equal to a Foo<B> is to use the checked_transmute method to convert to the desired type. During monomorphization we later verify that A = B so it should be safe to use as well.