Impl where bound surprisingly hitting type-requirement recursion limit?

help
1

Hi all,

I've got a possibly interesting example here where augmenting a type by throwing it in a unit 2-tuple (in this case, (T, ())) causes a type requirement evaluation recursion limit.

I don't believe it should be, but I'm not confident enough to label it as a compiler bug. Is someone more well-versed in quirky Rust type requirements able to point out why using a single value, or augmenting the single value (through a Box in this case) doesn't spin the type resolver, but throwing it in a tuple here does?

Any help is appreciated! :slight_smile:

use std::marker::PhantomData;
use std::any::{Any, type_name};

struct Nil;
struct Cons<X, Xs>(PhantomData<X>, PhantomData<Xs>);

trait List {}
impl List for Nil {}
impl<X, Xs> List for Cons<X, Xs> {}

trait Foo {
    type X;
}

// Single works entirely

struct Single;

impl Foo for Nil {
    type X = Single;
}

impl<X, Xs> Foo for Cons<X, Xs>
where
    Xs: Foo,
    <Xs as Foo>::X: Any,
{
    type X = Single;
}

struct Boxed;

impl Foo for Box<Nil> {
    type X = Boxed;
}

impl<X, Xs> Foo for Box<Cons<X, Xs>>
where
    Box<Xs>: Foo,
    <Box<Xs> as Foo>::X: Any,
{
    type X = Boxed;
}

// ... but tuple doesn't work when second
// `where` clause on Cons impl is uncommented

struct Tuple;

impl Foo for (Nil, ()) {
    type X = Tuple;
}

impl<X, Xs> Foo for (Cons<X, Xs>, ())
where
    (Xs, ()): Foo,
// <(Xs, ()) as Foo>::X: Any,
{
    type X = Tuple;
}


fn main() {
    println!("Foo single: {:?}", type_name::<<    Cons<(), Nil>      as Foo>::X>());
    println!("Foo boxed:  {:?}", type_name::<<Box<Cons<(), Nil>>     as Foo>::X>());
    println!("Foo tuple:  {:?}", type_name::<<(   Cons<(), Nil>, ()) as Foo>::X>());
}

(Playground)

Output:

Foo single: "playground::Single"
Foo boxed:  "playground::Boxed"
Foo tuple:  "playground::Tuple"

Errors:

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 1.01s
     Running `target/debug/playground`

...

And here's the exact same example with the 2nd where clause on the tuple variant uncommented:

use std::marker::PhantomData;
use std::any::{Any, type_name};

struct Nil;
struct Cons<X, Xs>(PhantomData<X>, PhantomData<Xs>);

trait List {}
impl List for Nil {}
impl<X, Xs> List for Cons<X, Xs> {}

trait Foo {
    type X;
}

// Single works entirely

struct Single;

impl Foo for Nil {
    type X = Single;
}

impl<X, Xs> Foo for Cons<X, Xs>
where
    Xs: Foo,
    <Xs as Foo>::X: Any,
{
    type X = Single;
}

struct Boxed;

impl Foo for Box<Nil> {
    type X = Boxed;
}

impl<X, Xs> Foo for Box<Cons<X, Xs>>
where
    Box<Xs>: Foo,
    <Box<Xs> as Foo>::X: Any,
{
    type X = Boxed;
}

// ... but tuple doesn't work when second
// `where` clause on Cons impl is uncommented

struct Tuple;

impl Foo for (Nil, ()) {
    type X = Tuple;
}

impl<X, Xs> Foo for (Cons<X, Xs>, ())
where
    (Xs, ()): Foo,
   <(Xs, ()) as Foo>::X: Any,
{
    type X = Tuple;
}


fn main() {
    println!("Foo single: {:?}", type_name::<<    Cons<(), Nil>      as Foo>::X>());
    println!("Foo boxed:  {:?}", type_name::<<Box<Cons<(), Nil>>     as Foo>::X>());
    println!("Foo tuple:  {:?}", type_name::<<(   Cons<(), Nil>, ()) as Foo>::X>());
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0275]: overflow evaluating the requirement `(Cons<_, _>, ()): Foo`
  |
  = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`playground`)
  = note: required because of the requirements on the impl of `Foo` for `(Cons<_, Cons<_, _>>, ())`
  = note: 127 redundant requirements hidden
  = note: required because of the requirements on the impl of `Foo` for `(Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, _>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, ())`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0275`.
error: could not compile `playground`

To learn more, run the command again with --verbose.
2

I've run into similar problems before; there appears to be a bug in the current trait solver that occasionally sends it on a wild goose chase. This should be equivalent, and compiles successfully:

impl<X, Xs, X2> Foo for (Cons<X, Xs>, ())
where
    (Xs, ()): Foo<X=X2>,
    X2: Any,
{
    type X = Tuple;
}

(Playground)

Edit: I found a possibly-related GitHub issue or two

4 Likes
3

Thank you so much! I thought it might be some kind of trait resolution bug!

Your trick to fix my MCVE worked perfectly on my much more complex example, so this thread is solved for now!

4

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.