]>
Commit | Line | Data |
---|---|---|
c295e0f8 XL |
1 | use crate::constraints::ConstraintSccIndex; |
2 | use crate::RegionInferenceContext; | |
74b04a01 | 3 | use itertools::Itertools; |
74b04a01 XL |
4 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
5 | use rustc_data_structures::graph::vec_graph::VecGraph; | |
6 | use rustc_data_structures::graph::WithSuccessors; | |
ba9703b0 | 7 | use rustc_middle::ty::RegionVid; |
74b04a01 XL |
8 | use std::ops::Range; |
9 | use std::rc::Rc; | |
10 | ||
11 | 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: FxHashMap<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 | ||
21 | impl 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 = FxHashSet::default(); | |
28 | self.graph | |
29 | .depth_first_search(scc0) | |
30 | .flat_map(move |scc1| { | |
31 | self.scc_regions | |
32 | .get(&scc1) | |
33 | .map_or(&[][..], |range| &self.universal_regions[range.clone()]) | |
34 | }) | |
35 | .copied() | |
36 | .filter(move |r| duplicates.insert(*r)) | |
37 | } | |
38 | } | |
39 | ||
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 { | |
44 | return g.clone(); | |
45 | } | |
46 | ||
47 | let graph = self.constraint_sccs.reverse(); | |
48 | let mut paired_scc_regions = self | |
49 | .universal_regions | |
50 | .universal_regions() | |
51 | .map(|region| (self.constraint_sccs.scc(region), region)) | |
52 | .collect_vec(); | |
53 | paired_scc_regions.sort(); | |
54 | let universal_regions = paired_scc_regions.iter().map(|&(_, region)| region).collect(); | |
55 | ||
56 | let mut scc_regions = FxHashMap::default(); | |
57 | let mut start = 0; | |
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); | |
61 | start += group_size; | |
62 | } | |
63 | ||
64 | let rev_graph = Rc::new(ReverseSccGraph { graph, scc_regions, universal_regions }); | |
65 | self.rev_scc_graph = Some(rev_graph.clone()); | |
66 | rev_graph | |
67 | } | |
68 | } |