ICE: `When translating generic parameters from `..` to `..`, the expected specialization failed to hold`

[matthiaskrgr]

auto-reduced (treereduce-rust):

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

trait Assoc {
    type Output;
}

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

impl Assoc for u8 {}

trait Foo {}

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

original:

// run-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;
}

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

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

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

fn main() {}

Version information

rustc 1.76.0-nightly (d253bf61a 2023-12-15)
binary: rustc
commit-hash: d253bf61ad38a59cc579aee688f81a06c31283d3
commit-date: 2023-12-15
host: x86_64-unknown-linux-gnu
release: 1.76.0-nightly
LLVM version: 17.0.6

Command:
/home/matthias/.rustup/toolchains/master/bin/rustc

Program output

warning: the feature `specialization` is incomplete and may not be safe to use and/or cause compiler crashes
 --> /tmp/icemaker_global_tempdir.YmODNJIFWMvh/rustc_testrunner_tmpdir_reporting.mIkKiuxcepa6/mvce.rs:1:12
  |
1 | #![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.YmODNJIFWMvh/rustc_testrunner_tmpdir_reporting.mIkKiuxcepa6/mvce.rs:16:39
   |
16 | impl Foo for <u16 as Assoc>::Output {}
   |                                       ^ consider adding a `main` function to `/tmp/icemaker_global_tempdir.YmODNJIFWMvh/rustc_testrunner_tmpdir_reporting.mIkKiuxcepa6/mvce.rs`

