Two posts ago I proposed a particular interface for shipping self-referential generators this year. Immediately after that, eddyb showed me a better interface, which I described in the next post. Now, to tie everything together, its time to talk about how we can integrate this into the futures ecosystem.

Starting point: this Generator API

To begin, I want to document the generator API I’ll be using in this post, which is roughly what followed from my previous post:

trait StableGenerator {
    type Yield;
    type Return;
    fn resume_stable(self: Anchor<&mut Self>) -> CoResult<Self::Yield, Self::Return>;
}

trait Generator: StableGenerator {
    fn resume(&mut self) -> CoResult<Self::Yield, Self::Return>;
}

Once again, we have two generator types, both of which have stable APIs. The first requires that the generator never move once you start calling resume, whereas the second doesn’t.

Constraining the problem

All async function are going to return either a Generator or a StableGenerator, possibly wrapped in a newtype. Ideally, this type would implement Future in some way - it would be able to possible to call combinators on it, await it, and put it on an event loop.

However, the core method of Future is poll, which does not restrict the type from being moved between calls to poll. For generators which need to be held stable, we cannot just implement Future on the generator - we can only implement it on an anchored generator. But we don’t want to anchor the generator before we pass it to a combinator, since this will probably require us to heap allocate it.

On the other hand, we anticipate that we will need to heap allocate the future before putting it on the event pool. The event loop is expected to be able to dynamically dispatch between multiple types of futures. Our goal is not to eliminate all heap allocations, but collapse them into the single allocation we use when putting the future on the event loop.

These are the things we need:

1. A way to apply await to a stable generator without heap allocation.
2. A way to apply a combinator to a stable generator without heap allocation.

Solving await

Await has the semantics of consuming a future and then continuously polling it, yielding when its not ready. Today, it expands something like this:

// This
await!(future)

// Expands like this
loop {
    match future.poll() {
	Ok(Async::NotReady)	=> yield,
	Ok(Async::Ready(data)) 	=> Ok(data),
	Err(error)		=> Err(error),
    }
}

Importantly, once you await a future, you can’t do anything with it again. This gives us the leeway to anchor the future without changing semantics:

await!(future);

loop {
    let future = Anchor::pinned(&mut pin(future));
    match future.poll() {
	Ok(Async::NotReady)	=> yield,
	Ok(Async::Ready(data)) 	=> Ok(data),
	Err(error)		=> Err(error),
    }
}

Solving combinators

Combinators are trickier: you actually are moving the future around when you use them. We need to make sure that you don’t poll a generator, then move it into a combinator after the fact, while still letting you apply combinators to the generator before you start polling it.

An opening arrives in the form of a recently planned change to futures - all of the combinators are being moved to a trait called FutureExt. The currently envisioned API of futures looks like this:

pub trait Future {
    type Item;
    type Error;

    fn poll(&mut self) -> Poll<Self::Item, Self::Error>;
}

pub trait FutureExt {
    // All the combinators are here
}

impl<T: Future> FutureExt for T {
   // ...
}

However, we can introduce a hitch into this by adding a third trait, analogous to the StableGenerator trait above:

pub trait StableFuture {
    type Item;
    type Error;

    fn poll_stable(self: Anchor<&mut Self>) -> Poll<Self::Item, Self::Error>;
}

impl<T: StableFuture + ?Sized> Future for Anchor<Box<T> {
    type Item = T::Item;
    type Error = T::Error;

    fn poll(&mut self) -> Poll<Self::Item, Self::Error> {
        self.as_mut().poll_stable()
    }
}

Now that we have this available, we can change the impls like so:

// Any Future can be a StableFuture
impl<T: Future + ?Sized> StableFuture for T {
     type Item = <T as Future>::Item;
     type Error = <T as Future>::Error;

    fn poll_stable(self: Anchor<&mut Self>) -> Poll<Self::Item, Self::Error> {
        T::poll(unsafe { Anchor::get_mut(self) })
    }
}

// Because all Futures are StableFutures, this blanket impl is strictly broader
// than the previous blanket impl of FutureExt for T: Future.
impl<T: FutureStable> FutureExt for T {
    // ...
}

Tada! Now you can call combinators on any future, whether it has to be kept stable while polling or not.

Caveat: some combinators are not stable-compatible

However, there are actually some combinators which - as a part of their API - move their underlying future after polling it. These combinators are not compatible with StableFuture, and need to also be bound Future. The most important of these is the current select combinator, which evaluates to the result of one of its futures as well as the other unfinished future, allowing you to keep polling it. This API is inherently incompatible with unanchored immovable futures, and we’ll need to decide what to do about that.

Combinators like this just have to be bound where Self: Future and they can still live in FutureExt.

Conclusion

So at this point we’ve built up exactly the abstraction we wanted to have:

• We can support self-referential generators with a safe API.
• We can await a self-referential future without allocating it.
• We can apply combinators to a self-referential future without allocating it.
• We only need to allocate once, when putting the future onto the event loop.

This is not only performant, it is also significantly more ergonomic than the current API of futures. No longer do you need to reference count data which you want to use before and after a yield point. This solves some of the most important pain points in the futures ecosystem.

But there are still many questions left to resolve before we get to stable. The names and hierarchies of the APIs discussed in this series are a total open question, and there are several slight variants on them which we need to decide the trade offs between. We haven’t even tried to address the syntax of generators and async functions in all of their variations; this remains a wide set of open questions that need to be resolved before stabilization.

Over the next few weeks we’ll continue to explore these questions, possibly in a continuation of this blog series or possibly in other ways. I hope to have some RFCs relating to this subject ready by early March.