ICE in librustc::traits::select::confirm_param_candidate

[aweinstock314]

Error message: error: internal compiler error: src/librustc/traits/select.rs:2922: Where clause `Binder(<base::default_allocator::DefaultAllocator as base::allocator::Allocator<N, R, C>>)` was applicable to `Obligation(predicate=Binder(TraitPredicate(<base::default_allocator::DefaultAllocator as base::allocator::Allocator<_, _, _>>)), depth=1)` but now is not

Commit that reproduces the issue: aweinstock314/nalgebra@5106e2d

I get the same error (except for the exact line number) on 1.38, 1.40, beta, and a couple of nightlies.

The other issues reachable via the query is:issue is:open ICE "but now is not" (#62742 and #55765) are both about the "was matchable against" bug! invocation at

rust/src/librustc/traits/select.rs

Line 3464 in 4884061

"Impl {:?} was matchable against {:?} but now is not",

, this bug! invocation is at

rust/src/librustc/traits/select.rs

Line 2781 in 4884061

"Where clause `{:?}` was applicable to `{:?}` but now is not",

, so this is unlikely to be a duplicate.

I haven't yet tried to minimize this: The commit beforehand (1 line difference) on the same nalgebra branch is a compile-fail due to a trait method not being found, and I'm still trying to figure out if that one's a bug in my code.

[hellow554]

It would be nice if you could post the backtrace next time :)

error: internal compiler error: src/librustc/traits/select.rs:2933: Where clause `Binder(<base::default_allocator::DefaultAllocator as base::allocator::Allocator<N, R, C>>)` was applicable to `Obligation(predicate=Binder(TraitPredicate(<base::default_allocator::DefaultAllocator as base::allocator::Allocator<_, _, _>>)), depth=1)` but now is not

