rustc_borrowck/region_infer/
reverse_sccs.rs

1use std::ops::Range;
2
3use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
4use rustc_data_structures::graph;
5use rustc_data_structures::graph::vec_graph::VecGraph;
6use rustc_middle::ty::RegionVid;
7
8use crate::constraints::ConstraintSccIndex;
9use crate::region_infer::ConstraintSccs;
10use crate::universal_regions::UniversalRegions;
11
12pub(crate) struct ReverseSccGraph {
13    graph: VecGraph<ConstraintSccIndex>,
14    /// For each SCC, the range of `universal_regions` that use that SCC as
15    /// their value.
16    scc_regions: FxIndexMap<ConstraintSccIndex, Range<usize>>,
17    /// All of the universal regions, in grouped so that `scc_regions` can
18    /// index into here.
19    universal_regions: Vec<RegionVid>,
20}
21
22impl ReverseSccGraph {
23    pub(super) fn compute(
24        constraint_sccs: &ConstraintSccs,
25        universal_regions: &UniversalRegions<'_>,
26    ) -> Self {
27        let graph = constraint_sccs.reverse();
28        let mut paired_scc_regions = universal_regions
29            .universal_regions_iter()
30            .map(|region| (constraint_sccs.scc(region), region))
31            .collect::<Vec<_>>();
32        paired_scc_regions.sort();
33        let universal_regions = paired_scc_regions.iter().map(|&(_, region)| region).collect();
34
35        let mut scc_regions = FxIndexMap::default();
36        let mut start = 0;
37        for chunk in paired_scc_regions.chunk_by(|&(scc1, _), &(scc2, _)| scc1 == scc2) {
38            let (scc, _) = chunk[0];
39
40            scc_regions.insert(scc, start..start + chunk.len());
41            start += chunk.len();
42        }
43        ReverseSccGraph { graph, scc_regions, universal_regions }
44    }
45
46    /// Find all universal regions that are required to outlive the given SCC.
47    pub(super) fn upper_bounds(&self, scc0: ConstraintSccIndex) -> impl Iterator<Item = RegionVid> {
48        let mut duplicates = FxIndexSet::default();
49        graph::depth_first_search(&self.graph, scc0)
50            .flat_map(move |scc1| {
51                self.scc_regions
52                    .get(&scc1)
53                    .map_or(&[][..], |range| &self.universal_regions[range.clone()])
54            })
55            .copied()
56            .filter(move |r| duplicates.insert(*r))
57    }
58}
rustc_borrowck/region_infer/reverse_sccs.rs

rustc_borrowck/region_infer/
reverse_sccs.rs
