error[E0391]: cycle detected when computing type of async fn

[Diggsey]

I tried this code:

use futures::future::FutureExt;

async fn foo() {
    FutureExt::boxed(async {
        foo().await;
    });
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=19653eea2af1dd97a8d48126dfd7d683

I expected it to compile, but it gave the following error:

error[E0391]: cycle detected when computing type of foo::{{opaque}}#0

edit:
With one minor change, it compiles:

async fn foo() {
    Box::new(async {
        foo().await;
    });
}

There are no rules that would explain why the first should fail when this succeeds.

[camelid]

A bit of a weird error message:

error[E0391]: cycle detected when computing type of `foo::{{opaque}}#0`
 --> src/main.rs:3:16
  |
3 | async fn foo() {
  |                ^
  |
note: ...which requires borrow-checking `foo`...
 --> src/main.rs:3:1
  |
3 | async fn foo() {
  | ^^^^^^^^^^^^^^
note: ...which requires processing `foo`...
 --> src/main.rs:3:1
  |
3 | async fn foo() {
  | ^^^^^^^^^^^^^^
note: ...which requires processing MIR for `foo`...
 --> src/main.rs:3:1
  |
3 | async fn foo() {
  | ^^^^^^^^^^^^^^
note: ...which requires unsafety-checking `foo`...
 --> src/main.rs:3:1
  |
3 | async fn foo() {
  | ^^^^^^^^^^^^^^
note: ...which requires building MIR for `foo`...
 --> src/main.rs:3:1
  |
3 | async fn foo() {
  | ^^^^^^^^^^^^^^
note: ...which requires type-checking `foo`...
 --> src/main.rs:3:1
  |
3 | async fn foo() {
  | ^^^^^^^^^^^^^^
  = note: ...which requires evaluating trait selection obligation `{std::future::ResumeTy, impl futures::Future, ()}: std::marker::Send`...
  = note: ...which again requires computing type of `foo::{{opaque}}#0`, completing the cycle
note: cycle used when checking item types in top-level module
 --> src/main.rs:1:1
  |
1 | / use futures::future::FutureExt;
2 | |
3 | | async fn foo() {
4 | |     FutureExt::boxed(async {
... |
8 | |
9 | | fn main() {}
  | |____________^

error: aborting due to previous error

[jyn514]

I think this is expected behavior? You can't have recursive async functions: https://www.reddit.com/r/rust/comments/cbdxxm/why_are_recursive_async_fns_forbidden/

[jyn514]

The error message is pretty bad, though.

[Diggsey]

@jyn514 this is not a recursive function.

[Diggsey]

For reference, the following very similar code snippet compiles just fine, and should be equivalent (modulo a Pin and some marker traits):

async fn foo() {
    Box::new(async {
        foo().await;
    });
}

[tmandry]

Discussed during the wg-async-foundations meeting.

It seems the difference in the examples could be coming from the signature of FutureExt::Boxed...

fn boxed<'a>(self) -> Pin<Box<dyn Future<Output = Self::Output> + 'a + Send>>

...demanding Self::Output, the return type of the async block, but that's clearly just (). EDIT: Maybe it's trying to make sure the async block body is well-formed before inferring its return type? That would explain why we're checking that the return type of foo is Send.

More spelunking will be needed to figure out where exactly the cycle is coming from and how hard it will be to avoid.

[spastorino]

I don't think is important to prioritize this one given that the async wg is already on it.

[noonien]

Any update on this?

[danielhenrymantilla]

Posting it here for the sake of visibility: in #87850 I've showcased a minimal repro of actually the issue here: featuring an auto-trait constraint on an existential type triggers this error (at least at the definition site of the existential; haven't checked beyond that).

[eholk]

I'm going to spend some time looking at this over the next async team sprint.

@rustbot claim

[eholk]

I'm finally getting around to looking at this today. Here's a standalone test case:

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

fn boxed<'a, F, T>(x: F) -> Pin<Box<dyn Future<Output = T> + Send + 'a>>
where
    F: Future<Output = T> + Sized + Send + 'a,
{
    Box::pin(x)
}

async fn foo() {
    boxed(async {
        foo().await;
    });
}

fn main() {
    let _ = foo();
}

The query stack when cycle comes up is:

#0 [evaluate_obligation] evaluating trait selection obligation `{core::future::ResumeTy, impl core::future::future::Future<Output = ()>, ()}: core::marker::Send`
#1 [typeck] type-checking `foo`
#2 [mir_built] building MIR for `foo`
#3 [unsafety_check_result] unsafety-checking `foo`
#4 [mir_const] processing MIR for `foo`
#5 [mir_promoted] processing `foo`
#6 [mir_borrowck] borrow-checking `foo`
#7 [type_of] computing type of `foo::{opaque#0}`
#8 [check_mod_item_types] checking item types in top-level module
#9 [analysis] running analysis passes on this crate

If I remove the + Send bound, then the code works, so the issue seems to be around checking auto traits, which makes sense given query #0.

I'm a little surprised to see that borrow checking is needed to find the type of foo::{opaque#0}, which I assume is the inner async { foo().await } block. Is there a way to say "assume borrow checking passes and check for real later?

[danielhenrymantilla]

I guess you'd like a impls_trait_modulo_regions, kind of like with copy_modulo_regions? Because you do need some lifetime-tracking (which I guess is done by borrow-checking?) to be able to know whether a trait is implemented.

• Demo

• _{^{For context, the copy_modulo_regions hacks do lead to unsoundness, since they act similar to Copy-specialization (since the whole specialization is kind of modulo-regions to begin with), so I'd advise caution when dealing with these things.}}

---

In this instance, however, maybe an approach would be for the query that checks whether an existential implements an auto-trait to temporarily "cache the 'does it impl the auto-trait'" query with a positive answer?

As in:

1. Let's see if that boxed() call typechecks:

2. Is async { foo().await } (i.e, foo::{opaque#0}) : Send?
   Auto-trait query involving an existential type, let's cache that it does, within the following scope:

3. Check the generator state / captures (since foo::{opaque#0} is : Send if they are):

   1. foo() is captured. Is it : Send?
      Let's typecheck its body [is that how it works?]:
      Given boxed(…), is that : Send?

      1. Let's typecheck the arg given to boxed(…) to know of F [is that how it works?]:

         1. Is its arg, async { foo().await }, i.e., foo::{opaque::#0} : Send?
            Cache-result says so.

      2. Okay, boxed::<foo::{opaque::#0}>() is Pin<Box<dyn Send …>>, so it is Send

   2. No other captures

   So foo::{opaque::#0} can indeed be : Send.

4. Result is okay, keep cache result.

I know it's pretty wave-handed, so I apologize if that's not how this compiler stuff works: the way I've understood it (which may be wrong!), is that currently the i.a.a step detects recursion and bails, and my idea may be able to tackle that?

For completeness regarding that algorithm, if 3.ii had featured another capture which were known not to be Send, then even if boxed() were, foo::{opaque#0} wouldn't, which would invalidate the cached query, and be able to blame that other capture.

• And what I mentioned regarding borrowck being necessary, is that 3.i.a type-checking stage does need to know of the actual lifetimes involved, to know which trait bounds are met, hence maybe why borrowck is involved?

[eholk]

Thanks for the suggestions, @danielhenrymantilla!

After thinking about this some more, I think this is going to take some much more significant changes that I'm ready to make right now. I'm going to shelve this issue for now.

[piegamesde]

This issue is preventing ergonomic recursive async functions. At the moment, one would have to write (writing from memory here, but you get the idea):

fn foo() -> BoxFuture<()> {
  Box::pin(async move {
    foo().await
  }) as BoxFuture<()>
}

with this issue resolved, one could move the boxing down to only recursive calls:

async fn foo() {
  (Box::pin(foo()) as BoxFuture<()>).await
}

This is not only more ergonomic, but also it is truly zero cost, while the current workaround is not (you always pay for the dynamic dispatch even when you don't recurse).

---

I found a workaround that is zero cost:

async fn foo() {
  #[inline(always)]
  fn foo_recurse() -> futures::future::BoxFuture<()> {
    Box::pin(foo())
  }
  foo_recurse().await
}

I find it really interesting that this works, but manually inlining the function triggers the bug.