async fn with elided lifetime causes rustc panic

[hack3ric]

Code to reproduce:

use futures::Stream;
use std::any::Any;

async fn foo(x: &str) -> impl Stream<Item = Box<dyn Any>> {}

and then run cargo check... (with full backtrace)

thread 'rustc' panicked at 'assertion failed: !erased_self_ty.has_escaping_bound_vars()', src/librustc/ty/util.rs:356:9
stack backtrace:
   0:        0x1054341e2 - std::panicking::default_hook::{{closure}}::h732feb85026a4422
   1:        0x105433eab - std::panicking::default_hook::h832638be7920e1d9
   2:        0x10410d3a3 - rustc::util::common::panic_hook::h50956d861d3d8265
   3:        0x105434aa1 - std::panicking::rust_panic_with_hook::h2746b02166e15af2
   4:        0x10409f2a5 - std::panicking::begin_panic::h230090070c2be599
   5:        0x104015c5d - rustc::ty::util::<impl rustc::ty::context::TyCtxt>::required_region_bounds::h2bfd0992e0240e65
   6:        0x1041b295b - rustc::infer::opaque_types::Instantiator::fold_opaque_ty::h6a2109340442464e
   7:        0x1042616a2 - <rustc::ty::fold::BottomUpFolder<F,G,H> as rustc::ty::fold::TypeFolder>::fold_ty::h7aa13d9636d94705
   8:        0x103e0765a - rustc::ty::fold::TypeFoldable::fold_with::h6eb10112104db7f6
   9:        0x1041b2d17 - rustc::infer::opaque_types::Instantiator::fold_opaque_ty::h6a2109340442464e
  10:        0x102eee399 - <rustc::ty::fold::BottomUpFolder<F,G,H> as rustc::ty::fold::TypeFolder>::fold_ty::h362061237fa87a5f
  11:        0x102e9619f - rustc_typeck::check::FnCtxt::instantiate_opaque_types_from_value::hdd338307918cfee6
  12:        0x102e8bcaa - rustc_typeck::check::check_fn::hac7bd15dbe73baf3
  13:        0x102fd07f4 - rustc::ty::context::GlobalCtxt::enter_local::h324ac2ec2e12e0e2
  14:        0x102e8b1ac - rustc_typeck::check::typeck_tables_of::h8a6866c5ac4e4538
  15:        0x102eab71e - rustc::ty::query::__query_compute::typeck_tables_of::h461c35490ac0925d
  16:        0x102f4d49b - rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::typeck_tables_of>::compute::hb6ba7a7a89baca84
  17:        0x102edc256 - rustc::dep_graph::graph::DepGraph::with_task_impl::h729ba93c71ed6836
  18:        0x102facd48 - rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query::ha9abd6cc76593f28
  19:        0x102eab71e - rustc::ty::query::__query_compute::typeck_tables_of::h461c35490ac0925d
  20:        0x102f4d49b - rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::typeck_tables_of>::compute::hb6ba7a7a89baca84
  21:        0x102edc256 - rustc::dep_graph::graph::DepGraph::with_task_impl::h729ba93c71ed6836
  22:        0x102facd48 - rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query::ha9abd6cc76593f28
  23:        0x103017d8c - rustc_typeck::collect::checked_type_of::h6778c833e01799c6
  24:        0x10301781e - rustc_typeck::collect::type_of::h1264787cfb7a8feb
  25:        0x102ead1cb - rustc::ty::query::__query_compute::type_of::h8914623b8a89443b
  26:        0x102f4d0cb - rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::type_of>::compute::h9e129d1cba94e459
  27:        0x102ed5816 - rustc::dep_graph::graph::DepGraph::with_task_impl::h2b7ac820718424f6
  28:        0x102f86f98 - rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query::h5ff957fa238b670a
  29:        0x102ff2a47 - rustc::hir::intravisit::walk_expr::hb0db1b8ea3eea671
  30:        0x103005314 - rustc::hir::intravisit::Visitor::visit_fn::hc5e7e3e1abe9958f
  31:        0x102fe36c3 - rustc::hir::intravisit::walk_impl_item::h4d45bdab776530c9
  32:        0x102eae0c8 - rustc::hir::map::Map::visit_item_likes_in_module::ha9769faef02af1e0
  33:        0x103013444 - rustc_typeck::collect::collect_mod_item_types::h2ec1a0c87fa3d49d
  34:        0x102eac5de - rustc::ty::query::__query_compute::collect_mod_item_types::heaa821ee7f695a15
  35:        0x102f4d75b - rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::collect_mod_item_types>::compute::h5f889db1173afe74
  36:        0x102ed5e38 - rustc::dep_graph::graph::DepGraph::with_task_impl::h2ef3fa01ca8acb95
  37:        0x102f7346e - rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query::h308b4698a27c8896
  38:        0x102ecb422 - rustc_typeck::check_crate::{{closure}}::{{closure}}::h9655a64665552d1e
  39:        0x102eae94d - rustc::util::common::time::h272405b2b749ed07
  40:        0x103058fee - rustc_typeck::check_crate::h484f134202177825
  41:        0x102acdfdf - rustc_interface::passes::analysis::hd60757f4c2b698a8
  42:        0x102a5f012 - rustc::ty::query::__query_compute::analysis::h78ec8ee67474784a
  43:        0x102a60fe5 - rustc::dep_graph::graph::DepGraph::with_task_impl::h4ac160ddc37c9308
  44:        0x1029de862 - rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query::he04d60713b4447ef
  45:        0x1029f9bec - rustc_interface::passes::BoxedGlobalCtxt::access::{{closure}}::h056779aae72902db
  46:        0x102b10acb - rustc_interface::passes::create_global_ctxt::{{closure}}::hfa8388d59c8efa62
  47:        0x1029fc489 - rustc_interface::interface::run_compiler_in_existing_thread_pool::hff72514f7ca933dc
  48:        0x102a0c9a4 - std::thread::local::LocalKey<T>::with::h91a2674509ca585e
  49:        0x102a1cbb2 - scoped_tls::ScopedKey<T>::set::h03f39cddb2457ca3
  50:        0x102a34245 - syntax::with_globals::h6d4146eff33e9bc1
  51:        0x102a569ba - std::sys_common::backtrace::__rust_begin_short_backtrace::hc2071b1843657bff
  52:        0x105443f3f - __rust_maybe_catch_panic
  53:        0x1029e4237 - core::ops::function::FnOnce::call_once{{vtable.shim}}::h1ae87809d2a636db
  54:        0x105417cce - <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once::hffc2c905ed2b6268
  55:        0x105442d5e - std::sys::unix::thread::Thread::new::thread_start::h6ca51316935dd8c4
  56:     0x7fff5b16f2eb - _pthread_body
  57:     0x7fff5b172249 - _pthread_start
