5 let mut relation = TransitiveRelation::default();
6 relation.add("a", "b");
7 relation.add("a", "c");
8 assert!(relation.contains(&"a", &"c"));
9 assert!(relation.contains(&"a", &"b"));
10 assert!(!relation.contains(&"b", &"a"));
11 assert!(!relation.contains(&"a", &"d"));
15 fn test_many_steps() {
16 let mut relation = TransitiveRelation::default();
17 relation.add("a", "b");
18 relation.add("a", "c");
19 relation.add("a", "f");
21 relation.add("b", "c");
22 relation.add("b", "d");
23 relation.add("b", "e");
25 relation.add("e", "g");
27 assert!(relation.contains(&"a", &"b"));
28 assert!(relation.contains(&"a", &"c"));
29 assert!(relation.contains(&"a", &"d"));
30 assert!(relation.contains(&"a", &"e"));
31 assert!(relation.contains(&"a", &"f"));
32 assert!(relation.contains(&"a", &"g"));
34 assert!(relation.contains(&"b", &"g"));
36 assert!(!relation.contains(&"a", &"x"));
37 assert!(!relation.contains(&"b", &"f"));
46 let mut relation = TransitiveRelation::default();
47 relation.add("a", "tcx");
48 relation.add("b", "tcx");
49 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
50 assert_eq!(relation.parents(&"a"), vec![&"tcx"]);
51 assert_eq!(relation.parents(&"b"), vec![&"tcx"]);
55 fn mubs_best_choice1() {
63 // This tests a particular state in the algorithm, in which we
64 // need the second pare down call to get the right result (after
65 // intersection, we have [1, 2], but 2 -> 1).
67 let mut relation = TransitiveRelation::default();
68 relation.add("0", "1");
69 relation.add("0", "2");
71 relation.add("2", "1");
73 relation.add("3", "1");
74 relation.add("3", "2");
76 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
77 assert_eq!(relation.parents(&"0"), vec![&"2"]);
78 assert_eq!(relation.parents(&"2"), vec![&"1"]);
79 assert!(relation.parents(&"1").is_empty());
83 fn mubs_best_choice2() {
91 // Like the precedecing test, but in this case intersection is [2,
92 // 1], and hence we rely on the first pare down call.
94 let mut relation = TransitiveRelation::default();
95 relation.add("0", "1");
96 relation.add("0", "2");
98 relation.add("1", "2");
100 relation.add("3", "1");
101 relation.add("3", "2");
103 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
104 assert_eq!(relation.parents(&"0"), vec![&"1"]);
105 assert_eq!(relation.parents(&"1"), vec![&"2"]);
106 assert!(relation.parents(&"2").is_empty());
110 fn mubs_no_best_choice() {
111 // in this case, the intersection yields [1, 2], and the "pare
112 // down" calls find nothing to remove.
113 let mut relation = TransitiveRelation::default();
114 relation.add("0", "1");
115 relation.add("0", "2");
117 relation.add("3", "1");
118 relation.add("3", "2");
120 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
121 assert_eq!(relation.parents(&"0"), vec![&"1", &"2"]);
122 assert_eq!(relation.parents(&"3"), vec![&"1", &"2"]);
126 fn mubs_best_choice_scc() {
127 // in this case, 1 and 2 form a cycle; we pick arbitrarily (but
130 let mut relation = TransitiveRelation::default();
131 relation.add("0", "1");
132 relation.add("0", "2");
134 relation.add("1", "2");
135 relation.add("2", "1");
137 relation.add("3", "1");
138 relation.add("3", "2");
140 assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
141 assert_eq!(relation.parents(&"0"), vec![&"1"]);
145 fn pdub_crisscross() {
146 // diagonal edges run left-to-right
152 let mut relation = TransitiveRelation::default();
153 relation.add("a", "a1");
154 relation.add("a", "b1");
155 relation.add("b", "a1");
156 relation.add("b", "b1");
157 relation.add("a1", "x");
158 relation.add("b1", "x");
160 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"a1", &"b1"]);
161 assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
162 assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
163 assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
167 fn pdub_crisscross_more() {
168 // diagonal edges run left-to-right
169 // a -> a1 -> a2 -> a3 -> x
172 // b -> b1 -> b2 ---------+
174 let mut relation = TransitiveRelation::default();
175 relation.add("a", "a1");
176 relation.add("a", "b1");
177 relation.add("b", "a1");
178 relation.add("b", "b1");
180 relation.add("a1", "a2");
181 relation.add("a1", "b2");
182 relation.add("b1", "a2");
183 relation.add("b1", "b2");
185 relation.add("a2", "a3");
187 relation.add("a3", "x");
188 relation.add("b2", "x");
190 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"a1", &"b1"]);
191 assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"), vec![&"a2", &"b2"]);
192 assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
194 assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
195 assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
205 let mut relation = TransitiveRelation::default();
206 relation.add("a", "a1");
207 relation.add("b", "b1");
208 relation.add("a1", "x");
209 relation.add("b1", "x");
211 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
212 assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
214 assert_eq!(relation.postdom_parent(&"a"), Some(&"a1"));
215 assert_eq!(relation.postdom_parent(&"b"), Some(&"b1"));
216 assert_eq!(relation.postdom_parent(&"a1"), Some(&"x"));
217 assert_eq!(relation.postdom_parent(&"b1"), Some(&"x"));
221 fn mubs_intermediate_node_on_one_side_only() {
227 // "digraph { a -> c -> d; b -> d; }",
228 let mut relation = TransitiveRelation::default();
229 relation.add("a", "c");
230 relation.add("c", "d");
231 relation.add("b", "d");
233 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
246 // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
247 let mut relation = TransitiveRelation::default();
248 relation.add("a", "c");
249 relation.add("c", "d");
250 relation.add("d", "c");
251 relation.add("a", "d");
252 relation.add("b", "d");
254 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
266 // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
267 let mut relation = TransitiveRelation::default();
268 relation.add("a", "c");
269 relation.add("c", "d");
270 relation.add("d", "c");
271 relation.add("b", "d");
272 relation.add("b", "c");
274 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
286 // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
287 let mut relation = TransitiveRelation::default();
288 relation.add("a", "c");
289 relation.add("c", "d");
290 relation.add("d", "e");
291 relation.add("e", "c");
292 relation.add("b", "d");
293 relation.add("b", "e");
295 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
308 // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
309 let mut relation = TransitiveRelation::default();
310 relation.add("a", "c");
311 relation.add("c", "d");
312 relation.add("d", "e");
313 relation.add("e", "c");
314 relation.add("a", "d");
315 relation.add("b", "e");
317 assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
322 // An example that was misbehaving in the compiler.
329 // plus a bunch of self-loops
331 // Here `->` represents `<=` and `0` is `'static`.
347 let mut relation = TransitiveRelation::default();
348 for (a, b) in pairs {
352 let p = relation.postdom_parent(&3);
353 assert_eq!(p, Some(&0));