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 bit_set::BitMatrix;
  12 use fx::FxHashMap;
  13 use sync::Lock;
  14 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
  15 use stable_hasher::{HashStable, StableHasher, StableHasherResult};
  16 use std::fmt::Debug;
  17 use std::hash::Hash;
  18 use std::mem;
  19
  20
  21 #[derive(Clone, Debug)]
  22 pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash> {
  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 Lock 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: Lock<Option<BitMatrix<usize, usize>>>,
  43 }
  44
  45 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable, Debug)]
  46 struct Index(usize);
  47
  48 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
  49 struct Edge {
  50     source: Index,
  51     target: Index,
  52 }
  53
  54 impl<T: Clone + Debug + Eq + Hash> Default for TransitiveRelation<T> {
  55     fn default() -> TransitiveRelation<T> {
  56         TransitiveRelation {
  57             elements: vec![],
  58             map: FxHashMap::default(),
  59             edges: vec![],
  60             closure: Lock::new(None),
  61         }
  62     }
  63 }
  64
  65 impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
  66     pub fn is_empty(&self) -> bool {
  67         self.edges.is_empty()
  68     }
  69
  70     fn index(&self, a: &T) -> Option<Index> {
  71         self.map.get(a).cloned()
  72     }
  73
  74     fn add_index(&mut self, a: T) -> Index {
  75         let &mut TransitiveRelation {
  76             ref mut elements,
  77             ref mut closure,
  78             ref mut map,
  79             ..
  80         } = self;
  81
  82         *map.entry(a.clone())
  83            .or_insert_with(|| {
  84                elements.push(a);
  85
  86                // if we changed the dimensions, clear the cache
  87                *closure.get_mut() = None;
  88
  89                Index(elements.len() - 1)
  90            })
  91     }
  92
  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     {
 100         let mut result = TransitiveRelation::default();
 101         for edge in &self.edges {
 102             result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?);
 103         }
 104         Some(result)
 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);
 111         let edge = Edge {
 112             source: a,
 113             target: b,
 114         };
 115         if !self.edges.contains(&edge) {
 116             self.edges.push(edge);
 117
 118             // added an edge, clear the cache
 119             *self.closure.get_mut() = None;
 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)) {
 126             (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)),
 127             (None, _) | (_, None) => false,
 128         }
 129     }
 130
 131     /// Thinking of `x R y` as an edge `x -> y` in a graph, this
 132     /// returns all things reachable from `a`.
 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.
 137     pub fn reachable_from(&self, a: &T) -> Vec<&T> {
 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
 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> {
 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> {
 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),
 216             (None, _) | (_, None) => {
 217                 return vec![];
 218             }
 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`)
 281             //
 282             // This same algorithm is used in `parents` below.
 283
 284             let mut candidates = closure.intersect_rows(a.0, b.0); // (1)
 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
 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| {
 326             let mut ancestors = closure.intersect_rows(a.0, a.0);
 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
 350     fn with_closure<OP, R>(&self, op: OP) -> R
 351         where OP: FnOnce(&BitMatrix<usize, usize>) -> R
 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
 363     fn compute_closure(&self) -> BitMatrix<usize, usize> {
 364         let mut matrix = BitMatrix::new(self.elements.len(),
 365                                         self.elements.len());
 366         let mut changed = true;
 367         while changed {
 368             changed = false;
 369             for edge in &self.edges {
 370                 // add an edge from S -> T
 371                 changed |= matrix.insert(edge.source.0, edge.target.0);
 372
 373                 // add all outgoing edges from T into S
 374                 changed |= matrix.union_rows(edge.target.0, edge.source.0);
 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]`.
 393 fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) {
 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
 417 impl<T> Encodable for TransitiveRelation<T>
 418     where T: Clone + Encodable + Debug + Eq + Hash + Clone
 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>
 430     where T: Clone + Decodable + Debug + Eq + Hash + Clone
 431 {
 432     fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> {
 433         d.read_struct("TransitiveRelation", 2, |d| {
 434             let elements: Vec<T> = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?;
 435             let edges = d.read_struct_field("edges", 1, |d| Decodable::decode(d))?;
 436             let map = elements.iter()
 437                               .enumerate()
 438                               .map(|(index, elem)| (elem.clone(), Index(index)))
 439                               .collect();
 440             Ok(TransitiveRelation { elements, edges, map, closure: Lock::new(None) })
 441         })
 442     }
 443 }
 444
 445 impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
 446     where T: HashStable<CTX> + Eq + Debug + Clone + Hash
 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,
 456             // "map" is just a copy of elements vec
 457             map: _,
 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
 490 #[test]
 491 fn test_one_step() {
 492     let mut relation = TransitiveRelation::default();
 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() {
 503     let mut relation = TransitiveRelation::default();
 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]
 528 fn mubs_triangle() {
 529     // a -> tcx
 530     //      ^
 531     //      |
 532     //      b
 533     let mut relation = TransitiveRelation::default();
 534     relation.add("a", "tcx");
 535     relation.add("b", "tcx");
 536     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
 537     assert_eq!(relation.parents(&"a"), vec![&"tcx"]);
 538     assert_eq!(relation.parents(&"b"), vec![&"tcx"]);
 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
 554     let mut relation = TransitiveRelation::default();
 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"]);
 564     assert_eq!(relation.parents(&"0"), vec![&"2"]);
 565     assert_eq!(relation.parents(&"2"), vec![&"1"]);
 566     assert!(relation.parents(&"1").is_empty());
 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
 581     let mut relation = TransitiveRelation::default();
 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"]);
 591     assert_eq!(relation.parents(&"0"), vec![&"1"]);
 592     assert_eq!(relation.parents(&"1"), vec![&"2"]);
 593     assert!(relation.parents(&"2").is_empty());
 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.
 600     let mut relation = TransitiveRelation::default();
 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"]);
 608     assert_eq!(relation.parents(&"0"), vec![&"1", &"2"]);
 609     assert_eq!(relation.parents(&"3"), vec![&"1", &"2"]);
 610 }
 611
 612 #[test]
 613 fn mubs_best_choice_scc() {
 614     // in this case, 1 and 2 form a cycle; we pick arbitrarily (but
 615     // consistently).
 616
 617     let mut relation = TransitiveRelation::default();
 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"]);
 628     assert_eq!(relation.parents(&"0"), vec![&"1"]);
 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
 639     let mut relation = TransitiveRelation::default();
 640     relation.add("a", "a1");
 641     relation.add("a", "b1");
 642     relation.add("b", "a1");
 643     relation.add("b", "b1");
 644     relation.add("a1", "x");
 645     relation.add("b1", "x");
 646
 647     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
 648                vec![&"a1", &"b1"]);
 649     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 650     assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
 651     assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
 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
 662     let mut relation = TransitiveRelation::default();
 663     relation.add("a", "a1");
 664     relation.add("a", "b1");
 665     relation.add("b", "a1");
 666     relation.add("b", "b1");
 667
 668     relation.add("a1", "a2");
 669     relation.add("a1", "b2");
 670     relation.add("b1", "a2");
 671     relation.add("b1", "b2");
 672
 673     relation.add("a2", "a3");
 674
 675     relation.add("a3", "x");
 676     relation.add("b2", "x");
 677
 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"]);
 682     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 683
 684     assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
 685     assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
 686 }
 687
 688 #[test]
 689 fn pdub_lub() {
 690     // a -> a1 -> x
 691     //            ^
 692     //            |
 693     // b -> b1 ---+
 694
 695     let mut relation = TransitiveRelation::default();
 696     relation.add("a", "a1");
 697     relation.add("b", "b1");
 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"));
 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"));
 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; }",
 718     let mut relation = TransitiveRelation::default();
 719     relation.add("a", "c");
 720     relation.add("c", "d");
 721     relation.add("b", "d");
 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; }",
 737     let mut relation = TransitiveRelation::default();
 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");
 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; }",
 757     let mut relation = TransitiveRelation::default();
 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");
 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; }",
 777     let mut relation = TransitiveRelation::default();
 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");
 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; }"
 799     let mut relation = TransitiveRelation::default();
 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");
 806
 807     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 808 }
 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
 837     let mut relation = TransitiveRelation::default();
 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 }