Mutually recursive `async fn`s are hard to make `Send`

[cramertj]

There are several other related issues to this, but I'm opening this to track this one specifically since it's a pain-- there are workarounds, but it'd be lovely (and should be possible) to make this "just work." The following example compiles just fine without + Send, but adding the Send bound causes a cycle error:

#![feature(async_await)]

use {
    std::{
        future::Future,
        pin::Pin,
    },
};

type BoxFuture = Pin<Box<dyn Future<Output = ()> /* + Send */>>; // adding Send causes a cycle error

async fn foo() -> BoxFuture {
    Box::pin(bar()) as _
}

async fn bar() {
    let _ = foo().await;
}

Working around the cycle error is possible, but annoying:

#![feature(async_await)]

use {
    std::{
        future::Future,
        pin::Pin,
    },
};

type BoxFuture = Pin<Box<dyn Future<Output = ()> + Send>>;

async fn foo() -> BoxFuture {
    box_bar()
}

fn box_bar() -> BoxFuture {
    Box::pin(bar())
}

async fn bar() {
    let _ = foo().await;
}

Ideally we wouldn't have a cycle error in either case, since it is possible to see that foo must be Send without ever looking at the body of bar, since bar is immediately boxed into a BoxFuture.

[nikomatsakis]

So this is tied to cycles amongst impl Trait. The problem arises because we need to know the hidden type of bar, which in turn is tied to the hidden type of foo, in order to figure out the whether the result of bar() will be Send. The easiest workaround here is to desugar to something that returns impl Future + Send:

#![feature(async_await)]

use {
    std::{
        future::Future,
        pin::Pin,
    },
};

type BoxFuture = Pin<Box<dyn Future<Output = ()> + Send>>; // adding Send causes a cycle error

fn foo() -> impl Future<Output = BoxFuture> + Send {
    async {
        Box::pin(bar()) as BoxFuture
    }
}

async fn bar() {
    let _ = foo().await;
}

fn main() { }

[nikomatsakis]

It's tricky but not impossible to imagine a more flexible handling of auto traits and leakage. We've discussed it before and it's probably a good idea. But I think it's pretty orthogonal from async-await.

Therefore, presuming that we want to keep our current desugaring, I think that we should probably consider this as non-blocking -- but it's definitely something to add to the list of "surprises that may trip up regular users".

[nikomatsakis]

It's actually sort of mysterious to me that this example builds at all. For example, in trying to convert this recursive async fn to something that builds:

#![feature(async_await)]

async fn foo(n: usize) {
    if n > 0 {
        Box::new(foo(n - 1)).await;
    }
}

fn is_send<T: Send>(t: T) { drop(t); }

fn main() {
    is_send(foo());
}

The only thing I could find which works is to use a Box<dyn Future> return type:

#![feature(async_await)]

use std::future::Future;
use std::pin::Pin;

fn foo(n: usize) -> Pin<Box<dyn Future<Output = ()> + Send>> {
    Box::pin(async move {
        if n > 0 {
            foo(n - 1).await;
        }
    })
}

fn is_send<T: Send>(t: T) { drop(t); }

fn main() {
    is_send(foo(22));
}

Any other setup (including, say, this one that uses Box::pin) all fail because the future we are awaiting (foo) winds up as part of the type of foo.

This is a consequence, as far as I can tell, of our desugaring to generators, which in turn is currently modeled after our approach to closures, and closures cannot capture themselves. This is needed to make "upvar inference" manageable. It occurs to me, though, that this restriction is not needed for move closures, which do not need to do upvar inference -- the same presumably applies to async move blocks. It'd be a bit of a complex refactoring, but we could restructure their types to lift the restriction.

[nikomatsakis]

I guess that the reason the original example sidesteps these problems is because foo never awaits the return type of bar(), so it never appears in the generator type.

[cramertj]

@nikomatsakis Right-- the point here is that there shouldn't be a cycle at all, because the value that appears inside the generator is not the future type itself, but the type Pin<Box<dyn Future<...> + Send>>.

[nikomatsakis]

Discussed in meeting today. Filed #62539 to try and improve diagnostics for the naive case. I am marking as "unclear" because it might be good enough for stabilization purposes to document the correct workarounds (rust-lang/async-book#22) and improve error messages (#62539).