Endless recursion while evaluating trait requirements

[mk12]

The following should compile successfully, but instead rustc chases requirements on &Vec<_>, &Vec<Vec<_>>, etc. until the recursion limit is exhausted. Increasing the limit does not help.

trait Foo { fn foo(self); }

struct S;
impl Foo for &S { fn foo(self) {} } // just to prove there is a way to bottom out

impl<'a, T> Foo for &'a Vec<T> where &'a T: Foo {
    fn foo(self) { array(self.as_slice()) }
}

fn array<'a, T>(a: &'a [T]) where &'a T: Foo {}

It gives:

error[E0275]: overflow evaluating the requirement `&Vec<_>: Foo`
  --> bug.rs:7:20
   |
7  |     fn foo(self) { array(self.as_slice()) }
   |                    ^^^^^
...
10 | fn array<'a, T>(a: &'a [T]) where &'a T: Foo {}
   |                                          --- required by this bound in `array`
   |
   = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`bug`)
note: required because of the requirements on the impl of `Foo` for `&Vec<Vec<_>>`
  --> bug.rs:6:13
   |
6  | impl<'a, T> Foo for &'a Vec<T> where &'a T: Foo {
   |             ^^^     ^^^^^^^^^^
   = note: 127 redundant requirements hidden
   = note: required because of the requirements on the impl of `Foo` for `&Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<_>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`

RUST_BACKTRACE=1 rustc bug.rs --crate-type=lib -Ztreat-err-as-bug=1:

Backtrace

thread 'rustc' panicked at 'aborting due to `-Z treat-err-as-bug=1`', compiler/rustc_errors/src/lib.rs:1035:27
stack backtrace:
   0: std::panicking::begin_panic
   1: rustc_errors::HandlerInner::emit_diagnostic
   2: rustc_errors::diagnostic_builder::DiagnosticBuilder::emit
   3: <rustc_infer::infer::InferCtxt as rustc_trait_selection::traits::error_reporting::InferCtxtExt>::report_overflow_error
   4: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively
   5: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicates_recursively
   6: rustc_infer::infer::InferCtxt::probe
   7: rustc_trait_selection::traits::select::SelectionContext::evaluate_candidate
   8: <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::try_fold
   9: <core::iter::adapters::ResultShunt<I,E> as core::iter::traits::iterator::Iterator>::next
  10: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
  11: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation_no_cache
  12: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  13: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation
  14: rustc_trait_selection::traits::select::SelectionContext::evaluate_stack
  15: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  16: rustc_trait_selection::traits::select::SelectionContext::evaluate_trait_predicate_recursively
  17: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively::{{closure}}
  18: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively
  19: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicates_recursively
  20: rustc_infer::infer::InferCtxt::probe
  21: rustc_trait_selection::traits::select::SelectionContext::evaluate_candidate
  22: <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::try_fold
  23: <core::iter::adapters::ResultShunt<I,E> as core::iter::traits::iterator::Iterator>::next
  24: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
  25: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation_no_cache
  26: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  27: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation
  28: rustc_trait_selection::traits::select::SelectionContext::evaluate_stack
  29: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  30: rustc_trait_selection::traits::select::SelectionContext::evaluate_trait_predicate_recursively
  31: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively::{{closure}}
  32: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively
  33: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicates_recursively
  34: rustc_infer::infer::InferCtxt::probe
  35: rustc_trait_selection::traits::select::SelectionContext::evaluate_candidate
  36: <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::try_fold
  37: <core::iter::adapters::ResultShunt<I,E> as core::iter::traits::iterator::Iterator>::next
  38: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
  39: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation_no_cache
  40: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  41: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation
  42: rustc_trait_selection::traits::select::SelectionContext::evaluate_stack
  43: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  44: rustc_trait_selection::traits::select::SelectionContext::evaluate_trait_predicate_recursively
  45: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively::{{closure}}
  46: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively
  47: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicates_recursively
  48: rustc_infer::infer::InferCtxt::probe
  49: rustc_trait_selection::traits::select::SelectionContext::evaluate_candidate
  50: <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::try_fold
  51: <core::iter::adapters::ResultShunt<I,E> as core::iter::traits::iterator::Iterator>::next
  52: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
  53: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation_no_cache
  54: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  55: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation
  56: rustc_trait_selection::traits::select::SelectionContext::evaluate_stack
  57: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  58: rustc_trait_selection::traits::select::SelectionContext::evaluate_trait_predicate_recursively
  59: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively::{{closure}}
  60: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively
  61: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicates_recursively
  62: rustc_infer::infer::InferCtxt::probe
  63: rustc_trait_selection::traits::select::SelectionContext::evaluate_candidate
  64: <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::try_fold
  65: <core::iter::adapters::ResultShunt<I,E> as core::iter::traits::iterator::Iterator>::next
  66: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
  67: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation_no_cache
  68: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  69: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation
  70: rustc_trait_selection::traits::select::SelectionContext::evaluate_stack
  71: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  72: rustc_trait_selection::traits::select::SelectionContext::evaluate_trait_predicate_recursively
  73: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively::{{closure}}
  74: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively
  75: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicates_recursively
  76: rustc_infer::infer::InferCtxt::probe
  77: rustc_trait_selection::traits::select::SelectionContext::evaluate_candidate
  78: <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::try_fold
  79: <core::iter::adapters::ResultShunt<I,E> as core::iter::traits::iterator::Iterator>::next
  80: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
  81: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation_no_cache
  82: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  83: rustc_trait_selection::traits::select::candidate_assembly::<impl rustc_trait_selection::traits::select::SelectionContext>::candidate_from_obligation
  84: rustc_trait_selection::traits::select::SelectionContext::evaluate_stack
  85: rustc_query_system::dep_graph::graph::DepGraph<K>::with_anon_task
  86: rustc_trait_selection::traits::select::SelectionContext::evaluate_trait_predicate_recursively
  87: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively::{{closure}}
  88: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicate_recursively
  89: rustc_trait_selection::traits::select::SelectionContext::evaluate_predicates_recursively
  90: rustc_infer::infer::InferCtxt::probe
  91: rustc_trait_selection::traits::select::SelectionContext::evaluate_candidate
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

