Recursing with multiple recurse method-versions on templated type (eg. for PageTable<Level>)

Question

Why can't the rust compiler see that Test<D> has its own implementation of recursive_descent() and then use that for next.recursive_descent() in the version of recursive_descent() that gets produced for Test<C>?

use std::marker::PhantomData;

struct C;
struct D;

trait Dereffable {
    type Next;
}

impl Dereffable for C {
    type Next = D;
}

// NOTE: D is not Dereffable!

#[repr(transparent)]
struct Test<TYP> {
    addr: usize,
    _marker: PhantomData<TYP>,
}

impl<TYP: Dereffable> Test<TYP> {
    fn recursive_descent(&self) -> usize {
        let next = self.deref_inner();
        next.recursive_descent()
    }

    fn deref_inner(&self) -> &Test<TYP::Next> {
        unsafe { &*(self.addr as *const Test<TYP::Next>) }
    }
}

impl Test<D> {
    fn recursive_descent(&self) -> usize {
        self.addr
    }
}

#[test]
fn test() {
    let d = Test::<D> {
        addr: 1337,
        _marker: PhantomData,
    };

    let c = Test::<C> {
        addr: &d as *const _ as usize,
        _marker: PhantomData,
    };

    assert_eq!(c.recursive_descent(), 1337);
}

error[E0599]: the method `recursive_descent` exists for reference `&Test<<TYP as Dereffable>::Next>`, but its trait bounds were not satisfied
  --> src/tests2.rs
   |
   |         next.recursive_descent()
   |              ^^^^^^^^^^^^^^^^^ method cannot be called on `&Test<<TYP as Dereffable>::Next>` due to unsatisfied trait bounds
   |
note: trait bound `<TYP as Dereffable>::Next: Dereffable` was not satisfied
  --> src/tests2.rs
   |
   | impl<TYP: Dereffable> Test<TYP> {
   |           ^^^^^^^^^^  ---------
   |           |
   |           unsatisfied trait bound introduced here

For more information about this error, try `rustc --explain E0599`.

Answer 1

In this answer I ignore the safety of this program.

To set the bounds necessary for the implementation of recursive_descent to be correct, we need a trait RecursiveDescent:

trait RecursiveDescent {
    fn recursive_descent(&self) -> usize;
}

This allow us to implement RecursiveDescent for Test exactly when it is allowed:

impl<TYP: Dereffable> RecursiveDescent for Test<TYP>
where
    Test<TYP::Next>: RecursiveDescent
{
    fn recursive_descent(&self) -> usize {
        let next = self.deref_inner();
        next.recursive_descent()
    }
}

The entire program (playground):

use std::marker::PhantomData;

struct C;
struct D;

trait Dereffable {
    type Next;
}

impl Dereffable for C {
    type Next = D;
}

// NOTE: D is not Dereffable!

#[repr(transparent)]
struct Test<TYP> {
    addr: usize,
    _marker: PhantomData<TYP>,
}

trait RecursiveDescent {
    fn recursive_descent(&self) -> usize;
}

impl<TYP: Dereffable> RecursiveDescent for Test<TYP>
where
    Test<TYP::Next>: RecursiveDescent
{
    fn recursive_descent(&self) -> usize {
        let next = self.deref_inner();
        next.recursive_descent()
    }
}

impl<TYP: Dereffable> Test<TYP> {
    fn deref_inner(&self) -> &Test<TYP::Next> {
        unsafe { &*(self.addr as *const Test<TYP::Next>) }
    }
}

impl RecursiveDescent for Test<D> {
    fn recursive_descent(&self) -> usize {
        self.addr
    }
}


#[test]
fn test() {
    let d = Test::<D> {
        addr: 1337,
        _marker: PhantomData,
    };

    let c = Test::<C> {
        addr: &d as *const _ as usize,
        _marker: PhantomData,
    };

    assert_eq!(c.recursive_descent(), 1337);
}