src/librustc_data_structures/transitive_relation.rs

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