1use super::{Crdt, Mergeable};
6use alloc::vec::Vec;
7
8#[derive(Clone, Copy, Debug, PartialEq, Eq)]
9pub enum Law {
10 Commutative,
11 Associative,
12 Idempotent,
13 Identity,
14 Convergence,
15}
16
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub struct LawFailure {
19 pub law: Law,
20 pub a: usize,
21 pub b: Option<usize>,
22 pub c: Option<usize>,
23}
24
25#[derive(Clone, Copy, Debug, PartialEq, Eq)]
26pub struct LawReport {
27 pub scenarios: usize,
28}
29
30pub fn check_merge_laws<T>(identity: &T, samples: &[T]) -> Result<LawReport, LawFailure>
31where
32 T: Mergeable + Clone + PartialEq,
33{
34 let mut scenarios = 0;
35
36 for (a_idx, a) in samples.iter().enumerate() {
37 let mut aa = a.clone();
38 aa.merge(a).map_err(|_| LawFailure {
39 law: Law::Idempotent,
40 a: a_idx,
41 b: None,
42 c: None,
43 })?;
44 scenarios += 1;
45 if aa != *a {
46 return Err(LawFailure {
47 law: Law::Idempotent,
48 a: a_idx,
49 b: None,
50 c: None,
51 });
52 }
53
54 let mut left_identity = identity.clone();
55 left_identity.merge(a).map_err(|_| LawFailure {
56 law: Law::Identity,
57 a: a_idx,
58 b: None,
59 c: None,
60 })?;
61 let mut right_identity = a.clone();
62 right_identity.merge(identity).map_err(|_| LawFailure {
63 law: Law::Identity,
64 a: a_idx,
65 b: None,
66 c: None,
67 })?;
68 scenarios += 2;
69 if left_identity != *a || right_identity != *a {
70 return Err(LawFailure {
71 law: Law::Identity,
72 a: a_idx,
73 b: None,
74 c: None,
75 });
76 }
77
78 for (b_idx, b) in samples.iter().enumerate() {
79 let mut ab = a.clone();
80 ab.merge(b).map_err(|_| LawFailure {
81 law: Law::Commutative,
82 a: a_idx,
83 b: Some(b_idx),
84 c: None,
85 })?;
86 let mut ba = b.clone();
87 ba.merge(a).map_err(|_| LawFailure {
88 law: Law::Commutative,
89 a: a_idx,
90 b: Some(b_idx),
91 c: None,
92 })?;
93 scenarios += 1;
94 if ab != ba {
95 return Err(LawFailure {
96 law: Law::Commutative,
97 a: a_idx,
98 b: Some(b_idx),
99 c: None,
100 });
101 }
102
103 for (c_idx, c) in samples.iter().enumerate() {
104 let mut left = a.clone();
105 left.merge(b).map_err(|_| LawFailure {
106 law: Law::Associative,
107 a: a_idx,
108 b: Some(b_idx),
109 c: Some(c_idx),
110 })?;
111 left.merge(c).map_err(|_| LawFailure {
112 law: Law::Associative,
113 a: a_idx,
114 b: Some(b_idx),
115 c: Some(c_idx),
116 })?;
117
118 let mut right_inner = b.clone();
119 right_inner.merge(c).map_err(|_| LawFailure {
120 law: Law::Associative,
121 a: a_idx,
122 b: Some(b_idx),
123 c: Some(c_idx),
124 })?;
125 let mut right = a.clone();
126 right.merge(&right_inner).map_err(|_| LawFailure {
127 law: Law::Associative,
128 a: a_idx,
129 b: Some(b_idx),
130 c: Some(c_idx),
131 })?;
132
133 scenarios += 1;
134 if left != right {
135 return Err(LawFailure {
136 law: Law::Associative,
137 a: a_idx,
138 b: Some(b_idx),
139 c: Some(c_idx),
140 });
141 }
142 }
143 }
144 }
145
146 Ok(LawReport { scenarios })
147}
148
149pub fn check_crdt_convergence<C>(
150 seed_state: &C,
151 deltas: &[C::Delta],
152) -> Result<LawReport, LawFailure>
153where
154 C: Crdt + Clone + PartialEq,
155 C::Delta: Clone,
156{
157 let expected = apply_all(seed_state, deltas.iter().cloned());
158 let mut scenarios = 1;
159
160 let reverse = apply_all(seed_state, deltas.iter().cloned().rev());
161 scenarios += 1;
162 if reverse != expected {
163 return Err(convergence_failure(0));
164 }
165
166 let duplicated = apply_all(
167 seed_state,
168 deltas.iter().cloned().flat_map(|d| [d.clone(), d]),
169 );
170 scenarios += 1;
171 if duplicated != expected {
172 return Err(convergence_failure(1));
173 }
174
175 for (seed_idx, seed) in [0x51a7_3eed_u64, 0xc0ff_ee13_u64, 0x5afe_0001_u64]
176 .iter()
177 .copied()
178 .enumerate()
179 {
180 let shuffled = shuffled(deltas, seed);
181 let shuffled_state = apply_all(seed_state, shuffled);
182 scenarios += 1;
183 if shuffled_state != expected {
184 return Err(convergence_failure(2 + seed_idx));
185 }
186 }
187
188 let mut even = seed_state.clone();
189 let mut odd = seed_state.clone();
190 for (idx, delta) in deltas.iter().cloned().enumerate() {
191 if idx % 2 == 0 {
192 even.apply_delta(delta);
193 } else {
194 odd.apply_delta(delta);
195 }
196 }
197 even.merge(&odd).map_err(|_| convergence_failure(5))?;
198 scenarios += 1;
199 if even != expected {
200 return Err(convergence_failure(5));
201 }
202
203 let mut lossy_a = seed_state.clone();
204 let mut lossy_b = seed_state.clone();
205 for (idx, delta) in deltas.iter().cloned().enumerate() {
206 if idx % 3 == 0 {
207 lossy_b.apply_delta(delta);
208 } else {
209 lossy_a.apply_delta(delta);
210 }
211 }
212 lossy_a
213 .merge(&lossy_b)
214 .map_err(|_| convergence_failure(6))?;
215 scenarios += 1;
216 if lossy_a != expected {
217 return Err(convergence_failure(6));
218 }
219
220 Ok(LawReport { scenarios })
221}
222
223fn apply_all<C, I>(seed_state: &C, deltas: I) -> C
224where
225 C: Crdt + Clone,
226 I: IntoIterator<Item = C::Delta>,
227{
228 let mut state = seed_state.clone();
229 for delta in deltas {
230 state.apply_delta(delta);
231 }
232 state
233}
234
235fn convergence_failure(a: usize) -> LawFailure {
236 LawFailure {
237 law: Law::Convergence,
238 a,
239 b: None,
240 c: None,
241 }
242}
243
244fn shuffled<T: Clone>(items: &[T], seed: u64) -> Vec<T> {
245 let mut out = items.to_vec();
246 let mut rng = XorShift64::new(seed);
247 let len = out.len();
248 if len < 2 {
249 return out;
250 }
251 let mut i = len - 1;
252 while i > 0 {
253 let j = rng.next_usize(i + 1);
254 out.swap(i, j);
255 i -= 1;
256 }
257 out
258}
259
260struct XorShift64 {
261 state: u64,
262}
263
264impl XorShift64 {
265 fn new(seed: u64) -> Self {
266 let state = if seed == 0 {
267 0x9e37_79b9_7f4a_7c15
268 } else {
269 seed
270 };
271 XorShift64 { state }
272 }
273
274 fn next_u64(&mut self) -> u64 {
275 let mut x = self.state;
276 x ^= x << 13;
277 x ^= x >> 7;
278 x ^= x << 17;
279 self.state = x;
280 x
281 }
282
283 fn next_usize(&mut self, upper: usize) -> usize {
284 (self.next_u64() as usize) % upper
285 }
286}