Async fn recursion (Rust 1.77)

help
1

Hey folks,

I was just reading the Release Notes for Rust 1.77. I find especially the part about recursion in async fn very interesting.

The article says that you require for async fn recursion some kind of indirection to avoid an infinite size for the state of the function.

My assumption is that this is the case because the compiler cannot tell at compile time how deep the recursion will go at runtime therefore it would have to build a state machine type with infinite states which would result in a state machine with infinite size to make sure that all possible cases are covered. On the other hand at the variant with the indirection with Box we get a state machine type with a finite number of states and therefore a state machine with finite size and every recursion step will result in an allocation at runtime (until we return or have no more memory) which would more or less "concatenate" multiple state machines of the same state machine type.

That said instead of trying to build something at compiletime to cover any possible cases we increase the size at runtime bit by bit depending on what acutally happens at runtime.

Is this interpretation correct?

Regards
keks

2

Yes, this sounds generally correct.

Another angle to look at this is by comparing to recursive data structures. Recursive, or mutually recursive structs/enums in Rust also require indirection to work, and indirection (e.g. in the form of Box and heap allocations) allows the overall size of the whole data structure to depend on runtime choices.

// error[E0072]: recursive types `FilledNode` and `Node` have infinite size

struct FilledNode {
    value: i32,
    next: Node,
}

enum Node {
    Filled(FilledNode),
    Empty,
}

// compiles fine (version 1)

struct FilledNode {
    value: i32,
    next: Node,
}

enum Node {
    Filled(Box<FilledNode>),
    Empty,
}

// compiles fine (version 2)

struct FilledNode {
    value: i32,
    next: Box<Node>,
}

enum Node {
    Filled(FilledNode),
    Empty,
}
1 Like
3

Thanks! :slight_smile: Yes, you're right that is indeed no problem which is specific for async fn/coroutines/generators. I didn't had that in mind while writing my initial post. Thank you also for pointing that out. :slight_smile:

4

Sorry, for bringing the topic back to the top, but there's still one thing that confuses me:

According to the PR for this new feature the technical basis has been introduced with Rust 1.69 (PR #101692) and with Rust 1.77 the limitation when checking for cycles has only been lifted.

The following example from the PR demonstrates what the feature can be used for:

async fn async_fibonacci(i: u32) -> u32 {
    if i == 0 || i == 1 {
        i
    } else {
        Box::pin(async_fibonacci(i - 1)).await 
          + Box::pin(async_fibonacci(i - 2)).await
    }
}

In earlier versions this was not possible without type erasure as you can also read in the PR.

My question is now why did the above-mentioned async fn result in a cyclic type in Rust <1.77 respectively <1.69? Shouldn't the indirection via Box also have prevented a cycle earlier even when the boxed coroutine was a field of it's "parent coroutine"?

Regards
keks

5

The cycle was in calculating other properties than size, like whether the returned future is Send or not. Call the return type of async_fibonacci() FibFut, and consider the reasoning the compiler must follow:

  • FibFut: Send if and only if its captures are Send:
    • The captured u32 is Send — OK!
    • The awaited Box<FibFut> is Send if its contents are Send:
      • Is FibFut: Send? Um, well, we were just trying to compute that…

This problem of course has a correct answer, but it's not one that will be reached unless the algorithm specifically supports this case, which it now does.

2 Likes
6

Ahhhh I see!!! :slight_smile: Thanks a lot. :+1:

7

Actually, I may have oversimplified when I said “The cycle was in calculating other properties than size” — it is also possible to have a cycle when computing size, because the size of Box<T> depends on whether T: Sized or not — if yes, it is one pointer, if no, it is one pointer plus metadata (slice length or dyn vtable pointer).

You can break that cycle by having the axiom that all async block futures are Sized, but again, that isn't something the compiler will intrinsically have available to it if nobody writes that knowledge in.

1 Like
8

Thanks for the addition! Makes sense. :slight_smile: This is indeed a cycle in terms of size but as far as I can tell still not in a way that could theoretically lead to an infinite size of the state machine (type), because that was, as you realized the wrong track which I was on. :wink:

9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.