ICE when compiling some specific set of traits defined for nalgebra's matrix

[farmaazon]

Code

available at https://github.com/farmaazon/rustc-ice-case

Meta

rustc --version --verbose:

rustc 1.51.0 (2fd73fabe 2021-03-23)
binary: rustc
commit-hash: 2fd73fabe469357a12c2c974c140f67e7cdd76d0
commit-date: 2021-03-23
host: x86_64-unknown-linux-gnu
release: 1.51.0
LLVM version: 11.0.1

also reproduced on

rustc 1.53.0-nightly (6df26f897 2021-04-20)
binary: rustc
commit-hash: 6df26f897cffb2d86880544bb451c6b5f8509b2d
commit-date: 2021-04-20
host: x86_64-unknown-linux-gnu
release: 1.53.0-nightly
LLVM version: 12.0.0

HOWEVER it does not reproduce on

rustc 1.40.0-nightly (b520af6fd 2019-11-03)
binary: rustc
commit-hash: b520af6fd515b186caed436d75162a42aa183d95
commit-date: 2019-11-03
host: x86_64-unknown-linux-gnu
release: 1.40.0-nightly
LLVM version: 9.0

Error output

error: internal compiler error: Encountered error `Unimplemented` selecting `Binder(<nalgebra::Matrix<f32, nalgebra::U4, nalgebra::U4, nalgebra::ArrayStorage<f32, nalgebra::U4, nalgebra::U4>> as JsBufferView>, [])` during codegen
  |
  = note: delayed at compiler/rustc_trait_selection/src/traits/codegen.rs:68:32

Backtrace

thread 'rustc' panicked at 'called `Result::unwrap()` on an `Err` value: ErrorReported', compiler/rustc_mir/src/monomorphize/collector.rs:785:84
stack backtrace:
   0: rust_begin_unwind
             at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/panicking.rs:493:5
   1: core::panicking::panic_fmt
             at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/core/src/panicking.rs:92:14
   2: core::result::unwrap_failed
             at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/core/src/result.rs:1355:5
   3: <rustc_mir::monomorphize::collector::MirNeighborCollector as rustc_middle::mir::visit::Visitor>::visit_terminator
   4: rustc_mir::monomorphize::collector::collect_neighbours
   5: rustc_mir::monomorphize::collector::collect_items_rec
   6: rustc_session::utils::<impl rustc_session::session::Session>::time
   7: rustc_mir::monomorphize::collector::collect_crate_mono_items
   8: rustc_mir::monomorphize::partitioning::collect_and_partition_mono_items
   9: rustc_query_impl::<impl rustc_query_system::query::config::QueryAccessors<rustc_query_impl::plumbing::QueryCtxt> for rustc_query_impl::queries::collect_and_partition_mono_items>::compute
  10: rustc_middle::dep_graph::<impl rustc_query_system::dep_graph::DepKind for rustc_middle::dep_graph::dep_node::DepKind>::with_deps
  11: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task_impl
  12: rustc_data_structures::stack::ensure_sufficient_stack
  13: rustc_query_system::query::plumbing::force_query_with_job
  14: rustc_query_system::query::plumbing::get_query_impl
  15: <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::collect_and_partition_mono_items
  16: rustc_codegen_ssa::back::symbol_export::exported_symbols_provider_local
  17: rustc_middle::dep_graph::<impl rustc_query_system::dep_graph::DepKind for rustc_middle::dep_graph::dep_node::DepKind>::with_deps
  18: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task_impl
  19: rustc_data_structures::stack::ensure_sufficient_stack
  20: rustc_query_system::query::plumbing::force_query_with_job
  21: rustc_query_system::query::plumbing::get_query_impl
  22: <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::exported_symbols
  23: rustc_metadata::rmeta::encoder::EncodeContext::encode_crate_root
  24: rustc_metadata::rmeta::encoder::encode_metadata_impl
  25: rustc_data_structures::sync::join
  26: rustc_metadata::rmeta::decoder::cstore_impl::<impl rustc_middle::middle::cstore::CrateStore for rustc_metadata::creader::CStore>::encode_metadata
  27: rustc_middle::ty::context::TyCtxt::encode_metadata
  28: rustc_interface::passes::QueryContext::enter
  29: rustc_interface::queries::Queries::ongoing_codegen
  30: rustc_interface::queries::<impl rustc_interface::interface::Compiler>::enter
  31: rustc_span::with_source_map
  32: rustc_interface::interface::create_compiler_and_run
  33: scoped_tls::ScopedKey<T>::set
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/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.53.0-nightly (6df26f897 2021-04-20) running on x86_64-unknown-linux-gnu

