Error: Reached the recursion limit while instantiating `<std::iter::Filter<std::iter::Sk...]&g-CodePudding

I have a function with following declaration:

fn find_solutions_internal<'a, I>(&self, words: I, iterate_from: usize, chain: &mut Vec<u32>)
    where I: Iterator<Item=&'a u32>   Clone;

Because the function recursively iterates over the same vector (max-depth of recursion is 5) with different filters I decided that it would be more effecient to pass the iterator as an argument.

Following part of code causes error:

let iterator = words.skip(iterate_from).filter(|&mask| mask & last_mask == 0);
let filtered_words = iterator.clone();

iterator.enumerate().for_each(|(i, &mask)| {
    chain.push(mask);
    self.find_solutions_internal(filtered_words.clone(), i, chain); // filtered_words.clone() is what indirectly causes the error
    chain.pop();
});

The error:

error: reached the recursion limit while instantiating `<std::iter::Filter<std::iter::Sk...]>::{closure#0}]>::{closure#0}]>`
115 |         self.iter.fold(init, fold)
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
note: `<std::iter::Filter<I, P> as Iterator>::fold` defined here
...

Self-contained example of the problematic code: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ada8578f166ad2a34373d82cc376921f

Working example with collected iteration to vector: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=4c13d2d0ac17038dac61c9e2d59bbab5

CodePudding user response：

As @Jmb commented, the compiler does not try figuring out how many times the function recurses, at least not for the purpose of allowing this kind of code to compile. The compiler assumes each call to find_solutions_internal() can potentially recurse, and so the compiler gets stuck repeatedly instantiating the function, as each recursive call has a unique iterator parameter type.

We can fix this problem by passing the iterator as a trait object when making the recursive call, though the fact that we're cloning the iterator complicates things, as the Clone trait doesn't work with trait objects. We can work around that with the dyn_clone crate, at the cost of some boilerplate.

First we define a clonable iterator trait:

use dyn_clone::DynClone;

trait ClonableIterator<T>: Iterator<Item = T>   DynClone {}
impl<I, T> ClonableIterator<T> for I where I: Iterator<Item = T>   DynClone {}
dyn_clone::clone_trait_object!(<T> ClonableIterator<T>);

Then in the recursive call we construct the trait object:

self.find_solutions_internal(
    Box::new(filtered_words.clone()) as Box<dyn ClonableIterator<_>>,
    i,
    chain,
);

While the above solution works, I think it'll likely end up slower than doing the simple thing of just collecting into a Vec. If the vector is really big, using a datastructure like Vector from the im crate, which supports O(1) cloning and O(log n) remove might be faster.