query stack during panic:
#0 [typeck_tables_of] processing `s3::Foo::bar`
#1 [typeck_tables_of] processing `s3::Foo::bar::{{closure}}#0`
#2 [type_of] processing `s3::Foo::bar::{{closure}}#0`
#3 [collect_mod_item_types] collecting item types in module `s3`
#4 [analysis] running analysis passes on this crate
end of query stack

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.38.0-nightly (78ca1bda3 2019-07-08) running on x86_64-apple-darwin

note: compiler flags: -C debuginfo=2 -C incremental --crate-type lib

note: some of the compiler flags provided by cargo are hidden

This also reproduces when &str is replaced with &_ (where _ is any type), but does't reproduce with &'static _.

[hack3ric]

This situation also reproduces:

async fn foo<'a>(x: &'a str) -> impl Stream<Item = Box<Any>> {}

[cramertj]

I wasn't able to reproduce this on master. @hackerer1c can you check your original example with the latest nightly to see if it works properly?

[nikomatsakis]

@cramertj it seems to fail on the playground:

thread 'rustc' panicked at 'assertion failed: !erased_self_ty.has_escaping_bound_vars()', src/librustc/ty/util.rs:441:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.38.0-nightly (03f19f7ff 2019-07-24) running on x86_64-unknown-linux-gnu

