1 use rustc_data_structures
::graph
;
2 use rustc_index
::vec
::IndexVec
;
3 use rustc_middle
::mir
::ConstraintCategory
;
4 use rustc_middle
::ty
::{RegionVid, VarianceDiagInfo}
;
5 use rustc_span
::DUMMY_SP
;
8 constraints
::OutlivesConstraintIndex
,
9 constraints
::{OutlivesConstraint, OutlivesConstraintSet}
,
10 type_check
::Locations
,
13 /// The construct graph organizes the constraints by their end-points.
14 /// It can be used to view a `R1: R2` constraint as either an edge `R1
15 /// -> R2` or `R2 -> R1` depending on the direction type `D`.
16 pub(crate) struct ConstraintGraph
<D
: ConstraintGraphDirecton
> {
18 first_constraints
: IndexVec
<RegionVid
, Option
<OutlivesConstraintIndex
>>,
19 next_constraints
: IndexVec
<OutlivesConstraintIndex
, Option
<OutlivesConstraintIndex
>>,
22 pub(crate) type NormalConstraintGraph
= ConstraintGraph
<Normal
>;
24 pub(crate) type ReverseConstraintGraph
= ConstraintGraph
<Reverse
>;
26 /// Marker trait that controls whether a `R1: R2` constraint
27 /// represents an edge `R1 -> R2` or `R2 -> R1`.
28 pub(crate) trait ConstraintGraphDirecton
: Copy
+ '
static {
29 fn start_region(c
: &OutlivesConstraint
<'_
>) -> RegionVid
;
30 fn end_region(c
: &OutlivesConstraint
<'_
>) -> RegionVid
;
31 fn is_normal() -> bool
;
34 /// In normal mode, a `R1: R2` constraint results in an edge `R1 ->
35 /// R2`. This is what we use when constructing the SCCs for
36 /// inference. This is because we compute the value of R1 by union'ing
37 /// all the things that it relies on.
38 #[derive(Copy, Clone, Debug)]
39 pub(crate) struct Normal
;
41 impl ConstraintGraphDirecton
for Normal
{
42 fn start_region(c
: &OutlivesConstraint
<'_
>) -> RegionVid
{
46 fn end_region(c
: &OutlivesConstraint
<'_
>) -> RegionVid
{
50 fn is_normal() -> bool
{
55 /// In reverse mode, a `R1: R2` constraint results in an edge `R2 ->
56 /// R1`. We use this for optimizing liveness computation, because then
57 /// we wish to iterate from a region (e.g., R2) to all the regions
58 /// that will outlive it (e.g., R1).
59 #[derive(Copy, Clone, Debug)]
60 pub(crate) struct Reverse
;
62 impl ConstraintGraphDirecton
for Reverse
{
63 fn start_region(c
: &OutlivesConstraint
<'_
>) -> RegionVid
{
67 fn end_region(c
: &OutlivesConstraint
<'_
>) -> RegionVid
{
71 fn is_normal() -> bool
{
76 impl<D
: ConstraintGraphDirecton
> ConstraintGraph
<D
> {
77 /// Creates a "dependency graph" where each region constraint `R1:
78 /// R2` is treated as an edge `R1 -> R2`. We use this graph to
79 /// construct SCCs for region inference but also for error
83 set
: &OutlivesConstraintSet
<'_
>,
84 num_region_vars
: usize,
86 let mut first_constraints
= IndexVec
::from_elem_n(None
, num_region_vars
);
87 let mut next_constraints
= IndexVec
::from_elem(None
, &set
.outlives
);
89 for (idx
, constraint
) in set
.outlives
.iter_enumerated().rev() {
90 let head
= &mut first_constraints
[D
::start_region(constraint
)];
91 let next
= &mut next_constraints
[idx
];
92 debug_assert
!(next
.is_none());
97 Self { _direction: direction, first_constraints, next_constraints }
100 /// Given the constraint set from which this graph was built
101 /// creates a region graph so that you can iterate over *regions*
102 /// and not constraints.
103 pub(crate) fn region_graph
<'rg
, 'tcx
>(
105 set
: &'rg OutlivesConstraintSet
<'tcx
>,
106 static_region
: RegionVid
,
107 ) -> RegionGraph
<'rg
, 'tcx
, D
> {
108 RegionGraph
::new(set
, self, static_region
)
111 /// Given a region `R`, iterate over all constraints `R: R1`.
112 pub(crate) fn outgoing_edges
<'a
, 'tcx
>(
114 region_sup
: RegionVid
,
115 constraints
: &'a OutlivesConstraintSet
<'tcx
>,
116 static_region
: RegionVid
,
117 ) -> Edges
<'a
, 'tcx
, D
> {
118 //if this is the `'static` region and the graph's direction is normal,
119 //then setup the Edges iterator to return all regions #53178
120 if region_sup
== static_region
&& D
::is_normal() {
125 next_static_idx
: Some(0),
129 //otherwise, just setup the iterator as normal
130 let first
= self.first_constraints
[region_sup
];
131 Edges { graph: self, constraints, pointer: first, next_static_idx: None, static_region }
136 pub(crate) struct Edges
<'s
, 'tcx
, D
: ConstraintGraphDirecton
> {
137 graph
: &'s ConstraintGraph
<D
>,
138 constraints
: &'s OutlivesConstraintSet
<'tcx
>,
139 pointer
: Option
<OutlivesConstraintIndex
>,
140 next_static_idx
: Option
<usize>,
141 static_region
: RegionVid
,
144 impl<'s
, 'tcx
, D
: ConstraintGraphDirecton
> Iterator
for Edges
<'s
, 'tcx
, D
> {
145 type Item
= OutlivesConstraint
<'tcx
>;
147 fn next(&mut self) -> Option
<Self::Item
> {
148 if let Some(p
) = self.pointer
{
149 self.pointer
= self.graph
.next_constraints
[p
];
151 Some(self.constraints
[p
].clone())
152 } else if let Some(next_static_idx
) = self.next_static_idx
{
153 self.next_static_idx
= if next_static_idx
== (self.graph
.first_constraints
.len() - 1) {
156 Some(next_static_idx
+ 1)
159 Some(OutlivesConstraint
{
160 sup
: self.static_region
,
161 sub
: next_static_idx
.into(),
162 locations
: Locations
::All(DUMMY_SP
),
164 category
: ConstraintCategory
::Internal
,
165 variance_info
: VarianceDiagInfo
::default(),
173 /// This struct brings together a constraint set and a (normal, not
174 /// reverse) constraint graph. It implements the graph traits and is
175 /// usd for doing the SCC computation.
176 pub(crate) struct RegionGraph
<'s
, 'tcx
, D
: ConstraintGraphDirecton
> {
177 set
: &'s OutlivesConstraintSet
<'tcx
>,
178 constraint_graph
: &'s ConstraintGraph
<D
>,
179 static_region
: RegionVid
,
182 impl<'s
, 'tcx
, D
: ConstraintGraphDirecton
> RegionGraph
<'s
, 'tcx
, D
> {
183 /// Creates a "dependency graph" where each region constraint `R1:
184 /// R2` is treated as an edge `R1 -> R2`. We use this graph to
185 /// construct SCCs for region inference but also for error
188 set
: &'s OutlivesConstraintSet
<'tcx
>,
189 constraint_graph
: &'s ConstraintGraph
<D
>,
190 static_region
: RegionVid
,
192 Self { set, constraint_graph, static_region }
195 /// Given a region `R`, iterate over all regions `R1` such that
196 /// there exists a constraint `R: R1`.
197 pub(crate) fn outgoing_regions(&self, region_sup
: RegionVid
) -> Successors
<'s
, 'tcx
, D
> {
199 edges
: self.constraint_graph
.outgoing_edges(region_sup
, self.set
, self.static_region
),
204 pub(crate) struct Successors
<'s
, 'tcx
, D
: ConstraintGraphDirecton
> {
205 edges
: Edges
<'s
, 'tcx
, D
>,
208 impl<'s
, 'tcx
, D
: ConstraintGraphDirecton
> Iterator
for Successors
<'s
, 'tcx
, D
> {
209 type Item
= RegionVid
;
211 fn next(&mut self) -> Option
<Self::Item
> {
212 self.edges
.next().map(|c
| D
::end_region(&c
))
216 impl<'s
, 'tcx
, D
: ConstraintGraphDirecton
> graph
::DirectedGraph
for RegionGraph
<'s
, 'tcx
, D
> {
217 type Node
= RegionVid
;
220 impl<'s
, 'tcx
, D
: ConstraintGraphDirecton
> graph
::WithNumNodes
for RegionGraph
<'s
, 'tcx
, D
> {
221 fn num_nodes(&self) -> usize {
222 self.constraint_graph
.first_constraints
.len()
226 impl<'s
, 'tcx
, D
: ConstraintGraphDirecton
> graph
::WithSuccessors
for RegionGraph
<'s
, 'tcx
, D
> {
227 fn successors(&self, node
: Self::Node
) -> <Self as graph
::GraphSuccessors
<'_
>>::Iter
{
228 self.outgoing_regions(node
)
232 impl<'s
, 'tcx
, D
: ConstraintGraphDirecton
> graph
::GraphSuccessors
<'_
> for RegionGraph
<'s
, 'tcx
, D
> {
233 type Item
= RegionVid
;
234 type Iter
= Successors
<'s
, 'tcx
, D
>;