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 😅