New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

async fn cannot be recursive #53690

Closed
upsuper opened this Issue Aug 25, 2018 · 20 comments

Comments

Projects
None yet
8 participants
@upsuper
Copy link
Contributor

upsuper commented Aug 25, 2018

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

This comment has been minimized.

Copy link
Member

eddyb commented Aug 25, 2018

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

@eddyb

This comment has been minimized.

Copy link
Member

eddyb commented Aug 25, 2018

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

This comment has been minimized.

Copy link
Contributor

withoutboats commented Aug 25, 2018

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

This comment has been minimized.

Copy link
Contributor Author

upsuper commented Aug 25, 2018

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

This comment has been minimized.

Copy link
Member

eddyb commented Aug 25, 2018

@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

This comment has been minimized.

Copy link
Contributor Author

upsuper commented Aug 25, 2018

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

@cramertj

This comment has been minimized.

Copy link
Member

cramertj commented Aug 27, 2018

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

This comment has been minimized.

Copy link

Arnavion commented Sep 5, 2018

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

This comment has been minimized.

Copy link
Contributor

SimonSapin commented Dec 6, 2018

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

This comment has been minimized.

Copy link
Member

eddyb commented Dec 6, 2018

cc @Zoxc

@Zoxc

This comment has been minimized.

Copy link
Contributor

Zoxc commented Dec 6, 2018

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

This comment has been minimized.

Copy link
Contributor

SimonSapin commented Dec 6, 2018

@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 comment has been minimized.

Copy link
Contributor

Zoxc commented Dec 6, 2018

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.

@SimonSapin

This comment has been minimized.

Copy link
Contributor

SimonSapin commented Dec 6, 2018

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

@Zoxc Zoxc removed the A-generators label Dec 6, 2018

@eddyb

This comment has been minimized.

Copy link
Member

eddyb commented Dec 6, 2018

@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

This comment has been minimized.

Copy link

ebkalderon commented Jan 27, 2019

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 comment has been minimized.

Copy link
Contributor

withoutboats commented Jan 28, 2019

This is indeed because you are calling build_dependencies recursively.

@Arnavion

This comment has been minimized.

Copy link

Arnavion commented Jan 28, 2019

@ebkalderon Just like in #53690 (comment) 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

This comment has been minimized.

Copy link

ebkalderon commented Jan 28, 2019

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

@cramertj

This comment has been minimized.

Copy link
Member

cramertj commented Jan 28, 2019

Closing, as this is working as-intended.

@cramertj cramertj closed this Jan 28, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment