microcosm.blue
Streaming Tree ARchive format
bad-example.com
1use crate::error::{Result, StarError};
2use crate::types::{StarMstNode, calculate_height};
3
4/// Validates the structure of a STAR MST node.
5///
6/// Checks:
7/// - Key height consistency (all keys must have same height)
8/// - Height matching against expectation
9/// - Structural rules (Height 0 vs >0 constraints)
10/// - Implicit/Explicit V rules
11///
12/// Returns (height, reconstructed_keys)
13pub fn validate_node_structure(
14 node: &StarMstNode,
15 expected: Option<u32>,
16) -> Result<(u32, Vec<Vec<u8>>)> {
17 let mut node_height = None;
18 let mut prev_key_bytes = Vec::new();
19 let mut entry_keys = Vec::new();
20
21 for e in &node.e {
22 let mut key = if e.p as usize <= prev_key_bytes.len() {
23 prev_key_bytes[..e.p as usize].to_vec()
24 } else {
25 prev_key_bytes.clone()
26 };
27 key.extend_from_slice(&e.k);
28
29 let h = calculate_height(&key);
30
31 if let Some(existing) = node_height {
32 if h != existing {
33 return Err(StarError::InvalidStructure(format!(
34 "Inconsistent key height in node: {} vs {}",
35 h, existing
36 )));
37 }
38 } else {
39 node_height = Some(h);
40 }
41
42 entry_keys.push(key.clone());
43 prev_key_bytes = key;
44 }
45
46 let height = match (node_height, expected) {
47 (Some(h), Some(exp)) => {
48 if h != exp {
49 return Err(StarError::HeightMismatch {
50 found: h,
51 expected: exp,
52 });
53 }
54 h
55 }
56 (Some(h), None) => h,
57 (None, Some(exp)) => {
58 if exp == 0 {
59 return Err(StarError::InvalidStructure(
60 "Height 0 cannot be empty".into(),
61 ));
62 }
63 exp
64 }
65 (None, None) => return Err(StarError::InvalidStructure("Root cannot be empty".into())),
66 };
67
68 if height == 0 {
69 if node.l.is_some() || node.l_archived.is_some() {
70 return Err(StarError::InvalidStructure(
71 "Height 0 node cannot have left child".into(),
72 ));
73 }
74 for e in &node.e {
75 if e.t.is_some() || e.t_archived.is_some() {
76 return Err(StarError::InvalidStructure(
77 "Height 0 entries cannot have subtrees".into(),
78 ));
79 }
80 if e.v.is_some() {
81 return Err(StarError::InvalidStructure(
82 "Height 0 node must omit record CIDs".into(),
83 ));
84 }
85 }
86 } else {
87 if node.e.is_empty() && node.l.is_none() {
88 return Err(StarError::InvalidStructure(
89 "Empty intermediate node must have left child".into(),
90 ));
91 }
92 for e in &node.e {
93 if e.v.is_none() {
94 return Err(StarError::InvalidStructure(
95 "Intermediate node must include record CIDs".into(),
96 ));
97 }
98 }
99 }
100
101 Ok((height, entry_keys))
102}