thread 'rustc' panicked at 'Box<Any>', src/librustc_errors/lib.rs:892:9
stack backtrace:
   0:     0x7f66dc54be94 - backtrace::backtrace::libunwind::trace::h3af7d8f0cad3d88e
                               at /cargo/registry/src/github.heygears.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/libunwind.rs:88
   1:     0x7f66dc54be94 - backtrace::backtrace::trace_unsynchronized::hcec51d2fabb72b74
                               at /cargo/registry/src/github.heygears.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/mod.rs:66
   2:     0x7f66dc54be94 - std::sys_common::backtrace::_print_fmt::hcd1780c700b0133c
                               at src/libstd/sys_common/backtrace.rs:84
   3:     0x7f66dc54be94 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::he6a1ce49d42ba791
                               at src/libstd/sys_common/backtrace.rs:61
   4:     0x7f66dc5845ac - core::fmt::write::hd8162e8147f9c30a
                               at src/libcore/fmt/mod.rs:1025
   5:     0x7f66dc5401c7 - std::io::Write::write_fmt::hafa84d2501c82b1a
                               at src/libstd/io/mod.rs:1426
   6:     0x7f66dc55033e - std::sys_common::backtrace::_print::hb630961a44ec5c08
                               at src/libstd/sys_common/backtrace.rs:65
   7:     0x7f66dc55033e - std::sys_common::backtrace::print::h8721ef57e620a95d
                               at src/libstd/sys_common/backtrace.rs:50
   8:     0x7f66dc55033e - std::panicking::default_hook::{{closure}}::h830d8b6321244162
                               at src/libstd/panicking.rs:193
   9:     0x7f66dc550031 - std::panicking::default_hook::h483ff228a4236089
                               at src/libstd/panicking.rs:210
  10:     0x7f66dcad72c3 - rustc_driver::report_ice::h6c459048104da02e
  11:     0x7f66dc550af0 - std::panicking::rust_panic_with_hook::hf9b4de76bea4ec49
                               at src/libstd/panicking.rs:475
  12:     0x7f66decb4a6d - std::panicking::begin_panic::h11dacb2a580cfc13
  13:     0x7f66dece9770 - rustc_errors::HandlerInner::bug::h6630f664722f00a9
  14:     0x7f66dece84da - rustc_errors::Handler::bug::hcd6102dbbb94a270
  15:     0x7f66de7fbb02 - rustc::util::bug::opt_span_bug_fmt::{{closure}}::h958ad6a6d585dbab
  16:     0x7f66de7f26c3 - rustc::ty::context::tls::with_opt::{{closure}}::hffb1b73c4cf34c3e
  17:     0x7f66de7f2618 - rustc::ty::context::tls::with_opt::h2f9609d99125a138
  18:     0x7f66de7fba18 - rustc::util::bug::opt_span_bug_fmt::h341a618023e54cd9
  19:     0x7f66de7fb982 - rustc::util::bug::bug_fmt::hee90e2fc57db382e
  20:     0x7f66de77bcdc - rustc::traits::select::SelectionContext::confirm_candidate::h9a41ea5dfb60b800
  21:     0x7f66de76ef1d - rustc::traits::select::SelectionContext::select::h3fcfb6a38fb36eea
  22:     0x7f66de3e76ed - rustc::infer::InferCtxt::commit_if_ok::h989729c049a84245
  23:     0x7f66de673b10 - rustc::traits::project::opt_normalize_projection_type::habfea972e4de8462
  24:     0x7f66de672066 - rustc::traits::project::normalize_projection_type::h1513d65033c29310
  25:     0x7f66de671dcf - <rustc::traits::project::AssocTypeNormalizer as rustc::ty::fold::TypeFolder>::fold_ty::h8c90ff7aa86152db
  26:     0x7f66de673070 - rustc::traits::project::opt_normalize_projection_type::habfea972e4de8462
  27:     0x7f66de672066 - rustc::traits::project::normalize_projection_type::h1513d65033c29310
  28:     0x7f66de671dcf - <rustc::traits::project::AssocTypeNormalizer as rustc::ty::fold::TypeFolder>::fold_ty::h8c90ff7aa86152db
  29:     0x7f66de434879 - <smallvec::SmallVec<A> as core::iter::traits::collect::FromIterator<<A as smallvec::Array>::Item>>::from_iter::h5c195ee5fa843a52
  30:     0x7f66de597ed0 - rustc::ty::fold::TypeFoldable::fold_with::h494171898eb4d2b9
  31:     0x7f66de5a8acf - rustc::ty::structural_impls::<impl rustc::ty::fold::TypeFoldable for &rustc::ty::TyS>::super_fold_with::h90eb496dc4436138
  32:     0x7f66de671c06 - <rustc::traits::project::AssocTypeNormalizer as rustc::ty::fold::TypeFolder>::fold_ty::h8c90ff7aa86152db
  33:     0x7f66dd4d4b46 - rustc::traits::project::normalize::h78c1fa95b6f240f0
  34:     0x7f66dd3ed080 - rustc_typeck::check::method::probe::ProbeContext::assemble_inherent_impl_probe::h494ffc1498e51dc6
  35:     0x7f66dd3ebf5e - rustc_typeck::check::method::probe::ProbeContext::assemble_inherent_candidates::h56005b43ad7cc91b
  36:     0x7f66dd3a615e - rustc::infer::InferCtxt::probe::hd652857fa9508021
  37:     0x7f66dd2ed944 - rustc_typeck::check::method::probe::<impl rustc_typeck::check::FnCtxt>::probe_for_return_type::ha7aedd7ef8784adb
  38:     0x7f66dd31d8d5 - rustc_typeck::check::FnCtxt::suggest_ref_or_into::hcd8cb08de7ed55de
  39:     0x7f66dd2dd169 - rustc_typeck::check::demand::<impl rustc_typeck::check::FnCtxt>::emit_coerce_suggestions::hb99f7ac0a38f7858
  40:     0x7f66dd349d7e - rustc_typeck::check::coercion::CoerceMany<E>::coerce_inner::h728474070fc6e1e1
  41:     0x7f66dd31c06a - rustc_typeck::check::FnCtxt::check_block_with_expected::hbc8145eb75063594
  42:     0x7f66dd2e2e74 - rustc_typeck::check::expr::<impl rustc_typeck::check::FnCtxt>::check_expr_kind::hdfa545abcd1f4f9a
  43:     0x7f66dd2e220b - rustc_typeck::check::expr::<impl rustc_typeck::check::FnCtxt>::check_expr_with_expectation_and_needs::h394f3bf285701128
  44:     0x7f66dd2ecafb - rustc_typeck::check::expr::<impl rustc_typeck::check::FnCtxt>::check_return_expr::he6756fd8b7df94fd
  45:     0x7f66dd30782f - rustc_typeck::check::check_fn::h5fcb7eecce1a7cc8
  46:     0x7f66dd4c1261 - rustc::ty::context::tls::with_context::{{closure}}::hf245d6ba2539ac8e
  47:     0x7f66dd3065f2 - rustc_typeck::check::typeck_tables_of::h0dff56b11c3b1dc9
  48:     0x7f66dd50528a - rustc::ty::query::__query_compute::typeck_tables_of::h6fbd03e165500945
  49:     0x7f66dd42a44b - rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::typeck_tables_of>::compute::hee42e90da8c65856
  50:     0x7f66dd3c92a2 - rustc::dep_graph::graph::DepGraph::with_task_impl::he626bbd887e9bd71
  51:     0x7f66dd45abb5 - rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query::h40bbc3f422f79644
  52:     0x7f66dd426a7f - rustc::ty::<impl rustc::ty::context::TyCtxt>::par_body_owners::hfe2b7e757907435a
  53:     0x7f66dd305f0d - rustc_typeck::check::typeck_item_bodies::hc448723e529dff79
  54:     0x7f66dd5056d5 - rustc::ty::query::__query_compute::typeck_item_bodies::h3b3cd5a8a42a51ab
  55:     0x7f66dd3b9154 - rustc::dep_graph::graph::DepGraph::with_task_impl::h31afe2e2781df8eb
  56:     0x7f66dd4807cb - rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query::h8ca4233134fb396f
  57:     0x7f66dd4d421e - rustc::util::common::time::hcf4211da7181e73a
  58:     0x7f66dd4f8e0d - rustc_typeck::check_crate::hd9bed871ae68fcef
  59:     0x7f66dcc41174 - rustc_interface::passes::analysis::hf458fdc494d55942
  60:     0x7f66dca6abb1 - rustc::ty::query::__query_compute::analysis::hb40ee54599ba8f81
  61:     0x7f66dcab87a9 - rustc::dep_graph::graph::DepGraph::with_task_impl::hfa107e8e634564ca
  62:     0x7f66dcae276d - rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query::hef9bfd321d7b5f9f
  63:     0x7f66dca886c5 - rustc::ty::context::tls::enter_global::he916f073b76f98f8
  64:     0x7f66dca9e094 - rustc_interface::interface::run_compiler_in_existing_thread_pool::h809fe2cdffb27eea
  65:     0x7f66dca6e892 - std::thread::local::LocalKey<T>::with::hdd7a4f7dd5973d77
  66:     0x7f66dca67dde - scoped_tls::ScopedKey<T>::set::h1a7050e3b333ae25
  67:     0x7f66dcae35e4 - syntax::with_globals::h5728c0a6d54600d2
  68:     0x7f66dca68a40 - std::sys_common::backtrace::__rust_begin_short_backtrace::hd043e51745c2002a
  69:     0x7f66dc5615ca - __rust_maybe_catch_panic
                               at src/libpanic_unwind/lib.rs:78
  70:     0x7f66dca7f079 - core::ops::function::FnOnce::call_once{{vtable.shim}}::h3e9570487439b1c8
  71:     0x7f66dc5321cf - <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once::h66f513834129f65f
                               at /rustc/c8ea4ace9213ae045123fdfeb59d1ac887656d31/src/liballoc/boxed.rs:1022
  72:     0x7f66dc55fff0 - <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once::hae4f8b730c770e10
                               at /rustc/c8ea4ace9213ae045123fdfeb59d1ac887656d31/src/liballoc/boxed.rs:1022
  73:     0x7f66dc55fff0 - std::sys_common::thread::start_thread::hade1fccd694a6ed2
                               at src/libstd/sys_common/thread.rs:13
  74:     0x7f66dc55fff0 - std::sys::unix::thread::Thread::new::thread_start::hcbccf366a29cb6fb
                               at src/libstd/sys/unix/thread.rs:80
  75:     0x7f66dc49d669 - start_thread
  76:     0x7f66dc3b2323 - clone
  77:                0x0 - <unknown>

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.41.0-nightly (c8ea4ace9 2019-12-14) running on x86_64-unknown-linux-gnu

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

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

