1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use bit_set::BitMatrix;
14 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
15 use stable_hasher::{HashStable, StableHasher, StableHasherResult};
21 #[derive(Clone, Debug)]
22 pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash> {
23 // List of elements. This is used to map from a T to a usize.
26 // Maps each element to an index.
27 map: FxHashMap<T, Index>,
29 // List of base edges in the graph. Require to compute transitive
33 // This is a cached transitive closure derived from the edges.
34 // Currently, we build it lazilly and just throw out any existing
35 // copy whenever a new edge is added. (The Lock is to permit
36 // the lazy computation.) This is kind of silly, except for the
37 // fact its size is tied to `self.elements.len()`, so I wanted to
38 // wait before building it up to avoid reallocating as new edges
39 // are added with new elements. Perhaps better would be to ask the
40 // user for a batch of edges to minimize this effect, but I
41 // already wrote the code this way. :P -nmatsakis
42 closure: Lock<Option<BitMatrix<usize, usize>>>,
45 // HACK(eddyb) manual impl avoids `Default` bound on `T`.
46 impl<T: Clone + Debug + Eq + Hash> Default for TransitiveRelation<T> {
47 fn default() -> Self {
49 elements: Default::default(),
50 map: Default::default(),
51 edges: Default::default(),
52 closure: Default::default(),
57 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable, Debug)]
60 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
66 impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
67 pub fn is_empty(&self) -> bool {
71 fn index(&self, a: &T) -> Option<Index> {
72 self.map.get(a).cloned()
75 fn add_index(&mut self, a: T) -> Index {
76 let &mut TransitiveRelation {
87 // if we changed the dimensions, clear the cache
88 *closure.get_mut() = None;
90 Index(elements.len() - 1)
94 /// Applies the (partial) function to each edge and returns a new
95 /// relation. If `f` returns `None` for any end-point, returns
97 pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>>
98 where F: FnMut(&T) -> Option<U>,
99 U: Clone + Debug + Eq + Hash + Clone,
101 let mut result = TransitiveRelation::default();
102 for edge in &self.edges {
103 result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?);
108 /// Indicate that `a < b` (where `<` is this relation)
109 pub fn add(&mut self, a: T, b: T) {
110 let a = self.add_index(a);
111 let b = self.add_index(b);
116 if !self.edges.contains(&edge) {
117 self.edges.push(edge);
119 // added an edge, clear the cache
120 *self.closure.get_mut() = None;
124 /// Check whether `a < target` (transitively)
125 pub fn contains(&self, a: &T, b: &T) -> bool {
126 match (self.index(a), self.index(b)) {
127 (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)),
128 (None, _) | (_, None) => false,
132 /// Thinking of `x R y` as an edge `x -> y` in a graph, this
133 /// returns all things reachable from `a`.
135 /// Really this probably ought to be `impl Iterator<Item=&T>`, but
136 /// I'm too lazy to make that work, and -- given the caching
137 /// strategy -- it'd be a touch tricky anyhow.
138 pub fn reachable_from(&self, a: &T) -> Vec<&T> {
139 match self.index(a) {
140 Some(a) => self.with_closure(|closure| {
141 closure.iter(a.0).map(|i| &self.elements[i]).collect()
147 /// Picks what I am referring to as the "postdominating"
148 /// upper-bound for `a` and `b`. This is usually the least upper
149 /// bound, but in cases where there is no single least upper
150 /// bound, it is the "mutual immediate postdominator", if you
151 /// imagine a graph where `a < b` means `a -> b`.
153 /// This function is needed because region inference currently
154 /// requires that we produce a single "UB", and there is no best
155 /// choice for the LUB. Rather than pick arbitrarily, I pick a
156 /// less good, but predictable choice. This should help ensure
157 /// that region inference yields predictable results (though it
158 /// itself is not fully sufficient).
160 /// Examples are probably clearer than any prose I could write
161 /// (there are corresponding tests below, btw). In each case,
162 /// the query is `postdom_upper_bound(a, b)`:
165 /// // returns Some(x), which is also LUB
171 /// // returns Some(x), which is not LUB (there is none)
172 /// // diagonal edges run left-to-right
182 pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> {
183 let mubs = self.minimal_upper_bounds(a, b);
184 self.mutual_immediate_postdominator(mubs)
187 /// Viewing the relation as a graph, computes the "mutual
188 /// immediate postdominator" of a set of points (if one
189 /// exists). See `postdom_upper_bound` for details.
190 pub fn mutual_immediate_postdominator<'a>(&'a self, mut mubs: Vec<&'a T>) -> Option<&'a T> {
194 1 => return Some(mubs[0]),
196 let m = mubs.pop().unwrap();
197 let n = mubs.pop().unwrap();
198 mubs.extend(self.minimal_upper_bounds(n, m));
204 /// Returns the set of bounds `X` such that:
206 /// - `a < X` and `b < X`
207 /// - there is no `Y != X` such that `a < Y` and `Y < X`
208 /// - except for the case where `X < a` (i.e., a strongly connected
209 /// component in the graph). In that case, the smallest
210 /// representative of the SCC is returned (as determined by the
211 /// internal indices).
213 /// Note that this set can, in principle, have any size.
214 pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> {
215 let (mut a, mut b) = match (self.index(a), self.index(b)) {
216 (Some(a), Some(b)) => (a, b),
217 (None, _) | (_, None) => {
222 // in some cases, there are some arbitrary choices to be made;
223 // it doesn't really matter what we pick, as long as we pick
224 // the same thing consistently when queried, so ensure that
225 // (a, b) are in a consistent relative order
227 mem::swap(&mut a, &mut b);
230 let lub_indices = self.with_closure(|closure| {
231 // Easy case is when either a < b or b < a:
232 if closure.contains(a.0, b.0) {
235 if closure.contains(b.0, a.0) {
239 // Otherwise, the tricky part is that there may be some c
240 // where a < c and b < c. In fact, there may be many such
241 // values. So here is what we do:
243 // 1. Find the vector `[X | a < X && b < X]` of all values
244 // `X` where `a < X` and `b < X`. In terms of the
245 // graph, this means all values reachable from both `a`
246 // and `b`. Note that this vector is also a set, but we
247 // use the term vector because the order matters
248 // to the steps below.
249 // - This vector contains upper bounds, but they are
250 // not minimal upper bounds. So you may have e.g.
251 // `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and
252 // `z < x` and `z < y`:
254 // z --+---> x ----+----> tcx
259 // In this case, we really want to return just `[z]`.
260 // The following steps below achieve this by gradually
261 // reducing the list.
262 // 2. Pare down the vector using `pare_down`. This will
263 // remove elements from the vector that can be reached
264 // by an earlier element.
265 // - In the example above, this would convert `[x, y,
266 // tcx, z]` to `[x, y, z]`. Note that `x` and `y` are
267 // still in the vector; this is because while `z < x`
268 // (and `z < y`) holds, `z` comes after them in the
270 // 3. Reverse the vector and repeat the pare down process.
271 // - In the example above, we would reverse to
272 // `[z, y, x]` and then pare down to `[z]`.
273 // 4. Reverse once more just so that we yield a vector in
274 // increasing order of index. Not necessary, but why not.
276 // I believe this algorithm yields a minimal set. The
277 // argument is that, after step 2, we know that no element
278 // can reach its successors (in the vector, not the graph).
279 // After step 3, we know that no element can reach any of
280 // its predecesssors (because of step 2) nor successors
281 // (because we just called `pare_down`)
283 // This same algorithm is used in `parents` below.
285 let mut candidates = closure.intersect_rows(a.0, b.0); // (1)
286 pare_down(&mut candidates, closure); // (2)
287 candidates.reverse(); // (3a)
288 pare_down(&mut candidates, closure); // (3b)
292 lub_indices.into_iter()
294 .map(|i| &self.elements[i])
298 /// Given an element A, returns the maximal set {B} of elements B
303 /// - for each i, j: B[i] R B[j] does not hold
305 /// The intuition is that this moves "one step up" through a lattice
306 /// (where the relation is encoding the `<=` relation for the lattice).
307 /// So e.g. if the relation is `->` and we have
315 /// then `parents(a)` returns `[b, c]`. The `postdom_parent` function
316 /// would further reduce this to just `f`.
317 pub fn parents(&self, a: &T) -> Vec<&T> {
318 let a = match self.index(a) {
320 None => return vec![]
323 // Steal the algorithm for `minimal_upper_bounds` above, but
324 // with a slight tweak. In the case where `a R a`, we remove
325 // that from the set of candidates.
326 let ancestors = self.with_closure(|closure| {
327 let mut ancestors = closure.intersect_rows(a.0, a.0);
329 // Remove anything that can reach `a`. If this is a
330 // reflexive relation, this will include `a` itself.
331 ancestors.retain(|&e| !closure.contains(e, a.0));
333 pare_down(&mut ancestors, closure); // (2)
334 ancestors.reverse(); // (3a)
335 pare_down(&mut ancestors, closure); // (3b)
339 ancestors.into_iter()
341 .map(|i| &self.elements[i])
345 /// A "best" parent in some sense. See `parents` and
346 /// `postdom_upper_bound` for more details.
347 pub fn postdom_parent(&self, a: &T) -> Option<&T> {
348 self.mutual_immediate_postdominator(self.parents(a))
351 fn with_closure<OP, R>(&self, op: OP) -> R
352 where OP: FnOnce(&BitMatrix<usize, usize>) -> R
354 let mut closure_cell = self.closure.borrow_mut();
355 let mut closure = closure_cell.take();
356 if closure.is_none() {
357 closure = Some(self.compute_closure());
359 let result = op(closure.as_ref().unwrap());
360 *closure_cell = closure;
364 fn compute_closure(&self) -> BitMatrix<usize, usize> {
365 let mut matrix = BitMatrix::new(self.elements.len(),
366 self.elements.len());
367 let mut changed = true;
370 for edge in &self.edges {
371 // add an edge from S -> T
372 changed |= matrix.insert(edge.source.0, edge.target.0);
374 // add all outgoing edges from T into S
375 changed |= matrix.union_rows(edge.target.0, edge.source.0);
382 /// Pare down is used as a step in the LUB computation. It edits the
383 /// candidates array in place by removing any element j for which
384 /// there exists an earlier element i<j such that i -> j. That is,
385 /// after you run `pare_down`, you know that for all elements that
386 /// remain in candidates, they cannot reach any of the elements that
389 /// Examples follow. Assume that a -> b -> c and x -> y -> z.
391 /// - Input: `[a, b, x]`. Output: `[a, x]`.
392 /// - Input: `[b, a, x]`. Output: `[b, a, x]`.
393 /// - Input: `[a, x, b, y]`. Output: `[a, x]`.
394 fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) {
396 while i < candidates.len() {
397 let candidate_i = candidates[i];
402 while j < candidates.len() {
403 let candidate_j = candidates[j];
404 if closure.contains(candidate_i, candidate_j) {
405 // If `i` can reach `j`, then we can remove `j`. So just
406 // mark it as dead and move on; subsequent indices will be
407 // shifted into its place.
410 candidates[j - dead] = candidate_j;
414 candidates.truncate(j - dead);
418 impl<T> Encodable for TransitiveRelation<T>
419 where T: Clone + Encodable + Debug + Eq + Hash + Clone
421 fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> {
422 s.emit_struct("TransitiveRelation", 2, |s| {
423 s.emit_struct_field("elements", 0, |s| self.elements.encode(s))?;
424 s.emit_struct_field("edges", 1, |s| self.edges.encode(s))?;
430 impl<T> Decodable for TransitiveRelation<T>
431 where T: Clone + Decodable + Debug + Eq + Hash + Clone
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.iter()
439 .map(|(index, elem)| (elem.clone(), Index(index)))
441 Ok(TransitiveRelation { elements, edges, map, closure: Lock::new(None) })
446 impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
447 where T: HashStable<CTX> + Eq + Debug + Clone + Hash
449 fn hash_stable<W: StableHasherResult>(&self,
451 hasher: &mut StableHasher<W>) {
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 {
457 // "map" is just a copy of elements vec
459 // "closure" is just a copy of the data above
463 elements.hash_stable(hcx, hasher);
464 edges.hash_stable(hcx, hasher);
468 impl<CTX> HashStable<CTX> for Edge {
469 fn hash_stable<W: StableHasherResult>(&self,
471 hasher: &mut StableHasher<W>) {
477 source.hash_stable(hcx, hasher);
478 target.hash_stable(hcx, hasher);
482 impl<CTX> HashStable<CTX> for Index {
483 fn hash_stable<W: StableHasherResult>(&self,
485 hasher: &mut StableHasher<W>) {
486 let Index(idx) = *self;
487 idx.hash_stable(hcx, hasher);
493 let mut relation = TransitiveRelation::default();
494 relation.add("a", "b");
495 relation.add("a", "c");
496 assert!(relation.contains(&"a", &"c"));
497 assert!(relation.contains(&"a", &"b"));
498 assert!(!relation.contains(&"b", &"a"));
499 assert!(!relation.contains(&"a", &"d"));
503 fn test_many_steps() {
504 let mut relation = TransitiveRelation::default();
505 relation.add("a", "b");
506 relation.add("a", "c");
507 relation.add("a", "f");
509 relation.add("b", "c");
510 relation.add("b", "d");
511 relation.add("b", "e");
513 relation.add("e", "g");
515 assert!(relation.contains(&"a", &"b"));
516 assert!(relation.contains(&"a", &"c"));
517 assert!(relation.contains(&"a", &"d"));
518 assert!(relation.contains(&"a", &"e"));
519 assert!(relation.contains(&"a", &"f"));
520 assert!(relation.contains(&"a", &"g"));
522 assert!(relation.contains(&"b", &"g"));
524 assert!(!relation.contains(&"a", &"x"));
525 assert!(!relation.contains(&"b", &"f"));
534 let mut relation = TransitiveRelation::default();
535 relation.add("a", "tcx");
536 relation.add("b", "tcx");
537 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
538 assert_eq!(relation.parents(&"a"), vec![&"tcx"]);
539 assert_eq!(relation.parents(&"b"), vec![&"tcx"]);
543 fn mubs_best_choice1() {
551 // This tests a particular state in the algorithm, in which we
552 // need the second pare down call to get the right result (after
553 // intersection, we have [1, 2], but 2 -> 1).
555 let mut relation = TransitiveRelation::default();
556 relation.add("0", "1");
557 relation.add("0", "2");
559 relation.add("2", "1");
561 relation.add("3", "1");
562 relation.add("3", "2");
564 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
565 assert_eq!(relation.parents(&"0"), vec![&"2"]);
566 assert_eq!(relation.parents(&"2"), vec![&"1"]);
567 assert!(relation.parents(&"1").is_empty());
571 fn mubs_best_choice2() {
579 // Like the precedecing test, but in this case intersection is [2,
580 // 1], and hence we rely on the first pare down call.
582 let mut relation = TransitiveRelation::default();
583 relation.add("0", "1");
584 relation.add("0", "2");
586 relation.add("1", "2");
588 relation.add("3", "1");
589 relation.add("3", "2");
591 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
592 assert_eq!(relation.parents(&"0"), vec![&"1"]);
593 assert_eq!(relation.parents(&"1"), vec![&"2"]);
594 assert!(relation.parents(&"2").is_empty());
598 fn mubs_no_best_choice() {
599 // in this case, the intersection yields [1, 2], and the "pare
600 // down" calls find nothing to remove.
601 let mut relation = TransitiveRelation::default();
602 relation.add("0", "1");
603 relation.add("0", "2");
605 relation.add("3", "1");
606 relation.add("3", "2");
608 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
609 assert_eq!(relation.parents(&"0"), vec![&"1", &"2"]);
610 assert_eq!(relation.parents(&"3"), vec![&"1", &"2"]);
614 fn mubs_best_choice_scc() {
615 // in this case, 1 and 2 form a cycle; we pick arbitrarily (but
618 let mut relation = TransitiveRelation::default();
619 relation.add("0", "1");
620 relation.add("0", "2");
622 relation.add("1", "2");
623 relation.add("2", "1");
625 relation.add("3", "1");
626 relation.add("3", "2");
628 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
629 assert_eq!(relation.parents(&"0"), vec![&"1"]);
633 fn pdub_crisscross() {
634 // diagonal edges run left-to-right
640 let mut relation = TransitiveRelation::default();
641 relation.add("a", "a1");
642 relation.add("a", "b1");
643 relation.add("b", "a1");
644 relation.add("b", "b1");
645 relation.add("a1", "x");
646 relation.add("b1", "x");
648 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
650 assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
651 assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
652 assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
656 fn pdub_crisscross_more() {
657 // diagonal edges run left-to-right
658 // a -> a1 -> a2 -> a3 -> x
661 // b -> b1 -> b2 ---------+
663 let mut relation = TransitiveRelation::default();
664 relation.add("a", "a1");
665 relation.add("a", "b1");
666 relation.add("b", "a1");
667 relation.add("b", "b1");
669 relation.add("a1", "a2");
670 relation.add("a1", "b2");
671 relation.add("b1", "a2");
672 relation.add("b1", "b2");
674 relation.add("a2", "a3");
676 relation.add("a3", "x");
677 relation.add("b2", "x");
679 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
681 assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"),
683 assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
685 assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
686 assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
696 let mut relation = TransitiveRelation::default();
697 relation.add("a", "a1");
698 relation.add("b", "b1");
699 relation.add("a1", "x");
700 relation.add("b1", "x");
702 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
703 assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
705 assert_eq!(relation.postdom_parent(&"a"), Some(&"a1"));
706 assert_eq!(relation.postdom_parent(&"b"), Some(&"b1"));
707 assert_eq!(relation.postdom_parent(&"a1"), Some(&"x"));
708 assert_eq!(relation.postdom_parent(&"b1"), Some(&"x"));
712 fn mubs_intermediate_node_on_one_side_only() {
718 // "digraph { a -> c -> d; b -> d; }",
719 let mut relation = TransitiveRelation::default();
720 relation.add("a", "c");
721 relation.add("c", "d");
722 relation.add("b", "d");
724 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
737 // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
738 let mut relation = TransitiveRelation::default();
739 relation.add("a", "c");
740 relation.add("c", "d");
741 relation.add("d", "c");
742 relation.add("a", "d");
743 relation.add("b", "d");
745 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
757 // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
758 let mut relation = TransitiveRelation::default();
759 relation.add("a", "c");
760 relation.add("c", "d");
761 relation.add("d", "c");
762 relation.add("b", "d");
763 relation.add("b", "c");
765 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
777 // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
778 let mut relation = TransitiveRelation::default();
779 relation.add("a", "c");
780 relation.add("c", "d");
781 relation.add("d", "e");
782 relation.add("e", "c");
783 relation.add("b", "d");
784 relation.add("b", "e");
786 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
799 // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
800 let mut relation = TransitiveRelation::default();
801 relation.add("a", "c");
802 relation.add("c", "d");
803 relation.add("d", "e");
804 relation.add("e", "c");
805 relation.add("a", "d");
806 relation.add("b", "e");
808 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
813 // An example that was misbehaving in the compiler.
820 // plus a bunch of self-loops
822 // Here `->` represents `<=` and `0` is `'static`.
838 let mut relation = TransitiveRelation::default();
839 for (a, b) in pairs {
843 let p = relation.postdom_parent(&3);
844 assert_eq!(p, Some(&0));