src/librustc_data_structures/transitive_relation.rs

   1 use crate::fx::FxHashMap;
   2 use crate::stable_hasher::{HashStable, StableHasher};
   3 use crate::sync::Lock;
   4 use rustc_index::bit_set::BitMatrix;
   5 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
   6 use std::fmt::Debug;
   7 use std::hash::Hash;
   8 use std::mem;
   9
  10 #[cfg(test)]
  11 mod tests;
  12
  13 #[derive(Clone, Debug)]
  14 pub struct TransitiveRelation<T: Eq + Hash> {
  15     // List of elements. This is used to map from a T to a usize.
  16     elements: Vec<T>,
  17
  18     // Maps each element to an index.
  19     map: FxHashMap<T, Index>,
  20
  21     // List of base edges in the graph. Require to compute transitive
  22     // closure.
  23     edges: Vec<Edge>,
  24
  25     // This is a cached transitive closure derived from the edges.
  26     // Currently, we build it lazilly and just throw out any existing
  27     // copy whenever a new edge is added. (The Lock is to permit
  28     // the lazy computation.) This is kind of silly, except for the
  29     // fact its size is tied to `self.elements.len()`, so I wanted to
  30     // wait before building it up to avoid reallocating as new edges
  31     // are added with new elements. Perhaps better would be to ask the
  32     // user for a batch of edges to minimize this effect, but I
  33     // already wrote the code this way. :P -nmatsakis
  34     closure: Lock<Option<BitMatrix<usize, usize>>>,
  35 }
  36
  37 // HACK(eddyb) manual impl avoids `Default` bound on `T`.
  38 impl<T: Eq + Hash> Default for TransitiveRelation<T> {
  39     fn default() -> Self {
  40         TransitiveRelation {
  41             elements: Default::default(),
  42             map: Default::default(),
  43             edges: Default::default(),
  44             closure: Default::default(),
  45         }
  46     }
  47 }
  48
  49 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, RustcEncodable, RustcDecodable, Debug)]
  50 struct Index(usize);
  51
  52 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
  53 struct Edge {
  54     source: Index,
  55     target: Index,
  56 }
  57
  58 impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
  59     pub fn is_empty(&self) -> bool {
  60         self.edges.is_empty()
  61     }
  62
  63     pub fn elements(&self) -> impl Iterator<Item = &T> {
  64         self.elements.iter()
  65     }
  66
  67     fn index(&self, a: &T) -> Option<Index> {
  68         self.map.get(a).cloned()
  69     }
  70
  71     fn add_index(&mut self, a: T) -> Index {
  72         let &mut TransitiveRelation { ref mut elements, ref mut closure, ref mut map, .. } = self;
  73
  74         *map.entry(a.clone()).or_insert_with(|| {
  75             elements.push(a);
  76
  77             // if we changed the dimensions, clear the cache
  78             *closure.get_mut() = None;
  79
  80             Index(elements.len() - 1)
  81         })
  82     }
  83
  84     /// Applies the (partial) function to each edge and returns a new
  85     /// relation. If `f` returns `None` for any end-point, returns
  86     /// `None`.
  87     pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>>
  88     where
  89         F: FnMut(&T) -> Option<U>,
  90         U: Clone + Debug + Eq + Hash + Clone,
  91     {
  92         let mut result = TransitiveRelation::default();
  93         for edge in &self.edges {
  94             result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?);
  95         }
  96         Some(result)
  97     }
  98
  99     /// Indicate that `a < b` (where `<` is this relation)
 100     pub fn add(&mut self, a: T, b: T) {
 101         let a = self.add_index(a);
 102         let b = self.add_index(b);
 103         let edge = Edge { source: a, target: b };
 104         if !self.edges.contains(&edge) {
 105             self.edges.push(edge);
 106
 107             // added an edge, clear the cache
 108             *self.closure.get_mut() = None;
 109         }
 110     }
 111
 112     /// Checks whether `a < target` (transitively)
 113     pub fn contains(&self, a: &T, b: &T) -> bool {
 114         match (self.index(a), self.index(b)) {
 115             (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)),
 116             (None, _) | (_, None) => false,
 117         }
 118     }
 119
 120     /// Thinking of `x R y` as an edge `x -> y` in a graph, this
 121     /// returns all things reachable from `a`.
 122     ///
 123     /// Really this probably ought to be `impl Iterator<Item = &T>`, but
 124     /// I'm too lazy to make that work, and -- given the caching
 125     /// strategy -- it'd be a touch tricky anyhow.
 126     pub fn reachable_from(&self, a: &T) -> Vec<&T> {
 127         match self.index(a) {
 128             Some(a) => {
 129                 self.with_closure(|closure| closure.iter(a.0).map(|i| &self.elements[i]).collect())
 130             }
 131             None => vec![],
 132         }
 133     }
 134
 135     /// Picks what I am referring to as the "postdominating"
 136     /// upper-bound for `a` and `b`. This is usually the least upper
 137     /// bound, but in cases where there is no single least upper
 138     /// bound, it is the "mutual immediate postdominator", if you
 139     /// imagine a graph where `a < b` means `a -> b`.
 140     ///
 141     /// This function is needed because region inference currently
 142     /// requires that we produce a single "UB", and there is no best
 143     /// choice for the LUB. Rather than pick arbitrarily, I pick a
 144     /// less good, but predictable choice. This should help ensure
 145     /// that region inference yields predictable results (though it
 146     /// itself is not fully sufficient).
 147     ///
 148     /// Examples are probably clearer than any prose I could write
 149     /// (there are corresponding tests below, btw). In each case,
 150     /// the query is `postdom_upper_bound(a, b)`:
 151     ///
 152     /// ```text
 153     /// // Returns Some(x), which is also LUB.
 154     /// a -> a1 -> x
 155     ///            ^
 156     ///            |
 157     /// b -> b1 ---+
 158     ///
 159     /// // Returns `Some(x)`, which is not LUB (there is none)
 160     /// // diagonal edges run left-to-right.
 161     /// a -> a1 -> x
 162     ///   \/       ^
 163     ///   /\       |
 164     /// b -> b1 ---+
 165     ///
 166     /// // Returns `None`.
 167     /// a -> a1
 168     /// b -> b1
 169     /// ```
 170     pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> {
 171         let mubs = self.minimal_upper_bounds(a, b);
 172         self.mutual_immediate_postdominator(mubs)
 173     }
 174
 175     /// Viewing the relation as a graph, computes the "mutual
 176     /// immediate postdominator" of a set of points (if one
 177     /// exists). See `postdom_upper_bound` for details.
 178     pub fn mutual_immediate_postdominator<'a>(&'a self, mut mubs: Vec<&'a T>) -> Option<&'a T> {
 179         loop {
 180             match mubs.len() {
 181                 0 => return None,
 182                 1 => return Some(mubs[0]),
 183                 _ => {
 184                     let m = mubs.pop().unwrap();
 185                     let n = mubs.pop().unwrap();
 186                     mubs.extend(self.minimal_upper_bounds(n, m));
 187                 }
 188             }
 189         }
 190     }
 191
 192     /// Returns the set of bounds `X` such that:
 193     ///
 194     /// - `a < X` and `b < X`
 195     /// - there is no `Y != X` such that `a < Y` and `Y < X`
 196     ///   - except for the case where `X < a` (i.e., a strongly connected
 197     ///     component in the graph). In that case, the smallest
 198     ///     representative of the SCC is returned (as determined by the
 199     ///     internal indices).
 200     ///
 201     /// Note that this set can, in principle, have any size.
 202     pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> {
 203         let (mut a, mut b) = match (self.index(a), self.index(b)) {
 204             (Some(a), Some(b)) => (a, b),
 205             (None, _) | (_, None) => {
 206                 return vec![];
 207             }
 208         };
 209
 210         // in some cases, there are some arbitrary choices to be made;
 211         // it doesn't really matter what we pick, as long as we pick
 212         // the same thing consistently when queried, so ensure that
 213         // (a, b) are in a consistent relative order
 214         if a > b {
 215             mem::swap(&mut a, &mut b);
 216         }
 217
 218         let lub_indices = self.with_closure(|closure| {
 219             // Easy case is when either a < b or b < a:
 220             if closure.contains(a.0, b.0) {
 221                 return vec![b.0];
 222             }
 223             if closure.contains(b.0, a.0) {
 224                 return vec![a.0];
 225             }
 226
 227             // Otherwise, the tricky part is that there may be some c
 228             // where a < c and b < c. In fact, there may be many such
 229             // values. So here is what we do:
 230             //
 231             // 1. Find the vector `[X | a < X && b < X]` of all values
 232             //    `X` where `a < X` and `b < X`.  In terms of the
 233             //    graph, this means all values reachable from both `a`
 234             //    and `b`. Note that this vector is also a set, but we
 235             //    use the term vector because the order matters
 236             //    to the steps below.
 237             //    - This vector contains upper bounds, but they are
 238             //      not minimal upper bounds. So you may have e.g.
 239             //      `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and
 240             //      `z < x` and `z < y`:
 241             //
 242             //           z --+---> x ----+----> tcx
 243             //               |           |
 244             //               |           |
 245             //               +---> y ----+
 246             //
 247             //      In this case, we really want to return just `[z]`.
 248             //      The following steps below achieve this by gradually
 249             //      reducing the list.
 250             // 2. Pare down the vector using `pare_down`. This will
 251             //    remove elements from the vector that can be reached
 252             //    by an earlier element.
 253             //    - In the example above, this would convert `[x, y,
 254             //      tcx, z]` to `[x, y, z]`. Note that `x` and `y` are
 255             //      still in the vector; this is because while `z < x`
 256             //      (and `z < y`) holds, `z` comes after them in the
 257             //      vector.
 258             // 3. Reverse the vector and repeat the pare down process.
 259             //    - In the example above, we would reverse to
 260             //      `[z, y, x]` and then pare down to `[z]`.
 261             // 4. Reverse once more just so that we yield a vector in
 262             //    increasing order of index. Not necessary, but why not.
 263             //
 264             // I believe this algorithm yields a minimal set. The
 265             // argument is that, after step 2, we know that no element
 266             // can reach its successors (in the vector, not the graph).
 267             // After step 3, we know that no element can reach any of
 268             // its predecesssors (because of step 2) nor successors
 269             // (because we just called `pare_down`)
 270             //
 271             // This same algorithm is used in `parents` below.
 272
 273             let mut candidates = closure.intersect_rows(a.0, b.0); // (1)
 274             pare_down(&mut candidates, closure); // (2)
 275             candidates.reverse(); // (3a)
 276             pare_down(&mut candidates, closure); // (3b)
 277             candidates
 278         });
 279
 280         lub_indices
 281             .into_iter()
 282             .rev() // (4)
 283             .map(|i| &self.elements[i])
 284             .collect()
 285     }
 286
 287     /// Given an element A, returns the maximal set {B} of elements B
 288     /// such that
 289     ///
 290     /// - A != B
 291     /// - A R B is true
 292     /// - for each i, j: B[i] R B[j] does not hold
 293     ///
 294     /// The intuition is that this moves "one step up" through a lattice
 295     /// (where the relation is encoding the `<=` relation for the lattice).
 296     /// So e.g., if the relation is `->` and we have
 297     ///
 298     /// ```
 299     /// a -> b -> d -> f
 300     /// |              ^
 301     /// +--> c -> e ---+
 302     /// ```
 303     ///
 304     /// then `parents(a)` returns `[b, c]`. The `postdom_parent` function
 305     /// would further reduce this to just `f`.
 306     pub fn parents(&self, a: &T) -> Vec<&T> {
 307         let a = match self.index(a) {
 308             Some(a) => a,
 309             None => return vec![],
 310         };
 311
 312         // Steal the algorithm for `minimal_upper_bounds` above, but
 313         // with a slight tweak. In the case where `a R a`, we remove
 314         // that from the set of candidates.
 315         let ancestors = self.with_closure(|closure| {
 316             let mut ancestors = closure.intersect_rows(a.0, a.0);
 317
 318             // Remove anything that can reach `a`. If this is a
 319             // reflexive relation, this will include `a` itself.
 320             ancestors.retain(|&e| !closure.contains(e, a.0));
 321
 322             pare_down(&mut ancestors, closure); // (2)
 323             ancestors.reverse(); // (3a)
 324             pare_down(&mut ancestors, closure); // (3b)
 325             ancestors
 326         });
 327
 328         ancestors
 329             .into_iter()
 330             .rev() // (4)
 331             .map(|i| &self.elements[i])
 332             .collect()
 333     }
 334
 335     /// A "best" parent in some sense. See `parents` and
 336     /// `postdom_upper_bound` for more details.
 337     pub fn postdom_parent(&self, a: &T) -> Option<&T> {
 338         self.mutual_immediate_postdominator(self.parents(a))
 339     }
 340
 341     fn with_closure<OP, R>(&self, op: OP) -> R
 342     where
 343         OP: FnOnce(&BitMatrix<usize, usize>) -> R,
 344     {
 345         let mut closure_cell = self.closure.borrow_mut();
 346         let mut closure = closure_cell.take();
 347         if closure.is_none() {
 348             closure = Some(self.compute_closure());
 349         }
 350         let result = op(closure.as_ref().unwrap());
 351         *closure_cell = closure;
 352         result
 353     }
 354
 355     fn compute_closure(&self) -> BitMatrix<usize, usize> {
 356         let mut matrix = BitMatrix::new(self.elements.len(), self.elements.len());
 357         let mut changed = true;
 358         while changed {
 359             changed = false;
 360             for edge in &self.edges {
 361                 // add an edge from S -> T
 362                 changed |= matrix.insert(edge.source.0, edge.target.0);
 363
 364                 // add all outgoing edges from T into S
 365                 changed |= matrix.union_rows(edge.target.0, edge.source.0);
 366             }
 367         }
 368         matrix
 369     }
 370
 371     /// Lists all the base edges in the graph: the initial _non-transitive_ set of element
 372     /// relations, which will be later used as the basis for the transitive closure computation.
 373     pub fn base_edges(&self) -> impl Iterator<Item = (&T, &T)> {
 374         self.edges
 375             .iter()
 376             .map(move |edge| (&self.elements[edge.source.0], &self.elements[edge.target.0]))
 377     }
 378 }
 379
 380 /// Pare down is used as a step in the LUB computation. It edits the
 381 /// candidates array in place by removing any element j for which
 382 /// there exists an earlier element i<j such that i -> j. That is,
 383 /// after you run `pare_down`, you know that for all elements that
 384 /// remain in candidates, they cannot reach any of the elements that
 385 /// come after them.
 386 ///
 387 /// Examples follow. Assume that a -> b -> c and x -> y -> z.
 388 ///
 389 /// - Input: `[a, b, x]`. Output: `[a, x]`.
 390 /// - Input: `[b, a, x]`. Output: `[b, a, x]`.
 391 /// - Input: `[a, x, b, y]`. Output: `[a, x]`.
 392 fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) {
 393     let mut i = 0;
 394     while i < candidates.len() {
 395         let candidate_i = candidates[i];
 396         i += 1;
 397
 398         let mut j = i;
 399         let mut dead = 0;
 400         while j < candidates.len() {
 401             let candidate_j = candidates[j];
 402             if closure.contains(candidate_i, candidate_j) {
 403                 // If `i` can reach `j`, then we can remove `j`. So just
 404                 // mark it as dead and move on; subsequent indices will be
 405                 // shifted into its place.
 406                 dead += 1;
 407             } else {
 408                 candidates[j - dead] = candidate_j;
 409             }
 410             j += 1;
 411         }
 412         candidates.truncate(j - dead);
 413     }
 414 }
 415
 416 impl<T> Encodable for TransitiveRelation<T>
 417 where
 418     T: Clone + Encodable + Debug + Eq + Hash + Clone,
 419 {
 420     fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> {
 421         s.emit_struct("TransitiveRelation", 2, |s| {
 422             s.emit_struct_field("elements", 0, |s| self.elements.encode(s))?;
 423             s.emit_struct_field("edges", 1, |s| self.edges.encode(s))?;
 424             Ok(())
 425         })
 426     }
 427 }
 428
 429 impl<T> Decodable for TransitiveRelation<T>
 430 where
 431     T: Clone + Decodable + Debug + Eq + Hash + Clone,
 432 {
 433     fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> {
 434         d.read_struct("TransitiveRelation", 2, |d| {
 435             let elements: Vec<T> = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?;
 436             let edges = d.read_struct_field("edges", 1, |d| Decodable::decode(d))?;
 437             let map = elements
 438                 .iter()
 439                 .enumerate()
 440                 .map(|(index, elem)| (elem.clone(), Index(index)))
 441                 .collect();
 442             Ok(TransitiveRelation { elements, edges, map, closure: Lock::new(None) })
 443         })
 444     }
 445 }
 446
 447 impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
 448 where
 449     T: HashStable<CTX> + Eq + Debug + Clone + Hash,
 450 {
 451     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 452         // We are assuming here that the relation graph has been built in a
 453         // deterministic way and we can just hash it the way it is.
 454         let TransitiveRelation {
 455             ref elements,
 456             ref edges,
 457             // "map" is just a copy of elements vec
 458             map: _,
 459             // "closure" is just a copy of the data above
 460             closure: _,
 461         } = *self;
 462
 463         elements.hash_stable(hcx, hasher);
 464         edges.hash_stable(hcx, hasher);
 465     }
 466 }
 467
 468 impl<CTX> HashStable<CTX> for Edge {
 469     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 470         let Edge { ref source, ref target } = *self;
 471
 472         source.hash_stable(hcx, hasher);
 473         target.hash_stable(hcx, hasher);
 474     }
 475 }
 476
 477 impl<CTX> HashStable<CTX> for Index {
 478     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 479         let Index(idx) = *self;
 480         idx.hash_stable(hcx, hasher);
 481     }
 482 }