query stack during panic:
#0 [typeck_tables_of] processing `base::conversion::<impl std::convert::From<base::matrix::Matrix<N, R, C, base::matrix_slice::SliceStorage<'a, N, R, C, RStride, CStride>>> for base::matrix::Matrix<N, R, C, base::array_storage::ArrayStorage<N, R, C>>>::from`
#1 [typeck_item_bodies] type-checking all item bodies
#2 [analysis] running analysis passes on this crate
end of query stack

[hellow554]

Something small-ish:

pub struct Matrix<R, C, S> {
    _phantoms: std::marker::PhantomData<(R, C, S)>,
}

impl<R, C, S> Matrix<R, C, S> {
    pub fn into_owned(self) -> Matrix<R, C, Owned<R, C, ()>>
    where
        (): Allocator<R, C>,
    {
        unimplemented!()
    }
}

impl<D, S> Matrix<D, D, S> {
    pub fn hermitian_part(&self) -> Matrix<D, D, Owned<D, D, ()>>
    where
        (): Allocator<D, D>,
    {
        unimplemented!()
    }
}

pub trait Allocator<R, C> {
    type Buffer;
}

pub trait Trait<R, C, A> {
    type Power;
}

impl<R, C, A: Allocator<R, C>> Trait<R, C, A> for () {
    type Power = A::Buffer;
}

