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::{FxIndexMap, FxIndexSet}; 7 use rustc_data_structures::graph::vec_graph::VecGraph; 8 use rustc_data_structures::graph::WithSuccessors; 9 use rustc_middle::ty::RegionVid; 10 use std::ops::Range; 11 12 pub(crate) struct ReverseSccGraph { 13 graph: VecGraph<ConstraintSccIndex>, 14 /// For each SCC, the range of `universal_regions` that use that SCC as 15 /// their value. 16 scc_regions: FxIndexMap<ConstraintSccIndex, Range<usize>>, 17 /// All of the universal regions, in grouped so that `scc_regions` can 18 /// index into here. 19 universal_regions: Vec<RegionVid>, 20 } 21 22 impl ReverseSccGraph { 23 /// Find all universal regions that are required to outlive the given SCC. upper_bounds<'a>( &'a self, scc0: ConstraintSccIndex, ) -> impl Iterator<Item = RegionVid> + 'a24 pub(super) fn upper_bounds<'a>( 25 &'a self, 26 scc0: ConstraintSccIndex, 27 ) -> impl Iterator<Item = RegionVid> + 'a { 28 let mut duplicates = FxIndexSet::default(); 29 self.graph 30 .depth_first_search(scc0) 31 .flat_map(move |scc1| { 32 self.scc_regions 33 .get(&scc1) 34 .map_or(&[][..], |range| &self.universal_regions[range.clone()]) 35 }) 36 .copied() 37 .filter(move |r| duplicates.insert(*r)) 38 } 39 } 40 41 impl RegionInferenceContext<'_> { 42 /// Compute the reverse SCC-based constraint graph (lazily). compute_reverse_scc_graph(&mut self)43 pub(super) fn compute_reverse_scc_graph(&mut self) { 44 if self.rev_scc_graph.is_some() { 45 return; 46 } 47 48 let graph = self.constraint_sccs.reverse(); 49 let mut paired_scc_regions = self 50 .universal_regions 51 .universal_regions() 52 .map(|region| (self.constraint_sccs.scc(region), region)) 53 .collect_vec(); 54 paired_scc_regions.sort(); 55 let universal_regions = paired_scc_regions.iter().map(|&(_, region)| region).collect(); 56 57 let mut scc_regions = FxIndexMap::default(); 58 let mut start = 0; 59 for (scc, group) in &paired_scc_regions.into_iter().group_by(|(scc, _)| *scc) { 60 let group_size = group.count(); 61 scc_regions.insert(scc, start..start + group_size); 62 start += group_size; 63 } 64 65 self.rev_scc_graph = Some(ReverseSccGraph { graph, scc_regions, universal_regions }); 66 } 67 } 68