ICE: Generic type alias to invalid type crashes during type check on latest stable

[RustyYato]

This also crashes on the latest nightly

playground

use std::marker::PhantomData;

fn _alias_check() {
    WrongImpl::foo(0i32);       // crash
    WrongImpl::<()>::foo(0i32); // fine
    CorrectImpl::foo(0i32);     // fine
}

pub trait Raw<T: ?Sized> {
    type Value;
}

pub type WrongImpl<T> = SafeImpl<T, RawImpl<T>>;

pub type CorrectImpl<T> = SafeImpl<[T], RawImpl<T>>;

pub struct RawImpl<T>(PhantomData<T>);

impl<T> Raw<[T]> for RawImpl<T> {
    type Value = T;
}

pub struct SafeImpl<T: ?Sized, A: Raw<T>>(PhantomData<(A, T)>);

impl<T: ?Sized, A: Raw<T>> SafeImpl<T, A> {
    pub fn foo(value: A::Value) {}
}

[hellow554]

Backtrace:

error: internal compiler error: src/librustc/traits/select.rs:3658: Impl DefId(0:25 ~ playground[abf7]::{{impl}}[0]) was matchable against Obligation(predicate=Binder(TraitPredicate(<RawImpl<_> as Raw<_>>)),depth=0) but now is not

thread 'rustc' panicked at 'Box<Any>', src/librustc_errors/lib.rs:637:9
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:197
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:211
   4: rustc::util::common::panic_hook
   5: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:478
   6: std::panicking::begin_panic
   7: rustc_errors::Handler::bug
   8: rustc::util::bug::opt_span_bug_fmt::{{closure}}
   9: rustc::ty::context::tls::with_opt::{{closure}}
  10: rustc::ty::context::tls::with_context_opt
  11: rustc::ty::context::tls::with_opt
  12: rustc::util::bug::opt_span_bug_fmt
  13: rustc::util::bug::bug_fmt
  14: rustc::infer::InferCtxt::in_snapshot
  15: rustc::traits::select::SelectionContext::confirm_candidate
  16: rustc::traits::select::SelectionContext::select
  17: rustc_data_structures::obligation_forest::ObligationForest<O>::process_obligations
  18: <rustc::traits::fulfill::FulfillmentContext as rustc::traits::engine::TraitEngine>::select_where_possible
  19: rustc_typeck::check::FnCtxt::select_obligations_where_possible
  20: rustc_typeck::check::FnCtxt::structurally_resolved_type
  21: rustc_typeck::check::callee::<impl rustc_typeck::check::FnCtxt>::check_call
  22: rustc_typeck::check::FnCtxt::check_expr_kind
  23: rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_needs
  24: rustc_typeck::check::FnCtxt::check_stmt
  25: rustc_typeck::check::FnCtxt::check_block_with_expected
  26: rustc_typeck::check::FnCtxt::check_expr_kind
  27: rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_needs
  28: rustc_typeck::check::FnCtxt::check_return_expr
  29: rustc_typeck::check::check_fn
  30: rustc::ty::context::GlobalCtxt::enter_local
  31: rustc_typeck::check::typeck_tables_of
  32: rustc::ty::query::__query_compute::typeck_tables_of
  33: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::typeck_tables_of>::compute
  34: rustc::dep_graph::graph::DepGraph::with_task_impl
  35: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  36: rustc::ty::<impl rustc::ty::context::TyCtxt>::par_body_owners
  37: rustc_typeck::check::typeck_item_bodies
  38: rustc::ty::query::__query_compute::typeck_item_bodies
  39: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::typeck_item_bodies>::compute
  40: rustc::dep_graph::graph::DepGraph::with_task_impl
  41: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  42: rustc::util::common::time
  43: rustc_typeck::check_crate
  44: rustc_interface::passes::analysis
  45: rustc::ty::query::__query_compute::analysis
  46: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::analysis>::compute
  47: rustc::dep_graph::graph::DepGraph::with_task_impl
  48: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  49: rustc::ty::context::tls::enter_global
  50: rustc_interface::passes::BoxedGlobalCtxt::access::{{closure}}
  51: rustc_interface::passes::create_global_ctxt::{{closure}}
  52: rustc_interface::interface::run_compiler_in_existing_thread_pool
  53: std::thread::local::LocalKey<T>::with
  54: scoped_tls::ScopedKey<T>::set
  55: syntax::with_globals
query stack during panic:
#0 [typeck_tables_of] processing `_alias_check`
#1 [typeck_item_bodies] type-checking all item bodies
#2 [analysis] running analysis passes on this crate
end of query stack
error: aborting due to previous error


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.36.0 (a53f9df32 2019-07-03) running on x86_64-unknown-linux-gnu

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

[lqd]

This started ICE-ing in 1.27. The first nightly where it's present seems to be nightly-2018-04-28 (there were a lot of missing nightlies in april 2018). Unfortunately there are no available CI artifacts for these old commits to automatically bisect to a PR.