pub type Owned<R, C, G> = <G as Trait<R, C, ()>>::Power;

pub fn crash<R, C>(input: Matrix<R, C, ()>) -> Matrix<R, C, u32>
where
    (): Allocator<R, C>,
{
    input.into_owned()
}

[Aaron1011]

This is an issue with how SelectionContext performs caching. Predicates are "freshened" before being used as cache keys, which replaces each distinct type variable with a deterministic FreshTy. This is supposed to allow us to cache predicates across different InferCtxts.

Unfortunately, this doesn't take into account relationships between type variables. This leads to the following scenario:

1. Someone tries to select the predicate <MyType as MyTrait<_#7t, _#8>>, where _#7t and _#8 are distinct type variables (there is no relationship between them). This succeeds, and we cache the result under the key <MyType as MyTrait<FreshTy(0), FreshTy(1)>>
2. We enter a different InferCtxt, and create the type variables _#9 and _#10. These region variables end up getting equated to each other - although we don't know the concrete type, it is the same for both of them.
3. We try to select the predicate <MyType as MyTrait<_#9t, _#10>>. We try to lookup the cached result under the key <MyType as MyTrait<FreshTy(0), FreshTy(1)>>. However, this is wrong: we cached the result assuming that FreshTy(0) and FreshTy(1) are different types. However, we now have the same type for both substs, so we have no guarantee that our cached result is valid.

In the minimized example, we end up caching <() as Allocator<R, C>> under <() as Allocator<FreshTy(0), FreshTy(1)>>. We then try to use this cached result when searching through inherent methods in the hermitian_part impl - we lookup <() as Allocator<_#0t, _#1t>> where _#0t == _#1t == D. We get a cached result of ParamCandidate(Binder(<() as Allocator<R, C>>, which does not actually apply here.

