hyphae_engine/
document.rs

1// SPDX-License-Identifier: Apache-2.0
2
3use std::collections::BTreeMap;
4
5use hyphae_query::Value;
6use thiserror::Error;
7
8const MAGIC: [u8; 8] = *b"HYDOC001";
9const DOCUMENT_FORMAT_VERSION: u16 = 1;
10const HEADER_LENGTH: usize = 56;
11const CHECKSUM_PREFIX_LENGTH: usize = 20;
12const DIGEST_PREFIX_LENGTH: usize = 24;
13const NULL: u8 = 0;
14const FALSE: u8 = 1;
15const TRUE: u8 = 2;
16const INTEGER: u8 = 3;
17const STRING: u8 = 4;
18const BYTES: u8 = 5;
19const ARRAY: u8 = 6;
20const OBJECT: u8 = 7;
21
22/// Maximum canonical document payload bytes.
23pub const MAX_DOCUMENT_BYTES: usize = 16 * 1024 * 1024;
24/// Maximum nested array/object depth, with the root at depth zero.
25pub const MAX_DOCUMENT_DEPTH: usize = 64;
26/// Maximum values decoded from one document.
27pub const MAX_DOCUMENT_NODES: usize = 1_000_000;
28
29/// Failure while encoding or verifying one canonical structured document.
30#[derive(Clone, Debug, Error, Eq, PartialEq)]
31pub enum DocumentError {
32    /// Canonical payload exceeds the hard bound.
33    #[error("document payload is {actual} bytes; maximum is {maximum}")]
34    TooLarge {
35        /// Observed or attempted payload length.
36        actual: usize,
37        /// Hard maximum.
38        maximum: usize,
39    },
40
41    /// Array/object nesting exceeds the hard bound.
42    #[error("document depth exceeds maximum {maximum}")]
43    TooDeep {
44        /// Hard maximum.
45        maximum: usize,
46    },
47
48    /// Value count exceeds the hard bound.
49    #[error("document node count exceeds maximum {maximum}")]
50    TooManyNodes {
51        /// Hard maximum.
52        maximum: usize,
53    },
54
55    /// Length cannot be represented by the canonical format.
56    #[error("document length overflow")]
57    LengthOverflow,
58
59    /// Encoded bytes are truncated or structurally noncanonical.
60    #[error("invalid canonical document: {reason}")]
61    Invalid {
62        /// Stable diagnostic reason.
63        reason: &'static str,
64    },
65
66    /// Document format is newer than this binary.
67    #[error("unsupported document format {found}; supported format is {supported}")]
68    UnsupportedVersion {
69        /// Version found on disk.
70        found: u16,
71        /// Highest supported version.
72        supported: u16,
73    },
74
75    /// Fast accidental-corruption check failed.
76    #[error("document CRC32C mismatch")]
77    ChecksumMismatch,
78
79    /// Canonical content digest failed.
80    #[error("document BLAKE3 mismatch")]
81    DigestMismatch,
82
83    /// A string or object key is not UTF-8.
84    #[error("document contains invalid UTF-8")]
85    InvalidUtf8,
86}
87
88/// Encodes one structured value into a checksummed canonical binary document.
89///
90/// # Errors
91///
92/// Returns an error for depth, node, length, or payload limits.
93pub fn encode_document(value: &Value) -> Result<Vec<u8>, DocumentError> {
94    let mut encoder = Encoder {
95        payload: Vec::new(),
96        nodes: 0,
97    };
98    encoder.value(value, 0)?;
99    encode_envelope(&encoder.payload)
100}
101
102/// Verifies and decodes one canonical binary document.
103///
104/// # Errors
105///
106/// Returns an error for version, length, integrity, UTF-8, ordering, depth,
107/// node count, unknown tags, or trailing bytes.
108pub fn decode_document(encoded: &[u8]) -> Result<Value, DocumentError> {
109    if encoded.len() < HEADER_LENGTH {
110        return Err(DocumentError::Invalid {
111            reason: "truncated header",
112        });
113    }
114    if encoded[..8] != MAGIC {
115        return Err(DocumentError::Invalid {
116            reason: "bad magic",
117        });
118    }
119    let version = u16::from_le_bytes(copy_array(&encoded[8..10]));
120    if version != DOCUMENT_FORMAT_VERSION {
121        return Err(DocumentError::UnsupportedVersion {
122            found: version,
123            supported: DOCUMENT_FORMAT_VERSION,
124        });
125    }
126    if u16::from_le_bytes(copy_array(&encoded[10..12])) != 0 {
127        return Err(DocumentError::Invalid {
128            reason: "unsupported flags",
129        });
130    }
131    let payload_length = usize::try_from(u64::from_le_bytes(copy_array(&encoded[12..20])))
132        .map_err(|_| DocumentError::LengthOverflow)?;
133    if payload_length > MAX_DOCUMENT_BYTES {
134        return Err(DocumentError::TooLarge {
135            actual: payload_length,
136            maximum: MAX_DOCUMENT_BYTES,
137        });
138    }
139    let expected_length = HEADER_LENGTH
140        .checked_add(payload_length)
141        .ok_or(DocumentError::LengthOverflow)?;
142    if encoded.len() != expected_length {
143        return Err(DocumentError::Invalid {
144            reason: "file length mismatch",
145        });
146    }
147    let payload = &encoded[HEADER_LENGTH..];
148    let expected_checksum = u32::from_le_bytes(copy_array(&encoded[20..24]));
149    let actual_checksum =
150        crc32c::crc32c_append(crc32c::crc32c(&encoded[..CHECKSUM_PREFIX_LENGTH]), payload);
151    if actual_checksum != expected_checksum {
152        return Err(DocumentError::ChecksumMismatch);
153    }
154    let expected_digest: [u8; 32] = copy_array(&encoded[24..56]);
155    let mut hasher = blake3::Hasher::new();
156    hasher.update(&encoded[..DIGEST_PREFIX_LENGTH]);
157    hasher.update(payload);
158    if *hasher.finalize().as_bytes() != expected_digest {
159        return Err(DocumentError::DigestMismatch);
160    }
161
162    let mut decoder = Decoder {
163        payload,
164        position: 0,
165        nodes: 0,
166    };
167    let value = decoder.value(0)?;
168    if decoder.position != payload.len() {
169        return Err(DocumentError::Invalid {
170            reason: "trailing payload bytes",
171        });
172    }
173    Ok(value)
174}
175
176struct Encoder {
177    payload: Vec<u8>,
178    nodes: usize,
179}
180
181impl Encoder {
182    fn value(&mut self, value: &Value, depth: usize) -> Result<(), DocumentError> {
183        if depth > MAX_DOCUMENT_DEPTH {
184            return Err(DocumentError::TooDeep {
185                maximum: MAX_DOCUMENT_DEPTH,
186            });
187        }
188        self.nodes = self
189            .nodes
190            .checked_add(1)
191            .ok_or(DocumentError::TooManyNodes {
192                maximum: MAX_DOCUMENT_NODES,
193            })?;
194        if self.nodes > MAX_DOCUMENT_NODES {
195            return Err(DocumentError::TooManyNodes {
196                maximum: MAX_DOCUMENT_NODES,
197            });
198        }
199        match value {
200            Value::Null => self.append(&[NULL]),
201            Value::Boolean(false) => self.append(&[FALSE]),
202            Value::Boolean(true) => self.append(&[TRUE]),
203            Value::Integer(value) => {
204                self.append(&[INTEGER])?;
205                self.append(&value.to_le_bytes())
206            }
207            Value::String(value) => {
208                self.append(&[STRING])?;
209                self.length_prefixed(value.as_bytes())
210            }
211            Value::Bytes(value) => {
212                self.append(&[BYTES])?;
213                self.length_prefixed(value)
214            }
215            Value::Array(values) => {
216                self.append(&[ARRAY])?;
217                self.length(values.len())?;
218                let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
219                    maximum: MAX_DOCUMENT_DEPTH,
220                })?;
221                for value in values {
222                    self.value(value, child_depth)?;
223                }
224                Ok(())
225            }
226            Value::Object(values) => {
227                self.append(&[OBJECT])?;
228                self.length(values.len())?;
229                let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
230                    maximum: MAX_DOCUMENT_DEPTH,
231                })?;
232                for (key, value) in values {
233                    self.length_prefixed(key.as_bytes())?;
234                    self.value(value, child_depth)?;
235                }
236                Ok(())
237            }
238        }
239    }
240
241    fn length_prefixed(&mut self, value: &[u8]) -> Result<(), DocumentError> {
242        self.length(value.len())?;
243        self.append(value)
244    }
245
246    fn length(&mut self, length: usize) -> Result<(), DocumentError> {
247        let encoded = u64::try_from(length).map_err(|_| DocumentError::LengthOverflow)?;
248        self.append(&encoded.to_le_bytes())
249    }
250
251    fn append(&mut self, bytes: &[u8]) -> Result<(), DocumentError> {
252        let next = self
253            .payload
254            .len()
255            .checked_add(bytes.len())
256            .ok_or(DocumentError::LengthOverflow)?;
257        if next > MAX_DOCUMENT_BYTES {
258            return Err(DocumentError::TooLarge {
259                actual: next,
260                maximum: MAX_DOCUMENT_BYTES,
261            });
262        }
263        self.payload.extend_from_slice(bytes);
264        Ok(())
265    }
266}
267
268struct Decoder<'payload> {
269    payload: &'payload [u8],
270    position: usize,
271    nodes: usize,
272}
273
274impl Decoder<'_> {
275    fn value(&mut self, depth: usize) -> Result<Value, DocumentError> {
276        if depth > MAX_DOCUMENT_DEPTH {
277            return Err(DocumentError::TooDeep {
278                maximum: MAX_DOCUMENT_DEPTH,
279            });
280        }
281        self.nodes = self
282            .nodes
283            .checked_add(1)
284            .ok_or(DocumentError::TooManyNodes {
285                maximum: MAX_DOCUMENT_NODES,
286            })?;
287        if self.nodes > MAX_DOCUMENT_NODES {
288            return Err(DocumentError::TooManyNodes {
289                maximum: MAX_DOCUMENT_NODES,
290            });
291        }
292        let tag = self.read(1)?[0];
293        match tag {
294            NULL => Ok(Value::Null),
295            FALSE => Ok(Value::Boolean(false)),
296            TRUE => Ok(Value::Boolean(true)),
297            INTEGER => Ok(Value::Integer(i64::from_le_bytes(copy_array(
298                self.read(8)?,
299            )))),
300            STRING => {
301                let bytes = self.length_prefixed()?;
302                let value = std::str::from_utf8(bytes).map_err(|_| DocumentError::InvalidUtf8)?;
303                Ok(Value::String(value.to_owned()))
304            }
305            BYTES => Ok(Value::Bytes(self.length_prefixed()?.to_vec())),
306            ARRAY => self.array(depth),
307            OBJECT => self.object(depth),
308            _ => Err(DocumentError::Invalid {
309                reason: "unknown value tag",
310            }),
311        }
312    }
313
314    fn array(&mut self, depth: usize) -> Result<Value, DocumentError> {
315        let count = self.length()?;
316        if count > MAX_DOCUMENT_NODES {
317            return Err(DocumentError::TooManyNodes {
318                maximum: MAX_DOCUMENT_NODES,
319            });
320        }
321        let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
322            maximum: MAX_DOCUMENT_DEPTH,
323        })?;
324        let mut values = Vec::with_capacity(count);
325        for _ in 0..count {
326            values.push(self.value(child_depth)?);
327        }
328        Ok(Value::Array(values))
329    }
330
331    fn object(&mut self, depth: usize) -> Result<Value, DocumentError> {
332        let count = self.length()?;
333        if count > MAX_DOCUMENT_NODES {
334            return Err(DocumentError::TooManyNodes {
335                maximum: MAX_DOCUMENT_NODES,
336            });
337        }
338        let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
339            maximum: MAX_DOCUMENT_DEPTH,
340        })?;
341        let mut values = BTreeMap::new();
342        let mut previous: Option<String> = None;
343        for _ in 0..count {
344            let bytes = self.length_prefixed()?;
345            let key = std::str::from_utf8(bytes)
346                .map_err(|_| DocumentError::InvalidUtf8)?
347                .to_owned();
348            if previous.as_ref().is_some_and(|previous| previous >= &key) {
349                return Err(DocumentError::Invalid {
350                    reason: "object keys are not strictly sorted",
351                });
352            }
353            let value = self.value(child_depth)?;
354            previous = Some(key.clone());
355            values.insert(key, value);
356        }
357        Ok(Value::Object(values))
358    }
359
360    fn length_prefixed(&mut self) -> Result<&[u8], DocumentError> {
361        let length = self.length()?;
362        self.read(length)
363    }
364
365    fn length(&mut self) -> Result<usize, DocumentError> {
366        usize::try_from(u64::from_le_bytes(copy_array(self.read(8)?)))
367            .map_err(|_| DocumentError::LengthOverflow)
368    }
369
370    fn read(&mut self, length: usize) -> Result<&[u8], DocumentError> {
371        let end = self
372            .position
373            .checked_add(length)
374            .ok_or(DocumentError::LengthOverflow)?;
375        let Some(value) = self.payload.get(self.position..end) else {
376            return Err(DocumentError::Invalid {
377                reason: "truncated value payload",
378            });
379        };
380        self.position = end;
381        Ok(value)
382    }
383}
384
385fn encode_envelope(payload: &[u8]) -> Result<Vec<u8>, DocumentError> {
386    if payload.len() > MAX_DOCUMENT_BYTES {
387        return Err(DocumentError::TooLarge {
388            actual: payload.len(),
389            maximum: MAX_DOCUMENT_BYTES,
390        });
391    }
392    let payload_length = u64::try_from(payload.len()).map_err(|_| DocumentError::LengthOverflow)?;
393    let capacity = HEADER_LENGTH
394        .checked_add(payload.len())
395        .ok_or(DocumentError::LengthOverflow)?;
396    let mut encoded = vec![0_u8; capacity];
397    encoded[..8].copy_from_slice(&MAGIC);
398    encoded[8..10].copy_from_slice(&DOCUMENT_FORMAT_VERSION.to_le_bytes());
399    encoded[10..12].copy_from_slice(&0_u16.to_le_bytes());
400    encoded[12..20].copy_from_slice(&payload_length.to_le_bytes());
401    encoded[HEADER_LENGTH..].copy_from_slice(payload);
402    let checksum =
403        crc32c::crc32c_append(crc32c::crc32c(&encoded[..CHECKSUM_PREFIX_LENGTH]), payload);
404    encoded[20..24].copy_from_slice(&checksum.to_le_bytes());
405    let mut hasher = blake3::Hasher::new();
406    hasher.update(&encoded[..DIGEST_PREFIX_LENGTH]);
407    hasher.update(payload);
408    encoded[24..56].copy_from_slice(hasher.finalize().as_bytes());
409    Ok(encoded)
410}
411
412fn copy_array<const N: usize>(source: &[u8]) -> [u8; N] {
413    let mut output = [0_u8; N];
414    output.copy_from_slice(source);
415    output
416}
417
418#[cfg(test)]
419mod tests {
420    use std::collections::BTreeMap;
421
422    use hyphae_query::Value;
423
424    use super::{
425        DOCUMENT_FORMAT_VERSION, DocumentError, MAX_DOCUMENT_DEPTH, NULL, OBJECT, decode_document,
426        encode_document, encode_envelope,
427    };
428
429    #[test]
430    fn canonical_document_round_trips_binary_and_nested_values() -> Result<(), DocumentError> {
431        let value = Value::Object(BTreeMap::from([
432            ("bytes".to_owned(), Value::Bytes(vec![0, 255, 7])),
433            (
434                "nested".to_owned(),
435                Value::Array(vec![Value::Integer(-7), Value::Null]),
436            ),
437        ]));
438        let first = encode_document(&value)?;
439        let second = encode_document(&value)?;
440        assert_eq!(first, second);
441        assert_eq!(decode_document(&first)?, value);
442        Ok(())
443    }
444
445    #[test]
446    fn corruption_and_future_versions_fail_before_decoding() -> Result<(), DocumentError> {
447        let mut corrupted = encode_document(&Value::Integer(7))?;
448        let last = corrupted.len() - 1;
449        corrupted[last] ^= 1;
450        assert_eq!(
451            decode_document(&corrupted),
452            Err(DocumentError::ChecksumMismatch)
453        );
454
455        let mut future = encode_document(&Value::Null)?;
456        future[8..10].copy_from_slice(&(DOCUMENT_FORMAT_VERSION + 1).to_le_bytes());
457        assert_eq!(
458            decode_document(&future),
459            Err(DocumentError::UnsupportedVersion {
460                found: DOCUMENT_FORMAT_VERSION + 1,
461                supported: DOCUMENT_FORMAT_VERSION
462            })
463        );
464        Ok(())
465    }
466
467    #[test]
468    fn depth_is_bounded_during_encoding() {
469        let mut value = Value::Null;
470        for _ in 0..=MAX_DOCUMENT_DEPTH {
471            value = Value::Array(vec![value]);
472        }
473        assert_eq!(
474            encode_document(&value),
475            Err(DocumentError::TooDeep {
476                maximum: MAX_DOCUMENT_DEPTH
477            })
478        );
479    }
480
481    #[test]
482    fn decoder_rejects_noncanonical_object_key_order() -> Result<(), DocumentError> {
483        let mut payload = vec![OBJECT];
484        payload.extend_from_slice(&2_u64.to_le_bytes());
485        payload.extend_from_slice(&1_u64.to_le_bytes());
486        payload.extend_from_slice(b"b");
487        payload.push(NULL);
488        payload.extend_from_slice(&1_u64.to_le_bytes());
489        payload.extend_from_slice(b"a");
490        payload.push(NULL);
491        let encoded = encode_envelope(&payload)?;
492        assert_eq!(
493            decode_document(&encoded),
494            Err(DocumentError::Invalid {
495                reason: "object keys are not strictly sorted"
496            })
497        );
498        Ok(())
499    }
500}
hyphae_engine/document.rs

hyphae_engine/
document.rs
