Stack overflow while evaluating trait requirement

Question

I have a function that takes a mutable reference to any iterator over given Items. The function can usually consume the items one-by-one, but occasionally has to perform lookahead. The item retrieved like this will sometimes be consumed, but sometimes has to be "prepended" back to the iterator (using e.g. a Chain), over which this function must then recurse.

However, the execution crashes at runtime while resolving trait requirements:

error[E0275]: overflow evaluating the requirement `std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, &mut std::iter::Chain<std::vec::IntoIter<std::string::String>, ...

The minimal code is (the condition here expresses that unlimited recursion depth cannot be reached):

fn foo<I: Iterator<Item = String>>(it: &mut I) -> String {
    if *(&1) == 1 {
        String::new()
    } else {
        foo(&mut vec![String::new()].into_iter().chain(it))
    }
}

fn main() {
    let mut it = vec!["Hello".to_string(), "World!".to_string()].into_iter();
    println!["{:?}", foo(&mut it)];
}

Playground

Changing the function to accept a trait object resolves the problem, but I'm not keen on using dynamic dispatch for this simple situation.

Do I have to restructure the code, use trait objects, or is there another solution to stop the checker from recursing indefinitely?

I'm using Rust 1.44.1 on x86_64-apple-darwin, but it crashes under nightly too.

Have you explored using [`peekable`](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.peekable) to avoid removing the entry from the iterator if you don't want to? — loganfsmyth, Jul 07 '20 at 20:45
See also [Why do I get “overflow evaluating the requirement” when rewriting a function using Diesel's traits into a trait method?](https://stackoverflow.com/q/56341062/155423); [Curiously recurring generic trait pattern: overflow evaluating the requirement](https://stackoverflow.com/q/50657585/155423); [Overflow evaluating the requirement when returning a recursive iterator using impl trait](https://stackoverflow.com/q/53989219/155423); [What does “Overflow evaluating the requirement” mean and how can I fix it?](https://stackoverflow.com/q/31196422/155423) — Shepmaster, Jul 08 '20 at 01:25
See also [What's going on with this bizarre recursive type error in Rust?](https://stackoverflow.com/q/53405287/155423); [Why do I get “overflow evaluating the requirement `Sized`” when using tokio_io's read_exact with a Rc?](https://stackoverflow.com/q/50189976/155423) — Shepmaster, Jul 08 '20 at 01:26

score 3 · Accepted Answer · answered Jul 07 '20 at 22:12

Your error-case might be simplified to:

fn f(i: impl Iterator<Item = ()>) {
    f(std::iter::once(()).chain(i)) // resolves to f(Chain<Once, I>)
}

fn main() {
    f(vec![].into_iter())
}

which lead to an error:

overflow evaluating the requirement `std::iter::Chain<std::iter::Once<()>, std::iter::Chain<std::iter::Once<()>, ..>>

This happens, because static dispatch must be instantiated at compile time. Compiler might assume that the depth would be, let say, 10, but what should be executed if it reaches depth 11? The straightforward solution you've already mentioned is a dynamic dispatch via trait object, for your case will look like this:

fn foo<I: Iterator<Item = String>>(it: &mut I) -> String {
    if *(&1) == 1 {
        String::new()
    } else {
        let mut it: Box<dyn Iterator<Item = _>> =
            Box::new(vec![String::new()].into_iter().chain(it));
        foo(&mut it) // might also case in-place with `as Box<dyn Iterator...>`
    }
}

The other way would be replacing recursion with iteration (which might also reduce compilation time), as @loganfsmyth noted peekable might be a good fit for you. Besides, seq might also be helpful for that case.

Thanks. Peekable was the solution I went for, since I have to let the deeper recursing frames to mutate the iterator. — DrunkCoder, Jul 08 '20 at 08:42

score 2 · Answer 2 · answered Jul 08 '20 at 04:17

As @Kitsu's answer explains, your current code is problematic because compiler is unable to figure out how deep the recursion may go.

Taking a step back from your current approach, if your basic requirement is for your function to:

Take one or more values from the iterator
Depending some logic, either:
- Return a result, or
- Put the values back to the iterator and then recurse into itself

then this could be a solution:

fn foo<I: Clone + Iterator<Item = String>>(mut it: I, n: i32) -> String {
    let mut start_iter = it.clone();
    let s = it.next();
    if n>4 {
        "Done".to_string()
    } else {
        foo(start_iter, n+1)
    }
}

fn main() {
    let mut it = ["apples", "bananas", "oranges", "mandarins", "peaches", "pears"].iter()
        .map(|s| s.to_string()).collect::<Vec<String>>().into_iter();
    println!["{:?}", foo(it, 0)];
}

I assume you must have some other state which allows the function to determine when to stop recursing - in my contrived example I have just passed down an additional i32 parameter.

Note that iterators are typically cheap to clone (probably a lot cheaper than constructing a chain iterator, especially a boxed one).

Stack overflow while evaluating trait requirement

2 Answers2