Boxed recursive function should not require trait object

[jimblandy]

The following code works (playground):

use std::future::Future;
use std::pin::Pin;

async fn recurse(i: usize) {
    if i == 0 {
        println!("Zero!");
        return;
    }
    
    println!("entering {}", i);
    let recursed = Box::pin(recurse(i-1)) as Pin<Box<dyn Future<Output=()>>>;
    recursed.await;
    println!("exiting {}", i);
}

fn main() {
    futures::executor::block_on(recurse(10));
}

but if the trait object is removed, and the construction of recursed is changed to:

    let recursed = Box::pin(recurse(i-1));

then Rust rejects the program:

error[E0733]: recursion in an `async fn` requires boxing
 --> src/main.rs:4:28
  |
4 | async fn recurse(i: usize) {
  |                            ^ recursive `async fn`
  |
  = note: a recursive `async fn` must be rewritten to return a boxed `dyn Future`

The future is boxed either way, so the use of a trait object shouldn't be required. In a thread on the internals forum, @withoutboats said:

Note that it should be allowed to just use Box::pin, without casting it into a trait object at all, and the fact that it isn't is an implementation limitation of how current rustc calculates the layout of the future type. It doesn't look like there's a bug tracking this limitation though.

Now there is!

[jonas-schievink]

This is tracked by #69663.

[withoutboats]

@jonas-schievink This seems distinct from that issue, which has to do (I think) with liveness analysis. This is rather separate: the object's liveness is computed properly, the problem is that we do not allow the future to be a recursively defined type without erasure.

The future in the example should be the moral equivalent of an enum with Box<Self> in one of its variants, but the compiler won't generate that. Instead it has to have Box<dyn Future> in the field.

[jonas-schievink]

Ah, yeah, I think you're right. This error is emitted by the code that checks for cycles in opaque impl Trait types.

[gzp79]

I faced the same issue and the error is a bit miss-leading. I had two types calling each other with distinct instances.
When I first met it I've started to refactor, move codes around, split function created new instances/clones to call async function on new instances as I was thinking it is some lifetime thing.
So I'd rephrase the error message to refer to the type as the root cause is an "infinite" sized type.

[traviscross]

@rustbot labels +I-types-nominated +T-types

@rust-lang/wg-async discussed this issue and felt it was desirable to support if feasible. However, the hard questions here relate to the type system, so we are nominating this for T-types for its thoughts and tracking.

[lcnr]

This can be supported by removing the https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/util/struct.OpaqueTypeExpander.html#method.expand_coroutine check. However, any PR should also add necessary tests and make sure that directly recursive coroutines have good error messages.

some discussions in https://rust-lang.zulipchat.com/#narrow/stream/326866-t-types.2Fnominated/topic/.2373625.3A.20Boxed.20recursive.20function.20should.20not.20require.20trait.20o.E2.80.A6 and https://rust-lang.zulipchat.com/#narrow/stream/326132-t-types.2Fmeetings/topic/2023-11-06.20planning.20meeting/near/400556344

[lcnr]

this has been implemented in #117703. Closing