A problem with some generators

I am playing around with generators, and I've found this problem:

#![feature(inclusive_range_syntax, generator_trait,
           generators, conservative_impl_trait)]

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

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

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

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

    It(g)
}

fn digits_u32(mut n: u32) -> impl Iterator<Item=u32> {
    generator_to_iterator(move || {
        if n == 0 {
            yield 0;
        } else {
            const LEN: usize = 10;
            let mut digits = [0u32; LEN];
            let mut idx = LEN - 1;
            while n != 0 {
                digits[idx] = n % 10;
                n /= 10;
                idx -= 1;
            }
            for &d in &digits[idx + 1 ..] { yield d; }
            //for i in idx + 1 .. LEN { yield digits[i]; }
        }
    })
}

fn main() {
    for i in 0 .. 100 {
        print!("{}: ", i);
        for d in digits_u32(i) {
            print!("{} ", d);
        }
        println!();
    }
}

digits_u32() is supposed to yield the digits of a u32 in order (yielding them in reversed order is simpler), the error it gives is:

  --> ...\test.rs:25:5
   |
25 |     generator_to_iterator(move || {
   |     ^^^^^^^^^^^^^^^^^^^^^ `[u32]` does not have a constant size known at compile-time
   |
   = help: the trait `std::marker::Sized` is not implemented for `[u32]`
   = note: only the last element of a tuple may have a dynamically sized type

As you see from the commented out line I've already found a workaround, but is this supposed to happen, and do you know if there's a better workaround? Thank you.

1 Like

Interesting example. I suppose the issue is the range operator yields the slice and the closure type storing the slice doesn't work. Changing it to use an iterator, however, runs into "named lifetimes" issue for impl trait. I guess one could restructure the code so that the generator is created inside a function that receives a &'a [u32] so that we can have a named lifetime for the impl trait, but I've not tried this.

I think ideally you'd want to move the array into the generated type for the iterator so that no references are needed to be maintained in the state machine, but I don't immediately see how to do that without your workaround to begin with.

2 Likes

By the way, I'm surprised you didn't post this in Help test async/await/generators/coroutines! - #33 by Nemo157 - announcements - Rust Internals :slight_smile:

In a sense, I did, but I was ignored (when I tried to implement that function I had the same problem):

So that's this, which works:

fn digits_u32<'a>(mut n: u32, digits: &'a mut [u32; 10]) -> impl Iterator<Item=u32> + 'a {
    generator_to_iterator(move || {
        if n == 0 {
            yield 0;
        } else {
            let mut idx = digits.len() - 1;
            while n != 0 {
                digits[idx] = n % 10;
                n /= 10;
                idx -= 1;
            }
            for &d in digits[idx + 1 ..].iter() { yield d; }
        }
    })
}

Of course this is pretty bad, and much worse than your original workaround. As mentioned, it seems like the problem is that the iterator over the array requires a reference to the array, and this then means the compiler generated impl Iterator has a lifetime associated with it. The lifetime is to a local array, which is also captured in the closure (I suspect) so it stays live across yields. Then it sounds like we'll get into the self-referential struct case where the closure both has the array and also an iterator that references the array. I could be wrong though. I'd be interested to hear a definitive explanation on this as well.

3 Likes

This is not supposed to compile, because generator environment would need to store both the array being iterated over and the iterator borrowing it, which is not allowed for generators, as they must stay movable while suspended.

The error message, on the other hand, is very misleading.

Interestingly, if I don't pass the generator to generator_to_iterator, the message is correct:

error[E0626]: borrow may still be in use when generator yields
  --> src/main.rs:37:24
   |
37 |             for &d in &digits[idx + 1 ..] { yield d; }
   |                        ^^^^^^               ------- possible yield occurs here