qualia_core_db/net/peer/replication/
merge.rs1use crate::net::qdnf::errors::QdnfError;
9use crate::net::qdnf::types::StrongDigest;
10
11pub const MAX_ALTERNATIVES: usize = 4;
12
13#[repr(u8)]
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub enum MergeProfile {
19 ConcurrentRetain = 1,
20 LwwHint = 2,
21}
22
23#[repr(C)]
25#[derive(Clone, Copy, Debug, PartialEq, Eq)]
26pub struct Alternate {
27 pub op_id: StrongDigest,
28 pub lamport: u64,
29}
30
31#[derive(Clone, Copy)]
32struct Slot {
33 occupied: bool,
34 alt: Alternate,
35}
36
37pub struct MergeSet {
39 slots: [Slot; MAX_ALTERNATIVES],
40}
41
42impl MergeSet {
43 pub const fn new() -> Self {
45 Self {
46 slots: [Slot {
47 occupied: false,
48 alt: Alternate {
49 op_id: StrongDigest::ZERO,
50 lamport: 0,
51 },
52 }; MAX_ALTERNATIVES],
53 }
54 }
55
56 pub fn insert(&mut self, alt: Alternate, revoked: bool) -> Result<(), QdnfError> {
62 if revoked {
63 return Err(QdnfError::Revoked);
64 }
65 if self.find_id(&alt.op_id).is_some() {
66 return Ok(());
67 }
68 let idx = self.find_free().ok_or(QdnfError::Capacity)?;
69 self.slots[idx] = Slot {
70 occupied: true,
71 alt,
72 };
73 Ok(())
74 }
75
76 pub fn len(&self) -> usize {
78 let mut n = 0usize;
79 let mut i = 0usize;
80 while i < MAX_ALTERNATIVES {
81 if self.slots[i].occupied {
82 n += 1;
83 }
84 i += 1;
85 }
86 n
87 }
88
89 pub fn is_empty(&self) -> bool {
91 self.len() == 0
92 }
93
94 fn find_id(&self, id: &StrongDigest) -> Option<usize> {
95 let mut i = 0usize;
96 while i < MAX_ALTERNATIVES {
97 if self.slots[i].occupied && self.slots[i].alt.op_id == *id {
98 return Some(i);
99 }
100 i += 1;
101 }
102 None
103 }
104
105 fn find_free(&self) -> Option<usize> {
106 let mut i = 0usize;
107 while i < MAX_ALTERNATIVES {
108 if !self.slots[i].occupied {
109 return Some(i);
110 }
111 i += 1;
112 }
113 None
114 }
115
116 fn first_occupied(&self) -> Option<StrongDigest> {
117 let mut i = 0usize;
118 while i < MAX_ALTERNATIVES {
119 if self.slots[i].occupied {
120 return Some(self.slots[i].alt.op_id);
121 }
122 i += 1;
123 }
124 None
125 }
126}
127
128impl Default for MergeSet {
129 fn default() -> Self {
130 Self::new()
131 }
132}
133
134pub fn lww_overrides_revocation() -> bool {
136 false
137}
138
139pub fn wall_clock_is_membership_authority() -> bool {
141 false
142}
143
144pub fn decide(set: &MergeSet, profile: MergeProfile) -> Result<StrongDigest, QdnfError> {
150 match set.len() {
151 0 => Err(QdnfError::Unauthorized),
152 1 => set.first_occupied().ok_or(QdnfError::Unauthorized),
153 _ => match profile {
154 MergeProfile::ConcurrentRetain | MergeProfile::LwwHint => Err(QdnfError::Conflict),
155 },
156 }
157}
158
159#[cfg(test)]
160mod tests {
161 use super::*;
162
163 fn alt(tag: u8, lamport: u64) -> Alternate {
164 let mut id = StrongDigest::ZERO;
165 id.0[0] = tag;
166 Alternate { op_id: id, lamport }
167 }
168
169 #[test]
170 fn lww_and_wall_clock_are_not_authority() {
171 assert!(!lww_overrides_revocation());
172 assert!(!wall_clock_is_membership_authority());
173 }
174
175 #[test]
176 fn insert_four_ok_fifth_is_capacity() {
177 let mut set = MergeSet::new();
178 let mut i = 1u8;
179 while i <= MAX_ALTERNATIVES as u8 {
180 set.insert(alt(i, u64::from(i) * 10), false).unwrap();
181 i += 1;
182 }
183 assert_eq!(set.len(), MAX_ALTERNATIVES);
184 assert_eq!(set.insert(alt(99, 1), false), Err(QdnfError::Capacity));
185 assert_eq!(set.len(), MAX_ALTERNATIVES);
186 }
187
188 #[test]
189 fn insert_revoked_is_revoked_len_unchanged() {
190 let mut set = MergeSet::new();
191 set.insert(alt(1, 5), false).unwrap();
192 assert_eq!(set.len(), 1);
193 assert_eq!(set.insert(alt(2, 99), true), Err(QdnfError::Revoked));
194 assert_eq!(set.len(), 1);
195 assert_eq!(
196 decide(&set, MergeProfile::ConcurrentRetain).unwrap(),
197 alt(1, 5).op_id
198 );
199 }
200
201 #[test]
202 fn concurrent_retain_two_alts_is_conflict() {
203 let mut set = MergeSet::new();
204 set.insert(alt(1, 1), false).unwrap();
205 set.insert(alt(2, 9), false).unwrap();
206 assert_eq!(set.len(), 2);
207 assert_eq!(
208 decide(&set, MergeProfile::ConcurrentRetain),
209 Err(QdnfError::Conflict)
210 );
211 }
212
213 #[test]
214 fn single_alt_concurrent_retain_is_ok() {
215 let mut set = MergeSet::new();
216 assert_eq!(
217 decide(&set, MergeProfile::ConcurrentRetain),
218 Err(QdnfError::Unauthorized)
219 );
220 set.insert(alt(7, 3), false).unwrap();
221 assert_eq!(
222 decide(&set, MergeProfile::ConcurrentRetain).unwrap(),
223 alt(7, 3).op_id
224 );
225 }
226
227 #[test]
228 fn lww_hint_two_alts_is_still_conflict() {
229 let mut set = MergeSet::new();
230 set.insert(alt(1, 1), false).unwrap();
231 set.insert(alt(2, 100), false).unwrap();
232 assert_eq!(
233 decide(&set, MergeProfile::LwwHint),
234 Err(QdnfError::Conflict)
235 );
236 let mut one = MergeSet::new();
237 one.insert(alt(3, 0), false).unwrap();
238 assert_eq!(
239 decide(&one, MergeProfile::LwwHint).unwrap(),
240 alt(3, 0).op_id
241 );
242 }
243
244 #[test]
245 fn duplicate_insert_is_idempotent() {
246 let mut set = MergeSet::new();
247 let a = alt(4, 1);
248 set.insert(a, false).unwrap();
249 set.insert(
250 Alternate {
251 op_id: a.op_id,
252 lamport: 50,
253 },
254 false,
255 )
256 .unwrap();
257 assert_eq!(set.len(), 1);
258 assert_eq!(
259 decide(&set, MergeProfile::ConcurrentRetain).unwrap(),
260 a.op_id
261 );
262 }
263}