compiler/rustc_data_structures/src/transitive_relation.rs

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