ICE type parameter out of range when substituting

[lightmelodies]

I'm trying to implement something like c++ std::conditional_t with generic_const_exprs. The follower code just works but much verbose due to lack of type alias inside struct.

Code

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

trait Ret {
    type R;
}

struct Cond<const PRED: bool, U, V>(std::marker::PhantomData<U>, std::marker::PhantomData<V>);

impl<U, V> Ret for Cond<true, U, V> {
    type R = U;
}

impl<U, V> Ret for Cond<false, U, V> {
    type R = V;
}

struct RobinHashTable<const MAX_LENGTH: usize>
where
    Cond<{ MAX_LENGTH < 65535 }, u16, u32>: Ret,
{
    _idx: <Cond<{ MAX_LENGTH < 65535 }, u16, u32> as Ret>::R,
}

fn main() {
    use std::mem::size_of;
    println!("{}", size_of::<RobinHashTable<1024>>());
    println!("{}", size_of::<RobinHashTable<65536>>());
}

I tried to change it to below forms but all got internal compiler error

struct RobinHashTable<const MAX_LENGTH: usize, CellIdx = Cond<{ MAX_LENGTH < 65535 }, u16, u32>>
where
    CellIdx: Ret,
{
    _idx: CellIdx::R,
}

struct RobinHashTable<
    const MAX_LENGTH: usize,
    CellIdx = <Cond<{ MAX_LENGTH < 65535 }, u16, u32> as Ret>::R,
> {
    _idx: CellIdx,
}

Meta

rustc --version --verbose:

rustc 1.67.0-nightly (234151769 2022-12-03)
binary: rustc
commit-hash: 23415176968e81e0aac92d0218612a89c4e68a82
commit-date: 2022-12-03
host: x86_64-unknown-linux-gnu
release: 1.67.0-nightly
LLVM version: 15.0.4

Error output

query stack during panic:
#0 [typeck] type-checking `main`
#1 [typeck_item_bodies] type-checking all item bodies
#2 [analysis] running analysis passes on this crate
end of query stack

Backtrace

error: internal compiler error: compiler/rustc_middle/src/ty/subst.rs:810:9: type parameter `CellIdx/#1` (CellIdx/1) out of range when substituting, substs=[Const { ty: usize, kind: Value(Leaf(0x0000000000000400)) }]

