CODEWITHSUNDEEP
recursionrustiteratortraits
DrunkCoder
DrunkCoder

Reputation: 419

Stack overflow while evaluating trait requirement

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.

Upvotes: 2

Views: 120

Answers (2)

harmic
harmic

Reputation: 30587

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).

Upvotes: 2

Kitsu
Kitsu

Reputation: 3435

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.

Upvotes: 3

Related Questions