Backtrace on nightly-2018-04-28

error: internal compiler error: librustc/traits/select.rs:3121: Impl DefId(0/0:10 ~ foo[9294]::{{impl}}[0]) was matchable against Obligation(predicate=Binder(TraitPredicate(<RawImpl<_> as Raw<_>>)),depth=0) but now is not

thread 'rustc' panicked at 'Box<Any>', librustc_errors/lib.rs:546:9
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:205
   3: std::panicking::default_hook
             at libstd/panicking.rs:221
   4: rustc::util::common::panic_hook
   5: std::panicking::rust_panic_with_hook
             at libstd/panicking.rs:461
   6: std::panicking::begin_panic
   7: rustc_errors::Handler::bug
   8: rustc::session::opt_span_bug_fmt::{{closure}}
   9: rustc::ty::context::tls::with_opt::{{closure}}
  10: rustc::ty::context::tls::with_context_opt
  11: rustc::ty::context::tls::with_opt
  12: rustc::session::opt_span_bug_fmt
  13: rustc::session::bug_fmt
  14: rustc::traits::select::SelectionContext::confirm_candidate
  15: rustc::traits::select::SelectionContext::select
  16: <rustc::traits::fulfill::FulfillProcessor<'a, 'b, 'gcx, 'tcx> as rustc_data_structures::obligation_forest::ObligationProcessor>::process_obligation
  17: <rustc::traits::fulfill::FulfillmentContext<'tcx> as rustc::traits::engine::TraitEngine<'tcx>>::select_where_possible
  18: rustc_typeck::check::FnCtxt::select_obligations_where_possible
  19: rustc_typeck::check::FnCtxt::structurally_resolved_type
  20: rustc_typeck::check::FnCtxt::check_expr_kind
  21: rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_needs
  22: rustc_typeck::check::FnCtxt::check_block_with_expected
  23: rustc_typeck::check::FnCtxt::check_expr_kind
  24: rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_needs
  25: rustc_typeck::check::FnCtxt::check_return_expr
  26: rustc_typeck::check::check_fn
  27: rustc::ty::context::tls::with_related_context
  28: rustc::infer::InferCtxtBuilder::enter
  29: rustc_typeck::check::typeck_tables_of
  30: rustc::ty::maps::<impl rustc::ty::maps::config::QueryConfig<'tcx> for rustc::ty::maps::queries::typeck_tables_of<'tcx>>::compute
  31: rustc::ty::context::tls::with_context
  32: rustc::dep_graph::graph::DepGraph::with_task_impl
  33: rustc::ty::context::tls::with_related_context
  34: rustc::ty::maps::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::force_query_with_job
  35: rustc::ty::maps::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::get_query
  36: rustc::ty::maps::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::ensure_query
  37: rustc::session::Session::track_errors
  38: rustc_typeck::check::typeck_item_bodies
  39: rustc::ty::context::tls::with_context
  40: rustc::dep_graph::graph::DepGraph::with_task_impl
  41: rustc::ty::context::tls::with_related_context
  42: rustc::ty::maps::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::force_query_with_job
  43: rustc::ty::maps::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::get_query
  44: rustc_typeck::check_crate
  45: rustc::ty::context::tls::enter_context
  46: <std::thread::local::LocalKey<T>>::with
  47: rustc::ty::context::TyCtxt::create_and_enter
  48: rustc_driver::driver::compile_input
  49: rustc_driver::run_compiler_impl
  50: syntax::with_globals
query stack during panic:
#0 [typeck_tables_of] processing `_alias_check`
#1 [typeck_item_bodies] type-checking all item bodies
end of query stack
error: aborting due to previous error


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.27.0-nightly (686d0ae13 2018-04-27) running on x86_64-unknown-linux-gnu

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

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

The range of commits between the previous nightly and this one is 7f3444e to 686d0ae.

It contains, in reverse chronological order:

• commit 686d0ae a rollup of 9 other PRs
  • std: Mark ptr::Unique with #[doc(hidden)] #49858 (std: Mark ptr::Unique with #[doc(hidden)])
  • Stabilize dyn trait #49968 (Stabilize dyn trait)
  • Add some utilities to libsyntax #50192 (Add some utilities to libsyntax)
  • rustc: Disable threads in LLD for wasm #50251 (rustc: Disable threads in LLD for wasm)
  • rustc: Emit uwtable for allocator shims #50263 (rustc: Emit uwtable for allocator shims)
  • Update parking_lot dependencies #50269 (Update parking_lot dependencies)
  • Allow #[inline] on closures #50273 (Allow #[inline] on closures)
  • fix search load page failure #50284 (fix search load page failure)
  • Don't ICE on tuple struct ctor with incorrect arg count #50257 (Don't ICE on tuple struct ctor with incorrect arg count)
