]>
Commit | Line | Data |
---|---|---|
8faf50e0 | 1 | use rustc_data_structures::graph; |
e74abb32 | 2 | use rustc_index::vec::IndexVec; |
ba9703b0 | 3 | use rustc_middle::mir::ConstraintCategory; |
17df50a5 | 4 | use rustc_middle::ty::{RegionVid, VarianceDiagInfo}; |
dfeec247 | 5 | use rustc_span::DUMMY_SP; |
8faf50e0 | 6 | |
c295e0f8 | 7 | use crate::{ |
60c5eb7d | 8 | constraints::OutlivesConstraintIndex, |
dfeec247 XL |
9 | constraints::{OutlivesConstraint, OutlivesConstraintSet}, |
10 | type_check::Locations, | |
60c5eb7d XL |
11 | }; |
12 | ||
b7449926 XL |
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`. | |
923072b8 | 16 | pub(crate) struct ConstraintGraph<D: ConstraintGraphDirecton> { |
b7449926 | 17 | _direction: D, |
dc9dc135 XL |
18 | first_constraints: IndexVec<RegionVid, Option<OutlivesConstraintIndex>>, |
19 | next_constraints: IndexVec<OutlivesConstraintIndex, Option<OutlivesConstraintIndex>>, | |
8faf50e0 XL |
20 | } |
21 | ||
923072b8 | 22 | pub(crate) type NormalConstraintGraph = ConstraintGraph<Normal>; |
b7449926 | 23 | |
923072b8 | 24 | pub(crate) type ReverseConstraintGraph = ConstraintGraph<Reverse>; |
b7449926 XL |
25 | |
26 | /// Marker trait that controls whether a `R1: R2` constraint | |
27 | /// represents an edge `R1 -> R2` or `R2 -> R1`. | |
923072b8 | 28 | pub(crate) trait ConstraintGraphDirecton: Copy + 'static { |
17df50a5 XL |
29 | fn start_region(c: &OutlivesConstraint<'_>) -> RegionVid; |
30 | fn end_region(c: &OutlivesConstraint<'_>) -> RegionVid; | |
b7449926 XL |
31 | fn is_normal() -> bool; |
32 | } | |
33 | ||
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)] | |
923072b8 | 39 | pub(crate) struct Normal; |
b7449926 XL |
40 | |
41 | impl ConstraintGraphDirecton for Normal { | |
17df50a5 | 42 | fn start_region(c: &OutlivesConstraint<'_>) -> RegionVid { |
b7449926 XL |
43 | c.sup |
44 | } | |
45 | ||
17df50a5 | 46 | fn end_region(c: &OutlivesConstraint<'_>) -> RegionVid { |
b7449926 XL |
47 | c.sub |
48 | } | |
49 | ||
50 | fn is_normal() -> bool { | |
51 | true | |
52 | } | |
53 | } | |
54 | ||
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)] | |
923072b8 | 60 | pub(crate) struct Reverse; |
b7449926 XL |
61 | |
62 | impl ConstraintGraphDirecton for Reverse { | |
17df50a5 | 63 | fn start_region(c: &OutlivesConstraint<'_>) -> RegionVid { |
b7449926 XL |
64 | c.sub |
65 | } | |
66 | ||
17df50a5 | 67 | fn end_region(c: &OutlivesConstraint<'_>) -> RegionVid { |
b7449926 XL |
68 | c.sup |
69 | } | |
70 | ||
71 | fn is_normal() -> bool { | |
72 | false | |
73 | } | |
74 | } | |
75 | ||
76 | impl<D: ConstraintGraphDirecton> ConstraintGraph<D> { | |
9fa01778 | 77 | /// Creates a "dependency graph" where each region constraint `R1: |
8faf50e0 XL |
78 | /// R2` is treated as an edge `R1 -> R2`. We use this graph to |
79 | /// construct SCCs for region inference but also for error | |
80 | /// reporting. | |
923072b8 FG |
81 | pub(crate) fn new( |
82 | direction: D, | |
83 | set: &OutlivesConstraintSet<'_>, | |
84 | num_region_vars: usize, | |
85 | ) -> Self { | |
8faf50e0 | 86 | let mut first_constraints = IndexVec::from_elem_n(None, num_region_vars); |
dc9dc135 | 87 | let mut next_constraints = IndexVec::from_elem(None, &set.outlives); |
8faf50e0 | 88 | |
dc9dc135 | 89 | for (idx, constraint) in set.outlives.iter_enumerated().rev() { |
b7449926 | 90 | let head = &mut first_constraints[D::start_region(constraint)]; |
8faf50e0 XL |
91 | let next = &mut next_constraints[idx]; |
92 | debug_assert!(next.is_none()); | |
93 | *next = *head; | |
94 | *head = Some(idx); | |
95 | } | |
96 | ||
dfeec247 | 97 | Self { _direction: direction, first_constraints, next_constraints } |
8faf50e0 XL |
98 | } |
99 | ||
b7449926 XL |
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. | |
923072b8 | 103 | pub(crate) fn region_graph<'rg, 'tcx>( |
b7449926 | 104 | &'rg self, |
17df50a5 | 105 | set: &'rg OutlivesConstraintSet<'tcx>, |
b7449926 | 106 | static_region: RegionVid, |
17df50a5 | 107 | ) -> RegionGraph<'rg, 'tcx, D> { |
b7449926 XL |
108 | RegionGraph::new(set, self, static_region) |
109 | } | |
110 | ||
8faf50e0 | 111 | /// Given a region `R`, iterate over all constraints `R: R1`. |
923072b8 | 112 | pub(crate) fn outgoing_edges<'a, 'tcx>( |
b7449926 XL |
113 | &'a self, |
114 | region_sup: RegionVid, | |
17df50a5 | 115 | constraints: &'a OutlivesConstraintSet<'tcx>, |
b7449926 | 116 | static_region: RegionVid, |
17df50a5 | 117 | ) -> Edges<'a, 'tcx, D> { |
b7449926 XL |
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() { | |
121 | Edges { | |
122 | graph: self, | |
123 | constraints, | |
124 | pointer: None, | |
125 | next_static_idx: Some(0), | |
126 | static_region, | |
127 | } | |
128 | } else { | |
129 | //otherwise, just setup the iterator as normal | |
130 | let first = self.first_constraints[region_sup]; | |
dfeec247 | 131 | Edges { graph: self, constraints, pointer: first, next_static_idx: None, static_region } |
8faf50e0 XL |
132 | } |
133 | } | |
134 | } | |
135 | ||
923072b8 | 136 | pub(crate) struct Edges<'s, 'tcx, D: ConstraintGraphDirecton> { |
b7449926 | 137 | graph: &'s ConstraintGraph<D>, |
17df50a5 | 138 | constraints: &'s OutlivesConstraintSet<'tcx>, |
dc9dc135 | 139 | pointer: Option<OutlivesConstraintIndex>, |
b7449926 XL |
140 | next_static_idx: Option<usize>, |
141 | static_region: RegionVid, | |
8faf50e0 XL |
142 | } |
143 | ||
17df50a5 XL |
144 | impl<'s, 'tcx, D: ConstraintGraphDirecton> Iterator for Edges<'s, 'tcx, D> { |
145 | type Item = OutlivesConstraint<'tcx>; | |
8faf50e0 XL |
146 | |
147 | fn next(&mut self) -> Option<Self::Item> { | |
148 | if let Some(p) = self.pointer { | |
149 | self.pointer = self.graph.next_constraints[p]; | |
b7449926 | 150 | |
17df50a5 | 151 | Some(self.constraints[p].clone()) |
b7449926 | 152 | } else if let Some(next_static_idx) = self.next_static_idx { |
dfeec247 XL |
153 | self.next_static_idx = if next_static_idx == (self.graph.first_constraints.len() - 1) { |
154 | None | |
155 | } else { | |
156 | Some(next_static_idx + 1) | |
157 | }; | |
b7449926 XL |
158 | |
159 | Some(OutlivesConstraint { | |
160 | sup: self.static_region, | |
161 | sub: next_static_idx.into(), | |
0bf4aa26 | 162 | locations: Locations::All(DUMMY_SP), |
04454e1e | 163 | span: DUMMY_SP, |
0bf4aa26 | 164 | category: ConstraintCategory::Internal, |
17df50a5 | 165 | variance_info: VarianceDiagInfo::default(), |
b7449926 | 166 | }) |
8faf50e0 XL |
167 | } else { |
168 | None | |
169 | } | |
170 | } | |
171 | } | |
172 | ||
b7449926 XL |
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. | |
923072b8 | 176 | pub(crate) struct RegionGraph<'s, 'tcx, D: ConstraintGraphDirecton> { |
17df50a5 | 177 | set: &'s OutlivesConstraintSet<'tcx>, |
b7449926 XL |
178 | constraint_graph: &'s ConstraintGraph<D>, |
179 | static_region: RegionVid, | |
8faf50e0 XL |
180 | } |
181 | ||
17df50a5 | 182 | impl<'s, 'tcx, D: ConstraintGraphDirecton> RegionGraph<'s, 'tcx, D> { |
9fa01778 | 183 | /// Creates a "dependency graph" where each region constraint `R1: |
8faf50e0 XL |
184 | /// R2` is treated as an edge `R1 -> R2`. We use this graph to |
185 | /// construct SCCs for region inference but also for error | |
186 | /// reporting. | |
923072b8 | 187 | pub(crate) fn new( |
17df50a5 | 188 | set: &'s OutlivesConstraintSet<'tcx>, |
b7449926 XL |
189 | constraint_graph: &'s ConstraintGraph<D>, |
190 | static_region: RegionVid, | |
191 | ) -> Self { | |
dfeec247 | 192 | Self { set, constraint_graph, static_region } |
8faf50e0 XL |
193 | } |
194 | ||
195 | /// Given a region `R`, iterate over all regions `R1` such that | |
196 | /// there exists a constraint `R: R1`. | |
923072b8 | 197 | pub(crate) fn outgoing_regions(&self, region_sup: RegionVid) -> Successors<'s, 'tcx, D> { |
8faf50e0 | 198 | Successors { |
b7449926 | 199 | edges: self.constraint_graph.outgoing_edges(region_sup, self.set, self.static_region), |
8faf50e0 XL |
200 | } |
201 | } | |
202 | } | |
203 | ||
923072b8 | 204 | pub(crate) struct Successors<'s, 'tcx, D: ConstraintGraphDirecton> { |
17df50a5 | 205 | edges: Edges<'s, 'tcx, D>, |
8faf50e0 XL |
206 | } |
207 | ||
17df50a5 | 208 | impl<'s, 'tcx, D: ConstraintGraphDirecton> Iterator for Successors<'s, 'tcx, D> { |
8faf50e0 XL |
209 | type Item = RegionVid; |
210 | ||
211 | fn next(&mut self) -> Option<Self::Item> { | |
b7449926 | 212 | self.edges.next().map(|c| D::end_region(&c)) |
8faf50e0 XL |
213 | } |
214 | } | |
215 | ||
17df50a5 | 216 | impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, 'tcx, D> { |
8faf50e0 XL |
217 | type Node = RegionVid; |
218 | } | |
219 | ||
17df50a5 | 220 | impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, 'tcx, D> { |
8faf50e0 XL |
221 | fn num_nodes(&self) -> usize { |
222 | self.constraint_graph.first_constraints.len() | |
223 | } | |
224 | } | |
225 | ||
17df50a5 | 226 | impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::WithSuccessors for RegionGraph<'s, 'tcx, D> { |
dfeec247 | 227 | fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter { |
b7449926 | 228 | self.outgoing_regions(node) |
8faf50e0 XL |
229 | } |
230 | } | |
231 | ||
04454e1e | 232 | impl<'s, 'tcx, D: ConstraintGraphDirecton> graph::GraphSuccessors<'_> for RegionGraph<'s, 'tcx, D> { |
8faf50e0 | 233 | type Item = RegionVid; |
04454e1e | 234 | type Iter = Successors<'s, 'tcx, D>; |
8faf50e0 | 235 | } |