Skip to main content

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

1//! Parsed cover structure and coverage checks.
2//!
3//! Intervals are inclusive digit ranges in `0..=15` at one depth. Validation
4//! rejects empty covers, inverted ranges, out-of-radix endpoints, overlaps,
5//! and interior gaps. A valid cover is not an existence proof.
6
7use super::key::{digit, DIGIT_RADIX};
8use super::outcome::QsrOutcome;
9use crate::net::qdnf::errors::QdnfError;
10use crate::net::qdnf::types::StrongDigest;
11
12/// Inclusive digit range `0..=15` at one trie depth.
13#[repr(C)]
14#[derive(Clone, Copy, Debug, PartialEq, Eq)]
15pub struct CoverInterval {
16    pub start: u8,
17    pub end: u8,
18}
19
20/// Validates `cover`.
21pub fn validate_cover(children: &[CoverInterval]) -> Result<(), QdnfError> {
22    if children.is_empty() {
23        return Err(QdnfError::Incomplete);
24    }
25    let mut prev_end: Option<u8> = None;
26    let mut i = 0usize;
27    while i < children.len() {
28        let child = children[i];
29        if child.end < child.start {
30            return Err(QdnfError::Malformed);
31        }
32        if child.end >= DIGIT_RADIX {
33            return Err(QdnfError::Range);
34        }
35        if let Some(end) = prev_end {
36            if child.start <= end {
37                return Err(QdnfError::Overlap);
38            }
39            if child.start > end + 1 {
40                return Err(QdnfError::Incomplete);
41            }
42        }
43        prev_end = Some(child.end);
44        i += 1;
45    }
46    Ok(())
47}
48
49/// True when `d` (0..16) lies in some validated interval. Does not validate.
50pub fn covers_digit(covers: &[CoverInterval], d: u8) -> bool {
51    let mut i = 0usize;
52    while i < covers.len() {
53        let c = covers[i];
54        if d >= c.start && d <= c.end {
55            return true;
56        }
57        i += 1;
58    }
59    false
60}
61
62/// Cover membership for the depth-0 digit. Not authenticated existence.
63///
64/// A covered digit means traversal may continue for that prefix. It does not
65/// mean the key is present.
66pub fn lookup_exact(key: &StrongDigest, covers: &[CoverInterval]) -> Result<QsrOutcome, QdnfError> {
67    validate_cover(covers)?;
68    let d = digit(key, 0)?;
69    if covers_digit(covers, d) {
70        Ok(QsrOutcome::NeedContinuation)
71    } else {
72        Ok(QsrOutcome::Incomplete)
73    }
74}
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn overlapping_cover_is_rejected() {
82        let children = [
83            CoverInterval { start: 0, end: 10 },
84            CoverInterval { start: 8, end: 12 },
85        ];
86        assert_eq!(validate_cover(&children), Err(QdnfError::Overlap));
87    }
88
89    #[test]
90    fn interior_gap_is_incomplete() {
91        let children = [
92            CoverInterval { start: 0, end: 4 },
93            CoverInterval { start: 6, end: 15 },
94        ];
95        assert_eq!(validate_cover(&children), Err(QdnfError::Incomplete));
96    }
97
98    #[test]
99    fn empty_cover_is_incomplete() {
100        assert_eq!(validate_cover(&[]), Err(QdnfError::Incomplete));
101    }
102
103    #[test]
104    fn inverted_interval_is_malformed() {
105        let children = [CoverInterval { start: 9, end: 3 }];
106        assert_eq!(validate_cover(&children), Err(QdnfError::Malformed));
107    }
108
109    #[test]
110    fn end_sixteen_is_range() {
111        let children = [CoverInterval { start: 0, end: 16 }];
112        assert_eq!(validate_cover(&children), Err(QdnfError::Range));
113    }
114
115    #[test]
116    fn adjacent_full_radix_is_ok() {
117        let children = [
118            CoverInterval { start: 0, end: 7 },
119            CoverInterval { start: 8, end: 15 },
120        ];
121        assert_eq!(validate_cover(&children), Ok(()));
122    }
123
124    #[test]
125    fn lookup_exact_is_cover_membership_not_existence() {
126        let covers = [CoverInterval { start: 0, end: 10 }];
127        assert_eq!(
128            lookup_exact(&StrongDigest::ZERO, &covers),
129            Ok(QsrOutcome::NeedContinuation)
130        );
131        let uncovered = [CoverInterval { start: 1, end: 15 }];
132        assert_eq!(
133            lookup_exact(&StrongDigest::ZERO, &uncovered),
134            Ok(QsrOutcome::Incomplete)
135        );
136    }
137}