]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
1 | // Copyright 2015 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
0bf4aa26 | 11 | use bit_set::BitMatrix; |
7cac9316 | 12 | use fx::FxHashMap; |
0531ce1d | 13 | use sync::Lock; |
8bb4bdeb | 14 | use rustc_serialize::{Encodable, Encoder, Decodable, Decoder}; |
7cac9316 | 15 | use stable_hasher::{HashStable, StableHasher, StableHasherResult}; |
e9174d1e | 16 | use std::fmt::Debug; |
7cac9316 | 17 | use std::hash::Hash; |
e9174d1e SL |
18 | use std::mem; |
19 | ||
cc61c64b | 20 | |
ea8adc8c | 21 | #[derive(Clone, Debug)] |
0531ce1d | 22 | pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash> { |
7cac9316 | 23 | // List of elements. This is used to map from a T to a usize. |
e9174d1e SL |
24 | elements: Vec<T>, |
25 | ||
7cac9316 XL |
26 | // Maps each element to an index. |
27 | map: FxHashMap<T, Index>, | |
28 | ||
e9174d1e SL |
29 | // List of base edges in the graph. Require to compute transitive |
30 | // closure. | |
31 | edges: Vec<Edge>, | |
32 | ||
33 | // This is a cached transitive closure derived from the edges. | |
34 | // Currently, we build it lazilly and just throw out any existing | |
0531ce1d | 35 | // copy whenever a new edge is added. (The Lock is to permit |
e9174d1e SL |
36 | // the lazy computation.) This is kind of silly, except for the |
37 | // fact its size is tied to `self.elements.len()`, so I wanted to | |
38 | // wait before building it up to avoid reallocating as new edges | |
39 | // are added with new elements. Perhaps better would be to ask the | |
40 | // user for a batch of edges to minimize this effect, but I | |
41 | // already wrote the code this way. :P -nmatsakis | |
8faf50e0 | 42 | closure: Lock<Option<BitMatrix<usize, usize>>>, |
e9174d1e SL |
43 | } |
44 | ||
ea8adc8c | 45 | #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable, Debug)] |
e9174d1e SL |
46 | struct Index(usize); |
47 | ||
ea8adc8c | 48 | #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)] |
e9174d1e SL |
49 | struct Edge { |
50 | source: Index, | |
51 | target: Index, | |
52 | } | |
53 | ||
0bf4aa26 XL |
54 | impl<T: Clone + Debug + Eq + Hash> Default for TransitiveRelation<T> { |
55 | fn default() -> TransitiveRelation<T> { | |
54a0048b SL |
56 | TransitiveRelation { |
57 | elements: vec![], | |
0bf4aa26 | 58 | map: FxHashMap::default(), |
54a0048b | 59 | edges: vec![], |
0531ce1d | 60 | closure: Lock::new(None), |
54a0048b | 61 | } |
e9174d1e | 62 | } |
0bf4aa26 | 63 | } |
e9174d1e | 64 | |
0bf4aa26 | 65 | impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> { |
8bb4bdeb XL |
66 | pub fn is_empty(&self) -> bool { |
67 | self.edges.is_empty() | |
68 | } | |
69 | ||
e9174d1e | 70 | fn index(&self, a: &T) -> Option<Index> { |
7cac9316 | 71 | self.map.get(a).cloned() |
e9174d1e SL |
72 | } |
73 | ||
74 | fn add_index(&mut self, a: T) -> Index { | |
7cac9316 XL |
75 | let &mut TransitiveRelation { |
76 | ref mut elements, | |
0531ce1d | 77 | ref mut closure, |
7cac9316 XL |
78 | ref mut map, |
79 | .. | |
80 | } = self; | |
81 | ||
b7449926 | 82 | *map.entry(a.clone()) |
7cac9316 XL |
83 | .or_insert_with(|| { |
84 | elements.push(a); | |
85 | ||
86 | // if we changed the dimensions, clear the cache | |
0531ce1d | 87 | *closure.get_mut() = None; |
7cac9316 XL |
88 | |
89 | Index(elements.len() - 1) | |
90 | }) | |
7cac9316 | 91 | } |
e9174d1e | 92 | |
7cac9316 XL |
93 | /// Applies the (partial) function to each edge and returns a new |
94 | /// relation. If `f` returns `None` for any end-point, returns | |
95 | /// `None`. | |
96 | pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>> | |
97 | where F: FnMut(&T) -> Option<U>, | |
98 | U: Clone + Debug + Eq + Hash + Clone, | |
99 | { | |
0bf4aa26 | 100 | let mut result = TransitiveRelation::default(); |
7cac9316 | 101 | for edge in &self.edges { |
b7449926 | 102 | result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?); |
e9174d1e | 103 | } |
7cac9316 | 104 | Some(result) |
e9174d1e SL |
105 | } |
106 | ||
107 | /// Indicate that `a < b` (where `<` is this relation) | |
108 | pub fn add(&mut self, a: T, b: T) { | |
109 | let a = self.add_index(a); | |
110 | let b = self.add_index(b); | |
54a0048b SL |
111 | let edge = Edge { |
112 | source: a, | |
113 | target: b, | |
114 | }; | |
e9174d1e SL |
115 | if !self.edges.contains(&edge) { |
116 | self.edges.push(edge); | |
117 | ||
118 | // added an edge, clear the cache | |
0531ce1d | 119 | *self.closure.get_mut() = None; |
e9174d1e SL |
120 | } |
121 | } | |
122 | ||
123 | /// Check whether `a < target` (transitively) | |
124 | pub fn contains(&self, a: &T, b: &T) -> bool { | |
125 | match (self.index(a), self.index(b)) { | |
54a0048b SL |
126 | (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)), |
127 | (None, _) | (_, None) => false, | |
e9174d1e SL |
128 | } |
129 | } | |
130 | ||
ff7c6d11 XL |
131 | /// Thinking of `x R y` as an edge `x -> y` in a graph, this |
132 | /// returns all things reachable from `a`. | |
7cac9316 XL |
133 | /// |
134 | /// Really this probably ought to be `impl Iterator<Item=&T>`, but | |
135 | /// I'm too lazy to make that work, and -- given the caching | |
136 | /// strategy -- it'd be a touch tricky anyhow. | |
ff7c6d11 | 137 | pub fn reachable_from(&self, a: &T) -> Vec<&T> { |
7cac9316 XL |
138 | match self.index(a) { |
139 | Some(a) => self.with_closure(|closure| { | |
140 | closure.iter(a.0).map(|i| &self.elements[i]).collect() | |
141 | }), | |
142 | None => vec![], | |
143 | } | |
144 | } | |
145 | ||
e9174d1e SL |
146 | /// Picks what I am referring to as the "postdominating" |
147 | /// upper-bound for `a` and `b`. This is usually the least upper | |
148 | /// bound, but in cases where there is no single least upper | |
149 | /// bound, it is the "mutual immediate postdominator", if you | |
150 | /// imagine a graph where `a < b` means `a -> b`. | |
151 | /// | |
152 | /// This function is needed because region inference currently | |
153 | /// requires that we produce a single "UB", and there is no best | |
154 | /// choice for the LUB. Rather than pick arbitrarily, I pick a | |
155 | /// less good, but predictable choice. This should help ensure | |
156 | /// that region inference yields predictable results (though it | |
157 | /// itself is not fully sufficient). | |
158 | /// | |
159 | /// Examples are probably clearer than any prose I could write | |
160 | /// (there are corresponding tests below, btw). In each case, | |
161 | /// the query is `postdom_upper_bound(a, b)`: | |
162 | /// | |
163 | /// ```text | |
164 | /// // returns Some(x), which is also LUB | |
165 | /// a -> a1 -> x | |
166 | /// ^ | |
167 | /// | | |
168 | /// b -> b1 ---+ | |
169 | /// | |
170 | /// // returns Some(x), which is not LUB (there is none) | |
171 | /// // diagonal edges run left-to-right | |
172 | /// a -> a1 -> x | |
173 | /// \/ ^ | |
174 | /// /\ | | |
175 | /// b -> b1 ---+ | |
176 | /// | |
177 | /// // returns None | |
178 | /// a -> a1 | |
179 | /// b -> b1 | |
180 | /// ``` | |
181 | pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> { | |
ff7c6d11 XL |
182 | let mubs = self.minimal_upper_bounds(a, b); |
183 | self.mutual_immediate_postdominator(mubs) | |
184 | } | |
185 | ||
186 | /// Viewing the relation as a graph, computes the "mutual | |
187 | /// immediate postdominator" of a set of points (if one | |
188 | /// exists). See `postdom_upper_bound` for details. | |
189 | pub fn mutual_immediate_postdominator<'a>(&'a self, mut mubs: Vec<&'a T>) -> Option<&'a T> { | |
e9174d1e SL |
190 | loop { |
191 | match mubs.len() { | |
192 | 0 => return None, | |
193 | 1 => return Some(mubs[0]), | |
194 | _ => { | |
195 | let m = mubs.pop().unwrap(); | |
196 | let n = mubs.pop().unwrap(); | |
197 | mubs.extend(self.minimal_upper_bounds(n, m)); | |
198 | } | |
199 | } | |
200 | } | |
201 | } | |
202 | ||
203 | /// Returns the set of bounds `X` such that: | |
204 | /// | |
205 | /// - `a < X` and `b < X` | |
206 | /// - there is no `Y != X` such that `a < Y` and `Y < X` | |
207 | /// - except for the case where `X < a` (i.e., a strongly connected | |
208 | /// component in the graph). In that case, the smallest | |
209 | /// representative of the SCC is returned (as determined by the | |
210 | /// internal indices). | |
211 | /// | |
212 | /// Note that this set can, in principle, have any size. | |
213 | pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> { | |
214 | let (mut a, mut b) = match (self.index(a), self.index(b)) { | |
215 | (Some(a), Some(b)) => (a, b), | |
54a0048b SL |
216 | (None, _) | (_, None) => { |
217 | return vec![]; | |
218 | } | |
e9174d1e SL |
219 | }; |
220 | ||
221 | // in some cases, there are some arbitrary choices to be made; | |
222 | // it doesn't really matter what we pick, as long as we pick | |
223 | // the same thing consistently when queried, so ensure that | |
224 | // (a, b) are in a consistent relative order | |
225 | if a > b { | |
226 | mem::swap(&mut a, &mut b); | |
227 | } | |
228 | ||
229 | let lub_indices = self.with_closure(|closure| { | |
230 | // Easy case is when either a < b or b < a: | |
231 | if closure.contains(a.0, b.0) { | |
232 | return vec![b.0]; | |
233 | } | |
234 | if closure.contains(b.0, a.0) { | |
235 | return vec![a.0]; | |
236 | } | |
237 | ||
238 | // Otherwise, the tricky part is that there may be some c | |
239 | // where a < c and b < c. In fact, there may be many such | |
240 | // values. So here is what we do: | |
241 | // | |
242 | // 1. Find the vector `[X | a < X && b < X]` of all values | |
243 | // `X` where `a < X` and `b < X`. In terms of the | |
244 | // graph, this means all values reachable from both `a` | |
245 | // and `b`. Note that this vector is also a set, but we | |
246 | // use the term vector because the order matters | |
247 | // to the steps below. | |
248 | // - This vector contains upper bounds, but they are | |
249 | // not minimal upper bounds. So you may have e.g. | |
250 | // `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and | |
251 | // `z < x` and `z < y`: | |
252 | // | |
253 | // z --+---> x ----+----> tcx | |
254 | // | | | |
255 | // | | | |
256 | // +---> y ----+ | |
257 | // | |
258 | // In this case, we really want to return just `[z]`. | |
259 | // The following steps below achieve this by gradually | |
260 | // reducing the list. | |
261 | // 2. Pare down the vector using `pare_down`. This will | |
262 | // remove elements from the vector that can be reached | |
263 | // by an earlier element. | |
264 | // - In the example above, this would convert `[x, y, | |
265 | // tcx, z]` to `[x, y, z]`. Note that `x` and `y` are | |
266 | // still in the vector; this is because while `z < x` | |
267 | // (and `z < y`) holds, `z` comes after them in the | |
268 | // vector. | |
269 | // 3. Reverse the vector and repeat the pare down process. | |
270 | // - In the example above, we would reverse to | |
271 | // `[z, y, x]` and then pare down to `[z]`. | |
272 | // 4. Reverse once more just so that we yield a vector in | |
273 | // increasing order of index. Not necessary, but why not. | |
274 | // | |
275 | // I believe this algorithm yields a minimal set. The | |
276 | // argument is that, after step 2, we know that no element | |
277 | // can reach its successors (in the vector, not the graph). | |
278 | // After step 3, we know that no element can reach any of | |
279 | // its predecesssors (because of step 2) nor successors | |
280 | // (because we just called `pare_down`) | |
ff7c6d11 XL |
281 | // |
282 | // This same algorithm is used in `parents` below. | |
e9174d1e | 283 | |
0bf4aa26 | 284 | let mut candidates = closure.intersect_rows(a.0, b.0); // (1) |
e9174d1e SL |
285 | pare_down(&mut candidates, closure); // (2) |
286 | candidates.reverse(); // (3a) | |
287 | pare_down(&mut candidates, closure); // (3b) | |
288 | candidates | |
289 | }); | |
290 | ||
291 | lub_indices.into_iter() | |
292 | .rev() // (4) | |
293 | .map(|i| &self.elements[i]) | |
294 | .collect() | |
295 | } | |
296 | ||
ff7c6d11 XL |
297 | /// Given an element A, returns the maximal set {B} of elements B |
298 | /// such that | |
299 | /// | |
300 | /// - A != B | |
301 | /// - A R B is true | |
302 | /// - for each i, j: B[i] R B[j] does not hold | |
303 | /// | |
304 | /// The intuition is that this moves "one step up" through a lattice | |
305 | /// (where the relation is encoding the `<=` relation for the lattice). | |
306 | /// So e.g. if the relation is `->` and we have | |
307 | /// | |
308 | /// ``` | |
309 | /// a -> b -> d -> f | |
310 | /// | ^ | |
311 | /// +--> c -> e ---+ | |
312 | /// ``` | |
313 | /// | |
314 | /// then `parents(a)` returns `[b, c]`. The `postdom_parent` function | |
315 | /// would further reduce this to just `f`. | |
316 | pub fn parents(&self, a: &T) -> Vec<&T> { | |
317 | let a = match self.index(a) { | |
318 | Some(a) => a, | |
319 | None => return vec![] | |
320 | }; | |
321 | ||
322 | // Steal the algorithm for `minimal_upper_bounds` above, but | |
323 | // with a slight tweak. In the case where `a R a`, we remove | |
324 | // that from the set of candidates. | |
325 | let ancestors = self.with_closure(|closure| { | |
0bf4aa26 | 326 | let mut ancestors = closure.intersect_rows(a.0, a.0); |
ff7c6d11 XL |
327 | |
328 | // Remove anything that can reach `a`. If this is a | |
329 | // reflexive relation, this will include `a` itself. | |
330 | ancestors.retain(|&e| !closure.contains(e, a.0)); | |
331 | ||
332 | pare_down(&mut ancestors, closure); // (2) | |
333 | ancestors.reverse(); // (3a) | |
334 | pare_down(&mut ancestors, closure); // (3b) | |
335 | ancestors | |
336 | }); | |
337 | ||
338 | ancestors.into_iter() | |
339 | .rev() // (4) | |
340 | .map(|i| &self.elements[i]) | |
341 | .collect() | |
342 | } | |
343 | ||
344 | /// A "best" parent in some sense. See `parents` and | |
345 | /// `postdom_upper_bound` for more details. | |
346 | pub fn postdom_parent(&self, a: &T) -> Option<&T> { | |
347 | self.mutual_immediate_postdominator(self.parents(a)) | |
348 | } | |
349 | ||
54a0048b | 350 | fn with_closure<OP, R>(&self, op: OP) -> R |
8faf50e0 | 351 | where OP: FnOnce(&BitMatrix<usize, usize>) -> R |
e9174d1e SL |
352 | { |
353 | let mut closure_cell = self.closure.borrow_mut(); | |
354 | let mut closure = closure_cell.take(); | |
355 | if closure.is_none() { | |
356 | closure = Some(self.compute_closure()); | |
357 | } | |
358 | let result = op(closure.as_ref().unwrap()); | |
359 | *closure_cell = closure; | |
360 | result | |
361 | } | |
362 | ||
8faf50e0 | 363 | fn compute_closure(&self) -> BitMatrix<usize, usize> { |
5bcae85e SL |
364 | let mut matrix = BitMatrix::new(self.elements.len(), |
365 | self.elements.len()); | |
e9174d1e SL |
366 | let mut changed = true; |
367 | while changed { | |
368 | changed = false; | |
b7449926 | 369 | for edge in &self.edges { |
e9174d1e | 370 | // add an edge from S -> T |
0bf4aa26 | 371 | changed |= matrix.insert(edge.source.0, edge.target.0); |
e9174d1e SL |
372 | |
373 | // add all outgoing edges from T into S | |
0bf4aa26 | 374 | changed |= matrix.union_rows(edge.target.0, edge.source.0); |
e9174d1e SL |
375 | } |
376 | } | |
377 | matrix | |
378 | } | |
379 | } | |
380 | ||
381 | /// Pare down is used as a step in the LUB computation. It edits the | |
382 | /// candidates array in place by removing any element j for which | |
383 | /// there exists an earlier element i<j such that i -> j. That is, | |
384 | /// after you run `pare_down`, you know that for all elements that | |
385 | /// remain in candidates, they cannot reach any of the elements that | |
386 | /// come after them. | |
387 | /// | |
388 | /// Examples follow. Assume that a -> b -> c and x -> y -> z. | |
389 | /// | |
390 | /// - Input: `[a, b, x]`. Output: `[a, x]`. | |
391 | /// - Input: `[b, a, x]`. Output: `[b, a, x]`. | |
392 | /// - Input: `[a, x, b, y]`. Output: `[a, x]`. | |
8faf50e0 | 393 | fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) { |
e9174d1e SL |
394 | let mut i = 0; |
395 | while i < candidates.len() { | |
396 | let candidate_i = candidates[i]; | |
397 | i += 1; | |
398 | ||
399 | let mut j = i; | |
400 | let mut dead = 0; | |
401 | while j < candidates.len() { | |
402 | let candidate_j = candidates[j]; | |
403 | if closure.contains(candidate_i, candidate_j) { | |
404 | // If `i` can reach `j`, then we can remove `j`. So just | |
405 | // mark it as dead and move on; subsequent indices will be | |
406 | // shifted into its place. | |
407 | dead += 1; | |
408 | } else { | |
409 | candidates[j - dead] = candidate_j; | |
410 | } | |
411 | j += 1; | |
412 | } | |
413 | candidates.truncate(j - dead); | |
414 | } | |
415 | } | |
416 | ||
8bb4bdeb | 417 | impl<T> Encodable for TransitiveRelation<T> |
7cac9316 | 418 | where T: Clone + Encodable + Debug + Eq + Hash + Clone |
8bb4bdeb XL |
419 | { |
420 | fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> { | |
421 | s.emit_struct("TransitiveRelation", 2, |s| { | |
422 | s.emit_struct_field("elements", 0, |s| self.elements.encode(s))?; | |
423 | s.emit_struct_field("edges", 1, |s| self.edges.encode(s))?; | |
424 | Ok(()) | |
425 | }) | |
426 | } | |
427 | } | |
428 | ||
429 | impl<T> Decodable for TransitiveRelation<T> | |
7cac9316 | 430 | where T: Clone + Decodable + Debug + Eq + Hash + Clone |
8bb4bdeb XL |
431 | { |
432 | fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> { | |
433 | d.read_struct("TransitiveRelation", 2, |d| { | |
7cac9316 | 434 | let elements: Vec<T> = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?; |
8bb4bdeb | 435 | let edges = d.read_struct_field("edges", 1, |d| Decodable::decode(d))?; |
7cac9316 XL |
436 | let map = elements.iter() |
437 | .enumerate() | |
438 | .map(|(index, elem)| (elem.clone(), Index(index))) | |
439 | .collect(); | |
0531ce1d | 440 | Ok(TransitiveRelation { elements, edges, map, closure: Lock::new(None) }) |
8bb4bdeb XL |
441 | }) |
442 | } | |
443 | } | |
444 | ||
cc61c64b | 445 | impl<CTX, T> HashStable<CTX> for TransitiveRelation<T> |
7cac9316 | 446 | where T: HashStable<CTX> + Eq + Debug + Clone + Hash |
cc61c64b XL |
447 | { |
448 | fn hash_stable<W: StableHasherResult>(&self, | |
449 | hcx: &mut CTX, | |
450 | hasher: &mut StableHasher<W>) { | |
451 | // We are assuming here that the relation graph has been built in a | |
452 | // deterministic way and we can just hash it the way it is. | |
453 | let TransitiveRelation { | |
454 | ref elements, | |
455 | ref edges, | |
7cac9316 XL |
456 | // "map" is just a copy of elements vec |
457 | map: _, | |
cc61c64b XL |
458 | // "closure" is just a copy of the data above |
459 | closure: _ | |
460 | } = *self; | |
461 | ||
462 | elements.hash_stable(hcx, hasher); | |
463 | edges.hash_stable(hcx, hasher); | |
464 | } | |
465 | } | |
466 | ||
467 | impl<CTX> HashStable<CTX> for Edge { | |
468 | fn hash_stable<W: StableHasherResult>(&self, | |
469 | hcx: &mut CTX, | |
470 | hasher: &mut StableHasher<W>) { | |
471 | let Edge { | |
472 | ref source, | |
473 | ref target, | |
474 | } = *self; | |
475 | ||
476 | source.hash_stable(hcx, hasher); | |
477 | target.hash_stable(hcx, hasher); | |
478 | } | |
479 | } | |
480 | ||
481 | impl<CTX> HashStable<CTX> for Index { | |
482 | fn hash_stable<W: StableHasherResult>(&self, | |
483 | hcx: &mut CTX, | |
484 | hasher: &mut StableHasher<W>) { | |
485 | let Index(idx) = *self; | |
486 | idx.hash_stable(hcx, hasher); | |
487 | } | |
488 | } | |
489 | ||
e9174d1e SL |
490 | #[test] |
491 | fn test_one_step() { | |
0bf4aa26 | 492 | let mut relation = TransitiveRelation::default(); |
e9174d1e SL |
493 | relation.add("a", "b"); |
494 | relation.add("a", "c"); | |
495 | assert!(relation.contains(&"a", &"c")); | |
496 | assert!(relation.contains(&"a", &"b")); | |
497 | assert!(!relation.contains(&"b", &"a")); | |
498 | assert!(!relation.contains(&"a", &"d")); | |
499 | } | |
500 | ||
501 | #[test] | |
502 | fn test_many_steps() { | |
0bf4aa26 | 503 | let mut relation = TransitiveRelation::default(); |
e9174d1e SL |
504 | relation.add("a", "b"); |
505 | relation.add("a", "c"); | |
506 | relation.add("a", "f"); | |
507 | ||
508 | relation.add("b", "c"); | |
509 | relation.add("b", "d"); | |
510 | relation.add("b", "e"); | |
511 | ||
512 | relation.add("e", "g"); | |
513 | ||
514 | assert!(relation.contains(&"a", &"b")); | |
515 | assert!(relation.contains(&"a", &"c")); | |
516 | assert!(relation.contains(&"a", &"d")); | |
517 | assert!(relation.contains(&"a", &"e")); | |
518 | assert!(relation.contains(&"a", &"f")); | |
519 | assert!(relation.contains(&"a", &"g")); | |
520 | ||
521 | assert!(relation.contains(&"b", &"g")); | |
522 | ||
523 | assert!(!relation.contains(&"a", &"x")); | |
524 | assert!(!relation.contains(&"b", &"f")); | |
525 | } | |
526 | ||
527 | #[test] | |
ff7c6d11 XL |
528 | fn mubs_triangle() { |
529 | // a -> tcx | |
530 | // ^ | |
531 | // | | |
532 | // b | |
0bf4aa26 | 533 | let mut relation = TransitiveRelation::default(); |
e9174d1e SL |
534 | relation.add("a", "tcx"); |
535 | relation.add("b", "tcx"); | |
536 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]); | |
ff7c6d11 XL |
537 | assert_eq!(relation.parents(&"a"), vec![&"tcx"]); |
538 | assert_eq!(relation.parents(&"b"), vec![&"tcx"]); | |
e9174d1e SL |
539 | } |
540 | ||
541 | #[test] | |
542 | fn mubs_best_choice1() { | |
543 | // 0 -> 1 <- 3 | |
544 | // | ^ | | |
545 | // | | | | |
546 | // +--> 2 <--+ | |
547 | // | |
548 | // mubs(0,3) = [1] | |
549 | ||
550 | // This tests a particular state in the algorithm, in which we | |
551 | // need the second pare down call to get the right result (after | |
552 | // intersection, we have [1, 2], but 2 -> 1). | |
553 | ||
0bf4aa26 | 554 | let mut relation = TransitiveRelation::default(); |
e9174d1e SL |
555 | relation.add("0", "1"); |
556 | relation.add("0", "2"); | |
557 | ||
558 | relation.add("2", "1"); | |
559 | ||
560 | relation.add("3", "1"); | |
561 | relation.add("3", "2"); | |
562 | ||
563 | assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]); | |
ff7c6d11 XL |
564 | assert_eq!(relation.parents(&"0"), vec![&"2"]); |
565 | assert_eq!(relation.parents(&"2"), vec![&"1"]); | |
566 | assert!(relation.parents(&"1").is_empty()); | |
e9174d1e SL |
567 | } |
568 | ||
569 | #[test] | |
570 | fn mubs_best_choice2() { | |
571 | // 0 -> 1 <- 3 | |
572 | // | | | | |
573 | // | v | | |
574 | // +--> 2 <--+ | |
575 | // | |
576 | // mubs(0,3) = [2] | |
577 | ||
578 | // Like the precedecing test, but in this case intersection is [2, | |
579 | // 1], and hence we rely on the first pare down call. | |
580 | ||
0bf4aa26 | 581 | let mut relation = TransitiveRelation::default(); |
e9174d1e SL |
582 | relation.add("0", "1"); |
583 | relation.add("0", "2"); | |
584 | ||
585 | relation.add("1", "2"); | |
586 | ||
587 | relation.add("3", "1"); | |
588 | relation.add("3", "2"); | |
589 | ||
590 | assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]); | |
ff7c6d11 XL |
591 | assert_eq!(relation.parents(&"0"), vec![&"1"]); |
592 | assert_eq!(relation.parents(&"1"), vec![&"2"]); | |
593 | assert!(relation.parents(&"2").is_empty()); | |
e9174d1e SL |
594 | } |
595 | ||
596 | #[test] | |
597 | fn mubs_no_best_choice() { | |
598 | // in this case, the intersection yields [1, 2], and the "pare | |
599 | // down" calls find nothing to remove. | |
0bf4aa26 | 600 | let mut relation = TransitiveRelation::default(); |
e9174d1e SL |
601 | relation.add("0", "1"); |
602 | relation.add("0", "2"); | |
603 | ||
604 | relation.add("3", "1"); | |
605 | relation.add("3", "2"); | |
606 | ||
607 | assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]); | |
ff7c6d11 XL |
608 | assert_eq!(relation.parents(&"0"), vec![&"1", &"2"]); |
609 | assert_eq!(relation.parents(&"3"), vec![&"1", &"2"]); | |
e9174d1e SL |
610 | } |
611 | ||
612 | #[test] | |
613 | fn mubs_best_choice_scc() { | |
ff7c6d11 XL |
614 | // in this case, 1 and 2 form a cycle; we pick arbitrarily (but |
615 | // consistently). | |
616 | ||
0bf4aa26 | 617 | let mut relation = TransitiveRelation::default(); |
e9174d1e SL |
618 | relation.add("0", "1"); |
619 | relation.add("0", "2"); | |
620 | ||
621 | relation.add("1", "2"); | |
622 | relation.add("2", "1"); | |
623 | ||
624 | relation.add("3", "1"); | |
625 | relation.add("3", "2"); | |
626 | ||
627 | assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]); | |
ff7c6d11 | 628 | assert_eq!(relation.parents(&"0"), vec![&"1"]); |
e9174d1e SL |
629 | } |
630 | ||
631 | #[test] | |
632 | fn pdub_crisscross() { | |
633 | // diagonal edges run left-to-right | |
634 | // a -> a1 -> x | |
635 | // \/ ^ | |
636 | // /\ | | |
637 | // b -> b1 ---+ | |
638 | ||
0bf4aa26 | 639 | let mut relation = TransitiveRelation::default(); |
54a0048b SL |
640 | relation.add("a", "a1"); |
641 | relation.add("a", "b1"); | |
642 | relation.add("b", "a1"); | |
643 | relation.add("b", "b1"); | |
e9174d1e SL |
644 | relation.add("a1", "x"); |
645 | relation.add("b1", "x"); | |
646 | ||
54a0048b SL |
647 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), |
648 | vec![&"a1", &"b1"]); | |
e9174d1e | 649 | assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x")); |
ff7c6d11 XL |
650 | assert_eq!(relation.postdom_parent(&"a"), Some(&"x")); |
651 | assert_eq!(relation.postdom_parent(&"b"), Some(&"x")); | |
e9174d1e SL |
652 | } |
653 | ||
654 | #[test] | |
655 | fn pdub_crisscross_more() { | |
656 | // diagonal edges run left-to-right | |
657 | // a -> a1 -> a2 -> a3 -> x | |
658 | // \/ \/ ^ | |
659 | // /\ /\ | | |
660 | // b -> b1 -> b2 ---------+ | |
661 | ||
0bf4aa26 | 662 | let mut relation = TransitiveRelation::default(); |
54a0048b SL |
663 | relation.add("a", "a1"); |
664 | relation.add("a", "b1"); | |
665 | relation.add("b", "a1"); | |
666 | relation.add("b", "b1"); | |
e9174d1e | 667 | |
54a0048b SL |
668 | relation.add("a1", "a2"); |
669 | relation.add("a1", "b2"); | |
670 | relation.add("b1", "a2"); | |
671 | relation.add("b1", "b2"); | |
e9174d1e SL |
672 | |
673 | relation.add("a2", "a3"); | |
674 | ||
675 | relation.add("a3", "x"); | |
676 | relation.add("b2", "x"); | |
677 | ||
54a0048b SL |
678 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), |
679 | vec![&"a1", &"b1"]); | |
680 | assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"), | |
681 | vec![&"a2", &"b2"]); | |
e9174d1e | 682 | assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x")); |
ff7c6d11 XL |
683 | |
684 | assert_eq!(relation.postdom_parent(&"a"), Some(&"x")); | |
685 | assert_eq!(relation.postdom_parent(&"b"), Some(&"x")); | |
e9174d1e SL |
686 | } |
687 | ||
688 | #[test] | |
689 | fn pdub_lub() { | |
690 | // a -> a1 -> x | |
691 | // ^ | |
692 | // | | |
693 | // b -> b1 ---+ | |
694 | ||
0bf4aa26 | 695 | let mut relation = TransitiveRelation::default(); |
54a0048b SL |
696 | relation.add("a", "a1"); |
697 | relation.add("b", "b1"); | |
e9174d1e SL |
698 | relation.add("a1", "x"); |
699 | relation.add("b1", "x"); | |
700 | ||
701 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]); | |
702 | assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x")); | |
ff7c6d11 XL |
703 | |
704 | assert_eq!(relation.postdom_parent(&"a"), Some(&"a1")); | |
705 | assert_eq!(relation.postdom_parent(&"b"), Some(&"b1")); | |
706 | assert_eq!(relation.postdom_parent(&"a1"), Some(&"x")); | |
707 | assert_eq!(relation.postdom_parent(&"b1"), Some(&"x")); | |
e9174d1e SL |
708 | } |
709 | ||
710 | #[test] | |
711 | fn mubs_intermediate_node_on_one_side_only() { | |
712 | // a -> c -> d | |
713 | // ^ | |
714 | // | | |
715 | // b | |
716 | ||
717 | // "digraph { a -> c -> d; b -> d; }", | |
0bf4aa26 | 718 | let mut relation = TransitiveRelation::default(); |
54a0048b SL |
719 | relation.add("a", "c"); |
720 | relation.add("c", "d"); | |
721 | relation.add("b", "d"); | |
e9174d1e SL |
722 | |
723 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]); | |
724 | } | |
725 | ||
726 | #[test] | |
727 | fn mubs_scc_1() { | |
728 | // +-------------+ | |
729 | // | +----+ | | |
730 | // | v | | | |
731 | // a -> c -> d <-+ | |
732 | // ^ | |
733 | // | | |
734 | // b | |
735 | ||
736 | // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }", | |
0bf4aa26 | 737 | let mut relation = TransitiveRelation::default(); |
54a0048b SL |
738 | relation.add("a", "c"); |
739 | relation.add("c", "d"); | |
740 | relation.add("d", "c"); | |
741 | relation.add("a", "d"); | |
742 | relation.add("b", "d"); | |
e9174d1e SL |
743 | |
744 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); | |
745 | } | |
746 | ||
747 | #[test] | |
748 | fn mubs_scc_2() { | |
749 | // +----+ | |
750 | // v | | |
751 | // a -> c -> d | |
752 | // ^ ^ | |
753 | // | | | |
754 | // +--- b | |
755 | ||
756 | // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }", | |
0bf4aa26 | 757 | let mut relation = TransitiveRelation::default(); |
54a0048b SL |
758 | relation.add("a", "c"); |
759 | relation.add("c", "d"); | |
760 | relation.add("d", "c"); | |
761 | relation.add("b", "d"); | |
762 | relation.add("b", "c"); | |
e9174d1e SL |
763 | |
764 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); | |
765 | } | |
766 | ||
767 | #[test] | |
768 | fn mubs_scc_3() { | |
769 | // +---------+ | |
770 | // v | | |
771 | // a -> c -> d -> e | |
772 | // ^ ^ | |
773 | // | | | |
774 | // b ---+ | |
775 | ||
776 | // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }", | |
0bf4aa26 | 777 | let mut relation = TransitiveRelation::default(); |
54a0048b SL |
778 | relation.add("a", "c"); |
779 | relation.add("c", "d"); | |
780 | relation.add("d", "e"); | |
781 | relation.add("e", "c"); | |
782 | relation.add("b", "d"); | |
783 | relation.add("b", "e"); | |
e9174d1e SL |
784 | |
785 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); | |
786 | } | |
787 | ||
788 | #[test] | |
789 | fn mubs_scc_4() { | |
790 | // +---------+ | |
791 | // v | | |
792 | // a -> c -> d -> e | |
793 | // | ^ ^ | |
794 | // +---------+ | | |
795 | // | | |
796 | // b ---+ | |
797 | ||
798 | // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }" | |
0bf4aa26 | 799 | let mut relation = TransitiveRelation::default(); |
54a0048b SL |
800 | relation.add("a", "c"); |
801 | relation.add("c", "d"); | |
802 | relation.add("d", "e"); | |
803 | relation.add("e", "c"); | |
804 | relation.add("a", "d"); | |
805 | relation.add("b", "e"); | |
e9174d1e SL |
806 | |
807 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); | |
808 | } | |
ff7c6d11 XL |
809 | |
810 | #[test] | |
811 | fn parent() { | |
812 | // An example that was misbehaving in the compiler. | |
813 | // | |
814 | // 4 -> 1 -> 3 | |
815 | // \ | / | |
816 | // \ v / | |
817 | // 2 -> 0 | |
818 | // | |
819 | // plus a bunch of self-loops | |
820 | // | |
821 | // Here `->` represents `<=` and `0` is `'static`. | |
822 | ||
823 | let pairs = vec![ | |
824 | (2, /*->*/ 0), | |
825 | (2, /*->*/ 2), | |
826 | (0, /*->*/ 0), | |
827 | (0, /*->*/ 0), | |
828 | (1, /*->*/ 0), | |
829 | (1, /*->*/ 1), | |
830 | (3, /*->*/ 0), | |
831 | (3, /*->*/ 3), | |
832 | (4, /*->*/ 0), | |
833 | (4, /*->*/ 1), | |
834 | (1, /*->*/ 3), | |
835 | ]; | |
836 | ||
0bf4aa26 | 837 | let mut relation = TransitiveRelation::default(); |
ff7c6d11 XL |
838 | for (a, b) in pairs { |
839 | relation.add(a, b); | |
840 | } | |
841 | ||
842 | let p = relation.postdom_parent(&3); | |
843 | assert_eq!(p, Some(&0)); | |
844 | } |