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