Auto merge of #127438 - compiler-errors:compute-outlives-visitor, r=lcnr

Make `push_outlives_components` into a `TypeVisitor`

This involves removing the `visited: &mut SsoHashSet<GenericArg<'tcx>>` that is being passed around the `VerifyBoundCx`. The fact that we were using it when decomposing different type tests seems sketchy, so I don't think, though it may technically result in us registering more redundant outlives components 🤷

I did end up deleting some of the comments that referred back to RFC 1214 during this refactor. I can add them back if you think they were useful.

r? lcnr

3 files changed, 127 insertions, 247 deletions

diff --git a/compiler/rustc_infer/src/infer/outlives/obligations.rs b/compiler/rustc_infer/src/infer/outlives/obligations.rs
index 9bb5f775e4a..d82ae7b4fb8 100644
--- a/compiler/rustc_infer/src/infer/outlives/obligations.rs
+++ b/compiler/rustc_infer/src/infer/outlives/obligations.rs
@@ -471,7 +471,7 @@ where
         // projection outlive; in some cases, this may add insufficient
         // edges into the inference graph, leading to inference failures
         // even though a satisfactory solution exists.
-        let verify_bound = self.verify_bound.alias_bound(alias_ty, &mut Default::default());
+        let verify_bound = self.verify_bound.alias_bound(alias_ty);
         debug!("alias_must_outlive: pushing {:?}", verify_bound);
         self.delegate.push_verify(origin, GenericKind::Alias(alias_ty), region, verify_bound);
     }
diff --git a/compiler/rustc_infer/src/infer/outlives/verify.rs b/compiler/rustc_infer/src/infer/outlives/verify.rs
index ad102dfcc1f..2392a82025a 100644
--- a/compiler/rustc_infer/src/infer/outlives/verify.rs
+++ b/compiler/rustc_infer/src/infer/outlives/verify.rs
@@ -1,8 +1,6 @@
 use crate::infer::outlives::env::RegionBoundPairs;
 use crate::infer::region_constraints::VerifyIfEq;
 use crate::infer::{GenericKind, VerifyBound};
-use rustc_data_structures::sso::SsoHashSet;
-use rustc_middle::ty::GenericArg;
 use rustc_middle::ty::{self, OutlivesPredicate, Ty, TyCtxt};
 use rustc_type_ir::outlives::{compute_alias_components_recursive, Component};
 
@@ -99,12 +97,8 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> {
         self.declared_generic_bounds_from_env_for_erased_ty(erased_alias_ty)
     }
 
