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 // Naming the benchmarks using uppercase letters helps them sort
12 // better.
13 #![allow(non_snake_case)]
14
15 #[cfg(feature = "bench")]
16 extern crate test;
17 #[cfg(feature = "bench")]
18 use self::test::Bencher;
19 use std::cmp;
20 #[cfg(feature = "persistent")]
21 use unify::Persistent;
22 use unify::{EqUnifyValue, InPlace, InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
23 use unify::{UnificationStore, UnificationTable};
24
25 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
26 struct UnitKey(u32);
27
28 impl UnifyKey for UnitKey {
29 type Value = ();
index(&self) -> u3230 fn index(&self) -> u32 {
31 self.0
32 }
from_index(u: u32) -> UnitKey33 fn from_index(u: u32) -> UnitKey {
34 UnitKey(u)
35 }
tag() -> &'static str36 fn tag() -> &'static str {
37 "UnitKey"
38 }
39 }
40
41 macro_rules! all_modes {
42 ($name:ident for $t:ty => $body:tt) => {
43 fn test_body<
44 $name: Clone + Default + UnificationStore<Key = $t, Value = <$t as UnifyKey>::Value>,
45 >() {
46 $body
47 }
48
49 test_body::<InPlace<$t>>();
50
51 #[cfg(feature = "persistent")]
52 test_body::<Persistent<$t>>();
53 };
54 }
55
56 #[test]
basic()57 fn basic() {
58 all_modes! {
59 S for UnitKey => {
60 let mut ut: UnificationTable<S> = UnificationTable::new();
61 let k1 = ut.new_key(());
62 let k2 = ut.new_key(());
63 assert_eq!(ut.unioned(k1, k2), false);
64 ut.union(k1, k2);
65 assert_eq!(ut.unioned(k1, k2), true);
66 }
67 }
68 }
69
70 #[test]
big_array()71 fn big_array() {
72 all_modes! {
73 S for UnitKey => {
74 let mut ut: UnificationTable<S> = UnificationTable::new();
75 let mut keys = Vec::new();
76 const MAX: usize = 1 << 15;
77
78 for _ in 0..MAX {
79 keys.push(ut.new_key(()));
80 }
81
82 for i in 1..MAX {
83 let l = keys[i - 1];
84 let r = keys[i];
85 ut.union(l, r);
86 }
87
88 for i in 0..MAX {
89 assert!(ut.unioned(keys[0], keys[i]));
90 }
91 }
92 }
93 }
94
95 #[cfg(feature = "bench")]
big_array_bench_generic<S: Default + UnificationStore<Key = UnitKey, Value = ()>>( b: &mut Bencher, )96 fn big_array_bench_generic<S: Default + UnificationStore<Key = UnitKey, Value = ()>>(
97 b: &mut Bencher,
98 ) {
99 let mut ut: UnificationTable<S> = UnificationTable::new();
100 let mut keys = Vec::new();
101 const MAX: usize = 1 << 15;
102
103 for _ in 0..MAX {
104 keys.push(ut.new_key(()));
105 }
106
107 b.iter(|| {
108 for i in 1..MAX {
109 let l = keys[i - 1];
110 let r = keys[i];
111 ut.union(l, r);
112 }
113
114 for i in 0..MAX {
115 assert!(ut.unioned(keys[0], keys[i]));
116 }
117 })
118 }
119
120 #[cfg(feature = "bench")]
121 #[bench]
big_array_bench_InPlace(b: &mut Bencher)122 fn big_array_bench_InPlace(b: &mut Bencher) {
123 big_array_bench_generic::<InPlace<UnitKey>>(b);
124 }
125
126 #[cfg(all(feature = "bench", feature = "persistent"))]
127 #[bench]
big_array_bench_Persistent(b: &mut Bencher)128 fn big_array_bench_Persistent(b: &mut Bencher) {
129 big_array_bench_generic::<Persistent<UnitKey>>(b);
130 }
131
132 #[cfg(feature = "bench")]
big_array_bench_in_snapshot_generic<S: Default + UnificationStore<Key = UnitKey, Value = ()>>( b: &mut Bencher, )133 fn big_array_bench_in_snapshot_generic<S: Default + UnificationStore<Key = UnitKey, Value = ()>>(
134 b: &mut Bencher,
135 ) {
136 let mut ut: UnificationTable<S> = UnificationTable::new();
137 let mut keys = Vec::new();
138 const MAX: usize = 1 << 15;
139
140 for _ in 0..MAX {
141 keys.push(ut.new_key(()));
142 }
143
144 b.iter(|| {
145 let snapshot = ut.snapshot();
146
147 for i in 1..MAX {
148 let l = keys[i - 1];
149 let r = keys[i];
150 ut.union(l, r);
151 }
152
153 for i in 0..MAX {
154 assert!(ut.unioned(keys[0], keys[i]));
155 }
156
157 ut.rollback_to(snapshot);
158 })
159 }
160
161 #[cfg(feature = "bench")]
162 #[bench]
big_array_bench_in_snapshot_InPlace(b: &mut Bencher)163 fn big_array_bench_in_snapshot_InPlace(b: &mut Bencher) {
164 big_array_bench_in_snapshot_generic::<InPlace<UnitKey>>(b);
165 }
166
167 #[cfg(all(feature = "bench", feature = "persistent"))]
168 #[bench]
big_array_bench_in_snapshot_Persistent(b: &mut Bencher)169 fn big_array_bench_in_snapshot_Persistent(b: &mut Bencher) {
170 big_array_bench_in_snapshot_generic::<Persistent<UnitKey>>(b);
171 }
172
173 #[cfg(feature = "bench")]
big_array_bench_clone_generic< S: Default + Clone + UnificationStore<Key = UnitKey, Value = ()>, >( b: &mut Bencher, )174 fn big_array_bench_clone_generic<
175 S: Default + Clone + UnificationStore<Key = UnitKey, Value = ()>,
176 >(
177 b: &mut Bencher,
178 ) {
179 let mut ut: UnificationTable<S> = UnificationTable::new();
180 let mut keys = Vec::new();
181 const MAX: usize = 1 << 15;
182
183 for _ in 0..MAX {
184 keys.push(ut.new_key(()));
185 }
186
187 b.iter(|| {
188 let saved_table = ut.clone();
189
190 for i in 1..MAX {
191 let l = keys[i - 1];
192 let r = keys[i];
193 ut.union(l, r);
194 }
195
196 for i in 0..MAX {
197 assert!(ut.unioned(keys[0], keys[i]));
198 }
199
200 ut = saved_table;
201 })
202 }
203
204 #[cfg(feature = "bench")]
205 #[bench]
big_array_bench_clone_InPlace(b: &mut Bencher)206 fn big_array_bench_clone_InPlace(b: &mut Bencher) {
207 big_array_bench_clone_generic::<InPlace<UnitKey>>(b);
208 }
209
210 #[cfg(all(feature = "bench", feature = "persistent"))]
211 #[bench]
big_array_bench_clone_Persistent(b: &mut Bencher)212 fn big_array_bench_clone_Persistent(b: &mut Bencher) {
213 big_array_bench_clone_generic::<Persistent<UnitKey>>(b);
214 }
215
216 #[test]
even_odd()217 fn even_odd() {
218 all_modes! {
219 S for UnitKey => {
220 let mut ut: UnificationTable<S> = UnificationTable::new();
221 let mut keys = Vec::new();
222 const MAX: usize = 1 << 10;
223
224 for i in 0..MAX {
225 let key = ut.new_key(());
226 keys.push(key);
227
228 if i >= 2 {
229 ut.union(key, keys[i - 2]);
230 }
231 }
232
233 for i in 1..MAX {
234 assert!(!ut.unioned(keys[i - 1], keys[i]));
235 }
236
237 for i in 2..MAX {
238 assert!(ut.unioned(keys[i - 2], keys[i]));
239 }
240 }
241 }
242 }
243
244 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
245 struct IntKey(u32);
246
247 impl UnifyKey for IntKey {
248 type Value = Option<i32>;
index(&self) -> u32249 fn index(&self) -> u32 {
250 self.0
251 }
from_index(u: u32) -> IntKey252 fn from_index(u: u32) -> IntKey {
253 IntKey(u)
254 }
tag() -> &'static str255 fn tag() -> &'static str {
256 "IntKey"
257 }
258 }
259
260 impl EqUnifyValue for i32 {}
261
262 #[test]
unify_same_int_twice()263 fn unify_same_int_twice() {
264 all_modes! {
265 S for IntKey => {
266 let mut ut: UnificationTable<S> = UnificationTable::new();
267 let k1 = ut.new_key(None);
268 let k2 = ut.new_key(None);
269 assert!(ut.unify_var_value(k1, Some(22)).is_ok());
270 assert!(ut.unify_var_value(k2, Some(22)).is_ok());
271 assert!(ut.unify_var_var(k1, k2).is_ok());
272 assert_eq!(ut.probe_value(k1), Some(22));
273 }
274 }
275 }
276
277 #[test]
unify_vars_then_int_indirect()278 fn unify_vars_then_int_indirect() {
279 all_modes! {
280 S for IntKey => {
281 let mut ut: UnificationTable<S> = UnificationTable::new();
282 let k1 = ut.new_key(None);
283 let k2 = ut.new_key(None);
284 assert!(ut.unify_var_var(k1, k2).is_ok());
285 assert!(ut.unify_var_value(k1, Some(22)).is_ok());
286 assert_eq!(ut.probe_value(k2), Some(22));
287 }
288 }
289 }
290
291 #[test]
unify_vars_different_ints_1()292 fn unify_vars_different_ints_1() {
293 all_modes! {
294 S for IntKey => {
295 let mut ut: UnificationTable<S> = UnificationTable::new();
296 let k1 = ut.new_key(None);
297 let k2 = ut.new_key(None);
298 assert!(ut.unify_var_var(k1, k2).is_ok());
299 assert!(ut.unify_var_value(k1, Some(22)).is_ok());
300 assert!(ut.unify_var_value(k2, Some(23)).is_err());
301 }
302 }
303 }
304
305 #[test]
unify_vars_different_ints_2()306 fn unify_vars_different_ints_2() {
307 all_modes! {
308 S for IntKey => {
309 let mut ut: UnificationTable<S> = UnificationTable::new();
310 let k1 = ut.new_key(None);
311 let k2 = ut.new_key(None);
312 assert!(ut.unify_var_var(k2, k1).is_ok());
313 assert!(ut.unify_var_value(k1, Some(22)).is_ok());
314 assert!(ut.unify_var_value(k2, Some(23)).is_err());
315 }
316 }
317 }
318
319 #[test]
unify_distinct_ints_then_vars()320 fn unify_distinct_ints_then_vars() {
321 all_modes! {
322 S for IntKey => {
323 let mut ut: UnificationTable<S> = UnificationTable::new();
324 let k1 = ut.new_key(None);
325 let k2 = ut.new_key(None);
326 assert!(ut.unify_var_value(k1, Some(22)).is_ok());
327 assert!(ut.unify_var_value(k2, Some(23)).is_ok());
328 assert!(ut.unify_var_var(k2, k1).is_err());
329 }
330 }
331 }
332
333 #[test]
unify_root_value_1()334 fn unify_root_value_1() {
335 all_modes! {
336 S for IntKey => {
337 let mut ut: UnificationTable<S> = UnificationTable::new();
338 let k1 = ut.new_key(None);
339 let k2 = ut.new_key(None);
340 let k3 = ut.new_key(None);
341 assert!(ut.unify_var_value(k1, Some(22)).is_ok());
342 assert!(ut.unify_var_var(k1, k2).is_ok());
343 assert!(ut.unify_var_value(k3, Some(23)).is_ok());
344 assert!(ut.unify_var_var(k1, k3).is_err());
345 }
346 }
347 }
348
349 #[test]
unify_root_value_2()350 fn unify_root_value_2() {
351 all_modes! {
352 S for IntKey => {
353 let mut ut: UnificationTable<S> = UnificationTable::new();
354 let k1 = ut.new_key(None);
355 let k2 = ut.new_key(None);
356 let k3 = ut.new_key(None);
357 assert!(ut.unify_var_value(k1, Some(22)).is_ok());
358 assert!(ut.unify_var_var(k2, k1).is_ok());
359 assert!(ut.unify_var_value(k3, Some(23)).is_ok());
360 assert!(ut.unify_var_var(k1, k3).is_err());
361 }
362 }
363 }
364
365 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
366 struct OrderedKey(u32);
367
368 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
369 struct OrderedRank(u32);
370
371 impl UnifyKey for OrderedKey {
372 type Value = OrderedRank;
index(&self) -> u32373 fn index(&self) -> u32 {
374 self.0
375 }
from_index(u: u32) -> OrderedKey376 fn from_index(u: u32) -> OrderedKey {
377 OrderedKey(u)
378 }
tag() -> &'static str379 fn tag() -> &'static str {
380 "OrderedKey"
381 }
order_roots( a: OrderedKey, a_rank: &OrderedRank, b: OrderedKey, b_rank: &OrderedRank, ) -> Option<(OrderedKey, OrderedKey)>382 fn order_roots(
383 a: OrderedKey,
384 a_rank: &OrderedRank,
385 b: OrderedKey,
386 b_rank: &OrderedRank,
387 ) -> Option<(OrderedKey, OrderedKey)> {
388 println!("{:?} vs {:?}", a_rank, b_rank);
389 if a_rank > b_rank {
390 Some((a, b))
391 } else if b_rank > a_rank {
392 Some((b, a))
393 } else {
394 None
395 }
396 }
397 }
398
399 impl UnifyValue for OrderedRank {
400 type Error = NoError;
401
unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError>402 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
403 Ok(OrderedRank(cmp::max(value1.0, value2.0)))
404 }
405 }
406
407 #[test]
ordered_key()408 fn ordered_key() {
409 all_modes! {
410 S for OrderedKey => {
411 let mut ut: UnificationTable<S> = UnificationTable::new();
412
413 let k0_1 = ut.new_key(OrderedRank(0));
414 let k0_2 = ut.new_key(OrderedRank(0));
415 let k0_3 = ut.new_key(OrderedRank(0));
416 let k0_4 = ut.new_key(OrderedRank(0));
417
418 ut.union(k0_1, k0_2); // rank of one of those will now be 1
419 ut.union(k0_3, k0_4); // rank of new root also 1
420 ut.union(k0_1, k0_3); // rank of new root now 2
421
422 let k0_5 = ut.new_key(OrderedRank(0));
423 let k0_6 = ut.new_key(OrderedRank(0));
424 ut.union(k0_5, k0_6); // rank of new root now 1
425
426 ut.union(k0_1, k0_5); // new root rank 2, should not be k0_5 or k0_6
427 assert!(vec![k0_1, k0_2, k0_3, k0_4].contains(&ut.find(k0_1)));
428 }
429 }
430 }
431
432 #[test]
ordered_key_k1()433 fn ordered_key_k1() {
434 all_modes! {
435 S for UnitKey => {
436 let mut ut: InPlaceUnificationTable<OrderedKey> = UnificationTable::new();
437
438 let k0_1 = ut.new_key(OrderedRank(0));
439 let k0_2 = ut.new_key(OrderedRank(0));
440 let k0_3 = ut.new_key(OrderedRank(0));
441 let k0_4 = ut.new_key(OrderedRank(0));
442
443 ut.union(k0_1, k0_2); // rank of one of those will now be 1
444 ut.union(k0_3, k0_4); // rank of new root also 1
445 ut.union(k0_1, k0_3); // rank of new root now 2
446
447 let k1_5 = ut.new_key(OrderedRank(1));
448 let k1_6 = ut.new_key(OrderedRank(1));
449 ut.union(k1_5, k1_6); // rank of new root now 1
450
451 ut.union(k0_1, k1_5); // even though k1 has lower rank, it wins
452 assert!(
453 vec![k1_5, k1_6].contains(&ut.find(k0_1)),
454 "unexpected choice for root: {:?}",
455 ut.find(k0_1)
456 );
457 }
458 }
459 }
460
461 /// Test that we *can* clone.
462 #[test]
clone_table()463 fn clone_table() {
464 all_modes! {
465 S for IntKey => {
466 let mut ut: UnificationTable<S> = UnificationTable::new();
467 let k1 = ut.new_key(None);
468 let k2 = ut.new_key(None);
469 let k3 = ut.new_key(None);
470 assert!(ut.unify_var_value(k1, Some(22)).is_ok());
471 assert!(ut.unify_var_value(k2, Some(22)).is_ok());
472 assert!(ut.unify_var_var(k1, k2).is_ok());
473 assert_eq!(ut.probe_value(k3), None);
474
475 let mut ut1 = ut.clone();
476 assert_eq!(ut1.probe_value(k1), Some(22));
477 assert_eq!(ut1.probe_value(k3), None);
478
479 assert!(ut.unify_var_value(k3, Some(44)).is_ok());
480
481 assert_eq!(ut1.probe_value(k1), Some(22));
482 assert_eq!(ut1.probe_value(k3), None);
483 assert_eq!(ut.probe_value(k3), Some(44));
484 }
485 }
486 }
487