compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs

   1 use crate::constraints::ConstraintSccIndex;
   2 use crate::RegionInferenceContext;
   3 use itertools::Itertools;
   4 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   5 use rustc_data_structures::graph::vec_graph::VecGraph;
   6 use rustc_data_structures::graph::WithSuccessors;
   7 use rustc_middle::ty::RegionVid;
   8 use std::ops::Range;
   9 use std::rc::Rc;
  10
  11 crate struct ReverseSccGraph {
  12     graph: VecGraph<ConstraintSccIndex>,
  13     /// For each SCC, the range of `universal_regions` that use that SCC as
  14     /// their value.
  15     scc_regions: FxHashMap<ConstraintSccIndex, Range<usize>>,
  16     /// All of the universal regions, in grouped so that `scc_regions` can
  17     /// index into here.
  18     universal_regions: Vec<RegionVid>,
  19 }
  20
  21 impl ReverseSccGraph {
  22     /// Find all universal regions that are required to outlive the given SCC.
  23     pub(super) fn upper_bounds<'a>(
  24         &'a self,
  25         scc0: ConstraintSccIndex,
  26     ) -> impl Iterator<Item = RegionVid> + 'a {
  27         let mut duplicates = FxHashSet::default();
  28         self.graph
  29             .depth_first_search(scc0)
  30             .flat_map(move |scc1| {
  31                 self.scc_regions
  32                     .get(&scc1)
  33                     .map_or(&[][..], |range| &self.universal_regions[range.clone()])
  34             })
  35             .copied()
  36             .filter(move |r| duplicates.insert(*r))
  37     }
  38 }
  39
  40 impl RegionInferenceContext<'_> {
  41     /// Compute and return the reverse SCC-based constraint graph (lazily).
  42     pub(super) fn reverse_scc_graph(&mut self) -> Rc<ReverseSccGraph> {
  43         if let Some(g) = &self.rev_scc_graph {
  44             return g.clone();
  45         }
  46
  47         let graph = self.constraint_sccs.reverse();
  48         let mut paired_scc_regions = self
  49             .universal_regions
  50             .universal_regions()
  51             .map(|region| (self.constraint_sccs.scc(region), region))
  52             .collect_vec();
  53         paired_scc_regions.sort();
  54         let universal_regions = paired_scc_regions.iter().map(|&(_, region)| region).collect();
  55
  56         let mut scc_regions = FxHashMap::default();
  57         let mut start = 0;
  58         for (scc, group) in &paired_scc_regions.into_iter().group_by(|(scc, _)| *scc) {
  59             let group_size = group.count();
  60             scc_regions.insert(scc, start..start + group_size);
  61             start += group_size;
  62         }
  63
  64         let rev_graph = Rc::new(ReverseSccGraph { graph, scc_regions, universal_regions });
  65         self.rev_scc_graph = Some(rev_graph.clone());
  66         rev_graph
  67     }
  68 }