Stream: wg-traits

Topic: overflow evaluating impl on wrapped type


Jack Wrenn (Jan 12 2020 at 21:30, on Zulip):

I'm doing a bit of type-level programming, and I've encountered a pattern that consistently seems to make rustc upset. I don't have a good mental model for why this is the case, and I'm hoping someone can shed some light. Playground link.

Let's say we define a type-level non-empty list, and a predicate Contains<E> that's satisfied if the type E appears in the list:

struct One<H>{}
struct Cons<H, T>{}

#[marker]
trait Contains<Needle>{}

/// The needle is the only element of the list.
impl<H> Contains<H> for One<H> {}

/// The needle is the first element of the list.
impl<H, T> Contains<H> for Cons<H, T> {}

/// The needle is in the tail of the list.
impl<E, H, T> Contains<E> for Cons<H, T>
where T: Contains<E>
{}

This works totally fine, as expected.

BUT, if we wrap each of the above types in another type, the compiler overflows evaluating the requirement Wrap<One<_>>: Contains<Wrap<_>>:

struct Wrap<T>(T);

/// The needle is the only element of the list.
impl<H> Contains< Wrap<H> > for Wrap< One<H> > {}

/// The needle is the first element of the list.
impl<H, T> Contains< Wrap<H> > for Wrap< Cons<H,T> > {}

/// The needle is in the tail of the list.
impl<E, H, T> Contains< Wrap<E> > for Wrap< Cons<H,T> >
where Wrap<T>: Contains< Wrap<E> >
{}

Why does this happen? Is there a name for what's going on here? What causes the type checker to start recursively enumerating types?

Last update: Jan 21 2020 at 08:50UTC