I think we either need to either:

1. Be much more conservative about the caching we perform
2. Somehow incorporate extra knowledge about inference variable relationships into the cache key. It's not obvious to me whether this could be done by unifying 'equivalent' inference variables, or if we would need to somehow store actual constraints from the InferCtxt.

This may have soundness implications, especially when it comes to regions. I don't think we're guaranteed to always ICE on a cache entry that's actually inapplicable.

[Aaron1011]

cc @eddyb: I believe this may have been exposed by #66821, since without it we wouldn't be caching the ParamCandidate, However, I think the underlying issue would still exist without that PR.

[eddyb]

Can't freshening try to resolve every variable it's replacing, on the fly?
Assuming we're still using union-find, one of _#9 and _#10 should get redirected to the other.

cc @nikomatsakis

[aweinstock314]

I got another ICE with the same codebase, after tweaking it to pass trait resolution. Commit that reproduces the ICE is at aweinstock314/nalgebra@649507d .

Should I file this as a separate issue, or treat it as related for now?
I'll probably try and create a minimal testcase for this next.

Backtrace is as follows:

error: internal compiler error: broken MIR in DefId(0:6065 ~ nalgebra[c4da]::geometry[0]::isometry[0]::{{impl}}[5]::to_homogeneous[0]) (NoSolution): failed to normalize `base::matrix::Matrix<N, _, _, <base::default_allocator::DefaultAllocator as base::allocator::Allocator<N, _, _>>::Buffer>`

thread 'rustc' panicked at 'no errors encountered even though `delay_span_bug` issued', src/librustc_errors/lib.rs:391:17
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/github.heygears.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/libunwind.rs:88
   1: backtrace::backtrace::trace_unsynchronized
             at /cargo/registry/src/github.heygears.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/mod.rs:66
   2: std::sys_common::backtrace::_print_fmt
             at src/libstd/sys_common/backtrace.rs:77
   3: <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt
             at src/libstd/sys_common/backtrace.rs:61
   4: core::fmt::write
             at src/libcore/fmt/mod.rs:1028
   5: std::io::Write::write_fmt
             at src/libstd/io/mod.rs:1412
   6: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:65
   7: std::sys_common::backtrace::print
             at src/libstd/sys_common/backtrace.rs:50
   8: std::panicking::default_hook::{{closure}}
             at src/libstd/panicking.rs:188
   9: std::panicking::default_hook
             at src/libstd/panicking.rs:205
  10: rustc_driver::report_ice
  11: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:468
  12: std::panicking::begin_panic
  13: <rustc_errors::HandlerInner as core::ops::drop::Drop>::drop
  14: core::ptr::real_drop_in_place
  15: <alloc::rc::Rc<T> as core::ops::drop::Drop>::drop
  16: core::ptr::real_drop_in_place
  17: rustc_interface::interface::run_compiler_in_existing_thread_pool
  18: std::thread::local::LocalKey<T>::with
  19: scoped_tls::ScopedKey<T>::set
  20: syntax::with_globals
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose 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.40.0 (73528e339 2019-12-16) running on x86_64-unknown-linux-gnu

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

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

query stack during panic:
end of query stack
error: could not compile `nalgebra`.

[hellow554]

@aweinstock314 a new issue would be great

[aweinstock314]

Issue #68090 gives an error message with very similar strings ("broken MIR in DefId"/"NoSolution") and their minimized example looks like it was minimized from a type that's also used by nalgebra, so I'll try to figure out whether the second ICE is a duplicate of that before filing an issue/adding to that thread.

[pnkfelix]

triage: P-high, removing nomination

[Centril]

cc @rust-lang/wg-traits

[nikomatsakis]

I'm familiar with this bug, I can try to dig in and make a recommendation for a fix.

[Alexendoo]

No longer ICEs since #86506