Repository: rust
Issue: ICE: `collection encountered polymorphic constant: Ty(..)`
Labels: I-ICE,T-compiler,C-bug,E-needs-mcve,F-generic_const_exprs,S-bug-has-test

<!--
[31mICE[0m: Rustc ./ice.rs '' 'error: internal compiler error: compiler/rustc_monomorphize/src/collector.rs:703:50: collection encountered polymorphic constant: Ty(usize, (Add: (1_usize: usize), (1_usize: usize)))', 'error: internal compiler error: compiler/rustc_monomorphize/src/collector.rs:703:50: collection encountered polymorphic constant: Ty(usize, (Add: (1_usize: usize), (1_usize: usize)))'
File: /tmp/im/ice.rs
-->

auto-reduced (treereduce-rust):
````rust
#![feature(generic_const_exprs)]

use std::array;

trait PrimRec<const N: usize, const O: usize> {
    fn eval(&self, x: [usize; N]) -> [usize; O];
}

struct Zero;

impl<const N: usize> PrimRec<N, 1> for Zero {
    fn eval(&self, _: [usize; N]) -> [usize; 1] {
        [0]
    }
}

struct S;

impl PrimRec<1, 1> for S {
    fn eval(&self, x: [usize; 1]) -> [usize; 1] {
        [x[0] + 1]
    }
}

struct Proj<const I: usize>;

impl<const N: usize, const I: usize> PrimRec<N, 1> for Proj<I> {
    fn eval(&self, x: [usize; N]) -> [usize; 1] {
        [x[I]]
    }
}

fn concat<const M: usize, const N: usize>(a: [usize; M], b: [usize; N]) -> [usize; M + N] {
    array::from_fn(|i| if i < M { a[i] } else { b[i - M] })
}

struct Compose<const N: usize, const I: usize, const O: usize, A, B>(A, B);

impl<const N: usize, const I: usize, const O: usize, A: PrimRec<N, I>, B: PrimRec<I, O>>
    PrimRec<N, O> for Compose<N, I, O, A, B>
{
    fn eval(&self, x: [usize; N]) -> [usize; O] {
        self.1.eval(self.0.eval(x))
    }
}

struct Rec<const N: usize, const O: usize, Base, F>(Base, F);

fn tail<const N: usize>(x: [usize; N + 1]) -> [usize; N] {
    array::from_fn(|i| x[i + 1])
}

fn cons<const N: usize>(x: usize, xs: [usize; N]) -> [usize; N + 1] {
    array::from_fn(|i| if i == 0 { x } else { xs[i - 1] })
}

impl<const N: usize, const O: usize, Base, F: PrimRec<{ O + (N + 1) }, O>> PrimRec<{ N + 1 }, O>
    for Rec<N, O, Base, F>
{
    fn eval(&self, x: [usize; N + 1]) -> [usize; O] {
        match (x[0], tail(x)) {
            (y, x) => {
                let xy = cons(y - 1, x);
                let input = concat(self.eval(xy), xy);
                self.1.eval(input)
            }
        }
    }
}

fn main() {
    let one = Compose(Zero, S);
    dbg!(one.eval([]));
    let add: Rec<1, 1, Proj<0>, Compose<3, 1, 1, Proj<0>, S>> =
        Rec(Proj::<0>, Compose(Proj::<0>, S));
    dbg!(add.eval([3, 2]));
}


````

<details><summary><strong>original code</strong></summary>
<p>

original:
````rust
#![feature(generic_const_exprs)]

use std::array;

trait PrimRec<const N: usize, const O: usize> {
    fn eval(&self, x: [usize; N]) -> [usize; O];
}

struct Zero;

impl<const N: usize> PrimRec<N, 1> for Zero {
    fn eval(&self, _: [usize; N]) -> [usize; 1] {
        [0]
    }
}

struct Const(usize);

impl<const N: usize> PrimRec<N, 1> for Const {
    fn eval(&self, _: [usize; N]) -> [usize; 1] {
        [self.0]
    }
}

struct S;

impl PrimRec<1, 1> for S {
    fn eval(&self, x: [usize; 1]) -> [usize; 1] {
        [x[0] + 1]
    }
}

struct Proj<const I: usize>;

impl<const N: usize, const I: usize> PrimRec<N, 1> for Proj<I> {
    fn eval(&self, x: [usize; N]) -> [usize; 1] {
        [x[I]]
    }
}

struct Merge<const N: usize, const O1: usize, const O2: usize, A: PrimRec<N, O1>, B: PrimRec<N, O2>>(
    A,
    B,
);

fn concat<const M: usize, const N: usize>(a: [usize; M], b: [usize; N]) -> [usize; M + N] {
    array::from_fn(|i| if i < M { a[i] } else { b[i - M] })
}

impl<const N: usize, const O1: usize, const O2: usize, A: PrimRec<N, O1>, B: PrimRec<N, O2>>
    PrimRec<N, { O1 + O2 }> for Merge<N, O1, O2, A, B>
{
    fn eval(&self, x: [usize; N]) -> [usize; O1 + O2] {
        concat(self.0.eval(x), self.1.eval(x))
    }
}

struct Compose<const N: usize, const I: usize, const O: usize, A: PrimRec<N, I>, B: PrimRec<I, O>>(
    A,
    B,
);

impl<const N: usize, const I: usize, const O: usize, A: PrimRec<N, I>, B: PrimRec<I, O>>
    PrimRec<N, O> for Compose<N, I, O, A, B>
{
    fn eval(&self, x: [usize; N]) -> [usize; O] {
        self.1.eval(self.0.eval(x))
    }
}

struct Rec<const N: usize, const O: usize, Base: PrimRec<N, O>, F: PrimRec<{ O + (N + 1) }, O>>(
    Base,
    F,
);

fn tail<const N: usize>(x: [usize; N + 1]) -> [usize; N] {
    array::from_fn(|i| x[i + 1])
}

fn cons<const N: usize>(x: usize, xs: [usize; N]) -> [usize; N + 1] {
    array::from_fn(|i| if i == 0 { x } else { xs[i - 1] })
}

impl<const N: usize, const O: usize, Base: PrimRec<N, O>, F: PrimRec<{ O + (N + 1) }, O>>
    PrimRec<{ N + 1 }, O> for Rec<N, O, Base, F>
{
    fn eval(&self, x: [usize; N + 1]) -> [usize; O] {
        match (x[0], tail(x)) {
            (y, x) => {
                let xy = cons(y - 1, x);
                let input = concat(self.eval(xy), xy);
                self.1.eval(input)
            }
            (y, x) => {
                let xy = cons(y - 1, x);
                let input = concat(self.eval(xy), xy);
                self.1.eval(input)
            }
        }
    }
}

fn main() {
    let one = Compose(Zero, S);
    dbg!(one.eval([]));
    let add: Rec<1, 1, Proj<0>, Compose<3, 1, 1, Proj<0>, S>> =
        Rec(Proj::<0>, Compose(Proj::<0>, S));
    dbg!(add.eval([3, 2]));
}

````
</p>
</details>

Version information
````
rustc 1.81.0-nightly (3186d17d5 2024-06-19)
binary: rustc
commit-hash: 3186d17d56f9803b739a2c0aabd23aafd8791485
commit-date: 2024-06-19
host: x86_64-unknown-linux-gnu
release: 1.81.0-nightly
LLVM version: 18.1.7

````

Command:
`/home/matthias/.rustup/toolchains/master/bin/rustc `

<!--
Include a backtrace in the code block by setting `RUST_BACKTRACE=1` in your
environment. E.g. `RUST_BACKTRACE=1 cargo build`.
-->
<details><summary><strong>Program output</strong></summary>
<p>

```
warning: the feature `generic_const_exprs` is incomplete and may not be safe to use and/or cause compiler crashes
 --> /tmp/icemaker_global_tempdir.BYeIIN3IDTg1/rustc_testrunner_tmpdir_reporting.pn272iv1coHt/mvce.rs:1:12
  |
1 | #![feature(generic_const_exprs)]
  |            ^^^^^^^^^^^^^^^^^^^
  |
  = note: see issue #76560 <https://github.com/rust-lang/rust/issues/76560> for more information
  = note: `#[warn(incomplete_features)]` on by default

warning: function cannot return without recursing
  --> /tmp/icemaker_global_tempdir.BYeIIN3IDTg1/rustc_testrunner_tmpdir_reporting.pn272iv1coHt/mvce.rs:60:5
   |
60 |     fn eval(&self, x: [usize; N + 1]) -> [usize; O] {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot return without recursing
...
64 |                 let input = concat(self.eval(xy), xy);
   |                                    ------------- recursive call site
   |
   = help: a `loop` may express intention better if this is on purpose
   = note: `#[warn(unconditional_recursion)]` on by default

error: internal compiler error: compiler/rustc_monomorphize/src/collector.rs:703:50: collection encountered polymorphic constant: Ty(usize, (Add: (1_usize: usize), (1_usize: usize)))
  --> /tmp/icemaker_global_tempdir.BYeIIN3IDTg1/rustc_testrunner_tmpdir_reporting.pn272iv1coHt/mvce.rs:34:49
   |
34 |     array::from_fn(|i| if i < M { a[i] } else { b[i - M] })
   |                                                 ^^^^^^^^

thread 'rustc' panicked at compiler/rustc_monomorphize/src/collector.rs:703:50:
Box<dyn Any>
stack backtrace:
   0:     0x7e169cf9a915 - std::backtrace_rs::backtrace::libunwind::trace::h7bb2e2c0ba47a528
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/../../backtrace/src/backtrace/libunwind.rs:116:5
   1:     0x7e169cf9a915 - std::backtrace_rs::backtrace::trace_unsynchronized::h4d0192941edee661
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x7e169cf9a915 - std::sys::backtrace::_print_fmt::hd97d629aac4a983f
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/sys/backtrace.rs:68:5
   3:     0x7e169cf9a915 - <std::sys::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::hfbfff27250bacb87
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/sys/backtrace.rs:44:22
   4:     0x7e169cfeb4bb - core::fmt::rt::Argument::fmt::he10ba4f740dba534
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/core/src/fmt/rt.rs:165:63
   5:     0x7e169cfeb4bb - core::fmt::write::h2407ad66766d3825
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/core/src/fmt/mod.rs:1168:21
   6:     0x7e169cf8f4ff - std::io::Write::write_fmt::ha9f6e1a0fc7453ce
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/io/mod.rs:1835:15
   7:     0x7e169cf9a6ee - std::sys::backtrace::_print::h7e0f8c040736e5d1
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/sys/backtrace.rs:47:5
   8:     0x7e169cf9a6ee - std::sys::backtrace::print::h5b5a8173569d0f1f
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/sys/backtrace.rs:34:9
   9:     0x7e169cf9d129 - std::panicking::default_hook::{{closure}}::h598070fde84813fd
  10:     0x7e169cf9cecc - std::panicking::default_hook::h475a3da7dddfd122
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/panicking.rs:292:9
  11:     0x7e169953d430 - std[2bd9c63c0a80de36]::panicking::update_hook::<alloc[84d3ef64e8f78ef7]::boxed::Box<rustc_driver_impl[9baf949efeffb90b]::install_ice_hook::{closure#0}>>::{closure#0}
  12:     0x7e169cf9da4f - <alloc::boxed::Box<F,A> as core::ops::function::Fn<Args>>::call::h7852cb703cb16a8a
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/alloc/src/boxed.rs:2076:9
  13:     0x7e169cf9da4f - std::panicking::rust_panic_with_hook::h09dcd92a3eced375
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/panicking.rs:804:13
  14:     0x7e169956e111 - std[2bd9c63c0a80de36]::panicking::begin_panic::<rustc_errors[a1210feefd110a67]::ExplicitBug>::{closure#0}
  15:     0x7e169956aa46 - std[2bd9c63c0a80de36]::sys::backtrace::__rust_end_short_backtrace::<std[2bd9c63c0a80de36]::panicking::begin_panic<rustc_errors[a1210feefd110a67]::ExplicitBug>::{closure#0}, !>
  16:     0x7e1699565cd6 - std[2bd9c63c0a80de36]::panicking::begin_panic::<rustc_errors[a1210feefd110a67]::ExplicitBug>
  17:     0x7e16995773b1 - <rustc_errors[a1210feefd110a67]::diagnostic::BugAbort as rustc_errors[a1210feefd110a67]::diagnostic::EmissionGuarantee>::emit_producing_guarantee
  18:     0x7e1699cea6e8 - <rustc_errors[a1210feefd110a67]::DiagCtxtHandle>::span_bug::<rustc_span[825a5f7bcd5860db]::span_encoding::Span, alloc[84d3ef64e8f78ef7]::string::String>
  19:     0x7e1699cf5f3d - rustc_middle[1e151660401c97c9]::util::bug::opt_span_bug_fmt::<rustc_span[825a5f7bcd5860db]::span_encoding::Span>::{closure#0}
  20:     0x7e1699cf620a - rustc_middle[1e151660401c97c9]::ty::context::tls::with_opt::<rustc_middle[1e151660401c97c9]::util::bug::opt_span_bug_fmt<rustc_span[825a5f7bcd5860db]::span_encoding::Span>::{closure#0}, !>::{closure#0}
  21:     0x7e1699cf1c5b - rustc_middle[1e151660401c97c9]::ty::context::tls::with_context_opt::<rustc_middle[1e151660401c97c9]::ty::context::tls::with_opt<rustc_middle[1e151660401c97c9]::util::bug::opt_span_bug_fmt<rustc_span[825a5f7bcd5860db]::span_encoding::Span>::{closure#0}, !>::{closure#0}, !>
  22:     0x7e1699cef657 - rustc_middle[1e151660401c97c9]::util::bug::span_bug_fmt::<rustc_span[825a5f7bcd5860db]::span_encoding::Span>
  23:     0x7e169b895886 - rustc_monomorphize[ce7da5b91994c407]::collector::collect_items_rec::{closure#0}
  24:     0x7e169aa8a20a - rustc_monomorphize[ce7da5b91994c407]::collector::collect_items_rec
  25:     0x7e169aa8a991 - rustc_monomorphize[ce7da5b91994c407]::collector::collect_items_rec
  26:     0x7e169aa8a991 - rustc_monomorphize[ce7da5b91994c407]::collector::collect_items_rec
  27:     0x7e169aa8a991 - rustc_monomorphize[ce7da5b91994c407]::collector::collect_items_rec
  28:     0x7e169aa8a991 - rustc_monomorphize[ce7da5b91994c407]::collector::collect_items_rec
  29:     0x7e169aa8a991 - rustc_monomorphize[ce7da5b91994c407]::collector::collect_items_rec
  30:     0x7e169aa8a991 - rustc_monomorphize[ce7da5b91994c407]::collector::collect_items_rec
  31:     0x7e169aa8a991 - rustc_monomorphize[ce7da5b91994c407]::collector::collect_items_rec
  32:     0x7e169afb40b9 - rustc_monomorphize[ce7da5b91994c407]::partitioning::collect_and_partition_mono_items
  33:     0x7e169baa5d64 - rustc_query_impl[90e082e217628c6f]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[90e082e217628c6f]::query_impl::collect_and_partition_mono_items::dynamic_query::{closure#2}::{closure#0}, rustc_middle[1e151660401c97c9]::query::erase::Erased<[u8; 24usize]>>
  34:     0x7e169baa5d49 - <rustc_query_impl[90e082e217628c6f]::query_impl::collect_and_partition_mono_items::dynamic_query::{closure#2} as core[86ed06ce5521d24]::ops::function::FnOnce<(rustc_middle[1e151660401c97c9]::ty::context::TyCtxt, ())>>::call_once
  35:     0x7e169baa5908 - rustc_query_system[79f2d7548a1d7730]::query::plumbing::try_execute_query::<rustc_query_impl[90e082e217628c6f]::DynamicConfig<rustc_query_system[79f2d7548a1d7730]::query::caches::SingleCache<rustc_middle[1e151660401c97c9]::query::erase::Erased<[u8; 24usize]>>, false, false, false>, rustc_query_impl[90e082e217628c6f]::plumbing::QueryCtxt, false>
  36:     0x7e169baa5621 - rustc_query_impl[90e082e217628c6f]::query_impl::collect_and_partition_mono_items::get_query_non_incr::__rust_end_short_backtrace
  37:     0x7e169b9039d4 - rustc_codegen_ssa[9f248794c5001305]::base::codegen_crate::<rustc_codegen_llvm[9bd2c74879613e19]::LlvmCodegenBackend>
  38:     0x7e169b8f8202 - <rustc_codegen_llvm[9bd2c74879613e19]::LlvmCodegenBackend as rustc_codegen_ssa[9f248794c5001305]::traits::backend::CodegenBackend>::codegen_crate
  39:     0x7e169b8f7b85 - rustc_interface[f14b298c5bc54b9d]::passes::start_codegen
  40:     0x7e169b8f7224 - <rustc_interface[f14b298c5bc54b9d]::queries::Queries>::codegen_and_build_linker
  41:     0x7e169b6e79f2 - rustc_interface[f14b298c5bc54b9d]::interface::run_compiler::<core[86ed06ce5521d24]::result::Result<(), rustc_span[825a5f7bcd5860db]::ErrorGuaranteed>, rustc_driver_impl[9baf949efeffb90b]::run_compiler::{closure#0}>::{closure#1}
  42:     0x7e169b6d5ce7 - std[2bd9c63c0a80de36]::sys::backtrace::__rust_begin_short_backtrace::<rustc_interface[f14b298c5bc54b9d]::util::run_in_thread_with_globals<rustc_interface[f14b298c5bc54b9d]::util::run_in_thread_pool_with_globals<rustc_interface[f14b298c5bc54b9d]::interface::run_compiler<core[86ed06ce5521d24]::result::Result<(), rustc_span[825a5f7bcd5860db]::ErrorGuaranteed>, rustc_driver_impl[9baf949efeffb90b]::run_compiler::{closure#0}>::{closure#1}, core[86ed06ce5521d24]::result::Result<(), rustc_span[825a5f7bcd5860db]::ErrorGuaranteed>>::{closure#0}, core[86ed06ce5521d24]::result::Result<(), rustc_span[825a5f7bcd5860db]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[86ed06ce5521d24]::result::Result<(), rustc_span[825a5f7bcd5860db]::ErrorGuaranteed>>
  43:     0x7e169b6d5aaa - <<std[2bd9c63c0a80de36]::thread::Builder>::spawn_unchecked_<rustc_interface[f14b298c5bc54b9d]::util::run_in_thread_with_globals<rustc_interface[f14b298c5bc54b9d]::util::run_in_thread_pool_with_globals<rustc_interface[f14b298c5bc54b9d]::interface::run_compiler<core[86ed06ce5521d24]::result::Result<(), rustc_span[825a5f7bcd5860db]::ErrorGuaranteed>, rustc_driver_impl[9baf949efeffb90b]::run_compiler::{closure#0}>::{closure#1}, core[86ed06ce5521d24]::result::Result<(), rustc_span[825a5f7bcd5860db]::ErrorGuaranteed>>::{closure#0}, core[86ed06ce5521d24]::result::Result<(), rustc_span[825a5f7bcd5860db]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[86ed06ce5521d24]::result::Result<(), rustc_span[825a5f7bcd5860db]::ErrorGuaranteed>>::{closure#2} as core[86ed06ce5521d24]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0}
  44:     0x7e169cfa78cb - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h080d8c35a4cd7df7
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/alloc/src/boxed.rs:2062:9
  45:     0x7e169cfa78cb - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::hbe3e90ec6c687c94
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/alloc/src/boxed.rs:2062:9
  46:     0x7e169cfa78cb - std::sys::pal::unix::thread::Thread::new::thread_start::h9be4fe738a3fe2ed
                               at /rustc/3186d17d56f9803b739a2c0aabd23aafd8791485/library/std/src/sys/pal/unix/thread.rs:108:17
  47:     0x7e169cd40ded - <unknown>
  48:     0x7e169cdc40dc - <unknown>
  49:                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: please make sure that you have updated to the latest nightly

note: rustc 1.81.0-nightly (3186d17d5 2024-06-19) running on x86_64-unknown-linux-gnu

query stack during panic:
#0 [collect_and_partition_mono_items] collect_and_partition_mono_items
end of query stack
error: aborting due to 1 previous error; 2 warnings emitted


```

</p>
</details>

<!--
query stack:
60 |     fn eval(&self, x: [usize; N + 1]) -> [usize; O] {
34 |     array::from_fn(|i| if i < M { a[i] } else { b[i - M] })
#0 [collect_and_partition_mono_items] collect_and_partition_mono_items

-->
@rustbot label +F-generic_const_exprs