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 std::cell::RefCell;
  13 use std::fmt::Debug;
  14 use std::mem;
  15
  16 #[derive(Clone)]
  17 pub struct TransitiveRelation<T: Debug + PartialEq> {
  18     // List of elements. This is used to map from a T to a usize.  We
  19     // expect domain to be small so just use a linear list versus a
  20     // hashmap or something.
  21     elements: Vec<T>,
  22
  23     // List of base edges in the graph. Require to compute transitive
  24     // closure.
  25     edges: Vec<Edge>,
  26
  27     // This is a cached transitive closure derived from the edges.
  28     // Currently, we build it lazilly and just throw out any existing
  29     // copy whenever a new edge is added. (The RefCell is to permit
  30     // the lazy computation.) This is kind of silly, except for the
  31     // fact its size is tied to `self.elements.len()`, so I wanted to
  32     // wait before building it up to avoid reallocating as new edges
  33     // are added with new elements. Perhaps better would be to ask the
  34     // user for a batch of edges to minimize this effect, but I
  35     // already wrote the code this way. :P -nmatsakis
  36     closure: RefCell<Option<BitMatrix>>,
  37 }
  38
  39 #[derive(Clone, PartialEq, PartialOrd)]
  40 struct Index(usize);
  41
  42 #[derive(Clone, PartialEq)]
  43 struct Edge {
  44     source: Index,
  45     target: Index,
  46 }
  47
  48 impl<T: Debug + PartialEq> TransitiveRelation<T> {
  49     pub fn new() -> TransitiveRelation<T> {
  50         TransitiveRelation {
  51             elements: vec![],
  52             edges: vec![],
  53             closure: RefCell::new(None),
  54         }
  55     }
  56
  57     fn index(&self, a: &T) -> Option<Index> {
  58         self.elements.iter().position(|e| *e == *a).map(Index)
  59     }
  60
  61     fn add_index(&mut self, a: T) -> Index {
  62         match self.index(&a) {
  63             Some(i) => i,
  64             None => {
  65                 self.elements.push(a);
  66
  67                 // if we changed the dimensions, clear the cache
  68                 *self.closure.borrow_mut() = None;
  69
  70                 Index(self.elements.len() - 1)
  71             }
  72         }
  73     }
  74
  75     /// Indicate that `a < b` (where `<` is this relation)
  76     pub fn add(&mut self, a: T, b: T) {
  77         let a = self.add_index(a);
  78         let b = self.add_index(b);
  79         let edge = Edge {
  80             source: a,
  81             target: b,
  82         };
  83         if !self.edges.contains(&edge) {
  84             self.edges.push(edge);
  85
  86             // added an edge, clear the cache
  87             *self.closure.borrow_mut() = None;
  88         }
  89     }
  90
  91     /// Check whether `a < target` (transitively)
  92     pub fn contains(&self, a: &T, b: &T) -> bool {
  93         match (self.index(a), self.index(b)) {
  94             (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)),
  95             (None, _) | (_, None) => false,
  96         }
  97     }
  98
  99     /// Picks what I am referring to as the "postdominating"
 100     /// upper-bound for `a` and `b`. This is usually the least upper
 101     /// bound, but in cases where there is no single least upper
 102     /// bound, it is the "mutual immediate postdominator", if you
 103     /// imagine a graph where `a < b` means `a -> b`.
 104     ///
 105     /// This function is needed because region inference currently
 106     /// requires that we produce a single "UB", and there is no best
 107     /// choice for the LUB. Rather than pick arbitrarily, I pick a
 108     /// less good, but predictable choice. This should help ensure
 109     /// that region inference yields predictable results (though it
 110     /// itself is not fully sufficient).
 111     ///
 112     /// Examples are probably clearer than any prose I could write
 113     /// (there are corresponding tests below, btw). In each case,
 114     /// the query is `postdom_upper_bound(a, b)`:
 115     ///
 116     /// ```text
 117     /// // returns Some(x), which is also LUB
 118     /// a -> a1 -> x
 119     ///            ^
 120     ///            |
 121     /// b -> b1 ---+
 122     ///
 123     /// // returns Some(x), which is not LUB (there is none)
 124     /// // diagonal edges run left-to-right
 125     /// a -> a1 -> x
 126     ///   \/       ^
 127     ///   /\       |
 128     /// b -> b1 ---+
 129     ///
 130     /// // returns None
 131     /// a -> a1
 132     /// b -> b1
 133     /// ```
 134     pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> {
 135         let mut mubs = self.minimal_upper_bounds(a, b);
 136         loop {
 137             match mubs.len() {
 138                 0 => return None,
 139                 1 => return Some(mubs[0]),
 140                 _ => {
 141                     let m = mubs.pop().unwrap();
 142                     let n = mubs.pop().unwrap();
 143                     mubs.extend(self.minimal_upper_bounds(n, m));
 144                 }
 145             }
 146         }
 147     }
 148
 149     /// Returns the set of bounds `X` such that:
 150     ///
 151     /// - `a < X` and `b < X`
 152     /// - there is no `Y != X` such that `a < Y` and `Y < X`
 153     ///   - except for the case where `X < a` (i.e., a strongly connected
 154     ///     component in the graph). In that case, the smallest
 155     ///     representative of the SCC is returned (as determined by the
 156     ///     internal indices).
 157     ///
 158     /// Note that this set can, in principle, have any size.
 159     pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> {
 160         let (mut a, mut b) = match (self.index(a), self.index(b)) {
 161             (Some(a), Some(b)) => (a, b),
 162             (None, _) | (_, None) => {
 163                 return vec![];
 164             }
 165         };
 166
 167         // in some cases, there are some arbitrary choices to be made;
 168         // it doesn't really matter what we pick, as long as we pick
 169         // the same thing consistently when queried, so ensure that
 170         // (a, b) are in a consistent relative order
 171         if a > b {
 172             mem::swap(&mut a, &mut b);
 173         }
 174
 175         let lub_indices = self.with_closure(|closure| {
 176             // Easy case is when either a < b or b < a:
 177             if closure.contains(a.0, b.0) {
 178                 return vec![b.0];
 179             }
 180             if closure.contains(b.0, a.0) {
 181                 return vec![a.0];
 182             }
 183
 184             // Otherwise, the tricky part is that there may be some c
 185             // where a < c and b < c. In fact, there may be many such
 186             // values. So here is what we do:
 187             //
 188             // 1. Find the vector `[X | a < X && b < X]` of all values
 189             //    `X` where `a < X` and `b < X`.  In terms of the
 190             //    graph, this means all values reachable from both `a`
 191             //    and `b`. Note that this vector is also a set, but we
 192             //    use the term vector because the order matters
 193             //    to the steps below.
 194             //    - This vector contains upper bounds, but they are
 195             //      not minimal upper bounds. So you may have e.g.
 196             //      `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and
 197             //      `z < x` and `z < y`:
 198             //
 199             //           z --+---> x ----+----> tcx
 200             //               |           |
 201             //               |           |
 202             //               +---> y ----+
 203             //
 204             //      In this case, we really want to return just `[z]`.
 205             //      The following steps below achieve this by gradually
 206             //      reducing the list.
 207             // 2. Pare down the vector using `pare_down`. This will
 208             //    remove elements from the vector that can be reached
 209             //    by an earlier element.
 210             //    - In the example above, this would convert `[x, y,
 211             //      tcx, z]` to `[x, y, z]`. Note that `x` and `y` are
 212             //      still in the vector; this is because while `z < x`
 213             //      (and `z < y`) holds, `z` comes after them in the
 214             //      vector.
 215             // 3. Reverse the vector and repeat the pare down process.
 216             //    - In the example above, we would reverse to
 217             //      `[z, y, x]` and then pare down to `[z]`.
 218             // 4. Reverse once more just so that we yield a vector in
 219             //    increasing order of index. Not necessary, but why not.
 220             //
 221             // I believe this algorithm yields a minimal set. The
 222             // argument is that, after step 2, we know that no element
 223             // can reach its successors (in the vector, not the graph).
 224             // After step 3, we know that no element can reach any of
 225             // its predecesssors (because of step 2) nor successors
 226             // (because we just called `pare_down`)
 227
 228             let mut candidates = closure.intersection(a.0, b.0); // (1)
 229             pare_down(&mut candidates, closure); // (2)
 230             candidates.reverse(); // (3a)
 231             pare_down(&mut candidates, closure); // (3b)
 232             candidates
 233         });
 234
 235         lub_indices.into_iter()
 236                    .rev() // (4)
 237                    .map(|i| &self.elements[i])
 238                    .collect()
 239     }
 240
 241     fn with_closure<OP, R>(&self, op: OP) -> R
 242         where OP: FnOnce(&BitMatrix) -> R
 243     {
 244         let mut closure_cell = self.closure.borrow_mut();
 245         let mut closure = closure_cell.take();
 246         if closure.is_none() {
 247             closure = Some(self.compute_closure());
 248         }
 249         let result = op(closure.as_ref().unwrap());
 250         *closure_cell = closure;
 251         result
 252     }
 253
 254     fn compute_closure(&self) -> BitMatrix {
 255         let mut matrix = BitMatrix::new(self.elements.len(),
 256                                         self.elements.len());
 257         let mut changed = true;
 258         while changed {
 259             changed = false;
 260             for edge in self.edges.iter() {
 261                 // add an edge from S -> T
 262                 changed |= matrix.add(edge.source.0, edge.target.0);
 263
 264                 // add all outgoing edges from T into S
 265                 changed |= matrix.merge(edge.target.0, edge.source.0);
 266             }
 267         }
 268         matrix
 269     }
 270 }
 271
 272 /// Pare down is used as a step in the LUB computation. It edits the
 273 /// candidates array in place by removing any element j for which
 274 /// there exists an earlier element i<j such that i -> j. That is,
 275 /// after you run `pare_down`, you know that for all elements that
 276 /// remain in candidates, they cannot reach any of the elements that
 277 /// come after them.
 278 ///
 279 /// Examples follow. Assume that a -> b -> c and x -> y -> z.
 280 ///
 281 /// - Input: `[a, b, x]`. Output: `[a, x]`.
 282 /// - Input: `[b, a, x]`. Output: `[b, a, x]`.
 283 /// - Input: `[a, x, b, y]`. Output: `[a, x]`.
 284 fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix) {
 285     let mut i = 0;
 286     while i < candidates.len() {
 287         let candidate_i = candidates[i];
 288         i += 1;
 289
 290         let mut j = i;
 291         let mut dead = 0;
 292         while j < candidates.len() {
 293             let candidate_j = candidates[j];
 294             if closure.contains(candidate_i, candidate_j) {
 295                 // If `i` can reach `j`, then we can remove `j`. So just
 296                 // mark it as dead and move on; subsequent indices will be
 297                 // shifted into its place.
 298                 dead += 1;
 299             } else {
 300                 candidates[j - dead] = candidate_j;
 301             }
 302             j += 1;
 303         }
 304         candidates.truncate(j - dead);
 305     }
 306 }
 307
 308 #[test]
 309 fn test_one_step() {
 310     let mut relation = TransitiveRelation::new();
 311     relation.add("a", "b");
 312     relation.add("a", "c");
 313     assert!(relation.contains(&"a", &"c"));
 314     assert!(relation.contains(&"a", &"b"));
 315     assert!(!relation.contains(&"b", &"a"));
 316     assert!(!relation.contains(&"a", &"d"));
 317 }
 318
 319 #[test]
 320 fn test_many_steps() {
 321     let mut relation = TransitiveRelation::new();
 322     relation.add("a", "b");
 323     relation.add("a", "c");
 324     relation.add("a", "f");
 325
 326     relation.add("b", "c");
 327     relation.add("b", "d");
 328     relation.add("b", "e");
 329
 330     relation.add("e", "g");
 331
 332     assert!(relation.contains(&"a", &"b"));
 333     assert!(relation.contains(&"a", &"c"));
 334     assert!(relation.contains(&"a", &"d"));
 335     assert!(relation.contains(&"a", &"e"));
 336     assert!(relation.contains(&"a", &"f"));
 337     assert!(relation.contains(&"a", &"g"));
 338
 339     assert!(relation.contains(&"b", &"g"));
 340
 341     assert!(!relation.contains(&"a", &"x"));
 342     assert!(!relation.contains(&"b", &"f"));
 343 }
 344
 345 #[test]
 346 fn mubs_triange() {
 347     let mut relation = TransitiveRelation::new();
 348     relation.add("a", "tcx");
 349     relation.add("b", "tcx");
 350     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
 351 }
 352
 353 #[test]
 354 fn mubs_best_choice1() {
 355     // 0 -> 1 <- 3
 356     // |    ^    |
 357     // |    |    |
 358     // +--> 2 <--+
 359     //
 360     // mubs(0,3) = [1]
 361
 362     // This tests a particular state in the algorithm, in which we
 363     // need the second pare down call to get the right result (after
 364     // intersection, we have [1, 2], but 2 -> 1).
 365
 366     let mut relation = TransitiveRelation::new();
 367     relation.add("0", "1");
 368     relation.add("0", "2");
 369
 370     relation.add("2", "1");
 371
 372     relation.add("3", "1");
 373     relation.add("3", "2");
 374
 375     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
 376 }
 377
 378 #[test]
 379 fn mubs_best_choice2() {
 380     // 0 -> 1 <- 3
 381     // |    |    |
 382     // |    v    |
 383     // +--> 2 <--+
 384     //
 385     // mubs(0,3) = [2]
 386
 387     // Like the precedecing test, but in this case intersection is [2,
 388     // 1], and hence we rely on the first pare down call.
 389
 390     let mut relation = TransitiveRelation::new();
 391     relation.add("0", "1");
 392     relation.add("0", "2");
 393
 394     relation.add("1", "2");
 395
 396     relation.add("3", "1");
 397     relation.add("3", "2");
 398
 399     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
 400 }
 401
 402 #[test]
 403 fn mubs_no_best_choice() {
 404     // in this case, the intersection yields [1, 2], and the "pare
 405     // down" calls find nothing to remove.
 406     let mut relation = TransitiveRelation::new();
 407     relation.add("0", "1");
 408     relation.add("0", "2");
 409
 410     relation.add("3", "1");
 411     relation.add("3", "2");
 412
 413     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
 414 }
 415
 416 #[test]
 417 fn mubs_best_choice_scc() {
 418     let mut relation = TransitiveRelation::new();
 419     relation.add("0", "1");
 420     relation.add("0", "2");
 421
 422     relation.add("1", "2");
 423     relation.add("2", "1");
 424
 425     relation.add("3", "1");
 426     relation.add("3", "2");
 427
 428     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
 429 }
 430
 431 #[test]
 432 fn pdub_crisscross() {
 433     // diagonal edges run left-to-right
 434     // a -> a1 -> x
 435     //   \/       ^
 436     //   /\       |
 437     // b -> b1 ---+
 438
 439     let mut relation = TransitiveRelation::new();
 440     relation.add("a", "a1");
 441     relation.add("a", "b1");
 442     relation.add("b", "a1");
 443     relation.add("b", "b1");
 444     relation.add("a1", "x");
 445     relation.add("b1", "x");
 446
 447     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
 448                vec![&"a1", &"b1"]);
 449     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 450 }
 451
 452 #[test]
 453 fn pdub_crisscross_more() {
 454     // diagonal edges run left-to-right
 455     // a -> a1 -> a2 -> a3 -> x
 456     //   \/    \/             ^
 457     //   /\    /\             |
 458     // b -> b1 -> b2 ---------+
 459
 460     let mut relation = TransitiveRelation::new();
 461     relation.add("a", "a1");
 462     relation.add("a", "b1");
 463     relation.add("b", "a1");
 464     relation.add("b", "b1");
 465
 466     relation.add("a1", "a2");
 467     relation.add("a1", "b2");
 468     relation.add("b1", "a2");
 469     relation.add("b1", "b2");
 470
 471     relation.add("a2", "a3");
 472
 473     relation.add("a3", "x");
 474     relation.add("b2", "x");
 475
 476     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
 477                vec![&"a1", &"b1"]);
 478     assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"),
 479                vec![&"a2", &"b2"]);
 480     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 481 }
 482
 483 #[test]
 484 fn pdub_lub() {
 485     // a -> a1 -> x
 486     //            ^
 487     //            |
 488     // b -> b1 ---+
 489
 490     let mut relation = TransitiveRelation::new();
 491     relation.add("a", "a1");
 492     relation.add("b", "b1");
 493     relation.add("a1", "x");
 494     relation.add("b1", "x");
 495
 496     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
 497     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 498 }
 499
 500 #[test]
 501 fn mubs_intermediate_node_on_one_side_only() {
 502     // a -> c -> d
 503     //           ^
 504     //           |
 505     //           b
 506
 507     // "digraph { a -> c -> d; b -> d; }",
 508     let mut relation = TransitiveRelation::new();
 509     relation.add("a", "c");
 510     relation.add("c", "d");
 511     relation.add("b", "d");
 512
 513     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
 514 }
 515
 516 #[test]
 517 fn mubs_scc_1() {
 518     // +-------------+
 519     // |    +----+   |
 520     // |    v    |   |
 521     // a -> c -> d <-+
 522     //           ^
 523     //           |
 524     //           b
 525
 526     // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
 527     let mut relation = TransitiveRelation::new();
 528     relation.add("a", "c");
 529     relation.add("c", "d");
 530     relation.add("d", "c");
 531     relation.add("a", "d");
 532     relation.add("b", "d");
 533
 534     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 535 }
 536
 537 #[test]
 538 fn mubs_scc_2() {
 539     //      +----+
 540     //      v    |
 541     // a -> c -> d
 542     //      ^    ^
 543     //      |    |
 544     //      +--- b
 545
 546     // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
 547     let mut relation = TransitiveRelation::new();
 548     relation.add("a", "c");
 549     relation.add("c", "d");
 550     relation.add("d", "c");
 551     relation.add("b", "d");
 552     relation.add("b", "c");
 553
 554     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 555 }
 556
 557 #[test]
 558 fn mubs_scc_3() {
 559     //      +---------+
 560     //      v         |
 561     // a -> c -> d -> e
 562     //           ^    ^
 563     //           |    |
 564     //           b ---+
 565
 566     // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
 567     let mut relation = TransitiveRelation::new();
 568     relation.add("a", "c");
 569     relation.add("c", "d");
 570     relation.add("d", "e");
 571     relation.add("e", "c");
 572     relation.add("b", "d");
 573     relation.add("b", "e");
 574
 575     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 576 }
 577
 578 #[test]
 579 fn mubs_scc_4() {
 580     //      +---------+
 581     //      v         |
 582     // a -> c -> d -> e
 583     // |         ^    ^
 584     // +---------+    |
 585     //                |
 586     //           b ---+
 587
 588     // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
 589     let mut relation = TransitiveRelation::new();
 590     relation.add("a", "c");
 591     relation.add("c", "d");
 592     relation.add("d", "e");
 593     relation.add("e", "c");
 594     relation.add("a", "d");
 595     relation.add("b", "e");
 596
 597     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 598 }