src/librustc_data_structures/transitive_relation.rs

   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;
  12 use fx::FxHashMap;
  13 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
  14 use stable_hasher::{HashStable, StableHasher, StableHasherResult};
  15 use std::cell::RefCell;
  16 use std::fmt::Debug;
  17 use std::hash::Hash;
  18 use std::mem;
  19
  20
  21 #[derive(Clone)]
  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.
  24     elements: Vec<T>,
  25
  26     // Maps each element to an index.
  27     map: FxHashMap<T, Index>,
  28
  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
  42     closure: RefCell<Option<BitMatrix>>,
  43 }
  44
  45 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
  46 struct Index(usize);
  47
  48 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
  49 struct Edge {
  50     source: Index,
  51     target: Index,
  52 }
  53
  54 impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> {
  55     pub fn new() -> TransitiveRelation<T> {
  56         TransitiveRelation {
  57             elements: vec![],
  58             map: FxHashMap(),
  59             edges: vec![],
  60             closure: RefCell::new(None),
  61         }
  62     }
  63
  64     pub fn is_empty(&self) -> bool {
  65         self.edges.is_empty()
  66     }
  67
  68     fn index(&self, a: &T) -> Option<Index> {
  69         self.map.get(a).cloned()
  70     }
  71
  72     fn add_index(&mut self, a: T) -> Index {
  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     }
  91
  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;
 108             }
 109         }
 110         Some(result)
 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);
 117         let edge = Edge {
 118             source: a,
 119             target: b,
 120         };
 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)) {
 132             (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)),
 133             (None, _) | (_, None) => false,
 134         }
 135     }
 136
 137     /// Returns a vector of all things less than `a`.
 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.
 142     pub fn less_than(&self, a: &T) -> Vec<&T> {
 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
 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),
 214             (None, _) | (_, None) => {
 215                 return vec![];
 216             }
 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
 293     fn with_closure<OP, R>(&self, op: OP) -> R
 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 {
 307         let mut matrix = BitMatrix::new(self.elements.len(),
 308                                         self.elements.len());
 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
 360 impl<T> Encodable for TransitiveRelation<T>
 361     where T: Clone + Encodable + Debug + Eq + Hash + Clone
 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>
 373     where T: Clone + Decodable + Debug + Eq + Hash + Clone
 374 {
 375     fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> {
 376         d.read_struct("TransitiveRelation", 2, |d| {
 377             let elements: Vec<T> = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?;
 378             let edges = d.read_struct_field("edges", 1, |d| Decodable::decode(d))?;
 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) })
 384         })
 385     }
 386 }
 387
 388 impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
 389     where T: HashStable<CTX> + Eq + Debug + Clone + Hash
 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,
 399             // "map" is just a copy of elements vec
 400             map: _,
 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
 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();
 565     relation.add("a", "a1");
 566     relation.add("a", "b1");
 567     relation.add("b", "a1");
 568     relation.add("b", "b1");
 569     relation.add("a1", "x");
 570     relation.add("b1", "x");
 571
 572     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
 573                vec![&"a1", &"b1"]);
 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();
 586     relation.add("a", "a1");
 587     relation.add("a", "b1");
 588     relation.add("b", "a1");
 589     relation.add("b", "b1");
 590
 591     relation.add("a1", "a2");
 592     relation.add("a1", "b2");
 593     relation.add("b1", "a2");
 594     relation.add("b1", "b2");
 595
 596     relation.add("a2", "a3");
 597
 598     relation.add("a3", "x");
 599     relation.add("b2", "x");
 600
 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"]);
 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();
 616     relation.add("a", "a1");
 617     relation.add("b", "b1");
 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();
 634     relation.add("a", "c");
 635     relation.add("c", "d");
 636     relation.add("b", "d");
 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();
 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");
 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();
 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");
 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();
 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");
 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();
 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");
 721
 722     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 723 }