Auto merge of #68772 - matthewjasper:relate-opt, r=davidtwco

Avoid exponential behaviour when relating types

When equating bound types we check subtyping in both directions. Since closures are invariant in their substs, we end up comparing the two types an exponential number of times. If there are no bound variables this isn't needed.

Closes #68061

3 files changed, 42 insertions, 2 deletions

diff --git a/src/librustc/infer/equate.rs b/src/librustc/infer/equate.rs
index 4a41cdb1407..f192295c1aa 100644
--- a/src/librustc/infer/equate.rs
+++ b/src/librustc/infer/equate.rs
@@ -125,7 +125,13 @@ impl TypeRelation<'tcx> for Equate<'combine, 'infcx, 'tcx> {
     where
         T: Relate<'tcx>,
     {
-        self.fields.higher_ranked_sub(a, b, self.a_is_expected)?;
-        self.fields.higher_ranked_sub(b, a, self.a_is_expected)
+        if a.skip_binder().has_escaping_bound_vars() || b.skip_binder().has_escaping_bound_vars() {
+            self.fields.higher_ranked_sub(a, b, self.a_is_expected)?;
+            self.fields.higher_ranked_sub(b, a, self.a_is_expected)
+        } else {
+            // Fast path for the common case.
+            self.relate(a.skip_binder(), b.skip_binder())?;
+            return Ok(a.clone());
+        }
     }
 }
diff --git a/src/librustc/infer/nll_relate/mod.rs b/src/librustc/infer/nll_relate/mod.rs
index 6b53871b9e2..6af004f7776 100644
--- a/src/librustc/infer/nll_relate/mod.rs
+++ b/src/librustc/infer/nll_relate/mod.rs
@@ -529,6 +529,10 @@ where
             b = self.infcx.shallow_resolve(b);
         }
 
+        if a == b {
+            return Ok(a);
+        }
+
         match (&a.kind, &b.kind) {
             (_, &ty::Infer(ty::TyVar(vid))) => {
                 if D::forbid_inference_vars() {
@@ -638,6 +642,13 @@ where
 
         debug!("binders({:?}: {:?}, ambient_variance={:?})", a, b, self.ambient_variance);
 
+        if !a.skip_binder().has_escaping_bound_vars() && !b.skip_binder().has_escaping_bound_vars()
+        {
+            // Fast path for the common case.
+            self.relate(a.skip_binder(), b.skip_binder())?;
+            return Ok(a.clone());
+        }
+
         if self.ambient_covariance() {
             // Covariance, so we want `for<..> A <: for<..> B` --
             // therefore we compare any instantiation of A (i.e., A
diff --git a/src/test/ui/closures/deeply-nested_closures.rs b/src/test/ui/closures/deeply-nested_closures.rs
new file mode 100644
index 00000000000..a02684ee1de
--- /dev/null
+++ b/src/test/ui/closures/deeply-nested_closures.rs
@@ -0,0 +1,23 @@
+// Check that this can be compiled in a reasonable time.
+
+// build-pass
+
+fn main() {
+    // 96 nested closures
+    let x = ();
+    || || || || || || || ||
+    || || || || || || || ||
+    || || || || || || || ||
+    || || || || || || || ||
+
+    || || || || || || || ||
+    || || || || || || || ||
+    || || || || || || || ||
+    || || || || || || || ||
+
+    || || || || || || || ||
+    || || || || || || || ||
+    || || || || || || || ||
+    || || || || || || || ||
+    [&(), &x];
+}