ICE: "failed to resolve instance for type", apparently caused by generic parameter inference

[Yokinman]

Code

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=c29a73a6b88b2ef3d327766daee94e1d

This example is a little large (213 lines), but it's also an error I can work around pretty easily so I'm not too worried about it.

To fix it, it seems like you can just change the impl at line 88,

impl<const A: usize, const B: usize, O> VarCmp<Var<B>> for Var<A>
where
    Const<A>: ToUInt,
    Const<B>: ToUInt,
    U<A>: Cmp<U<B>, Output=O>,
{
    type Output = O;
}

to use a more explicit path:

impl<const A: usize, const B: usize> VarCmp<Var<B>> for Var<A>
where
    Const<A>: ToUInt,
    Const<B>: ToUInt,
    U<A>: Cmp<U<B>>,
{
    type Output = <U<A> as Cmp<U<B>>>::Output;
}

(Fixed version: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=748b532ef879333714976bf96b904fcd)

For reference, this system is meant to order & group Var<N> types (e.g. Var<0> + Var<1> + Var<0> -> Sum<Sum<Var<0>, Var<0>>, Var<1>>).

Meta

rustc --version --verbose:

rustc 1.84.0 (9fc6b4312 2025-01-07)
binary: rustc
commit-hash: 9fc6b43126469e3858e2fe86cafb4f0fd5068869
commit-date: 2025-01-07
host: x86_64-pc-windows-msvc
release: 1.84.0
LLVM version: 19.1.5

This error also occurred in 1.83.0 stable, but updating to 1.84.0 didn't seem to change anything.

Error output

error: internal compiler error: compiler\rustc_middle\src\ty\instance.rs:581:21: failed to resolve instance for <Sum<Sum<Var<0>, Var<0>>, Sum<Sum<Var<1>, Sum<Var<1>, Var<1>>>, Sum<Var<2>, Var<2>>>> as Add<Sum<Var<0>, Sum<Sum<Var<1>, Var<1>>, Var<2>>>>>::add   
   --> src\lib.rs:212:23
    |
212 |     assert_eq!(y + z, z + y);
    |                       ^^^^^

thread 'rustc' panicked at compiler\rustc_middle\src\ty\instance.rs:581:21:
Box<dyn Any>

Backtrace

