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