ICE: solver coherence: 'called `Result::unwrap()` on an `Err` value: Sorts(ExpectedFound { expected: u32, found: u16 })'

[matthiaskrgr]

auto-reduced (treereduce-rust):

#![feature(specialization)] //~ WARN the feature `specialization` is incomplete

trait Assoc {
    type Output;
}

impl<T> Assoc for T {
    default 
}


impl Assoc for u16 { type Output = u16; }

trait Foo {}
impl Foo for u32 {}

impl Foo for <u16 as Assoc>::Output {}

original:

//@ check-pass

// Test that impls on projected self types can resolve overlap, even when the
// projections involve specialization, so long as the associated type is
// provided by the most specialized impl.

#![feature(specialization)] //~ WARN the feature `specialization` is incomplete

trait Assoc {
    type Output;
}

impl<T> Assoc for T {
    default type Output = bool;
}

impl Assoc for u8 { type Output = u8; }
impl Assoc for u16 { type Output = u16; }

trait Foo {}
impl Foo for u32 {}
impl Foo for <u8 as Assoc>::Output {}
impl Foo for <u16 as Assoc>::Output {}

fn main() {}

Version information

rustc 1.79.0-nightly (1b3a32958 2024-04-26)
binary: rustc
commit-hash: 1b3a32958bb54bde45e693217e8f7469459e5865
commit-date: 2024-04-26
host: x86_64-unknown-linux-gnu
release: 1.79.0-nightly
LLVM version: 18.1.4

Command:
/home/matthias/.rustup/toolchains/master/bin/rustc -Znext-solver=coherence

Program output

error: expected one of `!` or `::`, found `}`
  --> /tmp/icemaker_global_tempdir.VcNpYtiehp9n/rustc_testrunner_tmpdir_reporting.DaVMlM63CQKW/mvce.rs:15:1
   |
13 | impl<T> Assoc for T {
   |                     - while parsing this item list starting here
14 |     default 
   |            - expected one of `!` or `::`
15 | }
   | ^
   | |
   | unexpected token
   | the item list ends here

warning: the feature `specialization` is incomplete and may not be safe to use and/or cause compiler crashes
 --> /tmp/icemaker_global_tempdir.VcNpYtiehp9n/rustc_testrunner_tmpdir_reporting.DaVMlM63CQKW/mvce.rs:7:12
  |
7 | #![feature(specialization)] //~ WARN the feature `specialization` is incomplete
  |            ^^^^^^^^^^^^^^
  |
  = note: see issue #31844 <https://github.com/rust-lang/rust/issues/31844> for more information
  = help: consider using `min_specialization` instead, which is more stable and complete
  = note: `#[warn(incomplete_features)]` on by default

error[E0601]: `main` function not found in crate `mvce`
  --> /tmp/icemaker_global_tempdir.VcNpYtiehp9n/rustc_testrunner_tmpdir_reporting.DaVMlM63CQKW/mvce.rs:23:39
   |
23 | impl Foo for <u16 as Assoc>::Output {}
   |                                       ^ consider adding a `main` function to `/tmp/icemaker_global_tempdir.VcNpYtiehp9n/rustc_testrunner_tmpdir_reporting.DaVMlM63CQKW/mvce.rs`

error[E0046]: not all trait items implemented, missing: `Output`
  --> /tmp/icemaker_global_tempdir.VcNpYtiehp9n/rustc_testrunner_tmpdir_reporting.DaVMlM63CQKW/mvce.rs:13:1
   |
10 |     type Output;
   |     ----------- `Output` from trait
