]>
Commit | Line | Data |
---|---|---|
3dfed10e | 1 | use crate::fx::FxIndexSet; |
9fa01778 | 2 | use crate::sync::Lock; |
dfeec247 | 3 | use rustc_index::bit_set::BitMatrix; |
e9174d1e | 4 | use std::fmt::Debug; |
7cac9316 | 5 | use std::hash::Hash; |
e9174d1e SL |
6 | use std::mem; |
7 | ||
416331ca XL |
8 | #[cfg(test)] |
9 | mod tests; | |
cc61c64b | 10 | |
ea8adc8c | 11 | #[derive(Clone, Debug)] |
6a06907d | 12 | pub struct TransitiveRelation<T> { |
7cac9316 | 13 | // List of elements. This is used to map from a T to a usize. |
3dfed10e | 14 | elements: FxIndexSet<T>, |
7cac9316 | 15 | |
e9174d1e SL |
16 | // List of base edges in the graph. Require to compute transitive |
17 | // closure. | |
18 | edges: Vec<Edge>, | |
19 | ||
20 | // This is a cached transitive closure derived from the edges. | |
29967ef6 | 21 | // Currently, we build it lazily and just throw out any existing |
0531ce1d | 22 | // copy whenever a new edge is added. (The Lock is to permit |
e9174d1e SL |
23 | // the lazy computation.) This is kind of silly, except for the |
24 | // fact its size is tied to `self.elements.len()`, so I wanted to | |
25 | // wait before building it up to avoid reallocating as new edges | |
26 | // are added with new elements. Perhaps better would be to ask the | |
27 | // user for a batch of edges to minimize this effect, but I | |
28 | // already wrote the code this way. :P -nmatsakis | |
8faf50e0 | 29 | closure: Lock<Option<BitMatrix<usize, usize>>>, |
e9174d1e SL |
30 | } |
31 | ||
a1dfa0c6 | 32 | // HACK(eddyb) manual impl avoids `Default` bound on `T`. |
e74abb32 | 33 | impl<T: Eq + Hash> Default for TransitiveRelation<T> { |
a1dfa0c6 XL |
34 | fn default() -> Self { |
35 | TransitiveRelation { | |
36 | elements: Default::default(), | |
a1dfa0c6 XL |
37 | edges: Default::default(), |
38 | closure: Default::default(), | |
39 | } | |
40 | } | |
41 | } | |
42 | ||
3dfed10e | 43 | #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Debug)] |
e9174d1e SL |
44 | struct Index(usize); |
45 | ||
3dfed10e | 46 | #[derive(Clone, PartialEq, Eq, Debug)] |
e9174d1e SL |
47 | struct Edge { |
48 | source: Index, | |
49 | target: Index, | |
50 | } | |
51 | ||
6a06907d | 52 | impl<T: Eq + Hash> TransitiveRelation<T> { |
8bb4bdeb XL |
53 | pub fn is_empty(&self) -> bool { |
54 | self.edges.is_empty() | |
55 | } | |
56 | ||
dfeec247 | 57 | pub fn elements(&self) -> impl Iterator<Item = &T> { |
dc9dc135 XL |
58 | self.elements.iter() |
59 | } | |
60 | ||
e9174d1e | 61 | fn index(&self, a: &T) -> Option<Index> { |
3dfed10e | 62 | self.elements.get_index_of(a).map(Index) |
e9174d1e SL |
63 | } |
64 | ||
65 | fn add_index(&mut self, a: T) -> Index { | |
3dfed10e XL |
66 | let (index, added) = self.elements.insert_full(a); |
67 | if added { | |
dfeec247 | 68 | // if we changed the dimensions, clear the cache |
3dfed10e XL |
69 | *self.closure.get_mut() = None; |
70 | } | |
71 | Index(index) | |
7cac9316 | 72 | } |
e9174d1e | 73 | |
7cac9316 | 74 | /// Applies the (partial) function to each edge and returns a new |
9fa01778 | 75 | /// relation. If `f` returns `None` for any end-point, returns |
7cac9316 XL |
76 | /// `None`. |
77 | pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>> | |
dfeec247 XL |
78 | where |
79 | F: FnMut(&T) -> Option<U>, | |
80 | U: Clone + Debug + Eq + Hash + Clone, | |
7cac9316 | 81 | { |
0bf4aa26 | 82 | let mut result = TransitiveRelation::default(); |
7cac9316 | 83 | for edge in &self.edges { |
b7449926 | 84 | result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?); |
e9174d1e | 85 | } |
7cac9316 | 86 | Some(result) |
e9174d1e SL |
87 | } |
88 | ||
89 | /// Indicate that `a < b` (where `<` is this relation) | |
90 | pub fn add(&mut self, a: T, b: T) { | |
91 | let a = self.add_index(a); | |
92 | let b = self.add_index(b); | |
dfeec247 | 93 | let edge = Edge { source: a, target: b }; |
e9174d1e SL |
94 | if !self.edges.contains(&edge) { |
95 | self.edges.push(edge); | |
96 | ||
97 | // added an edge, clear the cache | |
0531ce1d | 98 | *self.closure.get_mut() = None; |
e9174d1e SL |
99 | } |
100 | } | |
101 | ||
9fa01778 | 102 | /// Checks whether `a < target` (transitively) |
e9174d1e SL |
103 | pub fn contains(&self, a: &T, b: &T) -> bool { |
104 | match (self.index(a), self.index(b)) { | |
54a0048b SL |
105 | (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)), |
106 | (None, _) | (_, None) => false, | |
e9174d1e SL |
107 | } |
108 | } | |
109 | ||
ff7c6d11 XL |
110 | /// Thinking of `x R y` as an edge `x -> y` in a graph, this |
111 | /// returns all things reachable from `a`. | |
7cac9316 | 112 | /// |
9fa01778 | 113 | /// Really this probably ought to be `impl Iterator<Item = &T>`, but |
7cac9316 XL |
114 | /// I'm too lazy to make that work, and -- given the caching |
115 | /// strategy -- it'd be a touch tricky anyhow. | |
ff7c6d11 | 116 | pub fn reachable_from(&self, a: &T) -> Vec<&T> { |
7cac9316 | 117 | match self.index(a) { |
dfeec247 XL |
118 | Some(a) => { |
119 | self.with_closure(|closure| closure.iter(a.0).map(|i| &self.elements[i]).collect()) | |
120 | } | |
7cac9316 XL |
121 | None => vec![], |
122 | } | |
123 | } | |
124 | ||
e9174d1e SL |
125 | /// Picks what I am referring to as the "postdominating" |
126 | /// upper-bound for `a` and `b`. This is usually the least upper | |
127 | /// bound, but in cases where there is no single least upper | |
128 | /// bound, it is the "mutual immediate postdominator", if you | |
129 | /// imagine a graph where `a < b` means `a -> b`. | |
130 | /// | |
131 | /// This function is needed because region inference currently | |
132 | /// requires that we produce a single "UB", and there is no best | |
133 | /// choice for the LUB. Rather than pick arbitrarily, I pick a | |
134 | /// less good, but predictable choice. This should help ensure | |
135 | /// that region inference yields predictable results (though it | |
136 | /// itself is not fully sufficient). | |
137 | /// | |
138 | /// Examples are probably clearer than any prose I could write | |
139 | /// (there are corresponding tests below, btw). In each case, | |
140 | /// the query is `postdom_upper_bound(a, b)`: | |
141 | /// | |
142 | /// ```text | |
9fa01778 | 143 | /// // Returns Some(x), which is also LUB. |
e9174d1e SL |
144 | /// a -> a1 -> x |
145 | /// ^ | |
146 | /// | | |
147 | /// b -> b1 ---+ | |
148 | /// | |
9fa01778 XL |
149 | /// // Returns `Some(x)`, which is not LUB (there is none) |
150 | /// // diagonal edges run left-to-right. | |
e9174d1e SL |
151 | /// a -> a1 -> x |
152 | /// \/ ^ | |
153 | /// /\ | | |
154 | /// b -> b1 ---+ | |
155 | /// | |
9fa01778 | 156 | /// // Returns `None`. |
e9174d1e SL |
157 | /// a -> a1 |
158 | /// b -> b1 | |
159 | /// ``` | |
160 | pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> { | |
ff7c6d11 XL |
161 | let mubs = self.minimal_upper_bounds(a, b); |
162 | self.mutual_immediate_postdominator(mubs) | |
163 | } | |
164 | ||
165 | /// Viewing the relation as a graph, computes the "mutual | |
166 | /// immediate postdominator" of a set of points (if one | |
167 | /// exists). See `postdom_upper_bound` for details. | |
168 | pub fn mutual_immediate_postdominator<'a>(&'a self, mut mubs: Vec<&'a T>) -> Option<&'a T> { | |
e9174d1e SL |
169 | loop { |
170 | match mubs.len() { | |
171 | 0 => return None, | |
172 | 1 => return Some(mubs[0]), | |
173 | _ => { | |
174 | let m = mubs.pop().unwrap(); | |
175 | let n = mubs.pop().unwrap(); | |
176 | mubs.extend(self.minimal_upper_bounds(n, m)); | |
177 | } | |
178 | } | |
179 | } | |
180 | } | |
181 | ||
182 | /// Returns the set of bounds `X` such that: | |
183 | /// | |
184 | /// - `a < X` and `b < X` | |
185 | /// - there is no `Y != X` such that `a < Y` and `Y < X` | |
186 | /// - except for the case where `X < a` (i.e., a strongly connected | |
187 | /// component in the graph). In that case, the smallest | |
188 | /// representative of the SCC is returned (as determined by the | |
189 | /// internal indices). | |
190 | /// | |
191 | /// Note that this set can, in principle, have any size. | |
192 | pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> { | |
193 | let (mut a, mut b) = match (self.index(a), self.index(b)) { | |
194 | (Some(a), Some(b)) => (a, b), | |
54a0048b SL |
195 | (None, _) | (_, None) => { |
196 | return vec![]; | |
197 | } | |
e9174d1e SL |
198 | }; |
199 | ||
200 | // in some cases, there are some arbitrary choices to be made; | |
201 | // it doesn't really matter what we pick, as long as we pick | |
202 | // the same thing consistently when queried, so ensure that | |
203 | // (a, b) are in a consistent relative order | |
204 | if a > b { | |
205 | mem::swap(&mut a, &mut b); | |
206 | } | |
207 | ||
208 | let lub_indices = self.with_closure(|closure| { | |
209 | // Easy case is when either a < b or b < a: | |
210 | if closure.contains(a.0, b.0) { | |
211 | return vec![b.0]; | |
212 | } | |
213 | if closure.contains(b.0, a.0) { | |
214 | return vec![a.0]; | |
215 | } | |
216 | ||
217 | // Otherwise, the tricky part is that there may be some c | |
218 | // where a < c and b < c. In fact, there may be many such | |
219 | // values. So here is what we do: | |
220 | // | |
221 | // 1. Find the vector `[X | a < X && b < X]` of all values | |
222 | // `X` where `a < X` and `b < X`. In terms of the | |
223 | // graph, this means all values reachable from both `a` | |
224 | // and `b`. Note that this vector is also a set, but we | |
225 | // use the term vector because the order matters | |
226 | // to the steps below. | |
227 | // - This vector contains upper bounds, but they are | |
228 | // not minimal upper bounds. So you may have e.g. | |
229 | // `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and | |
230 | // `z < x` and `z < y`: | |
231 | // | |
232 | // z --+---> x ----+----> tcx | |
233 | // | | | |
234 | // | | | |
235 | // +---> y ----+ | |
236 | // | |
237 | // In this case, we really want to return just `[z]`. | |
238 | // The following steps below achieve this by gradually | |
239 | // reducing the list. | |
240 | // 2. Pare down the vector using `pare_down`. This will | |
241 | // remove elements from the vector that can be reached | |
242 | // by an earlier element. | |
243 | // - In the example above, this would convert `[x, y, | |
244 | // tcx, z]` to `[x, y, z]`. Note that `x` and `y` are | |
245 | // still in the vector; this is because while `z < x` | |
246 | // (and `z < y`) holds, `z` comes after them in the | |
247 | // vector. | |
248 | // 3. Reverse the vector and repeat the pare down process. | |
249 | // - In the example above, we would reverse to | |
250 | // `[z, y, x]` and then pare down to `[z]`. | |
251 | // 4. Reverse once more just so that we yield a vector in | |
252 | // increasing order of index. Not necessary, but why not. | |
253 | // | |
254 | // I believe this algorithm yields a minimal set. The | |
255 | // argument is that, after step 2, we know that no element | |
256 | // can reach its successors (in the vector, not the graph). | |
257 | // After step 3, we know that no element can reach any of | |
29967ef6 | 258 | // its predecessors (because of step 2) nor successors |
e9174d1e | 259 | // (because we just called `pare_down`) |
ff7c6d11 XL |
260 | // |
261 | // This same algorithm is used in `parents` below. | |
e9174d1e | 262 | |
0bf4aa26 | 263 | let mut candidates = closure.intersect_rows(a.0, b.0); // (1) |
e9174d1e SL |
264 | pare_down(&mut candidates, closure); // (2) |
265 | candidates.reverse(); // (3a) | |
266 | pare_down(&mut candidates, closure); // (3b) | |
267 | candidates | |
268 | }); | |
269 | ||
dfeec247 XL |
270 | lub_indices |
271 | .into_iter() | |
272 | .rev() // (4) | |
273 | .map(|i| &self.elements[i]) | |
274 | .collect() | |
e9174d1e SL |
275 | } |
276 | ||
ff7c6d11 XL |
277 | /// Given an element A, returns the maximal set {B} of elements B |
278 | /// such that | |
279 | /// | |
280 | /// - A != B | |
281 | /// - A R B is true | |
f9f354fc | 282 | /// - for each i, j: `B[i]` R `B[j]` does not hold |
ff7c6d11 XL |
283 | /// |
284 | /// The intuition is that this moves "one step up" through a lattice | |
285 | /// (where the relation is encoding the `<=` relation for the lattice). | |
0731742a | 286 | /// So e.g., if the relation is `->` and we have |
ff7c6d11 XL |
287 | /// |
288 | /// ``` | |
289 | /// a -> b -> d -> f | |
290 | /// | ^ | |
291 | /// +--> c -> e ---+ | |
292 | /// ``` | |
293 | /// | |
294 | /// then `parents(a)` returns `[b, c]`. The `postdom_parent` function | |
295 | /// would further reduce this to just `f`. | |
296 | pub fn parents(&self, a: &T) -> Vec<&T> { | |
297 | let a = match self.index(a) { | |
298 | Some(a) => a, | |
dfeec247 | 299 | None => return vec![], |
ff7c6d11 XL |
300 | }; |
301 | ||
302 | // Steal the algorithm for `minimal_upper_bounds` above, but | |
303 | // with a slight tweak. In the case where `a R a`, we remove | |
304 | // that from the set of candidates. | |
305 | let ancestors = self.with_closure(|closure| { | |
0bf4aa26 | 306 | let mut ancestors = closure.intersect_rows(a.0, a.0); |
ff7c6d11 XL |
307 | |
308 | // Remove anything that can reach `a`. If this is a | |
309 | // reflexive relation, this will include `a` itself. | |
310 | ancestors.retain(|&e| !closure.contains(e, a.0)); | |
311 | ||
312 | pare_down(&mut ancestors, closure); // (2) | |
313 | ancestors.reverse(); // (3a) | |
314 | pare_down(&mut ancestors, closure); // (3b) | |
315 | ancestors | |
316 | }); | |
317 | ||
dfeec247 XL |
318 | ancestors |
319 | .into_iter() | |
320 | .rev() // (4) | |
321 | .map(|i| &self.elements[i]) | |
322 | .collect() | |
ff7c6d11 XL |
323 | } |
324 | ||
54a0048b | 325 | fn with_closure<OP, R>(&self, op: OP) -> R |
dfeec247 XL |
326 | where |
327 | OP: FnOnce(&BitMatrix<usize, usize>) -> R, | |
e9174d1e SL |
328 | { |
329 | let mut closure_cell = self.closure.borrow_mut(); | |
330 | let mut closure = closure_cell.take(); | |
331 | if closure.is_none() { | |
332 | closure = Some(self.compute_closure()); | |
333 | } | |
334 | let result = op(closure.as_ref().unwrap()); | |
335 | *closure_cell = closure; | |
336 | result | |
337 | } | |
338 | ||
8faf50e0 | 339 | fn compute_closure(&self) -> BitMatrix<usize, usize> { |
dfeec247 | 340 | let mut matrix = BitMatrix::new(self.elements.len(), self.elements.len()); |
e9174d1e SL |
341 | let mut changed = true; |
342 | while changed { | |
343 | changed = false; | |
b7449926 | 344 | for edge in &self.edges { |
e9174d1e | 345 | // add an edge from S -> T |
0bf4aa26 | 346 | changed |= matrix.insert(edge.source.0, edge.target.0); |
e9174d1e SL |
347 | |
348 | // add all outgoing edges from T into S | |
0bf4aa26 | 349 | changed |= matrix.union_rows(edge.target.0, edge.source.0); |
e9174d1e SL |
350 | } |
351 | } | |
352 | matrix | |
353 | } | |
60c5eb7d XL |
354 | |
355 | /// Lists all the base edges in the graph: the initial _non-transitive_ set of element | |
356 | /// relations, which will be later used as the basis for the transitive closure computation. | |
dfeec247 | 357 | pub fn base_edges(&self) -> impl Iterator<Item = (&T, &T)> { |
60c5eb7d XL |
358 | self.edges |
359 | .iter() | |
360 | .map(move |edge| (&self.elements[edge.source.0], &self.elements[edge.target.0])) | |
361 | } | |
e9174d1e SL |
362 | } |
363 | ||
364 | /// Pare down is used as a step in the LUB computation. It edits the | |
365 | /// candidates array in place by removing any element j for which | |
366 | /// there exists an earlier element i<j such that i -> j. That is, | |
367 | /// after you run `pare_down`, you know that for all elements that | |
368 | /// remain in candidates, they cannot reach any of the elements that | |
369 | /// come after them. | |
370 | /// | |
371 | /// Examples follow. Assume that a -> b -> c and x -> y -> z. | |
372 | /// | |
373 | /// - Input: `[a, b, x]`. Output: `[a, x]`. | |
374 | /// - Input: `[b, a, x]`. Output: `[b, a, x]`. | |
375 | /// - Input: `[a, x, b, y]`. Output: `[a, x]`. | |
8faf50e0 | 376 | fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) { |
e9174d1e | 377 | let mut i = 0; |
f035d41b | 378 | while let Some(&candidate_i) = candidates.get(i) { |
e9174d1e SL |
379 | i += 1; |
380 | ||
381 | let mut j = i; | |
382 | let mut dead = 0; | |
f035d41b | 383 | while let Some(&candidate_j) = candidates.get(j) { |
e9174d1e SL |
384 | if closure.contains(candidate_i, candidate_j) { |
385 | // If `i` can reach `j`, then we can remove `j`. So just | |
386 | // mark it as dead and move on; subsequent indices will be | |
387 | // shifted into its place. | |
388 | dead += 1; | |
389 | } else { | |
390 | candidates[j - dead] = candidate_j; | |
391 | } | |
392 | j += 1; | |
393 | } | |
394 | candidates.truncate(j - dead); | |
395 | } | |
396 | } |