introduce reachability to the constraint graph

1 files changed, 25 insertions, 5 deletions

diff --git a/compiler/rustc_borrowck/src/polonius/mod.rs b/compiler/rustc_borrowck/src/polonius/mod.rs
index 7d0f9397021..313ed5d6649 100644
--- a/compiler/rustc_borrowck/src/polonius/mod.rs
+++ b/compiler/rustc_borrowck/src/polonius/mod.rs
@@ -37,6 +37,7 @@ mod constraints;
 mod dump;
 pub(crate) mod legacy;
 mod liveness_constraints;
+mod loan_liveness;
 mod typeck_constraints;
 
 use std::collections::BTreeMap;
@@ -49,8 +50,12 @@ use rustc_mir_dataflow::points::PointIndex;
 pub(crate) use self::constraints::*;
 pub(crate) use self::dump::dump_polonius_mir;
 use self::liveness_constraints::create_liveness_constraints;
+use self::loan_liveness::compute_loan_liveness;
 use self::typeck_constraints::convert_typeck_constraints;
-use crate::RegionInferenceContext;
+use crate::dataflow::BorrowIndex;
+use crate::{BorrowSet, RegionInferenceContext};
+
+pub(crate) type LiveLoans = SparseBitMatrix<PointIndex, BorrowIndex>;
 
 /// This struct holds the data needed to create the Polonius localized constraints.
 pub(crate) struct PoloniusContext {
@@ -82,14 +87,20 @@ impl PoloniusContext {
         Self { live_region_variances: BTreeMap::new(), live_regions: None }
     }
 
-    /// Creates a constraint set for `-Zpolonius=next` by:
+    /// Computes live loans using the set of loans model for `-Zpolonius=next`.
+    ///
+    /// First, creates a constraint graph combining regions and CFG points, by:
     /// - converting NLL typeck constraints to be localized
     /// - encoding liveness constraints
-    pub(crate) fn create_localized_constraints<'tcx>(
+    ///
+    /// Then, this graph is traversed, and combined with kills, reachability is recorded as loan
+    /// liveness, to be used by the loan scope and active loans computations.
+    pub(crate) fn compute_loan_liveness<'tcx>(
         &self,
         tcx: TyCtxt<'tcx>,
         regioncx: &RegionInferenceContext<'tcx>,
         body: &Body<'tcx>,
+        borrow_set: &BorrowSet<'tcx>,
     ) -> LocalizedOutlivesConstraintSet {
         let mut localized_outlives_constraints = LocalizedOutlivesConstraintSet::default();
         convert_typeck_constraints(
@@ -113,8 +124,17 @@ impl PoloniusContext {
             &mut 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.
+        // Now that we have a complete graph, we can compute reachability to trace the liveness of
+        // loans for the next step in the chain, the NLL loan scope and active loans computations.
+        let _live_loans = compute_loan_liveness(
+            tcx,
+            body,
+            regioncx.liveness_constraints(),
+            borrow_set,
+            &localized_outlives_constraints,
+        );
+        // FIXME: record the live loans in the regioncx's liveness constraints, where the
+        // location-insensitive variant's data is stored.
 
         localized_outlives_constraints
     }