Skip to main content

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

1//! Public staged QSR lookup: exact cover/snapshot, then tokens, then handover.
2//!
3//! [`lookup_exact`] is cover membership (`NeedContinuation` / `Incomplete`), not
4//! existence. Authenticated membership uses the snapshot. Found is membership,
5//! not completeness. Four-bit digits remain indexing only.
6
7use super::cover::{lookup_exact, CoverInterval};
8use super::handover::{lookup_via_handover, Handover};
9use super::outcome::QsrOutcome;
10use super::tokens::{lookup_private, PrivateToken};
11use super::traversal::{lookup_into, QsrSnapshot};
12use crate::net::qdnf::errors::QdnfError;
13use crate::net::qdnf::types::{Generation, StrongDigest};
14
15/// Scoped private-token stage. Admission happens before the private snapshot.
16#[derive(Clone, Copy, Debug)]
17pub struct TokenStage<'a> {
18    pub token: &'a PrivateToken,
19    pub expected: &'a PrivateToken,
20    pub snapshot: &'a QsrSnapshot,
21    pub covers: &'a [CoverInterval],
22    pub generation: Generation,
23}
24
25/// Writer-handover stage. Successor snapshot is consulted only after transfer.
26#[derive(Clone, Copy, Debug)]
27pub struct HandoverStage<'a> {
28    pub handover: &'a Handover,
29    pub snapshot: &'a QsrSnapshot,
30    pub covers: &'a [CoverInterval],
31    pub generation: Generation,
32}
33
34/// Public QSR lookup surface. `NativePeer::lookup_qsr` is cover-only
35/// [`lookup_exact`]; `NativePeer::lookup_qsr_full` calls [`Qsr::lookup`].
36pub struct Qsr;
37
38impl Qsr {
39    /// Exact cover/snapshot first, then scoped tokens, then writer handover.
40    ///
41    /// Wrong tokens are Unauthorized and do not fall through. Found does not
42    /// imply index completeness.
43    pub fn lookup(
44        key: &StrongDigest,
45        covers: &[CoverInterval],
46        snapshot: &QsrSnapshot,
47        required_generation: Generation,
48        token: Option<TokenStage<'_>>,
49        handover: Option<HandoverStage<'_>>,
50        out: &mut [StrongDigest],
51    ) -> Result<QsrOutcome, QdnfError> {
52        lookup_staged(
53            key,
54            covers,
55            snapshot,
56            required_generation,
57            token,
58            handover,
59            out,
60        )
61    }
62}
63
64/// Staged lookup.
65pub(super) fn lookup_staged(
66    key: &StrongDigest,
67    covers: &[CoverInterval],
68    snapshot: &QsrSnapshot,
69    required_generation: Generation,
70    token: Option<TokenStage<'_>>,
71    handover: Option<HandoverStage<'_>>,
72    out: &mut [StrongDigest],
73) -> Result<QsrOutcome, QdnfError> {
74    let cover = lookup_exact(key, covers)?;
75    let exact = if cover == QsrOutcome::NeedContinuation {
76        lookup_into(snapshot, key, covers, required_generation, out)?
77    } else {
78        cover
79    };
80    if terminal_membership(exact) {
81        return Ok(exact);
82    }
83
84    if let Some(stage) = token {
85        let tok = lookup_private(
86            stage.token,
87            stage.expected,
88            stage.snapshot,
89            key,
90            stage.covers,
91            stage.generation,
92            out,
93        )?;
94        if terminal_membership(tok) {
95            return Ok(tok);
96        }
97    }
98
99    if let Some(stage) = handover {
100        return lookup_via_handover(
101            stage.handover,
102            stage.snapshot,
103            key,
104            stage.covers,
105            stage.generation,
106            out,
107        );
108    }
109
110    Ok(exact)
111}
112
113fn terminal_membership(outcome: QsrOutcome) -> bool {
114    matches!(
115        outcome,
116        QsrOutcome::Found { .. }
117            | QsrOutcome::Conflict
118            | QsrOutcome::Stale
119            | QsrOutcome::NeedContinuation
120    )
121}
122
123#[cfg(test)]
124mod tests {
125    use super::super::completeness::membership_implies_completeness;
126    use super::super::handover::{
127        accept_mutation, drain_accepted, fence_old, persist_boundary, Handover,
128    };
129    use super::super::key::{digit, keys_equal, DIGIT_RADIX};
130    use super::super::tokens::issue_token;
131    use super::*;
132
133    fn key_rest(rest: u8) -> StrongDigest {
134        let mut k = StrongDigest::ZERO;
135        k.0[0] = 0x10;
136        let mut i = 1usize;
137        while i < 48 {
138            k.0[i] = rest;
139            i += 1;
140        }
141        k
142    }
143
144    fn full_cover() -> [CoverInterval; 1] {
145        [CoverInterval { start: 0, end: 15 }]
146    }
147
148    fn uncovered_first_digit() -> [CoverInterval; 1] {
149        // Depth-0 digit of `key_rest` is 0x1 (high nibble of 0x10). 2..=15 misses it.
150        [CoverInterval { start: 2, end: 15 }]
151    }
152
153    #[test]
154    fn exact_miss_token_hit() {
155        let key = key_rest(0x21);
156        assert_eq!(digit(&key, 0).unwrap(), 0x01);
157        assert_eq!(DIGIT_RADIX, 16);
158        let miss_covers = uncovered_first_digit();
159        assert_eq!(lookup_exact(&key, &miss_covers), Ok(QsrOutcome::Incomplete));
160
161        let public = QsrSnapshot::empty(Generation(1));
162        let mut private = QsrSnapshot::empty(Generation(1));
163        let mut target = StrongDigest::ZERO;
164        target.0[47] = 0x5a;
165        private.insert(key, target).unwrap();
166        let token = issue_token(&key, 4, 1);
167        let stage = TokenStage {
168            token: &token,
169            expected: &token,
170            snapshot: &private,
171            covers: &full_cover(),
172            generation: Generation(1),
173        };
174        let mut out = [StrongDigest::ZERO; 1];
175        let outcome = Qsr::lookup(
176            &key,
177            &miss_covers,
178            &public,
179            Generation(1),
180            Some(stage),
181            None,
182            &mut out,
183        )
184        .unwrap();
185        assert_eq!(outcome, QsrOutcome::Found { count: 1 });
186        assert!(keys_equal(&out[0], &target));
187        assert!(!membership_implies_completeness());
188        assert_ne!(outcome, QsrOutcome::EmptyInSnapshot);
189        assert_ne!(outcome, QsrOutcome::Incomplete);
190    }
191
192    #[test]
193    fn exact_miss_handover_hit() {
194        let key = key_rest(0x22);
195        let miss_covers = uncovered_first_digit();
196        assert_eq!(lookup_exact(&key, &miss_covers), Ok(QsrOutcome::Incomplete));
197
198        let public = QsrSnapshot::empty(Generation(2));
199        let mut successor = QsrSnapshot::empty(Generation(2));
200        let mut target = StrongDigest::ZERO;
201        target.0[0] = 0x44;
202        successor.insert(key, target).unwrap();
203
204        let mut h = Handover::start(1, 2);
205        accept_mutation(&mut h).unwrap();
206        fence_old(&mut h);
207        drain_accepted(&mut h);
208        persist_boundary(&mut h);
209
210        let stage = HandoverStage {
211            handover: &h,
212            snapshot: &successor,
213            covers: &full_cover(),
214            generation: Generation(2),
215        };
216        let mut out = [StrongDigest::ZERO; 1];
217        let outcome = super::super::lookup_qsr_full(
218            &key,
219            &miss_covers,
220            &public,
221            Generation(2),
222            None,
223            Some(stage),
224            &mut out,
225        )
226        .unwrap();
227        assert_eq!(outcome, QsrOutcome::Found { count: 1 });
228        assert!(keys_equal(&out[0], &target));
229        assert!(!membership_implies_completeness());
230    }
231
232    #[test]
233    fn wrong_token_does_not_fall_through_to_handover() {
234        let key = key_rest(0x23);
235        let miss_covers = uncovered_first_digit();
236        let public = QsrSnapshot::empty(Generation(1));
237        let mut private = QsrSnapshot::empty(Generation(1));
238        private.insert(key, StrongDigest::ZERO).unwrap();
239        let expected = issue_token(&key, 1, 1);
240        let wrong = issue_token(&key, 1, 2);
241        let mut h = Handover::start(1, 2);
242        accept_mutation(&mut h).unwrap();
243        fence_old(&mut h);
244        drain_accepted(&mut h);
245        persist_boundary(&mut h);
246        let mut successor = QsrSnapshot::empty(Generation(1));
247        successor.insert(key, StrongDigest::ZERO).unwrap();
248        let mut out = [StrongDigest::ZERO; 1];
249        let result = Qsr::lookup(
250            &key,
251            &miss_covers,
252            &public,
253            Generation(1),
254            Some(TokenStage {
255                token: &wrong,
256                expected: &expected,
257                snapshot: &private,
258                covers: &full_cover(),
259                generation: Generation(1),
260            }),
261            Some(HandoverStage {
262                handover: &h,
263                snapshot: &successor,
264                covers: &full_cover(),
265                generation: Generation(1),
266            }),
267            &mut out,
268        );
269        assert_eq!(result, Err(QdnfError::Unauthorized));
270        assert_ne!(result, Ok(QsrOutcome::Found { count: 1 }));
271    }
272
273    #[test]
274    fn r06_radix16_nibbles_span_all_96_positions_and_verify_full_key() {
275        let mut k1 = StrongDigest::ZERO;
276        let mut i = 0usize;
277        while i < 48 {
278            k1.0[i] = ((i as u8).wrapping_mul(3) << 4) | ((i as u8).wrapping_add(7) & 0x0f);
279            i += 1;
280        }
281        for depth in 0..super::super::key::KEY_DEPTH {
282            let nib = digit(&k1, depth).unwrap();
283            assert!(nib < DIGIT_RADIX);
284            let expected = if depth % 2 == 0 {
285                k1.0[depth / 2] >> 4
286            } else {
287                k1.0[depth / 2] & 0x0f
288            };
289            assert_eq!(nib, expected);
290        }
291        let mut k2 = k1;
292        k2.0[47] ^= 0x01; // differ only in the 95th nibble (last 4 bits of 384-bit key)
293        assert_eq!(digit(&k1, 0), digit(&k2, 0));
294        assert_ne!(digit(&k1, 95), digit(&k2, 95));
295        assert!(!keys_equal(&k1, &k2));
296
297        let mut snap = QsrSnapshot::empty(Generation(1));
298        let target = StrongDigest([0x99; 48]);
299        snap.insert(k1, target).unwrap();
300        let mut out = [StrongDigest::ZERO; 1];
301        assert_eq!(
302            Qsr::lookup(&k1, &full_cover(), &snap, Generation(1), None, None, &mut out).unwrap(),
303            QsrOutcome::Found { count: 1 }
304        );
305        assert_eq!(
306            Qsr::lookup(&k2, &full_cover(), &snap, Generation(1), None, None, &mut out).unwrap(),
307            QsrOutcome::EmptyInSnapshot
308        );
309    }
310}