rustc_borrowck/region_infer/
reverse_sccs.rs

Help
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::RegionInferenceContext;
9use crate::constraints::ConstraintSccIndex;
10
11pub(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: FxIndexMap<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
21impl ReverseSccGraph {
22    /// Find all universal regions that are required to outlive the given SCC.
23    pub(super) fn upper_bounds(&self, scc0: ConstraintSccIndex) -> impl Iterator<Item = RegionVid> {
24        let mut duplicates = FxIndexSet::default();
25        graph::depth_first_search(&self.graph, scc0)
26            .flat_map(move |scc1| {
27                self.scc_regions
28                    .get(&scc1)
29                    .map_or(&[][..], |range| &self.universal_regions[range.clone()])
30            })
31            .copied()
32            .filter(move |r| duplicates.insert(*r))
33    }
34}
35
36impl RegionInferenceContext<'_> {
37    /// Compute the reverse SCC-based constraint graph (lazily).
38    pub(super) fn compute_reverse_scc_graph(&mut self) {
39        if self.rev_scc_graph.is_some() {
40            return;
41        }
42
43        let graph = self.constraint_sccs.reverse();
44        let mut paired_scc_regions = self
45            .universal_regions()
46            .universal_regions_iter()
47            .map(|region| (self.constraint_sccs.scc(region), region))
48            .collect::<Vec<_>>();
49        paired_scc_regions.sort();
50        let universal_regions = paired_scc_regions.iter().map(|&(_, region)| region).collect();
51
52        let mut scc_regions = FxIndexMap::default();
53        let mut start = 0;
54        for chunk in paired_scc_regions.chunk_by(|&(scc1, _), &(scc2, _)| scc1 == scc2) {
55            let (scc, _) = chunk[0];
56            scc_regions.insert(scc, start..start + chunk.len());
57            start += chunk.len();
58        }
59
60        self.rev_scc_graph = Some(ReverseSccGraph { graph, scc_regions, universal_regions });
61    }
62}
rustc_borrowck/region_infer/reverse_sccs.rs

rustc_borrowck/region_infer/
reverse_sccs.rs
