Better handling for exponential-sized types in misc places

Mostly to fix ui/issues/issue-37311-type-length-limit/issue-37311.rs.

Most parts of the compiler can handle deeply nested types with a lot
of duplicates just fine, but some parts still attempt to naively
traverse type tree.

Before such problems were caught by type length limit check,
but now these places will have to be changed to handle
duplicated types gracefully.

8 files changed, 15 insertions, 11 deletions

diff --git a/src/test/ui/infinite/infinite-instantiation.stderr b/src/test/ui/infinite/infinite-instantiation.stderr
index 1aaefea9f04..d27d14842ce 100644
--- a/src/test/ui/infinite/infinite-instantiation.stderr
+++ b/src/test/ui/infinite/infinite-instantiation.stderr
@@ -1,4 +1,4 @@
-error: reached the recursion limit while instantiating `function::<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<usize>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
+error: reached the recursion limit while instantiating `function::<Option<Option<Option<...>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
   --> $DIR/infinite-instantiation.rs:21:9
    |
 LL |         function(counter - 1, t.to_option());
diff --git a/src/test/ui/issues/issue-37311-type-length-limit/issue-37311.rs b/src/test/ui/issues/issue-37311-type-length-limit/issue-37311.rs
index fec4b171536..d3d5863ddb3 100644
--- a/src/test/ui/issues/issue-37311-type-length-limit/issue-37311.rs
+++ b/src/test/ui/issues/issue-37311-type-length-limit/issue-37311.rs
@@ -12,8 +12,8 @@ trait Foo {
 
 impl<T> Foo for T {
     #[allow(unconditional_recursion)]
-    fn recurse(&self) { //~ ERROR reached the type-length limit
-        (self, self).recurse();
+    fn recurse(&self) {
+        (self, self).recurse(); //~ ERROR reached the recursion limit
     }
 }
 
diff --git a/src/test/ui/issues/issue-37311-type-length-limit/issue-37311.stderr b/src/test/ui/issues/issue-37311-type-length-limit/issue-37311.stderr
index 6229d90d4b4..a94f190d6b2 100644
--- a/src/test/ui/issues/issue-37311-type-length-limit/issue-37311.stderr
+++ b/src/test/ui/issues/issue-37311-type-length-limit/issue-37311.stderr
@@ -1,10 +1,14 @@
-error: reached the type-length limit while instantiating `<(&(&(&(&(&(&(&(&(&(&(&(&(&(&(&(...))))))))))))))) as Foo>::recurse`
+error: reached the recursion limit while instantiating `<(&(&(&(&(&(&(&(&(&(&(&(&(&(&(&(.....), ...), ...) as Foo>::recurse`
+  --> $DIR/issue-37311.rs:16:9
+   |
+LL |         (self, self).recurse();
+   |         ^^^^^^^^^^^^^^^^^^^^^^
+   |
+note: `<T as Foo>::recurse` defined here
   --> $DIR/issue-37311.rs:15:5
    |
 LL |     fn recurse(&self) {
    |     ^^^^^^^^^^^^^^^^^
-   |
-   = note: consider adding a `#![type_length_limit="2097149"]` attribute to your crate
 
 error: aborting due to previous error
 
diff --git a/src/test/ui/issues/issue-67552.stderr b/src/test/ui/issues/issue-67552.stderr
index 8243e52039d..f3e73399b57 100644
--- a/src/test/ui/issues/issue-67552.stderr
+++ b/src/test/ui/issues/issue-67552.stderr
@@ -1,4 +1,4 @@
-error: reached the recursion limit while instantiating `rec::<&mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut &mut Empty>`
+error: reached the recursion limit while instantiating `rec::<&mut &mut &mut &mut &mut &... &mut &mut &mut &mut &mut Empty>`
   --> $DIR/issue-67552.rs:27:9
    |
 LL |         rec(identity(&mut it))
diff --git a/src/test/ui/issues/issue-8727.stderr b/src/test/ui/issues/issue-8727.stderr
index dd57e69f2cf..279e3ffbb4a 100644
--- a/src/test/ui/issues/issue-8727.stderr
+++ b/src/test/ui/issues/issue-8727.stderr
@@ -9,7 +9,7 @@ LL |     generic::<Option<T>>();
    = note: `#[warn(unconditional_recursion)]` on by default
    = help: a `loop` may express intention better if this is on purpose
 
-error: reached the recursion limit while instantiating `generic::<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<Option<i32>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
+error: reached the recursion limit while instantiating `generic::<Option<Option<Option<O...>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
   --> $DIR/issue-8727.rs:7:5
    |
 LL |     generic::<Option<T>>();
diff --git a/src/test/ui/recursion/issue-38591-non-regular-dropck-recursion.stderr b/src/test/ui/recursion/issue-38591-non-regular-dropck-recursion.stderr
index 536e26d2955..4d77b3d295c 100644
--- a/src/test/ui/recursion/issue-38591-non-regular-dropck-recursion.stderr
+++ b/src/test/ui/recursion/issue-38591-non-regular-dropck-recursion.stderr
@@ -1,4 +1,4 @@
-error: reached the recursion limit while instantiating `drop_in_place::<S<fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(u32))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))>> - shim(Some(S<fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(fn(u32))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))>))`
+error: reached the recursion limit while instantiating `drop_in_place::<S<fn(fn(fn(fn(fn...)))))))))))))))))))))))))))))>))`
   --> $SRC_DIR/core/src/ptr/mod.rs:LL:COL
    |
 LL | / pub unsafe fn drop_in_place<T: ?Sized>(to_drop: *mut T) {
diff --git a/src/test/ui/recursion/recursion.stderr b/src/test/ui/recursion/recursion.stderr
index db4c99eeb8b..085bf82ef8b 100644
--- a/src/test/ui/recursion/recursion.stderr
+++ b/src/test/ui/recursion/recursion.stderr
@@ -1,4 +1,4 @@
-error: reached the recursion limit while instantiating `test::<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Cons<Nil>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
+error: reached the recursion limit while instantiating `test::<Cons<Cons<Cons<Cons<Cons<...>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
   --> $DIR/recursion.rs:17:11
    |
 LL |     _ => {test (n-1, i+1, Cons {head:2*i+1, tail:first}, Cons{head:i*i, tail:second})}
diff --git a/src/test/ui/type_length_limit.stderr b/src/test/ui/type_length_limit.stderr
index e8fddfd4ece..cf3d64d734b 100644
--- a/src/test/ui/type_length_limit.stderr
+++ b/src/test/ui/type_length_limit.stderr
@@ -1,4 +1,4 @@
-error: reached the type-length limit while instantiating `std::mem::drop::<Option<((((((G,... G), (G, G, G), (G, G, G))))))>>`
+error: reached the type-length limit while instantiating `std::mem::drop::<Option<((((...,....., ...), ..., ...), ..., ...)>>`
   --> $SRC_DIR/core/src/mem/mod.rs:LL:COL
    |
 LL | pub fn drop<T>(_x: T) {}