error: internal compiler error: unexpected panic

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.54.0-nightly (770792ff8 2021-05-07) running on x86_64-apple-darwin

note: compiler flags: -Z treat-err-as-bug=1 --crate-type lib

query stack during panic:
#0 [typeck] type-checking `<impl at bug.rs:6:1: 8:2>::foo`
#1 [typeck_item_bodies] type-checking all item bodies
#2 [analysis] running analysis passes on this crate
end of query stack

Meta

This is what I used for the backtrace. I've reproduced the error in many versions though, so I don't think it's environment specific or a recent regression.

rustc --version --verbose:

rustc 1.54.0-nightly (770792ff8 2021-05-07)
binary: rustc
commit-hash: 770792ff8d1ec542e78e77876ac936f43ffb8e05
commit-date: 2021-05-07
host: x86_64-apple-darwin
release: 1.54.0-nightly
LLVM version: 12.0.0

[apiraino]

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-medium

[e2-71828]

Here's an URLO post that may contain another repro for this bug.

[hhirtz]

This also fails on stable 1.55:

trait Foo { fn foo(self); }

struct S;
impl Foo for &S { fn foo(self) {} } // just to prove there is a way to bottom out

impl<'a, T> Foo for &'a Vec<T> where &'a T: Foo {
    fn foo(self) {}
}

fn array<'a, T>(a: &'a [T]) where &'a T: Foo {}

pub fn f() {
    let g = [1, 2, 3];
    array(&g);
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=dc9117e13d9f0fd6ddc8931595c705c1

[cmpute]

Related: #39959