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