ICE on generic associated type with a bound referencing the quantified type

[jyn514]

I was reading https://varkor.github.io/blog/2019/03/28/idiomatic-monads-in-rust.html and decided to try some of the code samples, but the compiler panicked!

trait Functor<A> {
    type HigherSelf<T>: Functor<T>;
}

Crashes with error: internal compiler error: src/librustc/ty/subst.rs:570: type parameter T/#2 (T/2) out of range when substituting (root type=Some(T)) substs=[<Self as Functor<A>>::HigherSelf, T]

The compiler mentions that 'generic associated types are unstable', but the crash occurs even with the feature gate turned off. This happens on both stable and nightly.

Traceback

thread 'rustc' panicked at 'Box<Any>', src/librustc_errors/lib.rs:572:9
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:197
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:211
   4: rustc::util::common::panic_hook
   5: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:478
   6: std::panicking::begin_panic
   7: rustc_errors::Handler::span_bug
   8: rustc::util::bug::opt_span_bug_fmt::{{closure}}
   9: rustc::ty::context::tls::with_opt::{{closure}}
  10: rustc::ty::context::tls::with_context_opt
  11: rustc::ty::context::tls::with_opt
  12: rustc::util::bug::opt_span_bug_fmt
  13: rustc::util::bug::span_bug_fmt
  14: <rustc::ty::subst::SubstFolder as rustc::ty::fold::TypeFolder>::fold_ty
  15: <smallvec::SmallVec<A> as core::iter::traits::collect::FromIterator<<A as smallvec::Array>::Item>>::from_iter
  16: rustc::ty::fold::TypeFoldable::fold_with
  17: rustc::ty::subst::Subst::subst
  18: <core::iter::adapters::Map<I,F> as core::iter::traits::iterator::Iterator>::fold
  19: rustc::ty::GenericPredicates::instantiate_into
  20: rustc::ty::wf::WfPredicates::nominal_obligations
  21: rustc::ty::wf::WfPredicates::compute_trait_ref
  22: rustc::ty::wf::predicate_obligations
  23: <core::iter::adapters::flatten::FlatMap<I,U,F> as core::iter::traits::iterator::Iterator>::next
  24: rustc_typeck::check::wfcheck::check_where_clauses
  25: rustc::ty::context::GlobalCtxt::enter_local
  26: rustc_typeck::check::wfcheck::check_trait
  27: rustc_typeck::check::wfcheck::check_item_well_formed
  28: rustc::ty::query::__query_compute::check_item_well_formed
  29: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::check_item_well_formed>::compute
  30: rustc::dep_graph::graph::DepGraph::with_task_impl
  31: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  32: <rustc_typeck::check::wfcheck::CheckTypeWellFormedVisitor as rustc::hir::itemlikevisit::ParItemLikeVisitor>::visit_item
  33: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:85
  34: rustc_data_structures::sync::par_for_each_in
  35: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:85
  36: rustc::hir::Crate::par_visit_all_item_likes
  37: rustc::util::common::time
  38: rustc_typeck::check_crate
  39: rustc_interface::passes::analysis
  40: rustc::ty::query::__query_compute::analysis
  41: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::analysis>::compute
  42: rustc::dep_graph::graph::DepGraph::with_task_impl
  43: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  44: rustc::ty::context::tls::enter_global
  45: rustc_interface::passes::BoxedGlobalCtxt::access::{{closure}}
  46: rustc_interface::passes::create_global_ctxt::{{closure}}
  47: rustc_interface::interface::run_compiler_in_existing_thread_pool
  48: std::thread::local::LocalKey<T>::with
  49: scoped_tls::ScopedKey<T>::set
  50: syntax::with_globals
query stack during panic:
#0 [check_item_well_formed] processing `Functor`
#1 [analysis] running analysis passes on this crate
end of query stack

Version

$ rustc --version -v
rustc 1.36.0 (a53f9df32 2019-07-03)
binary: rustc
commit-hash: a53f9df32fbb0b5f4382caaad8f1a46f36ea887c
commit-date: 2019-07-03
host: x86_64-unknown-linux-gnu
release: 1.36.0
LLVM version: 8.0

This issue has been assigned to @doctorn via this comment.

[cofibrant]

I'd like to take a look at this if no-one minds?

@rustbot claim

[jyn514]

FWIW, it doesn't look like the bound has to reference the quantified type, this gives the same crash:

trait Functor<A> {
    type Associated<B>: Iterator<Item = B>;
}

[cofibrant]

@jyn514 the bound didn’t reference the quantified type in the first example either did it?

[jyn514]

It referenced the trait, not the type being bounded. I was using the words that @Centril used for the issue title, maybe I'm getting the terminology wrong.

[cofibrant]

This is particularly interesting because the ICE occurs even without ![feature(generic_associated_types)] (i.e. including a generic trait bound for the generic associated type somehow means it isn't recognised as such).