async fn cannot be recursive

[upsuper]

With the current design of async functions, it doesn't seem to be able to call them recursively.

The most straightforward way:

async fn foo() -> u32 {
    await!(foo()) + 1
}

fails apparently, because the size of the future type is indefinite, and thus the compiler complains:

error[E0275]: overflow evaluating the requirement `impl std::future::Future`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate

Another idea would be to put the recursive future into another heap-allocated object:

async fn foo() -> u32 {
    let x = Box::new(foo());
    await!(x) + 1
}

However this doesn't work either, because resolving the return type of foo requires the return type of foo, which forms a cycle dependency, and compiler complains:

error[E0391]: cycle detected when processing `foo`
 --> src/main.rs:7:1
  |
7 | async fn foo() -> u32 {
  | ^^^^^^^^^^^^^^^^^^^^^
  |
note: ...which requires evaluating trait selection obligation `std::boxed::Box<impl std::future::Future>: std::future::Future`...
note: ...which requires processing `foo::{{impl-Trait}}`...

If the type is a problem, maybe we can use trait object?

async fn foo() -> u32 {
    let x: Box<dyn Future<Output = u32>> = Box::new(foo());
    await!(x) + 1
}

But it still doesn't work, because Future isn't object-safe due to the poll method, which is correctly reported by the compiler:

error[E0038]: the trait `std::future::Future` cannot be made into an object
  --> src/main.rs:10:12
   |
10 |     let x: Box<dyn Future<Output = u32>> = Box::new(foo());
   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `std::future::Future` cannot be made into an object
   |
   = note: method `poll` has a non-standard `self` type

So it seems that there is no way an async function can be called recursively.

I'm not sure how much problematic it would be, but it seems this limitation wasn't mentioned in the RFC nor any introduction of async, so maybe it's worth considering.

Recursion without additional allocation may be very challenging, but we should probably allow opt-in async recursion with some explicit cost.

[eddyb]

cc @cramertj @withoutboats (I'm not sure how easy the second example would be to fix)

[eddyb]

Wait, why are you using PinMut there? Doesn't await! include it?
If you remove it you get a cycle because of Box<impl Future>: Future, which IMO shouldn't cycle, are there extra bounds on the Box impl (is there even a box impl)?

[withoutboats]

Definitely the trait object form will be fixed someday. I don't know if we can ever make a non-dynamic call with a heap allocation work. Recursion without heap allocating the new stack frame doesn't work at all as far as I know (unless its tail call recursion 😱).

[upsuper]

I wasn't aware that await! includes PinMut, but it doesn't matter anyway. If you do

async fn foo() -> u32 {
    let x = Box::new(foo());
    await!(x) + 1
}

you get exactly the same error.

[eddyb]

@upsuper You get a different error, involving Box<impl Future>: Future.

The error you were getting before was about Box<impl Future>: Unpin.
Unpin is an auto trait, so it "leaks out" of -> impl Future and therefore can cause more cycles.

[upsuper]

Ah, okay, I didn't notice that... Thanks for pointing that out.

[cramertj]

yeah, we can't ever allow non-tail recursion in async fn without intermediate heap allocations because the stack isn't "real"-- it has to be statically-sized.

[Arnavion]

Changing it to a version that doesn't actually recurse indefinitely:

async fn foo(x: bool) -> u32 {
    if x {
        await!(foo(false)) + 1
    }
    else {
        4
    }
}

doesn't compile for the same reason.

---

Using FutureObj of PinBox of F to erase the type:

async fn foo(x: bool) -> u32 {
    if x {
        let f: std::future::FutureObj<u32> = std::future::FutureObj::new(std::pin::PinBox::new(foo(false)));
        await!(f) + 1
    }
    else {
        4
    }
}

fails with

error[E0391]: cycle detected when processing `foo`
 --> src/lib.rs:3:1
  |
3 | async fn foo(x: bool) -> u32 {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
note: ...which requires evaluating trait selection obligation `std::pin::PinBox<impl std::future::Future>: std::marker::Send`...
note: ...which requires processing `foo::{{impl-Trait}}`...
 --> src/lib.rs:3:26
  |
3 | async fn foo(x: bool) -> u32 {
  |                          ^^^
  = note: ...which again requires processing `foo`, completing the cycle
note: cycle used when processing `foo::{{closure}}`
 --> src/lib.rs:3:30
  |
3 |   async fn foo(x: bool) -> u32 {
  |  ______________________________^
4 | |     if x {
5 | |         let f: std::future::FutureObj<u32> = std::future::FutureObj::new(std::pin::PinBox::new(foo(false)));
6 | |         await!(f) + 1
... |
10| |     }
11| | }
  | |_^

---

Changing the async fn to an async block still doesn't compile:

fn foo(x: bool) -> impl std::future::Future<Output = u32> {
    async move {
        if x {
            let f: std::future::FutureObj<u32> = std::future::FutureObj::new(std::pin::PinBox::new(foo(false)));
            await!(f) + 1
        }
        else {
            4
        }
    }
}

with the same error about evaluating the Send bound.

---

Adding the Send bound on the return type explicitly finally makes it compile:

fn foo(x: bool) -> impl std::future::Future<Output = u32> + Send {
    async move {
        if x {
            let f: std::future::FutureObj<u32> = std::future::FutureObj::new(std::pin::PinBox::new(foo(false)));
            await!(f) + 1
        }
        else {
            4
        }
    }
}

[SimonSapin]

I think the error[E0391]: cycle detected when processing `foo` error occurs when the type definition of the generator is infinite (even if its size in memory is finite).

However, in this case:

use futures::future::FutureObj;

async fn foo(x: bool) -> u32 {
    if x {
        let f = FutureObj::new(Box::new(foo(false)));
        await!(f) + 1
    }
    else {
        4
    }
}

I would expect FutureObj (as a substitute for Box<dyn Future> until that is made to work) to provide type erasure: by the time we get to the await/yield point, the inner future/generator returned by the recursive call has been moved is not on the stack anymore.

However, that is fixed if we move the recursive call to a separate (non async) function. This compiles:

 
 async fn foo(x: bool) -> u32 {
     if x {
-        let f = FutureObj::new(Box::new(foo(false)));
+        fn out_of_line() -> FutureObj<'static, u32> {
+            FutureObj::new(Box::new(foo(false)))
+        }
+        let f = out_of_line();
         await!(f) + 1
     }
     else {

This seems to indicate that there is a bug (or missing optimization, in some points of view) in the implementation of generators. It looks like their memory layout keeps a "slot" for all intermediate expressions, not just those that need to be preserved across await/yield points. In the failing example, the generator for foo would include a slot for the return value of foo(false), whose type is that same generator itself, making a recursive type.

Can anyone familiar with the implementation confirm?

[eddyb]

cc @Zoxc

[Zoxc]

This is a limitation of the current impl Trait implementation, though there might be more going on. Here is a simple example:

fn test() -> impl Sync {
    test()
}

[SimonSapin]

@Zoxc I think your example is “the anonymous concrete type returned by test is itself”, which is similar to #53690 (comment) which is “the anonymous concrete type returned by foo contains (box of) itself”. In both cases, in order to tell whether T: Sync (respectively Send) we need to know whether T: Sync.

However in #53690 (comment), because of type ereasure, I would expect the concrete generator type not to contain (a box of) itself, because that intermediate expression is been moved (into FutureObj) by the type we get to a yield point. But it seems that it does. Why is that?

[Zoxc]

This is an example of what happens in #53690 (comment) with impl Trait:

trait Trait {}

fn share<T: Send>(t: &T) {}

fn foo() -> impl Trait {
    let a = foo();
    share(&a);
}

In your example, when type checking the body of foo, you use the result of the foo call to create a FutureObj which require Send, so the compiler needs to know the return type of the foo in order to check this. However in order to find this type, we need to type check the body of foo, which we are already doing, so we get a cycle error.

Anyway this is all working as "intended" and there isn't really a bug here.