ICE type parameter out of range when substituting

lightmelodies commented 1 year ago

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,
}

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', /rustc/23415176968e81e0aac92d0218612a89c4e68a82/compiler/rustc_errors/src/lib.rs:1575:9 stack backtrace: 0: std::panicking::begin_panic:: 1: std::panic::panic_any:: 2: ::bug::<&alloc::string::String> 3: ::bug::<&alloc::string::String> 4: rustc_middle::ty::context::tls::with_context_opt::::{closure#0}, ()>::{closure#0}, ()> 5: rustc_middle::util::bug::opt_span_bug_fmt:: 6: rustc_middle::util::bug::bug_fmt 7: ::type_param_out_of_range 8: ::try_fold_ty 9: <&rustc_middle::ty::list::List as rustc_middle::ty::fold::TypeFoldable>::try_fold_with:: 10: ::super_fold_with:: 11: ::super_fold_with:: 12: <::create_substs_for_ast_path::{closure#0}::SubstsForAstPathCtxt as rustc_hir_analysis::astconv::CreateSubstsForGenericArgsCtxt>::inferred_kind 13: ::res_to_ty 14: ::ast_ty_to_ty_inner::{closure#0} 15: <::instantiate_value_path::CreateCtorSubstsContext as rustc_hir_analysis::astconv::CreateSubstsForGenericArgsCtxt>::provided_kind 16: ::create_substs_for_generic_args::<::instantiate_value_path::CreateCtorSubstsContext> 17: ::check_expr_path 18: ::check_call 19: ::check_expr_with_expectation_and_args 20: ::check_expr_with_expectation_and_args 21: ::check_argument_types 22: ::check_call 23: ::check_expr_with_expectation_and_args 24: ::check_expr_with_expectation_and_args 25: ::check_expr_with_expectation_and_args 26: ::check_argument_types 27: ::check_call 28: ::check_expr_with_expectation_and_args 29: ::check_argument_types 30: ::check_call 31: ::check_expr_with_expectation_and_args 32: ::check_block_with_expected 33: ::check_expr_with_expectation_and_args 34: ::check_block_with_expected 35: ::check_expr_with_expectation_and_args 36: ::check_return_expr 37: rustc_hir_typeck::check::check_fn 38: rustc_hir_typeck::typeck 39: >::with_task:: 40: rustc_query_system::query::plumbing::try_execute_query::> 41: rustc_data_structures::sync::par_for_each_in::<&[rustc_span::def_id::LocalDefId], ::par_body_owners::{closure#0}> 42: rustc_hir_typeck::typeck_item_bodies 43: >::with_task:: 44: rustc_query_system::query::plumbing::try_execute_query::> 45: rustc_query_system::query::plumbing::get_query:: 46: ::time::<(), rustc_hir_analysis::check_crate::{closure#7}> 47: rustc_hir_analysis::check_crate 48: rustc_interface::passes::analysis 49: >::with_task::> 50: rustc_query_system::query::plumbing::try_execute_query::>> 51: rustc_query_system::query::plumbing::get_query:: 52: ::enter::> 53: ::enter::, rustc_errors::ErrorGuaranteed>> 54: rustc_span::with_source_map::, rustc_interface::interface::run_compiler, rustc_driver::run_compiler::{closure#1}>::{closure#0}::{closure#0}> 55: >::set::, 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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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 https://github.com/rust-lang/project-const-generics/issues/33.

gurry commented 10 months ago

Related to or possible duplicate of #106994

rust-lang / rust

ICE type parameter out of range when substituting #105238

Code

Meta

Error output