Overflow evaluating the requirement `_: std::marker::Sized`

Hi folks,

I'm getting this error, which I totally believe Rust is having a problem with, but it is a bit frustrating to try and figure out what it is having a hard time with. It seems to blow some internal limit on depth, probably in some sort of recursive trait evaluation, but it won't print the stack (that I can discover) so I can't really tell where it thinks the cycle is.

I have a repo at https://github.com/frankmcsherry/trie/, which should explode with cargo build. The likely culprit is trying to evaluate whether the result of

https://github.com/frankmcsherry/trie/blob/master/src/arbor.rs#L93-L100

should be Sized or not, which ... well I think all of the types are well-founded at the call site, and it shouldn't be a big deal, but I'm guessing Rust has either found some other possible implementations, or has a wonky evaluation strategy that explores too deeply in some direction. I'm not sure, but any advice would be great!

2 Likes

I have a somewhat minimized example, which I think is a bit ... weird.

It seems there is an implementation with a where clause that is basically unrelated to the program (clue is in the name of the type ;)), but it causes explosion on e.g. playpen.

pub trait Cursor { }
impl Cursor for () { }

pub trait TrieRef {
    type Cursor: Cursor;
    fn cursor(&self) -> Self::Cursor;
}

pub struct Unrelated<L> {
    nothing: L
}

impl<'a> TrieRef for &'a Vec<u32> {
    type Cursor = ();
    fn cursor(&self) -> Self::Cursor { () }
}

// Comment me out, and everything seems to work great.
impl<'a, L> TrieRef for &'a Unrelated<L> where &'a L: TrieRef {
    type Cursor = ();
    fn cursor(&self) -> Self::Cursor { () }
}


fn test<'a, T>(reference: &'a T) -> <&'a T as TrieRef>::Cursor where &'a T : TrieRef {
    reference.cursor()
}

fn main() {
    let z = test(&Vec::<u32>::new());
}

I can see how it could cause Rust to go down a rabbit hole, maybe, but ... none of the types it is exploring:

note: consider adding a `#![recursion_limit="128"]` attribute to your crate
note: required because of the requirements on the impl of `TrieRef` for `&Unrelated<_>`
note: required because of the requirements on the impl of `TrieRef` for `&Unrelated<Unrelated<_>>`
note: required because of the requirements on the impl of `TrieRef` for `&Unrelated<Unrelated<Unrelated<_>>>`
note: required because of the requirements on the impl of `TrieRef` for `&Unrelated<Unrelated<Unrelated<Unrelated<_>>>>`
note: required because of the requirements on the impl of `TrieRef` for `&Unrelated<Unrelated<Unrelated<Unrelated<Unrelated<_>>>>>`
...

have anything to do with the program...

This looks fairly similar to another recent thread:

With eddyb and talchas, this got reduced down to

pub trait Trait {}

impl<'a> Trait for &'a u32 { }
impl<'a, T: ?Sized> Trait for &'a Box<T> where &'a T: Trait {}

fn test<'a, T>(_: &'a T) where &'a T: Trait {}

fn main() {
    test(&0u32);
}

I suspect eddyb would like me to point out that it has nothing to do with the &'a u32 implementation, and the compiler goes into a tailspin even without that, but I'm not sure I can back that up myself.

1 Like