]> git.proxmox.com Git - rustc.git/blob - src/librustc_data_structures/transitive_relation.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_data_structures / transitive_relation.rs
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.
4 //
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.
10
11 use bitvec::BitMatrix;
12 use std::cell::RefCell;
13 use std::fmt::Debug;
14 use std::mem;
15
16 #[derive(Clone)]
17 pub struct TransitiveRelation<T: Debug + PartialEq> {
18 // List of elements. This is used to map from a T to a usize. We
19 // expect domain to be small so just use a linear list versus a
20 // hashmap or something.
21 elements: Vec<T>,
22
23 // List of base edges in the graph. Require to compute transitive
24 // closure.
25 edges: Vec<Edge>,
26
27 // This is a cached transitive closure derived from the edges.
28 // Currently, we build it lazilly and just throw out any existing
29 // copy whenever a new edge is added. (The RefCell is to permit
30 // the lazy computation.) This is kind of silly, except for the
31 // fact its size is tied to `self.elements.len()`, so I wanted to
32 // wait before building it up to avoid reallocating as new edges
33 // are added with new elements. Perhaps better would be to ask the
34 // user for a batch of edges to minimize this effect, but I
35 // already wrote the code this way. :P -nmatsakis
36 closure: RefCell<Option<BitMatrix>>,
37 }
38
39 #[derive(Clone, PartialEq, PartialOrd)]
40 struct Index(usize);
41
42 #[derive(Clone, PartialEq)]
43 struct Edge {
44 source: Index,
45 target: Index,
46 }
47
48 impl<T: Debug + PartialEq> TransitiveRelation<T> {
49 pub fn new() -> TransitiveRelation<T> {
50 TransitiveRelation {
51 elements: vec![],
52 edges: vec![],
53 closure: RefCell::new(None),
54 }
55 }
56
57 fn index(&self, a: &T) -> Option<Index> {
58 self.elements.iter().position(|e| *e == *a).map(Index)
59 }
60
61 fn add_index(&mut self, a: T) -> Index {
62 match self.index(&a) {
63 Some(i) => i,
64 None => {
65 self.elements.push(a);
66
67 // if we changed the dimensions, clear the cache
68 *self.closure.borrow_mut() = None;
69
70 Index(self.elements.len() - 1)
71 }
72 }
73 }
74
75 /// Indicate that `a < b` (where `<` is this relation)
76 pub fn add(&mut self, a: T, b: T) {
77 let a = self.add_index(a);
78 let b = self.add_index(b);
79 let edge = Edge {
80 source: a,
81 target: b,
82 };
83 if !self.edges.contains(&edge) {
84 self.edges.push(edge);
85
86 // added an edge, clear the cache
87 *self.closure.borrow_mut() = None;
88 }
89 }
90
91 /// Check whether `a < target` (transitively)
92 pub fn contains(&self, a: &T, b: &T) -> bool {
93 match (self.index(a), self.index(b)) {
94 (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)),
95 (None, _) | (_, None) => false,
96 }
97 }
98
99 /// Picks what I am referring to as the "postdominating"
100 /// upper-bound for `a` and `b`. This is usually the least upper
101 /// bound, but in cases where there is no single least upper
102 /// bound, it is the "mutual immediate postdominator", if you
103 /// imagine a graph where `a < b` means `a -> b`.
104 ///
105 /// This function is needed because region inference currently
106 /// requires that we produce a single "UB", and there is no best
107 /// choice for the LUB. Rather than pick arbitrarily, I pick a
108 /// less good, but predictable choice. This should help ensure
109 /// that region inference yields predictable results (though it
110 /// itself is not fully sufficient).
111 ///
112 /// Examples are probably clearer than any prose I could write
113 /// (there are corresponding tests below, btw). In each case,
114 /// the query is `postdom_upper_bound(a, b)`:
115 ///
116 /// ```text
117 /// // returns Some(x), which is also LUB
118 /// a -> a1 -> x
119 /// ^
120 /// |
121 /// b -> b1 ---+
122 ///
123 /// // returns Some(x), which is not LUB (there is none)
124 /// // diagonal edges run left-to-right
125 /// a -> a1 -> x
126 /// \/ ^
127 /// /\ |
128 /// b -> b1 ---+
129 ///
130 /// // returns None
131 /// a -> a1
132 /// b -> b1
133 /// ```
134 pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> {
135 let mut mubs = self.minimal_upper_bounds(a, b);
136 loop {
137 match mubs.len() {
138 0 => return None,
139 1 => return Some(mubs[0]),
140 _ => {
141 let m = mubs.pop().unwrap();
142 let n = mubs.pop().unwrap();
143 mubs.extend(self.minimal_upper_bounds(n, m));
144 }
145 }
146 }
147 }
148
149 /// Returns the set of bounds `X` such that:
150 ///
151 /// - `a < X` and `b < X`
152 /// - there is no `Y != X` such that `a < Y` and `Y < X`
153 /// - except for the case where `X < a` (i.e., a strongly connected
154 /// component in the graph). In that case, the smallest
155 /// representative of the SCC is returned (as determined by the
156 /// internal indices).
157 ///
158 /// Note that this set can, in principle, have any size.
159 pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> {
160 let (mut a, mut b) = match (self.index(a), self.index(b)) {
161 (Some(a), Some(b)) => (a, b),
162 (None, _) | (_, None) => {
163 return vec![];
164 }
165 };
166
167 // in some cases, there are some arbitrary choices to be made;
168 // it doesn't really matter what we pick, as long as we pick
169 // the same thing consistently when queried, so ensure that
170 // (a, b) are in a consistent relative order
171 if a > b {
172 mem::swap(&mut a, &mut b);
173 }
174
175 let lub_indices = self.with_closure(|closure| {
176 // Easy case is when either a < b or b < a:
177 if closure.contains(a.0, b.0) {
178 return vec![b.0];
179 }
180 if closure.contains(b.0, a.0) {
181 return vec![a.0];
182 }
183
184 // Otherwise, the tricky part is that there may be some c
185 // where a < c and b < c. In fact, there may be many such
186 // values. So here is what we do:
187 //
188 // 1. Find the vector `[X | a < X && b < X]` of all values
189 // `X` where `a < X` and `b < X`. In terms of the
190 // graph, this means all values reachable from both `a`
191 // and `b`. Note that this vector is also a set, but we
192 // use the term vector because the order matters
193 // to the steps below.
194 // - This vector contains upper bounds, but they are
195 // not minimal upper bounds. So you may have e.g.
196 // `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and
197 // `z < x` and `z < y`:
198 //
199 // z --+---> x ----+----> tcx
200 // | |
201 // | |
202 // +---> y ----+
203 //
204 // In this case, we really want to return just `[z]`.
205 // The following steps below achieve this by gradually
206 // reducing the list.
207 // 2. Pare down the vector using `pare_down`. This will
208 // remove elements from the vector that can be reached
209 // by an earlier element.
210 // - In the example above, this would convert `[x, y,
211 // tcx, z]` to `[x, y, z]`. Note that `x` and `y` are
212 // still in the vector; this is because while `z < x`
213 // (and `z < y`) holds, `z` comes after them in the
214 // vector.
215 // 3. Reverse the vector and repeat the pare down process.
216 // - In the example above, we would reverse to
217 // `[z, y, x]` and then pare down to `[z]`.
218 // 4. Reverse once more just so that we yield a vector in
219 // increasing order of index. Not necessary, but why not.
220 //
221 // I believe this algorithm yields a minimal set. The
222 // argument is that, after step 2, we know that no element
223 // can reach its successors (in the vector, not the graph).
224 // After step 3, we know that no element can reach any of
225 // its predecesssors (because of step 2) nor successors
226 // (because we just called `pare_down`)
227
228 let mut candidates = closure.intersection(a.0, b.0); // (1)
229 pare_down(&mut candidates, closure); // (2)
230 candidates.reverse(); // (3a)
231 pare_down(&mut candidates, closure); // (3b)
232 candidates
233 });
234
235 lub_indices.into_iter()
236 .rev() // (4)
237 .map(|i| &self.elements[i])
238 .collect()
239 }
240
241 fn with_closure<OP, R>(&self, op: OP) -> R
242 where OP: FnOnce(&BitMatrix) -> R
243 {
244 let mut closure_cell = self.closure.borrow_mut();
245 let mut closure = closure_cell.take();
246 if closure.is_none() {
247 closure = Some(self.compute_closure());
248 }
249 let result = op(closure.as_ref().unwrap());
250 *closure_cell = closure;
251 result
252 }
253
254 fn compute_closure(&self) -> BitMatrix {
255 let mut matrix = BitMatrix::new(self.elements.len());
256 let mut changed = true;
257 while changed {
258 changed = false;
259 for edge in self.edges.iter() {
260 // add an edge from S -> T
261 changed |= matrix.add(edge.source.0, edge.target.0);
262
263 // add all outgoing edges from T into S
264 changed |= matrix.merge(edge.target.0, edge.source.0);
265 }
266 }
267 matrix
268 }
269 }
270
271 /// Pare down is used as a step in the LUB computation. It edits the
272 /// candidates array in place by removing any element j for which
273 /// there exists an earlier element i<j such that i -> j. That is,
274 /// after you run `pare_down`, you know that for all elements that
275 /// remain in candidates, they cannot reach any of the elements that
276 /// come after them.
277 ///
278 /// Examples follow. Assume that a -> b -> c and x -> y -> z.
279 ///
280 /// - Input: `[a, b, x]`. Output: `[a, x]`.
281 /// - Input: `[b, a, x]`. Output: `[b, a, x]`.
282 /// - Input: `[a, x, b, y]`. Output: `[a, x]`.
283 fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix) {
284 let mut i = 0;
285 while i < candidates.len() {
286 let candidate_i = candidates[i];
287 i += 1;
288
289 let mut j = i;
290 let mut dead = 0;
291 while j < candidates.len() {
292 let candidate_j = candidates[j];
293 if closure.contains(candidate_i, candidate_j) {
294 // If `i` can reach `j`, then we can remove `j`. So just
295 // mark it as dead and move on; subsequent indices will be
296 // shifted into its place.
297 dead += 1;
298 } else {
299 candidates[j - dead] = candidate_j;
300 }
301 j += 1;
302 }
303 candidates.truncate(j - dead);
304 }
305 }
306
307 #[test]
308 fn test_one_step() {
309 let mut relation = TransitiveRelation::new();
310 relation.add("a", "b");
311 relation.add("a", "c");
312 assert!(relation.contains(&"a", &"c"));
313 assert!(relation.contains(&"a", &"b"));
314 assert!(!relation.contains(&"b", &"a"));
315 assert!(!relation.contains(&"a", &"d"));
316 }
317
318 #[test]
319 fn test_many_steps() {
320 let mut relation = TransitiveRelation::new();
321 relation.add("a", "b");
322 relation.add("a", "c");
323 relation.add("a", "f");
324
325 relation.add("b", "c");
326 relation.add("b", "d");
327 relation.add("b", "e");
328
329 relation.add("e", "g");
330
331 assert!(relation.contains(&"a", &"b"));
332 assert!(relation.contains(&"a", &"c"));
333 assert!(relation.contains(&"a", &"d"));
334 assert!(relation.contains(&"a", &"e"));
335 assert!(relation.contains(&"a", &"f"));
336 assert!(relation.contains(&"a", &"g"));
337
338 assert!(relation.contains(&"b", &"g"));
339
340 assert!(!relation.contains(&"a", &"x"));
341 assert!(!relation.contains(&"b", &"f"));
342 }
343
344 #[test]
345 fn mubs_triange() {
346 let mut relation = TransitiveRelation::new();
347 relation.add("a", "tcx");
348 relation.add("b", "tcx");
349 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
350 }
351
352 #[test]
353 fn mubs_best_choice1() {
354 // 0 -> 1 <- 3
355 // | ^ |
356 // | | |
357 // +--> 2 <--+
358 //
359 // mubs(0,3) = [1]
360
361 // This tests a particular state in the algorithm, in which we
362 // need the second pare down call to get the right result (after
363 // intersection, we have [1, 2], but 2 -> 1).
364
365 let mut relation = TransitiveRelation::new();
366 relation.add("0", "1");
367 relation.add("0", "2");
368
369 relation.add("2", "1");
370
371 relation.add("3", "1");
372 relation.add("3", "2");
373
374 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
375 }
376
377 #[test]
378 fn mubs_best_choice2() {
379 // 0 -> 1 <- 3
380 // | | |
381 // | v |
382 // +--> 2 <--+
383 //
384 // mubs(0,3) = [2]
385
386 // Like the precedecing test, but in this case intersection is [2,
387 // 1], and hence we rely on the first pare down call.
388
389 let mut relation = TransitiveRelation::new();
390 relation.add("0", "1");
391 relation.add("0", "2");
392
393 relation.add("1", "2");
394
395 relation.add("3", "1");
396 relation.add("3", "2");
397
398 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
399 }
400
401 #[test]
402 fn mubs_no_best_choice() {
403 // in this case, the intersection yields [1, 2], and the "pare
404 // down" calls find nothing to remove.
405 let mut relation = TransitiveRelation::new();
406 relation.add("0", "1");
407 relation.add("0", "2");
408
409 relation.add("3", "1");
410 relation.add("3", "2");
411
412 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
413 }
414
415 #[test]
416 fn mubs_best_choice_scc() {
417 let mut relation = TransitiveRelation::new();
418 relation.add("0", "1");
419 relation.add("0", "2");
420
421 relation.add("1", "2");
422 relation.add("2", "1");
423
424 relation.add("3", "1");
425 relation.add("3", "2");
426
427 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
428 }
429
430 #[test]
431 fn pdub_crisscross() {
432 // diagonal edges run left-to-right
433 // a -> a1 -> x
434 // \/ ^
435 // /\ |
436 // b -> b1 ---+
437
438 let mut relation = TransitiveRelation::new();
439 relation.add("a", "a1");
440 relation.add("a", "b1");
441 relation.add("b", "a1");
442 relation.add("b", "b1");
443 relation.add("a1", "x");
444 relation.add("b1", "x");
445
446 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
447 vec![&"a1", &"b1"]);
448 assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
449 }
450
451 #[test]
452 fn pdub_crisscross_more() {
453 // diagonal edges run left-to-right
454 // a -> a1 -> a2 -> a3 -> x
455 // \/ \/ ^
456 // /\ /\ |
457 // b -> b1 -> b2 ---------+
458
459 let mut relation = TransitiveRelation::new();
460 relation.add("a", "a1");
461 relation.add("a", "b1");
462 relation.add("b", "a1");
463 relation.add("b", "b1");
464
465 relation.add("a1", "a2");
466 relation.add("a1", "b2");
467 relation.add("b1", "a2");
468 relation.add("b1", "b2");
469
470 relation.add("a2", "a3");
471
472 relation.add("a3", "x");
473 relation.add("b2", "x");
474
475 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
476 vec![&"a1", &"b1"]);
477 assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"),
478 vec![&"a2", &"b2"]);
479 assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
480 }
481
482 #[test]
483 fn pdub_lub() {
484 // a -> a1 -> x
485 // ^
486 // |
487 // b -> b1 ---+
488
489 let mut relation = TransitiveRelation::new();
490 relation.add("a", "a1");
491 relation.add("b", "b1");
492 relation.add("a1", "x");
493 relation.add("b1", "x");
494
495 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
496 assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
497 }
498
499 #[test]
500 fn mubs_intermediate_node_on_one_side_only() {
501 // a -> c -> d
502 // ^
503 // |
504 // b
505
506 // "digraph { a -> c -> d; b -> d; }",
507 let mut relation = TransitiveRelation::new();
508 relation.add("a", "c");
509 relation.add("c", "d");
510 relation.add("b", "d");
511
512 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
513 }
514
515 #[test]
516 fn mubs_scc_1() {
517 // +-------------+
518 // | +----+ |
519 // | v | |
520 // a -> c -> d <-+
521 // ^
522 // |
523 // b
524
525 // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
526 let mut relation = TransitiveRelation::new();
527 relation.add("a", "c");
528 relation.add("c", "d");
529 relation.add("d", "c");
530 relation.add("a", "d");
531 relation.add("b", "d");
532
533 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
534 }
535
536 #[test]
537 fn mubs_scc_2() {
538 // +----+
539 // v |
540 // a -> c -> d
541 // ^ ^
542 // | |
543 // +--- b
544
545 // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
546 let mut relation = TransitiveRelation::new();
547 relation.add("a", "c");
548 relation.add("c", "d");
549 relation.add("d", "c");
550 relation.add("b", "d");
551 relation.add("b", "c");
552
553 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
554 }
555
556 #[test]
557 fn mubs_scc_3() {
558 // +---------+
559 // v |
560 // a -> c -> d -> e
561 // ^ ^
562 // | |
563 // b ---+
564
565 // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
566 let mut relation = TransitiveRelation::new();
567 relation.add("a", "c");
568 relation.add("c", "d");
569 relation.add("d", "e");
570 relation.add("e", "c");
571 relation.add("b", "d");
572 relation.add("b", "e");
573
574 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
575 }
576
577 #[test]
578 fn mubs_scc_4() {
579 // +---------+
580 // v |
581 // a -> c -> d -> e
582 // | ^ ^
583 // +---------+ |
584 // |
585 // b ---+
586
587 // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
588 let mut relation = TransitiveRelation::new();
589 relation.add("a", "c");
590 relation.add("c", "d");
591 relation.add("d", "e");
592 relation.add("e", "c");
593 relation.add("a", "d");
594 relation.add("b", "e");
595
596 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
597 }