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