note: compiler flags: -C codegen-units=1 -C debuginfo=2 --crate-type lib

note: some of the compiler flags provided by cargo are hidden

error: Could not compile `playground`.

To learn more, run the command again with --verbose.

[cramertj]

Oh, literally with that code and using futures 0.1 Stream-- got it!

[Aaron1011]

Minimized:

#![feature(async_await)]

trait FirstTrait {}
trait SecondTrait {
    type Item;
}

async fn foo(x: &str) -> impl SecondTrait<Item = dyn FirstTrait> {}

[Centril]

Reduced further:

#![feature(async_await)]

trait Object {}

trait Alpha<Param> {}

async fn foo<'a>(_: &'a ()) -> impl Alpha<dyn Object> {}

[jespersm]

I tried researching this a bit, with a locally built rustc:

1. Without debug logging, it panics.
2. If I turn on all debug logging, it reports a cycle and aborts with error E0391.
3. If I turn on debug logging for just rustc::ty, it ends up stack overflowing.

For case 2: It checks the opaque type, and then rechecks the return value, which needs to the the opaque type again:

DEBUG 2019-08-06T11:38:07Z: rustc::ty::print::pretty: try_print_visible_def_path: def_id=DefId(0:0 ~ issue_62517[317d])
error[E0391]: cycle detected when processing `foo::{{opaque}}#0`
  --> src/test/ui/async-await/issues/issue-62517.rs:10:32
   |
10 | async fn foo<'a>(_: &'a ()) -> impl Alpha<dyn Object> {
   |                                ^^^^^^^^^^^^^^^^^^^^^^
   |
note: ...which requires processing `foo::{{opaque}}#0`...
  --> src/test/ui/async-await/issues/issue-62517.rs:10:32
   |
10 | async fn foo<'a>(_: &'a ()) -> impl Alpha<dyn Object> {
   |                                ^^^^^^^^^^^^^^^^^^^^^^
note: ...which requires processing `foo::{{opaque}}#0`...
  --> src/test/ui/async-await/issues/issue-62517.rs:10:32
   |
10 | async fn foo<'a>(_: &'a ()) -> impl Alpha<dyn Object> {
   |                                ^^^^^^^^^^^^^^^^^^^^^^
   = note: ...which again requires processing `foo::{{opaque}}#0`, completing the cycle
note: cycle used when processing `foo`
  --> src/test/ui/async-await/issues/issue-62517.rs:10:1
   |
10 | async fn foo<'a>(_: &'a ()) -> impl Alpha<dyn Object> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

For case 3: It reports loops on this debug logging:

DEBUG 2019-08-06T11:31:03Z: rustc::ty::query::plumbing: ty::query::get_query<associated_item_def_ids>(key=DefId(2:7504 ~ core[b63e]::future[0]::future[0]::Future[0]), span=src/test/ui/async-await/issues/issue-62517.rs:1:1: 1:1)
DEBUG 2019-08-06T11:31:03Z: rustc::ty::query::plumbing: ty::query::get_query<associated_item>(key=DefId(2:7505 ~ core[b63e]::future[0]::future[0]::Future[0]::Output[0]), span=src/test/ui/async-await/issues/issue-62517.rs:1:1: 1:1)
DEBUG 2019-08-06T11:31:03Z: rustc::ty::query::plumbing: ty::query::get_query<get_lang_items>(key=crate0, span=src/test/ui/async-await/issues/issue-62517.rs:1:1: 1:1)
DEBUG 2019-08-06T11:31:03Z: rustc::ty::query::plumbing: ty::query::get_query<get_lang_items>(key=crate0, span=src/test/ui/async-await/issues/issue-62517.rs:1:1: 1:1)
DEBUG 2019-08-06T11:31:03Z: rustc::ty::query::plumbing: ty::query::get_query<inferred_outlives_of>(key=DefId(0:16 ~ issue_62517[317d]::foo[0]::{{opaque}}[0]), span=src/test/ui/async-await/issues/issue-62517.rs:1:1: 1:1)
DEBUG 2019-08-06T11:31:03Z: rustc::ty::query::plumbing: ty::query::get_query<def_kind>(key=DefId(0:16 ~ issue_62517[317d]::foo[0]::{{opaque}}[0]), span=src/test/ui/async-await/issues/issue-62517.rs:1:1: 1:1)
DEBUG 2019-08-06T11:31:03Z: rustc::ty::query::plumbing: ty::query::get_query<predicates_of>(key=DefId(0:16 ~ issue_62517[317d]::foo[0]::{{opaque}}[0]), span=src/test/ui/async-await/issues/issue-62517.rs:1:1: 1:1)
DEBUG 2019-08-06T11:31:03Z: rustc::ty::query::plumbing: ty::query::get_query<predicates_of>(key=DefId(0:16 ~ issue_62517[317d]::foo[0]::{{opaque}}[0]), span=src/test/ui/async-await/issues/issue-62517.rs:1:1: 1:1)
DEBUG 2019-08-06T11:31:03Z: rustc::ty::query::plumbing: ty::query::get_query<predicates_of>(key=DefId(0:16 ~ issue_62517[317d]::foo[0]::{{opaque}}[0]), span=src/test/ui/async-await/issues/issue-62517.rs:1:1: 1:1)
...

