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