Joel Galenson | 2370d12 | 2020-10-12 16:02:26 -0700 | [diff] [blame] | 1 | use std::collections::HashMap; |
| 2 | use std::fmt::Debug; |
| 3 | use std::hash::Hash; |
| 4 | use std::rc::{Rc, Weak}; |
| 5 | |
Joel Galenson | 2370d12 | 2020-10-12 16:02:26 -0700 | [diff] [blame] | 6 | use quickcheck::{Arbitrary, Gen, quickcheck}; |
| 7 | |
| 8 | use weak_table::WeakKeyHashMap; |
| 9 | |
| 10 | use self::Cmd::*; |
| 11 | |
| 12 | 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 | { |
| 55 | pub fn new() -> Self { |
| 56 | Tester::with_capacity(8) |
| 57 | } |
| 58 | |
| 59 | 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 | |
| 67 | 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 118 | pub fn remove_other(&mut self, key: &K) { |
| 119 | self.strong.remove(key); |
| 120 | self.weak.remove(key); |
| 121 | } |
| 122 | |
| 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 | |
| 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> { |
David LeGare | 77e4bb9 | 2022-03-02 16:21:23 +0000 | [diff] [blame] | 140 | fn arbitrary(g: &mut Gen) -> Self { |
| 141 | let choice = u8::arbitrary(g); |
Joel Galenson | 2370d12 | 2020-10-12 16:02:26 -0700 | [diff] [blame] | 142 | |
David LeGare | 77e4bb9 | 2022-03-02 16:21:23 +0000 | [diff] [blame] | 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)), |
Joel Galenson | 2370d12 | 2020-10-12 16:02:26 -0700 | [diff] [blame] | 149 | _ => unreachable!(), |
| 150 | } |
| 151 | } |
| 152 | } |
| 153 | |
| 154 | impl<K: Arbitrary, V: Arbitrary> Arbitrary for Script<K, V> { |
David LeGare | 77e4bb9 | 2022-03-02 16:21:23 +0000 | [diff] [blame] | 155 | fn arbitrary(g: &mut Gen) -> Self { |
Joel Galenson | 2370d12 | 2020-10-12 16:02:26 -0700 | [diff] [blame] | 156 | Script(Vec::<Cmd<K, V>>::arbitrary(g)) |
| 157 | } |
| 158 | |
| 159 | fn shrink(&self) -> Box<dyn Iterator<Item=Self>> { |
| 160 | Box::new(self.0.shrink().map(|v| Script(v))) |
| 161 | } |
| 162 | } |