1use super::cover::{covers_digit, CoverInterval};
9use super::key::digit;
10use super::outcome::QsrOutcome;
11use super::roots::{bind_roots, IndexRoots};
12use super::traversal::{lookup_into, QsrSnapshot};
13use crate::net::qdnf::errors::QdnfError;
14use crate::net::qdnf::types::{Generation, StrongDigest};
15
16#[repr(u8)]
18#[derive(Clone, Copy, Debug, PartialEq, Eq)]
19pub enum CompletenessKind {
20 Unknown = 0,
22 PublisherAsserted = 1,
24 IndependentlyReconstructed = 2,
26}
27
28#[repr(C)]
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
31pub struct CompletenessEvidence {
32 pub kind: CompletenessKind,
33 pub roots: IndexRoots,
34 pub complete_for_prefix: bool,
37}
38
39#[derive(Clone, Copy, Debug, PartialEq, Eq)]
41pub struct QsrAnswer {
42 pub outcome: QsrOutcome,
43 pub completeness: CompletenessEvidence,
44}
45
46pub fn membership_implies_completeness() -> bool {
48 false
49}
50
51pub fn absence_is_authoritative(answer: &QsrAnswer) -> bool {
53 matches!(answer.outcome, QsrOutcome::EmptyInSnapshot)
54 && answer.completeness.complete_for_prefix
55 && answer.completeness.kind == CompletenessKind::IndependentlyReconstructed
56}
57
58pub fn lookup_with_completeness(
66 snapshot: &QsrSnapshot,
67 key: &StrongDigest,
68 covers: &[CoverInterval],
69 required_generation: Generation,
70 claimed: CompletenessEvidence,
71 expected_roots: &IndexRoots,
72 out: &mut [StrongDigest],
73) -> Result<QsrAnswer, QdnfError> {
74 let bound = bind_roots(
75 snapshot,
76 expected_roots.compiler_digest,
77 expected_roots.index_root,
78 )?;
79 if claimed.roots != *expected_roots || bound != *expected_roots {
80 return Ok(QsrAnswer {
81 outcome: QsrOutcome::Conflict,
82 completeness: CompletenessEvidence {
83 kind: claimed.kind,
84 roots: *expected_roots,
85 complete_for_prefix: false,
86 },
87 });
88 }
89
90 let outcome = lookup_into(snapshot, key, covers, required_generation, out)?;
91 let prefix_covered = match digit(key, 0) {
92 Ok(d) => covers_digit(covers, d),
93 Err(_) => false,
94 };
95 let reconstructed = claimed.kind == CompletenessKind::IndependentlyReconstructed
96 && bound == *expected_roots
97 && prefix_covered
98 && !matches!(outcome, QsrOutcome::Stale | QsrOutcome::Incomplete);
99
100 let complete_for_prefix = match claimed.kind {
101 CompletenessKind::IndependentlyReconstructed => reconstructed,
102 CompletenessKind::PublisherAsserted | CompletenessKind::Unknown => false,
103 };
104
105 Ok(QsrAnswer {
106 outcome,
107 completeness: CompletenessEvidence {
108 kind: claimed.kind,
109 roots: bound,
110 complete_for_prefix,
111 },
112 })
113}
114
115#[cfg(test)]
116mod tests {
117 use super::super::key::KEY_DEPTH;
118 use super::super::roots::bind_roots;
119 use super::*;
120 use crate::crypto::network::digest::sha384;
121
122 fn full_cover() -> [CoverInterval; 1] {
123 [CoverInterval { start: 0, end: 15 }]
124 }
125
126 fn compiler_index() -> (StrongDigest, StrongDigest) {
127 (
128 sha384(b"qdnf:qsr:compiler:test"),
129 sha384(b"qdnf:qsr:index:test"),
130 )
131 }
132
133 fn evidence(
134 kind: CompletenessKind,
135 roots: IndexRoots,
136 complete_for_prefix: bool,
137 ) -> CompletenessEvidence {
138 CompletenessEvidence {
139 kind,
140 roots,
141 complete_for_prefix,
142 }
143 }
144
145 fn key_same_first_byte(rest: u8) -> StrongDigest {
146 let mut k = StrongDigest::ZERO;
147 k.0[0] = 0x10;
148 let mut i = 1usize;
149 while i < 48 {
150 k.0[i] = rest;
151 i += 1;
152 }
153 k
154 }
155
156 #[test]
157 fn found_publisher_asserted_is_not_prefix_complete() {
158 let mut key = StrongDigest::ZERO;
159 key.0[0] = 0x20;
160 let mut target = StrongDigest::ZERO;
161 target.0[47] = 0x77;
162 let mut snap = QsrSnapshot::empty(Generation(3));
163 snap.insert(key, target).unwrap();
164 let (compiler, index) = compiler_index();
165 let roots = bind_roots(&snap, compiler, index).unwrap();
166 let claimed = evidence(CompletenessKind::PublisherAsserted, roots, true);
167 let mut out = [StrongDigest::ZERO; 1];
168 let answer = lookup_with_completeness(
169 &snap,
170 &key,
171 &full_cover(),
172 Generation(3),
173 claimed,
174 &roots,
175 &mut out,
176 )
177 .unwrap();
178 assert_eq!(answer.outcome, QsrOutcome::Found { count: 1 });
179 assert_eq!(
180 answer.completeness.kind,
181 CompletenessKind::PublisherAsserted
182 );
183 assert!(!answer.completeness.complete_for_prefix);
184 assert!(!absence_is_authoritative(&answer));
185 assert!(crate::net::qdnf::resolve::qsr::key::keys_equal(
186 &out[0], &target
187 ));
188 }
189
190 #[test]
191 fn missing_key_partial_cover_is_incomplete_not_authoritative() {
192 let snap = QsrSnapshot::empty(Generation(1));
193 let (compiler, index) = compiler_index();
194 let roots = bind_roots(&snap, compiler, index).unwrap();
195 let claimed = evidence(CompletenessKind::IndependentlyReconstructed, roots, true);
196 let covers = [CoverInterval { start: 1, end: 15 }];
197 let mut out = [StrongDigest::ZERO; 1];
198 let answer = lookup_with_completeness(
199 &snap,
200 &StrongDigest::ZERO,
201 &covers,
202 Generation(1),
203 claimed,
204 &roots,
205 &mut out,
206 )
207 .unwrap();
208 assert_eq!(answer.outcome, QsrOutcome::Incomplete);
209 assert!(!answer.completeness.complete_for_prefix);
210 assert!(!absence_is_authoritative(&answer));
211 }
212
213 #[test]
214 fn missing_key_full_cover_reconstructed_is_authoritative_empty() {
215 let snap = QsrSnapshot::empty(Generation(1));
216 let (compiler, index) = compiler_index();
217 let roots = bind_roots(&snap, compiler, index).unwrap();
218 let claimed = evidence(CompletenessKind::IndependentlyReconstructed, roots, false);
219 let mut out = [StrongDigest::ZERO; 1];
220 let answer = lookup_with_completeness(
221 &snap,
222 &StrongDigest::ZERO,
223 &full_cover(),
224 Generation(1),
225 claimed,
226 &roots,
227 &mut out,
228 )
229 .unwrap();
230 assert_eq!(answer.outcome, QsrOutcome::EmptyInSnapshot);
231 assert_eq!(
232 answer.completeness.kind,
233 CompletenessKind::IndependentlyReconstructed
234 );
235 assert!(answer.completeness.complete_for_prefix);
236 assert!(absence_is_authoritative(&answer));
237 }
238
239 #[test]
240 fn publisher_asserted_mismatched_snapshot_root_is_conflict() {
241 let snap = QsrSnapshot::empty(Generation(1));
242 let (compiler, index) = compiler_index();
243 let roots = bind_roots(&snap, compiler, index).unwrap();
244 let mut forged = roots;
245 forged.snapshot_root.0[0] ^= 0xff;
246 assert_ne!(forged.snapshot_root, roots.snapshot_root);
247 let claimed = evidence(CompletenessKind::PublisherAsserted, forged, true);
248 let mut out = [StrongDigest::ZERO; 1];
249 let answer = lookup_with_completeness(
250 &snap,
251 &StrongDigest::ZERO,
252 &full_cover(),
253 Generation(1),
254 claimed,
255 &roots,
256 &mut out,
257 )
258 .unwrap();
259 assert_eq!(answer.outcome, QsrOutcome::Conflict);
260 assert!(!answer.completeness.complete_for_prefix);
261 assert!(!absence_is_authoritative(&answer));
262 }
263
264 #[test]
265 fn forged_index_root_is_conflict() {
266 let snap = QsrSnapshot::empty(Generation(1));
267 let (compiler, index) = compiler_index();
268 let roots = bind_roots(&snap, compiler, index).unwrap();
269 let mut forged = roots;
270 forged.index_root.0[47] ^= 0x01;
271 assert_ne!(forged.index_root, roots.index_root);
272 let claimed = evidence(CompletenessKind::IndependentlyReconstructed, forged, true);
273 let mut out = [StrongDigest::ZERO; 1];
274 let answer = lookup_with_completeness(
275 &snap,
276 &StrongDigest::ZERO,
277 &full_cover(),
278 Generation(1),
279 claimed,
280 &roots,
281 &mut out,
282 )
283 .unwrap();
284 assert_eq!(answer.outcome, QsrOutcome::Conflict);
285 assert!(!absence_is_authoritative(&answer));
286 }
287
288 #[test]
289 fn same_first_byte_different_key_found_only_for_exact_key() {
290 let a = key_same_first_byte(0x01);
291 let b = key_same_first_byte(0x02);
292 assert_eq!(a.0[0], b.0[0]);
293 assert_eq!(a.0[0] % KEY_DEPTH as u8, b.0[0] % KEY_DEPTH as u8);
294
295 let mut snap = QsrSnapshot::empty(Generation(1));
296 snap.insert(a, StrongDigest::ZERO).unwrap();
297 let (compiler, index) = compiler_index();
298 let roots = bind_roots(&snap, compiler, index).unwrap();
299 let claimed = evidence(CompletenessKind::IndependentlyReconstructed, roots, true);
300 let covers = full_cover();
301 let mut out = [StrongDigest::ZERO; 1];
302
303 let found =
304 lookup_with_completeness(&snap, &a, &covers, Generation(1), claimed, &roots, &mut out)
305 .unwrap();
306 assert_eq!(found.outcome, QsrOutcome::Found { count: 1 });
307 assert!(found.completeness.complete_for_prefix);
308 assert!(!absence_is_authoritative(&found));
309
310 let missing =
311 lookup_with_completeness(&snap, &b, &covers, Generation(1), claimed, &roots, &mut out)
312 .unwrap();
313 assert_eq!(missing.outcome, QsrOutcome::EmptyInSnapshot);
314 assert_ne!(missing.outcome, QsrOutcome::Found { count: 1 });
315 assert!(absence_is_authoritative(&missing));
316 assert_eq!(found.completeness.kind, missing.completeness.kind);
317 assert_eq!(found.completeness.roots, missing.completeness.roots);
318 }
319
320 #[test]
321 fn membership_does_not_imply_completeness() {
322 assert!(!membership_implies_completeness());
323 }
324
325 #[test]
326 fn publisher_asserted_empty_is_membership_not_authoritative_absence() {
327 let snap = QsrSnapshot::empty(Generation(1));
328 let (compiler, index) = compiler_index();
329 let roots = bind_roots(&snap, compiler, index).unwrap();
330 let claimed = evidence(CompletenessKind::PublisherAsserted, roots, true);
331 let mut out = [StrongDigest::ZERO; 1];
332 let answer = lookup_with_completeness(
333 &snap,
334 &StrongDigest::ZERO,
335 &full_cover(),
336 Generation(1),
337 claimed,
338 &roots,
339 &mut out,
340 )
341 .unwrap();
342 assert_eq!(answer.outcome, QsrOutcome::EmptyInSnapshot);
343 assert!(!answer.completeness.complete_for_prefix);
344 assert!(!absence_is_authoritative(&answer));
345 }
346}