Recursive generator in Rust

Question

I am trying to port this python prime number generator to rust using rust generators and this generator-to-iterator wrapper.

My problem is that the original implementation is recursive, and I didn't manage to get passed the following error:

error[E0720]: opaque type expands to a recursive type
  --> src/main.rs:27:29
   |
27 | fn recursive_generator() -> impl Iterator<Item = u64> {
   |                             ^^^^^^^^^^^^^^^^^^^^^^^^^ expands to a recursive type
   |
   = note: expanded type is `GeneratorToIterator<[generator@src/main.rs:28:25: 
   48:6 {u64, (), impl std::iter::Iterator}]>`

Below is the implementation of the recursive generator producing this error:

fn recursive_generator() -> impl Iterator<Item = u64> {
    GeneratorToIterator(move || {
        // Yield a few values
        yield 1;
        yield 2;
        yield 3;

        // Initialize the inner generator
        let mut inner_value: u64 = 0;
        let mut inner_generator = recursive_generator();

        // Get the first value of the inner generator
        match inner_generator.next(){
             Some(x) => inner_value += x,
             None => {},
        }

        // Yield some other values
        yield 4;
        yield 5;
        yield 6;
    })
}

The full implementation (with the GeneratorToIterator definition) can be found here.

I found this related question but I did not manage to compile their gen_to_iter function.

EDIT: Thanks to @bluss answer, I've finally been able to implement a working version of the prime number generator in rust.

Answer 1

The error explanation E0720 mentions that an impl Trait type must expand to one that doesn't contain other impl Trait types, but here the type is of course recursive, since that's the point.

This can be worked around by using boxed trait objects instead - Box<Iterator<Item=u64>> works well here and avoids the problem.

Either adjust recursive_generator to return Box<Iterator<Item=u64>>, or change the line of the recursive call to use the boxed iterator just for that recursive case.