compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs

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