note: compiler flags: -C embed-bitcode=no -C debuginfo=2 -C incremental --crate-type rlib --crate-type cdylib

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

query stack during panic:
#0 [collect_and_partition_mono_items] collect_and_partition_mono_items
#1 [exported_symbols] exported_symbols
end of query stack
error: internal compiler error: Encountered error `Unimplemented` selecting `Binder(<nalgebra::Matrix<f32, nalgebra::U4, nalgebra::U4, nalgebra::ArrayStorage<f32, nalgebra::U4, nalgebra::U4>> as JsBufferView>, [])` during codegen
  |
  = note: delayed at compiler/rustc_trait_selection/src/traits/codegen.rs:68:32

thread 'rustc' panicked at 'no errors encountered even though `delay_span_bug` issued', compiler/rustc_errors/src/lib.rs:1018:13
stack backtrace:
   0:     0x7ff5969ef320 - std::backtrace_rs::backtrace::libunwind::trace::hdcf4f90f85129e83
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/../../backtrace/src/backtrace/libunwind.rs:90:5
   1:     0x7ff5969ef320 - std::backtrace_rs::backtrace::trace_unsynchronized::h2669e30cb82f6732
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x7ff5969ef320 - std::sys_common::backtrace::_print_fmt::hfbda19e17f6db318
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/sys_common/backtrace.rs:67:5
   3:     0x7ff5969ef320 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h1a8751bf59281272
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/sys_common/backtrace.rs:46:22
   4:     0x7ff596a606df - core::fmt::write::h7aa6cd0067dca82a
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/core/src/fmt/mod.rs:1094:17
   5:     0x7ff5969e3be5 - std::io::Write::write_fmt::hd7dd3a1df9b6befb
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/io/mod.rs:1580:15
   6:     0x7ff5969f30cb - std::sys_common::backtrace::_print::h551e9ec8a9fa8106
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/sys_common/backtrace.rs:49:5
   7:     0x7ff5969f30cb - std::sys_common::backtrace::print::ha4b1c5e95fa040b3
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/sys_common/backtrace.rs:36:9
   8:     0x7ff5969f30cb - std::panicking::default_hook::{{closure}}::h0b34c9ab7fb9f857
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/panicking.rs:208:50
   9:     0x7ff5969f2bad - std::panicking::default_hook::h3067e8318decd17a
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/panicking.rs:225:9
  10:     0x7ff5971b53dd - rustc_driver::report_ice::h0582ed2432eb0d01
  11:     0x7ff5969f37e0 - std::panicking::rust_panic_with_hook::h81b8facc50f34daa
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/panicking.rs:595:17
  12:     0x7ff5969f33b7 - std::panicking::begin_panic_handler::{{closure}}::ha376ab85d95a000e
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/panicking.rs:497:13
  13:     0x7ff5969ef7dc - std::sys_common::backtrace::__rust_end_short_backtrace::h6795c8afdd1a77e6
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/sys_common/backtrace.rs:141:18
  14:     0x7ff5969f3319 - rust_begin_unwind
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/panicking.rs:493:5
  15:     0x7ff5969bf0db - std::panicking::begin_panic_fmt::hf43a0025042538e2
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/panicking.rs:435:5
  16:     0x7ff599639ac9 - rustc_errors::HandlerInner::flush_delayed::ha043eb844eec51b4
  17:     0x7ff5996385bb - <rustc_errors::HandlerInner as core::ops::drop::Drop>::drop::h20e6dc4c247e2972
  18:     0x7ff598cb0576 - core::ptr::drop_in_place<rustc_session::parse::ParseSess>::ha7b7bc007b685a43
  19:     0x7ff598cbee11 - <alloc::rc::Rc<T> as core::ops::drop::Drop>::drop::h0df1456cb7f7b3c5
  20:     0x7ff598ca52bd - core::ptr::drop_in_place<rustc_interface::interface::Compiler>::h4b05c244ac5fa340
  21:     0x7ff598ca4e94 - rustc_span::with_source_map::h67cb68e15a9ffc39
  22:     0x7ff598ca6a01 - rustc_interface::interface::create_compiler_and_run::he6a465670788f848
  23:     0x7ff598cc0188 - scoped_tls::ScopedKey<T>::set::h8de4c07d6e313e7a
  24:     0x7ff598cc06a3 - std::sys_common::backtrace::__rust_begin_short_backtrace::h953d4096b984a1d5
  25:     0x7ff598cc3f95 - core::ops::function::FnOnce::call_once{{vtable.shim}}::hf2d8af4e3cccbbb1
  26:     0x7ff596a035b7 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h3aa31cb6360b59d9
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/alloc/src/boxed.rs:1546:9
  27:     0x7ff596a035b7 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h7719d3c7c5841461
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/alloc/src/boxed.rs:1546:9
  28:     0x7ff596a035b7 - std::sys::unix::thread::Thread::new::thread_start::hfbe13ead469fd0bc
                               at /rustc/6df26f897cffb2d86880544bb451c6b5f8509b2d/library/std/src/sys/unix/thread.rs:71:17
  29:     0x7ff596917299 - start_thread
  30:     0x7ff59682c053 - clone
  31:                0x0 - <unknown>

