Skip to main content

qualia_core_db/net/peer/replication/
tombstone.rs

1//! Tombstones retained until an authorized ack frontier (SVC-01.11 partial).
2//!
3//! A tombstone is not a completeness proof that every replica compacted. A
4//! stale returning replica cannot contribute until reauthorize/resnapshot.
5//! Transport ACK is not an authorized frontier. Packages remain open.
6
7use crate::net::qdnf::errors::QdnfError;
8use crate::net::qdnf::types::StrongDigest;
9
10pub const MAX_TOMBSTONES: usize = 16;
11
12#[repr(C)]
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub struct Tombstone {
15    pub op_id: StrongDigest,
16    pub epoch: u64,
17    pub sequence: u32,
18}
19
20#[derive(Clone, Copy)]
21struct Slot {
22    occupied: bool,
23    ts: Tombstone,
24}
25
26/// Replica contribution gate. Stale until [`ReplicaGate::reauthorize`].
27#[repr(u8)]
28#[derive(Clone, Copy, Debug, PartialEq, Eq)]
29pub enum ReplicaStatus {
30    Authorized = 1,
31    Stale = 2,
32}
33
34pub struct TombstoneTable {
35    slots: [Slot; MAX_TOMBSTONES],
36    /// Exclusive: sequences `< frontier_seq` in `frontier_epoch` may compact
37    /// when `has_frontier` is set. Epoch exclusion: `epoch < excluded_before`.
38    has_frontier: bool,
39    frontier_epoch: u64,
40    frontier_seq: u32,
41    excluded_before: u64,
42}
43
44pub struct ReplicaGate {
45    status: ReplicaStatus,
46}
47
48impl TombstoneTable {
49    /// Creates a default `TombstoneTable`.
50    pub const fn new() -> Self {
51        Self {
52            slots: [Slot {
53                occupied: false,
54                ts: Tombstone {
55                    op_id: StrongDigest::ZERO,
56                    epoch: 0,
57                    sequence: 0,
58                },
59            }; MAX_TOMBSTONES],
60            has_frontier: false,
61            frontier_epoch: 0,
62            frontier_seq: 0,
63            excluded_before: 0,
64        }
65    }
66
67    /// Retains a tombstone entry; `QdnfError` at capacity or on duplicates.
68    pub fn retain(&mut self, ts: Tombstone) -> Result<(), QdnfError> {
69        if ts.op_id == StrongDigest::ZERO {
70            return Err(QdnfError::Malformed);
71        }
72        if self.find_id(&ts.op_id).is_some() {
73            return Ok(());
74        }
75        let idx = self.find_free().ok_or(QdnfError::Capacity)?;
76        self.slots[idx] = Slot { occupied: true, ts };
77        Ok(())
78    }
79
80    /// Number of live tombstone slots.
81    pub fn occupied_count(&self) -> usize {
82        let mut n = 0usize;
83        let mut i = 0usize;
84        while i < MAX_TOMBSTONES {
85            if self.slots[i].occupied {
86                n += 1;
87            }
88            i += 1;
89        }
90        n
91    }
92
93    /// Transport ACK is not an authorized compaction frontier.
94    pub fn apply_transport_ack(&mut self, _op_id: StrongDigest) -> Result<(), QdnfError> {
95        Err(QdnfError::Unauthorized)
96    }
97
98    /// Authorized ack frontier. Compacts matching retained tombstones.
99    pub fn apply_authorized_frontier(
100        &mut self,
101        epoch: u64,
102        sequence: u32,
103    ) -> Result<usize, QdnfError> {
104        self.has_frontier = true;
105        self.frontier_epoch = epoch;
106        self.frontier_seq = sequence;
107        Ok(self.compact())
108    }
109
110    /// Explicit epoch exclusion: tombstones with `epoch < excluded_before` compact.
111    pub fn apply_epoch_exclusion(&mut self, excluded_before: u64) -> Result<usize, QdnfError> {
112        self.excluded_before = excluded_before;
113        Ok(self.compact())
114    }
115
116    /// `true` when `op_id` has a tombstone.
117    pub fn contains(&self, op_id: &StrongDigest) -> bool {
118        self.find_id(op_id).is_some()
119    }
120
121    fn compact(&mut self) -> usize {
122        let mut released = 0usize;
123        let mut i = 0usize;
124        while i < MAX_TOMBSTONES {
125            if self.slots[i].occupied && self.may_compact(&self.slots[i].ts) {
126                self.slots[i].occupied = false;
127                released += 1;
128            }
129            i += 1;
130        }
131        released
132    }
133
134    fn may_compact(&self, ts: &Tombstone) -> bool {
135        if ts.epoch < self.excluded_before {
136            return true;
137        }
138        self.has_frontier && ts.epoch == self.frontier_epoch && ts.sequence < self.frontier_seq
139    }
140
141    fn find_id(&self, id: &StrongDigest) -> Option<usize> {
142        let mut i = 0usize;
143        while i < MAX_TOMBSTONES {
144            if self.slots[i].occupied && self.slots[i].ts.op_id == *id {
145                return Some(i);
146            }
147            i += 1;
148        }
149        None
150    }
151
152    fn find_free(&self) -> Option<usize> {
153        let mut i = 0usize;
154        while i < MAX_TOMBSTONES {
155            if !self.slots[i].occupied {
156                return Some(i);
157            }
158            i += 1;
159        }
160        None
161    }
162}
163
164impl Default for TombstoneTable {
165    fn default() -> Self {
166        Self::new()
167    }
168}
169
170impl ReplicaGate {
171    /// `ReplicaGate::authorized`.
172    pub const fn authorized() -> Self {
173        Self {
174            status: ReplicaStatus::Authorized,
175        }
176    }
177
178    /// `ReplicaGate::stale`.
179    pub const fn stale() -> Self {
180        Self {
181            status: ReplicaStatus::Stale,
182        }
183    }
184
185    /// Contributes this replica's gate state; `QdnfError` when stale/unauthorized.
186    pub fn contribute(&self) -> Result<(), QdnfError> {
187        match self.status {
188            ReplicaStatus::Authorized => Ok(()),
189            ReplicaStatus::Stale => Err(QdnfError::Unauthorized),
190        }
191    }
192
193    /// Marks the gate stale — contributions rejected until reauthorized.
194    pub fn mark_stale(&mut self) {
195        self.status = ReplicaStatus::Stale;
196    }
197
198    /// Clears the stale flag after re-authorization.
199    pub fn reauthorize(&mut self) {
200        self.status = ReplicaStatus::Authorized;
201    }
202}
203
204/// Honest capability probe: `false` — per-replica tombstones do not imply global completeness.
205pub fn tombstone_implies_global_completeness() -> bool {
206    false
207}
208
209/// Honest capability probe: `false` — transport acks are not compaction frontiers.
210pub fn transport_ack_is_compaction_frontier() -> bool {
211    false
212}
213
214#[cfg(test)]
215mod tests {
216    use super::*;
217
218    fn ts(seq: u32) -> Tombstone {
219        let mut id = StrongDigest::ZERO;
220        id.0[0] = seq as u8;
221        id.0[1] = 0x7a;
222        Tombstone {
223            op_id: id,
224            epoch: 1,
225            sequence: seq,
226        }
227    }
228
229    #[test]
230    fn retain_until_authorized_frontier() {
231        let mut table = TombstoneTable::new();
232        table.retain(ts(1)).unwrap();
233        table.retain(ts(2)).unwrap();
234        assert_eq!(table.occupied_count(), 2);
235        assert_eq!(
236            table.apply_transport_ack(ts(1).op_id),
237            Err(QdnfError::Unauthorized)
238        );
239        assert_eq!(table.occupied_count(), 2);
240        let released = table.apply_authorized_frontier(1, 2).unwrap();
241        assert_eq!(released, 1);
242        assert!(table.contains(&ts(2).op_id));
243        assert!(!table.contains(&ts(1).op_id));
244    }
245
246    #[test]
247    fn epoch_exclusion_compacts_older_epoch() {
248        let mut table = TombstoneTable::new();
249        let mut old = ts(1);
250        old.epoch = 3;
251        let mut keep = ts(9);
252        keep.epoch = 5;
253        table.retain(old).unwrap();
254        table.retain(keep).unwrap();
255        let n = table.apply_epoch_exclusion(4).unwrap();
256        assert_eq!(n, 1);
257        assert!(table.contains(&keep.op_id));
258        assert!(!table.contains(&old.op_id));
259    }
260
261    #[test]
262    fn seventeenth_retain_is_capacity() {
263        let mut table = TombstoneTable::new();
264        let mut i = 1u32;
265        while i <= MAX_TOMBSTONES as u32 {
266            table.retain(ts(i)).unwrap();
267            i += 1;
268        }
269        assert_eq!(table.retain(ts(99)), Err(QdnfError::Capacity));
270    }
271
272    #[test]
273    fn stale_replica_cannot_contribute_until_reauthorize() {
274        let mut gate = ReplicaGate::stale();
275        assert_eq!(gate.contribute(), Err(QdnfError::Unauthorized));
276        gate.reauthorize();
277        gate.contribute().unwrap();
278        gate.mark_stale();
279        assert_eq!(gate.contribute(), Err(QdnfError::Unauthorized));
280    }
281
282    #[test]
283    fn completeness_and_transport_ack_are_not_frontiers() {
284        assert!(!tombstone_implies_global_completeness());
285        assert!(!transport_ack_is_compaction_frontier());
286    }
287}