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

rustc_borrowck/region_infer/
reverse_sccs.rs
