1 use std::collections::HashMap;
2 use std::fmt::Debug;
3 use std::hash::Hash;
4 use std::rc::{Rc, Weak};
5
6 use quickcheck::{Arbitrary, Gen, quickcheck};
7
8 use weak_table::WeakKeyHashMap;
9
10 use self::Cmd::*;
11
test_script<K, V>(script: &Script<K, V>) -> bool where K: Clone + Debug + Eq + Hash, V: Clone + Debug + Eq12 fn test_script<K, V>(script: &Script<K, V>) -> bool
13 where K: Clone + Debug + Eq + Hash,
14 V: Clone + Debug + Eq
15 {
16 let mut tester = Tester::with_capacity(4);
17 tester.execute_script(script);
18 tester.check()
19 }
20
21 quickcheck! {
22 fn prop_u8_u8(script: Script<u8, u8>) -> bool {
23 test_script(&script)
24 }
25
26 fn prop_string_usize(script: Script<String, usize>) -> bool {
27 test_script(&script)
28 }
29 }
30
31 #[derive(Clone, Debug)]
32 pub enum Cmd<K, V>
33 {
34 Insert(K, V),
35 Reinsert(usize, V),
36 RemoveInserted(usize),
37 RemoveOther(K),
38 ForgetInserted(usize),
39 }
40
41 #[derive(Clone, Debug)]
42 pub struct Script<K, V>(Vec<Cmd<K, V>>);
43
44 #[derive(Clone, Debug)]
45 pub struct Tester<K: Hash + Eq, V> {
46 weak: WeakKeyHashMap<Weak<K>, V>,
47 strong: HashMap<Rc<K>, V>,
48 log: Vec<K>,
49 }
50
51 impl<K, V> Tester<K, V>
52 where K: Hash + Eq + Clone + Debug,
53 V: Eq + Clone + Debug
54 {
new() -> Self55 pub fn new() -> Self {
56 Tester::with_capacity(8)
57 }
58
with_capacity(capacity: usize) -> Self59 pub fn with_capacity(capacity: usize) -> Self {
60 Tester {
61 weak: WeakKeyHashMap::with_capacity(capacity),
62 strong: HashMap::new(),
63 log: Vec::new(),
64 }
65 }
66
check(&self) -> bool67 pub fn check(&self) -> bool {
68 let copy = self.weak.iter().map(|(k, v)| (k, v.clone())).collect();
69 if self.strong == copy {
70 // eprintln!("Tester::check: succeeded: {:?}", self.weak);
71 true
72 } else {
73 eprintln!("Tester::check: failed: {:?} ≠ {:?}", self.strong, copy);
74 false
75 }
76 }
77
execute_script(&mut self, script: &Script<K, V>)78 pub fn execute_script(&mut self, script: &Script<K, V>) {
79 // eprintln!("\n*** Starting script ***");
80 for cmd in &script.0 {
81 self.execute_command(cmd);
82 }
83 }
84
execute_command(&mut self, cmd: &Cmd<K, V>)85 pub fn execute_command(&mut self, cmd: &Cmd<K, V>) {
86 // eprintln!("Executing command: {:?}", cmd);
87 match *cmd {
88 Insert(ref k, ref v) => self.insert(k, v, true),
89 Reinsert(index, ref v) => self.reinsert(index, v),
90 RemoveInserted(index) => self.remove_inserted(index),
91 RemoveOther(ref k) => self.remove_other(k),
92 ForgetInserted(index) => self.forget_inserted(index),
93 }
94 // eprintln!("Table state: {:?}", self.weak);
95 }
96
insert(&mut self, key: &K, value: &V, log: bool)97 pub fn insert(&mut self, key: &K, value: &V, log: bool) {
98 let key_ptr = Rc::new(key.clone());
99 self.weak.insert(key_ptr.clone(), value.clone());
100 self.strong.remove(key);
101 self.strong.insert(key_ptr, value.clone());
102 if log { self.log.push(key.clone()); }
103 }
104
reinsert(&mut self, index: usize, value: &V)105 pub fn reinsert(&mut self, index: usize, value: &V) {
106 if let Some(key) = self.nth_key_mod_len(index) {
107 self.insert(&key, value, false);
108 }
109 }
110
remove_inserted(&mut self, index: usize)111 pub fn remove_inserted(&mut self, index: usize) {
112 if let Some(key) = self.nth_key_mod_len(index) {
113 self.strong.remove(&key);
114 self.weak.remove(&key);
115 }
116 }
117
remove_other(&mut self, key: &K)118 pub fn remove_other(&mut self, key: &K) {
119 self.strong.remove(key);
120 self.weak.remove(key);
121 }
122
forget_inserted(&mut self, index: usize)123 pub fn forget_inserted(&mut self, index: usize) {
124 if let Some(key) = self.nth_key_mod_len(index) {
125 self.strong.remove(&key);
126 }
127 }
128
nth_key_mod_len(&self, n: usize) -> Option<K>129 fn nth_key_mod_len(&self, n: usize) -> Option<K>
130 {
131 if self.log.is_empty() {
132 None
133 } else {
134 Some(self.log[n % self.log.len()].clone())
135 }
136 }
137 }
138
139 impl<K: Arbitrary, V: Arbitrary> Arbitrary for Cmd<K, V> {
arbitrary(g: &mut Gen) -> Self140 fn arbitrary(g: &mut Gen) -> Self {
141 let choice = u8::arbitrary(g);
142
143 match choice % 10 {
144 0..=3 => Insert(K::arbitrary(g), V::arbitrary(g)),
145 4 => Reinsert(usize::arbitrary(g), V::arbitrary(g)),
146 5..=6 => RemoveInserted(usize::arbitrary(g)),
147 7 => RemoveOther(K::arbitrary(g)),
148 8..=9 => ForgetInserted(usize::arbitrary(g)),
149 _ => unreachable!(),
150 }
151 }
152 }
153
154 impl<K: Arbitrary, V: Arbitrary> Arbitrary for Script<K, V> {
arbitrary(g: &mut Gen) -> Self155 fn arbitrary(g: &mut Gen) -> Self {
156 Script(Vec::<Cmd<K, V>>::arbitrary(g))
157 }
158
shrink(&self) -> Box<dyn Iterator<Item=Self>>159 fn shrink(&self) -> Box<dyn Iterator<Item=Self>> {
160 Box::new(self.0.shrink().map(|v| Script(v)))
161 }
162 }
163