| use bit_set::BitMatrix; |
| use fx::FxHashMap; |
| use sync::Lock; |
| use rustc_serialize::{Encodable, Encoder, Decodable, Decoder}; |
| use stable_hasher::{HashStable, StableHasher, StableHasherResult}; |
| use std::fmt::Debug; |
| use std::hash::Hash; |
| use std::mem; |
| |
| |
| #[derive(Clone, Debug)] |
| pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash> { |
| // List of elements. This is used to map from a T to a usize. |
| elements: Vec<T>, |
| |
| // Maps each element to an index. |
| map: FxHashMap<T, Index>, |
| |
| // List of base edges in the graph. Require to compute transitive |
| // closure. |
| edges: Vec<Edge>, |
| |
| // This is a cached transitive closure derived from the edges. |
| // Currently, we build it lazilly and just throw out any existing |
| // copy whenever a new edge is added. (The Lock is to permit |
| // the lazy computation.) This is kind of silly, except for the |
| // fact its size is tied to `self.elements.len()`, so I wanted to |
| // wait before building it up to avoid reallocating as new edges |
| // are added with new elements. Perhaps better would be to ask the |
| // user for a batch of edges to minimize this effect, but I |
| // already wrote the code this way. :P -nmatsakis |
| closure: Lock<Option<BitMatrix<usize, usize>>>, |
| } |
| |
| // HACK(eddyb) manual impl avoids `Default` bound on `T`. |
| impl<T: Clone + Debug + Eq + Hash> Default for TransitiveRelation<T> { |
| fn default() -> Self { |
| TransitiveRelation { |
| elements: Default::default(), |
| map: Default::default(), |
| edges: Default::default(), |
| closure: Default::default(), |
| } |
| } |
| } |
| |
| #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable, Debug)] |
| struct Index(usize); |
| |
| #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)] |
| struct Edge { |
| source: Index, |
| target: Index, |
| } |
| |
| impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> { |
| pub fn is_empty(&self) -> bool { |
| self.edges.is_empty() |
| } |
| |
| fn index(&self, a: &T) -> Option<Index> { |
| self.map.get(a).cloned() |
| } |
| |
| fn add_index(&mut self, a: T) -> Index { |
| let &mut TransitiveRelation { |
| ref mut elements, |
| ref mut closure, |
| ref mut map, |
| .. |
| } = self; |
| |
| *map.entry(a.clone()) |
| .or_insert_with(|| { |
| elements.push(a); |
| |
| // if we changed the dimensions, clear the cache |
| *closure.get_mut() = None; |
| |
| Index(elements.len() - 1) |
| }) |
| } |
| |
| /// Applies the (partial) function to each edge and returns a new |
| /// relation. If `f` returns `None` for any end-point, returns |
| /// `None`. |
| pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>> |
| where F: FnMut(&T) -> Option<U>, |
| U: Clone + Debug + Eq + Hash + Clone, |
| { |
| let mut result = TransitiveRelation::default(); |
| for edge in &self.edges { |
| result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?); |
| } |
| Some(result) |
| } |
| |
| /// Indicate that `a < b` (where `<` is this relation) |
| pub fn add(&mut self, a: T, b: T) { |
| let a = self.add_index(a); |
| let b = self.add_index(b); |
| let edge = Edge { |
| source: a, |
| target: b, |
| }; |
| if !self.edges.contains(&edge) { |
| self.edges.push(edge); |
| |
| // added an edge, clear the cache |
| *self.closure.get_mut() = None; |
| } |
| } |
| |
| /// Check whether `a < target` (transitively) |
| pub fn contains(&self, a: &T, b: &T) -> bool { |
| match (self.index(a), self.index(b)) { |
| (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)), |
| (None, _) | (_, None) => false, |
| } |
| } |
| |
| /// Thinking of `x R y` as an edge `x -> y` in a graph, this |
| /// returns all things reachable from `a`. |
| /// |
| /// Really this probably ought to be `impl Iterator<Item=&T>`, but |
| /// I'm too lazy to make that work, and -- given the caching |
| /// strategy -- it'd be a touch tricky anyhow. |
| pub fn reachable_from(&self, a: &T) -> Vec<&T> { |
| match self.index(a) { |
| Some(a) => self.with_closure(|closure| { |
| closure.iter(a.0).map(|i| &self.elements[i]).collect() |
| }), |
| None => vec![], |
| } |
| } |
| |
| /// Picks what I am referring to as the "postdominating" |
| /// upper-bound for `a` and `b`. This is usually the least upper |
| /// bound, but in cases where there is no single least upper |
| /// bound, it is the "mutual immediate postdominator", if you |
| /// imagine a graph where `a < b` means `a -> b`. |
| /// |
| /// This function is needed because region inference currently |
| /// requires that we produce a single "UB", and there is no best |
| /// choice for the LUB. Rather than pick arbitrarily, I pick a |
| /// less good, but predictable choice. This should help ensure |
| /// that region inference yields predictable results (though it |
| /// itself is not fully sufficient). |
| /// |
| /// Examples are probably clearer than any prose I could write |
| /// (there are corresponding tests below, btw). In each case, |
| /// the query is `postdom_upper_bound(a, b)`: |
| /// |
| /// ```text |
| /// // returns Some(x), which is also LUB |
| /// a -> a1 -> x |
| /// ^ |
| /// | |
| /// b -> b1 ---+ |
| /// |
| /// // returns Some(x), which is not LUB (there is none) |
| /// // diagonal edges run left-to-right |
| /// a -> a1 -> x |
| /// \/ ^ |
| /// /\ | |
| /// b -> b1 ---+ |
| /// |
| /// // returns None |
| /// a -> a1 |
| /// b -> b1 |
| /// ``` |
| pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> { |
| let mubs = self.minimal_upper_bounds(a, b); |
| self.mutual_immediate_postdominator(mubs) |
| } |
| |
| /// Viewing the relation as a graph, computes the "mutual |
| /// immediate postdominator" of a set of points (if one |
| /// exists). See `postdom_upper_bound` for details. |
| pub fn mutual_immediate_postdominator<'a>(&'a self, mut mubs: Vec<&'a T>) -> Option<&'a T> { |
| loop { |
| match mubs.len() { |
| 0 => return None, |
| 1 => return Some(mubs[0]), |
| _ => { |
| let m = mubs.pop().unwrap(); |
| let n = mubs.pop().unwrap(); |
| mubs.extend(self.minimal_upper_bounds(n, m)); |
| } |
| } |
| } |
| } |
| |
| /// Returns the set of bounds `X` such that: |
| /// |
| /// - `a < X` and `b < X` |
| /// - there is no `Y != X` such that `a < Y` and `Y < X` |
| /// - except for the case where `X < a` (i.e., a strongly connected |
| /// component in the graph). In that case, the smallest |
| /// representative of the SCC is returned (as determined by the |
| /// internal indices). |
| /// |
| /// Note that this set can, in principle, have any size. |
| pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> { |
| let (mut a, mut b) = match (self.index(a), self.index(b)) { |
| (Some(a), Some(b)) => (a, b), |
| (None, _) | (_, None) => { |
| return vec![]; |
| } |
| }; |
| |
| // in some cases, there are some arbitrary choices to be made; |
| // it doesn't really matter what we pick, as long as we pick |
| // the same thing consistently when queried, so ensure that |
| // (a, b) are in a consistent relative order |
| if a > b { |
| mem::swap(&mut a, &mut b); |
| } |
| |
| let lub_indices = self.with_closure(|closure| { |
| // Easy case is when either a < b or b < a: |
| if closure.contains(a.0, b.0) { |
| return vec![b.0]; |
| } |
| if closure.contains(b.0, a.0) { |
| return vec![a.0]; |
| } |
| |
| // Otherwise, the tricky part is that there may be some c |
| // where a < c and b < c. In fact, there may be many such |
| // values. So here is what we do: |
| // |
| // 1. Find the vector `[X | a < X && b < X]` of all values |
| // `X` where `a < X` and `b < X`. In terms of the |
| // graph, this means all values reachable from both `a` |
| // and `b`. Note that this vector is also a set, but we |
| // use the term vector because the order matters |
| // to the steps below. |
| // - This vector contains upper bounds, but they are |
| // not minimal upper bounds. So you may have e.g. |
| // `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and |
| // `z < x` and `z < y`: |
| // |
| // z --+---> x ----+----> tcx |
| // | | |
| // | | |
| // +---> y ----+ |
| // |
| // In this case, we really want to return just `[z]`. |
| // The following steps below achieve this by gradually |
| // reducing the list. |
| // 2. Pare down the vector using `pare_down`. This will |
| // remove elements from the vector that can be reached |
| // by an earlier element. |
| // - In the example above, this would convert `[x, y, |
| // tcx, z]` to `[x, y, z]`. Note that `x` and `y` are |
| // still in the vector; this is because while `z < x` |
| // (and `z < y`) holds, `z` comes after them in the |
| // vector. |
| // 3. Reverse the vector and repeat the pare down process. |
| // - In the example above, we would reverse to |
| // `[z, y, x]` and then pare down to `[z]`. |
| // 4. Reverse once more just so that we yield a vector in |
| // increasing order of index. Not necessary, but why not. |
| // |
| // I believe this algorithm yields a minimal set. The |
| // argument is that, after step 2, we know that no element |
| // can reach its successors (in the vector, not the graph). |
| // After step 3, we know that no element can reach any of |
| // its predecesssors (because of step 2) nor successors |
| // (because we just called `pare_down`) |
| // |
| // This same algorithm is used in `parents` below. |
| |
| let mut candidates = closure.intersect_rows(a.0, b.0); // (1) |
| pare_down(&mut candidates, closure); // (2) |
| candidates.reverse(); // (3a) |
| pare_down(&mut candidates, closure); // (3b) |
| candidates |
| }); |
| |
| lub_indices.into_iter() |
| .rev() // (4) |
| .map(|i| &self.elements[i]) |
| .collect() |
| } |
| |
| /// Given an element A, returns the maximal set {B} of elements B |
| /// such that |
| /// |
| /// - A != B |
| /// - A R B is true |
| /// - for each i, j: B[i] R B[j] does not hold |
| /// |
| /// The intuition is that this moves "one step up" through a lattice |
| /// (where the relation is encoding the `<=` relation for the lattice). |
| /// So e.g., if the relation is `->` and we have |
| /// |
| /// ``` |
| /// a -> b -> d -> f |
| /// | ^ |
| /// +--> c -> e ---+ |
| /// ``` |
| /// |
| /// then `parents(a)` returns `[b, c]`. The `postdom_parent` function |
| /// would further reduce this to just `f`. |
| pub fn parents(&self, a: &T) -> Vec<&T> { |
| let a = match self.index(a) { |
| Some(a) => a, |
| None => return vec![] |
| }; |
| |
| // Steal the algorithm for `minimal_upper_bounds` above, but |
| // with a slight tweak. In the case where `a R a`, we remove |
| // that from the set of candidates. |
| let ancestors = self.with_closure(|closure| { |
| let mut ancestors = closure.intersect_rows(a.0, a.0); |
| |
| // Remove anything that can reach `a`. If this is a |
| // reflexive relation, this will include `a` itself. |
| ancestors.retain(|&e| !closure.contains(e, a.0)); |
| |
| pare_down(&mut ancestors, closure); // (2) |
| ancestors.reverse(); // (3a) |
| pare_down(&mut ancestors, closure); // (3b) |
| ancestors |
| }); |
| |
| ancestors.into_iter() |
| .rev() // (4) |
| .map(|i| &self.elements[i]) |
| .collect() |
| } |
| |
| /// A "best" parent in some sense. See `parents` and |
| /// `postdom_upper_bound` for more details. |
| pub fn postdom_parent(&self, a: &T) -> Option<&T> { |
| self.mutual_immediate_postdominator(self.parents(a)) |
| } |
| |
| fn with_closure<OP, R>(&self, op: OP) -> R |
| where OP: FnOnce(&BitMatrix<usize, usize>) -> R |
| { |
| let mut closure_cell = self.closure.borrow_mut(); |
| let mut closure = closure_cell.take(); |
| if closure.is_none() { |
| closure = Some(self.compute_closure()); |
| } |
| let result = op(closure.as_ref().unwrap()); |
| *closure_cell = closure; |
| result |
| } |
| |
| fn compute_closure(&self) -> BitMatrix<usize, usize> { |
| let mut matrix = BitMatrix::new(self.elements.len(), |
| self.elements.len()); |
| let mut changed = true; |
| while changed { |
| changed = false; |
| for edge in &self.edges { |
| // add an edge from S -> T |
| changed |= matrix.insert(edge.source.0, edge.target.0); |
| |
| // add all outgoing edges from T into S |
| changed |= matrix.union_rows(edge.target.0, edge.source.0); |
| } |
| } |
| matrix |
| } |
| } |
| |
| /// Pare down is used as a step in the LUB computation. It edits the |
| /// candidates array in place by removing any element j for which |
| /// there exists an earlier element i<j such that i -> j. That is, |
| /// after you run `pare_down`, you know that for all elements that |
| /// remain in candidates, they cannot reach any of the elements that |
| /// come after them. |
| /// |
| /// Examples follow. Assume that a -> b -> c and x -> y -> z. |
| /// |
| /// - Input: `[a, b, x]`. Output: `[a, x]`. |
| /// - Input: `[b, a, x]`. Output: `[b, a, x]`. |
| /// - Input: `[a, x, b, y]`. Output: `[a, x]`. |
| fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) { |
| let mut i = 0; |
| while i < candidates.len() { |
| let candidate_i = candidates[i]; |
| i += 1; |
| |
| let mut j = i; |
| let mut dead = 0; |
| while j < candidates.len() { |
| let candidate_j = candidates[j]; |
| if closure.contains(candidate_i, candidate_j) { |
| // If `i` can reach `j`, then we can remove `j`. So just |
| // mark it as dead and move on; subsequent indices will be |
| // shifted into its place. |
| dead += 1; |
| } else { |
| candidates[j - dead] = candidate_j; |
| } |
| j += 1; |
| } |
| candidates.truncate(j - dead); |
| } |
| } |
| |
| impl<T> Encodable for TransitiveRelation<T> |
| where T: Clone + Encodable + Debug + Eq + Hash + Clone |
| { |
| fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> { |
| s.emit_struct("TransitiveRelation", 2, |s| { |
| s.emit_struct_field("elements", 0, |s| self.elements.encode(s))?; |
| s.emit_struct_field("edges", 1, |s| self.edges.encode(s))?; |
| Ok(()) |
| }) |
| } |
| } |
| |
| impl<T> Decodable for TransitiveRelation<T> |
| where T: Clone + Decodable + Debug + Eq + Hash + Clone |
| { |
| fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> { |
| d.read_struct("TransitiveRelation", 2, |d| { |
| let elements: Vec<T> = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?; |
| let edges = d.read_struct_field("edges", 1, |d| Decodable::decode(d))?; |
| let map = elements.iter() |
| .enumerate() |
| .map(|(index, elem)| (elem.clone(), Index(index))) |
| .collect(); |
| Ok(TransitiveRelation { elements, edges, map, closure: Lock::new(None) }) |
| }) |
| } |
| } |
| |
| impl<CTX, T> HashStable<CTX> for TransitiveRelation<T> |
| where T: HashStable<CTX> + Eq + Debug + Clone + Hash |
| { |
| fn hash_stable<W: StableHasherResult>(&self, |
| hcx: &mut CTX, |
| hasher: &mut StableHasher<W>) { |
| // We are assuming here that the relation graph has been built in a |
| // deterministic way and we can just hash it the way it is. |
| let TransitiveRelation { |
| ref elements, |
| ref edges, |
| // "map" is just a copy of elements vec |
| map: _, |
| // "closure" is just a copy of the data above |
| closure: _ |
| } = *self; |
| |
| elements.hash_stable(hcx, hasher); |
| edges.hash_stable(hcx, hasher); |
| } |
| } |
| |
| impl<CTX> HashStable<CTX> for Edge { |
| fn hash_stable<W: StableHasherResult>(&self, |
| hcx: &mut CTX, |
| hasher: &mut StableHasher<W>) { |
| let Edge { |
| ref source, |
| ref target, |
| } = *self; |
| |
| source.hash_stable(hcx, hasher); |
| target.hash_stable(hcx, hasher); |
| } |
| } |
| |
| impl<CTX> HashStable<CTX> for Index { |
| fn hash_stable<W: StableHasherResult>(&self, |
| hcx: &mut CTX, |
| hasher: &mut StableHasher<W>) { |
| let Index(idx) = *self; |
| idx.hash_stable(hcx, hasher); |
| } |
| } |
| |
| #[test] |
| fn test_one_step() { |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "b"); |
| relation.add("a", "c"); |
| assert!(relation.contains(&"a", &"c")); |
| assert!(relation.contains(&"a", &"b")); |
| assert!(!relation.contains(&"b", &"a")); |
| assert!(!relation.contains(&"a", &"d")); |
| } |
| |
| #[test] |
| fn test_many_steps() { |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "b"); |
| relation.add("a", "c"); |
| relation.add("a", "f"); |
| |
| relation.add("b", "c"); |
| relation.add("b", "d"); |
| relation.add("b", "e"); |
| |
| relation.add("e", "g"); |
| |
| assert!(relation.contains(&"a", &"b")); |
| assert!(relation.contains(&"a", &"c")); |
| assert!(relation.contains(&"a", &"d")); |
| assert!(relation.contains(&"a", &"e")); |
| assert!(relation.contains(&"a", &"f")); |
| assert!(relation.contains(&"a", &"g")); |
| |
| assert!(relation.contains(&"b", &"g")); |
| |
| assert!(!relation.contains(&"a", &"x")); |
| assert!(!relation.contains(&"b", &"f")); |
| } |
| |
| #[test] |
| fn mubs_triangle() { |
| // a -> tcx |
| // ^ |
| // | |
| // b |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "tcx"); |
| relation.add("b", "tcx"); |
| assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]); |
| assert_eq!(relation.parents(&"a"), vec![&"tcx"]); |
| assert_eq!(relation.parents(&"b"), vec![&"tcx"]); |
| } |
| |
| #[test] |
| fn mubs_best_choice1() { |
| // 0 -> 1 <- 3 |
| // | ^ | |
| // | | | |
| // +--> 2 <--+ |
| // |
| // mubs(0,3) = [1] |
| |
| // This tests a particular state in the algorithm, in which we |
| // need the second pare down call to get the right result (after |
| // intersection, we have [1, 2], but 2 -> 1). |
| |
| let mut relation = TransitiveRelation::default(); |
| relation.add("0", "1"); |
| relation.add("0", "2"); |
| |
| relation.add("2", "1"); |
| |
| relation.add("3", "1"); |
| relation.add("3", "2"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]); |
| assert_eq!(relation.parents(&"0"), vec![&"2"]); |
| assert_eq!(relation.parents(&"2"), vec![&"1"]); |
| assert!(relation.parents(&"1").is_empty()); |
| } |
| |
| #[test] |
| fn mubs_best_choice2() { |
| // 0 -> 1 <- 3 |
| // | | | |
| // | v | |
| // +--> 2 <--+ |
| // |
| // mubs(0,3) = [2] |
| |
| // Like the precedecing test, but in this case intersection is [2, |
| // 1], and hence we rely on the first pare down call. |
| |
| let mut relation = TransitiveRelation::default(); |
| relation.add("0", "1"); |
| relation.add("0", "2"); |
| |
| relation.add("1", "2"); |
| |
| relation.add("3", "1"); |
| relation.add("3", "2"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]); |
| assert_eq!(relation.parents(&"0"), vec![&"1"]); |
| assert_eq!(relation.parents(&"1"), vec![&"2"]); |
| assert!(relation.parents(&"2").is_empty()); |
| } |
| |
| #[test] |
| fn mubs_no_best_choice() { |
| // in this case, the intersection yields [1, 2], and the "pare |
| // down" calls find nothing to remove. |
| let mut relation = TransitiveRelation::default(); |
| relation.add("0", "1"); |
| relation.add("0", "2"); |
| |
| relation.add("3", "1"); |
| relation.add("3", "2"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]); |
| assert_eq!(relation.parents(&"0"), vec![&"1", &"2"]); |
| assert_eq!(relation.parents(&"3"), vec![&"1", &"2"]); |
| } |
| |
| #[test] |
| fn mubs_best_choice_scc() { |
| // in this case, 1 and 2 form a cycle; we pick arbitrarily (but |
| // consistently). |
| |
| let mut relation = TransitiveRelation::default(); |
| relation.add("0", "1"); |
| relation.add("0", "2"); |
| |
| relation.add("1", "2"); |
| relation.add("2", "1"); |
| |
| relation.add("3", "1"); |
| relation.add("3", "2"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]); |
| assert_eq!(relation.parents(&"0"), vec![&"1"]); |
| } |
| |
| #[test] |
| fn pdub_crisscross() { |
| // diagonal edges run left-to-right |
| // a -> a1 -> x |
| // \/ ^ |
| // /\ | |
| // b -> b1 ---+ |
| |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "a1"); |
| relation.add("a", "b1"); |
| relation.add("b", "a1"); |
| relation.add("b", "b1"); |
| relation.add("a1", "x"); |
| relation.add("b1", "x"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), |
| vec![&"a1", &"b1"]); |
| assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x")); |
| assert_eq!(relation.postdom_parent(&"a"), Some(&"x")); |
| assert_eq!(relation.postdom_parent(&"b"), Some(&"x")); |
| } |
| |
| #[test] |
| fn pdub_crisscross_more() { |
| // diagonal edges run left-to-right |
| // a -> a1 -> a2 -> a3 -> x |
| // \/ \/ ^ |
| // /\ /\ | |
| // b -> b1 -> b2 ---------+ |
| |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "a1"); |
| relation.add("a", "b1"); |
| relation.add("b", "a1"); |
| relation.add("b", "b1"); |
| |
| relation.add("a1", "a2"); |
| relation.add("a1", "b2"); |
| relation.add("b1", "a2"); |
| relation.add("b1", "b2"); |
| |
| relation.add("a2", "a3"); |
| |
| relation.add("a3", "x"); |
| relation.add("b2", "x"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), |
| vec![&"a1", &"b1"]); |
| assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"), |
| vec![&"a2", &"b2"]); |
| assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x")); |
| |
| assert_eq!(relation.postdom_parent(&"a"), Some(&"x")); |
| assert_eq!(relation.postdom_parent(&"b"), Some(&"x")); |
| } |
| |
| #[test] |
| fn pdub_lub() { |
| // a -> a1 -> x |
| // ^ |
| // | |
| // b -> b1 ---+ |
| |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "a1"); |
| relation.add("b", "b1"); |
| relation.add("a1", "x"); |
| relation.add("b1", "x"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]); |
| assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x")); |
| |
| assert_eq!(relation.postdom_parent(&"a"), Some(&"a1")); |
| assert_eq!(relation.postdom_parent(&"b"), Some(&"b1")); |
| assert_eq!(relation.postdom_parent(&"a1"), Some(&"x")); |
| assert_eq!(relation.postdom_parent(&"b1"), Some(&"x")); |
| } |
| |
| #[test] |
| fn mubs_intermediate_node_on_one_side_only() { |
| // a -> c -> d |
| // ^ |
| // | |
| // b |
| |
| // "digraph { a -> c -> d; b -> d; }", |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "c"); |
| relation.add("c", "d"); |
| relation.add("b", "d"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]); |
| } |
| |
| #[test] |
| fn mubs_scc_1() { |
| // +-------------+ |
| // | +----+ | |
| // | v | | |
| // a -> c -> d <-+ |
| // ^ |
| // | |
| // b |
| |
| // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }", |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "c"); |
| relation.add("c", "d"); |
| relation.add("d", "c"); |
| relation.add("a", "d"); |
| relation.add("b", "d"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); |
| } |
| |
| #[test] |
| fn mubs_scc_2() { |
| // +----+ |
| // v | |
| // a -> c -> d |
| // ^ ^ |
| // | | |
| // +--- b |
| |
| // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }", |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "c"); |
| relation.add("c", "d"); |
| relation.add("d", "c"); |
| relation.add("b", "d"); |
| relation.add("b", "c"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); |
| } |
| |
| #[test] |
| fn mubs_scc_3() { |
| // +---------+ |
| // v | |
| // a -> c -> d -> e |
| // ^ ^ |
| // | | |
| // b ---+ |
| |
| // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }", |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "c"); |
| relation.add("c", "d"); |
| relation.add("d", "e"); |
| relation.add("e", "c"); |
| relation.add("b", "d"); |
| relation.add("b", "e"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); |
| } |
| |
| #[test] |
| fn mubs_scc_4() { |
| // +---------+ |
| // v | |
| // a -> c -> d -> e |
| // | ^ ^ |
| // +---------+ | |
| // | |
| // b ---+ |
| |
| // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }" |
| let mut relation = TransitiveRelation::default(); |
| relation.add("a", "c"); |
| relation.add("c", "d"); |
| relation.add("d", "e"); |
| relation.add("e", "c"); |
| relation.add("a", "d"); |
| relation.add("b", "e"); |
| |
| assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]); |
| } |
| |
| #[test] |
| fn parent() { |
| // An example that was misbehaving in the compiler. |
| // |
| // 4 -> 1 -> 3 |
| // \ | / |
| // \ v / |
| // 2 -> 0 |
| // |
| // plus a bunch of self-loops |
| // |
| // Here `->` represents `<=` and `0` is `'static`. |
| |
| let pairs = vec![ |
| (2, /*->*/ 0), |
| (2, /*->*/ 2), |
| (0, /*->*/ 0), |
| (0, /*->*/ 0), |
| (1, /*->*/ 0), |
| (1, /*->*/ 1), |
| (3, /*->*/ 0), |
| (3, /*->*/ 3), |
| (4, /*->*/ 0), |
| (4, /*->*/ 1), |
| (1, /*->*/ 3), |
| ]; |
| |
| let mut relation = TransitiveRelation::default(); |
| for (a, b) in pairs { |
| relation.add(a, b); |
| } |
| |
| let p = relation.postdom_parent(&3); |
| assert_eq!(p, Some(&0)); |
| } |
