Rust: 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 :scream:).

[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 https://github.com/rust-lang/rust/issues/53690#issuecomment-415955382 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 https://github.com/rust-lang/rust/issues/53690#issuecomment-444801527, 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 https://github.com/rust-lang/rust/issues/53690#issuecomment-444801527 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.

[SimonSapin]

The out_of_line case does compile. I think it is a bug that manually inlining a function causes this error.

[eddyb]

@SimonSapin You're manually breaking a cyclic dependency, it makes sense that it would work.

The hard part is implementing the auto trait check without a cyclic dependency, and we can either:

• special-case the self-call case: we keep track of the inference variables we're using to compute the concrete type of impl Traits, so we can use that instead of requesting the type globally
  
  
  
  • doesn't do anything for mutually recursive functions
  
  
  • there's a risk here of getting some additional constraints from that, which can change the final inferred type, instead of being an error if it was checked separately (maybe we can alleviate this by deferring until after the "global" type is inferred, and checking outside of the original inference context, kind of like the second option, but still local)
  
  
• solve it generally (which was actually the first way I implemented checking auto traits, including tests with mutual recursive calls): we could keep a global set of "pending obligations", and check them after inference is done
  
  
  
  • doesn't play well at all with incremental, short of a new infrastructure for "side-outputs" and having a "gather" query for them
  
  

cc @nikomatsakis @michaelwoerister

[ebkalderon]

Not sure how related this is, but I ran into a case where an async fn couldn't compile due to a recursive data type (Playground). This code compiles and works fine if the method in question isn't async.

error[E0720]: opaque type expands to a recursive type
  --> src/main.rs:26:46
   |
26 |     pub async fn build_dependencies(self) -> DependenciesBuilt {
   |                                              ^^^^^^^^^^^^^^^^^ expands to self-referential type
   |
   = note: expanded type is `std::future::GenFuture<[static generator@src/main.rs:26:64: 37:6 {fn(std::ops::Range<i32>) -> <std::ops::Range<i32> as std::iter::IntoIterator>::IntoIter {<std::ops::Range<i32> as std::iter::IntoIterator>::into_iter}, i32, std::ops::Range<i32>, Builder, impl std::future::Future, (), DataLoaded, impl std::future::Future, DependenciesFetched, impl std::future::Future}]>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0720`.

[withoutboats]

This is indeed because you are calling build_dependencies recursively.

[Arnavion]

@ebkalderon Just like in https://github.com/rust-lang/rust/issues/53690#issuecomment-418911229 you can fix this by erasing the type of the recursive future.

let f: std::pin::Pin<Box<std::future::Future<Output = _>>> = Box::pin(fetched.build_dependencies());
let deps_built = await!(f);

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=db84fccf524660efce45a75299bd3fdd

[ebkalderon]

@Arnavion Thanks for the information! Wrapping the future in a Pin<Box<_>> seems to do the trick.

[cramertj]

Closing, as this is working as-intended.

[stuhood]

So, while it seems that this is working as intended (or at least "as it must"), the error message leaves much to be desired. Would be great to lift whatever friendly message is (I'd assume?) on infinitely sized structs over here.

[gilescope]

@stuhood - working on improving the error message: #62539 - feel free to make suggestions!