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 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> TransitiveRelation<T> {
  55     pub fn new() -> TransitiveRelation<T> {
  56         TransitiveRelation {
  57             elements: vec![],
  58             map: FxHashMap(),
  59             edges: vec![],
  60             closure: Lock::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 mut 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.get_mut() = None;
  86
  87                Index(elements.len() - 1)
  88            })
  89     }
  90
  91     /// Applies the (partial) function to each edge and returns a new
  92     /// relation.  If `f` returns `None` for any end-point, returns
  93     /// `None`.
  94     pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>>
  95         where F: FnMut(&T) -> Option<U>,
  96               U: Clone + Debug + Eq + Hash + Clone,
  97     {
  98         let mut result = TransitiveRelation::new();
  99         for edge in &self.edges {
 100             result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?);
 101         }
 102         Some(result)
 103     }
 104
 105     /// Indicate that `a < b` (where `<` is this relation)
 106     pub fn add(&mut self, a: T, b: T) {
 107         let a = self.add_index(a);
 108         let b = self.add_index(b);
 109         let edge = Edge {
 110             source: a,
 111             target: b,
 112         };
 113         if !self.edges.contains(&edge) {
 114             self.edges.push(edge);
 115
 116             // added an edge, clear the cache
 117             *self.closure.get_mut() = None;
 118         }
 119     }
 120
 121     /// Check whether `a < target` (transitively)
 122     pub fn contains(&self, a: &T, b: &T) -> bool {
 123         match (self.index(a), self.index(b)) {
 124             (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)),
 125             (None, _) | (_, None) => false,
 126         }
 127     }
 128
 129     /// Thinking of `x R y` as an edge `x -> y` in a graph, this
 130     /// returns all things reachable from `a`.
 131     ///
 132     /// Really this probably ought to be `impl Iterator<Item=&T>`, but
 133     /// I'm too lazy to make that work, and -- given the caching
 134     /// strategy -- it'd be a touch tricky anyhow.
 135     pub fn reachable_from(&self, a: &T) -> Vec<&T> {
 136         match self.index(a) {
 137             Some(a) => self.with_closure(|closure| {
 138                 closure.iter(a.0).map(|i| &self.elements[i]).collect()
 139             }),
 140             None => vec![],
 141         }
 142     }
 143
 144     /// Picks what I am referring to as the "postdominating"
 145     /// upper-bound for `a` and `b`. This is usually the least upper
 146     /// bound, but in cases where there is no single least upper
 147     /// bound, it is the "mutual immediate postdominator", if you
 148     /// imagine a graph where `a < b` means `a -> b`.
 149     ///
 150     /// This function is needed because region inference currently
 151     /// requires that we produce a single "UB", and there is no best
 152     /// choice for the LUB. Rather than pick arbitrarily, I pick a
 153     /// less good, but predictable choice. This should help ensure
 154     /// that region inference yields predictable results (though it
 155     /// itself is not fully sufficient).
 156     ///
 157     /// Examples are probably clearer than any prose I could write
 158     /// (there are corresponding tests below, btw). In each case,
 159     /// the query is `postdom_upper_bound(a, b)`:
 160     ///
 161     /// ```text
 162     /// // returns Some(x), which is also LUB
 163     /// a -> a1 -> x
 164     ///            ^
 165     ///            |
 166     /// b -> b1 ---+
 167     ///
 168     /// // returns Some(x), which is not LUB (there is none)
 169     /// // diagonal edges run left-to-right
 170     /// a -> a1 -> x
 171     ///   \/       ^
 172     ///   /\       |
 173     /// b -> b1 ---+
 174     ///
 175     /// // returns None
 176     /// a -> a1
 177     /// b -> b1
 178     /// ```
 179     pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> {
 180         let mubs = self.minimal_upper_bounds(a, b);
 181         self.mutual_immediate_postdominator(mubs)
 182     }
 183
 184     /// Viewing the relation as a graph, computes the "mutual
 185     /// immediate postdominator" of a set of points (if one
 186     /// exists). See `postdom_upper_bound` for details.
 187     pub fn mutual_immediate_postdominator<'a>(&'a self, mut mubs: Vec<&'a T>) -> Option<&'a T> {
 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             // This same algorithm is used in `parents` below.
 281
 282             let mut candidates = closure.intersection(a.0, b.0); // (1)
 283             pare_down(&mut candidates, closure); // (2)
 284             candidates.reverse(); // (3a)
 285             pare_down(&mut candidates, closure); // (3b)
 286             candidates
 287         });
 288
 289         lub_indices.into_iter()
 290                    .rev() // (4)
 291                    .map(|i| &self.elements[i])
 292                    .collect()
 293     }
 294
 295     /// Given an element A, returns the maximal set {B} of elements B
 296     /// such that
 297     ///
 298     /// - A != B
 299     /// - A R B is true
 300     /// - for each i, j: B[i] R B[j] does not hold
 301     ///
 302     /// The intuition is that this moves "one step up" through a lattice
 303     /// (where the relation is encoding the `<=` relation for the lattice).
 304     /// So e.g. if the relation is `->` and we have
 305     ///
 306     /// ```
 307     /// a -> b -> d -> f
 308     /// |              ^
 309     /// +--> c -> e ---+
 310     /// ```
 311     ///
 312     /// then `parents(a)` returns `[b, c]`. The `postdom_parent` function
 313     /// would further reduce this to just `f`.
 314     pub fn parents(&self, a: &T) -> Vec<&T> {
 315         let a = match self.index(a) {
 316             Some(a) => a,
 317             None => return vec![]
 318         };
 319
 320         // Steal the algorithm for `minimal_upper_bounds` above, but
 321         // with a slight tweak. In the case where `a R a`, we remove
 322         // that from the set of candidates.
 323         let ancestors = self.with_closure(|closure| {
 324             let mut ancestors = closure.intersection(a.0, a.0);
 325
 326             // Remove anything that can reach `a`. If this is a
 327             // reflexive relation, this will include `a` itself.
 328             ancestors.retain(|&e| !closure.contains(e, a.0));
 329
 330             pare_down(&mut ancestors, closure); // (2)
 331             ancestors.reverse(); // (3a)
 332             pare_down(&mut ancestors, closure); // (3b)
 333             ancestors
 334         });
 335
 336         ancestors.into_iter()
 337                  .rev() // (4)
 338                  .map(|i| &self.elements[i])
 339                  .collect()
 340     }
 341
 342     /// A "best" parent in some sense. See `parents` and
 343     /// `postdom_upper_bound` for more details.
 344     pub fn postdom_parent(&self, a: &T) -> Option<&T> {
 345         self.mutual_immediate_postdominator(self.parents(a))
 346     }
 347
 348     fn with_closure<OP, R>(&self, op: OP) -> R
 349         where OP: FnOnce(&BitMatrix<usize, usize>) -> R
 350     {
 351         let mut closure_cell = self.closure.borrow_mut();
 352         let mut closure = closure_cell.take();
 353         if closure.is_none() {
 354             closure = Some(self.compute_closure());
 355         }
 356         let result = op(closure.as_ref().unwrap());
 357         *closure_cell = closure;
 358         result
 359     }
 360
 361     fn compute_closure(&self) -> BitMatrix<usize, usize> {
 362         let mut matrix = BitMatrix::new(self.elements.len(),
 363                                         self.elements.len());
 364         let mut changed = true;
 365         while changed {
 366             changed = false;
 367             for edge in &self.edges {
 368                 // add an edge from S -> T
 369                 changed |= matrix.add(edge.source.0, edge.target.0);
 370
 371                 // add all outgoing edges from T into S
 372                 changed |= matrix.merge(edge.target.0, edge.source.0);
 373             }
 374         }
 375         matrix
 376     }
 377 }
 378
 379 /// Pare down is used as a step in the LUB computation. It edits the
 380 /// candidates array in place by removing any element j for which
 381 /// there exists an earlier element i<j such that i -> j. That is,
 382 /// after you run `pare_down`, you know that for all elements that
 383 /// remain in candidates, they cannot reach any of the elements that
 384 /// come after them.
 385 ///
 386 /// Examples follow. Assume that a -> b -> c and x -> y -> z.
 387 ///
 388 /// - Input: `[a, b, x]`. Output: `[a, x]`.
 389 /// - Input: `[b, a, x]`. Output: `[b, a, x]`.
 390 /// - Input: `[a, x, b, y]`. Output: `[a, x]`.
 391 fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) {
 392     let mut i = 0;
 393     while i < candidates.len() {
 394         let candidate_i = candidates[i];
 395         i += 1;
 396
 397         let mut j = i;
 398         let mut dead = 0;
 399         while j < candidates.len() {
 400             let candidate_j = candidates[j];
 401             if closure.contains(candidate_i, candidate_j) {
 402                 // If `i` can reach `j`, then we can remove `j`. So just
 403                 // mark it as dead and move on; subsequent indices will be
 404                 // shifted into its place.
 405                 dead += 1;
 406             } else {
 407                 candidates[j - dead] = candidate_j;
 408             }
 409             j += 1;
 410         }
 411         candidates.truncate(j - dead);
 412     }
 413 }
 414
 415 impl<T> Encodable for TransitiveRelation<T>
 416     where T: Clone + Encodable + Debug + Eq + Hash + Clone
 417 {
 418     fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> {
 419         s.emit_struct("TransitiveRelation", 2, |s| {
 420             s.emit_struct_field("elements", 0, |s| self.elements.encode(s))?;
 421             s.emit_struct_field("edges", 1, |s| self.edges.encode(s))?;
 422             Ok(())
 423         })
 424     }
 425 }
 426
 427 impl<T> Decodable for TransitiveRelation<T>
 428     where T: Clone + Decodable + Debug + Eq + Hash + Clone
 429 {
 430     fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> {
 431         d.read_struct("TransitiveRelation", 2, |d| {
 432             let elements: Vec<T> = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?;
 433             let edges = d.read_struct_field("edges", 1, |d| Decodable::decode(d))?;
 434             let map = elements.iter()
 435                               .enumerate()
 436                               .map(|(index, elem)| (elem.clone(), Index(index)))
 437                               .collect();
 438             Ok(TransitiveRelation { elements, edges, map, closure: Lock::new(None) })
 439         })
 440     }
 441 }
 442
 443 impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
 444     where T: HashStable<CTX> + Eq + Debug + Clone + Hash
 445 {
 446     fn hash_stable<W: StableHasherResult>(&self,
 447                                           hcx: &mut CTX,
 448                                           hasher: &mut StableHasher<W>) {
 449         // We are assuming here that the relation graph has been built in a
 450         // deterministic way and we can just hash it the way it is.
 451         let TransitiveRelation {
 452             ref elements,
 453             ref edges,
 454             // "map" is just a copy of elements vec
 455             map: _,
 456             // "closure" is just a copy of the data above
 457             closure: _
 458         } = *self;
 459
 460         elements.hash_stable(hcx, hasher);
 461         edges.hash_stable(hcx, hasher);
 462     }
 463 }
 464
 465 impl<CTX> HashStable<CTX> for Edge {
 466     fn hash_stable<W: StableHasherResult>(&self,
 467                                           hcx: &mut CTX,
 468                                           hasher: &mut StableHasher<W>) {
 469         let Edge {
 470             ref source,
 471             ref target,
 472         } = *self;
 473
 474         source.hash_stable(hcx, hasher);
 475         target.hash_stable(hcx, hasher);
 476     }
 477 }
 478
 479 impl<CTX> HashStable<CTX> for Index {
 480     fn hash_stable<W: StableHasherResult>(&self,
 481                                           hcx: &mut CTX,
 482                                           hasher: &mut StableHasher<W>) {
 483         let Index(idx) = *self;
 484         idx.hash_stable(hcx, hasher);
 485     }
 486 }
 487
 488 #[test]
 489 fn test_one_step() {
 490     let mut relation = TransitiveRelation::new();
 491     relation.add("a", "b");
 492     relation.add("a", "c");
 493     assert!(relation.contains(&"a", &"c"));
 494     assert!(relation.contains(&"a", &"b"));
 495     assert!(!relation.contains(&"b", &"a"));
 496     assert!(!relation.contains(&"a", &"d"));
 497 }
 498
 499 #[test]
 500 fn test_many_steps() {
 501     let mut relation = TransitiveRelation::new();
 502     relation.add("a", "b");
 503     relation.add("a", "c");
 504     relation.add("a", "f");
 505
 506     relation.add("b", "c");
 507     relation.add("b", "d");
 508     relation.add("b", "e");
 509
 510     relation.add("e", "g");
 511
 512     assert!(relation.contains(&"a", &"b"));
 513     assert!(relation.contains(&"a", &"c"));
 514     assert!(relation.contains(&"a", &"d"));
 515     assert!(relation.contains(&"a", &"e"));
 516     assert!(relation.contains(&"a", &"f"));
 517     assert!(relation.contains(&"a", &"g"));
 518
 519     assert!(relation.contains(&"b", &"g"));
 520
 521     assert!(!relation.contains(&"a", &"x"));
 522     assert!(!relation.contains(&"b", &"f"));
 523 }
 524
 525 #[test]
 526 fn mubs_triangle() {
 527     // a -> tcx
 528     //      ^
 529     //      |
 530     //      b
 531     let mut relation = TransitiveRelation::new();
 532     relation.add("a", "tcx");
 533     relation.add("b", "tcx");
 534     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
 535     assert_eq!(relation.parents(&"a"), vec![&"tcx"]);
 536     assert_eq!(relation.parents(&"b"), vec![&"tcx"]);
 537 }
 538
 539 #[test]
 540 fn mubs_best_choice1() {
 541     // 0 -> 1 <- 3
 542     // |    ^    |
 543     // |    |    |
 544     // +--> 2 <--+
 545     //
 546     // mubs(0,3) = [1]
 547
 548     // This tests a particular state in the algorithm, in which we
 549     // need the second pare down call to get the right result (after
 550     // intersection, we have [1, 2], but 2 -> 1).
 551
 552     let mut relation = TransitiveRelation::new();
 553     relation.add("0", "1");
 554     relation.add("0", "2");
 555
 556     relation.add("2", "1");
 557
 558     relation.add("3", "1");
 559     relation.add("3", "2");
 560
 561     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
 562     assert_eq!(relation.parents(&"0"), vec![&"2"]);
 563     assert_eq!(relation.parents(&"2"), vec![&"1"]);
 564     assert!(relation.parents(&"1").is_empty());
 565 }
 566
 567 #[test]
 568 fn mubs_best_choice2() {
 569     // 0 -> 1 <- 3
 570     // |    |    |
 571     // |    v    |
 572     // +--> 2 <--+
 573     //
 574     // mubs(0,3) = [2]
 575
 576     // Like the precedecing test, but in this case intersection is [2,
 577     // 1], and hence we rely on the first pare down call.
 578
 579     let mut relation = TransitiveRelation::new();
 580     relation.add("0", "1");
 581     relation.add("0", "2");
 582
 583     relation.add("1", "2");
 584
 585     relation.add("3", "1");
 586     relation.add("3", "2");
 587
 588     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
 589     assert_eq!(relation.parents(&"0"), vec![&"1"]);
 590     assert_eq!(relation.parents(&"1"), vec![&"2"]);
 591     assert!(relation.parents(&"2").is_empty());
 592 }
 593
 594 #[test]
 595 fn mubs_no_best_choice() {
 596     // in this case, the intersection yields [1, 2], and the "pare
 597     // down" calls find nothing to remove.
 598     let mut relation = TransitiveRelation::new();
 599     relation.add("0", "1");
 600     relation.add("0", "2");
 601
 602     relation.add("3", "1");
 603     relation.add("3", "2");
 604
 605     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
 606     assert_eq!(relation.parents(&"0"), vec![&"1", &"2"]);
 607     assert_eq!(relation.parents(&"3"), vec![&"1", &"2"]);
 608 }
 609
 610 #[test]
 611 fn mubs_best_choice_scc() {
 612     // in this case, 1 and 2 form a cycle; we pick arbitrarily (but
 613     // consistently).
 614
 615     let mut relation = TransitiveRelation::new();
 616     relation.add("0", "1");
 617     relation.add("0", "2");
 618
 619     relation.add("1", "2");
 620     relation.add("2", "1");
 621
 622     relation.add("3", "1");
 623     relation.add("3", "2");
 624
 625     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
 626     assert_eq!(relation.parents(&"0"), vec![&"1"]);
 627 }
 628
 629 #[test]
 630 fn pdub_crisscross() {
 631     // diagonal edges run left-to-right
 632     // a -> a1 -> x
 633     //   \/       ^
 634     //   /\       |
 635     // b -> b1 ---+
 636
 637     let mut relation = TransitiveRelation::new();
 638     relation.add("a", "a1");
 639     relation.add("a", "b1");
 640     relation.add("b", "a1");
 641     relation.add("b", "b1");
 642     relation.add("a1", "x");
 643     relation.add("b1", "x");
 644
 645     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
 646                vec![&"a1", &"b1"]);
 647     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 648     assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
 649     assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
 650 }
 651
 652 #[test]
 653 fn pdub_crisscross_more() {
 654     // diagonal edges run left-to-right
 655     // a -> a1 -> a2 -> a3 -> x
 656     //   \/    \/             ^
 657     //   /\    /\             |
 658     // b -> b1 -> b2 ---------+
 659
 660     let mut relation = TransitiveRelation::new();
 661     relation.add("a", "a1");
 662     relation.add("a", "b1");
 663     relation.add("b", "a1");
 664     relation.add("b", "b1");
 665
 666     relation.add("a1", "a2");
 667     relation.add("a1", "b2");
 668     relation.add("b1", "a2");
 669     relation.add("b1", "b2");
 670
 671     relation.add("a2", "a3");
 672
 673     relation.add("a3", "x");
 674     relation.add("b2", "x");
 675
 676     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
 677                vec![&"a1", &"b1"]);
 678     assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"),
 679                vec![&"a2", &"b2"]);
 680     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 681
 682     assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
 683     assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
 684 }
 685
 686 #[test]
 687 fn pdub_lub() {
 688     // a -> a1 -> x
 689     //            ^
 690     //            |
 691     // b -> b1 ---+
 692
 693     let mut relation = TransitiveRelation::new();
 694     relation.add("a", "a1");
 695     relation.add("b", "b1");
 696     relation.add("a1", "x");
 697     relation.add("b1", "x");
 698
 699     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
 700     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 701
 702     assert_eq!(relation.postdom_parent(&"a"), Some(&"a1"));
 703     assert_eq!(relation.postdom_parent(&"b"), Some(&"b1"));
 704     assert_eq!(relation.postdom_parent(&"a1"), Some(&"x"));
 705     assert_eq!(relation.postdom_parent(&"b1"), Some(&"x"));
 706 }
 707
 708 #[test]
 709 fn mubs_intermediate_node_on_one_side_only() {
 710     // a -> c -> d
 711     //           ^
 712     //           |
 713     //           b
 714
 715     // "digraph { a -> c -> d; b -> d; }",
 716     let mut relation = TransitiveRelation::new();
 717     relation.add("a", "c");
 718     relation.add("c", "d");
 719     relation.add("b", "d");
 720
 721     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
 722 }
 723
 724 #[test]
 725 fn mubs_scc_1() {
 726     // +-------------+
 727     // |    +----+   |
 728     // |    v    |   |
 729     // a -> c -> d <-+
 730     //           ^
 731     //           |
 732     //           b
 733
 734     // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
 735     let mut relation = TransitiveRelation::new();
 736     relation.add("a", "c");
 737     relation.add("c", "d");
 738     relation.add("d", "c");
 739     relation.add("a", "d");
 740     relation.add("b", "d");
 741
 742     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 743 }
 744
 745 #[test]
 746 fn mubs_scc_2() {
 747     //      +----+
 748     //      v    |
 749     // a -> c -> d
 750     //      ^    ^
 751     //      |    |
 752     //      +--- b
 753
 754     // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
 755     let mut relation = TransitiveRelation::new();
 756     relation.add("a", "c");
 757     relation.add("c", "d");
 758     relation.add("d", "c");
 759     relation.add("b", "d");
 760     relation.add("b", "c");
 761
 762     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 763 }
 764
 765 #[test]
 766 fn mubs_scc_3() {
 767     //      +---------+
 768     //      v         |
 769     // a -> c -> d -> e
 770     //           ^    ^
 771     //           |    |
 772     //           b ---+
 773
 774     // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
 775     let mut relation = TransitiveRelation::new();
 776     relation.add("a", "c");
 777     relation.add("c", "d");
 778     relation.add("d", "e");
 779     relation.add("e", "c");
 780     relation.add("b", "d");
 781     relation.add("b", "e");
 782
 783     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 784 }
 785
 786 #[test]
 787 fn mubs_scc_4() {
 788     //      +---------+
 789     //      v         |
 790     // a -> c -> d -> e
 791     // |         ^    ^
 792     // +---------+    |
 793     //                |
 794     //           b ---+
 795
 796     // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
 797     let mut relation = TransitiveRelation::new();
 798     relation.add("a", "c");
 799     relation.add("c", "d");
 800     relation.add("d", "e");
 801     relation.add("e", "c");
 802     relation.add("a", "d");
 803     relation.add("b", "e");
 804
 805     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 806 }
 807
 808 #[test]
 809 fn parent() {
 810     // An example that was misbehaving in the compiler.
 811     //
 812     // 4 -> 1 -> 3
 813     //   \  |   /
 814     //    \ v  /
 815     // 2 -> 0
 816     //
 817     // plus a bunch of self-loops
 818     //
 819     // Here `->` represents `<=` and `0` is `'static`.
 820
 821     let pairs = vec![
 822         (2, /*->*/ 0),
 823         (2, /*->*/ 2),
 824         (0, /*->*/ 0),
 825         (0, /*->*/ 0),
 826         (1, /*->*/ 0),
 827         (1, /*->*/ 1),
 828         (3, /*->*/ 0),
 829         (3, /*->*/ 3),
 830         (4, /*->*/ 0),
 831         (4, /*->*/ 1),
 832         (1, /*->*/ 3),
 833     ];
 834
 835     let mut relation = TransitiveRelation::new();
 836     for (a, b) in pairs {
 837         relation.add(a, b);
 838     }
 839
 840     let p = relation.postdom_parent(&3);
 841     assert_eq!(p, Some(&0));
 842 }