Tracking issue for RFC 2033: Experimentally add coroutines to Rust

[aturon]

RFC.

This is an experimental RFC, which means that we have enough confidence in the overall direction that we're willing to land an early implementation to gain experience. However, a complete RFC will be required before any stabilization.

This issue tracks the initial implementation.

related issues

[alexcrichton]

cc #43076, an initial implementation

[mitranim]

Copied from #43076:

---

I'm using this branch for stream-heavy data processing. By streams I mean iterators with blocking FS calls. Because Generator is missing an Iterator or IntoIterator implementation, you must call your own wrapper. Zoxc kindly provided an example, but it's quite unergonomic. Consider:

Python:

def my_iter(iter):
    for value in iter:
        yield value

Rust with generators:

fn my_iter<A, I: Iterator<Item=A>>(iter: I) -> impl Iterator<Item=A> {
    gen_to_iter(move || {
        for value in iter {
            yield value;
        }
    })
}

Two extra steps: inner closure + wrapper, and, worse, you have to write the wrapper yourself. We should be able to do better.

TL:DR: There should be a built-in solution for Generator→Iterator.

[silene]

I was a bit surprised that, during the RFC discussion, links to the C++ world seemed to reference documents dating back from 2015. There have been some progress since then. The latest draft TS for coroutines in C++ is n4680. I guess the content of that draft TS will be discussed again when the complete RFC for Rust's coroutines is worded, so here are some of the salient points.

First, it envisions coroutines in a way similar to what this experimental RFC proposes, that is, they are stackless state machines. A function is a coroutine if and only if its body contains the co_await keyword somewhere (or co_yield which is just syntactic sugar for co_await, or co_return). Any occurrence of co_await in the body marks a suspension point where control is returned to the caller.

The object passed to co_await should provide three methods. The first one tells the state machine whether the suspension should be skipped and the coroutine immediately resumed (kind of a degenerate case). The second method is executed before returning control to the caller; it is meant to be used for chaining asynchronous tasks, handling recursive calls, etc. The third method is executed once the coroutine is resumed, e.g. to construct the value returned by the co_await expression. When implementing most generators, these three methods would have trivial bodies, respectively { return false; }, {}, and {}.

Various customization mechanisms are also provided. They tell how to construct the object received by the caller, how to allocate the local variables of the state machine, what to do at the start of the coroutine (e.g. immediately suspend), what to do at the end, what do to in case of an unhandled exception, what to do with the value passed to co_yield or co_return (how yielded values are passed back to the caller is completely controlled by the code).

[arielb1]

One subtle point that came up is how we handle the partially-empty boxes created inside of box statements with respect to OIBITs/borrows.

For example, if we have something like:

fn foo(...) -> Foo<...> {}
fn bar(...) -> Bar<...> {}
box (foo(...), yield, bar(...))

Then at the yield point, the generator obviously contains a live Foo<...> for OIBIT and borrow purposes. It also contains a semi-empty Box<(Foo<...>, (), Bar<...>)>, and we have to decide whether we should have that mean that it is to be treated like it contains a Box, just the Foo<...>, or something else.

[masonk]

I might be missing something in the RFC, but based on the definition of resume in the Generator struct, and the given examples, it looks like these generators don't have two way communication. Ideally this language construct would allow us to yield values out and resume values into the generator.

Here's an example of implementing the async/await pattern using coroutines in ES6. The generator yields Promises and the coroutine resumes the generator with the unwrapped value of a Promise each time the Promise completes. There is no way this pattern could have been implemented without the two-way communication.

Rust has a problem here because what's the type of resume? In the ES6 example, the generator always yields out some kind of Promise and is always resumed with the unwrapped value of the Promise. However the contained type changes on each line. In other words, first it yields a Promise<X> and is resumed with an X, and then it yields a Promise<Y> and is resumed with a Y. I can imagine various ways of declaring that this generator first yields a Wrapper<X> and then a Wrapper<Y>, and expects to be resumed with an X and then a Y, but I can't imagine how the compiler will prove that this is what happens when the code runs.

