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;
11 pub(crate) struct ReverseSccGraph {
12 graph: VecGraph<ConstraintSccIndex>,
13 /// For each SCC, the range of `universal_regions` that use that SCC as
15 scc_regions: FxHashMap<ConstraintSccIndex, Range<usize>>,
16 /// All of the universal regions, in grouped so that `scc_regions` can
18 universal_regions: Vec<RegionVid>,
21 impl ReverseSccGraph {
22 /// Find all universal regions that are required to outlive the given SCC.
23 pub(super) fn upper_bounds<'a>(
25 scc0: ConstraintSccIndex,
26 ) -> impl Iterator<Item = RegionVid> + 'a {
27 let mut duplicates = FxHashSet::default();
29 .depth_first_search(scc0)
30 .flat_map(move |scc1| {
33 .map_or(&[][..], |range| &self.universal_regions[range.clone()])
36 .filter(move |r| duplicates.insert(*r))
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 {
47 let graph = self.constraint_sccs.reverse();
48 let mut paired_scc_regions = self
51 .map(|region| (self.constraint_sccs.scc(region), region))
53 paired_scc_regions.sort();
54 let universal_regions = paired_scc_regions.iter().map(|&(_, region)| region).collect();
56 let mut scc_regions = FxHashMap::default();
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);
64 let rev_graph = Rc::new(ReverseSccGraph { graph, scc_regions, universal_regions });
65 self.rev_scc_graph = Some(rev_graph.clone());