]>
git.proxmox.com Git - rustc.git/blob - src/librustc_data_structures/transitive_relation/tests.rs
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));