diff options
| -rw-r--r-- | src/librustc_mir/borrow_check/region_infer/mod.rs | 93 |
1 files changed, 60 insertions, 33 deletions
diff --git a/src/librustc_mir/borrow_check/region_infer/mod.rs b/src/librustc_mir/borrow_check/region_infer/mod.rs index 6e0b368b61a..880edf706a5 100644 --- a/src/librustc_mir/borrow_check/region_infer/mod.rs +++ b/src/librustc_mir/borrow_check/region_infer/mod.rs @@ -67,6 +67,12 @@ pub struct RegionInferenceContext<'tcx> { /// compute the values of each region. constraint_sccs: Rc<Sccs<RegionVid, ConstraintSccIndex>>, + /// SCCs in "dependency order" (or "post order"), meaning that if S1 -> S2, + /// then S2 appears first. If you process the SCCs in this order, then you + /// are always ensured that when you proces a given SCC, all of its + /// successors have been processed. + scc_dependency_order: Vec<ConstraintSccIndex>, + /// 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 /// to outlive a given SCC. Computed lazily. @@ -277,7 +283,10 @@ impl<'tcx> RegionInferenceContext<'tcx> { scc_values.merge_liveness(scc, region, &liveness_constraints); } - let scc_universes = Self::compute_scc_universes(&constraint_sccs, &definitions); + let scc_dependency_order = Self::compute_scc_dependency_order(&constraint_sccs); + + let scc_universes = + Self::compute_scc_universes(&constraint_sccs, &scc_dependency_order, &definitions); let scc_representatives = Self::compute_scc_representatives(&constraint_sccs, &definitions); @@ -290,6 +299,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { constraints, constraint_graph, constraint_sccs, + scc_dependency_order, rev_scc_graph: None, member_constraints, member_constraints_applied: Vec::new(), @@ -307,6 +317,43 @@ impl<'tcx> RegionInferenceContext<'tcx> { result } + /// Returns a vector of all scc-ids in "dependency" or "post order". See the + /// `scc_dependency_order` field for more details. + fn compute_scc_dependency_order( + constraints_scc: &Sccs<RegionVid, ConstraintSccIndex>, + ) -> Vec<ConstraintSccIndex> { + let mut visited = &mut BitSet::new_empty(constraints_scc.num_sccs()); + let mut output = vec![]; + + for scc in constraints_scc.all_sccs() { + Self::compute_scc_dependency_order_if_new( + constraints_scc, + scc, + &mut visited, + &mut output, + ); + } + + output + } + + fn compute_scc_dependency_order_if_new( + constraints_scc: &Sccs<RegionVid, ConstraintSccIndex>, + index: ConstraintSccIndex, + visited: &mut BitSet<ConstraintSccIndex>, + output: &mut Vec<ConstraintSccIndex>, + ) { + if !visited.insert(index) { + return; + } + + for &succ in constraints_scc.successors(index) { + Self::compute_scc_dependency_order_if_new(constraints_scc, succ, visited, output); + } + + output.push(index); + } + /// Each SCC is the combination of many region variables which /// have been equated. Therefore, we can associate a universe with /// each SCC which is minimum of all the universes of its @@ -315,10 +362,11 @@ impl<'tcx> RegionInferenceContext<'tcx> { /// SCC could have as well. This implies that the SCC must have /// the minimum, or narrowest, universe. fn compute_scc_universes( - constraints_scc: &Sccs<RegionVid, ConstraintSccIndex>, + constraint_sccs: &Sccs<RegionVid, ConstraintSccIndex>, + scc_dependency_order: &[ConstraintSccIndex], definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>, ) -> IndexVec<ConstraintSccIndex, ty::UniverseIndex> { - let num_sccs = constraints_scc.num_sccs(); + let num_sccs = constraint_sccs.num_sccs(); let mut scc_universes = IndexVec::from_elem_n(ty::UniverseIndex::MAX, num_sccs); debug!("compute_scc_universes()"); @@ -327,7 +375,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { // that contains R is "no bigger" than U. This effectively sets the universe // for each SCC to be the minimum of the regions within. for (region_vid, region_definition) in definitions.iter_enumerated() { - let scc = constraints_scc.scc(region_vid); + let scc = constraint_sccs.scc(region_vid); let scc_universe = &mut scc_universes[scc]; let scc_min = std::cmp::min(region_definition.universe, *scc_universe); if scc_min != *scc_universe { @@ -372,8 +420,8 @@ impl<'tcx> RegionInferenceContext<'tcx> { // constraint lowers the universe of `R1` to `U0`, which in turn // means that the `R1: !1` constraint will (later) cause // `R1` to become `'static`. - for scc_a in constraints_scc.all_sccs() { - for &scc_b in constraints_scc.successors(scc_a) { + for &scc_a in scc_dependency_order { + for &scc_b in constraint_sccs.successors(scc_a) { let scc_universe_a = scc_universes[scc_a]; let scc_universe_b = scc_universes[scc_b]; let scc_universe_min = std::cmp::min(scc_universe_a, scc_universe_b); @@ -616,9 +664,8 @@ impl<'tcx> RegionInferenceContext<'tcx> { // SCC. For each SCC, we visit its successors and compute // their values, then we union all those values to get our // own. - let visited = &mut BitSet::new_empty(self.constraint_sccs.num_sccs()); - for scc_index in self.constraint_sccs.all_sccs() { - self.propagate_constraint_sccs_if_new(scc_index, visited); + for i in 0..self.scc_dependency_order.len() { + self.compute_value_for_scc(self.scc_dependency_order[i]); } // Sort the applied member constraints so we can binary search @@ -626,37 +673,17 @@ impl<'tcx> RegionInferenceContext<'tcx> { self.member_constraints_applied.sort_by_key(|applied| applied.member_region_scc); } - /// Computes the value of the SCC `scc_a` if it has not already - /// been computed. The `visited` parameter is a bitset - #[inline] - fn propagate_constraint_sccs_if_new( - &mut self, - scc_a: ConstraintSccIndex, - visited: &mut BitSet<ConstraintSccIndex>, - ) { - if visited.insert(scc_a) { - self.propagate_constraint_sccs_new(scc_a, visited); - } - } - /// Computes the value of the SCC `scc_a`, which has not yet been - /// computed. This works by first computing all successors of the - /// SCC (if they haven't been computed already) and then unioning - /// together their elements. - fn propagate_constraint_sccs_new( - &mut self, - scc_a: ConstraintSccIndex, - visited: &mut BitSet<ConstraintSccIndex>, - ) { + /// computed, by unioning the values of its successors. + /// Assumes that all successors have been computed already + /// (which is assured by iterating over SCCs in dependency order). + 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) { debug!("propagate_constraint_sccs: scc_a = {:?} scc_b = {:?}", scc_a, scc_b); - // ...compute the value of `B`... - self.propagate_constraint_sccs_if_new(scc_b, visited); - // ...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 |