src/librustc_data_structures/unify/tests.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 #![allow(non_snake_case)]
  12
  13 extern crate test;
  14 use self::test::Bencher;
  15 use std::collections::HashSet;
  16 use unify::{UnifyKey, UnificationTable};
  17
  18 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  19 struct UnitKey(u32);
  20
  21 impl UnifyKey for UnitKey {
  22     type Value = ();
  23     fn index(&self) -> u32 { self.0 }
  24     fn from_index(u: u32) -> UnitKey { UnitKey(u) }
  25     fn tag(_: Option<UnitKey>) -> &'static str { "UnitKey" }
  26 }
  27
  28 #[test]
  29 fn basic() {
  30     let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
  31     let k1 = ut.new_key(());
  32     let k2 = ut.new_key(());
  33     assert_eq!(ut.unioned(k1, k2), false);
  34     ut.union(k1, k2);
  35     assert_eq!(ut.unioned(k1, k2), true);
  36 }
  37
  38 #[test]
  39 fn big_array() {
  40     let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
  41     let mut keys = Vec::new();
  42     const MAX: usize = 1 << 15;
  43
  44     for _ in 0..MAX {
  45         keys.push(ut.new_key(()));
  46     }
  47
  48     for i in 1..MAX {
  49         let l = keys[i-1];
  50         let r = keys[i];
  51         ut.union(l, r);
  52     }
  53
  54     for i in 0..MAX {
  55         assert!(ut.unioned(keys[0], keys[i]));
  56     }
  57 }
  58
  59 #[bench]
  60 fn big_array_bench(b: &mut Bencher) {
  61     let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
  62     let mut keys = Vec::new();
  63     const MAX: usize = 1 << 15;
  64
  65     for _ in 0..MAX {
  66         keys.push(ut.new_key(()));
  67     }
  68
  69
  70     b.iter(|| {
  71         for i in 1..MAX {
  72             let l = keys[i-1];
  73             let r = keys[i];
  74             ut.union(l, r);
  75         }
  76
  77         for i in 0..MAX {
  78             assert!(ut.unioned(keys[0], keys[i]));
  79         }
  80     })
  81 }
  82
  83 #[test]
  84 fn even_odd() {
  85     let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
  86     let mut keys = Vec::new();
  87     const MAX: usize = 1 << 10;
  88
  89     for i in 0..MAX {
  90         let key = ut.new_key(());
  91         keys.push(key);
  92
  93         if i >= 2 {
  94             ut.union(key, keys[i-2]);
  95         }
  96     }
  97
  98     for i in 1..MAX {
  99         assert!(!ut.unioned(keys[i-1], keys[i]));
 100     }
 101
 102     for i in 2..MAX {
 103         assert!(ut.unioned(keys[i-2], keys[i]));
 104     }
 105 }
 106
 107 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
 108 struct IntKey(u32);
 109
 110 impl UnifyKey for IntKey {
 111     type Value = Option<i32>;
 112     fn index(&self) -> u32 { self.0 }
 113     fn from_index(u: u32) -> IntKey { IntKey(u) }
 114     fn tag(_: Option<IntKey>) -> &'static str { "IntKey" }
 115 }
 116
 117 /// Test unifying a key whose value is `Some(_)`  with a key whose value is `None`.
 118 /// Afterwards both should be `Some(_)`.
 119 #[test]
 120 fn unify_key_Some_key_None() {
 121     let mut ut: UnificationTable<IntKey> = UnificationTable::new();
 122     let k1 = ut.new_key(Some(22));
 123     let k2 = ut.new_key(None);
 124     assert!(ut.unify_var_var(k1, k2).is_ok());
 125     assert_eq!(ut.probe(k2), Some(22));
 126     assert_eq!(ut.probe(k1), Some(22));
 127 }
 128
 129 /// Test unifying a key whose value is `None`  with a key whose value is `Some(_)`.
 130 /// Afterwards both should be `Some(_)`.
 131 #[test]
 132 fn unify_key_None_key_Some() {
 133     let mut ut: UnificationTable<IntKey> = UnificationTable::new();
 134     let k1 = ut.new_key(Some(22));
 135     let k2 = ut.new_key(None);
 136     assert!(ut.unify_var_var(k2, k1).is_ok());
 137     assert_eq!(ut.probe(k2), Some(22));
 138     assert_eq!(ut.probe(k1), Some(22));
 139 }
 140
 141 /// Test unifying a key whose value is `Some(x)` with a key whose value is `Some(y)`.
 142 /// This should yield an error.
 143 #[test]
 144 fn unify_key_Some_x_key_Some_y() {
 145     let mut ut: UnificationTable<IntKey> = UnificationTable::new();
 146     let k1 = ut.new_key(Some(22));
 147     let k2 = ut.new_key(Some(23));
 148     assert_eq!(ut.unify_var_var(k1, k2), Err((22, 23)));
 149     assert_eq!(ut.unify_var_var(k2, k1), Err((23, 22)));
 150     assert_eq!(ut.probe(k1), Some(22));
 151     assert_eq!(ut.probe(k2), Some(23));
 152 }
 153
 154 /// Test unifying a key whose value is `Some(x)` with a key whose value is `Some(x)`.
 155 /// This should be ok.
 156 #[test]
 157 fn unify_key_Some_x_key_Some_x() {
 158     let mut ut: UnificationTable<IntKey> = UnificationTable::new();
 159     let k1 = ut.new_key(Some(22));
 160     let k2 = ut.new_key(Some(22));
 161     assert!(ut.unify_var_var(k1, k2).is_ok());
 162     assert_eq!(ut.probe(k1), Some(22));
 163     assert_eq!(ut.probe(k2), Some(22));
 164 }
 165
 166 /// Test unifying a key whose value is `None` with a value is `x`.
 167 /// Afterwards key should be `x`.
 168 #[test]
 169 fn unify_key_None_val() {
 170     let mut ut: UnificationTable<IntKey> = UnificationTable::new();
 171     let k1 = ut.new_key(None);
 172     assert!(ut.unify_var_value(k1, 22).is_ok());
 173     assert_eq!(ut.probe(k1), Some(22));
 174 }
 175
 176 /// Test unifying a key whose value is `Some(x)` with the value `y`.
 177 /// This should yield an error.
 178 #[test]
 179 fn unify_key_Some_x_val_y() {
 180     let mut ut: UnificationTable<IntKey> = UnificationTable::new();
 181     let k1 = ut.new_key(Some(22));
 182     assert_eq!(ut.unify_var_value(k1, 23), Err((22, 23)));
 183     assert_eq!(ut.probe(k1), Some(22));
 184 }
 185
 186 /// Test unifying a key whose value is `Some(x)` with the value `x`.
 187 /// This should be ok.
 188 #[test]
 189 fn unify_key_Some_x_val_x() {
 190     let mut ut: UnificationTable<IntKey> = UnificationTable::new();
 191     let k1 = ut.new_key(Some(22));
 192     assert!(ut.unify_var_value(k1, 22).is_ok());
 193     assert_eq!(ut.probe(k1), Some(22));
 194 }
 195