error: internal compiler error: compiler/rustc_trait_selection/src/traits/specialize/mod.rs:123:21: When translating substitutions from DefId(0:8 ~ mvce[0e9d]::{impl#1}) to DefId(0:5 ~ mvce[0e9d]::{impl#0}), the expected specialization failed to hold

thread 'rustc' panicked at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/compiler/rustc_errors/src/lib.rs:1119:75:
Box<dyn Any>
stack backtrace:
   0:     0x7f146c02d45c - std::backtrace_rs::backtrace::libunwind::trace::hd6103882acf895e3
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/../../backtrace/src/backtrace/libunwind.rs:104:5
   1:     0x7f146c02d45c - std::backtrace_rs::backtrace::trace_unsynchronized::h8bf8e05e9006d12a
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x7f146c02d45c - std::sys_common::backtrace::_print_fmt::h40fa413ec9439832
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/sys_common/backtrace.rs:68:5
   3:     0x7f146c02d45c - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h5055b8322c3eecd3
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/sys_common/backtrace.rs:44:22
   4:     0x7f146c080510 - core::fmt::rt::Argument::fmt::h142c2cad35d6896a
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/core/src/fmt/rt.rs:142:9
   5:     0x7f146c080510 - core::fmt::write::hd72f8a00b68449f5
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/core/src/fmt/mod.rs:1120:17
   6:     0x7f146c0212bf - std::io::Write::write_fmt::h1bcd670a0cd9a7ff
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/io/mod.rs:1810:15
   7:     0x7f146c02d244 - std::sys_common::backtrace::_print::h579af4e2f431a26b
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/sys_common/backtrace.rs:47:5
   8:     0x7f146c02d244 - std::sys_common::backtrace::print::hdb76c2f48b3f9ac2
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/sys_common/backtrace.rs:34:9
   9:     0x7f146c02ff47 - std::panicking::default_hook::{{closure}}::hb2313c1cb20e0e8d
  10:     0x7f146c02fcaf - std::panicking::default_hook::h0c0e9cb7313537d7
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/panicking.rs:292:9
  11:     0x7f1468d3f330 - std[90fcdab509e9b154]::panicking::update_hook::<alloc[197ac5e7db877155]::boxed::Box<rustc_driver_impl[c59161498cce3c44]::install_ice_hook::{closure#0}>>::{closure#0}
  12:     0x7f146c030688 - <alloc::boxed::Box<F,A> as core::ops::function::Fn<Args>>::call::h0f5771c93d1f75ce
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/alloc/src/boxed.rs:2029:9
  13:     0x7f146c030688 - std::panicking::rust_panic_with_hook::h4edda63d730d17fc
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/panicking.rs:783:13
  14:     0x7f1468d773b4 - std[90fcdab509e9b154]::panicking::begin_panic::<rustc_errors[b8d39b1188f581a8]::ExplicitBug>::{closure#0}
  15:     0x7f1468d73846 - std[90fcdab509e9b154]::sys_common::backtrace::__rust_end_short_backtrace::<std[90fcdab509e9b154]::panicking::begin_panic<rustc_errors[b8d39b1188f581a8]::ExplicitBug>::{closure#0}, !>
  16:     0x7f1468d6eea6 - std[90fcdab509e9b154]::panicking::begin_panic::<rustc_errors[b8d39b1188f581a8]::ExplicitBug>
  17:     0x7f1468d82558 - <rustc_errors[b8d39b1188f581a8]::diagnostic_builder::Bug as rustc_errors[b8d39b1188f581a8]::diagnostic_builder::EmissionGuarantee>::diagnostic_builder_emit_producing_guarantee
  18:     0x7f1469163a15 - <rustc_errors[b8d39b1188f581a8]::Handler>::bug::<alloc[197ac5e7db877155]::string::String>
  19:     0x7f14691fe5fd - rustc_middle[17eaf787359ec706]::util::bug::opt_span_bug_fmt::<rustc_span[9c405c0df40bde1a]::span_encoding::Span>::{closure#0}
  20:     0x7f14691e7f0a - rustc_middle[17eaf787359ec706]::ty::context::tls::with_opt::<rustc_middle[17eaf787359ec706]::util::bug::opt_span_bug_fmt<rustc_span[9c405c0df40bde1a]::span_encoding::Span>::{closure#0}, !>::{closure#0}
  21:     0x7f14691e7d88 - rustc_middle[17eaf787359ec706]::ty::context::tls::with_context_opt::<rustc_middle[17eaf787359ec706]::ty::context::tls::with_opt<rustc_middle[17eaf787359ec706]::util::bug::opt_span_bug_fmt<rustc_span[9c405c0df40bde1a]::span_encoding::Span>::{closure#0}, !>::{closure#0}, !>
  22:     0x7f146715b670 - rustc_middle[17eaf787359ec706]::util::bug::bug_fmt
  23:     0x7f146a3b9f90 - rustc_trait_selection[2323e8e34cf002d2]::traits::specialize::translate_args_with_cause::<rustc_trait_selection[2323e8e34cf002d2]::traits::specialize::translate_args::{closure#0}>
  24:     0x7f146a2a9347 - rustc_trait_selection[2323e8e34cf002d2]::traits::project::opt_normalize_projection_type
  25:     0x7f146a2a5f9e - <rustc_trait_selection[2323e8e34cf002d2]::traits::project::AssocTypeNormalizer as rustc_type_ir[f2235eff04baa55d]::fold::TypeFolder<rustc_middle[17eaf787359ec706]::ty::context::TyCtxt>>::fold_ty
  26:     0x7f146a95b95c - rustc_trait_selection[2323e8e34cf002d2]::traits::project::normalize_with_depth_to::<rustc_middle[17eaf787359ec706]::ty::ImplHeader>::{closure#0}
  27:     0x7f146a95ae43 - rustc_trait_selection[2323e8e34cf002d2]::traits::coherence::fresh_impl_header_normalized
  28:     0x7f146a959108 - rustc_trait_selection[2323e8e34cf002d2]::traits::coherence::overlap
  29:     0x7f146a76e9f3 - <rustc_middle[17eaf787359ec706]::traits::specialization_graph::Children as rustc_trait_selection[2323e8e34cf002d2]::traits::specialize::specialization_graph::ChildrenExt>::insert
  30:     0x7f146a76e07b - <rustc_middle[17eaf787359ec706]::traits::specialization_graph::Graph as rustc_trait_selection[2323e8e34cf002d2]::traits::specialize::specialization_graph::GraphExt>::insert
  31:     0x7f146aaa6d8a - rustc_trait_selection[2323e8e34cf002d2]::traits::specialize::specialization_graph_provider
  32:     0x7f146aaa67b2 - rustc_query_impl[43baca739a647e2b]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[43baca739a647e2b]::query_impl::specialization_graph_of::dynamic_query::{closure#2}::{closure#0}, rustc_middle[17eaf787359ec706]::query::erase::Erased<[u8; 8usize]>>
  33:     0x7f146a0811d4 - rustc_query_system[f7d04bba5a359203]::query::plumbing::try_execute_query::<rustc_query_impl[43baca739a647e2b]::DynamicConfig<rustc_query_system[f7d04bba5a359203]::query::caches::DefaultCache<rustc_span[9c405c0df40bde1a]::def_id::DefId, rustc_middle[17eaf787359ec706]::query::erase::Erased<[u8; 8usize]>>, false, false, false>, rustc_query_impl[43baca739a647e2b]::plumbing::QueryCtxt, false>
  34:     0x7f146a4220de - rustc_query_impl[43baca739a647e2b]::query_impl::specialization_graph_of::get_query_non_incr::__rust_end_short_backtrace
  35:     0x7f146a1ec291 - rustc_hir_analysis[521878d46db95bb1]::coherence::coherent_trait
  36:     0x7f146a1ec16f - rustc_query_impl[43baca739a647e2b]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[43baca739a647e2b]::query_impl::coherent_trait::dynamic_query::{closure#2}::{closure#0}, rustc_middle[17eaf787359ec706]::query::erase::Erased<[u8; 0usize]>>
  37:     0x7f146a9832fd - rustc_query_system[f7d04bba5a359203]::query::plumbing::try_execute_query::<rustc_query_impl[43baca739a647e2b]::DynamicConfig<rustc_query_system[f7d04bba5a359203]::query::caches::DefaultCache<rustc_span[9c405c0df40bde1a]::def_id::DefId, rustc_middle[17eaf787359ec706]::query::erase::Erased<[u8; 0usize]>>, false, false, false>, rustc_query_impl[43baca739a647e2b]::plumbing::QueryCtxt, false>
  38:     0x7f146a98308d - rustc_query_impl[43baca739a647e2b]::query_impl::coherent_trait::get_query_non_incr::__rust_end_short_backtrace
  39:     0x7f146a96e7aa - rustc_hir_analysis[521878d46db95bb1]::check_crate
  40:     0x7f146aab0117 - rustc_interface[1819133c53e350af]::passes::analysis
  41:     0x7f146aaafd5d - rustc_query_impl[43baca739a647e2b]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[43baca739a647e2b]::query_impl::analysis::dynamic_query::{closure#2}::{closure#0}, rustc_middle[17eaf787359ec706]::query::erase::Erased<[u8; 1usize]>>
  42:     0x7f146afa9ff2 - rustc_query_system[f7d04bba5a359203]::query::plumbing::try_execute_query::<rustc_query_impl[43baca739a647e2b]::DynamicConfig<rustc_query_system[f7d04bba5a359203]::query::caches::SingleCache<rustc_middle[17eaf787359ec706]::query::erase::Erased<[u8; 1usize]>>, false, false, false>, rustc_query_impl[43baca739a647e2b]::plumbing::QueryCtxt, false>
  43:     0x7f146afa9df9 - rustc_query_impl[43baca739a647e2b]::query_impl::analysis::get_query_non_incr::__rust_end_short_backtrace
  44:     0x7f146b045e97 - rustc_interface[1819133c53e350af]::interface::run_compiler::<core[ea5c17b9bf3f7e3c]::result::Result<(), rustc_span[9c405c0df40bde1a]::ErrorGuaranteed>, rustc_driver_impl[c59161498cce3c44]::run_compiler::{closure#0}>::{closure#0}
  45:     0x7f146afbceda - std[90fcdab509e9b154]::sys_common::backtrace::__rust_begin_short_backtrace::<rustc_interface[1819133c53e350af]::util::run_in_thread_with_globals<rustc_interface[1819133c53e350af]::util::run_in_thread_pool_with_globals<rustc_interface[1819133c53e350af]::interface::run_compiler<core[ea5c17b9bf3f7e3c]::result::Result<(), rustc_span[9c405c0df40bde1a]::ErrorGuaranteed>, rustc_driver_impl[c59161498cce3c44]::run_compiler::{closure#0}>::{closure#0}, core[ea5c17b9bf3f7e3c]::result::Result<(), rustc_span[9c405c0df40bde1a]::ErrorGuaranteed>>::{closure#0}, core[ea5c17b9bf3f7e3c]::result::Result<(), rustc_span[9c405c0df40bde1a]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[ea5c17b9bf3f7e3c]::result::Result<(), rustc_span[9c405c0df40bde1a]::ErrorGuaranteed>>
  46:     0x7f146afbcd03 - <<std[90fcdab509e9b154]::thread::Builder>::spawn_unchecked_<rustc_interface[1819133c53e350af]::util::run_in_thread_with_globals<rustc_interface[1819133c53e350af]::util::run_in_thread_pool_with_globals<rustc_interface[1819133c53e350af]::interface::run_compiler<core[ea5c17b9bf3f7e3c]::result::Result<(), rustc_span[9c405c0df40bde1a]::ErrorGuaranteed>, rustc_driver_impl[c59161498cce3c44]::run_compiler::{closure#0}>::{closure#0}, core[ea5c17b9bf3f7e3c]::result::Result<(), rustc_span[9c405c0df40bde1a]::ErrorGuaranteed>>::{closure#0}, core[ea5c17b9bf3f7e3c]::result::Result<(), rustc_span[9c405c0df40bde1a]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[ea5c17b9bf3f7e3c]::result::Result<(), rustc_span[9c405c0df40bde1a]::ErrorGuaranteed>>::{closure#1} as core[ea5c17b9bf3f7e3c]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0}
  47:     0x7f146c03a515 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h9895702b6be34956
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/alloc/src/boxed.rs:2015:9
  48:     0x7f146c03a515 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::hbd2c76ba009df5db
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/alloc/src/boxed.rs:2015:9
  49:     0x7f146c03a515 - std::sys::unix::thread::Thread::new::thread_start::h8bdfca0a04fd1f70
                               at /rustc/d253bf61ad38a59cc579aee688f81a06c31283d3/library/std/src/sys/unix/thread.rs:108:17
  50:     0x7f1465eaa9eb - <unknown>
  51:     0x7f1465f2e7cc - <unknown>
  52:                0x0 - <unknown>

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.76.0-nightly (d253bf61a 2023-12-15) running on x86_64-unknown-linux-gnu

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 [analysis] running analysis passes on this crate
end of query stack
error: aborting due to 2 previous errors; 1 warning emitted

For more information about this error, try `rustc --explain E0601`.

[compiler-errors]

Minimal:

#![feature(specialization)]
#![allow(incomplete_features)]

trait Assoc {
    type Output;
}

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

impl Assoc for u8 {}

trait Foo {}

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

fn main() {}

What the HECK

[compiler-errors]

Oh, lol. This is because we can't select <u8 as Clone> during subst rebasing because it's an unknowable trait ref. Lol.