Skip to main content

qualia_core_db/net/peer/replication/
merge.rs

1//! Dataset merge/conflict: retain concurrent alternatives (SVC-01.10 partial).
2//!
3//! Membership and revocation are independent of LWW and wall-clock. A Lamport
4//! field on an alternative is a hint only and never selects a winner. Two
5//! non-revoked concurrent alternatives remain both retained; [`decide`] reports
6//! [`QdnfError::Conflict`] so the caller keeps them. Packages remain open.
7
8use crate::net::qdnf::errors::QdnfError;
9use crate::net::qdnf::types::StrongDigest;
10
11pub const MAX_ALTERNATIVES: usize = 4;
12
13/// Accepted merge/conflict profile for one logical key.
14///
15/// [`MergeProfile::LwwHint`] must not drop a non-revoked concurrent alternative.
16#[repr(u8)]
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub enum MergeProfile {
19    ConcurrentRetain = 1,
20    LwwHint = 2,
21}
22
23/// One concurrent alternative for a logical key. `lamport` is never authority.
24#[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
37/// Up to [`MAX_ALTERNATIVES`] concurrent alternatives for one logical key.
38pub struct MergeSet {
39    slots: [Slot; MAX_ALTERNATIVES],
40}
41
42impl MergeSet {
43    /// Creates a default `MergeSet`.
44    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    /// Insert a non-revoked alternative. Revocation cannot be overridden by LWW.
57    ///
58    /// [`QdnfError::Revoked`] if `revoked` is true (set is unchanged).
59    /// Duplicate `op_id` is idempotent [`Ok`].
60    /// A fifth distinct id is [`QdnfError::Capacity`].
61    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    /// Number of elements.
77    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    /// `true` when empty.
90    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
134/// Last-writer-wins cannot override membership or revocation authority.
135pub fn lww_overrides_revocation() -> bool {
136    false
137}
138
139/// Wall-clock ordering is not membership authority.
140pub fn wall_clock_is_membership_authority() -> bool {
141    false
142}
143
144/// Apply `profile` to `set`. LWW/wall-clock never drop a non-revoked concurrent alt.
145///
146/// Empty set → [`QdnfError::Unauthorized`].
147/// `len > 1` → [`QdnfError::Conflict`] (retain alternatives; do not pick a winner).
148/// `len == 1` → `Ok` of that operation id, for either profile.
149pub 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}