Recursive generator in Rust causing "recursive type" error; workaround?

Question

I have a construct of the form:

pub enum Value {
    Nil,
    Str(String),
    Seq(Vec<Value>),
}

A Value is either null, a string, or a vector of other Values, which can then in turn be any of the three options.

I'd like to make a method that lazily iterates over each String in a Value, respecting nesting. My first attempt looks something like this:

#![feature(generators)]
#![feature(generator_trait)]

use std::ops::{Generator, GeneratorState};
use std::pin::Pin;

fn gen_to_iter<G>(g: G) -> impl Iterator<Item = G::Yield>
where
    G: Generator<Return = ()> + Unpin,
{
    struct It<G>(G);

    impl<G: Generator<Return = ()> + Unpin> Iterator for It<G> {
        type Item = G::Yield;

        fn next(&mut self) -> Option<Self::Item> {
            match Pin::new(&mut self.0).resume() {
                GeneratorState::Yielded(y) => Some(y),
                GeneratorState::Complete(()) => None,
            }
        }
    }

    It(g)
}

pub enum Value {
    Nil,
    Str(String),
    Seq(Vec<Value>),
}

impl Value {
    pub fn iter_over<'a>(&'a self) -> impl Iterator<Item = &'a String> {
        let closure = move || match *self {
            Value::Nil => {}
            Value::Str(ref s) => {
                yield s;
            }
            Value::Seq(ref vs) => {
                for v in vs {
                    for i in v.iter_over() {
                        yield i;
                    }
                }
            }
        };

        gen_to_iter(closure)
    }
}

fn main() {
    let val = Value::Seq(vec![Value::Str("test".to_string())]);

    for s in val.iter_over() {
        println!("{}", s);
    }
}

(playground)

When running the above code, I get a compiler error about a recursive type, since I'm calling iter_over inside another call to iter_over:

error[E0720]: opaque type expands to a recursive type
  --> src/main.rs:34:39
   |
34 |     pub fn iter_over<'a>(&'a self) -> impl Iterator<Item = &'a String> {
   |                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expands to a recursive type
   |
   = note: expanded type is `gen_to_iter::It<[generator@src/main.rs:35:23: 47:10 self:&'a Value for<'r, 's, 't0, 't1, 't2, 't3, 't4, 't5, 't6, 't7, 't8, 't9, 't10, 't11, 't12, 't13, 't14, 't15, 't16, 't17> {&'r Value, Value, &'s std::string::String, &'t0 std::string::String, (), &'t1 std::vec::Vec<Value>, fn(&'t2 std::vec::Vec<Value>) -> <&'t2 std::vec::Vec<Value> as std::iter::IntoIterator>::IntoIter {<&'t2 std::vec::Vec<Value> as std::iter::IntoIterator>::into_iter}, &'t3 std::vec::Vec<Value>, std::slice::Iter<'t4, Value>, std::slice::Iter<'t5, Value>, &'t6 Value, &'t7 Value, fn(impl std::iter::Iterator) -> <impl std::iter::Iterator as std::iter::IntoIterator>::IntoIter {<impl std::iter::Iterator as std::iter::IntoIterator>::into_iter}, &'t9 Value, &'t10 Value, impl std::iter::Iterator, impl std::iter::Iterator, impl std::iter::Iterator, &'t14 std::string::String, &'t15 std::string::String, &'t16 std::string::String, &'t17 std::string::String, ()}]>`

Aside from abandoning a lazy approach and just using vectors, I can't seem to figure out a workaround. What are some potential avenues I can take here?

Answer 1

When generators yield, they need to store the local variables that are in scope and other values that live beyond the yield expression. Generators are enums with one variant for the initial state, one variant for each yield expression and one stateless variant for the "done" state. The generator defined in iter_over has a variant (for the yield i) that must store another instance of the same generator type (indirectly, because it's wrapped in an It). Simplified, you end up with a type like this:

enum State<'a> {
    Seq(std::slice::Iter<'a, Value>, State<'a>),
    Done,
}

This type isn't valid, and the compiler tells us why and how to fix it:

error[E0072]: recursive type `State` has infinite size
  --> src/main.rs:60:1
   |
60 | enum State<'a> {
   | ^^^^^^^^^^^^^^ recursive type has infinite size
61 |     Seq(std::slice::Iter<'a, Value>, State<'a>),
   |                                      --------- recursive without indirection
   |
   = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `State` representable

We can apply the advice given by the compiler to your situation: we can wrap the inner iterator in a Box to avoid the infinite size problem.

impl Value {
    pub fn iter_over<'a>(&'a self) -> impl Iterator<Item = &'a String> {
        let closure = move || {
            match *self {
                Value::Nil => {},
                Value::Str(ref s) => { yield s; },
                Value::Seq(ref vs) => {
                    for v in vs {
                        // This Box is necessary to give the generator a finite size.
                        for i in Box::new(v.iter_over()) {
                            yield i;
                        }
                    }
                },
            }
        };

        gen_to_iter(closure)
    }
}

---

UPDATE: A breaking change causes the above solution to no longer work. It's no longer sufficient to box the iterator. It's an error for pretty much the same reason type T = Box<T>; is invalid, even though struct T(Box<T>); is valid; only named types can be recursive. To solve this, we must hide the type behind a trait object. Boxing is still necessary; the generator must own the inner iterator, so we can't use a reference here.

impl Value {
    pub fn iter_over<'a>(&'a self) -> impl Iterator<Item = &'a String> {
        let closure = move || {
            match *self {
                Value::Nil => {},
                Value::Str(ref s) => { yield s; },
                Value::Seq(ref vs) => {
                    for v in vs {
                        // An `impl trait` type cannot refer to itself, even with indirection.
                        // https://github.com/rust-lang/rust/pull/56074#issuecomment-442982242
                        let iter = Box::new(v.iter_over()) as Box<dyn Iterator<Item = &'a String>>;
                        for i in iter {
                            yield i;
                        }
                    }
                },
            }
        };

        gen_to_iter(closure)
    }
}