error: internal compiler error: unexpected panic

[hameerabbasi]

Bisected:

********************************************************************************
Regression in nightly-2020-04-10
********************************************************************************

fetching https://static.rust-lang.org/dist/2020-04-09/channel-rust-nightly-git-commit-hash.txt
nightly manifest 2020-04-09: 40 B / 40 B [=================] 100.00 % 1.13 MB/s converted 2020-04-09 to 485c5fb6e1bf12cd11a8fac5ee94962e17cff74b
fetching https://static.rust-lang.org/dist/2020-04-10/channel-rust-nightly-git-commit-hash.txt
nightly manifest 2020-04-10: 40 B / 40 B [=================] 100.00 % 1.39 MB/s converted 2020-04-10 to 94d346360da50f159e0dc777dc9bc3c5b6b51a00
looking for regression commit between 2020-04-09 and 2020-04-10
cloning rust repository
fetching (via local git) commits from 485c5fb6e1bf12cd11a8fac5ee94962e17cff74b to 94d346360da50f159e0dc777dc9bc3c5b6b51a00
opening existing repository at "rust.git"
refreshing repository
looking up first commit
looking up second commit
checking that commits are by bors and thus have ci artifacts...
finding bors merge commits
found 6 bors merge commits in the specified range
  commit[0] 2020-04-08UTC: Auto merge of #70931 - Dylan-DPC:rollup-f8orcao, r=Dylan-DPC
  commit[1] 2020-04-08UTC: Auto merge of #70721 - anyska:bless-all-mir-opt, r=oli-obk
  commit[2] 2020-04-09UTC: Auto merge of #70936 - Dylan-DPC:rollup-2ng3e5h, r=Dylan-DPC
  commit[3] 2020-04-09UTC: Auto merge of #70860 - lcnr:has_local_value, r=nikomatsakis
  commit[4] 2020-04-09UTC: Auto merge of #70943 - Centril:rollup-eowm2h3, r=Centril
  commit[5] 2020-04-09UTC: Auto merge of #70960 - Centril:rollup-9vmokvw, r=Centril
