Handle universe leaks by rewriting the constraint graph

This version is a squash-rebased version of a series
of exiermental commits, since large parts of them
were broken out into PR #125069.

It explicitly handles universe violations in higher-kinded
outlives constraints by adding extra outlives static constraints.

4 files changed, 111 insertions, 68 deletions

diff --git a/compiler/rustc_borrowck/src/constraints/mod.rs b/compiler/rustc_borrowck/src/constraints/mod.rs
index b54e05b2b34..9a76539f579 100644
--- a/compiler/rustc_borrowck/src/constraints/mod.rs
+++ b/compiler/rustc_borrowck/src/constraints/mod.rs
@@ -1,4 +1,6 @@
+use crate::region_infer::{ConstraintSccs, RegionDefinition, RegionTracker};
 use crate::type_check::Locations;
+use crate::universal_regions::UniversalRegions;
 use rustc_index::{IndexSlice, IndexVec};
 use rustc_middle::mir::ConstraintCategory;
 use rustc_middle::ty::{RegionVid, TyCtxt, VarianceDiagInfo};
@@ -48,6 +50,88 @@ impl<'tcx> OutlivesConstraintSet<'tcx> {
     ) -> &IndexSlice<OutlivesConstraintIndex, OutlivesConstraint<'tcx>> {
         &self.outlives
     }
+
+    /// Computes cycles (SCCs) in the graph of regions. In particular,
+    /// find all regions R1, R2 such that R1: R2 and R2: R1 and group
+    /// them into an SCC, and find the relationships between SCCs.
+    pub(crate) fn compute_sccs(
+        &self,
+        static_region: RegionVid,
+        definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>,
+    ) -> ConstraintSccs {
+        let constraint_graph = self.graph(definitions.len());
+        let region_graph = &constraint_graph.region_graph(self, static_region);
+        ConstraintSccs::new_with_annotation(&region_graph, |r| {
+            RegionTracker::new(r, &definitions[r])
+        })
+    }
+
+    /// This method handles universe errors by rewriting the constraint
+    /// graph. For each strongly connected component in the constraint
+    /// graph such that there is a series of constraints
+    ///    A: B: C: ... : X  where
+    /// A's universe is smaller than X's and A is a placeholder,
+    /// add A: 'static.
+    ///
+    /// For a more precise definition, see the documentation for
+    /// [`RegionTracker::has_incompatible_universes()`].
+    ///
+    /// Every constraint added by this method is an
+    /// `IllegalUniverse` constraint.
+    #[instrument(skip(self, universal_regions, definitions))]
+    pub(crate) fn add_outlives_static(
+        &mut self,
+        universal_regions: &UniversalRegions<'tcx>,
+        definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>,
+    ) -> ConstraintSccs {
+        let fr_static = universal_regions.fr_static;
+        let sccs = self.compute_sccs(fr_static, definitions);
+
+        // Changed to `true` if we added any constraints to `self` and need to
+        // recompute SCCs.
+        let mut added_constraints = false;
+
+        for scc in sccs.all_sccs() {
+            // No point in adding 'static: 'static!
+            // This micro-optimisation makes somewhat sense
+            // because static outlives *everything*.
+            if scc == sccs.scc(fr_static) {
+                continue;
+            }
+
+            let annotation = sccs.annotation(scc);
+
+            // If this SCC participates in a universe violation,
+            // e.g. if it reaches a region with a universe smaller than
+            // the largest region reached, add a requirement that it must
+            // outlive `'static`.
+            if annotation.has_incompatible_universes() {
+                // Optimisation opportunity: this will add more constraints than
+                // needed for correctness, since an SCC upstream of another with
+                // a universe violation will "infect" its downstream SCCs to also
+                // outlive static.
+                added_constraints = true;
+                let scc_representative_outlives_static = OutlivesConstraint {
+                    sup: annotation.representative,
+                    sub: fr_static,
+                    category: ConstraintCategory::IllegalUniverse,
+                    locations: Locations::All(rustc_span::DUMMY_SP),
+                    span: rustc_span::DUMMY_SP,
+                    variance_info: VarianceDiagInfo::None,
+                    from_closure: false,
+                };
+                self.push(scc_representative_outlives_static);
+            }
+        }
+
+        if added_constraints {
+            // We changed the constraint set and so must recompute SCCs.
+            self.compute_sccs(fr_static, definitions)
+        } else {
+            // If we didn't add any back-edges; no more work needs doing
+            sccs
+        }
+    }
 }
 
 impl<'tcx> Index<OutlivesConstraintIndex> for OutlivesConstraintSet<'tcx> {
diff --git a/compiler/rustc_borrowck/src/diagnostics/region_errors.rs b/compiler/rustc_borrowck/src/diagnostics/region_errors.rs
index db78edc45b9..61f107db784 100644
--- a/compiler/rustc_borrowck/src/diagnostics/region_errors.rs
+++ b/compiler/rustc_borrowck/src/diagnostics/region_errors.rs
@@ -66,7 +66,8 @@ impl<'tcx> ConstraintDescription for ConstraintCategory<'tcx> {
             ConstraintCategory::Predicate(_)
             | ConstraintCategory::Boring
             | ConstraintCategory::BoringNoLocation
-            | ConstraintCategory::Internal => "",
+            | ConstraintCategory::Internal
+            | ConstraintCategory::IllegalUniverse => "",
         }
     }
 }
diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs
index c56eaaff076..78e0b4783c3 100644
--- a/compiler/rustc_borrowck/src/region_infer/mod.rs
+++ b/compiler/rustc_borrowck/src/region_infer/mod.rs
@@ -62,7 +62,7 @@ pub struct RegionTracker {
     /// The representative Region Variable Id for this SCC. We prefer
     /// placeholders over existentially quantified variables, otherwise
     ///  it's the one with the smallest Region Variable ID.
-    representative: RegionVid,
+    pub(crate) representative: RegionVid,
 
     /// Is the current representative a placeholder?
     representative_is_placeholder: bool,
@@ -97,7 +97,7 @@ impl scc::Annotation for RegionTracker {
 }
 
 impl RegionTracker {
-    fn new(rvid: RegionVid, definition: &RegionDefinition<'_>) -> Self {
+    pub(crate) fn new(rvid: RegionVid, definition: &RegionDefinition<'_>) -> Self {
         let (representative_is_placeholder, representative_is_existential) = match definition.origin
         {
             rustc_infer::infer::NllRegionVariableOrigin::FreeRegion => (false, false),
@@ -132,7 +132,7 @@ impl RegionTracker {
 
     /// Returns `true` if during the annotated SCC reaches a placeholder
     /// with a universe larger than the smallest reachable one, `false` otherwise.
-    pub fn has_incompatible_universes(&self) -> bool {
+    pub(crate) fn has_incompatible_universes(&self) -> bool {
         self.universe().cannot_name(self.max_placeholder_universe_reached)
     }
 }
@@ -163,7 +163,7 @@ pub struct RegionInferenceContext<'tcx> {
     /// The SCC computed from `constraints` and the constraint
     /// graph. We have an edge from SCC A to SCC B if `A: B`. Used to
     /// compute the values of each region.
-    constraint_sccs: Rc<ConstraintSccs>,
+    constraint_sccs: ConstraintSccs,
 
     /// Reverse of the SCC constraint graph --  i.e., an edge `A -> B` exists if
     /// `B: A`. This is used to compute the universal regions that are required
@@ -401,7 +401,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         universal_regions: Rc<UniversalRegions<'tcx>>,
         placeholder_indices: Rc<PlaceholderIndices>,
         universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>,
-        outlives_constraints: OutlivesConstraintSet<'tcx>,
+        mut outlives_constraints: OutlivesConstraintSet<'tcx>,
         member_constraints_in: MemberConstraintSet<'tcx, RegionVid>,
         universe_causes: FxIndexMap<ty::UniverseIndex, UniverseInfo<'tcx>>,
         type_tests: Vec<TypeTest<'tcx>>,
@@ -419,17 +419,10 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             .map(|info| RegionDefinition::new(info.universe, info.origin))
             .collect();
 
-        let fr_static = universal_regions.fr_static;
+        let constraint_sccs =
+            outlives_constraints.add_outlives_static(&universal_regions, &definitions);
         let constraints = Frozen::freeze(outlives_constraints);
         let constraint_graph = Frozen::freeze(constraints.graph(definitions.len()));
-        let constraint_sccs = {
-            let constraint_graph = constraints.graph(definitions.len());
-            let region_graph = &constraint_graph.region_graph(&constraints, fr_static);
-            let sccs = ConstraintSccs::new_with_annotation(&region_graph, |r| {
-                RegionTracker::new(r, &definitions[r])
-            });
-            Rc::new(sccs)
-        };
 
         if cfg!(debug_assertions) {
             sccs_info(infcx, &constraint_sccs);
@@ -548,21 +541,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                 }
 
                 NllRegionVariableOrigin::Placeholder(placeholder) => {
-                    // Each placeholder region is only visible from
-                    // its universe `ui` and its extensions. So we
-                    // can't just add it into `scc` unless the
-                    // universe of the scc can name this region.
-                    let scc_universe = self.scc_universe(scc);
-                    if scc_universe.can_name(placeholder.universe) {
-                        self.scc_values.add_element(scc, placeholder);
-                    } else {
-                        debug!(
-                            "init_free_and_bound_regions: placeholder {:?} is \
-                             not compatible with universe {:?} of its SCC {:?}",
-                            placeholder, scc_universe, scc,
-                        );
-                        self.add_incompatible_universe(scc);
-                    }
+                    self.scc_values.add_element(scc, placeholder);
                 }
 
                 NllRegionVariableOrigin::Existential { .. } => {
@@ -744,23 +723,10 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// (which is assured by iterating over SCCs in dependency order).
     #[instrument(skip(self), level = "debug")]
     fn compute_value_for_scc(&mut self, scc_a: ConstraintSccIndex) {
-        let constraint_sccs = self.constraint_sccs.clone();
-
         // Walk each SCC `B` such that `A: B`...
-        for &scc_b in constraint_sccs.successors(scc_a) {
+        for &scc_b in self.constraint_sccs.successors(scc_a) {
             debug!(?scc_b);
-
-            // ...and add elements from `B` into `A`. One complication
-            // arises because of universes: If `B` contains something
-            // that `A` cannot name, then `A` can only contain `B` if
-            // it outlives static.
-            if self.universe_compatible(scc_b, scc_a) {
-                // `A` can name everything that is in `B`, so just
-                // merge the bits.
-                self.scc_values.add_region(scc_a, scc_b);
-            } else {
-                self.add_incompatible_universe(scc_a);
-            }
+            self.scc_values.add_region(scc_a, scc_b);
         }
 
         // Now take member constraints into account.
@@ -886,35 +852,20 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// in `scc_a`. Used during constraint propagation, and only once
     /// the value of `scc_b` has been computed.
     fn universe_compatible(&self, scc_b: ConstraintSccIndex, scc_a: ConstraintSccIndex) -> bool {
-        let universe_a = self.constraint_sccs().annotation(scc_a).universe();
-        let universe_b = self.constraint_sccs().annotation(scc_b).universe();
+        let a_annotation = self.constraint_sccs().annotation(scc_a);
+        let b_annotation = self.constraint_sccs().annotation(scc_b);
+        let a_universe = a_annotation.universe();
 
-        // Quick check: if scc_b's declared universe is a subset of
+        // If scc_b's declared universe is a subset of
         // scc_a's declared universe (typically, both are ROOT), then
         // it cannot contain any problematic universe elements.
-        if universe_a.can_name(universe_b) {
+        if a_universe.can_name(b_annotation.universe()) {
             return true;
         }
 
-        // Otherwise, we have to iterate over the universe elements in
-        // B's value, and check whether all of them are nameable
-        // from universe_a
-        self.scc_values.placeholders_contained_in(scc_b).all(|p| universe_a.can_name(p.universe))
-    }
-
-    /// Extend `scc` so that it can outlive some placeholder region
-    /// from a universe it can't name; at present, the only way for
-    /// this to be true is if `scc` outlives `'static`. This is
-    /// actually stricter than necessary: ideally, we'd support bounds
-    /// like `for<'a: 'b>` that might then allow us to approximate
-    /// `'a` with `'b` and not `'static`. But it will have to do for
-    /// now.
-    fn add_incompatible_universe(&mut self, scc: ConstraintSccIndex) {
-        debug!("add_incompatible_universe(scc={:?})", scc);
-
-        let fr_static = self.universal_regions.fr_static;
-        self.scc_values.add_all_points(scc);
-        self.scc_values.add_element(scc, fr_static);
+        // Otherwise, there can be no placeholder in `b` with a too high
+        // universe index to name from `a`.
+        a_universe.can_name(b_annotation.max_placeholder_universe_reached)
     }
 
     /// Once regions have been propagated, this method is used to see
@@ -1896,6 +1847,10 @@ impl<'tcx> RegionInferenceContext<'tcx> {
 
             // This loop can be hot.
             for constraint in outgoing_edges_from_graph {
+                if matches!(constraint.category, ConstraintCategory::IllegalUniverse) {
+                    debug!("Ignoring illegal universe constraint: {constraint:?}");
+                    continue;
+                }
                 handle_constraint(constraint);
             }
 
diff --git a/compiler/rustc_middle/src/mir/query.rs b/compiler/rustc_middle/src/mir/query.rs
index 46b38e4a6a6..cd8e28522ec 100644
--- a/compiler/rustc_middle/src/mir/query.rs
+++ b/compiler/rustc_middle/src/mir/query.rs
@@ -274,6 +274,9 @@ pub enum ConstraintCategory<'tcx> {
 
     /// A constraint that doesn't correspond to anything the user sees.
     Internal,
+
+    /// An internal constraint derived from an illegal universe relation.
+    IllegalUniverse,
 }
 
 #[derive(Copy, Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash)]