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 bitvec
::BitMatrix
;
13 use rustc_serialize
::{Encodable, Encoder, Decodable, Decoder}
;
14 use stable_hasher
::{HashStable, StableHasher, StableHasherResult}
;
15 use std
::cell
::RefCell
;
22 pub struct TransitiveRelation
<T
: Clone
+ Debug
+ Eq
+ Hash
+ Clone
> {
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 RefCell 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
: RefCell
<Option
<BitMatrix
>>,
45 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
48 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
54 impl<T
: Clone
+ Debug
+ Eq
+ Hash
+ Clone
> TransitiveRelation
<T
> {
55 pub fn new() -> TransitiveRelation
<T
> {
60 closure
: RefCell
::new(None
),
64 pub fn is_empty(&self) -> bool
{
68 fn index(&self, a
: &T
) -> Option
<Index
> {
69 self.map
.get(a
).cloned()
72 fn add_index(&mut self, a
: T
) -> Index
{
73 let &mut TransitiveRelation
{
84 // if we changed the dimensions, clear the cache
85 *closure
.borrow_mut() = None
;
87 Index(elements
.len() - 1)
92 /// Applies the (partial) function to each edge and returns a new
93 /// relation. If `f` returns `None` for any end-point, returns
95 pub fn maybe_map
<F
, U
>(&self, mut f
: F
) -> Option
<TransitiveRelation
<U
>>
96 where F
: FnMut(&T
) -> Option
<U
>,
97 U
: Clone
+ Debug
+ Eq
+ Hash
+ Clone
,
99 let mut result
= TransitiveRelation
::new();
100 for edge
in &self.edges
{
101 let r
= f(&self.elements
[edge
.source
.0]).and_then(|source
| {
102 f(&self.elements
[edge
.target
.0]).and_then(|target
| {
103 Some(result
.add(source
, target
))
113 /// Indicate that `a < b` (where `<` is this relation)
114 pub fn add(&mut self, a
: T
, b
: T
) {
115 let a
= self.add_index(a
);
116 let b
= self.add_index(b
);
121 if !self.edges
.contains(&edge
) {
122 self.edges
.push(edge
);
124 // added an edge, clear the cache
125 *self.closure
.borrow_mut() = None
;
129 /// Check whether `a < target` (transitively)
130 pub fn contains(&self, a
: &T
, b
: &T
) -> bool
{
131 match (self.index(a
), self.index(b
)) {
132 (Some(a
), Some(b
)) => self.with_closure(|closure
| closure
.contains(a
.0, b
.0)),
133 (None
, _
) | (_
, None
) => false,
137 /// Returns a vector of all things less than `a`.
139 /// Really this probably ought to be `impl Iterator<Item=&T>`, but
140 /// I'm too lazy to make that work, and -- given the caching
141 /// strategy -- it'd be a touch tricky anyhow.
142 pub fn less_than(&self, a
: &T
) -> Vec
<&T
> {
143 match self.index(a
) {
144 Some(a
) => self.with_closure(|closure
| {
145 closure
.iter(a
.0).map(|i
| &self.elements
[i
]).collect()
151 /// Picks what I am referring to as the "postdominating"
152 /// upper-bound for `a` and `b`. This is usually the least upper
153 /// bound, but in cases where there is no single least upper
154 /// bound, it is the "mutual immediate postdominator", if you
155 /// imagine a graph where `a < b` means `a -> b`.
157 /// This function is needed because region inference currently
158 /// requires that we produce a single "UB", and there is no best
159 /// choice for the LUB. Rather than pick arbitrarily, I pick a
160 /// less good, but predictable choice. This should help ensure
161 /// that region inference yields predictable results (though it
162 /// itself is not fully sufficient).
164 /// Examples are probably clearer than any prose I could write
165 /// (there are corresponding tests below, btw). In each case,
166 /// the query is `postdom_upper_bound(a, b)`:
169 /// // returns Some(x), which is also LUB
175 /// // returns Some(x), which is not LUB (there is none)
176 /// // diagonal edges run left-to-right
186 pub fn postdom_upper_bound(&self, a
: &T
, b
: &T
) -> Option
<&T
> {
187 let mut mubs
= self.minimal_upper_bounds(a
, b
);
191 1 => return Some(mubs
[0]),
193 let m
= mubs
.pop().unwrap();
194 let n
= mubs
.pop().unwrap();
195 mubs
.extend(self.minimal_upper_bounds(n
, m
));
201 /// Returns the set of bounds `X` such that:
203 /// - `a < X` and `b < X`
204 /// - there is no `Y != X` such that `a < Y` and `Y < X`
205 /// - except for the case where `X < a` (i.e., a strongly connected
206 /// component in the graph). In that case, the smallest
207 /// representative of the SCC is returned (as determined by the
208 /// internal indices).
210 /// Note that this set can, in principle, have any size.
211 pub fn minimal_upper_bounds(&self, a
: &T
, b
: &T
) -> Vec
<&T
> {
212 let (mut a
, mut b
) = match (self.index(a
), self.index(b
)) {
213 (Some(a
), Some(b
)) => (a
, b
),
214 (None
, _
) | (_
, None
) => {
219 // in some cases, there are some arbitrary choices to be made;
220 // it doesn't really matter what we pick, as long as we pick
221 // the same thing consistently when queried, so ensure that
222 // (a, b) are in a consistent relative order
224 mem
::swap(&mut a
, &mut b
);
227 let lub_indices
= self.with_closure(|closure
| {
228 // Easy case is when either a < b or b < a:
229 if closure
.contains(a
.0, b
.0) {
232 if closure
.contains(b
.0, a
.0) {
236 // Otherwise, the tricky part is that there may be some c
237 // where a < c and b < c. In fact, there may be many such
238 // values. So here is what we do:
240 // 1. Find the vector `[X | a < X && b < X]` of all values
241 // `X` where `a < X` and `b < X`. In terms of the
242 // graph, this means all values reachable from both `a`
243 // and `b`. Note that this vector is also a set, but we
244 // use the term vector because the order matters
245 // to the steps below.
246 // - This vector contains upper bounds, but they are
247 // not minimal upper bounds. So you may have e.g.
248 // `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and
249 // `z < x` and `z < y`:
251 // z --+---> x ----+----> tcx
256 // In this case, we really want to return just `[z]`.
257 // The following steps below achieve this by gradually
258 // reducing the list.
259 // 2. Pare down the vector using `pare_down`. This will
260 // remove elements from the vector that can be reached
261 // by an earlier element.
262 // - In the example above, this would convert `[x, y,
263 // tcx, z]` to `[x, y, z]`. Note that `x` and `y` are
264 // still in the vector; this is because while `z < x`
265 // (and `z < y`) holds, `z` comes after them in the
267 // 3. Reverse the vector and repeat the pare down process.
268 // - In the example above, we would reverse to
269 // `[z, y, x]` and then pare down to `[z]`.
270 // 4. Reverse once more just so that we yield a vector in
271 // increasing order of index. Not necessary, but why not.
273 // I believe this algorithm yields a minimal set. The
274 // argument is that, after step 2, we know that no element
275 // can reach its successors (in the vector, not the graph).
276 // After step 3, we know that no element can reach any of
277 // its predecesssors (because of step 2) nor successors
278 // (because we just called `pare_down`)
280 let mut candidates
= closure
.intersection(a
.0, b
.0); // (1)
281 pare_down(&mut candidates
, closure
); // (2)
282 candidates
.reverse(); // (3a)
283 pare_down(&mut candidates
, closure
); // (3b)
287 lub_indices
.into_iter()
289 .map(|i
| &self.elements
[i
])
293 fn with_closure
<OP
, R
>(&self, op
: OP
) -> R
294 where OP
: FnOnce(&BitMatrix
) -> R
296 let mut closure_cell
= self.closure
.borrow_mut();
297 let mut closure
= closure_cell
.take();
298 if closure
.is_none() {
299 closure
= Some(self.compute_closure());
301 let result
= op(closure
.as_ref().unwrap());
302 *closure_cell
= closure
;
306 fn compute_closure(&self) -> BitMatrix
{
307 let mut matrix
= BitMatrix
::new(self.elements
.len(),
308 self.elements
.len());
309 let mut changed
= true;
312 for edge
in self.edges
.iter() {
313 // add an edge from S -> T
314 changed
|= matrix
.add(edge
.source
.0, edge
.target
.0);
316 // add all outgoing edges from T into S
317 changed
|= matrix
.merge(edge
.target
.0, edge
.source
.0);
324 /// Pare down is used as a step in the LUB computation. It edits the
325 /// candidates array in place by removing any element j for which
326 /// there exists an earlier element i<j such that i -> j. That is,
327 /// after you run `pare_down`, you know that for all elements that
328 /// remain in candidates, they cannot reach any of the elements that
331 /// Examples follow. Assume that a -> b -> c and x -> y -> z.
333 /// - Input: `[a, b, x]`. Output: `[a, x]`.
334 /// - Input: `[b, a, x]`. Output: `[b, a, x]`.
335 /// - Input: `[a, x, b, y]`. Output: `[a, x]`.
336 fn pare_down(candidates
: &mut Vec
<usize>, closure
: &BitMatrix
) {
338 while i
< candidates
.len() {
339 let candidate_i
= candidates
[i
];
344 while j
< candidates
.len() {
345 let candidate_j
= candidates
[j
];
346 if closure
.contains(candidate_i
, candidate_j
) {
347 // If `i` can reach `j`, then we can remove `j`. So just
348 // mark it as dead and move on; subsequent indices will be
349 // shifted into its place.
352 candidates
[j
- dead
] = candidate_j
;
356 candidates
.truncate(j
- dead
);
360 impl<T
> Encodable
for TransitiveRelation
<T
>
361 where T
: Clone
+ Encodable
+ Debug
+ Eq
+ Hash
+ Clone
363 fn encode
<E
: Encoder
>(&self, s
: &mut E
) -> Result
<(), E
::Error
> {
364 s
.emit_struct("TransitiveRelation", 2, |s
| {
365 s
.emit_struct_field("elements", 0, |s
| self.elements
.encode(s
))?
;
366 s
.emit_struct_field("edges", 1, |s
| self.edges
.encode(s
))?
;
372 impl<T
> Decodable
for TransitiveRelation
<T
>
373 where T
: Clone
+ Decodable
+ Debug
+ Eq
+ Hash
+ Clone
375 fn decode
<D
: Decoder
>(d
: &mut D
) -> Result
<Self, D
::Error
> {
376 d
.read_struct("TransitiveRelation", 2, |d
| {
377 let elements
: Vec
<T
> = d
.read_struct_field("elements", 0, |d
| Decodable
::decode(d
))?
;
378 let edges
= d
.read_struct_field("edges", 1, |d
| Decodable
::decode(d
))?
;
379 let map
= elements
.iter()
381 .map(|(index
, elem
)| (elem
.clone(), Index(index
)))
383 Ok(TransitiveRelation { elements, edges, map, closure: RefCell::new(None) }
)
388 impl<CTX
, T
> HashStable
<CTX
> for TransitiveRelation
<T
>
389 where T
: HashStable
<CTX
> + Eq
+ Debug
+ Clone
+ Hash
391 fn hash_stable
<W
: StableHasherResult
>(&self,
393 hasher
: &mut StableHasher
<W
>) {
394 // We are assuming here that the relation graph has been built in a
395 // deterministic way and we can just hash it the way it is.
396 let TransitiveRelation
{
399 // "map" is just a copy of elements vec
401 // "closure" is just a copy of the data above
405 elements
.hash_stable(hcx
, hasher
);
406 edges
.hash_stable(hcx
, hasher
);
410 impl<CTX
> HashStable
<CTX
> for Edge
{
411 fn hash_stable
<W
: StableHasherResult
>(&self,
413 hasher
: &mut StableHasher
<W
>) {
419 source
.hash_stable(hcx
, hasher
);
420 target
.hash_stable(hcx
, hasher
);
424 impl<CTX
> HashStable
<CTX
> for Index
{
425 fn hash_stable
<W
: StableHasherResult
>(&self,
427 hasher
: &mut StableHasher
<W
>) {
428 let Index(idx
) = *self;
429 idx
.hash_stable(hcx
, hasher
);
435 let mut relation
= TransitiveRelation
::new();
436 relation
.add("a", "b");
437 relation
.add("a", "c");
438 assert
!(relation
.contains(&"a", &"c"));
439 assert
!(relation
.contains(&"a", &"b"));
440 assert
!(!relation
.contains(&"b", &"a"));
441 assert
!(!relation
.contains(&"a", &"d"));
445 fn test_many_steps() {
446 let mut relation
= TransitiveRelation
::new();
447 relation
.add("a", "b");
448 relation
.add("a", "c");
449 relation
.add("a", "f");
451 relation
.add("b", "c");
452 relation
.add("b", "d");
453 relation
.add("b", "e");
455 relation
.add("e", "g");
457 assert
!(relation
.contains(&"a", &"b"));
458 assert
!(relation
.contains(&"a", &"c"));
459 assert
!(relation
.contains(&"a", &"d"));
460 assert
!(relation
.contains(&"a", &"e"));
461 assert
!(relation
.contains(&"a", &"f"));
462 assert
!(relation
.contains(&"a", &"g"));
464 assert
!(relation
.contains(&"b", &"g"));
466 assert
!(!relation
.contains(&"a", &"x"));
467 assert
!(!relation
.contains(&"b", &"f"));
472 let mut relation
= TransitiveRelation
::new();
473 relation
.add("a", "tcx");
474 relation
.add("b", "tcx");
475 assert_eq
!(relation
.minimal_upper_bounds(&"a", &"b"), vec
![&"tcx"]);
479 fn mubs_best_choice1() {
487 // This tests a particular state in the algorithm, in which we
488 // need the second pare down call to get the right result (after
489 // intersection, we have [1, 2], but 2 -> 1).
491 let mut relation
= TransitiveRelation
::new();
492 relation
.add("0", "1");
493 relation
.add("0", "2");
495 relation
.add("2", "1");
497 relation
.add("3", "1");
498 relation
.add("3", "2");
500 assert_eq
!(relation
.minimal_upper_bounds(&"0", &"3"), vec
![&"2"]);
504 fn mubs_best_choice2() {
512 // Like the precedecing test, but in this case intersection is [2,
513 // 1], and hence we rely on the first pare down call.
515 let mut relation
= TransitiveRelation
::new();
516 relation
.add("0", "1");
517 relation
.add("0", "2");
519 relation
.add("1", "2");
521 relation
.add("3", "1");
522 relation
.add("3", "2");
524 assert_eq
!(relation
.minimal_upper_bounds(&"0", &"3"), vec
![&"1"]);
528 fn mubs_no_best_choice() {
529 // in this case, the intersection yields [1, 2], and the "pare
530 // down" calls find nothing to remove.
531 let mut relation
= TransitiveRelation
::new();
532 relation
.add("0", "1");
533 relation
.add("0", "2");
535 relation
.add("3", "1");
536 relation
.add("3", "2");
538 assert_eq
!(relation
.minimal_upper_bounds(&"0", &"3"), vec
![&"1", &"2"]);
542 fn mubs_best_choice_scc() {
543 let mut relation
= TransitiveRelation
::new();
544 relation
.add("0", "1");
545 relation
.add("0", "2");
547 relation
.add("1", "2");
548 relation
.add("2", "1");
550 relation
.add("3", "1");
551 relation
.add("3", "2");
553 assert_eq
!(relation
.minimal_upper_bounds(&"0", &"3"), vec
![&"1"]);
557 fn pdub_crisscross() {
558 // diagonal edges run left-to-right
564 let mut relation
= TransitiveRelation
::new();
565 relation
.add("a", "a1");
566 relation
.add("a", "b1");
567 relation
.add("b", "a1");
568 relation
.add("b", "b1");
569 relation
.add("a1", "x");
570 relation
.add("b1", "x");
572 assert_eq
!(relation
.minimal_upper_bounds(&"a", &"b"),
574 assert_eq
!(relation
.postdom_upper_bound(&"a", &"b"), Some(&"x"));
578 fn pdub_crisscross_more() {
579 // diagonal edges run left-to-right
580 // a -> a1 -> a2 -> a3 -> x
583 // b -> b1 -> b2 ---------+
585 let mut relation
= TransitiveRelation
::new();
586 relation
.add("a", "a1");
587 relation
.add("a", "b1");
588 relation
.add("b", "a1");
589 relation
.add("b", "b1");
591 relation
.add("a1", "a2");
592 relation
.add("a1", "b2");
593 relation
.add("b1", "a2");
594 relation
.add("b1", "b2");
596 relation
.add("a2", "a3");
598 relation
.add("a3", "x");
599 relation
.add("b2", "x");
601 assert_eq
!(relation
.minimal_upper_bounds(&"a", &"b"),
603 assert_eq
!(relation
.minimal_upper_bounds(&"a1", &"b1"),
605 assert_eq
!(relation
.postdom_upper_bound(&"a", &"b"), Some(&"x"));
615 let mut relation
= TransitiveRelation
::new();
616 relation
.add("a", "a1");
617 relation
.add("b", "b1");
618 relation
.add("a1", "x");
619 relation
.add("b1", "x");
621 assert_eq
!(relation
.minimal_upper_bounds(&"a", &"b"), vec
![&"x"]);
622 assert_eq
!(relation
.postdom_upper_bound(&"a", &"b"), Some(&"x"));
626 fn mubs_intermediate_node_on_one_side_only() {
632 // "digraph { a -> c -> d; b -> d; }",
633 let mut relation
= TransitiveRelation
::new();
634 relation
.add("a", "c");
635 relation
.add("c", "d");
636 relation
.add("b", "d");
638 assert_eq
!(relation
.minimal_upper_bounds(&"a", &"b"), vec
![&"d"]);
651 // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
652 let mut relation
= TransitiveRelation
::new();
653 relation
.add("a", "c");
654 relation
.add("c", "d");
655 relation
.add("d", "c");
656 relation
.add("a", "d");
657 relation
.add("b", "d");
659 assert_eq
!(relation
.minimal_upper_bounds(&"a", &"b"), vec
![&"c"]);
671 // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
672 let mut relation
= TransitiveRelation
::new();
673 relation
.add("a", "c");
674 relation
.add("c", "d");
675 relation
.add("d", "c");
676 relation
.add("b", "d");
677 relation
.add("b", "c");
679 assert_eq
!(relation
.minimal_upper_bounds(&"a", &"b"), vec
![&"c"]);
691 // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
692 let mut relation
= TransitiveRelation
::new();
693 relation
.add("a", "c");
694 relation
.add("c", "d");
695 relation
.add("d", "e");
696 relation
.add("e", "c");
697 relation
.add("b", "d");
698 relation
.add("b", "e");
700 assert_eq
!(relation
.minimal_upper_bounds(&"a", &"b"), vec
![&"c"]);
713 // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
714 let mut relation
= TransitiveRelation
::new();
715 relation
.add("a", "c");
716 relation
.add("c", "d");
717 relation
.add("d", "e");
718 relation
.add("e", "c");
719 relation
.add("a", "d");
720 relation
.add("b", "e");
722 assert_eq
!(relation
.minimal_upper_bounds(&"a", &"b"), vec
![&"c"]);