ERROR: no commits between 485c5fb6e1bf12cd11a8fac5ee94962e17cff74b and 94d346360da50f159e0dc777dc9bc3c5b6b51a00 within last 167 days

[ehuss]

@farmaazon Thanks for the report and putting together the reproduction!

@hameerabbasi I think there may have been a mistake with bisecting. nalgebra 0.26 requires nightly-2021-01-09 at a minimum due to the use of the resolver field in Cargo.toml:

error: failed to download `nalgebra v0.26.1`

Caused by:
  unable to get packages from source

Caused by:
  failed to parse manifest at `/home/eric/.cargo/registry/src/github.com-1ecc6299db9ec823/nalgebra-0.26.1/Cargo.toml`

Caused by:
  feature `resolver` is required

  consider adding `cargo-features = ["resolver"]` to the manifest

Changing to nalgebra 0.25 I was able to reproduce the ICE in 1.47. nalgebra 0.25 does not build on earlier versions.

I think if you want to bisect further, someone will need to create a smaller reproduction that does not involve any dependencies.

[farmaazon]

I think if you want to bisect further, someone will need to create a smaller reproduction that does not involve any dependencies.

@ehuss Nalgebra 0.21.1 compiles on both old nightly (2019-11-03) and the stable and it still reproduce the bug.

[hameerabbasi]

Thanks for the pointers and sorry for the unnecessary ping. I've updated my bisection in #84399 (comment) based on the reproducer in #84399 (comment).

[SNCPlay42]

Reduced:

use std::marker::PhantomData;
pub trait Allocator<R> {
    type Buffer;
}
pub struct DefaultAllocator;
impl <R> Allocator<R> for DefaultAllocator {
    type Buffer = ();
}
pub type Owned<R> = <DefaultAllocator as Allocator<R>>::Buffer;
pub type MatrixMN<R> = Matrix<R, Owned<R>>;
pub type Matrix4<N> = Matrix<N, ()>;
pub struct Matrix<R, S> {
    pub data: S,
    _phantoms: PhantomData<R>,
}
pub fn set_object_transform(matrix: &Matrix4<()>) {
    matrix.js_buffer_view();
}
pub trait Storable {
    type Cell;
    fn slice_to_items(_buffer: &()) -> &[Self::Cell] {
        unimplemented!()
    }
}
pub type Cell<T> = <T as Storable>::Cell;
impl<R> Storable for MatrixMN<R>
where
    DefaultAllocator: Allocator<R>,
{
    type Cell = ();
}
pub trait JsBufferView {
    fn js_buffer_view(&self) -> usize {
        unimplemented!()
    }
}
impl<R> JsBufferView for [MatrixMN<R>]
where
    DefaultAllocator: Allocator<R>,
    MatrixMN<R>: Storable,
    [Cell<MatrixMN<R>>]: JsBufferView,
{
    fn js_buffer_view(&self) -> usize {
        <MatrixMN<R> as Storable>::slice_to_items(&()).js_buffer_view()
    }
}
impl JsBufferView for [()] {}
impl<R> JsBufferView for MatrixMN<R> where DefaultAllocator: Allocator<R> {}

---

Regression in nightly-2020-04-10

---

