1 #![deny(rustc::untranslatable_diagnostic)]
2 #![deny(rustc::diagnostic_outside_of_impl)]
3 use crate::constraints::ConstraintSccIndex;
4 use crate::RegionInferenceContext;
5 use itertools::Itertools;
6 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
7 use rustc_data_structures::graph::vec_graph::VecGraph;
8 use rustc_data_structures::graph::WithSuccessors;
9 use rustc_middle::ty::RegionVid;
13 pub(crate) struct ReverseSccGraph {
14 graph: VecGraph<ConstraintSccIndex>,
15 /// For each SCC, the range of `universal_regions` that use that SCC as
17 scc_regions: FxHashMap<ConstraintSccIndex, Range<usize>>,
18 /// All of the universal regions, in grouped so that `scc_regions` can
20 universal_regions: Vec<RegionVid>,
23 impl ReverseSccGraph {
24 /// Find all universal regions that are required to outlive the given SCC.
25 pub(super) fn upper_bounds<'a>(
27 scc0: ConstraintSccIndex,
28 ) -> impl Iterator<Item = RegionVid> + 'a {
29 let mut duplicates = FxHashSet::default();
31 .depth_first_search(scc0)
32 .flat_map(move |scc1| {
35 .map_or(&[][..], |range| &self.universal_regions[range.clone()])
38 .filter(move |r| duplicates.insert(*r))
42 impl RegionInferenceContext<'_> {
43 /// Compute and return the reverse SCC-based constraint graph (lazily).
44 pub(super) fn reverse_scc_graph(&mut self) -> Rc<ReverseSccGraph> {
45 if let Some(g) = &self.rev_scc_graph {
49 let graph = self.constraint_sccs.reverse();
50 let mut paired_scc_regions = self
53 .map(|region| (self.constraint_sccs.scc(region), region))
55 paired_scc_regions.sort();
56 let universal_regions = paired_scc_regions.iter().map(|&(_, region)| region).collect();
58 let mut scc_regions = FxHashMap::default();
60 for (scc, group) in &paired_scc_regions.into_iter().group_by(|(scc, _)| *scc) {
61 let group_size = group.count();
62 scc_regions.insert(scc, start..start + group_size);
66 let rev_graph = Rc::new(ReverseSccGraph { graph, scc_regions, universal_regions });
67 self.rev_scc_graph = Some(rev_graph.clone());