Skip to main content

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

1//! Membership versus index completeness for QSR (E07.4).
2//!
3//! A Found / EmptyInSnapshot answer is membership in a named snapshot under a
4//! cover. It is not completeness. Completeness is recorded as publisher-asserted
5//! or independently reconstructed from admitted covers plus matching roots.
6//! Forged, missing, or partial covers cannot prove absence.
7
8use 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/// How completeness was obtained. Publisher signatures are not reconstruction.
17#[repr(u8)]
18#[derive(Clone, Copy, Debug, PartialEq, Eq)]
19pub enum CompletenessKind {
20    /// Unknown / not claimed.
21    Unknown = 0,
22    /// Publisher signed a completeness assertion. Not independently reconstructed.
23    PublisherAsserted = 1,
24    /// Local reconstruction from admitted covers + snapshot root matched compiler digest.
25    IndependentlyReconstructed = 2,
26}
27
28/// Bound roots plus whether the queried prefix is independently complete.
29#[repr(C)]
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
31pub struct CompletenessEvidence {
32    pub kind: CompletenessKind,
33    pub roots: IndexRoots,
34    /// True only when IndependentlyReconstructed and the cover is endpoint-complete
35    /// for the queried prefix. Publisher assertion never sets this by itself.
36    pub complete_for_prefix: bool,
37}
38
39/// Membership answer plus completeness. Completeness is never inferred from Found/Empty.
40#[derive(Clone, Copy, Debug, PartialEq, Eq)]
41pub struct QsrAnswer {
42    pub outcome: QsrOutcome,
43    pub completeness: CompletenessEvidence,
44}
45
46/// Membership of a key in a snapshot does not imply the index is complete.
47pub fn membership_implies_completeness() -> bool {
48    false
49}
50
51/// Authoritative absence: EmptyInSnapshot under independently reconstructed prefix completeness.
52pub 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
58/// Exact lookup with explicit completeness evidence. Calls [`lookup_into`] for membership.
59///
60/// Root disagreement is [`QsrOutcome::Conflict`] and is never treated as absence.
61/// Publisher-asserted completeness is recorded; `complete_for_prefix` stays false
62/// unless this node independently reconstructed matching roots and an endpoint-complete
63/// cover for the queried first digit. Narrower covers are complete only for digits
64/// they include; absence outside the cover is Incomplete, not EmptyInSnapshot.
65pub 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}