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

rustc_borrowck/region_infer/
reverse_sccs.rs
