]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | use crate::borrow_check::nll::type_check::Locations; |
dc9dc135 XL |
2 | use crate::borrow_check::nll::constraints::OutlivesConstraintIndex; |
3 | use crate::borrow_check::nll::constraints::{OutlivesConstraintSet, OutlivesConstraint}; | |
0bf4aa26 | 4 | use rustc::mir::ConstraintCategory; |
8faf50e0 XL |
5 | use rustc::ty::RegionVid; |
6 | use rustc_data_structures::graph; | |
e74abb32 | 7 | use rustc_index::vec::IndexVec; |
0bf4aa26 | 8 | use syntax_pos::DUMMY_SP; |
8faf50e0 | 9 | |
b7449926 XL |
10 | /// The construct graph organizes the constraints by their end-points. |
11 | /// It can be used to view a `R1: R2` constraint as either an edge `R1 | |
12 | /// -> R2` or `R2 -> R1` depending on the direction type `D`. | |
13 | crate struct ConstraintGraph<D: ConstraintGraphDirecton> { | |
14 | _direction: D, | |
dc9dc135 XL |
15 | first_constraints: IndexVec<RegionVid, Option<OutlivesConstraintIndex>>, |
16 | next_constraints: IndexVec<OutlivesConstraintIndex, Option<OutlivesConstraintIndex>>, | |
8faf50e0 XL |
17 | } |
18 | ||
b7449926 XL |
19 | crate type NormalConstraintGraph = ConstraintGraph<Normal>; |
20 | ||
21 | crate type ReverseConstraintGraph = ConstraintGraph<Reverse>; | |
22 | ||
23 | /// Marker trait that controls whether a `R1: R2` constraint | |
24 | /// represents an edge `R1 -> R2` or `R2 -> R1`. | |
25 | crate trait ConstraintGraphDirecton: Copy + 'static { | |
26 | fn start_region(c: &OutlivesConstraint) -> RegionVid; | |
27 | fn end_region(c: &OutlivesConstraint) -> RegionVid; | |
28 | fn is_normal() -> bool; | |
29 | } | |
30 | ||
31 | /// In normal mode, a `R1: R2` constraint results in an edge `R1 -> | |
32 | /// R2`. This is what we use when constructing the SCCs for | |
33 | /// inference. This is because we compute the value of R1 by union'ing | |
34 | /// all the things that it relies on. | |
35 | #[derive(Copy, Clone, Debug)] | |
36 | crate struct Normal; | |
37 | ||
38 | impl ConstraintGraphDirecton for Normal { | |
39 | fn start_region(c: &OutlivesConstraint) -> RegionVid { | |
40 | c.sup | |
41 | } | |
42 | ||
43 | fn end_region(c: &OutlivesConstraint) -> RegionVid { | |
44 | c.sub | |
45 | } | |
46 | ||
47 | fn is_normal() -> bool { | |
48 | true | |
49 | } | |
50 | } | |
51 | ||
52 | /// In reverse mode, a `R1: R2` constraint results in an edge `R2 -> | |
53 | /// R1`. We use this for optimizing liveness computation, because then | |
54 | /// we wish to iterate from a region (e.g., R2) to all the regions | |
55 | /// that will outlive it (e.g., R1). | |
56 | #[derive(Copy, Clone, Debug)] | |
57 | crate struct Reverse; | |
58 | ||
59 | impl ConstraintGraphDirecton for Reverse { | |
60 | fn start_region(c: &OutlivesConstraint) -> RegionVid { | |
61 | c.sub | |
62 | } | |
63 | ||
64 | fn end_region(c: &OutlivesConstraint) -> RegionVid { | |
65 | c.sup | |
66 | } | |
67 | ||
68 | fn is_normal() -> bool { | |
69 | false | |
70 | } | |
71 | } | |
72 | ||
73 | impl<D: ConstraintGraphDirecton> ConstraintGraph<D> { | |
9fa01778 | 74 | /// Creates a "dependency graph" where each region constraint `R1: |
8faf50e0 XL |
75 | /// R2` is treated as an edge `R1 -> R2`. We use this graph to |
76 | /// construct SCCs for region inference but also for error | |
77 | /// reporting. | |
b7449926 XL |
78 | crate fn new( |
79 | direction: D, | |
dc9dc135 | 80 | set: &OutlivesConstraintSet, |
b7449926 XL |
81 | num_region_vars: usize, |
82 | ) -> Self { | |
8faf50e0 | 83 | let mut first_constraints = IndexVec::from_elem_n(None, num_region_vars); |
dc9dc135 | 84 | let mut next_constraints = IndexVec::from_elem(None, &set.outlives); |
8faf50e0 | 85 | |
dc9dc135 | 86 | for (idx, constraint) in set.outlives.iter_enumerated().rev() { |
b7449926 | 87 | let head = &mut first_constraints[D::start_region(constraint)]; |
8faf50e0 XL |
88 | let next = &mut next_constraints[idx]; |
89 | debug_assert!(next.is_none()); | |
90 | *next = *head; | |
91 | *head = Some(idx); | |
92 | } | |
93 | ||
94 | Self { | |
b7449926 | 95 | _direction: direction, |
8faf50e0 XL |
96 | first_constraints, |
97 | next_constraints, | |
98 | } | |
99 | } | |
100 | ||
b7449926 XL |
101 | /// Given the constraint set from which this graph was built |
102 | /// creates a region graph so that you can iterate over *regions* | |
103 | /// and not constraints. | |
104 | crate fn region_graph<'rg>( | |
105 | &'rg self, | |
dc9dc135 | 106 | set: &'rg OutlivesConstraintSet, |
b7449926 XL |
107 | static_region: RegionVid, |
108 | ) -> RegionGraph<'rg, D> { | |
109 | RegionGraph::new(set, self, static_region) | |
110 | } | |
111 | ||
8faf50e0 | 112 | /// Given a region `R`, iterate over all constraints `R: R1`. |
b7449926 XL |
113 | crate fn outgoing_edges<'a>( |
114 | &'a self, | |
115 | region_sup: RegionVid, | |
dc9dc135 | 116 | constraints: &'a OutlivesConstraintSet, |
b7449926 XL |
117 | static_region: RegionVid, |
118 | ) -> Edges<'a, D> { | |
119 | //if this is the `'static` region and the graph's direction is normal, | |
120 | //then setup the Edges iterator to return all regions #53178 | |
121 | if region_sup == static_region && D::is_normal() { | |
122 | Edges { | |
123 | graph: self, | |
124 | constraints, | |
125 | pointer: None, | |
126 | next_static_idx: Some(0), | |
127 | static_region, | |
128 | } | |
129 | } else { | |
130 | //otherwise, just setup the iterator as normal | |
131 | let first = self.first_constraints[region_sup]; | |
132 | Edges { | |
133 | graph: self, | |
134 | constraints, | |
135 | pointer: first, | |
136 | next_static_idx: None, | |
137 | static_region, | |
138 | } | |
8faf50e0 XL |
139 | } |
140 | } | |
141 | } | |
142 | ||
b7449926 XL |
143 | crate struct Edges<'s, D: ConstraintGraphDirecton> { |
144 | graph: &'s ConstraintGraph<D>, | |
dc9dc135 XL |
145 | constraints: &'s OutlivesConstraintSet, |
146 | pointer: Option<OutlivesConstraintIndex>, | |
b7449926 XL |
147 | next_static_idx: Option<usize>, |
148 | static_region: RegionVid, | |
8faf50e0 XL |
149 | } |
150 | ||
b7449926 XL |
151 | impl<'s, D: ConstraintGraphDirecton> Iterator for Edges<'s, D> { |
152 | type Item = OutlivesConstraint; | |
8faf50e0 XL |
153 | |
154 | fn next(&mut self) -> Option<Self::Item> { | |
155 | if let Some(p) = self.pointer { | |
156 | self.pointer = self.graph.next_constraints[p]; | |
b7449926 XL |
157 | |
158 | Some(self.constraints[p]) | |
159 | } else if let Some(next_static_idx) = self.next_static_idx { | |
160 | self.next_static_idx = | |
161 | if next_static_idx == (self.graph.first_constraints.len() - 1) { | |
162 | None | |
163 | } else { | |
164 | Some(next_static_idx + 1) | |
165 | }; | |
166 | ||
167 | Some(OutlivesConstraint { | |
168 | sup: self.static_region, | |
169 | sub: next_static_idx.into(), | |
0bf4aa26 XL |
170 | locations: Locations::All(DUMMY_SP), |
171 | category: ConstraintCategory::Internal, | |
b7449926 | 172 | }) |
8faf50e0 XL |
173 | } else { |
174 | None | |
175 | } | |
176 | } | |
177 | } | |
178 | ||
b7449926 XL |
179 | /// This struct brings together a constraint set and a (normal, not |
180 | /// reverse) constraint graph. It implements the graph traits and is | |
181 | /// usd for doing the SCC computation. | |
182 | crate struct RegionGraph<'s, D: ConstraintGraphDirecton> { | |
dc9dc135 | 183 | set: &'s OutlivesConstraintSet, |
b7449926 XL |
184 | constraint_graph: &'s ConstraintGraph<D>, |
185 | static_region: RegionVid, | |
8faf50e0 XL |
186 | } |
187 | ||
b7449926 | 188 | impl<'s, D: ConstraintGraphDirecton> RegionGraph<'s, D> { |
9fa01778 | 189 | /// Creates a "dependency graph" where each region constraint `R1: |
8faf50e0 XL |
190 | /// R2` is treated as an edge `R1 -> R2`. We use this graph to |
191 | /// construct SCCs for region inference but also for error | |
192 | /// reporting. | |
b7449926 | 193 | crate fn new( |
dc9dc135 | 194 | set: &'s OutlivesConstraintSet, |
b7449926 XL |
195 | constraint_graph: &'s ConstraintGraph<D>, |
196 | static_region: RegionVid, | |
197 | ) -> Self { | |
8faf50e0 XL |
198 | Self { |
199 | set, | |
200 | constraint_graph, | |
b7449926 | 201 | static_region, |
8faf50e0 XL |
202 | } |
203 | } | |
204 | ||
205 | /// Given a region `R`, iterate over all regions `R1` such that | |
206 | /// there exists a constraint `R: R1`. | |
b7449926 | 207 | crate fn outgoing_regions(&self, region_sup: RegionVid) -> Successors<'_, D> { |
8faf50e0 | 208 | Successors { |
b7449926 | 209 | edges: self.constraint_graph.outgoing_edges(region_sup, self.set, self.static_region), |
8faf50e0 XL |
210 | } |
211 | } | |
212 | } | |
213 | ||
b7449926 XL |
214 | crate struct Successors<'s, D: ConstraintGraphDirecton> { |
215 | edges: Edges<'s, D>, | |
8faf50e0 XL |
216 | } |
217 | ||
b7449926 | 218 | impl<'s, D: ConstraintGraphDirecton> Iterator for Successors<'s, D> { |
8faf50e0 XL |
219 | type Item = RegionVid; |
220 | ||
221 | fn next(&mut self) -> Option<Self::Item> { | |
b7449926 | 222 | self.edges.next().map(|c| D::end_region(&c)) |
8faf50e0 XL |
223 | } |
224 | } | |
225 | ||
b7449926 | 226 | impl<'s, D: ConstraintGraphDirecton> graph::DirectedGraph for RegionGraph<'s, D> { |
8faf50e0 XL |
227 | type Node = RegionVid; |
228 | } | |
229 | ||
b7449926 | 230 | impl<'s, D: ConstraintGraphDirecton> graph::WithNumNodes for RegionGraph<'s, D> { |
8faf50e0 XL |
231 | fn num_nodes(&self) -> usize { |
232 | self.constraint_graph.first_constraints.len() | |
233 | } | |
234 | } | |
235 | ||
b7449926 | 236 | impl<'s, D: ConstraintGraphDirecton> graph::WithSuccessors for RegionGraph<'s, D> { |
416331ca XL |
237 | fn successors( |
238 | &self, | |
8faf50e0 | 239 | node: Self::Node, |
416331ca | 240 | ) -> <Self as graph::GraphSuccessors<'_>>::Iter { |
b7449926 | 241 | self.outgoing_regions(node) |
8faf50e0 XL |
242 | } |
243 | } | |
244 | ||
b7449926 | 245 | impl<'s, 'graph, D: ConstraintGraphDirecton> graph::GraphSuccessors<'graph> for RegionGraph<'s, D> { |
8faf50e0 | 246 | type Item = RegionVid; |
b7449926 | 247 | type Iter = Successors<'graph, D>; |
8faf50e0 | 248 | } |