Recursive associated type

#1

Hello,

The following piece of code may be stupid but illustrates the purpose:

trait Allocator {
    fn alloc(&self) {}
}

trait Page {
    type Next: Page;
    type Alloc: Allocator;

    fn get_next(&self) -> &Self::Next;

    fn map(&self, alloc: &Self::Alloc) {
        self.get_next().map( alloc );
    }
}

I have defined a Page trait which provides a map() method taking an Allocator as an argument, whose Alloc is the associated type.

The trait has another associated type Next which will have the same type as the implementor of the trait Page, hence is bound to Page.

The map() method will get Next and call map() recursively. The problem is that the associated type Self::Alloc given in the map() definition does not match anymore when map() is called by a Next object.

The compiler complains with:

 error[E0308]: mismatched types
    self.get_next().map( alloc );
                         ^^^^^ expected associated type, found Self

  = note: expected type `&<<Self as Page>::Next as Page>::Alloc`
             found type `&<Self as Page>::Alloc`

Why doesn’t it follow the map() prototype and expect something related to Self::Next ?

It seems to lively interpret Self as Self::Next during the call to map() because of the self.get_next() call … or something like that no ?

Obviously, if i try to change the map() prototype to define something like:

fn map(&self, alloc: &<Self::Next as Page>::Alloc)

I go deeper in the inception level with an error like:

 = note: expected type `&<<<Self as Page>::Next as Page>::Next as Page>::Alloc`
            found type `&<<Self as Page>::Next as Page>::Alloc`

Any help would be welcome :slight_smile: many thanks in advance.

#2

How about:

trait Allocator {
    fn alloc(&self) {}
}

trait Page {
    type Next: Page<Alloc = Self::Alloc>;
    type Alloc: Allocator;    

    fn get_next(&self) -> &Self::Next;

    fn map(&self, alloc: &Self::Alloc) {
        self.get_next().map( alloc );
    }
}

Note we explicitly bound Next to have the same allocator type.

#3

Great, it works for this example and for a more complex one with two traits having to share an Allocator trait.
Each of them will explicitly bound their respective associated type to match the ‘local’ Allocator.

By the way, i didn’t know we could “partially” bound associated types (i mean we did nothing for Page<Next=XXX>)

Thanks again