• commit a997525 - Remove hack around comparisons of i1 values (fixes #40980) #50137 (Remove hack around comparisons of i1 values)
• commit 3c43aa5 - Move query code outside macros and store query jobs separately from query results #50102 (Move query code outside macros and store query jobs separately from query results)
• commit 71d3dac - Partial future-proofing for Box<T, A> #50097 (Partial future-proofing for Box<T, A>)
• commit ada45fd a rollup of 7 other PRs
  • Add "the Rustc book" #49707 (Add "the Rustc book")
  • Bump bootstrap compiler to 2018-04-24 #50222 (Bump bootstrap compiler to 2018-04-24)
  • Fix ICE with erroneous impl Trait in a trait impl #50227 (Fix ICE with erroneous impl Trait in a trait impl)
  • Add setting to go to item if there is only one result #50229 (Add setting to go to item if there is only one result)
  • Add more doc aliases #50231 (Add more doc aliases)
  • Make dump_{alloc,allocs,local}() no-ops when tracing is disabled. #50246 (Make dump_{alloc,allocs,local}() no-ops when tracing is disabled.)
  • Rename InternedString to LocalInternedString and introduce a new thread-safe InternedString #49894 (Rename InternedString to LocalInternedString and introduce a new thread-safe InternedString)
• commit 9822b57 - compiletest: detect non-ICE compiler panics #49891 (compiletest: detect non-ICE compiler panics)
• commit 8a09bc6 - Create a canonical trait query for evaluate_obligation #48995 (Create a canonical trait query for evaluate_obligation ) <- this one looks interesting
• commit e05b78d - Use ScalarPair for tagged enums #49420 (Use ScalarPair for tagged enums)
• commit 7d8f0e2 - drop elaboration should reveal all #50253 (drop elaboration should reveal all)
• commit 7f3444e - Treat repr(Rust) univariant fieldless enums as ZSTs #49513 (Treat repr(Rust) univariant fieldless enums as ZSTs)

In particular #48995 may be related, "a new canonical trait query for evaluate_obligation in the trait selector".

---

update: made the commit range shorter

[pnkfelix]

visiting for triage: @nikomatsakis do you plan to investigate or delegate in near term?

[pnkfelix]

nominating for reassignment.

[nikomatsakis]

I can look at it, although maybe @tmandry might be a good fit, too.

[nikomatsakis]

OK, I put some work into investigation here. I at least see what is going wrong, and actually the fix I suspect is a refactoring that I've been considering for some time, but which I think has been blocked on getting rid of the leak-check (so cc #65232).

The problem is that, the way our type checker works, when we have a subtyping relationship $1 <: $2 between two inference variables, we record this in a kind of "side-table" called the sub_relations. The two type variables therefore are not equated exactly -- but, once we know one of them, we do learn a lot about the other. So what happens is that when we equate $1 with some type (say &'a u32) then we go and instantiate $2 to be equal to a variation of $1. Specifically, a variation in which all lifetimes are replaced with variables: &'b u32, you might say. Then we relate $1 and $2, which gives rise to a region constraint (in this case, 'a: 'b). OK, so far so good.

Now the problem is that when we do our canonicalization, even though $1 and $2 are in some way related, we have to treat them as independent variables. So we canonicalize them to fresh independent variables. Then we go and evaluate which impl will apply. In this case, it's the impl providing RawImpl<T>: Raw<[T]>. So we get back a result that's like "yep there is only one option and it is $1 = $3 and $2 = [$3]".

OK, so then we go and apply that result to our actual variables. But remember that we had a subtyping relationship between $1 and $2. So now we wind up with:

$1 <: $2 (from before)
$1 = $3
$2 = [$3]

which together implies that $3 <: [$3]. This is, of course, impossible.

As it happens, we (sort of) detect this when we are "generalizing" $2. We walk down the type we are generalizing from ([$3]) and we encounter the type variable $3, which we see is "related" to $2 via some chain of equality and subtyping. We then fail because of our version of the occurs check. Thus unification fails, which then causes the ICE that we see (because we expected unification to succeed).

Here are some of the solutions I think we could do here:

• Instead of making unification fail we could generate a constraint that will eventually lead to an error.
• We could handle $1 <: $2 constraints by generating an obligation instead -- but for this to work, we can't have the leak-check around (or, at least, we can only do it for variables in the root universe I think). This is because the obligation needs to be passed back out from unification. If we took that approach, though, we'd be able to successfully unify $1 with $3 and $2 with [$3], and we'd only fail later when we tried to make $3 a subtype of [$3] (in the same way, with the occurs check).

I think I favor the second half. I've been steadily trying to maneuver our type system implementation into a combination of two things:

• Straight-up HM variables, that are instantiated once with firm equality.
• A list of pending obligations for things where we can't make progress immediately (e.g. because of ambiguity that may later be resolved).

The current "sub relations" list is basically a third bullet, and it's kind of a special case of the pending obligations. The ICE we're seeing here is precisely arising because of the "canonicalization" system assumes that it can treat unbound variables as independent things from one another. Right now, we can't because of these implicit links due to subtyping.