error: overflow evaluating the requirement <_ as core::iter::Iterator>::Item

[mitchmindtree]

src/lib.rs:1:1: 1:1 error: overflow evaluating the requirement `<_ as core::iter::Iterator>::Item` [E0275
src/lib.rs:1 //!                                                                                         
             ^                                                                                           

The error suggests adding a recursion requirement to my crate root

note: consider adding a `#![recursion_limit="128"]` attribute to your crate

It continues to recommend doubling the recursion limit until I've raised it so high that rustc itself overflows it's stack

thread 'rustc' has overflowed its stack                                                                                                                                                            
Could not compile `mindtree_utils`.

Here's a link to the repository that is failing to build in case you would like to give it a go.

The error only appeared in the latest nightly for rustc (I'm fairly sure the crate was building fine before I updated). Here's the version of the nightly I've just downloaded which seems to have caused the failure:

rustc 1.0.0-nightly (123a754cb 2015-03-24) (built 2015-03-25)

[steveklabnik]

Can you show some code that reproduces this?

[mitchmindtree]

Alright, I think I've found the culprit (playpen link).

/// A trait that produces a clone of the previously yielded element along
/// with the current element.
pub trait ZipPrev: Iterator + Sized {
    fn zip_prev(self) -> Items<Self::Item, Self> {
        Items {
            maybe_prev: None,
            iter: self,
        }
    }
}

/// The iterator produced by the zip_prev method.
pub struct Items<A, I> {
    maybe_prev: Option<A>,
    iter: I,
}

impl<I> Iterator for Items<I::Item, I>
    where
        I: Iterator,
        I::Item: Clone,
{
    type Item = (I::Item, Option<I::Item>);
    #[inline]
    fn next(&mut self) -> Option<(I::Item, Option<I::Item>)> {
        let Items { ref mut iter, ref mut maybe_prev } = *self;
        if let Some(item) = iter.next() {
            let old_maybe_prev = maybe_prev.take();
            *maybe_prev = Some(item.clone());
            Some((item, old_maybe_prev))
        } else {
            None
        }
    }
}

impl<I> ZipPrev for I
    where
        I: Iterator,
        I::Item: Clone {}

fn main() {}

Perhaps it's the implementation of Iterator for Items<I::Item, I> where I: Iterator that's causing the recursion? The crate that this came from was compiling a couple days ago (I've only made a couple changes to clean it up a bit before sharing).

[Munksgaard]

We are having similar issues with rust-sessions. Here is the cooked down version:

use std::marker::{PhantomData, PhantomFn};

struct Chan<T> ( PhantomData<T> );

struct Eps;

struct Send<A,R> ( PhantomData<(A, R)> );

trait Dual: PhantomFn<Self> {}

impl Dual for (Eps, Eps) {}

impl <A, T> Dual for (Send<A, T>, Send<A, T>)
    where (T, T): Dual {}

fn request<R, S> (rx: Chan<R>) where (R, S): Dual {
    borrow_request(&rx)
}

fn borrow_request<R, S> (rx: &Chan<R>) where (R, S): Dual {}

That code compiles with rustc 1.0.0-dev (d5408f376 2015-03-19) but not with rustc 1.0.0-dev (b0fd67b3e 2015-03-26)

cc @laumann

[Gerstacker]

Here's another example. This fails with overflow evaluating '_ : core::marker::Sized'. Commenting one line in main and uncommenting its alternative makes the code compile.

https://gist.github.com/Gerstacker/b402c38381604e2ff117

In playpen:
http://is.gd/0bkFkN

[laumann]

What's the status of this?

The example @Munksgaard posts can be "fixed" by adding explicit type annotations to the call to borrow_request(), ie

fn request<R, S> (rx: Chan<R>) where (R, S): Dual {
    borrow_request::<R, S>(&rx)
}

but it's rather unsatisfactory, since whoever calls request() will also be forced to explicitly annotate the function call (and so on).

[Gerstacker]

This annotation workaround fixed mine as well, letting rustc get far enough to expose an embarrassing problem in my code.

[Munksgaard]

It seems like PR #23580 is the cause of this issue. Perhaps @nikomatsakis could comment on whether or not this is intentional?

[Munksgaard]

Specifically, 809a554 compiles my above snippet while 76ead08 doesn't.

[steveklabnik]

This no longer ICEs.

[Munksgaard]

Confirmed 👍

[alexreg]

I'm completely new to working with libstd, but would be happy to take this on under a mentor.

[dylanede]

I'm also getting this error in a particular case where I can't find a workaround (at least, not yet). I would also be interested in taking this on.

[dylanede]

Here's a boiled down example that exhibits the same error, and I think it is pretty minimal. As I boiled it down the exact trait bounds on the requirement in the error message reduced until it became core::marker::Sized.

trait Foo<T> {
    type Out;
}

impl Foo<()> for () {
    type Out = ();
}

//Removing this impl stops the error, despite being unrelated to the call.
impl<A, B> Foo<(A, B)> for () where (): Foo<A, Out=B> {
    type Out = ();
}

fn bar<T>(_: T) where (): Foo<T> {}

fn main() {
    bar(());
}

playpen link: http://is.gd/VBG9Sp

In the case where this popped up that this example originates from, the function call involved cannot be worked around by giving explicit type parameters (in this example, bar::<()>) as the code relies on inference to work as part of a macro, so this issue is a blocker for me.

[dylanede]

Perhaps @nikomatsakis could comment on which code in the compiler is likely to be relevant to this issue, given the reduced example I've posted?

[Manishearth]

@dylanede note that you have a recursive impl there, so while the error message could be improved, the fact that this doesn't work isn't a bug. Perhaps try structuring your traits differently?

[nikomatsakis]

Hmm. I'm not sure the extent to which this is a bug -- I'm also not sure if the minified example will turn out to be representative of the other cases where this crops up. Overflow is tricky like that.

I have to work through that impl in my head -- it is at least somewhat recursive, and the fact that it doesn't apply in one particular case isn't necessarily relevant, since the compiler may encounter an overflow just trying to figure out if it applies (this is presumably happening before we have processing the argument type, and hence we don't know that it cannot apply yet). It seems plausible we might rejigger the trait matching mechanism to make the minified example work, basically by treating the overflow case as ambiguous -- later on we might know that the argument is () and thus narrow down the set of relevant impls. That is at least a "medium complexity" change though.

In any case, certainly the error message can be vastly improved (and #30533 will help here, by giving access to the complete backtrace).

In short, I'm not sure why this issue was marked as E-Easy -- but I guess it depends on how you plan to "fix" it.

[dylanede]

@Manishearth How is the recursion a problem? Foo<(A, B)> depends on Foo<A>, but that has a grounded base case. The call to bar is depending on Foo<()>, which doesn't invoke the recursion.

[Manishearth]

@nikomatsakis the regression test for the original ICE is the easy part

[Manishearth]

@dylanede the overflow is in the definition of bar (which in turn comes from the second impl), it's just detected/reported in the wrong place AIUI.

That type of recursive impl usually doesn't work in Rust.

[dylanede]

OK, I'll see if I can at least understand the relevant code.

[nikomatsakis]

@dylanede feel to ping me on IRC (nmatsakis); if I get a moment I will try to look at what's going on a bit

[bluss]

Here's a reduction that shows where I am hitting this in ndarray.

The idea is to implement both addition of arrays and addition of array with scalar. Playground link to code.

use std::ops::{Add, DerefMut};

#[derive(Clone)]
struct Array<S>(S);

impl<A, S> Add for Array<S>
    where A: Clone + Add<Output=A>,
          S: DerefMut<Target=[A]>,
{
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        panic!()
    }
}

impl<A, S> Add<A> for Array<S>
    where A: Clone + Add<Output=A>,
          S: DerefMut<Target=[A]>,
{
    type Output = Self;
    fn add(self, rhs: A) -> Self {
        panic!()
    }
}

fn main() {
}

// error: overflow evaluating the requirement `<_ as core::ops::Deref>::Target`

My current workaround looks approximately like the following. It's suboptimal since it requires a marker trait on all allowable scalars B, and I would in fact prefer if A == B is required here.

// workaround
trait ScalarMarker { }
impl<A, S, B> Add<B> for Array<S>
    where A: Clone + Add<B, Output=A>,
          S: DerefMut<Target=[A]>,
          B: ScalarMarker
{
    type Output = Self;
    fn add(self, rhs: B) -> Self {
        panic!()
    }
}

[brson]

Triage: @bluss example still overflows.

[earthengine]

Not sure if this is relevant, but a popular lib tokio seems triggers this error when used with Rc in a certain way.

extern crate tokio_core;
extern crate tokio_io;

use std::{borrow::Borrow, rc::Rc};
use tokio_core::net::TcpStream;
use tokio_io::io::read_exact;

fn read_one(conn: Rc<TcpStream>) {
    read_exact(conn.borrow(), [0u8]);
}

Stackoverflow question

The workaround is to use

read_exact(&*conn,[0u8]);

But for new users this will just get them confused.

[aldanor]

Here's another one that overflows. Is it supposed to? (and if not, is there a workaround?)

trait X {
    type Item;
}

trait Y {
    type Item: X;
}

impl<T: Y> X for T {
    type Item = <Self::Item as X>::Item;
}

// error[E0275]: overflow evaluating the requirement `<T as X>::Item`
//  --> src/main.rs:9:12
//   |
// 9 | impl<T: Y> X for T {
//   |            ^       ^

[marmeladema]

Another somehow simple example:

use std::borrow::Cow;
enum Test <'a> {
    Int(u8),
    Array(Cow<'a, [Test<'a>]>),
}

[LukeMiles49]

It seems like this is happening whenever an associated type is referenced while it's still evaluating the impl it's defined in, here is a small example that seems like it should be fine:

trait TraitWithAssociatedType {
    type AssociatedType;
}
trait AnyTrait { }
struct StructWithImpl;
struct AnyStruct;

impl TraitWithAssociatedType for StructWithImpl where Self::AssociatedType: AnyTrait {
    type AssociatedType = AnyStruct;
}

Intuitively it seems like the overflow might be comming from infinite recursion when it tries to check the impl TraitWithAssociatedType, which requires it to evaluate Self::AssociatedType to see whether it should apply to StructWithImpl, but that means it tries to first evaluate the whole impl TraitWithAssociatedType to get AssociatedType, even if it could just use the definition type AssociatedType = AnyStruct. (Might be wrong about this, I'm not a compiler writer, that's just what seems to make sense to me.)

In this case replacing Self::AssociatedType with AnyStruct fixes the problem, but that means writing the type out in full, and there might be some places where that is either not possible or requires a lot of duplication.