Hmm. What would Yato's second example look like with manually boxed futures? I don't know how to write that myself, but based on experience with manual futures in JavaScript I'm worried that the actual logic will get lost in the mechanics, even for something very simple like that.
You asked to implement my solution, it is done, take a look:
It is done without any overhead and without boxing
As written it goes into an infinite loop in RecursiveHelper.
Okay, I got your point !! What if we do something like this:
Just extend Future trait little-bit ... 
Then in custom code library such as tokio or other could do something like this:
#[tokio::recursive]
async fn recursive() {
recursive().await;
recursive().await;
}
And library will use Future that implement recursion ...
Also I have created the same implementation, but with different name RecursiveFuture:
Is it possible to write such macros that will generate from:
#[tokio::recursive]
async fn recursive() {
recursive().await;
recursive().await;
}
the following code:
#[tokio::recursive]
fn recursive() -> BoxFuture<'static, ()> {
async move {
recursive().await;
recursive().await;
}.boxed()
}
Note that no Rust language feature implicitly allocates at the moment, so this would be a significant change.
"You must have an allocator if you call and await this function at this point" also seems like a fairly odd consequence to impose on users, especially because it can happen non-locally at any arbitrary point you create a cycle in the control flow graph.
I don't really understand the problems with manually boxing, since the compiler even tells you to do it when this happens. Does this cause issues for anyone here?
20 Likes
Well, like I said upthread, my concern is with readability. What does a moderately complex recursive async function look like with manual boxing where necessary? Can you point me at some examples?
I'd be interested in the same data. I don't have any examples myself since I haven't used async/await so far.
There's some recursion in the logic in tokio-postgres to load information about custom types. It didn't really seem like that big of a deal to just make a wrapper function that returned a boxed future and call that when necessary to break cycles: https://github.com/sfackler/rust-postgres/blob/master/tokio-postgres/src/prepare.rs#L106-L112.
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 
1 Like
I think it would be better just to use box / Box::new explicitly inside recursive. Otherwise the outer-most call gets boxed unnecessarily.
5 Likes
Why it is better ? It is my contract as programmer who wrote this function that it returns BoxFuture ...
It is very explicitly when I wrote #[async_recursive] !!
Even though there's no magic solution, the fact remains that recursive async functions are cumbersome, and the compiler is not helpful about them.
Currently the compiler just points to function's return type, and leaves it to the user to guess what the right solution is. The rewritten form is kinda annoying to write.
So I would really like to see some solution to this. For example, if std had a macro for #[boxed_async] transformation, then the compiler could recommend it automatically. It would downgrade the problem from tricky situation with boilerplate solution to a 1-line autofix.
4 Likes
Compiler could make error more readable, something like:
It is not possible to make recursive call without level of indirection !!
Please, use boxed_async macro or run async function in sheduler
that is supports impl RecursiveFuture
Have you seen my message above ?
I've already implemented custom macros #[async_recursive] and today at the morning already renamed it to #[boxed_async_recursion] ))
Because the outer-most call gets boxed unnecessarily. recursive doesn't need to return a boxed future, it's only the recursive calls to recursive inside recursive that need to be boxed. Using box explicitly where you want to break the cycles in the control flow graph is more efficient. #[boxed_async_recursion] can't do this if the recursion happens across multiple functions.
Admittedly this is a micro-optimization so maybe something like #[boxed_async_recursion] would still make sense to have in the standard library. I think better error messages that suggest where to put box would be preferable though.
1 Like
What do you mean ?
Something like this:
#[boxed_async_recursion]
async fn another_recursive(k: u8, l: u32) -> u8 {
recursive(k, l).await;
another_recursive(k, l).await;
2u8
}
#[boxed_async_recursion]
async fn recursive(k: u8, l: u32) -> u8 {
another_recursive(k, l).await;
recursive(k, l).await;
2u8
}
It compiles !!
@canndrew Could you explain what do you mean by recursion from another function ?
@RustyYato Also seems like it is possible to use alloca-like function to implement recursive async/.await functions:
pub trait RecursiveFuture {
/// The type of value produced on completion.
type Output;
fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
fn create_self<'a>(self) -> Pin<&'a mut Self> where Self: Sized {
unimplemented!("Using alloca-like from C library by default !!");
}
fn dispose_self<'b>(self: Pin<&'b mut Self>) where Self: Sized {
unimplemented!("Dispose object created by alloca-like with dealloca function !!");
}
}
You can't use stack space to store the future, this includes alloca. But this doesn't contradict anything that I said, because you still have indirection, just now it's through a reference instead of a box
1 Like
async functions by itself indirection !!
But with alloca we will have Zero-Cost Abstraction !!
I mean what you wrote - with recursive and another_recursive calling each other recursively - but what I'm saying is that there's no way to do this with a macro without doing unnecessary boxing.
Consider these two functions:
async fn not_recursive(x: u8) -> u8 {
x
}
#[boxed_async_recursion]
async fn also_not_recursive(x: u8) -> u8 {
x
}
Calling not_recursive is zero-cost but calling also_not_recursive isn't since it allocates on the heap. So #[boxed_async_recursion] is adding unnecessary cost.
This is also true if you have a function which is actually recursive since only the recursive calls to the function need to be boxed but #[boxed_async_recursion] will box the initial call to the function as well. You could try to modify the macro to be smarter about this by moving the call to .boxed() inside to where the recursion happens instead of wrapping the entire function body in .boxed(). But this won't work if you have mutually-recursive functions (or even otherwise, since macros only operate on syntax and can't necessarily see all the recursion points).
Please, take a look at RecursiveFuture in Playground, it is possible to have Zero-Cost Abstraction even with recursive calls with alloca:
pub trait RecursiveFuture {
/// The type of value produced on completion.
type Output;
fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
fn create_self<'a>(self) -> Pin<&'a mut Self> where Self: Sized {
unimplemented!("Using alloca-like from C library by default !!");
}
fn dispose_self<'b>(self: Pin<&'b mut Self>) where Self: Sized {
unimplemented!("Dispose object created by alloca-like with dealloca function !!");
}
}
See Rust Playground