"computing type of ...::{opaque#0}" query cycle in `async fn` w/ auto trait obligations.

[inanna-malick]

I tried this code using GATs and the async feature

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=8856ef117840a1d3b4be93441c2b36b1

I expected it to compile. For reference, the same code implemented using manual .then future chaining compiles as shown here:

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=8cd834a4ff4d4b969d6ba1de9db91fee

Note that the above are built with nightly 1.67, but the same error occurs on stable 1.65.

Tagging @jackh726 as suggested by @jyn514

Note that GATs are an amazing feature that I'm incredibly grateful to you for implementing, and also that I'm not surprised that my extremely galaxy brained Haskell shenanigans hit some edge case.

---

EDIT(@eddyb): changed title as per #104343 (comment) - this does not seem to involve GATs at all, just the unfortunate interaction of async fn's -> impl Future desugaring + the "leaky" auto trait semantics of -> impl Trait.

[eddyb]

Note that this a cycle between type-checking and resolving an -> impl Trait, as made clear by:

error[E0391]: cycle detected when computing type of `expand_and_collapse_async::{opaque#0}`
...
   = note: ...which again requires computing type of `expand_and_collapse_async::{opaque#0}`, completing the cycle

(::{opaque#0} refers to the unnamed def for an -> impl Trait, in this case the implicit -> impl Future used by async fn)

Sadly the rest of the cycle is irrelevant and could ideally be cut out - part of the problem is computing type of is just the type_of query, it might be easier to do this if it was a separate query.

cc @oli-obk

[eddyb]

It's likely all the auto-trait bounds you have (Sync/Send), minimal example (playground:

fn require_sync<T: Sync>(_: T) {}

fn test() -> impl Copy {
    if false { require_sync(test()); }
    123
}

error[E0391]: cycle detected when computing type of `test::{opaque#0}`
note: ...which requires borrow-checking `test`...
...
note: ...which requires type-checking `test`...
  = note: ...which requires evaluating trait selection obligation `impl core::marker::Copy: core::marker::Sync`...
  = note: ...which again requires computing type of `test::{opaque#0}`, completing the cycle

[eddyb]

It is, in fact, Sync/Send, though I had to start reducing before noticing BoxFuture/FutureExt::boxed require Send, heh - in the end, was able to go all the way back to 1.43.0: https://godbolt.org/z/b6MjcqPd5

So this has nothing to do with GATs, it's just perhaps not the kind of code you'd write without GATs.

EDIT: conversely, removing auto trait bounds but keeping GATs makes the original example compile.
EDIT2: however, since the bounds are more important, you can desugar async fn to add the bound.

[jackh726]

Wow, thanks for the analysis here @eddyb!

This is a tough one. We essentially need to recognize coinductive cycles across queries. Or, we have to delay checking the bounds of require_sync(test()) until after we've identified the type of impl Copy. But then what about:

fn require_sync<T: Sync>(t: T) -> T { t }
fn test() -> impl Copy {
    require_sync(test())
}

(I don't this problem can compile, because we should never be able to figure out what T is; but the point I'm making is that there is no way we can delay checking bounds)

[jyn514]

@jackh726 it should be possible to delay checking bounds if they don't affect the return type of the function, right? First infer the return type as i32, then check the Send bound? I agree your code can't compile, but I think eddyb's MCVE should be possible in theory.

[eddyb]

I think one of my early implementations actually solved this problem, but in a way that I don't trust to be sound wrt queries (esp. incrementally) - all it did is really just defer such obligations as much as possible (into TyCtxt-global state AFAIK), and checked them only after forcing type_of for all -> impl Traits (so no more cycles can occur).

Maybe a sound way to do this would be to put the obligations in the result of typeck and then have something else that checks typeck(def_id).deferred_obligations for every def_id in the crate. At least that way it's "pull" not "push", and at most inefficient wrt incremental (I guess there should be a per-def_id query to at least avoid requesting typeck if its inputs haven't changed etc.).
But that's assuming MIR borrowck doesn't care about lifetime implications (which it might? not sure how complex that becomes).

---

However, a more immediate issue: #104343 (comment) contains, in the query cycle (tho at the bottom, maybe this should be reversed to look more like a backtrace?) the actual bound that caused the problem, so at least the user can guess something from it.

Someone should investigate how a similar thing doesn't get triggered for the example in this issue (interaction with dyn Trait? some obligation indirection? etc.).

[Dylan-DPC]

Current output:

error[E0283]: type annotations needed: cannot satisfy `impl futures::Future<Output = Out>: std::marker::Send`
   --> src/lib.rs:36:14
    |
36  |             .boxed()
    |              ^^^^^
    |
    = note: cannot satisfy `impl futures::Future<Output = Out>: std::marker::Send`
note: required by a bound in `futures::FutureExt::boxed`
   --> /playground/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/futures-util-0.3.31/src/future/future/mod.rs:516:23
    |
514 |     fn boxed<'a>(self) -> BoxFuture<'a, Self::Output>
    |        ----- required by a bound in this associated function
515 |     where
516 |         Self: Sized + Send + 'a,
    |                       ^^^^ required by this bound in `FutureExt::boxed`