qualia_core_db/net/qdnf/resolve/qsr/
cover.rs1use super::key::{digit, DIGIT_RADIX};
8use super::outcome::QsrOutcome;
9use crate::net::qdnf::errors::QdnfError;
10use crate::net::qdnf::types::StrongDigest;
11
12#[repr(C)]
14#[derive(Clone, Copy, Debug, PartialEq, Eq)]
15pub struct CoverInterval {
16 pub start: u8,
17 pub end: u8,
18}
19
20pub 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
49pub 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
62pub 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}