Missing `Send` on "recursive" `Future`

[CheaterCodes]

Yesterday in the rust community discord, we came across the following (minimized) example.
I don't understand why these futures aren't Send. Obviously, bar can only be Send if foo is as well. However, while bar requires foo to be Send in order to successfully type-check, it's Sendness shouldn't depend on it.

I tried this code:

fn spawn<T: Send>(_: T) { }

async fn foo() {
    spawn(bar())
}

async fn bar() {
    foo().await;
}

I expected to see this happen: I believe the code should compile.

Instead, this happened:

error: future cannot be sent between threads safely
 --> <source>:4:5
  |
4 |     spawn(bar())
  |     ^^^^^^^^^^^^ future returned by `bar` is not `Send`
  |
  = note: cannot satisfy `impl Future<Output = ()>: Send`
note: future is not `Send` as it awaits another future which is not `Send`
 --> <source>:8:5
  |
8 |     foo().await;
  |     ^^^^^ await occurs here on type `impl Future<Output = ()>`, which is not `Send`
note: required by a bound in `spawn`
 --> <source>:1:13
  |
1 | fn spawn<T: Send>(_: T) { }
  |             ^^^^ required by this bound in `spawn`

Meta

rustc --version --verbose:

rustc 1.85.0-nightly (4363f9b6f 2025-01-02)
binary: rustc
commit-hash: 4363f9b6f6d3656d94adbcabba6348a485ef9a56
commit-date: 2025-01-02
host: x86_64-unknown-linux-gnu
release: 1.85.0-nightly
LLVM version: 19.1.6

This also happens on stable rustc 1.83.0.
Before rustc 1.75 the type checker encounters a cycle instead.
With -Znext-solver there's an ICE.

[theemathas]

A few variations:

fn spawn<T: Send>(_: T) { }

fn foo() -> impl std::future::Future<Output = ()> {
    spawn(async { foo().await; });
    async {}
}

Error output

error: future cannot be sent between threads safely
 --> src/lib.rs:4:5
  |
4 |     spawn(async { foo().await; });
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ future created by async block is not `Send`
  |
  = note: cannot satisfy `impl Future<Output = ()>: Send`
note: future is not `Send` as it awaits another future which is not `Send`
 --> src/lib.rs:4:19
  |
4 |     spawn(async { foo().await; });
  |                   ^^^^^ await occurs here on type `impl Future<Output = ()>`, which is not `Send`
note: required by a bound in `spawn`
 --> src/lib.rs:1:13
  |
1 | fn spawn<T: Send>(_: T) { }
  |             ^^^^ required by this bound in `spawn`

fn spawn<T: Send>(_: T) { }

fn foo() -> impl std::future::Future<Output = ()> {
    spawn(async { let _x = foo(); async {}.await; });
    async {}
}

Error output

error: future cannot be sent between threads safely
 --> src/lib.rs:4:5
  |
4 |     spawn(async { let _x = foo(); async {}.await; });
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ future created by async block is not `Send`
  |
  = note: cannot satisfy `impl Future<Output = ()>: Send`
note: future is not `Send` as this value is used across an await
 --> src/lib.rs:4:44
  |
4 |     spawn(async { let _x = foo(); async {}.await; });
  |                       --                   ^^^^^ await occurs here, with `_x` maybe used later
  |                       |
  |                       has type `impl Future<Output = ()>` which is not `Send`
note: required by a bound in `spawn`
 --> src/lib.rs:1:13
  |
1 | fn spawn<T: Send>(_: T) { }
  |             ^^^^ required by this bound in `spawn`

fn spawn<T: Send>(_: T) { }

fn foo() -> impl std::future::Future<Output = ()> {
    spawn(foo());
    async {}
}

Error output

error[E0283]: type annotations needed: cannot satisfy `impl Future<Output = ()>: Send`
 --> src/lib.rs:4:5
  |
4 |     spawn(foo());
  |     ^^^^^^^^^^^^
  |
  = note: cannot satisfy `impl Future<Output = ()>: Send`
note: required by a bound in `spawn`
 --> src/lib.rs:1:13
  |
1 | fn spawn<T: Send>(_: T) { }
  |             ^^^^ required by this bound in `spawn`

For more information about this error, try `rustc --explain E0283`.

[theemathas]

A version that doesn't use async-await:

trait Trait {}
impl Trait for i32 {}

fn require_send(_: impl Send) {}

fn foo() -> impl Trait {
    require_send(foo());
    123
}

Error output

error[E0283]: type annotations needed: cannot satisfy `impl Trait: Send`
 --> src/lib.rs:7:5
  |
7 |     require_send(foo());
  |     ^^^^^^^^^^^^^^^^^^^
  |
  = note: cannot satisfy `impl Trait: Send`
note: required by a bound in `require_send`
 --> src/lib.rs:4:25
  |
4 | fn require_send(_: impl Send) {}
  |                         ^^^^ required by this bound in `require_send`

For more information about this error, try `rustc --explain E0283`.

[theemathas]

Oddly enough, I could cause the same issue with a const block, but not with a const item.

const fn require_send(_: impl Send + Copy) {}

const fn foo() -> impl Copy {
    const { require_send(foo()); }
    123
}

Error output

error[E0283]: type annotations needed: cannot satisfy `impl Copy: Send`
 --> src/lib.rs:4:13
  |
4 |     const { require_send(foo()); }
  |             ^^^^^^^^^^^^^^^^^^^
  |
  = note: cannot satisfy `impl Copy: Send`
note: required by a bound in `require_send`
 --> src/lib.rs:1:31
  |
1 | const fn require_send(_: impl Send + Copy) {}
  |                               ^^^^ required by this bound in `require_send`

For more information about this error, try `rustc --explain E0283`.

[rnotlnglgq]

Temporarily I'm avoiding the async keyword to add the required Send bound. There's also an async-recursion crate for stay with async.