TL;DR:
yield value is the less interesting half. It has the potential to be a much more ergonomic way to build an Iterator, but nothing more.

let resumedValue = yield value; is the fun half. It's what turns on the unique flow control possibilities of coroutines.

(Here are some more very interesting ideas for how to use two-way coroutines.)

[mikeyhew]

@arielb1

Then at the yield point, the generator obviously contains a live Foo<...> for OIBIT and borrow purposes. It also contains a semi-empty Box<(Foo<...>, (), Bar<...>)>, and we have to decide whether we should have that mean that it is to be treated like it contains a Box, just the Foo<...>, or something else.

I don't know what you mean by "OIBIT". But at the yield point, you do not have a Box<(Foo<...>, (), Bar<...>)> yet. You have a <Box<(Foo<...>, (), Bar<...>)> as Boxed>::Place and a Foo<...> that would need to be dropped if the generator were dropped before resuming.

[clarfon]

Looking at the API, it doesn't seem very ergonomic/idiomatic that you have to check if resume returns Yielded or Complete every single iteration. What makes the most sense is two methods:

fn resume(&mut self) -> Option<Self::Yield>;
fn await_done(self) -> Self::Return;

Note that this would technically require adding an additional state to closure-based generators which holds the return value, instead of immediately returning it. This would make futures and iterators more ergonomic, though.

I also think that explicitly clarifying that dropping a Generator does not exhaust it, stopping it entirely. This makes sense if we view the generator as a channel: resume requests a value from the channel, await_done waits until the channel is closed and returns a final state, and drop simply closes the channel.

[jnferner]

Has there been any progress regarding the generator -> iterator conversion? If not, is there any active discussion about it somewhere? It would be useful to link it.
@Nemikolh and @uHOOCCOOHu, I'm curious about why you disagree with @clarcharr's suggestion. Care to share your thoughts?

[phaux]

Has there been any progress regarding the generator -> iterator conversion? If not, is there any active discussion about it somewhere?

https://internals.rust-lang.org/t/pre-rfc-generator-integration-with-for-loops/6625

[Flupp]

I was looking at the current Generator-API and immediately felt uneasy when I read

If Complete is returned then the generator has completely finished with the value provided. It is invalid for the generator to be resumed again.

Instead of relying on the programmer to not resume after completion, I would strongly prefer if this was ensured by the compiler. This is easily possible by using slightly different types:

pub enum GeneratorState<S, Y, R> {
    Yielded(S, Y),
    Complete(R),
}

pub trait Generator where Self: std::marker::Sized {
    type Yield;
    type Return;
    fn resume(self) -> GeneratorState<Self, Self::Yield, Self::Return>;
}

(see this rust playground for a small usage example)

The current API documentation also states:

This function may panic if it is called after the Complete variant has been returned previously. While generator literals in the language are guaranteed to panic on resuming after Complete, this is not guaranteed for all implementations of the Generator trait.

So you might not immediately notice a resume-after-completion at runtime even when it actually occurs. A panic on resume-after-completion needs additional checks to be performed by resume, which would not be necessary with the above idea.

In fact, the same idea was already brought up in a different context, however, the focus of this discussion was not on type safety.

I assume there are good reasons for the current API. Nevertheless I think it is worth (re)considering the above idea to prevent resume-after-completion. This protects the programmer from a class of mistakes similar to use-after-free, which is already successfully prevented by rust.

[Nemo157]

I too would have preferred a similar construction for the compile time safety. Unfortunately, that construction doesn't work with immovable generators, once they have been resumed they can't ever be passed by value. I can't think of a way to encode that constraint in a similar way for pinned references, it seems you need some kind of affine reference that you can pass in and recieve back in the GeneratorState::Yielded variant rather than the current lifetime scoped Pin reference.

[clarfon]

