Is there a way to implement a cartesian product over iterators that are *not cloneable*?

Question

The idea is that I want the cartesian product of iterators that are all Box<dyn...>, because I have a function higher up that returns different types of iterators, some of which must be run through the cartesian product function. However, I'm having problems with the borrow checker given that Box<dyn ..> is not cloneable. Is there any way to get around this?

The code:

fn cartesian_product<'a>(iterators: &'a mut Vec<Box<dyn Iterator<Item = Sexp> + 'a>>) -> Box<dyn Iterator<Item = Vec<Sexp>> + 'a> {
        if let Some(iter) = iterators.pop() {
            let current_iterator = iter.map(|val| vec![val]);
            let child_iterators = (Self::cartesian_product(iterators));
            let combined_iterators = current_iterator.flat_map(move |vec| { 
                
                let val = child_iterators.map(move |item| 
                    {
                        let mut vec_cloned = vec.clone();
                        let mut item_cloned = item.clone();
                        item_cloned.append(&mut vec_cloned);
                        item_cloned
                    });
                val 
            });
            Box::new(combined_iterators)
        }
        else {
            Box::new(std::iter::empty())
        }
    }

The bug, currently:

cannot move out of `child_iterators`, a captured variable in an `FnMut` closure
move occurs because `child_iterators` has type `Box<dyn Iterator<Item = Vec<sexp::Sexp>>>`, which does not implement the `Copy` trait

I tried the above function, as well as a custom iterator that also has a hard time with the borrow checker.

To be clear, I don't want to call collect at any point.

Answer 1

There are many strategies that can be employed.

First, the probably most efficient way is to collect both iterators into Vecs, then iter() it and call cartesian_product() on that. This won't work if the iterators are very big, however.

In particular, only one iterator is required to be Clone, so you can collect the shorter of them.

Another strategy will be to have a custom trait that has Iterator as a supertrait but is also cloneable as dyn Trait. For how to do that, see How to clone a struct storing a boxed trait object?.

Answer 2

very cursed code but works

use std::iter;

struct IterRestart<I: Iterator> {
    original: I,
    current: iter::Peekable<I>,
}

impl<I: Clone + Iterator> IterRestart<I>
where
    I::Item: Clone,
{
    fn new(iter: I) -> Self {
        Self {
            original: iter.clone(),
            current: iter.peekable(),
        }
    }

    fn boxed<'a>(iter: I) -> Box<dyn CartesianIterator<Item = I::Item> + 'a>
    where
        I: 'a,
    {
        Box::new(Self::new(iter))
    }
}

impl<I: Iterator> Iterator for IterRestart<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        self.current.next()
    }
}

impl<I: Clone + Iterator> CartesianIterator for IterRestart<I>
where
    I::Item: Clone,
{
    fn restart(&mut self) {
        self.current = self.original.clone().peekable();
    }

    fn current(&mut self) -> Option<Self::Item> {
        self.current.peek().cloned()
    }
}

trait CartesianIterator: Iterator {
    fn restart(&mut self);
    fn current(&mut self) -> Option<Self::Item>;
}

fn cartesian_product<E: Clone>(
    mut iterators: Vec<Box<dyn CartesianIterator<Item = E>>>,
) -> impl Iterator<Item = Vec<E>> {
    let mut buffer = iterators
        .iter_mut()
        .filter_map(|iter| iter.current())
        .collect::<Vec<_>>();
    iter::from_fn(move || {
        if buffer.len() != iterators.len() {
            return None;
        }

        iterators
            .iter_mut()
            .enumerate()
            .rev()
            .find_map(|(i, iter)| {
                iter.next();
                let no_current = iter.current().is_none();
                if no_current {
                    iter.restart();
                }
                buffer[i] = iter.current().unwrap();
                (!no_current).then_some(())
            })?;

        Some(buffer.clone())
    })
}

fn main() {
    let nums = 0..4;
    let stepped_nums = (0..8).step_by(2);
    let eh = vec![0, 17, 26];
    let mut iter = cartesian_product(vec![
        IterRestart::boxed(nums),
        IterRestart::boxed(stepped_nums),
        IterRestart::boxed(eh.into_iter()),
    ]);

    while let Some(pair) = iter.next() {
        println!("{:?}", pair);
    }
}