found 6 bors merge commits in the specified range
commit[0] 2020-04-08UTC: Auto merge of #70931 - Dylan-DPC:rollup-f8orcao, r=Dylan-DPC
commit[1] 2020-04-08UTC: Auto merge of #70721 - anyska:bless-all-mir-opt, r=oli-obk
commit[2] 2020-04-09UTC: Auto merge of #70936 - Dylan-DPC:rollup-2ng3e5h, r=Dylan-DPC
commit[3] 2020-04-09UTC: Auto merge of #70860 - lcnr:has_local_value, r=nikomatsakis
commit[4] 2020-04-09UTC: Auto merge of #70943 - Centril:rollup-eowm2h3, r=Centril
commit[5] 2020-04-09UTC: Auto merge of #70960 - Centril:rollup-9vmokvw, r=Centril
ERROR: no commits between 485c5fb and 94d3463 within last 167 days

[apiraino]

Assigning priority as discussed as part of the Prioritization Working Group procedure and removing I-prioritize.

@rustbot label -I-prioritize +P-medium

[wdanilo]

@apiraino thanks for the update. I've noticed that the assigned label is p-medium. Would you mind sharing any insights when approximately this could be fixed? I'm asking cause this bug prevents our codebase from updating to a new Rust compiler (in fact we are using an old version, which is not supported anymore because of trouble in updating it for the last months). The situation is even worse here, as even if we comment out this code, the same panic happens in other parts of our codebase.

[Aaron1011]

This is caused by the way that ParamEnv::and interacts with type freshening

In ParamEnv::and(), we throw away the caller_bounds if the value is 'global', and we're in Reveal::All:

rust/compiler/rustc_middle/src/ty/mod.rs

Lines 1205 to 1217 in cb81dc5

	pub fn and<T: TypeFoldable<'tcx>>(self, value: T) -> ParamEnvAnd<'tcx, T> {
	match self.reveal() {
	Reveal::UserFacing => ParamEnvAnd { param_env: self, value },
	Reveal::All => {
	if value.is_global() {
	ParamEnvAnd { param_env: self.without_caller_bounds(), value }
	} else {
	ParamEnvAnd { param_env: self, value }
	}
	}
	}
	}

When we're querying the selection candidate cache, we call ParamEnv::and with the 'freshened' trait predicate:

rust/compiler/rustc_trait_selection/src/traits/select/mod.rs

Lines 1077 to 1080 in cb81dc5

	let tcx = self.tcx();
	let trait_ref = &cache_fresh_trait_pred.skip_binder().trait_ref;
	if self.can_use_global_caches(param_env) {
	if let Some(res) = tcx.selection_cache.get(&param_env.and(*trait_ref), tcx) {

A 'freshened' predicate will have inference variables replaced with InferTy::FreshTy, which is not considered 'global'. However, our candidate may actually depend on the ParamEnv involved - for example, a ParamCandidate only makes sense when we have a ParamEnv with predicates involving a generic parameter. That's what's happening here - we're incorrectly re-using cached candidate with an inapplicable ParamEnv, resulting in a failure to select a predicate that should be guaranteed to succeed.

The behavior of ParamEnv::and seems quite subtle and error-prone. I think the simplest fix would be to restrict the discarding of caller_bounds to only 'obviously correct' cases without any inference variables or freshened types. If the performance hit due to reduced caching is too great, we can try to fix the call sites, or add something like ParamEnv::keep_caller_bounds_and that never discards caller_bounds.

[apiraino]

@Aaron1011 thanks for the overview, follow-up question for my full understanding: you are pointing to where the problem in rustc is, correct? Are there any implications about fixes/workarounds the issue reporter can apply to their code?
In other words, I'd like to understand if we should bump up the priority so the compiler team can watch it closer.

@wdanilo we generally assign a P-medium to non-critical issues (see our general guidance document). If an issue is caused by rustc and not an external library and it's blocking compliing working code, then we should re-evaluate.

[Aaron1011]

@apiraino: The bug is due to a caching issue deep in rustc, so there's essentially no way to predict whether or not a given change will trigger it. I'm working on a fix in #84472

[apiraino]

great @Aaron1011 thanks for the additional details and for working on a patch!

Updating priority accordingly
@rustbot label -P-medium +P-high

[Alexendoo]

Fixed by #84472