]>
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 | ||
11 | use bitvec::BitMatrix; | |
7cac9316 | 12 | use fx::FxHashMap; |
8bb4bdeb | 13 | use rustc_serialize::{Encodable, Encoder, Decodable, Decoder}; |
7cac9316 | 14 | use stable_hasher::{HashStable, StableHasher, StableHasherResult}; |
e9174d1e SL |
15 | use std::cell::RefCell; |
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)] |
7cac9316 XL |
22 | pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash + Clone> { |
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 | |
35 | // copy whenever a new edge is added. (The RefCell is to permit | |
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 | |
54a0048b | 42 | closure: RefCell<Option<BitMatrix>>, |
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 | ||
7cac9316 | 54 | impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> { |
e9174d1e | 55 | pub fn new() -> TransitiveRelation<T> { |
54a0048b SL |
56 | TransitiveRelation { |
57 | elements: vec![], | |
7cac9316 | 58 | map: FxHashMap(), |
54a0048b SL |
59 | edges: vec![], |
60 | closure: RefCell::new(None), | |
61 | } | |
e9174d1e SL |
62 | } |
63 | ||
8bb4bdeb XL |
64 | pub fn is_empty(&self) -> bool { |
65 | self.edges.is_empty() | |
66 | } | |
67 | ||
e9174d1e | 68 | fn index(&self, a: &T) -> Option<Index> { |
7cac9316 | 69 | self.map.get(a).cloned() |
e9174d1e SL |
70 | } |
71 | ||
72 | fn add_index(&mut self, a: T) -> Index { | |
7cac9316 XL |
73 | let &mut TransitiveRelation { |
74 | ref mut elements, | |
75 | ref closure, | |
76 | ref mut map, | |
77 | .. | |
78 | } = self; | |
79 | ||
80 | map.entry(a.clone()) | |
81 | .or_insert_with(|| { | |
82 | elements.push(a); | |
83 | ||
84 | // if we changed the dimensions, clear the cache | |
85 | *closure.borrow_mut() = None; | |
86 | ||
87 | Index(elements.len() - 1) | |
88 | }) | |
89 | .clone() | |
90 | } | |
e9174d1e | 91 | |
7cac9316 XL |
92 | /// Applies the (partial) function to each edge and returns a new |
93 | /// relation. If `f` returns `None` for any end-point, returns | |
94 | /// `None`. | |
95 | pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>> | |
96 | where F: FnMut(&T) -> Option<U>, | |
97 | U: Clone + Debug + Eq + Hash + Clone, | |
98 | { | |
99 | let mut result = TransitiveRelation::new(); | |
100 | for edge in &self.edges { | |
101 | let r = f(&self.elements[edge.source.0]).and_then(|source| { | |
102 | f(&self.elements[edge.target.0]).and_then(|target| { | |
103 | Some(result.add(source, target)) | |
104 | }) | |
105 | }); | |
106 | if r.is_none() { | |
107 | return None; | |
e9174d1e SL |
108 | } |
109 | } | |
7cac9316 | 110 | Some(result) |
e9174d1e SL |
111 | } |
112 | ||
113 | /// Indicate that `a < b` (where `<` is this relation) | |
114 | pub fn add(&mut self, a: T, b: T) { | |
115 | let a = self.add_index(a); | |
116 | let b = self.add_index(b); | |
54a0048b SL |
117 | let edge = Edge { |
118 | source: a, | |
119 | target: b, | |
120 | }; | |
e9174d1e SL |
121 | if !self.edges.contains(&edge) { |
122 | self.edges.push(edge); | |
123 | ||
124 | // added an edge, clear the cache | |
125 | *self.closure.borrow_mut() = None; | |
126 | } | |
127 | } | |
128 | ||
129 | /// Check whether `a < target` (transitively) | |
130 | pub fn contains(&self, a: &T, b: &T) -> bool { | |
131 | match (self.index(a), self.index(b)) { | |
54a0048b SL |
132 | (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)), |
133 | (None, _) | (_, None) => false, | |
e9174d1e SL |
134 | } |
135 | } | |
136 | ||
abe05a73 | 137 | /// Returns a vector of all things greater than `a`. |
7cac9316 XL |
138 | /// |
139 | /// Really this probably ought to be `impl Iterator<Item=&T>`, but | |
140 | /// I'm too lazy to make that work, and -- given the caching | |
141 | /// strategy -- it'd be a touch tricky anyhow. | |
abe05a73 | 142 | pub fn greater_than(&self, a: &T) -> Vec<&T> { |
7cac9316 XL |
143 | match self.index(a) { |
144 | Some(a) => self.with_closure(|closure| { | |
145 | closure.iter(a.0).map(|i| &self.elements[i]).collect() | |
146 | }), | |
147 | None => vec![], | |
148 | } | |
149 | } | |
150 | ||
e9174d1e SL |
151 | /// Picks what I am referring to as the "postdominating" |
152 | /// upper-bound for `a` and `b`. This is usually the least upper | |
153 | /// bound, but in cases where there is no single least upper | |
154 | /// bound, it is the "mutual immediate postdominator", if you | |
155 | /// imagine a graph where `a < b` means `a -> b`. | |
156 | /// | |
157 | /// This function is needed because region inference currently | |
158 | /// requires that we produce a single "UB", and there is no best | |
159 | /// choice for the LUB. Rather than pick arbitrarily, I pick a | |
160 | /// less good, but predictable choice. This should help ensure | |
161 | /// that region inference yields predictable results (though it | |
162 | /// itself is not fully sufficient). | |
163 | /// | |
164 | /// Examples are probably clearer than any prose I could write | |
165 | /// (there are corresponding tests below, btw). In each case, | |
166 | /// the query is `postdom_upper_bound(a, b)`: | |
167 | /// | |
168 | /// ```text | |
169 | /// // returns Some(x), which is also LUB | |
170 | /// a -> a1 -> x | |
171 | /// ^ | |
172 | /// | | |
173 | /// b -> b1 ---+ | |
174 | /// | |
175 | /// // returns Some(x), which is not LUB (there is none) | |
176 | /// // diagonal edges run left-to-right | |
177 | /// a -> a1 -> x | |
178 | /// \/ ^ | |
179 | /// /\ | | |
180 | /// b -> b1 ---+ | |
181 | /// | |
182 | /// // returns None | |
183 | /// a -> a1 | |
184 | /// b -> b1 | |
185 | /// ``` | |
186 | pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> { | |
187 | let mut mubs = self.minimal_upper_bounds(a, b); | |
188 | loop { | |
189 | match mubs.len() { | |
190 | 0 => return None, | |
191 | 1 => return Some(mubs[0]), | |
192 | _ => { | |
193 | let m = mubs.pop().unwrap(); | |
194 | let n = mubs.pop().unwrap(); | |
195 | mubs.extend(self.minimal_upper_bounds(n, m)); | |
196 | } | |
197 | } | |
198 | } | |
199 | } | |
200 | ||
201 | /// Returns the set of bounds `X` such that: | |
202 | /// | |
203 | /// - `a < X` and `b < X` | |
204 | /// - there is no `Y != X` such that `a < Y` and `Y < X` | |
205 | /// - except for the case where `X < a` (i.e., a strongly connected | |
206 | /// component in the graph). In that case, the smallest | |
207 | /// representative of the SCC is returned (as determined by the | |
208 | /// internal indices). | |
209 | /// | |
210 | /// Note that this set can, in principle, have any size. | |
211 | pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> { | |
212 | let (mut a, mut b) = match (self.index(a), self.index(b)) { | |
213 | (Some(a), Some(b)) => (a, b), | |
54a0048b SL |
214 | (None, _) | (_, None) => { |
215 | return vec![]; | |
216 | } | |
e9174d1e SL |
217 | }; |
218 | ||
219 | // in some cases, there are some arbitrary choices to be made; | |
220 | // it doesn't really matter what we pick, as long as we pick | |
221 | // the same thing consistently when queried, so ensure that | |
222 | // (a, b) are in a consistent relative order | |
223 | if a > b { | |
224 | mem::swap(&mut a, &mut b); | |
225 | } | |
226 | ||
227 | let lub_indices = self.with_closure(|closure| { | |
228 | // Easy case is when either a < b or b < a: | |
229 | if closure.contains(a.0, b.0) { | |
230 | return vec![b.0]; | |
231 | } | |
232 | if closure.contains(b.0, a.0) { | |
233 | return vec![a.0]; | |
234 | } | |
235 | ||
236 | // Otherwise, the tricky part is that there may be some c | |
237 | // where a < c and b < c. In fact, there may be many such | |
238 | // values. So here is what we do: | |
239 | // | |
240 | // 1. Find the vector `[X | a < X && b < X]` of all values | |
241 | // `X` where `a < X` and `b < X`. In terms of the | |
242 | // graph, this means all values reachable from both `a` | |
243 | // and `b`. Note that this vector is also a set, but we | |
244 | // use the term vector because the order matters | |
245 | // to the steps below. | |
246 | // - This vector contains upper bounds, but they are | |
247 | // not minimal upper bounds. So you may have e.g. | |
248 | // `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and | |
249 | // `z < x` and `z < y`: | |
250 | // | |
251 | // z --+---> x ----+----> tcx | |
252 | // | | | |
253 | // | | | |
254 | // +---> y ----+ | |
255 | // | |
256 | // In this case, we really want to return just `[z]`. | |
257 | // The following steps below achieve this by gradually | |
258 | // reducing the list. | |
259 | // 2. Pare down the vector using `pare_down`. This will | |
260 | // remove elements from the vector that can be reached | |
261 | // by an earlier element. | |
262 | // - In the example above, this would convert `[x, y, | |
263 | // tcx, z]` to `[x, y, z]`. Note that `x` and `y` are | |
264 | // still in the vector; this is because while `z < x` | |
265 | // (and `z < y`) holds, `z` comes after them in the | |
266 | // vector. | |
267 | // 3. Reverse the vector and repeat the pare down process. | |
268 | // - In the example above, we would reverse to | |
269 | // `[z, y, x]` and then pare down to `[z]`. | |
270 | // 4. Reverse once more just so that we yield a vector in | |
271 | // increasing order of index. Not necessary, but why not. | |
272 | // | |
273 | // I believe this algorithm yields a minimal set. The | |
274 | // argument is that, after step 2, we know that no element | |
275 | // can reach its successors (in the vector, not the graph). | |
276 | // After step 3, we know that no element can reach any of | |
277 | // its predecesssors (because of step 2) nor successors | |
278 | // (because we just called `pare_down`) | |
279 | ||
280 | let mut candidates = closure.intersection(a.0, b.0); // (1) | |
281 | pare_down(&mut candidates, closure); // (2) | |
282 | candidates.reverse(); // (3a) | |
283 | pare_down(&mut candidates, closure); // (3b) | |
284 | candidates | |
285 | }); | |
286 | ||
287 | lub_indices.into_iter() | |
288 | .rev() // (4) | |
289 | .map(|i| &self.elements[i]) | |
290 | .collect() | |
291 | } | |
292 | ||
54a0048b | 293 | fn with_closure<OP, R>(&self, op: OP) -> R |
e9174d1e SL |
294 | where OP: FnOnce(&BitMatrix) -> R |
295 | { | |
296 | let mut closure_cell = self.closure.borrow_mut(); | |
297 | let mut closure = closure_cell.take(); | |
298 | if closure.is_none() { | |
299 | closure = Some(self.compute_closure()); | |
300 | } | |
301 | let result = op(closure.as_ref().unwrap()); | |
302 | *closure_cell = closure; | |
303 | result | |
304 | } | |
305 | ||
306 | fn compute_closure(&self) -> BitMatrix { | |
5bcae85e SL |
307 | let mut matrix = BitMatrix::new(self.elements.len(), |
308 | self.elements.len()); | |
e9174d1e SL |
309 | let mut changed = true; |
310 | while changed { | |
311 | changed = false; | |
312 | for edge in self.edges.iter() { | |
313 | // add an edge from S -> T | |
314 | changed |= matrix.add(edge.source.0, edge.target.0); | |
315 | ||
316 | // add all outgoing edges from T into S | |
317 | changed |= matrix.merge(edge.target.0, edge.source.0); | |
318 | } | |
319 | } | |
320 | matrix | |
321 | } | |
322 | } | |
323 | ||
324 | /// Pare down is used as a step in the LUB computation. It edits the | |
325 | /// candidates array in place by removing any element j for which | |
326 | /// there exists an earlier element i<j such that i -> j. That is, | |
327 | /// after you run `pare_down`, you know that for all elements that | |
328 | /// remain in candidates, they cannot reach any of the elements that | |
329 | /// come after them. | |
330 | /// | |
331 | /// Examples follow. Assume that a -> b -> c and x -> y -> z. | |
332 | /// | |
333 | /// - Input: `[a, b, x]`. Output: `[a, x]`. | |
334 | /// - Input: `[b, a, x]`. Output: `[b, a, x]`. | |
335 | /// - Input: `[a, x, b, y]`. Output: `[a, x]`. | |
336 | fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix) { | |
337 | let mut i = 0; | |
338 | while i < candidates.len() { | |
339 | let candidate_i = candidates[i]; | |
340 | i += 1; | |
341 | ||
342 | let mut j = i; | |
343 | let mut dead = 0; | |
344 | while j < candidates.len() { | |
345 | let candidate_j = candidates[j]; | |
346 | if closure.contains(candidate_i, candidate_j) { | |
347 | // If `i` can reach `j`, then we can remove `j`. So just | |
348 | // mark it as dead and move on; subsequent indices will be | |
349 | // shifted into its place. | |
350 | dead += 1; | |
351 | } else { | |
352 | candidates[j - dead] = candidate_j; | |
353 | } | |
354 | j += 1; | |
355 | } | |
356 | candidates.truncate(j - dead); | |
357 | } | |
358 | } | |
359 | ||
8bb4bdeb | 360 | impl<T> Encodable for TransitiveRelation<T> |
7cac9316 | 361 | where T: Clone + Encodable + Debug + Eq + Hash + Clone |
8bb4bdeb XL |
362 | { |
363 | fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> { | |
364 | s.emit_struct("TransitiveRelation", 2, |s| { | |
365 | s.emit_struct_field("elements", 0, |s| self.elements.encode(s))?; | |
366 | s.emit_struct_field("edges", 1, |s| self.edges.encode(s))?; | |
367 | Ok(()) | |
368 | }) | |
369 | } | |
370 | } | |
371 | ||
372 | impl<T> Decodable for TransitiveRelation<T> | |
7cac9316 | 373 | where T: Clone + Decodable + Debug + Eq + Hash + Clone |
8bb4bdeb XL |
374 | { |
375 | fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> { | |
376 | d.read_struct("TransitiveRelation", 2, |d| { | |
7cac9316 | 377 | let elements: Vec<T> = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?; |
8bb4bdeb | 378 | let edges = d.read_struct_field("edges", 1, |d| Decodable::decode(d))?; |
7cac9316 XL |
379 | let map = elements.iter() |
380 | .enumerate() | |
381 | .map(|(index, elem)| (elem.clone(), Index(index))) | |
382 | .collect(); | |
383 | Ok(TransitiveRelation { elements, edges, map, closure: RefCell::new(None) }) | |
8bb4bdeb XL |
384 | }) |
385 | } | |
386 | } | |
387 | ||
cc61c64b | 388 | impl<CTX, T> HashStable<CTX> for TransitiveRelation<T> |
7cac9316 | 389 | where T: HashStable<CTX> + Eq + Debug + Clone + Hash |
cc61c64b XL |
390 | { |
391 | fn hash_stable<W: StableHasherResult>(&self, | |
392 | hcx: &mut CTX, | |
393 | hasher: &mut StableHasher<W>) { | |
394 | // We are assuming here that the relation graph has been built in a | |
395 | // deterministic way and we can just hash it the way it is. | |
396 | let TransitiveRelation { | |
397 | ref elements, | |
398 | ref edges, | |
7cac9316 XL |
399 | // "map" is just a copy of elements vec |
400 | map: _, | |
cc61c64b XL |
401 | // "closure" is just a copy of the data above |
402 | closure: _ | |
403 | } = *self; | |
404 | ||
405 | elements.hash_stable(hcx, hasher); | |
406 | edges.hash_stable(hcx, hasher); | |
407 | } | |
408 | } | |
409 | ||
410 | impl<CTX> HashStable<CTX> for Edge { | |
411 | fn hash_stable<W: StableHasherResult>(&self, | |
412 | hcx: &mut CTX, | |
413 | hasher: &mut StableHasher<W>) { | |
414 | let Edge { | |
415 | ref source, | |
416 | ref target, | |
417 | } = *self; | |
418 | ||
419 | source.hash_stable(hcx, hasher); | |
420 | target.hash_stable(hcx, hasher); | |
421 | } | |
422 | } | |
423 | ||
424 | impl<CTX> HashStable<CTX> for Index { | |
425 | fn hash_stable<W: StableHasherResult>(&self, | |
426 | hcx: &mut CTX, | |
427 | hasher: &mut StableHasher<W>) { | |
428 | let Index(idx) = *self; | |
429 | idx.hash_stable(hcx, hasher); | |
430 | } | |
431 | } | |
432 | ||
e9174d1e SL |
433 | #[test] |
434 | fn test_one_step() { | |
435 | let mut relation = TransitiveRelation::new(); | |
436 | relation.add("a", "b"); | |
437 | relation.add("a", "c"); | |
438 | assert!(relation.contains(&"a", &"c")); | |
439 | assert!(relation.contains(&"a", &"b")); | |
440 | assert!(!relation.contains(&"b", &"a")); | |
441 | assert!(!relation.contains(&"a", &"d")); | |
442 | } | |
443 | ||
444 | #[test] | |
445 | fn test_many_steps() { | |
446 | let mut relation = TransitiveRelation::new(); | |
447 | relation.add("a", "b"); | |
448 | relation.add("a", "c"); | |
449 | relation.add("a", "f"); | |
450 | ||
451 | relation.add("b", "c"); | |
452 | relation.add("b", "d"); | |
453 | relation.add("b", "e"); | |
454 | ||
455 | relation.add("e", "g"); | |
456 | ||
457 | assert!(relation.contains(&"a", &"b")); | |
458 | assert!(relation.contains(&"a", &"c")); | |
459 | assert!(relation.contains(&"a", &"d")); | |
460 | assert!(relation.contains(&"a", &"e")); | |
461 | assert!(relation.contains(&"a", &"f")); | |
462 | assert!(relation.contains(&"a", &"g")); | |
463 | ||
464 | assert!(relation.contains(&"b", &"g")); | |
465 | ||
466 | assert!(!relation.contains(&"a", &"x")); | |
467 | assert!(!relation.contains(&"b", &"f")); | |
468 | } | |
469 | ||
470 | #[test] | |
471 | fn mubs_triange() { | |
472 | let mut relation = TransitiveRelation::new(); | |
473 | relation.add("a", "tcx"); | |
474 | relation.add("b", "tcx"); | |
475 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]); | |
476 | } | |
477 | ||
478 | #[test] | |
479 | fn mubs_best_choice1() { | |
480 | // 0 -> 1 <- 3 | |
481 | // | ^ | | |
482 | // | | | | |
483 | // +--> 2 <--+ | |
484 | // | |
485 | // mubs(0,3) = [1] | |
486 | ||
487 | // This tests a particular state in the algorithm, in which we | |
488 | // need the second pare down call to get the right result (after | |
489 | // intersection, we have [1, 2], but 2 -> 1). | |
490 | ||
491 | let mut relation = TransitiveRelation::new(); | |
492 | relation.add("0", "1"); | |
493 | relation.add("0", "2"); | |
494 | ||
495 | relation.add("2", "1"); | |
496 | ||
497 | relation.add("3", "1"); | |
498 | relation.add("3", "2"); | |
499 | ||
500 | assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]); | |
501 | } | |
502 | ||
503 | #[test] | |
504 | fn mubs_best_choice2() { | |
505 | // 0 -> 1 <- 3 | |
506 | // | | | | |
507 | // | v | | |
508 | // +--> 2 <--+ | |
509 | // | |
510 | // mubs(0,3) = [2] | |
511 | ||
512 | // Like the precedecing test, but in this case intersection is [2, | |
513 | // 1], and hence we rely on the first pare down call. | |
514 | ||
515 | let mut relation = TransitiveRelation::new(); | |
516 | relation.add("0", "1"); | |
517 | relation.add("0", "2"); | |
518 | ||
519 | relation.add("1", "2"); | |
520 | ||
521 | relation.add("3", "1"); | |
522 | relation.add("3", "2"); | |
523 | ||
524 | assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]); | |
525 | } | |
526 | ||
527 | #[test] | |
528 | fn mubs_no_best_choice() { | |
529 | // in this case, the intersection yields [1, 2], and the "pare | |
530 | // down" calls find nothing to remove. | |
531 | let mut relation = TransitiveRelation::new(); | |
532 | relation.add("0", "1"); | |
533 | relation.add("0", "2"); | |
534 | ||
535 | relation.add("3", "1"); | |
536 | relation.add("3", "2"); | |
537 | ||
538 | assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]); | |
539 | } | |
540 | ||
541 | #[test] | |
542 | fn mubs_best_choice_scc() { | |
543 | let mut relation = TransitiveRelation::new(); | |
544 | relation.add("0", "1"); | |
545 | relation.add("0", "2"); | |
546 | ||
547 | relation.add("1", "2"); | |
548 | relation.add("2", "1"); | |
549 | ||
550 | relation.add("3", "1"); | |
551 | relation.add("3", "2"); | |
552 | ||
553 | assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]); | |
554 | } | |
555 | ||
556 | #[test] | |
557 | fn pdub_crisscross() { | |
558 | // diagonal edges run left-to-right | |
559 | // a -> a1 -> x | |
560 | // \/ ^ | |
561 | // /\ | | |
562 | // b -> b1 ---+ | |
563 | ||
564 | let mut relation = TransitiveRelation::new(); | |
54a0048b SL |
565 | relation.add("a", "a1"); |
566 | relation.add("a", "b1"); | |
567 | relation.add("b", "a1"); | |
568 | relation.add("b", "b1"); | |
e9174d1e SL |
569 | relation.add("a1", "x"); |
570 | relation.add("b1", "x"); | |
571 | ||
54a0048b SL |
572 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), |
573 | vec![&"a1", &"b1"]); | |
e9174d1e SL |
574 | assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x")); |
575 | } | |
576 | ||
577 | #[test] | |
578 | fn pdub_crisscross_more() { | |
579 | // diagonal edges run left-to-right | |
580 | // a -> a1 -> a2 -> a3 -> x | |
581 | // \/ \/ ^ | |
582 | // /\ /\ | | |
583 | // b -> b1 -> b2 ---------+ | |
584 | ||
585 | let mut relation = TransitiveRelation::new(); | |
54a0048b SL |
586 | relation.add("a", "a1"); |
587 | relation.add("a", "b1"); | |
588 | relation.add("b", "a1"); | |
589 | relation.add("b", "b1"); | |
e9174d1e | 590 | |
54a0048b SL |
591 | relation.add("a1", "a2"); |
592 | relation.add("a1", "b2"); | |
593 | relation.add("b1", "a2"); | |
594 | relation.add("b1", "b2"); | |
e9174d1e SL |
595 | |
596 | relation.add("a2", "a3"); | |
597 | ||
598 | relation.add("a3", "x"); | |
599 | relation.add("b2", "x"); | |
600 | ||
54a0048b SL |
601 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), |
602 | vec![&"a1", &"b1"]); | |
603 | assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"), | |
604 | vec![&"a2", &"b2"]); | |
e9174d1e SL |
605 | assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x")); |
606 | } | |
607 | ||
608 | #[test] | |
609 | fn pdub_lub() { | |
610 | // a -> a1 -> x | |
611 | // ^ | |
612 | // | | |
613 | // b -> b1 ---+ | |
614 | ||
615 | let mut relation = TransitiveRelation::new(); | |
54a0048b SL |
616 | relation.add("a", "a1"); |
617 | relation.add("b", "b1"); | |
e9174d1e SL |
618 | relation.add("a1", "x"); |
619 | relation.add("b1", "x"); | |
620 | ||
621 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]); | |
622 | assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x")); | |
623 | } | |
624 | ||
625 | #[test] | |
626 | fn mubs_intermediate_node_on_one_side_only() { | |
627 | // a -> c -> d | |
628 | // ^ | |
629 | // | | |
630 | // b | |
631 | ||
632 | // "digraph { a -> c -> d; b -> d; }", | |
633 | let mut relation = TransitiveRelation::new(); | |
54a0048b SL |
634 | relation.add("a", "c"); |
635 | relation.add("c", "d"); | |
636 | relation.add("b", "d"); | |
e9174d1e SL |
637 | |
638 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]); | |
639 | } | |
640 | ||
641 | #[test] | |
642 | fn mubs_scc_1() { | |
643 | // +-------------+ | |
644 | // | +----+ | | |
645 | // | v | | | |
646 | // a -> c -> d <-+ | |
647 | // ^ | |
648 | // | | |
649 | // b | |
650 | ||
651 | // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }", | |
652 | let mut relation = TransitiveRelation::new(); | |
54a0048b SL |
653 | relation.add("a", "c"); |
654 | relation.add("c", "d"); | |
655 | relation.add("d", "c"); | |
656 | relation.add("a", "d"); | |
657 | relation.add("b", "d"); | |
e9174d1e SL |
658 | |
659 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); | |
660 | } | |
661 | ||
662 | #[test] | |
663 | fn mubs_scc_2() { | |
664 | // +----+ | |
665 | // v | | |
666 | // a -> c -> d | |
667 | // ^ ^ | |
668 | // | | | |
669 | // +--- b | |
670 | ||
671 | // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }", | |
672 | let mut relation = TransitiveRelation::new(); | |
54a0048b SL |
673 | relation.add("a", "c"); |
674 | relation.add("c", "d"); | |
675 | relation.add("d", "c"); | |
676 | relation.add("b", "d"); | |
677 | relation.add("b", "c"); | |
e9174d1e SL |
678 | |
679 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); | |
680 | } | |
681 | ||
682 | #[test] | |
683 | fn mubs_scc_3() { | |
684 | // +---------+ | |
685 | // v | | |
686 | // a -> c -> d -> e | |
687 | // ^ ^ | |
688 | // | | | |
689 | // b ---+ | |
690 | ||
691 | // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }", | |
692 | let mut relation = TransitiveRelation::new(); | |
54a0048b SL |
693 | relation.add("a", "c"); |
694 | relation.add("c", "d"); | |
695 | relation.add("d", "e"); | |
696 | relation.add("e", "c"); | |
697 | relation.add("b", "d"); | |
698 | relation.add("b", "e"); | |
e9174d1e SL |
699 | |
700 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); | |
701 | } | |
702 | ||
703 | #[test] | |
704 | fn mubs_scc_4() { | |
705 | // +---------+ | |
706 | // v | | |
707 | // a -> c -> d -> e | |
708 | // | ^ ^ | |
709 | // +---------+ | | |
710 | // | | |
711 | // b ---+ | |
712 | ||
713 | // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }" | |
714 | let mut relation = TransitiveRelation::new(); | |
54a0048b SL |
715 | relation.add("a", "c"); |
716 | relation.add("c", "d"); | |
717 | relation.add("d", "e"); | |
718 | relation.add("e", "c"); | |
719 | relation.add("a", "d"); | |
720 | relation.add("b", "e"); | |
e9174d1e SL |
721 | |
722 | assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); | |
723 | } |