set up skeleton for localized constraints conversion

4 files changed, 164 insertions, 1 deletions

diff --git a/compiler/rustc_borrowck/src/lib.rs b/compiler/rustc_borrowck/src/lib.rs
index 63e20b16f7a..f42945787e1 100644
--- a/compiler/rustc_borrowck/src/lib.rs
+++ b/compiler/rustc_borrowck/src/lib.rs
@@ -202,6 +202,7 @@ fn do_mir_borrowck<'tcx>(
         polonius_output,
         opt_closure_req,
         nll_errors,
+        localized_outlives_constraints,
     } = nll::compute_regions(
         &infcx,
         free_regions,
diff --git a/compiler/rustc_borrowck/src/nll.rs b/compiler/rustc_borrowck/src/nll.rs
index 7656031ed3a..66bb62641e6 100644
--- a/compiler/rustc_borrowck/src/nll.rs
+++ b/compiler/rustc_borrowck/src/nll.rs
@@ -29,6 +29,7 @@ use crate::consumers::ConsumerOptions;
 use crate::diagnostics::RegionErrors;
 use crate::facts::{AllFacts, AllFactsExt, RustcFacts};
 use crate::location::LocationTable;
+use crate::polonius::LocalizedOutlivesConstraintSet;
 use crate::region_infer::RegionInferenceContext;
 use crate::type_check::{self, MirTypeckResults};
 use crate::universal_regions::UniversalRegions;
@@ -45,6 +46,9 @@ pub(crate) struct NllOutput<'tcx> {
     pub polonius_output: Option<Box<PoloniusOutput>>,
     pub opt_closure_req: Option<ClosureRegionRequirements<'tcx>>,
     pub nll_errors: RegionErrors<'tcx>,
+
+    /// When using `-Zpolonius=next`: the localized typeck and liveness constraints.
+    pub localized_outlives_constraints: LocalizedOutlivesConstraintSet,
 }
 
 /// Rewrites the regions in the MIR to use NLL variables, also scraping out the set of universal
@@ -135,6 +139,18 @@ pub(crate) fn compute_regions<'a, 'tcx>(
         elements,
     );
 
