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