src/librustc_data_structures/transitive_relation.rs

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