Tokio Recursion Error

I just googled "rust async await recursion" and the first result it showed me was the Recursion chapter from The Async Book and they propose the same workaround:

In order to allow this, we have to introduce an indirection using Box . Unfortunately, compiler limitations mean that just wrapping the calls to recursive() in Box::pin isn't enough. To make this work, we have to make recursive into a non- async function which returns a .boxed() async block:

use futures::future::{BoxFuture, FutureExt};

fn recursive() -> BoxFuture<'static, ()> {
    async move {
        recursive().await;
        recursive().await;
    }.boxed()
}

You mean something like the following code:

enum FutureResult {
    HandleUrl2,
    HandleUrl,
}

fn do_some_stuff(url: &str) -> FutureResult {
    return FutureResult::HandleUrl2;
}

fn handle_url(url: &str) -> FutureResult {
    do_some_stuff(url);
    if url == "Some url" {
        return FutureResult::HandleUrl;
    }
    let child_url = "Some url";
    return handle_url(child_url);
}

But I do not see any issues with such approach !?

Right, the async keyword is just syntactic sugar that turns the call into an impl Future

The example you've shown isn't correct. Each async function is compiled into its own type.

// This function:
async fn foo() {
    step_one().await;
    step_two().await;
}
// generates a type like this:
enum Foo {
    First(StepOne),
    Second(StepTwo),
}

// So this function:
async fn recursive() {
    recursive().await;
    recursive().await;
}

// generates a type like this:
enum Recursive {
    First(Recursive),
    Second(Recursive),
}

(quoting the first section in the Async Book's Recursion chapter)

No it does not work (:

It's not only boxing the future, it must be pinned too... I've corrected my example in post #14.

BoxFuture works, but what if I need the following:

async fn recursive() -> BoxFuture<'static, ()> {
   // Await on some other function
    async move {
        recursive().await;
        recursive().await;
    }.boxed()
}

Then it does not work !!

you shouldn't add the async keyword to the function, doing that makes the future return a future.
BoxFuture is a future on it's own, and it can be awaited.

1 Like

To expand on @naim's comment:

use futures::future::{BoxFuture, FutureExt};

fn recursive() -> BoxFuture<'static, ()> {
    async move {
        recursive().await;
        recursive().await;
    }
    .boxed()
}

(playground)

Put all of your awaits into the async block.

fn recursive() -> BoxFuture<'static, ()> {
    async move {
        // Await on some other function

        recursive().await;
        recursive().await;
    }.boxed()
}

But it is possible to handle with generating the following enum:

async step_one() -> u8 {
    1u8
}

async step_third() -> u32 {
    1u32
}

// So this function:
async fn recursive() {
    step_one().await;
    recursive().await;
    step_third().await;
    recursive().await;
}

// generates types like this:
enum RecursiveHelper {
    First(u8),
    Third(u32),
}

enum Recursive {
    First(u8),
    SecondSelfCall(RecursiveHelper),
    Third(u32),
    FourthSelfCall(RecursiveHelper),
}

I've just broken recursion and all should work !!
And I do not get why it is not implemented in such way ?
Is there any other technical issues ?

I can't see how it's true that your example async function should desugar to those two enums; Every call to recursive needs the full state. Which is recursive by definition. Break the recursion with indirection, which is what has been shown several times already.

It is hard to make such indirection and it is not readable at all !!

Take a look at example that I show above ...
Why t is not implemented in this way ?

The enum presented isn't actually meant to be for the programmer to write, It's just to show you what the compiler may emit.

enum FuncStates {
    State1{ /* state data */ },
    State2{ /* state data */ },
    State3{ /* state data */ },
   /* etc... */
}

You need to create a type that the compiler won't try to add to the imaginary enum (because if it does, it would be adding the enum to itself - which is not allowed).

enum States {
   State1 {},
   State2 { x: States }, // <- not allowed, compiler won't be able to find the size. It's infinite...
    /* etc... */
}

It is possible to add indirection by adding an indirect type:

enum States {
    State1 {},
    State2 { x: Box<States> }, // this will compile, because a Box is a pointer.
}

Rust requires a Box for this to be possible, and tokio's executor's spawn function requires functions to be Pin & Send, this example complies with all these requirements:

I understood that it is not meant to be written by programmer !!
But I am asking why the indirection is not broken by generating proper enum as I show above ?

Because the states won't have a defined size. Every state would require it's previous states, that would require memory allocation.
Your previous example doesn't store previous states of calls to recursive, how would describe a recursive binary-tree search with an enum? I don't see how it's possible without either setting a limit (will utilize allot of unused memory), or dynamic allocation.

The documentation for std::boxed describes exactly why it cannot be done the way you wrote. Your structs are an incorrect formulation of the types.

The compiler won't automatically box the recursive call for you because it prefers to make things influencing performance (e.g. allocation) explicit. A key part of zero cost abstractions (which Rust's async-await tries to be) is making sure you don't pay for the things you don't need.

If it tried to help out in simple examples like this then you wouldn't have enough control when you really need it.

2 Likes

I have implemented my own macro function for generating wrapper for recursion call https://github.com/redradist/RustAsyncHelpers

fn recursive() -> BoxFuture<'static, u8> {
    async move {
        recursive().await;
        recursive().await;
        2u8
    }.boxed()
}

But after using my macro function it is possible to do following:

#[async_recursive]
async fn recursive() -> u8 {
    recursive().await;
    recursive().await;
    2u8
}

I hope if community will like this macro function, I could create pull-request to Rust libstd :wink:

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.