Rollup merge of #146980 - hkBst:hir-analysis-1, r=jdonszelmann

simplify setup_constraining_predicates, and note it is potentially cubic

1 files changed, 25 insertions, 28 deletions

diff --git a/compiler/rustc_hir_analysis/src/constrained_generic_params.rs b/compiler/rustc_hir_analysis/src/constrained_generic_params.rs
index 2a633810cd7..f8d0ea3e7bf 100644
--- a/compiler/rustc_hir_analysis/src/constrained_generic_params.rs
+++ b/compiler/rustc_hir_analysis/src/constrained_generic_params.rs
@@ -167,15 +167,20 @@ pub(crate) fn setup_constraining_predicates<'tcx>(
     // which is `O(nt)` where `t` is the depth of type-parameter constraints,
     // remembering that `t` should be less than 7 in practice.
     //
+    // FIXME(hkBst): the big-O bound above would be accurate for the number
+    // of calls to `parameters_for`, which itself is some O(complexity of type).
+    // That would make this potentially cubic instead of merely quadratic...
+    // ...unless we cache those `parameters_for` calls.
+    //
     // Basically, I iterate over all projections and swap every
     // "ready" projection to the start of the list, such that
     // all of the projections before `i` are topologically sorted
     // and constrain all the parameters in `input_parameters`.
     //
-    // In the example, `input_parameters` starts by containing `U` - which
-    // is constrained by the trait-ref - and so on the first pass we
+    // In the first example, `input_parameters` starts by containing `U`,
+    // which is constrained by the self type `U`. Then, on the first pass we
     // observe that `<U as Iterator>::Item = T` is a "ready" projection that
-    // constrains `T` and swap it to front. As it is the sole projection,
+    // constrains `T` and swap it to the front. As it is the sole projection,
     // no more swaps can take place afterwards, with the result being
     //   * <U as Iterator>::Item = T
     //   * T: Debug
@@ -193,33 +198,25 @@ pub(crate) fn setup_constraining_predicates<'tcx>(
         for j in i..predicates.len() {
             // Note that we don't have to care about binders here,
             // as the impl trait ref never contains any late-bound regions.
-            if let ty::ClauseKind::Projection(projection) = predicates[j].0.kind().skip_binder() {
-                // Special case: watch out for some kind of sneaky attempt
-                // to project out an associated type defined by this very
-                // trait.
-                let unbound_trait_ref = projection.projection_term.trait_ref(tcx);
-                if Some(unbound_trait_ref) == impl_trait_ref {
-                    continue;
-                }
-
-                // A projection depends on its input types and determines its output
-                // type. For example, if we have
-                //     `<<T as Bar>::Baz as Iterator>::Output = <U as Iterator>::Output`
-                // Then the projection only applies if `T` is known, but it still
-                // does not determine `U`.
-                let inputs = parameters_for(tcx, projection.projection_term, true);
-                let relies_only_on_inputs = inputs.iter().all(|p| input_parameters.contains(p));
-                if !relies_only_on_inputs {
-                    continue;
-                }
+            if let ty::ClauseKind::Projection(projection) = predicates[j].0.kind().skip_binder() &&
+
+            // Special case: watch out for some kind of sneaky attempt to
+            // project out an associated type defined by this very trait.
+            !impl_trait_ref.is_some_and(|t| t == projection.projection_term.trait_ref(tcx)) &&
+
+            // A projection depends on its input types and determines its output
+            // type. For example, if we have
+            //     `<<T as Bar>::Baz as Iterator>::Output = <U as Iterator>::Output`
+            // then the projection only applies if `T` is known, but it still
+            // does not determine `U`.
+                parameters_for(tcx, projection.projection_term, true).iter().all(|p| input_parameters.contains(p))
+            {
                 input_parameters.extend(parameters_for(tcx, projection.term, false));
-            } else {
-                continue;
+
+                predicates.swap(i, j);
+                i += 1;
+                changed = true;
             }
-            // fancy control flow to bypass borrow checker
-            predicates.swap(i, j);
-            i += 1;
-            changed = true;
         }
         debug!(
             "setup_constraining_predicates: predicates={:?} \