qualia_core_db/net/qdnf/resolve/qsr/
exact.rs1use 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#[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#[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
34pub struct Qsr;
37
38impl Qsr {
39 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
64pub(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 [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; 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}