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