How to correctly use iterator strucs and filters in generic traits

help
1

I have this code which tries to create a tree of groups of data which are at the same "distance" from one another.

#[derive(Debug, PartialEq)]
pub struct Node
{
    value: u32,
    distance: u32,
    childs: Vec<Self>,
}
pub trait IterClone: Iterator + Clone {}

impl Node {

    pub fn new<I, C>(value: u32, distance: u32, mut iter: I, c: &C) -> Self where
    I: Iterator<Item = u32> + Clone,
    C: Fn(u32, u32) ->  u32
    {
        let mut r = Self {
            value,
            distance,
            childs: vec![],
        };

        while let Some(x) = iter.next() {
            r.childs.push(
                Self::new(x, r.distance, iter.clone().filter(|&v| c(v, value) == distance), c)
            )
        }
        r
    }
}

fn main() {
     let hamming = |a: u32, b: u32| -> u32
    {
        (a ^ b).count_ones()
    };

  let node = Node::new(0, 2, (0..(u8::MAX as u32)).filter(|&v| hamming(v, 0) == 2), &hamming);

  println!("{:?}", node);

}

I want the new function to take some kind of iterator as input as I don't want to have to allocate the input in memory.

The issue here seems to be that the new need to be implemented ( monomorphed?) for each actual type of I : Filter::<range, _>,
Filter::<Filter::<Range, _>, _>,
Filter::<Filter::<Filter::<Range, _>, _>, _>,
....

Compiling demo v0.1.0 (/home/jsbjr/dev/demo)
error[E0275]: overflow evaluating the requirement `for<'a> {closure@src/main.rs:37:59: 37:63}: FnMut(&'a _)`
  |
  = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`demo`)
  = note: required for `Filter<Range<u32>, ...>` to implement `Iterator`
  = note: 128 redundant requirements hidden
  = note: required for `Filter<..., ...>` to implement `Iterator`
  = note: the full name for the type has been written to '/home/jsbjr/dev/demo/target/debug/deps/demo-82a3ee1db27297eb.long-type-3730044516670567393.txt'
  = note: consider using `--verbose` to print the full type name to the console

For more information about this error, try `rustc --explain E0275`.
error: could not compile `demo` (bin "demo") due to 1 previous error

I tried to hide the type with a Box< dyn Iterator<Item = u32>> but then I can't clone the iterator to pass it to the next Nodes.

And I can't use Box< dyn Iterator<Item = u32> + Clone> because is sized and therefore not allowed for dynamic trait composition.

2

Cloning an iterator is not a good idea anyways, since iterators are supposed to change their state during iteration. So the result of the clone() is dependent on how many calls to next() have preceded it.
Instead I'd recommend to not clone iterators at all, but, if needed, clone their elements.

Of course you'd then need to rewrite your function to decide ahead of time which elements to pass to those.

3

thanks for the response,

So the result of the clone() is dependent on how many calls to next() have preceded it.

In this specific case that is the behaviour I want, I would like the cloned Iterators to iterate only over the remaining elements when they were cloned.

I don't want to clone the elements of the iterators if possible. I expect the iterator to go over millions of values and I don't want to have them all in memory when possible.

4

You get infinite type recursion because you are adding a new Filter each recursion. Ordinarily, I would suggest Box<dyn Iterator>, but you have already noticed that that doesn’t work with cloning. Given that, what I would suggest is replacing your use of Filter with an iterator adapter you wrote yourself that allows adding more conditions to an existing filter. Since your filters are all the same function with different parameters, this should be straightforward.

However, at some point in the future, it may be feasible to actually clone the Box<dyn IterClone>. This is the purpose of the CloneToUninit trait; if it worked as intended, you would simply write trait IterClone: Iterator + CloneToUninit and get the result you want. Unfortunately, it currently doesn't work with Box yet (I tried and failed), only Arc and Rc which are no good for iterators, but I see someone has posted a new PR #146381 to implement that.

1 Like
5

after lots of trial and error, i got something that compiles. can probably be simplified tho Rust Playground

6

Thanks it does work, I will need some time to understand why and how.
I will also have a look at how generated code looks like