[nikomatsakis]

I've been digging into this. I don't quite know what the problem is yet but I see the "clues", so to speak, so I thought I'd jot down some notes while I wait for a build. I am working with @Aaron1011's minimization.

First off, the core of the problem is the dyn SecondTrait. The challenge here is that, in the lowering phase, the elided lifetime bound (dyn SecondTrait + 'X) is "passed on" to resolve lifetimes, which then applies the object lifetime bound defaulting rules to determine that 'X is 'static. However, while we are still in the HIR lowering phase, we treat it like any other elided lifetime. (As ever, the current setup is a pain that could really use to be reformed.)

When lowering the async fn return type, we encounter the impl FirstTrait<Item=...> return, and so we wind up generating two nested opaque types. The reference to that inner opaque type winds up with a late-bound lifetime, which doesn't seem right at all. I'm still trying to figure out what's going on there.

[nikomatsakis]

OK I'm starting to see what's going wrong. This is interacting with a bug in the handling of impl trait. It's something like this:

First off, in HIR lowering, we see the dyn Foo and lower that to dyn Foo + (elided). In the impl Trait desugaring, then, we create an opaque type with one lifetime parameter, corresponding to this (elided). This is already incorrect, as dyn Foo should be dyn Foo + 'static. In lifetime resolution, we don't know that this elided lifetime comes from a dyn Foo and hence we will treat it as any other elided lifetime, rather than applying the lifetime defaulting rules.

Somehow, when this is mixed with async fn, we wind up creating a late-bound lifetime. I'm not yet 100% sure how that comes to be.

I think the proper fix, well, the proper fix is to remove the resolve_lifetimes code altogether, though exactly what this looks like I don't know. It will take some thought.

But I think that for the time being what should be happening is that object lifetime defaults should be translated somewhat differently. e.g., instead of transforming them to a normal elided lifetime, maybe we should make a "object lifetime default elided", so that other parts of the system can know to ignore them. But I'd like to better understand just where the ICE arises.

Note that this is a bug in impl trait as well, though I've not been able to create an ICE there. For example, [this code is rejected]https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=ad989b84fb4d9e48c0243fd4ac7a13cc), but I don't believe it should be.

[nikomatsakis]

I have a fix coming. I think I see the problem, though I've not traced every single step. (Also I've not had time to run a full x.py check run).

The core problem is that impl TRait<Item = dyn Foo> generates an implied lifetime for the bound, which winds up (in the opaque type create a type Foo<'a> = impl Trait<item = dyn Foo> sort of result. This results in incorrect errors for impl Trait, but with async fn (I think because the lifetime replacement is ignored) it results in ICEs. I didn't 100% trace out the async fn pathway so I can't spell out every step, but it seems clear.

My fix is to distinguish implicit trait object lifetime bounds from other implicit lifetimes, so that when we generate the opaque type we don't create lifetime parameters for them. This also fixes the interaction with impl Trait.