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         let mut changed = true;
 257         while changed {
 258             changed = false;
 259             for edge in self.edges.iter() {
 260                 // add an edge from S -> T
 261                 changed |= matrix.add(edge.source.0, edge.target.0);
 262
 263                 // add all outgoing edges from T into S
 264                 changed |= matrix.merge(edge.target.0, edge.source.0);
 265             }
 266         }
 267         matrix
 268     }
 269 }
 270
 271 /// Pare down is used as a step in the LUB computation. It edits the
 272 /// candidates array in place by removing any element j for which
 273 /// there exists an earlier element i<j such that i -> j. That is,
 274 /// after you run `pare_down`, you know that for all elements that
 275 /// remain in candidates, they cannot reach any of the elements that
 276 /// come after them.
 277 ///
 278 /// Examples follow. Assume that a -> b -> c and x -> y -> z.
 279 ///
 280 /// - Input: `[a, b, x]`. Output: `[a, x]`.
 281 /// - Input: `[b, a, x]`. Output: `[b, a, x]`.
 282 /// - Input: `[a, x, b, y]`. Output: `[a, x]`.
 283 fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix) {
 284     let mut i = 0;
 285     while i < candidates.len() {
 286         let candidate_i = candidates[i];
 287         i += 1;
 288
 289         let mut j = i;
 290         let mut dead = 0;
 291         while j < candidates.len() {
 292             let candidate_j = candidates[j];
 293             if closure.contains(candidate_i, candidate_j) {
 294                 // If `i` can reach `j`, then we can remove `j`. So just
 295                 // mark it as dead and move on; subsequent indices will be
 296                 // shifted into its place.
 297                 dead += 1;
 298             } else {
 299                 candidates[j - dead] = candidate_j;
 300             }
 301             j += 1;
 302         }
 303         candidates.truncate(j - dead);
 304     }
 305 }
 306
 307 #[test]
 308 fn test_one_step() {
 309     let mut relation = TransitiveRelation::new();
 310     relation.add("a", "b");
 311     relation.add("a", "c");
 312     assert!(relation.contains(&"a", &"c"));
 313     assert!(relation.contains(&"a", &"b"));
 314     assert!(!relation.contains(&"b", &"a"));
 315     assert!(!relation.contains(&"a", &"d"));
 316 }
 317
 318 #[test]
 319 fn test_many_steps() {
 320     let mut relation = TransitiveRelation::new();
 321     relation.add("a", "b");
 322     relation.add("a", "c");
 323     relation.add("a", "f");
 324
 325     relation.add("b", "c");
 326     relation.add("b", "d");
 327     relation.add("b", "e");
 328
 329     relation.add("e", "g");
 330
 331     assert!(relation.contains(&"a", &"b"));
 332     assert!(relation.contains(&"a", &"c"));
 333     assert!(relation.contains(&"a", &"d"));
 334     assert!(relation.contains(&"a", &"e"));
 335     assert!(relation.contains(&"a", &"f"));
 336     assert!(relation.contains(&"a", &"g"));
 337
 338     assert!(relation.contains(&"b", &"g"));
 339
 340     assert!(!relation.contains(&"a", &"x"));
 341     assert!(!relation.contains(&"b", &"f"));
 342 }
 343
 344 #[test]
 345 fn mubs_triange() {
 346     let mut relation = TransitiveRelation::new();
 347     relation.add("a", "tcx");
 348     relation.add("b", "tcx");
 349     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
 350 }
 351
 352 #[test]
 353 fn mubs_best_choice1() {
 354     // 0 -> 1 <- 3
 355     // |    ^    |
 356     // |    |    |
 357     // +--> 2 <--+
 358     //
 359     // mubs(0,3) = [1]
 360
 361     // This tests a particular state in the algorithm, in which we
 362     // need the second pare down call to get the right result (after
 363     // intersection, we have [1, 2], but 2 -> 1).
 364
 365     let mut relation = TransitiveRelation::new();
 366     relation.add("0", "1");
 367     relation.add("0", "2");
 368
 369     relation.add("2", "1");
 370
 371     relation.add("3", "1");
 372     relation.add("3", "2");
 373
 374     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
 375 }
 376
 377 #[test]
 378 fn mubs_best_choice2() {
 379     // 0 -> 1 <- 3
 380     // |    |    |
 381     // |    v    |
 382     // +--> 2 <--+
 383     //
 384     // mubs(0,3) = [2]
 385
 386     // Like the precedecing test, but in this case intersection is [2,
 387     // 1], and hence we rely on the first pare down call.
 388
 389     let mut relation = TransitiveRelation::new();
 390     relation.add("0", "1");
 391     relation.add("0", "2");
 392
 393     relation.add("1", "2");
 394
 395     relation.add("3", "1");
 396     relation.add("3", "2");
 397
 398     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
 399 }
 400
 401 #[test]
 402 fn mubs_no_best_choice() {
 403     // in this case, the intersection yields [1, 2], and the "pare
 404     // down" calls find nothing to remove.
 405     let mut relation = TransitiveRelation::new();
 406     relation.add("0", "1");
 407     relation.add("0", "2");
 408
 409     relation.add("3", "1");
 410     relation.add("3", "2");
 411
 412     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
 413 }
 414
 415 #[test]
 416 fn mubs_best_choice_scc() {
 417     let mut relation = TransitiveRelation::new();
 418     relation.add("0", "1");
 419     relation.add("0", "2");
 420
 421     relation.add("1", "2");
 422     relation.add("2", "1");
 423
 424     relation.add("3", "1");
 425     relation.add("3", "2");
 426
 427     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
 428 }
 429
 430 #[test]
 431 fn pdub_crisscross() {
 432     // diagonal edges run left-to-right
 433     // a -> a1 -> x
 434     //   \/       ^
 435     //   /\       |
 436     // b -> b1 ---+
 437
 438     let mut relation = TransitiveRelation::new();
 439     relation.add("a", "a1");
 440     relation.add("a", "b1");
 441     relation.add("b", "a1");
 442     relation.add("b", "b1");
 443     relation.add("a1", "x");
 444     relation.add("b1", "x");
 445
 446     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
 447                vec![&"a1", &"b1"]);
 448     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 449 }
 450
 451 #[test]
 452 fn pdub_crisscross_more() {
 453     // diagonal edges run left-to-right
 454     // a -> a1 -> a2 -> a3 -> x
 455     //   \/    \/             ^
 456     //   /\    /\             |
 457     // b -> b1 -> b2 ---------+
 458
 459     let mut relation = TransitiveRelation::new();
 460     relation.add("a", "a1");
 461     relation.add("a", "b1");
 462     relation.add("b", "a1");
 463     relation.add("b", "b1");
 464
 465     relation.add("a1", "a2");
 466     relation.add("a1", "b2");
 467     relation.add("b1", "a2");
 468     relation.add("b1", "b2");
 469
 470     relation.add("a2", "a3");
 471
 472     relation.add("a3", "x");
 473     relation.add("b2", "x");
 474
 475     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
 476                vec![&"a1", &"b1"]);
 477     assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"),
 478                vec![&"a2", &"b2"]);
 479     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 480 }
 481
 482 #[test]
 483 fn pdub_lub() {
 484     // a -> a1 -> x
 485     //            ^
 486     //            |
 487     // b -> b1 ---+
 488
 489     let mut relation = TransitiveRelation::new();
 490     relation.add("a", "a1");
 491     relation.add("b", "b1");
 492     relation.add("a1", "x");
 493     relation.add("b1", "x");
 494
 495     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
 496     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 497 }
 498
 499 #[test]
 500 fn mubs_intermediate_node_on_one_side_only() {
 501     // a -> c -> d
 502     //           ^
 503     //           |
 504     //           b
 505
 506     // "digraph { a -> c -> d; b -> d; }",
 507     let mut relation = TransitiveRelation::new();
 508     relation.add("a", "c");
 509     relation.add("c", "d");
 510     relation.add("b", "d");
 511
 512     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
 513 }
 514
 515 #[test]
 516 fn mubs_scc_1() {
 517     // +-------------+
 518     // |    +----+   |
 519     // |    v    |   |
 520     // a -> c -> d <-+
 521     //           ^
 522     //           |
 523     //           b
 524
 525     // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
 526     let mut relation = TransitiveRelation::new();
 527     relation.add("a", "c");
 528     relation.add("c", "d");
 529     relation.add("d", "c");
 530     relation.add("a", "d");
 531     relation.add("b", "d");
 532
 533     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 534 }
 535
 536 #[test]
 537 fn mubs_scc_2() {
 538     //      +----+
 539     //      v    |
 540     // a -> c -> d
 541     //      ^    ^
 542     //      |    |
 543     //      +--- b
 544
 545     // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
 546     let mut relation = TransitiveRelation::new();
 547     relation.add("a", "c");
 548     relation.add("c", "d");
 549     relation.add("d", "c");
 550     relation.add("b", "d");
 551     relation.add("b", "c");
 552
 553     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 554 }
 555
 556 #[test]
 557 fn mubs_scc_3() {
 558     //      +---------+
 559     //      v         |
 560     // a -> c -> d -> e
 561     //           ^    ^
 562     //           |    |
 563     //           b ---+
 564
 565     // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
 566     let mut relation = TransitiveRelation::new();
 567     relation.add("a", "c");
 568     relation.add("c", "d");
 569     relation.add("d", "e");
 570     relation.add("e", "c");
 571     relation.add("b", "d");
 572     relation.add("b", "e");
 573
 574     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 575 }
 576
 577 #[test]
 578 fn mubs_scc_4() {
 579     //      +---------+
 580     //      v         |
 581     // a -> c -> d -> e
 582     // |         ^    ^
 583     // +---------+    |
 584     //                |
 585     //           b ---+
 586
 587     // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
 588     let mut relation = TransitiveRelation::new();
 589     relation.add("a", "c");
 590     relation.add("c", "d");
 591     relation.add("d", "e");
 592     relation.add("e", "c");
 593     relation.add("a", "d");
 594     relation.add("b", "e");
 595
 596     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 597 }