src/librustc_data_structures/transitive_relation.rs

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