Hang with weird trait requirement

[jruderman]

Found with a modified fuzz-rustc.

Code

This input effectively hangs the compiler during item_types_checking / trait selection.

fn f<B>(x: Vec<[[[B; 1]; 1]; 1]>) -> impl PartialEq<B> {
    x
}

fn main() {}

Time complexity

The time spent increases exponentially(?) with the complexity of type x and with the recursion_limit setting.

Setting	Time to reject
#![recursion_limit = "16"]	0.6 sec
#![recursion_limit = "32"]	3.5 sec
#![recursion_limit = "48"]	107 sec
#![recursion_limit = "128"] (default)	Impatience prevailed

Regression

Regression in nightly-2022-05-28, from #96046. At the same time, the error message changed from E0275 to E0277.

Error before 2022-05-28

E0275: An evaluation of a trait requirement overflowed

error[E0275]: overflow evaluating the requirement `[&&[Vec<&&[&&[_]], _>]]: PartialEq<[_]>`
  |
  = help: consider increasing the recursion limit by adding a `#![recursion_limit = "96"]` attribute to your crate (`main`)
  = note: required because of the requirements on the impl of `PartialEq<&[_]>` for `&[&&[Vec<&&[&&[_]], _>]]`
  = note: 47 redundant requirements hidden
  = note: required because of the requirements on the impl of `PartialEq<Vec<&[&[&[Vec<&[&[&[Vec<&[&[&&[Vec<&[&[&&[Vec<&[&&[&&[Vec<&[&&[&&[Vec<&&[&&[_]], _>]]; _], _>]]], _>]; _]], _>]]], _>; _]]], _>]]], _>>` for `Vec<[[[Vec<&[&[&[Vec<&[&[&[Vec<&[&[&&[Vec<&[&[&&[Vec<&[&&[&&[Vec<&[&&[&&[Vec<&&[&&[_]], _>]]; _], _>]]], _>]; _]], _>]]], _>; _]]], _>]]], _>; 1]; 1]; 1]>`

Current error

E0277: trait requirement not satisfied

error[E0277]: can't compare `Vec<[[[B; 1]; 1]; 1]>` with `B`
 --> input.rs:3:38
  |
3 | fn f<B>(x: Vec<[[[B; 1]; 1]; 1]>) -> impl PartialEq<B> {
  |                                      ^^^^^^^^^^^^^^^^^ no implementation for `Vec<[[[B; 1]; 1]; 1]> == B`
4 |     x
  |     - return type was inferred to be `Vec<[[[B; 1]; 1]; 1]>` here
  |
  = help: the trait `PartialEq<B>` is not implemented for `Vec<[[[B; 1]; 1]; 1]>`
help: consider introducing a `where` clause, but there might be an alternative better way to express this requirement
  |
3 | fn f<B>(x: Vec<[[[B; 1]; 1]; 1]>) -> impl PartialEq<B> where Vec<[[[B; 1]; 1]; 1]>: PartialEq<B> {
  |                                                        +++++++++++++++++++++++++++++++++++++++++

Version

rustc --version --verbose:

rustc 1.67.0-nightly (85f4f41de 2022-11-08)
binary: rustc
commit-hash: 85f4f41deb1557ca8ab228319d33003dd2f20f45
commit-date: 2022-11-08
host: x86_64-apple-darwin
release: 1.67.0-nightly
LLVM version: 15.0.4

@rustbot label +I-compiletime +I-hang

[estebank]

cc @compiler-errors I believe this might related to what you were looking at recently

[compiler-errors]

Hm, don't think so? This doesn't have to with opaques that have higher-ranked (lifetime) vars in their substs.

[estebank]

Ah! Fair enough, I misremembered what you were working on :)

[compiler-errors]

This doesn't even have to do with impl Trait -- requiring the bound Vec<[[[B; 1]; 1]; 1]>: PartialEq<B> anywhere causes the hanging, e.g.:

#![recursion_limit = "48"]

fn f<B>(x: Vec<[[[B; 1]; 1]; 1]>) {
    is_eq::<_, B>(x);
}

fn is_eq<T: PartialEq<B>, B>(_: T) {}

fn main() {}

I'll look into it regardless.