...
13 | impl<T> Assoc for T {
   | ^^^^^^^^^^^^^^^^^^^ missing `Output` in implementation

error[E0520]: `Output` specializes an item from a parent `impl`, but that item is not marked `default`
  --> /tmp/icemaker_global_tempdir.VcNpYtiehp9n/rustc_testrunner_tmpdir_reporting.DaVMlM63CQKW/mvce.rs:18:22
   |
13 | impl<T> Assoc for T {
   | ------------------- parent `impl` is here
...
18 | impl Assoc for u16 { type Output = u16; }
   |                      ^^^^^^^^^^^ cannot specialize default item `Output`
   |
   = note: to specialize, `Output` in the parent `impl` must be marked `default`

thread 'rustc' panicked at compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs:352:18:
called `Result::unwrap()` on an `Err` value: Sorts(ExpectedFound { expected: u32, found: u16 })
stack backtrace:
   0:     0x76f272ab6015 - std::backtrace_rs::backtrace::libunwind::trace::h4c55e2c372987d5e
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/../../backtrace/src/backtrace/libunwind.rs:105:5
   1:     0x76f272ab6015 - std::backtrace_rs::backtrace::trace_unsynchronized::hce938b03028abd04
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x76f272ab6015 - std::sys_common::backtrace::_print_fmt::h7224c4dd9bb24216
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/sys_common/backtrace.rs:68:5
   3:     0x76f272ab6015 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h90199bc1e9538393
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/sys_common/backtrace.rs:44:22
   4:     0x76f272b0527b - core::fmt::rt::Argument::fmt::h99091d315a9edc70
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/core/src/fmt/rt.rs:165:63
   5:     0x76f272b0527b - core::fmt::write::h957cfb08804d4951
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/core/src/fmt/mod.rs:1157:21
   6:     0x76f272aaac3f - std::io::Write::write_fmt::h403b2ebe17559453
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/io/mod.rs:1832:15
   7:     0x76f272ab5dee - std::sys_common::backtrace::_print::h32e8cdac40e53a67
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/sys_common/backtrace.rs:47:5
   8:     0x76f272ab5dee - std::sys_common::backtrace::print::h0fe3ded68e4b3f7a
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/sys_common/backtrace.rs:34:9
   9:     0x76f272ab8759 - std::panicking::default_hook::{{closure}}::hb64b24bf17e43a2c
  10:     0x76f272ab849d - std::panicking::default_hook::hf8b5abecad7ca8bf
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/panicking.rs:298:9
  11:     0x76f26f4326bc - std[cda2fed61da7e3aa]::panicking::update_hook::<alloc[3319e6d1a4cc4e17]::boxed::Box<rustc_driver_impl[37b3e731affd2934]::install_ice_hook::{closure#0}>>::{closure#0}
  12:     0x76f272ab8e56 - <alloc::boxed::Box<F,A> as core::ops::function::Fn<Args>>::call::h22c7123f3e8870f3
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/alloc/src/boxed.rs:2036:9
  13:     0x76f272ab8e56 - std::panicking::rust_panic_with_hook::ha6622cef7edeb437
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/panicking.rs:799:13
  14:     0x76f272ab8c04 - std::panicking::begin_panic_handler::{{closure}}::h4a88a108ee42ac5f
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/panicking.rs:664:13
  15:     0x76f272ab64d9 - std::sys_common::backtrace::__rust_end_short_backtrace::h99b2927289cdd120
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/sys_common/backtrace.rs:171:18
  16:     0x76f272ab8937 - rust_begin_unwind
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/panicking.rs:652:5
  17:     0x76f272b01743 - core::panicking::panic_fmt::h6753019afa32865b
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/core/src/panicking.rs:72:14
  18:     0x76f272b01d86 - core::result::unwrap_failed::h355d7b82293d1305
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/core/src/result.rs:1654:5
  19:     0x76f270d93278 - <rustc_trait_selection[4ae1fc89cbf26186]::solve::eval_ctxt::EvalCtxt>::unify_query_var_values
  20:     0x76f26ff70235 - <rustc_trait_selection[4ae1fc89cbf26186]::traits::coherence::AmbiguityCausesVisitor as rustc_trait_selection[4ae1fc89cbf26186]::solve::inspect::analyse::ProofTreeVisitor>::visit_goal
  21:     0x76f26ff707e3 - <rustc_trait_selection[4ae1fc89cbf26186]::traits::coherence::AmbiguityCausesVisitor as rustc_trait_selection[4ae1fc89cbf26186]::solve::inspect::analyse::ProofTreeVisitor>::visit_goal
  22:     0x76f270d943c4 - rustc_trait_selection[4ae1fc89cbf26186]::traits::coherence::overlap
  23:     0x76f2714d7d40 - <rustc_middle[d75d00d4f148731e]::traits::specialization_graph::Children as rustc_trait_selection[4ae1fc89cbf26186]::traits::specialize::specialization_graph::ChildrenExt>::insert
  24:     0x76f26e0d1218 - <rustc_middle[d75d00d4f148731e]::traits::specialization_graph::Graph as rustc_trait_selection[4ae1fc89cbf26186]::traits::specialize::specialization_graph::GraphExt>::insert
  25:     0x76f27088f4fc - rustc_trait_selection[4ae1fc89cbf26186]::traits::specialize::specialization_graph_provider
  26:     0x76f27088f05f - rustc_query_impl[9f33ac55070ec74]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[9f33ac55070ec74]::query_impl::specialization_graph_of::dynamic_query::{closure#2}::{closure#0}, rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 8usize]>>
  27:     0x76f270891a4e - rustc_query_system[f4e6670f65fd34a]::query::plumbing::try_execute_query::<rustc_query_impl[9f33ac55070ec74]::DynamicConfig<rustc_query_system[f4e6670f65fd34a]::query::caches::DefIdCache<rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 8usize]>>, false, false, false>, rustc_query_impl[9f33ac55070ec74]::plumbing::QueryCtxt, false>
  28:     0x76f270f64c74 - rustc_query_impl[9f33ac55070ec74]::query_impl::specialization_graph_of::get_query_non_incr::__rust_end_short_backtrace
  29:     0x76f270d2b170 - rustc_hir_analysis[63d5f7453e3e6b9f]::coherence::coherent_trait
  30:     0x76f270d2ae65 - rustc_query_impl[9f33ac55070ec74]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[9f33ac55070ec74]::query_impl::coherent_trait::dynamic_query::{closure#2}::{closure#0}, rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 1usize]>>
  31:     0x76f270b5bfd8 - rustc_query_system[f4e6670f65fd34a]::query::plumbing::try_execute_query::<rustc_query_impl[9f33ac55070ec74]::DynamicConfig<rustc_query_system[f4e6670f65fd34a]::query::caches::DefIdCache<rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 1usize]>>, false, false, false>, rustc_query_impl[9f33ac55070ec74]::plumbing::QueryCtxt, false>
  32:     0x76f270b5ac09 - rustc_query_impl[9f33ac55070ec74]::query_impl::coherent_trait::get_query_non_incr::__rust_end_short_backtrace
  33:     0x76f270eb4ea8 - rustc_hir_analysis[63d5f7453e3e6b9f]::check::wfcheck::check_well_formed
  34:     0x76f270eb2c6d - rustc_query_impl[9f33ac55070ec74]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[9f33ac55070ec74]::query_impl::check_well_formed::dynamic_query::{closure#2}::{closure#0}, rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 1usize]>>
  35:     0x76f270eb2400 - rustc_query_system[f4e6670f65fd34a]::query::plumbing::try_execute_query::<rustc_query_impl[9f33ac55070ec74]::DynamicConfig<rustc_query_system[f4e6670f65fd34a]::query::caches::VecCache<rustc_hir[b405c0b97a7e2b69]::hir_id::OwnerId, rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 1usize]>>, false, false, false>, rustc_query_impl[9f33ac55070ec74]::plumbing::QueryCtxt, false>
  36:     0x76f270eb217f - rustc_query_impl[9f33ac55070ec74]::query_impl::check_well_formed::get_query_non_incr::__rust_end_short_backtrace
  37:     0x76f270eb00f7 - rustc_hir_analysis[63d5f7453e3e6b9f]::check::wfcheck::check_mod_type_wf
  38:     0x76f270eaff27 - rustc_query_impl[9f33ac55070ec74]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[9f33ac55070ec74]::query_impl::check_mod_type_wf::dynamic_query::{closure#2}::{closure#0}, rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 1usize]>>
  39:     0x76f2715da0c6 - rustc_query_system[f4e6670f65fd34a]::query::plumbing::try_execute_query::<rustc_query_impl[9f33ac55070ec74]::DynamicConfig<rustc_query_system[f4e6670f65fd34a]::query::caches::DefaultCache<rustc_span[a27099297aeb4f84]::def_id::LocalModDefId, rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 1usize]>>, false, false, false>, rustc_query_impl[9f33ac55070ec74]::plumbing::QueryCtxt, false>
  40:     0x76f2715d9e7f - rustc_query_impl[9f33ac55070ec74]::query_impl::check_mod_type_wf::get_query_non_incr::__rust_end_short_backtrace
  41:     0x76f270b48e1b - rustc_hir_analysis[63d5f7453e3e6b9f]::check_crate
  42:     0x76f270b2ae87 - rustc_interface[2c0a8ee4ca531b31]::passes::analysis
  43:     0x76f270b2a9db - rustc_query_impl[9f33ac55070ec74]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[9f33ac55070ec74]::query_impl::analysis::dynamic_query::{closure#2}::{closure#0}, rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 1usize]>>
  44:     0x76f2715f35e5 - rustc_query_system[f4e6670f65fd34a]::query::plumbing::try_execute_query::<rustc_query_impl[9f33ac55070ec74]::DynamicConfig<rustc_query_system[f4e6670f65fd34a]::query::caches::SingleCache<rustc_middle[d75d00d4f148731e]::query::erase::Erased<[u8; 1usize]>>, false, false, false>, rustc_query_impl[9f33ac55070ec74]::plumbing::QueryCtxt, false>
  45:     0x76f2715f3349 - rustc_query_impl[9f33ac55070ec74]::query_impl::analysis::get_query_non_incr::__rust_end_short_backtrace
  46:     0x76f27145210e - rustc_interface[2c0a8ee4ca531b31]::interface::run_compiler::<core[1844992cd7eaeb93]::result::Result<(), rustc_span[a27099297aeb4f84]::ErrorGuaranteed>, rustc_driver_impl[37b3e731affd2934]::run_compiler::{closure#0}>::{closure#1}
  47:     0x76f27143eb09 - std[cda2fed61da7e3aa]::sys_common::backtrace::__rust_begin_short_backtrace::<rustc_interface[2c0a8ee4ca531b31]::util::run_in_thread_with_globals<rustc_interface[2c0a8ee4ca531b31]::util::run_in_thread_pool_with_globals<rustc_interface[2c0a8ee4ca531b31]::interface::run_compiler<core[1844992cd7eaeb93]::result::Result<(), rustc_span[a27099297aeb4f84]::ErrorGuaranteed>, rustc_driver_impl[37b3e731affd2934]::run_compiler::{closure#0}>::{closure#1}, core[1844992cd7eaeb93]::result::Result<(), rustc_span[a27099297aeb4f84]::ErrorGuaranteed>>::{closure#0}, core[1844992cd7eaeb93]::result::Result<(), rustc_span[a27099297aeb4f84]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[1844992cd7eaeb93]::result::Result<(), rustc_span[a27099297aeb4f84]::ErrorGuaranteed>>
  48:     0x76f27143e8ba - <<std[cda2fed61da7e3aa]::thread::Builder>::spawn_unchecked_<rustc_interface[2c0a8ee4ca531b31]::util::run_in_thread_with_globals<rustc_interface[2c0a8ee4ca531b31]::util::run_in_thread_pool_with_globals<rustc_interface[2c0a8ee4ca531b31]::interface::run_compiler<core[1844992cd7eaeb93]::result::Result<(), rustc_span[a27099297aeb4f84]::ErrorGuaranteed>, rustc_driver_impl[37b3e731affd2934]::run_compiler::{closure#0}>::{closure#1}, core[1844992cd7eaeb93]::result::Result<(), rustc_span[a27099297aeb4f84]::ErrorGuaranteed>>::{closure#0}, core[1844992cd7eaeb93]::result::Result<(), rustc_span[a27099297aeb4f84]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[1844992cd7eaeb93]::result::Result<(), rustc_span[a27099297aeb4f84]::ErrorGuaranteed>>::{closure#2} as core[1844992cd7eaeb93]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0}
  49:     0x76f272ac2c8b - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::hfbef881afe54fc64
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/alloc/src/boxed.rs:2022:9
  50:     0x76f272ac2c8b - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h248e9437ec3cc6be
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/alloc/src/boxed.rs:2022:9
  51:     0x76f272ac2c8b - std::sys::pal::unix::thread::Thread::new::thread_start::h8f5142e9cff5a60d
                               at /rustc/1b3a32958bb54bde45e693217e8f7469459e5865/library/std/src/sys/pal/unix/thread.rs:108:17
  52:     0x76f26c2a955a - <unknown>
  53:     0x76f26c326a3c - <unknown>
  54:                0x0 - <unknown>

error: 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: please make sure that you have updated to the latest nightly

note: rustc 1.79.0-nightly (1b3a32958 2024-04-26) running on x86_64-unknown-linux-gnu

note: compiler flags: -Z next-solver=coherence -Z dump-mir-dir=dir

query stack during panic:
#0 [specialization_graph_of] building specialization graph of trait `Foo`
#1 [coherent_trait] coherence checking all impls of trait `Foo`
#2 [check_well_formed] checking that `<impl at /tmp/icemaker_global_tempdir.VcNpYtiehp9n/rustc_testrunner_tmpdir_reporting.DaVMlM63CQKW/mvce.rs:21:1: 21:17>` is well-formed
#3 [check_mod_type_wf] checking that types are well-formed in top-level module
#4 [analysis] running analysis passes on this crate
end of query stack
error: aborting due to 4 previous errors; 1 warning emitted

Some errors have detailed explanations: E0046, E0520, E0601.
For more information about an error, try `rustc --explain E0046`.

@rustbot label +F-specialization

[matthiaskrgr]

#122385 fyi @lcnr

[matthiaskrgr]

There is also a ProofTreeVisitor issue causing an ICE when compiling alloc which I will handle in a separate PR.

this is probably the same problem here.
When compiling ./library/alloc/src/lib.rs" with 2021, we run into Sorts(ExpectedFound { expected: string::String, found: str }) but I have not bothered trying to reduce that 😅

[lqd]

The original code already produces that ICE (so I guess that via specialization-overlap-projection.rs this is already a known issue?), and is a check-pass test. In these situations, your reduction procedure could just check that the flag is the cause of the error first, and then minimize the code.

That is, instead of reducing with a condition like rustc code.rs -Znext-solver=coherence &| grep ICE, using a condition like rustc code.rs && rustc code -Znext-solver=coherence &| grep ICE.

This would keep the *-pass property, and fuzz deeper within rustc by not being limited by unrelated basic syntax errors in general. I mean, unless you're fuzzing diagnostics or failure paths in particular for *-fail tests, which is useful in its own right. Otherwise, the procedure still has a bias towards that, but it's not intentional, and coverage is reduced.

#![feature(specialization)]

trait Assoc {
    type Output;
}

impl<T> Assoc for T {
    default type Output = bool;
}

impl Assoc for u16 { type Output = u16; }

trait Foo {}
impl Foo for u32 {}
impl Foo for <u16 as Assoc>::Output {}

fn main() {}

[matthiaskrgr]

There is no fuzzing involved here.
The ICE was detected on the original straight form the rustc repo and the responsible compiler flag was found (all unrelated compiler flags are dismissed).
Then with the reduced set of flags, I run https://github.com/langston-barrett/treereduce to automatically reduce the file, as long as the ice still triggers with the reduced set of flags and this becomes reduced snippet from which I generate the markdown report.

[lqd]

Right I'm saying this can be suboptimal as it introduces new unrelated errors. It turned something that worked without the flag and ICEd with it, into something that fails without the flag and still ICEs with the flag. This can be prevented during reduction.

The reduced snippet would have to be fixed to remove the unrelated errors when fixing the ICE, or worse it could be ignored in favor of the original unreduced piece of code.