1 use crate::borrow_check
::constraints
::ConstraintSccIndex
;
2 use crate::borrow_check
::RegionInferenceContext
;
3 use itertools
::Itertools
;
4 use rustc
::ty
::RegionVid
;
5 use rustc_data_structures
::fx
::{FxHashMap, FxHashSet}
;
6 use rustc_data_structures
::graph
::vec_graph
::VecGraph
;
7 use rustc_data_structures
::graph
::WithSuccessors
;
11 crate struct ReverseSccGraph
{
12 graph
: VecGraph
<ConstraintSccIndex
>,
13 /// For each SCC, the range of `universal_regions` that use that SCC as
15 scc_regions
: FxHashMap
<ConstraintSccIndex
, Range
<usize>>,
16 /// All of the universal regions, in grouped so that `scc_regions` can
18 universal_regions
: Vec
<RegionVid
>,
21 impl ReverseSccGraph
{
22 /// Find all universal regions that are required to outlive the given SCC.
23 pub(super) fn upper_bounds
<'a
>(
25 scc0
: ConstraintSccIndex
,
26 ) -> impl Iterator
<Item
= RegionVid
> + 'a
{
27 let mut duplicates
= FxHashSet
::default();
29 .depth_first_search(scc0
)
30 .flat_map(move |scc1
| {
33 .map_or(&[][..], |range
| &self.universal_regions
[range
.clone()])
36 .filter(move |r
| duplicates
.insert(*r
))
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
{
47 let graph
= self.constraint_sccs
.reverse();
48 let mut paired_scc_regions
= self
51 .map(|region
| (self.constraint_sccs
.scc(region
), region
))
53 paired_scc_regions
.sort();
54 let universal_regions
= paired_scc_regions
.iter().map(|&(_
, region
)| region
).collect();
56 let mut scc_regions
= FxHashMap
::default();
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
);
64 let rev_graph
= Rc
::new(ReverseSccGraph { graph, scc_regions, universal_regions }
);
65 self.rev_scc_graph
= Some(rev_graph
.clone());