+    // If requested for `-Zpolonius=next`, convert NLL constraints to localized outlives
+    // constraints.
+    let mut localized_outlives_constraints = LocalizedOutlivesConstraintSet::default();
+    if infcx.tcx.sess.opts.unstable_opts.polonius.is_next_enabled() {
+        polonius::create_localized_constraints(
+            &mut regioncx,
+            infcx.infcx.tcx,
+            body,
+            &mut localized_outlives_constraints,
+        );
+    }
+
     // If requested: dump NLL facts, and run legacy polonius analysis.
     let polonius_output = all_facts.as_ref().and_then(|all_facts| {
         if infcx.tcx.sess.opts.unstable_opts.nll_facts {
@@ -175,6 +191,7 @@ pub(crate) fn compute_regions<'a, 'tcx>(
         polonius_output,
         opt_closure_req: closure_region_requirements,
         nll_errors,
+        localized_outlives_constraints,
     }
 }
 
diff --git a/compiler/rustc_borrowck/src/polonius/mod.rs b/compiler/rustc_borrowck/src/polonius/mod.rs
index 70f8fdaa637..03db7ba50ed 100644
--- a/compiler/rustc_borrowck/src/polonius/mod.rs
+++ b/compiler/rustc_borrowck/src/polonius/mod.rs
@@ -35,5 +35,146 @@
 
 mod constraints;
 pub(crate) use constraints::*;
-
 pub(crate) mod legacy;
+
+use rustc_middle::mir::{Body, Location};
+use rustc_middle::ty::TyCtxt;
+use rustc_mir_dataflow::points::PointIndex;
+
+use crate::RegionInferenceContext;
+use crate::constraints::OutlivesConstraint;
+use crate::region_infer::values::LivenessValues;
+use crate::type_check::Locations;
+use crate::universal_regions::UniversalRegions;
+
+/// When using `-Zpolonius=next`, fills the given constraint set by:
+/// - converting NLL typeck constraints to be localized
+/// - encoding liveness constraints
+pub(crate) fn create_localized_constraints<'tcx>(
+    regioncx: &mut RegionInferenceContext<'tcx>,
+    tcx: TyCtxt<'tcx>,
+    body: &Body<'tcx>,
+    localized_outlives_constraints: &mut LocalizedOutlivesConstraintSet,
+) {
+    if !tcx.sess.opts.unstable_opts.polonius.is_next_enabled() {
+        return;
+    }
+
+    convert_typeck_constraints(
+        body,
+        regioncx.liveness_constraints(),
+        regioncx.outlives_constraints(),
+        localized_outlives_constraints,
+    );
+    create_liveness_constraints(
+        body,
+        regioncx.liveness_constraints(),
+        regioncx.universal_regions(),
+        localized_outlives_constraints,
+    );
+
+    // FIXME: here, we can trace loan reachability in the constraint graph and record this as loan
+    // liveness for the next step in the chain, the NLL loan scope and active loans computations.
+}
+
+/// Propagate loans throughout the subset graph at a given point (with some subtleties around the
+/// location where effects start to be visible).
+fn convert_typeck_constraints<'tcx>(
+    body: &Body<'tcx>,
+    liveness: &LivenessValues,
+    outlives_constraints: impl Iterator<Item = OutlivesConstraint<'tcx>>,
+    localized_outlives_constraints: &mut LocalizedOutlivesConstraintSet,
+) {
+    for outlives_constraint in outlives_constraints {
+        match outlives_constraint.locations {
+            Locations::All(_) => {
+                // FIXME: for now, turn logical constraints holding at all points into physical
+                // edges at every point in the graph. We can encode this into *traversal* instead.
+                for (block, bb) in body.basic_blocks.iter_enumerated() {
+                    let statement_count = bb.statements.len();
+                    for statement_index in 0..=statement_count {
+                        let current_location = Location { block, statement_index };
+                        let current_point = liveness.point_from_location(current_location);
+
+                        localized_outlives_constraints.push(LocalizedOutlivesConstraint {
+                            source: outlives_constraint.sup,
+                            from: current_point,
+                            target: outlives_constraint.sub,
+                            to: current_point,
+                        });
+                    }
+                }
+            }
+
+            _ => {}
+        }
+    }
+}
+
+/// Propagate loans throughout the CFG: for each statement in the MIR, create localized outlives
+/// constraints for loans that are propagated to the next statements.
+pub(crate) fn create_liveness_constraints<'tcx>(
+    body: &Body<'tcx>,
+    liveness: &LivenessValues,
+    universal_regions: &UniversalRegions<'tcx>,
+    localized_outlives_constraints: &mut LocalizedOutlivesConstraintSet,
+) {
+    for (block, bb) in body.basic_blocks.iter_enumerated() {
+        let statement_count = bb.statements.len();
+        for statement_index in 0..=statement_count {
+            let current_location = Location { block, statement_index };
+            let current_point = liveness.point_from_location(current_location);
+
+            if statement_index < statement_count {
+                // Intra-block edges, straight line constraints from each point to its successor
+                // within the same block.
+                let next_location = Location { block, statement_index: statement_index + 1 };
+                let next_point = liveness.point_from_location(next_location);
+                propagate_loans_between_points(
+                    current_point,
+                    next_point,
+                    liveness,
+                    universal_regions,
+                    localized_outlives_constraints,
+                );
+            } else {
+                // Inter-block edges, from the block's terminator to each successor block's entry
+                // point.
+                for successor_block in bb.terminator().successors() {
+                    let next_location = Location { block: successor_block, statement_index: 0 };
+                    let next_point = liveness.point_from_location(next_location);
+                    propagate_loans_between_points(
+                        current_point,
+                        next_point,
+                        liveness,
+                        universal_regions,
+                        localized_outlives_constraints,
+                    );
+                }
+            }
+        }
+    }
+}
+
+/// Propagate loans within a region between two points in the CFG, if that region is live at both
+/// the source and target points.
+fn propagate_loans_between_points(
+    current_point: PointIndex,
+    next_point: PointIndex,
+    _liveness: &LivenessValues,
+    universal_regions: &UniversalRegions<'_>,
+    localized_outlives_constraints: &mut LocalizedOutlivesConstraintSet,
+) {
+    // Universal regions are semantically live at all points.
+    // FIXME: We always have universal regions but they're not always (or often) involved in the
+    // subset graph. So for now, we emit this edge, but we only need to emit edges for universal
+    // regions that existential regions can actually reach.
+    for region in universal_regions.universal_regions_iter() {
+        localized_outlives_constraints.push(LocalizedOutlivesConstraint {
+            source: region,
+            from: current_point,
+            target: region,
+            to: next_point,
+        });
+    }
+}
diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs
index 0eecf98a6ed..f2aa8b8e780 100644
--- a/compiler/rustc_borrowck/src/region_infer/mod.rs
+++ b/compiler/rustc_borrowck/src/region_infer/mod.rs
@@ -2224,6 +2224,10 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     fn scc_representative(&self, scc: ConstraintSccIndex) -> RegionVid {
         self.constraint_sccs.annotation(scc).representative
     }
+
+    pub(crate) fn liveness_constraints(&self) -> &LivenessValues {
+        &self.liveness_constraints
+    }
 }
 
 impl<'tcx> RegionDefinition<'tcx> {