thread 'rustc' panicked at 'Box<dyn Any>', /rustc/23415176968e81e0aac92d0218612a89c4e68a82/compiler/rustc_errors/src/lib.rs:1575:9
stack backtrace:
   0: std::panicking::begin_panic::<rustc_errors::ExplicitBug>
   1: std::panic::panic_any::<rustc_errors::ExplicitBug>
   2: <rustc_errors::HandlerInner>::bug::<&alloc::string::String>
   3: <rustc_errors::Handler>::bug::<&alloc::string::String>
   4: rustc_middle::ty::context::tls::with_context_opt::<rustc_middle::ty::context::tls::with_opt<rustc_middle::util::bug::opt_span_bug_fmt<rustc_span::span_encoding::Span>::{closure#0}, ()>::{closure#0}, ()>
   5: rustc_middle::util::bug::opt_span_bug_fmt::<rustc_span::span_encoding::Span>
   6: rustc_middle::util::bug::bug_fmt
   7: <rustc_middle::ty::subst::SubstFolder>::type_param_out_of_range
   8: <rustc_middle::ty::subst::SubstFolder as rustc_middle::ty::fold::FallibleTypeFolder>::try_fold_ty
   9: <&rustc_middle::ty::list::List<rustc_middle::ty::subst::GenericArg> as rustc_middle::ty::fold::TypeFoldable>::try_fold_with::<rustc_middle::ty::subst::SubstFolder>
  10: <rustc_middle::ty::consts::Const as rustc_middle::ty::fold::TypeSuperFoldable>::super_fold_with::<rustc_middle::ty::subst::SubstFolder>
  11: <rustc_middle::ty::Ty as rustc_middle::ty::fold::TypeSuperFoldable>::super_fold_with::<rustc_middle::ty::subst::SubstFolder>
  12: <<dyn rustc_hir_analysis::astconv::AstConv>::create_substs_for_ast_path::{closure#0}::SubstsForAstPathCtxt as rustc_hir_analysis::astconv::CreateSubstsForGenericArgsCtxt>::inferred_kind
  13: <dyn rustc_hir_analysis::astconv::AstConv>::res_to_ty
  14: <dyn rustc_hir_analysis::astconv::AstConv>::ast_ty_to_ty_inner::{closure#0}
  15: <<rustc_hir_typeck::fn_ctxt::FnCtxt>::instantiate_value_path::CreateCtorSubstsContext as rustc_hir_analysis::astconv::CreateSubstsForGenericArgsCtxt>::provided_kind
  16: <dyn rustc_hir_analysis::astconv::AstConv>::create_substs_for_generic_args::<<rustc_hir_typeck::fn_ctxt::FnCtxt>::instantiate_value_path::CreateCtorSubstsContext>
  17: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_path
  18: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_call
  19: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_with_expectation_and_args
  20: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_with_expectation_and_args
  21: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_argument_types
  22: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_call
  23: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_with_expectation_and_args
  24: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_with_expectation_and_args
  25: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_with_expectation_and_args
  26: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_argument_types
  27: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_call
  28: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_with_expectation_and_args
  29: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_argument_types
  30: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_call
  31: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_with_expectation_and_args
  32: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_block_with_expected
  33: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_with_expectation_and_args
  34: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_block_with_expected
  35: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_expr_with_expectation_and_args
  36: <rustc_hir_typeck::fn_ctxt::FnCtxt>::check_return_expr
  37: rustc_hir_typeck::check::check_fn
  38: rustc_hir_typeck::typeck
  39: <rustc_query_system::dep_graph::graph::DepGraph<rustc_middle::dep_graph::dep_node::DepKind>>::with_task::<rustc_middle::ty::context::TyCtxt, rustc_span::def_id::LocalDefId, &rustc_middle::ty::context::TypeckResults>
  40: rustc_query_system::query::plumbing::try_execute_query::<rustc_query_impl::plumbing::QueryCtxt, rustc_query_system::query::caches::VecCache<rustc_span::def_id::LocalDefId, &rustc_middle::ty::context::TypeckResults>>
  41: rustc_data_structures::sync::par_for_each_in::<&[rustc_span::def_id::LocalDefId], <rustc_middle::hir::map::Map>::par_body_owners<rustc_hir_typeck::typeck_item_bodies::{closure#0}>::{closure#0}>
  42: rustc_hir_typeck::typeck_item_bodies
  43: <rustc_query_system::dep_graph::graph::DepGraph<rustc_middle::dep_graph::dep_node::DepKind>>::with_task::<rustc_middle::ty::context::TyCtxt, (), ()>
  44: rustc_query_system::query::plumbing::try_execute_query::<rustc_query_impl::plumbing::QueryCtxt, rustc_query_system::query::caches::DefaultCache<(), ()>>
  45: rustc_query_system::query::plumbing::get_query::<rustc_query_impl::queries::typeck_item_bodies, rustc_query_impl::plumbing::QueryCtxt>
  46: <rustc_session::session::Session>::time::<(), rustc_hir_analysis::check_crate::{closure#7}>
  47: rustc_hir_analysis::check_crate
  48: rustc_interface::passes::analysis
  49: <rustc_query_system::dep_graph::graph::DepGraph<rustc_middle::dep_graph::dep_node::DepKind>>::with_task::<rustc_middle::ty::context::TyCtxt, (), core::result::Result<(), rustc_errors::ErrorGuaranteed>>
  50: rustc_query_system::query::plumbing::try_execute_query::<rustc_query_impl::plumbing::QueryCtxt, rustc_query_system::query::caches::DefaultCache<(), core::result::Result<(), rustc_errors::ErrorGuaranteed>>>
  51: rustc_query_system::query::plumbing::get_query::<rustc_query_impl::queries::analysis, rustc_query_impl::plumbing::QueryCtxt>
  52: <rustc_interface::passes::QueryContext>::enter::<rustc_driver::run_compiler::{closure#1}::{closure#2}::{closure#2}, core::result::Result<(), rustc_errors::ErrorGuaranteed>>
  53: <rustc_interface::interface::Compiler>::enter::<rustc_driver::run_compiler::{closure#1}::{closure#2}, core::result::Result<core::option::Option<rustc_interface::queries::Linker>, rustc_errors::ErrorGuaranteed>>
  54: rustc_span::with_source_map::<core::result::Result<(), rustc_errors::ErrorGuaranteed>, rustc_interface::interface::run_compiler<core::result::Result<(), rustc_errors::ErrorGuaranteed>, rustc_driver::run_compiler::{closure#1}>::{closure#0}::{closure#0}>
  55: <scoped_tls::ScopedKey<rustc_span::SessionGlobals>>::set::<rustc_interface::interface::run_compiler<core::result::Result<(), rustc_errors::ErrorGuaranteed>, rustc_driver::run_compiler::{closure#1}>::{closure#0}, core::result::Result<(), rustc_errors::ErrorGuaranteed>>
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

note: 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: rustc 1.67.0-nightly (234151769 2022-12-03) running on x86_64-unknown-linux-gnu

note: compiler flags: --crate-type bin -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 [typeck] type-checking `main`
#1 [typeck_item_bodies] type-checking all item bodies
#2 [analysis] running analysis passes on this crate
end of query stack

[jruderman]

ICEs as far back as nightly-2021-04-26. Before that, the compiler rejected the use of MAX_LENGTH in the default for CellIdx.

[langston-barrett]

I was able to reproduce this with

rustc 1.70.0-nightly (7b4f48927 2023-03-12)
binary: rustc
commit-hash: 7b4f48927dce585f747a58083b45ab62b9d73a53
commit-date: 2023-03-12
host: x86_64-unknown-linux-gnu
release: 1.70.0-nightly
LLVM version: 15.0.7

Minimized with treereduce:

#![feature(generic_const_exprs)]

struct Cond<const PRED: bool, U, V>(stdmarkerPhantomData<U>);

struct RobinHashTable<const MAX_LENGTH: usize, CellIdx = Cond<{ MAX_LENGTH < 65535 }, u16, u32>> {
    _idx: CellIdxR,
}

fn main() {
    println!("{}", std::mem::size_of::<RobinHashTable>);
}

[voidc]

This issue can be even further minimized:

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

struct Foo<const P: bool>;
struct Bar<const N: usize, T = Foo<{ N < 7 }>>;
type X = Bar<3>;

fn main() {}

The anon const for {N < 7} inherits both generic parameters from its parent Bar. Now, when we try substituting in the default type Foo<{N < 7}> we only have a substitution for N and not for T. So, in essence, this is another manifestation of rust-lang/project-const-generics#33.

[gurry]

Related to or possible duplicate of #106994