Skip to main content

qualia_core_db/net/qdnf/resolve/qsr/
traversal.rs

1//! Closed-world exact lookup against an immutable local QSR snapshot.
2//!
3//! Compares the full 48-byte key. First-byte equality is not membership.
4//! `key.0[0] % 96` is not used.
5
6use super::cover::{covers_digit, validate_cover, CoverInterval};
7use super::key::{digit, keys_equal};
8use super::outcome::QsrOutcome;
9use crate::net::qdnf::errors::QdnfError;
10use crate::net::qdnf::types::{Generation, StrongDigest};
11
12/// Occupied slots in a closed-world local map.
13pub const SNAPSHOT_CAP: usize = 32;
14
15/// Immutable generation-pinned map of exact key → target digest pairs.
16#[repr(C)]
17#[derive(Clone, Copy, Debug)]
18pub struct QsrSnapshot {
19    keys: [StrongDigest; SNAPSHOT_CAP],
20    values: [StrongDigest; SNAPSHOT_CAP],
21    len: u8,
22    generation: Generation,
23}
24
25impl QsrSnapshot {
26    /// Empty value.
27    pub const fn empty(generation: Generation) -> Self {
28        Self {
29            keys: [StrongDigest::ZERO; SNAPSHOT_CAP],
30            values: [StrongDigest::ZERO; SNAPSHOT_CAP],
31            len: 0,
32            generation,
33        }
34    }
35
36    #[inline]
37    /// `QsrSnapshot::len`.
38    pub const fn len(&self) -> usize {
39        self.len as usize
40    }
41
42    #[inline]
43    /// Generation.
44    pub const fn generation(&self) -> Generation {
45        self.generation
46    }
47
48    /// Append a pair. Duplicate keys are retained so conflict detection can fire.
49    pub fn insert(&mut self, key: StrongDigest, value: StrongDigest) -> Result<(), QdnfError> {
50        if self.len as usize >= SNAPSHOT_CAP {
51            return Err(QdnfError::Capacity);
52        }
53        let i = self.len as usize;
54        self.keys[i] = key;
55        self.values[i] = value;
56        self.len = self.len + 1;
57        Ok(())
58    }
59
60    /// Occupied `(key, value)` at insert index `i`. Read-only; not a membership answer.
61    #[inline]
62    pub fn pair_at(&self, i: usize) -> Option<(StrongDigest, StrongDigest)> {
63        if i >= self.len as usize {
64            return None;
65        }
66        Some((self.keys[i], self.values[i]))
67    }
68}
69
70/// Exact lookup. Copies matching targets into `out` when `Found`.
71pub fn lookup_into(
72    snapshot: &QsrSnapshot,
73    key: &StrongDigest,
74    covers: &[CoverInterval],
75    required_generation: Generation,
76    out: &mut [StrongDigest],
77) -> Result<QsrOutcome, QdnfError> {
78    validate_cover(covers)?;
79    if required_generation != snapshot.generation && required_generation != Generation(0) {
80        return Ok(QsrOutcome::Stale);
81    }
82    let d0 = digit(key, 0)?;
83    if !covers_digit(covers, d0) {
84        return Ok(QsrOutcome::Incomplete);
85    }
86
87    let occupied = snapshot.len as usize;
88    let mut match_i = usize::MAX;
89    let mut match_n: u8 = 0;
90    let mut conflict = false;
91    let mut i = 0usize;
92    while i < occupied {
93        if keys_equal(&snapshot.keys[i], key) {
94            if match_n == 0 {
95                match_i = i;
96                match_n = 1;
97            } else if !keys_equal(&snapshot.values[i], &snapshot.values[match_i]) {
98                conflict = true;
99            } else if match_n < 64 {
100                match_n = match_n + 1;
101            }
102        }
103        i += 1;
104    }
105
106    if conflict {
107        return Ok(QsrOutcome::Conflict);
108    }
109    if match_n == 0 {
110        return Ok(QsrOutcome::EmptyInSnapshot);
111    }
112    if out.is_empty() {
113        return Ok(QsrOutcome::NeedContinuation);
114    }
115    out[0] = snapshot.values[match_i];
116    Ok(QsrOutcome::Found { count: 1 })
117}
118
119/// Exact lookup using a one-slot stack buffer for the target copy.
120pub fn lookup(
121    snapshot: &QsrSnapshot,
122    key: &StrongDigest,
123    covers: &[CoverInterval],
124    required_generation: Generation,
125) -> Result<QsrOutcome, QdnfError> {
126    let mut slot = [StrongDigest::ZERO; 1];
127    lookup_into(snapshot, key, covers, required_generation, &mut slot)
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133    use crate::net::qdnf::resolve::qsr::key::KEY_DEPTH;
134
135    fn key_same_first_byte(rest: u8) -> StrongDigest {
136        let mut k = StrongDigest::ZERO;
137        k.0[0] = 0x10;
138        let mut i = 1usize;
139        while i < 48 {
140            k.0[i] = rest;
141            i += 1;
142        }
143        k
144    }
145
146    fn full_cover() -> [CoverInterval; 1] {
147        [CoverInterval { start: 0, end: 15 }]
148    }
149
150    #[test]
151    fn shared_first_byte_is_distinguished_by_full_key() {
152        let a = key_same_first_byte(0x01);
153        let b = key_same_first_byte(0x02);
154        assert_eq!(a.0[0], b.0[0]);
155        assert_eq!(a.0[0] % KEY_DEPTH as u8, b.0[0] % KEY_DEPTH as u8);
156
157        let mut snap = QsrSnapshot::empty(Generation(1));
158        snap.insert(a, StrongDigest::ZERO).unwrap();
159        let covers = full_cover();
160
161        assert_eq!(
162            lookup(&snap, &a, &covers, Generation(1)),
163            Ok(QsrOutcome::Found { count: 1 })
164        );
165        assert_eq!(
166            lookup(&snap, &b, &covers, Generation(1)),
167            Ok(QsrOutcome::EmptyInSnapshot)
168        );
169    }
170
171    #[test]
172    fn first_byte_modulo_must_not_succeed() {
173        let a = key_same_first_byte(0xaa);
174        let b = key_same_first_byte(0xbb);
175        assert_eq!(a.0[0] % 96, b.0[0] % 96);
176
177        let mut snap = QsrSnapshot::empty(Generation(1));
178        snap.insert(a, StrongDigest::ZERO).unwrap();
179        let covers = full_cover();
180
181        assert_eq!(
182            lookup(&snap, &b, &covers, Generation(0)),
183            Ok(QsrOutcome::EmptyInSnapshot)
184        );
185        assert_ne!(
186            lookup(&snap, &b, &covers, Generation(0)),
187            Ok(QsrOutcome::Found { count: 1 })
188        );
189    }
190
191    #[test]
192    fn stale_generation_is_stale() {
193        let mut snap = QsrSnapshot::empty(Generation(2));
194        snap.insert(StrongDigest::ZERO, StrongDigest::ZERO).unwrap();
195        let covers = full_cover();
196        assert_eq!(
197            lookup(&snap, &StrongDigest::ZERO, &covers, Generation(1)),
198            Ok(QsrOutcome::Stale)
199        );
200        assert_eq!(
201            lookup(&snap, &StrongDigest::ZERO, &covers, Generation(0)),
202            Ok(QsrOutcome::Found { count: 1 })
203        );
204    }
205
206    #[test]
207    fn empty_snapshot_full_cover_is_empty_in_snapshot() {
208        let snap = QsrSnapshot::empty(Generation(1));
209        let covers = full_cover();
210        assert_eq!(
211            lookup(&snap, &StrongDigest::ZERO, &covers, Generation(1)),
212            Ok(QsrOutcome::EmptyInSnapshot)
213        );
214        assert_ne!(
215            lookup(&snap, &StrongDigest::ZERO, &covers, Generation(1)),
216            Ok(QsrOutcome::Found { count: 1 })
217        );
218    }
219
220    #[test]
221    fn overlapping_cover_is_rejected_before_lookup() {
222        let snap = QsrSnapshot::empty(Generation(0));
223        let covers = [
224            CoverInterval { start: 0, end: 10 },
225            CoverInterval { start: 8, end: 12 },
226        ];
227        assert_eq!(
228            lookup(&snap, &StrongDigest::ZERO, &covers, Generation(0)),
229            Err(QdnfError::Overlap)
230        );
231    }
232
233    #[test]
234    fn lookup_copies_target_into_caller_buffer() {
235        let mut key = StrongDigest::ZERO;
236        key.0[0] = 0x20;
237        let mut target = StrongDigest::ZERO;
238        target.0[47] = 0x77;
239        let mut snap = QsrSnapshot::empty(Generation(3));
240        snap.insert(key, target).unwrap();
241        let covers = full_cover();
242        let mut out = [StrongDigest::ZERO; 1];
243        assert_eq!(
244            lookup_into(&snap, &key, &covers, Generation(3), &mut out),
245            Ok(QsrOutcome::Found { count: 1 })
246        );
247        assert!(keys_equal(&out[0], &target));
248    }
249
250    #[test]
251    fn duplicate_key_conflicting_values_are_conflict() {
252        let key = StrongDigest::ZERO;
253        let mut v1 = StrongDigest::ZERO;
254        let mut v2 = StrongDigest::ZERO;
255        v1.0[0] = 1;
256        v2.0[0] = 2;
257        let mut snap = QsrSnapshot::empty(Generation(1));
258        snap.insert(key, v1).unwrap();
259        snap.insert(key, v2).unwrap();
260        assert_eq!(
261            lookup(&snap, &key, &full_cover(), Generation(1)),
262            Ok(QsrOutcome::Conflict)
263        );
264    }
265}