ICE with const generics with dependent const parameters

[Centril]

#![feature(const_generics)]

fn foo<const N: usize, const A: [u8; N]>() {}

fn bar() {
    foo::<1, {[1]}>();
}

results in an ICE:

error: internal compiler error: src/librustc/ty/subst.rs:597: const parameter `N/#0` (Const { ty: usize, val: Param(N/#0) }/0) out of range when substituting substs=[]

thread 'rustc' panicked at 'Box<Any>', src/librustc_errors/lib.rs:584:9
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.29/src/backtrace/libunwind.rs:88
   1: backtrace::backtrace::trace_unsynchronized
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.29/src/backtrace/mod.rs:66
   2: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:47
   3: std::sys_common::backtrace::print
             at src/libstd/sys_common/backtrace.rs:36
   4: std::panicking::default_hook::{{closure}}
             at src/libstd/panicking.rs:200
   5: std::panicking::default_hook
             at src/libstd/panicking.rs:214
   6: rustc::util::common::panic_hook
   7: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:481
   8: std::panicking::begin_panic
   9: rustc_errors::Handler::span_bug
  10: rustc::util::bug::opt_span_bug_fmt::{{closure}}
  11: rustc::ty::context::tls::with_opt::{{closure}}
  12: rustc::ty::context::tls::with_context_opt
  13: rustc::ty::context::tls::with_opt
  14: rustc::util::bug::opt_span_bug_fmt
  15: rustc::util::bug::span_bug_fmt
  16: <rustc::ty::subst::SubstFolder as rustc::ty::fold::TypeFolder>::fold_const
  17: rustc::ty::structural_impls::<impl rustc::ty::fold::TypeFoldable for &rustc::ty::TyS>::super_fold_with
  18: <rustc::ty::subst::SubstFolder as rustc::ty::fold::TypeFolder>::fold_ty
  19: rustc::traits::codegen::<impl rustc::ty::context::TyCtxt>::subst_and_normalize_erasing_regions
  20: rustc::ty::instance::Instance::resolve
  21: <rustc::traits::project::AssocTypeNormalizer as rustc::ty::fold::TypeFolder>::fold_const
  22: <smallvec::SmallVec<A> as core::iter::traits::collect::FromIterator<<A as smallvec::Array>::Item>>::from_iter
  23: rustc::ty::fold::TypeFoldable::fold_with
  24: rustc::ty::structural_impls::<impl rustc::ty::fold::TypeFoldable for &rustc::ty::TyS>::super_fold_with
  25: <rustc::traits::project::AssocTypeNormalizer as rustc::ty::fold::TypeFolder>::fold_ty
  26: rustc::traits::project::normalize
  27: rustc_typeck::check::FnCtxt::instantiate_value_path
  28: rustc_typeck::check::expr::<impl rustc_typeck::check::FnCtxt>::check_expr_with_expectation_and_needs
  29: rustc_typeck::check::callee::<impl rustc_typeck::check::FnCtxt>::check_call
  30: rustc_typeck::check::expr::<impl rustc_typeck::check::FnCtxt>::check_expr_with_expectation_and_needs
  31: rustc_typeck::check::FnCtxt::check_stmt
  32: rustc_typeck::check::FnCtxt::check_block_with_expected
  33: rustc_typeck::check::expr::<impl rustc_typeck::check::FnCtxt>::check_expr_with_expectation_and_needs
  34: rustc_typeck::check::expr::<impl rustc_typeck::check::FnCtxt>::check_return_expr
  35: rustc_typeck::check::check_fn
  36: rustc::ty::context::GlobalCtxt::enter_local
  37: rustc_typeck::check::typeck_tables_of
  38: rustc::ty::query::__query_compute::typeck_tables_of
  39: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::typeck_tables_of>::compute
  40: rustc::dep_graph::graph::DepGraph::with_task_impl
  41: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  42: rustc::ty::<impl rustc::ty::context::TyCtxt>::par_body_owners
  43: rustc_typeck::check::typeck_item_bodies
  44: rustc::ty::query::__query_compute::typeck_item_bodies
  45: rustc::dep_graph::graph::DepGraph::with_task_impl
  46: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  47: rustc::util::common::time
  48: rustc_typeck::check_crate
  49: rustc_interface::passes::analysis
  50: rustc::ty::query::__query_compute::analysis
  51: rustc::dep_graph::graph::DepGraph::with_task_impl
  52: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  53: rustc_interface::passes::BoxedGlobalCtxt::access::{{closure}}
  54: rustc_interface::passes::create_global_ctxt::{{closure}}
  55: rustc_interface::interface::run_compiler_in_existing_thread_pool
  56: std::thread::local::LocalKey<T>::with
  57: scoped_tls::ScopedKey<T>::set
  58: syntax::with_globals
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
query stack during panic:
#0 [typeck_tables_of] processing `bar`
#1 [typeck_item_bodies] type-checking all item bodies
#2 [analysis] running analysis passes on this crate
end of query stack
error: aborting due to previous error


note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.38.0-nightly (4b65a86eb 2019-07-15) running on x86_64-unknown-linux-gnu

[Aaron1011]

This appears to be due to the fact that we always create an empty substs for an AnonConst. We could either try to parse the body of the AnonConst to determine which generic parameters are actually used (in this case, N), or just use all of the available generic parameters (regardless of which actually get used).

I'm not sure which approach would be correct.

[ranweiler]

I was going to pick this up, but as of rustc 1.39.0-nightly (fba38ac27 2019-08-31), I no longer get an ICE, but the following error:

error[E0391]: cycle detected when processing `foo::A`
 --> src/main.rs:3:30
  |
3 | fn foo<const N: usize, const A: [u8; N]>() {}
  |                              ^
  |
  = note: ...which again requires processing `foo::A`, completing the cycle
note: cycle used when processing `foo`
 --> src/main.rs:3:1
  |
3 | fn foo<const N: usize, const A: [u8; N]>() {}
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

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

Bisecting, the ICE was fixed in rustc 1.39.0-nightly (bea0372a1 2019-08-20), possibly in #63497.

(cc @eddyb)

[PvdBerg1998]

Just out of curiosity, how is this a loop? I feel like this should be possible.

[ranweiler]

I think this requires lazy normalization (#60471), because const A is a projection. @eddyb, am I understanding that correctly, or did I get it wrong?

[eddyb]

@ranweiler Perhaps, at first glance this is an instance of #43408.

The cycle error happens to be the canonical result of fixing #43408 without lazy normalization (which is what happened here for direct uses of const generics as the whole array length expression).

@PvdBerg1998 First off, we're not even supposed to allow const generics with types other than a few whitelisted primitives, initially, but that whitelist hasn't been implemented yet.

But also, what's happening is that computing the types of all the const parameters ends up being cyclical (since the type of A depends on the type of N, but it's not that fine-grained yet).
It might be the case that such a specific cycle may be fixable without lazy normalization (cc @varkor).

[est31]

FYI this also occurs with bool instead of an array:

#![feature(const_generics)]
trait Foo {}

impl<const N: usize> Foo for [(); N]
where
    Self:FooImpl<{N==0}>
{}

trait FooImpl<const IS_ZERO: bool>{}

See also #61935 (used to not ICE when I filed it, now it ICE's).

[est31]

Now it gives an error:

error[E0391]: cycle detected when const-evaluating + checking `<impl at src/lib.rs:4:1: 7:3>::{{constant}}#0`

Same goes for @Centril 's bug report above.

[eddyb]

That's expected fallout from #66883 (explicitly needing lazy normalization rather than ICE-ing randomly).

However, note that non-trivial expressions that use type/const parameters, should, outside of bounds / impl headers, actually work now (previously they couldn't at all).

[lcnr]

We can't really support the original example rn. See #74159 which makes this explicit and adds a regression test for #62878

#![feature(const_generics)]

fn foo<const N: usize, const A: [u8; N]>() {}

fn bar() {
    foo::<1, {[1]}>();
}

Didn't look too much into the rest of this issue, so there might still be something we want to do here before closing this