A resume/await_done version seems much more ergonomic than moving the generator every time resume is called. And plus, this would prevent all of @withoutboats' work on pinning from actually being applied.

[rpjohnst]

Note that Iterator has a similar constraint- it's not really a big deal, it doesn't affect safety, and the vast majority of users of the trait don't even have to worry about it.

[Lisoph]

Question regarding the current experimental implementation: Can the yield and return types of generators (move-like syntax) be annotated? I would like to do the following:

use std::hash::Hash;

// Somehow add annotations so that `generator` implements
// `Generator<Yield = Box<Hash>, Return = ()>`.
// As of now, `Box<i32>` gets deduced for the Yield type.
let mut generator = || {
    yield Box::new(123i32);
    yield Box::new("hello");
};

[Nemo157]

I was hopeful that let mut generator: impl Generator<Yield = Box<Debug>> = || { ... }; might allow this, but testing with

fn foo() -> impl Generator<Yield = Box<Debug + 'static>> {
    || {
        yield Box::new(123i32);
        yield Box::new("hello");
    }
}

it seems the associated types of the return value aren't used to infer the types for the yield expression; this could be different once let _: impl Trait is implemented, but I wouldn't expect it to be.

(Note that Hash can't be used as a trait object because its methods have generic type parameters which must go through monomorphization).

One terrible way to do this is to place an unreachable yield at the start of the generator declaring its yield and return types, e.g.:

let mut generator = || {
    if false { yield { return () } as Box<Debug> };
    yield Box::new(123i32);
    yield Box::new("hello");
};

EDIT: The more I look at yield { return () } as Box<Debug> the more I wonder how long till Cthulu truly owns me.

[Lisoph]

Yeah, I was hoping as well impl Trait would do the trick, but couldn't get it to work either. Your if false { yield { return () } as Box<Debug> }; hack does indeed work, though after seeing that, I don't think I will be able to sleep for tonight.

I guess the only way is to introduce more syntax to annotate the types?

[Diggsey]

Will the Generator::resume() method be changed to use Pin<Self> and be safe, or is the idea to add a new SafeGenerator trait?

[Nemo157]

I assumed that it would be changed, and I happened to be looking at the Pin RFC just now and noticed that it agrees, but it is blocked on object safety of arbitrary self types (which is currently an open RFC):

Once the arbitrary_self_types feature becomes object safe, we will make three changes to the generator API:

1. We will change the resume method to take self by self: Pin<Self> instead of &mut self.
2. We will implement !Unpin for the anonymous type of an immovable generator.
3. We will make it safe to define an immovable generator.

The third point has actually happened already, but it doesn't help much since that required making Generator::resume unsafe.

[Nemo157]

I can confirm that the following definition of Generator works with the changes in #54383 (full playground of what I tested):

trait Generator {
    type Yield;
    type Return;

    fn resume(self: Pin<&mut Self>) -> GeneratorState<Self::Yield, Self::Return>;
}

impl<G> Generator for Pin<G>
where
    G: DerefMut,
    G::Target: Generator
{
    type Yield = <<G as Deref>::Target as Generator>::Yield;
    type Return = <<G as Deref>::Target as Generator>::Return;

    fn resume(self: Pin<&mut Self>) -> GeneratorState<Self::Yield, Self::Return> {
        <G::Target as Generator>::resume(Pin::get_mut(self).as_mut())
    }
}

I'm going to have a look whether I can figure out the changes to make the MIR transform match this trait as well.

[clarfon]

Going to again point out what I mentioned earlier: rather than a single resume method, I honestly think that resume should return Option<Yield> and that there should be a separate await method that consumes self and returns Return.

[omni-viral]

Why generator doesn't accept values on resume?
It'd be great to have yield return value provided into resume.

[omni-viral]

@clarcharr you can implement such
await with current API.

[dylanede]

Any update on whether Generator is going to be changed to depend on GATs, as suggested by #43122 (comment)?

The strange behaviour mentiond in #43122 (comment) is still reproducible as well.

[clarfon]

@omni-viral Both definitions of generators can be written in terms of each other. I was more stating that I feel a double-method approach is more ergonomic for consumers.

[Nemo157]

@clarcharr how do you write the pinned version in terms of a version of Generator that consumes self? Once it's pinned you're not allowed to move it so there is no way to produce a value to pass into await.

[clarfon]

Oh, right.

It's unfortunate we don't have a way to do a form of consume-and-drop with the Pin API.

[newpavlov]

Why Generator trait cares about immovability of the implementer, while Iterator does not? I am afraid Generator development is too heavily influenced with async use-cases, which results in an unfortunate disregard towards potential synchronous uses.

[clarfon]

I'm fairly certain that Iterator would get the same treatment if it could be changed in a non-breaking way.

[Nemo157]

@newpavlov note that only static generators are immovable. If you look at the testcases in the linked PR (e.g. https://github.com/rust-lang/rust/pull/55704/files#diff-d78b6984fcee145621a3415c60978b88) there's no unsafety required to deal with a non-static generator anymore, you just have to wrap references in Pin::new() before calling resume.

This also means you can have a fully safe generic Iterator implementation for a wrapped generator by requiring a Generator + Unpin (which can also be passed a Pin<Box<dyn Generator>> (or stack-pinned variant of) if you want to define an iterator via an immovable generator).

I was recently wondering if adding an &mut variant of resume for Unpin generators would be useful, e.g.

     fn resume_unpinned(&mut self) -> GeneratorState<Self::Yield, Self::Return> where Self: Unpin {
        Pin::new(self).resume()
     }

but I can't think of a name that seems short enough to be worth it.

[Nemo157]

@newpavlov also, not supporting immovability drastically lowers the usefulness of generators for pretty much all usecases, e.g. an iterator-generator as simple as

|| {
    let items = [1, 2, 3];
    for &i in &items {
        yield i;
    }
}

runs afoul of error[E0626]: borrow may still be in use when generator yields.

[newpavlov]

@Nemo157
I guess I will repeat the question (couldn't find an answer with a cursory search), but could you remind me why Generator can not be implemented only for pinned self-referential types? In other words your snippet will automatically pin the generator closure.

[Nemo157]

will automatically pin the generator closure

but where will it be pinned? To construct efficient adaptors you need to be able to pass the generator around by value as you add layers on, only once you want to actually use it do you pin the top level and have that pinning apply to the entire structure at once.

It could be automatically pinned to the heap via Pin<Box<_>> but then you have an indirection between each layer of adaptors.

[newpavlov]

You can distinguish between safe and unsafe generators, you will pass around by value "unsafe" generator, it will not implement Generator trait, but could instead implement something like UnsafeGenerator with an unsafe resume method. And we will have impl<T: UnsafeGenerator> Generator for Pin<T> { .. }, thus to safely use the resulting generator you will have to pin it first, which can be done either automatically or manually.

[Nemo157]

With #55704 we can distinguish between potentially self-referential and guaranteed movable generators, they're named Generator and Generator + Unpin respectively. Neither of them require any unsafe code to interact with.

[newpavlov]

My point is that I am looking forward to using Generators in a synchronous code and implementing it manually for custom structs, so baking Pin semantics into the trait seems suspicious to me.

[Nemo157]

It's trivial to opt-out of pinning and use Generator still, I think this is a key part of providing all the potential power of generators, then allowing more user-friendly abstractions to be built on top of them that might restrict that in some way. Since Iterator can't be adapted to support pinned values directly you just opt-out in the adaptation layer and force users to pin any self-referential generator they want to use with it:

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

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

let gen = || { yield 5; yield 6; };
for item in gen {
    println!("{}", item);
}

let gen = static || { yield 5; yield 6; };
for item in Box::pinned(gen) {
    println!("{}", item);
}

[newpavlov]

So why use this approach instead of the UnsafeGenerator which I've proposed earlier? IIUC both are essentially equivalent to each other, but with yours users have to learn about Pin semantics even if do not work with self-referential structs.

[clarfon]

I do agree that the burden of figuring out how to work with self-referential structs should be put on the creators of the self-referential structs, rather than in the API for something like Generator.

For example, why is it that we can't just use &mut self as usual and pass in an &mut PinMut<'a_ T> instead? It seems silly, but it does get around having to put this weird API in the Generator trait.

[yuriks]

If your generator is Unpin, then all someone has to do to use it is to do Pin::new(generator). In return, people who have generators that are not Unpin can also use your code and abstractions on their generators. The Pin API was designed so that pointers to structs which are not self-referential can be easily be put in and out of a Pin. Having a separate UnsafeGenerator trait would force everyone to implement things twice, once for UnsafeGenerator and once for Generator.

[yuriks]

Also, you keep implying that somehow self-referential generators are only relevant for async i/o use cases, but that's not at all true. Any generator that uses borrows to local variables (like this example in this thread) will need to be self-referential.

[newpavlov]

Having a separate UnsafeGenerator trait would force everyone to implement things twice, once for UnsafeGenerator and once for Generator.

Why is that? I don't see why impl<T: UnsafeGenerator> Generator for Pin<T> { .. } wouldn't work.

[Pauan]

@newpavlov Just to make it clear: Pin has absolutely nothing whatsoever to do with asynchronous vs synchronous.

The reason for Pin is to allow for borrowing across yield points, which is necessary/useful for both asynchronous and synchronous code.

Pin just means "you cannot move this value", which allows for self-referential references.

If your struct does not need to pin anything, then a Pin<&mut Self> is the same as &mut Self (it uses DerefMut), so it is just as convenient to use.

It is only when your struct needs to pin something that you need to deal with the complexity of Pin.

In practice that means the only time you need to deal with Pin is if you are creating abstractions which wrap other Generators (like map, filter, etc.)

But if you're creating standalone Generators then you don't need to deal with Pin (because it derefs to &mut Self).

Why is that? I don't see why impl<T: UnsafeGenerator> Generator for Pin<T> { .. } wouldn't work.

Let's suppose we did that. That means that now this code won't work:

let unsafe_generator = || {
    let items = [1, 2, 3];
    for &i in &items {
        yield i;
    }
};

unsafe_generator.map(|x| ...)

It doesn't work because the map method requires self to be a Generator, but unsafe_generator is an UnsafeGenerator.

And your Generator impl requires UnsafeGenerator to be wrapped in Pin, so you would need to use this instead:

let unsafe_generator = || {
    let items = [1, 2, 3];
    for &i in &items {
        yield i;
    }
};

let unsafe_generator = unsafe { Pin::new_unchecked(&mut unsafe_generator) };
unsafe_generator.map(|x| ...)

And now you must carefully ensure that unsafe_generator remains pinned, and is never moved. Hopefully you agree that this is much worse than the previous code.

---

If instead we require Pin<&mut Self> for the resume method, that means we don't need to do any of that funky stuff, we can just pass unsafe_generator directly to map, and everything works smoothly. Unsafe generators can be treated exactly the same as safe generators!

The difference with your system and the Pin<&mut Self> system is: where is the Pin created?

With your system, you must manually create the Pin (such as when passing unsafe_generator to another API which expects a Generator).

But with Pin<&mut Self> you don't need to create the Pin: it's created automatically for you.

[ishitatsuyuki]

Has there been any discussions about avoiding more than one Box allocation when embedding an immovable generator inside another? That's basically what happens in C++ for optimization purpose, but in Rust we probably need that in the type system.

Another optimization question is about safe-to-move references: particularly, dereferenced Vec references will not change even if the generator moves, but due to how the types work it still requires an immovable generator for now.

[Nemo157]

No boxes are needed, see https://docs.rs/pin-utils/0.1.0-alpha.4/pin_utils/macro.pin_mut.html for stack pinning that works even for generators in generators.