stack backtrace:
   0:     0x7ffa23abba41 - std::backtrace_rs::backtrace::dbghelp64::trace
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\..\..\backtrace\src\backtrace\dbghelp64.rs:91
   1:     0x7ffa23abba41 - std::backtrace_rs::backtrace::trace_unsynchronized
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\..\..\backtrace\src\backtrace\mod.rs:66
   2:     0x7ffa23abba41 - std::sys::backtrace::_print_fmt
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\sys\backtrace.rs:66
   3:     0x7ffa23abba41 - std::sys::backtrace::impl$0::print::impl$0::fmt
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\sys\backtrace.rs:39
   4:     0x7ffa23aedd1a - core::fmt::rt::Argument::fmt
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/core\src\fmt\rt.rs:177
   5:     0x7ffa23aedd1a - core::fmt::write
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/core\src\fmt\mod.rs:1189
   6:     0x7ffa23ab1de7 - std::io::Write::write_fmt<std::sys::pal::windows::stdio::Stderr>
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\io\mod.rs:1884
   7:     0x7ffa23abb885 - std::sys::backtrace::BacktraceLock::print
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\sys\backtrace.rs:42
   8:     0x7ffa23abe7a3 - std::panicking::default_hook::closure$1
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\panicking.rs:268
   9:     0x7ffa23abe582 - std::panicking::default_hook
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\panicking.rs:295
  10:     0x7ffa2509ab1e - strncpy
  11:     0x7ffa23abeee2 - alloc::boxed::impl$30::call
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/alloc\src\boxed.rs:1986
  12:     0x7ffa23abeee2 - std::panicking::rust_panic_with_hook
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\panicking.rs:809
  13:     0x7ffa2688b993 - <rustc_hir_pretty[ab0fe6e31331acdd]::State>::print_variant
  14:     0x7ffa2687d999 - <rustc_hir_pretty[ab0fe6e31331acdd]::State>::print_variant
  15:     0x7ffa2687d958 - <rustc_hir_pretty[ab0fe6e31331acdd]::State>::print_variant
  16:     0x7ffa268993c5 - <rustc_errors[3bd8408db383e9c9]::diagnostic::BugAbort as rustc_errors[3bd8408db383e9c9]::diagnostic::EmissionGuarantee>::emit_producing_guarantee
  17:     0x7ffa266ee57f - ar_archive_writer[5ad4fe434effa9d8]::object_reader::get_member_alignment
  18:     0x7ffa267a0f36 - rustc_middle[87d6ac0499a2eaf7]::util::bug::bug_fmt
  19:     0x7ffa267818bd - <rustc_middle[87d6ac0499a2eaf7]::ty::consts::Const>::to_valtree
  20:     0x7ffa267816d6 - <rustc_middle[87d6ac0499a2eaf7]::ty::consts::Const>::to_valtree
  21:     0x7ffa267a0e69 - rustc_middle[87d6ac0499a2eaf7]::util::bug::bug_fmt
  22:     0x7ffa24ee608c - <rustc_middle[87d6ac0499a2eaf7]::ty::instance::Instance>::expect_resolve
  23:     0x7ffa23e6c637 - <rustc_monomorphize[85a23766e536164]::collector::MirUsedCollector as rustc_middle[87d6ac0499a2eaf7]::mir::visit::Visitor>::visit_terminator
  24:     0x7ffa23e770a9 - rustc_monomorphize[85a23766e536164]::collector::items_of_instance
  25:     0x7ffa24840ee7 - rustc_query_impl[8be1416e77d742ed]::plumbing::query_key_hash_verify_all
  26:     0x7ffa247784db - rustc_ty_utils[4902e6e6aecd2893]::ty::self_ty_of_trait_impl_enabling_order_dep_trait_object_hack
  27:     0x7ffa24853bed - rustc_query_impl[8be1416e77d742ed]::plumbing::query_key_hash_verify_all
  28:     0x7ffa23e997f4 - rustc_monomorphize[85a23766e536164]::polymorphize::unused_generic_params
  29:     0x7ffa23e96624 - rustc_monomorphize[85a23766e536164]::polymorphize::unused_generic_params
  30:     0x7ffa23e96f82 - rustc_monomorphize[85a23766e536164]::polymorphize::unused_generic_params
  31:     0x7ffa23e96f82 - rustc_monomorphize[85a23766e536164]::polymorphize::unused_generic_params
  32:     0x7ffa23e8d616 - rustc_monomorphize[85a23766e536164]::partitioning::collect_and_partition_mono_items
  33:     0x7ffa236b8007 - rustc_ty_utils[4902e6e6aecd2893]::ty::adt_sized_constraint
  34:     0x7ffa2369e9fd - rustc_ty_utils[4902e6e6aecd2893]::ty::adt_sized_constraint
  35:     0x7ffa235c568f - rustc_ty_utils[4902e6e6aecd2893]::ty::adt_sized_constraint
  36:     0x7ffa236dd2ee - rustc_query_impl[8be1416e77d742ed]::query_system
  37:     0x7ffa20bb29bb - <rustc_codegen_llvm[85ae7dac9399dd6b]::LlvmCodegenBackend as rustc_codegen_ssa[ce0820b527006769]::traits::backend::CodegenBackend>::codegen_crate
  38:     0x7ffa20b13073 - <rustc_interface[c014954558e9d384]::queries::Linker>::codegen_and_build_linker
  39:     0x7ffa20ac74bd - _rust_alloc_error_handler
  40:     0x7ffa20ac2fcf - _rust_alloc_error_handler
  41:     0x7ffa20accfc5 - _rust_alloc_error_handler
  42:     0x7ffa23ad0bad - alloc::boxed::impl$28::call_once
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/alloc\src\boxed.rs:1972
  43:     0x7ffa23ad0bad - alloc::boxed::impl$28::call_once
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/alloc\src\boxed.rs:1972
  44:     0x7ffa23ad0bad - std::sys::pal::windows::thread::impl$0::new::thread_start
                               at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\sys\pal\windows\thread.rs:55
  45:     0x7ffa9f687374 - BaseThreadInitThunk
  46:     0x7ffaa03bcc91 - RtlUserThreadStart

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.84.0 (9fc6b4312 2025-01-07) running on x86_64-pc-windows-msvc

note: compiler flags: -C embed-bitcode=no -C debuginfo=2 -C incremental=[REDACTED]

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

query stack during panic:
#0 [items_of_instance] collecting items used by `test`
#1 [collect_and_partition_mono_items] collect_and_partition_mono_items
end of query stack

[cyrgani]

reduction:

struct Equal;

struct Bar;

trait TwiceNested {}
impl<M> TwiceNested for Bar where Bar: NestMakeEqual<NestEq = M> {}

struct Sum;

trait Not {
    fn not();
}

impl<P> Not for Sum
where
    Bar: NestMakeEqual<NestEq = P>,
    Self: Problem<P>,
{
    fn not() {}
}

trait NestMakeEqual {
    type NestEq;
}

trait MakeEqual {
    type Eq;
}

struct Foo;
impl MakeEqual for Foo {
    type Eq = Equal;
}

impl<O> NestMakeEqual for Bar
where
    Foo: MakeEqual<Eq = O>,
{
    type NestEq = O;
}

trait Problem<M> {}
impl Problem<()> for Sum where Bar: TwiceNested {}
impl Problem<Equal> for Sum where Bar: TwiceNested {}

fn main() {
    Sum::not();
}

@rustbot label:-E-needs-mcve

[cyrgani]

According to cargo-bisect-rustc, this was a regression in nightly-2017-07-08 (compiled fine before that).

[cyrgani]

With the next solver, this doesn't ICE, but it does not compile either (I think this is a bug too):

error[E0284]: type annotations needed: cannot normalize `<Bar as NestMakeEqual>::NestEq`
  --> src/main.rs:14:17
   |
14 | impl<P> Not for Sum
   |                 ^^^ cannot normalize `<Bar as NestMakeEqual>::NestEq`
   |
note: required for `Sum` to implement `Not`
  --> src/main.rs:14:9
   |
14 | impl<P> Not for Sum
   |         ^^^     ^^^
15 | where
16 |     Bar: NestMakeEqual<NestEq = P>,
   |                        ---------- unsatisfied trait bound introduced here