-    #[instrument(level = "debug", skip(self, visited))]
-    pub fn alias_bound(
-        &self,
-        alias_ty: ty::AliasTy<'tcx>,
-        visited: &mut SsoHashSet<GenericArg<'tcx>>,
-    ) -> VerifyBound<'tcx> {
+    #[instrument(level = "debug", skip(self))]
+    pub fn alias_bound(&self, alias_ty: ty::AliasTy<'tcx>) -> VerifyBound<'tcx> {
         let alias_ty_as_ty = alias_ty.to_ty(self.tcx);
 
         // Search the env for where clauses like `P: 'a`.
@@ -130,21 +124,17 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> {
         // see the extensive comment in projection_must_outlive
         let recursive_bound = {
             let mut components = smallvec![];
-            compute_alias_components_recursive(self.tcx, alias_ty_as_ty, &mut components, visited);
-            self.bound_from_components(&components, visited)
+            compute_alias_components_recursive(self.tcx, alias_ty_as_ty, &mut components);
+            self.bound_from_components(&components)
         };
 
         VerifyBound::AnyBound(env_bounds.chain(definition_bounds).collect()).or(recursive_bound)
     }
 
-    fn bound_from_components(
-        &self,
-        components: &[Component<TyCtxt<'tcx>>],
-        visited: &mut SsoHashSet<GenericArg<'tcx>>,
-    ) -> VerifyBound<'tcx> {
+    fn bound_from_components(&self, components: &[Component<TyCtxt<'tcx>>]) -> VerifyBound<'tcx> {
         let mut bounds = components
             .iter()
-            .map(|component| self.bound_from_single_component(component, visited))
+            .map(|component| self.bound_from_single_component(component))
             // Remove bounds that must hold, since they are not interesting.
             .filter(|bound| !bound.must_hold());
 
@@ -159,7 +149,6 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> {
     fn bound_from_single_component(
         &self,
         component: &Component<TyCtxt<'tcx>>,
-        visited: &mut SsoHashSet<GenericArg<'tcx>>,
     ) -> VerifyBound<'tcx> {
         match *component {
             Component::Region(lt) => VerifyBound::OutlivedBy(lt),
@@ -167,10 +156,8 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> {
             Component::Placeholder(placeholder_ty) => {
                 self.param_or_placeholder_bound(Ty::new_placeholder(self.tcx, placeholder_ty))
             }
-            Component::Alias(alias_ty) => self.alias_bound(alias_ty, visited),
-            Component::EscapingAlias(ref components) => {
-                self.bound_from_components(components, visited)
-            }
+            Component::Alias(alias_ty) => self.alias_bound(alias_ty),
+            Component::EscapingAlias(ref components) => self.bound_from_components(components),
             Component::UnresolvedInferenceVariable(v) => {
                 // Ignore this, we presume it will yield an error later, since
                 // if a type variable is not resolved by this point it never
diff --git a/compiler/rustc_type_ir/src/outlives.rs b/compiler/rustc_type_ir/src/outlives.rs
index 61dfa2643d8..10b6f3355d9 100644
--- a/compiler/rustc_type_ir/src/outlives.rs
+++ b/compiler/rustc_type_ir/src/outlives.rs
@@ -3,11 +3,10 @@
 //! RFC for reference.
 
 use smallvec::{smallvec, SmallVec};
-use tracing::debug;
 
 use crate::data_structures::SsoHashSet;
 use crate::inherent::*;
-use crate::visit::TypeVisitableExt as _;
+use crate::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableExt as _, TypeVisitor};
 use crate::{self as ty, Interner};
 
 #[derive(derivative::Derivative)]
@@ -56,216 +55,148 @@ pub enum Component<I: Interner> {
 /// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**.
 pub fn push_outlives_components<I: Interner>(
     tcx: I,
-    ty0: I::Ty,
+    ty: I::Ty,
     out: &mut SmallVec<[Component<I>; 4]>,
 ) {
-    let mut visited = SsoHashSet::new();
-    compute_components_for_ty(tcx, ty0, out, &mut visited);
-    debug!("components({:?}) = {:?}", ty0, out);
+    ty.visit_with(&mut OutlivesCollector { tcx, out, visited: Default::default() });
 }
 
-fn compute_components_for_arg<I: Interner>(
+struct OutlivesCollector<'a, I: Interner> {
     tcx: I,
-    arg: I::GenericArg,
-    out: &mut SmallVec<[Component<I>; 4]>,
-    visited: &mut SsoHashSet<I::GenericArg>,
-) {
-    match arg.kind() {
-        ty::GenericArgKind::Type(ty) => {
-            compute_components_for_ty(tcx, ty, out, visited);
-        }
-        ty::GenericArgKind::Lifetime(lt) => {
-            compute_components_for_lt(lt, out);
-        }
-        ty::GenericArgKind::Const(ct) => {
-            compute_components_for_const(tcx, ct, out, visited);
-        }
-    }
+    out: &'a mut SmallVec<[Component<I>; 4]>,
+    visited: SsoHashSet<I::Ty>,
 }
 
-fn compute_components_for_ty<I: Interner>(
-    tcx: I,
-    ty: I::Ty,
-    out: &mut SmallVec<[Component<I>; 4]>,
-    visited: &mut SsoHashSet<I::GenericArg>,
-) {
-    if !visited.insert(ty.into()) {
-        return;
-    }
-    // Descend through the types, looking for the various "base"
-    // components and collecting them into `out`. This is not written
-    // with `collect()` because of the need to sometimes skip subtrees
-    // in the `subtys` iterator (e.g., when encountering a
-    // projection).
-    match ty.kind() {
-        ty::FnDef(_, args) => {
-            // HACK(eddyb) ignore lifetimes found shallowly in `args`.
-            // This is inconsistent with `ty::Adt` (including all args)
-            // and with `ty::Closure` (ignoring all args other than
-            // upvars, of which a `ty::FnDef` doesn't have any), but
-            // consistent with previous (accidental) behavior.
-            // See https://github.com/rust-lang/rust/issues/70917
-            // for further background and discussion.
-            for child in args.iter() {
-                match child.kind() {
-                    ty::GenericArgKind::Type(ty) => {
-                        compute_components_for_ty(tcx, ty, out, visited);
-                    }
-                    ty::GenericArgKind::Lifetime(_) => {}
-                    ty::GenericArgKind::Const(ct) => {
-                        compute_components_for_const(tcx, ct, out, visited);
+impl<I: Interner> TypeVisitor<I> for OutlivesCollector<'_, I> {
+    fn visit_ty(&mut self, ty: I::Ty) -> Self::Result {
+        if !self.visited.insert(ty) {
+            return;
+        }
+        // Descend through the types, looking for the various "base"
+        // components and collecting them into `out`. This is not written
+        // with `collect()` because of the need to sometimes skip subtrees
+        // in the `subtys` iterator (e.g., when encountering a
+        // projection).
+        match ty.kind() {
+            ty::FnDef(_, args) => {
+                // HACK(eddyb) ignore lifetimes found shallowly in `args`.
+                // This is inconsistent with `ty::Adt` (including all args)
+                // and with `ty::Closure` (ignoring all args other than
+                // upvars, of which a `ty::FnDef` doesn't have any), but
+                // consistent with previous (accidental) behavior.
+                // See https://github.com/rust-lang/rust/issues/70917
+                // for further background and discussion.
+                for child in args.iter() {
+                    match child.kind() {
+                        ty::GenericArgKind::Lifetime(_) => {}
+                        ty::GenericArgKind::Type(_) | ty::GenericArgKind::Const(_) => {
+                            child.visit_with(self);
+                        }
                     }
                 }
             }
-        }
-
-        ty::Pat(element, _) | ty::Array(element, _) => {
-            compute_components_for_ty(tcx, element, out, visited);
-        }
-
-        ty::Closure(_, args) => {
-            let tupled_ty = args.as_closure().tupled_upvars_ty();
-            compute_components_for_ty(tcx, tupled_ty, out, visited);
-        }
-
-        ty::CoroutineClosure(_, args) => {
-            let tupled_ty = args.as_coroutine_closure().tupled_upvars_ty();
-            compute_components_for_ty(tcx, tupled_ty, out, visited);
-        }
 
-        ty::Coroutine(_, args) => {
-            // Same as the closure case
-            let tupled_ty = args.as_coroutine().tupled_upvars_ty();
-            compute_components_for_ty(tcx, tupled_ty, out, visited);
+            ty::Closure(_, args) => {
+                args.as_closure().tupled_upvars_ty().visit_with(self);
+            }
 
-            // We ignore regions in the coroutine interior as we don't
-            // want these to affect region inference
-        }
+            ty::CoroutineClosure(_, args) => {
+                args.as_coroutine_closure().tupled_upvars_ty().visit_with(self);
+            }
 
-        // All regions are bound inside a witness, and we don't emit
-        // higher-ranked outlives components currently.
-        ty::CoroutineWitness(..) => {},
+            ty::Coroutine(_, args) => {
+                args.as_coroutine().tupled_upvars_ty().visit_with(self);
 
-        // OutlivesTypeParameterEnv -- the actual checking that `X:'a`
-        // is implied by the environment is done in regionck.
-        ty::Param(p) => {
-            out.push(Component::Param(p));
-        }
+                // We ignore regions in the coroutine interior as we don't
+                // want these to affect region inference
+            }
 
-        ty::Placeholder(p) => {
-            out.push(Component::Placeholder(p));
-        }
+            // All regions are bound inside a witness, and we don't emit
+            // higher-ranked outlives components currently.
+            ty::CoroutineWitness(..) => {}
 
-        // For projections, we prefer to generate an obligation like
-        // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the
-        // regionck more ways to prove that it holds. However,
-        // regionck is not (at least currently) prepared to deal with
-        // higher-ranked regions that may appear in the
-        // trait-ref. Therefore, if we see any higher-ranked regions,
-        // we simply fallback to the most restrictive rule, which
-        // requires that `Pi: 'a` for all `i`.
-        ty::Alias(_, alias_ty) => {
-            if !alias_ty.has_escaping_bound_vars() {
-                // best case: no escaping regions, so push the
-                // projection and skip the subtree (thus generating no
-                // constraints for Pi). This defers the choice between
-                // the rules OutlivesProjectionEnv,
-                // OutlivesProjectionTraitDef, and
-                // OutlivesProjectionComponents to regionck.
-                out.push(Component::Alias(alias_ty));
-            } else {
-                // fallback case: hard code
-                // OutlivesProjectionComponents. Continue walking
-                // through and constrain Pi.
-                let mut subcomponents = smallvec![];
-                let mut subvisited = SsoHashSet::new();
-                compute_alias_components_recursive(tcx, ty, &mut subcomponents, &mut subvisited);
-                out.push(Component::EscapingAlias(subcomponents.into_iter().collect()));
+            // OutlivesTypeParameterEnv -- the actual checking that `X:'a`
+            // is implied by the environment is done in regionck.
+            ty::Param(p) => {
+                self.out.push(Component::Param(p));
             }
-        }
 
-        // We assume that inference variables are fully resolved.
-        // So, if we encounter an inference variable, just record
-        // the unresolved variable as a component.
-        ty::Infer(infer_ty) => {
-            out.push(Component::UnresolvedInferenceVariable(infer_ty));
-        }
-
-        // Most types do not introduce any region binders, nor
-        // involve any other subtle cases, and so the WF relation
-        // simply constraints any regions referenced directly by
-        // the type and then visits the types that are lexically
-        // contained within. (The comments refer to relevant rules
-        // from RFC1214.)
+            ty::Placeholder(p) => {
+                self.out.push(Component::Placeholder(p));
+            }
 
-        ty::Bool |            // OutlivesScalar
-        ty::Char |            // OutlivesScalar
-        ty::Int(..) |         // OutlivesScalar
-        ty::Uint(..) |        // OutlivesScalar
-        ty::Float(..) |       // OutlivesScalar
-        ty::Never |           // OutlivesScalar
-        ty::Foreign(..) |     // OutlivesNominalType
-        ty::Str |             // OutlivesScalar (ish)
-        ty::Bound(..) |
-        ty::Error(_) => {
-            // Trivial.
-        }
+            // For projections, we prefer to generate an obligation like
+            // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the
+            // regionck more ways to prove that it holds. However,
+            // regionck is not (at least currently) prepared to deal with
+            // higher-ranked regions that may appear in the
+            // trait-ref. Therefore, if we see any higher-ranked regions,
+            // we simply fallback to the most restrictive rule, which
+            // requires that `Pi: 'a` for all `i`.
+            ty::Alias(_, alias_ty) => {
+                if !alias_ty.has_escaping_bound_vars() {
+                    // best case: no escaping regions, so push the
+                    // projection and skip the subtree (thus generating no
+                    // constraints for Pi). This defers the choice between
+                    // the rules OutlivesProjectionEnv,
+                    // OutlivesProjectionTraitDef, and
+                    // OutlivesProjectionComponents to regionck.
+                    self.out.push(Component::Alias(alias_ty));
+                } else {
+                    // fallback case: hard code
+                    // OutlivesProjectionComponents. Continue walking
+                    // through and constrain Pi.
+                    let mut subcomponents = smallvec![];
+                    compute_alias_components_recursive(self.tcx, ty, &mut subcomponents);
+                    self.out.push(Component::EscapingAlias(subcomponents.into_iter().collect()));
+                }
+            }
 
-        // OutlivesNominalType
-        ty::Adt(_, args) => {
-            for arg in args.iter() {
-                compute_components_for_arg(tcx, arg, out, visited);
+            // We assume that inference variables are fully resolved.
+            // So, if we encounter an inference variable, just record
+            // the unresolved variable as a component.
+            ty::Infer(infer_ty) => {
+                self.out.push(Component::UnresolvedInferenceVariable(infer_ty));
             }
-        }
 
-        // OutlivesNominalType
-        ty::Slice(ty) |
-        ty::RawPtr(ty, _) => {
-            compute_components_for_ty(tcx, ty, out, visited);
-        }
-        ty::Tuple(tys) => {
-            for ty in tys.iter() {
-                compute_components_for_ty(tcx, ty, out, visited);
+            // Most types do not introduce any region binders, nor
+            // involve any other subtle cases, and so the WF relation
+            // simply constraints any regions referenced directly by
+            // the type and then visits the types that are lexically
+            // contained within.
+            ty::Bool
+            | ty::Char
+            | ty::Int(_)
+            | ty::Uint(_)
+            | ty::Float(_)
+            | ty::Str
+            | ty::Never
+            | ty::Error(_) => {
+                // Trivial
             }
-        }
 
-        // OutlivesReference
-        ty::Ref(lt, ty, _) => {
-            compute_components_for_lt(lt, out);
-            compute_components_for_ty(tcx, ty, out, visited);
-        }
+            ty::Bound(_, _) => {
+                // FIXME: Bound vars matter here!
+            }
 
-        ty::Dynamic(preds, lt, _) => {
-            compute_components_for_lt(lt, out);
-            for pred in preds.iter() {
-                match pred.skip_binder() {
-                    ty::ExistentialPredicate::Trait(tr) => {
-                        for arg in tr.args.iter() {
-                            compute_components_for_arg(tcx, arg, out, visited);
-                        }
-                    }
-                    ty::ExistentialPredicate::Projection(proj) => {
-                        for arg in proj.args.iter() {
-                            compute_components_for_arg(tcx, arg, out, visited);
-                        }
-                        match proj.term.kind() {
-                            ty::TermKind::Ty(ty) => {
-                                compute_components_for_ty(tcx, ty, out, visited)
-                            }
-                            ty::TermKind::Const(ct) => {
-                                compute_components_for_const(tcx, ct, out, visited)
-                            }
-                        }
-                    }
-                    ty::ExistentialPredicate::AutoTrait(..) => {}
-                }
+            ty::Adt(_, _)
+            | ty::Foreign(_)
+            | ty::Array(_, _)
+            | ty::Pat(_, _)
+            | ty::Slice(_)
+            | ty::RawPtr(_, _)
+            | ty::Ref(_, _, _)
+            | ty::FnPtr(_)
+            | ty::Dynamic(_, _, _)
+            | ty::Tuple(_) => {
+                ty.super_visit_with(self);
             }
         }
+    }
 
-        ty::FnPtr(sig) => {
-            for ty in sig.skip_binder().inputs_and_output.iter() {
-                compute_components_for_ty(tcx, ty, out, visited);
-            }
+    fn visit_region(&mut self, lt: I::Region) -> Self::Result {
+        if !lt.is_bound() {
+            self.out.push(Component::Region(lt));
         }
     }
 }
@@ -278,7 +209,6 @@ pub fn compute_alias_components_recursive<I: Interner>(
     tcx: I,
     alias_ty: I::Ty,
     out: &mut SmallVec<[Component<I>; 4]>,
-    visited: &mut SsoHashSet<I::GenericArg>,
 ) {
     let ty::Alias(kind, alias_ty) = alias_ty.kind() else {
         unreachable!("can only call `compute_alias_components_recursive` on an alias type")
@@ -287,49 +217,12 @@ pub fn compute_alias_components_recursive<I: Interner>(
     let opt_variances =
         if kind == ty::Opaque { Some(tcx.variances_of(alias_ty.def_id)) } else { None };
 
+    let mut visitor = OutlivesCollector { tcx, out, visited: Default::default() };
+
     for (index, child) in alias_ty.args.iter().enumerate() {
         if opt_variances.and_then(|variances| variances.get(index)) == Some(ty::Bivariant) {
             continue;
         }
-        compute_components_for_arg(tcx, child, out, visited);
-    }
-}
-
-fn compute_components_for_lt<I: Interner>(lt: I::Region, out: &mut SmallVec<[Component<I>; 4]>) {
-    if !lt.is_bound() {
-        out.push(Component::Region(lt));
-    }
-}
-
-fn compute_components_for_const<I: Interner>(
-    tcx: I,
-    ct: I::Const,
-    out: &mut SmallVec<[Component<I>; 4]>,
-    visited: &mut SsoHashSet<I::GenericArg>,
-) {
-    if !visited.insert(ct.into()) {
-        return;
-    }
-    match ct.kind() {
-        ty::ConstKind::Param(_)
-        | ty::ConstKind::Bound(_, _)
-        | ty::ConstKind::Infer(_)
-        | ty::ConstKind::Placeholder(_)
-        | ty::ConstKind::Error(_) => {
-            // Trivial
-        }
-        ty::ConstKind::Expr(e) => {
-            for arg in e.args().iter() {
-                compute_components_for_arg(tcx, arg, out, visited);
-            }
-        }
-        ty::ConstKind::Value(ty, _) => {
-            compute_components_for_ty(tcx, ty, out, visited);
-        }
-        ty::ConstKind::Unevaluated(uv) => {
-            for arg in uv.args.iter() {
-                compute_components_for_arg(tcx, arg, out, visited);
-            }
-        }
+        child.visit_with(&mut visitor);
     }
 }