1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
use super::*;
use super::super::tests::TestGraph;
#[test]
fn diamond() {
let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
let d = dominators(&graph);
assert_eq!(d.immediate_dominator(0), None);
assert_eq!(d.immediate_dominator(1), Some(0));
assert_eq!(d.immediate_dominator(2), Some(0));
assert_eq!(d.immediate_dominator(3), Some(0));
}
#[test]
fn paper() {
// example from the paper:
let graph = TestGraph::new(
6,
&[(6, 5), (6, 4), (5, 1), (4, 2), (4, 3), (1, 2), (2, 3), (3, 2), (2, 1)],
);
let d = dominators(&graph);
assert_eq!(d.immediate_dominator(0), None); // <-- note that 0 is not in graph
assert_eq!(d.immediate_dominator(1), Some(6));
assert_eq!(d.immediate_dominator(2), Some(6));
assert_eq!(d.immediate_dominator(3), Some(6));
assert_eq!(d.immediate_dominator(4), Some(6));
assert_eq!(d.immediate_dominator(5), Some(6));
assert_eq!(d.immediate_dominator(6), None);
}
#[test]
fn paper_slt() {
// example from the paper:
let graph = TestGraph::new(
1,
&[(1, 2), (1, 3), (2, 3), (2, 7), (3, 4), (3, 6), (4, 5), (5, 4), (6, 7), (7, 8), (8, 5)],
);
dominators(&graph);
}
#[test]
fn immediate_dominator() {
let graph = TestGraph::new(1, &[(1, 2), (2, 3)]);
let d = dominators(&graph);
assert_eq!(d.immediate_dominator(0), None);
assert_eq!(d.immediate_dominator(1), None);
assert_eq!(d.immediate_dominator(2), Some(1));
assert_eq!(d.immediate_dominator(3), Some(2));
}
#[test]
fn transitive_dominator() {
let graph = TestGraph::new(
0,
&[
// First tree branch.
(0, 1),
(1, 2),
(2, 3),
(3, 4),
// Second tree branch.
(1, 5),
(5, 6),
// Third tree branch.
(0, 7),
// These links make 0 the dominator for 2 and 3.
(7, 2),
(5, 3),
],
);
let d = dominators(&graph);
assert_eq!(d.immediate_dominator(2), Some(0));
assert_eq!(d.immediate_dominator(3), Some(0)); // This used to return Some(1).
}
|
