hyphae_query/
document.rs

1// SPDX-License-Identifier: Apache-2.0
2
3use std::collections::BTreeMap;
4
5use crate::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/// Returns the exact canonical envelope length without allocating the encoded
103/// document.
104///
105/// # Errors
106///
107/// Returns the same depth, node, payload, or arithmetic-limit errors as
108/// [`encode_document`].
109pub fn encoded_document_len(value: &Value) -> Result<usize, DocumentError> {
110    let mut measurer = DocumentMeasurer {
111        payload_bytes: 0,
112        nodes: 0,
113    };
114    measurer.value(value, 0)?;
115    HEADER_LENGTH
116        .checked_add(measurer.payload_bytes)
117        .ok_or(DocumentError::LengthOverflow)
118}
119
120/// Verifies and decodes one canonical binary document.
121///
122/// # Errors
123///
124/// Returns an error for version, length, integrity, UTF-8, ordering, depth,
125/// node count, unknown tags, or trailing bytes.
126pub fn decode_document(encoded: &[u8]) -> Result<Value, DocumentError> {
127    if encoded.len() < HEADER_LENGTH {
128        return Err(DocumentError::Invalid {
129            reason: "truncated header",
130        });
131    }
132    if encoded[..8] != MAGIC {
133        return Err(DocumentError::Invalid {
134            reason: "bad magic",
135        });
136    }
137    let version = u16::from_le_bytes(copy_array(&encoded[8..10]));
138    if version != DOCUMENT_FORMAT_VERSION {
139        return Err(DocumentError::UnsupportedVersion {
140            found: version,
141            supported: DOCUMENT_FORMAT_VERSION,
142        });
143    }
144    if u16::from_le_bytes(copy_array(&encoded[10..12])) != 0 {
145        return Err(DocumentError::Invalid {
146            reason: "unsupported flags",
147        });
148    }
149    let payload_length = usize::try_from(u64::from_le_bytes(copy_array(&encoded[12..20])))
150        .map_err(|_| DocumentError::LengthOverflow)?;
151    if payload_length > MAX_DOCUMENT_BYTES {
152        return Err(DocumentError::TooLarge {
153            actual: payload_length,
154            maximum: MAX_DOCUMENT_BYTES,
155        });
156    }
157    let expected_length = HEADER_LENGTH
158        .checked_add(payload_length)
159        .ok_or(DocumentError::LengthOverflow)?;
160    if encoded.len() != expected_length {
161        return Err(DocumentError::Invalid {
162            reason: "file length mismatch",
163        });
164    }
165    let payload = &encoded[HEADER_LENGTH..];
166    let expected_checksum = u32::from_le_bytes(copy_array(&encoded[20..24]));
167    let actual_checksum =
168        crc32c::crc32c_append(crc32c::crc32c(&encoded[..CHECKSUM_PREFIX_LENGTH]), payload);
169    if actual_checksum != expected_checksum {
170        return Err(DocumentError::ChecksumMismatch);
171    }
172    let expected_digest: [u8; 32] = copy_array(&encoded[24..56]);
173    let mut hasher = blake3::Hasher::new();
174    hasher.update(&encoded[..DIGEST_PREFIX_LENGTH]);
175    hasher.update(payload);
176    if *hasher.finalize().as_bytes() != expected_digest {
177        return Err(DocumentError::DigestMismatch);
178    }
179
180    let mut decoder = Decoder {
181        payload,
182        position: 0,
183        nodes: 0,
184    };
185    let value = decoder.value(0)?;
186    if decoder.position != payload.len() {
187        return Err(DocumentError::Invalid {
188            reason: "trailing payload bytes",
189        });
190    }
191    Ok(value)
192}
193
194struct Encoder {
195    payload: Vec<u8>,
196    nodes: usize,
197}
198
199impl Encoder {
200    fn value(&mut self, value: &Value, depth: usize) -> Result<(), DocumentError> {
201        if depth > MAX_DOCUMENT_DEPTH {
202            return Err(DocumentError::TooDeep {
203                maximum: MAX_DOCUMENT_DEPTH,
204            });
205        }
206        self.nodes = self
207            .nodes
208            .checked_add(1)
209            .ok_or(DocumentError::TooManyNodes {
210                maximum: MAX_DOCUMENT_NODES,
211            })?;
212        if self.nodes > MAX_DOCUMENT_NODES {
213            return Err(DocumentError::TooManyNodes {
214                maximum: MAX_DOCUMENT_NODES,
215            });
216        }
217        match value {
218            Value::Null => self.append(&[NULL]),
219            Value::Boolean(false) => self.append(&[FALSE]),
220            Value::Boolean(true) => self.append(&[TRUE]),
221            Value::Integer(value) => {
222                self.append(&[INTEGER])?;
223                self.append(&value.to_le_bytes())
224            }
225            Value::String(value) => {
226                self.append(&[STRING])?;
227                self.length_prefixed(value.as_bytes())
228            }
229            Value::Bytes(value) => {
230                self.append(&[BYTES])?;
231                self.length_prefixed(value)
232            }
233            Value::Array(values) => {
234                self.append(&[ARRAY])?;
235                self.length(values.len())?;
236                let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
237                    maximum: MAX_DOCUMENT_DEPTH,
238                })?;
239                for value in values {
240                    self.value(value, child_depth)?;
241                }
242                Ok(())
243            }
244            Value::Object(values) => {
245                self.append(&[OBJECT])?;
246                self.length(values.len())?;
247                let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
248                    maximum: MAX_DOCUMENT_DEPTH,
249                })?;
250                for (key, value) in values {
251                    self.length_prefixed(key.as_bytes())?;
252                    self.value(value, child_depth)?;
253                }
254                Ok(())
255            }
256        }
257    }
258
259    fn length_prefixed(&mut self, value: &[u8]) -> Result<(), DocumentError> {
260        self.length(value.len())?;
261        self.append(value)
262    }
263
264    fn length(&mut self, length: usize) -> Result<(), DocumentError> {
265        let encoded = u64::try_from(length).map_err(|_| DocumentError::LengthOverflow)?;
266        self.append(&encoded.to_le_bytes())
267    }
268
269    fn append(&mut self, bytes: &[u8]) -> Result<(), DocumentError> {
270        let next = self
271            .payload
272            .len()
273            .checked_add(bytes.len())
274            .ok_or(DocumentError::LengthOverflow)?;
275        if next > MAX_DOCUMENT_BYTES {
276            return Err(DocumentError::TooLarge {
277                actual: next,
278                maximum: MAX_DOCUMENT_BYTES,
279            });
280        }
281        self.payload.extend_from_slice(bytes);
282        Ok(())
283    }
284}
285
286struct DocumentMeasurer {
287    payload_bytes: usize,
288    nodes: usize,
289}
290
291impl DocumentMeasurer {
292    fn value(&mut self, value: &Value, depth: usize) -> Result<(), DocumentError> {
293        if depth > MAX_DOCUMENT_DEPTH {
294            return Err(DocumentError::TooDeep {
295                maximum: MAX_DOCUMENT_DEPTH,
296            });
297        }
298        self.nodes = self
299            .nodes
300            .checked_add(1)
301            .ok_or(DocumentError::TooManyNodes {
302                maximum: MAX_DOCUMENT_NODES,
303            })?;
304        if self.nodes > MAX_DOCUMENT_NODES {
305            return Err(DocumentError::TooManyNodes {
306                maximum: MAX_DOCUMENT_NODES,
307            });
308        }
309        match value {
310            Value::Null | Value::Boolean(_) => self.append(1),
311            Value::Integer(_) => {
312                self.append(1)?;
313                self.append(8)
314            }
315            Value::String(value) => {
316                self.append(1)?;
317                self.length_prefixed(value.len())
318            }
319            Value::Bytes(value) => {
320                self.append(1)?;
321                self.length_prefixed(value.len())
322            }
323            Value::Array(values) => {
324                self.append(1)?;
325                self.append(8)?;
326                let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
327                    maximum: MAX_DOCUMENT_DEPTH,
328                })?;
329                for value in values {
330                    self.value(value, child_depth)?;
331                }
332                Ok(())
333            }
334            Value::Object(values) => {
335                self.append(1)?;
336                self.append(8)?;
337                let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
338                    maximum: MAX_DOCUMENT_DEPTH,
339                })?;
340                for (key, value) in values {
341                    self.length_prefixed(key.len())?;
342                    self.value(value, child_depth)?;
343                }
344                Ok(())
345            }
346        }
347    }
348
349    fn length_prefixed(&mut self, length: usize) -> Result<(), DocumentError> {
350        self.append(8)?;
351        self.append(length)
352    }
353
354    fn append(&mut self, bytes: usize) -> Result<(), DocumentError> {
355        let next = self
356            .payload_bytes
357            .checked_add(bytes)
358            .ok_or(DocumentError::LengthOverflow)?;
359        if next > MAX_DOCUMENT_BYTES {
360            return Err(DocumentError::TooLarge {
361                actual: next,
362                maximum: MAX_DOCUMENT_BYTES,
363            });
364        }
365        self.payload_bytes = next;
366        Ok(())
367    }
368}
369
370struct Decoder<'payload> {
371    payload: &'payload [u8],
372    position: usize,
373    nodes: usize,
374}
375
376impl Decoder<'_> {
377    fn value(&mut self, depth: usize) -> Result<Value, DocumentError> {
378        if depth > MAX_DOCUMENT_DEPTH {
379            return Err(DocumentError::TooDeep {
380                maximum: MAX_DOCUMENT_DEPTH,
381            });
382        }
383        self.nodes = self
384            .nodes
385            .checked_add(1)
386            .ok_or(DocumentError::TooManyNodes {
387                maximum: MAX_DOCUMENT_NODES,
388            })?;
389        if self.nodes > MAX_DOCUMENT_NODES {
390            return Err(DocumentError::TooManyNodes {
391                maximum: MAX_DOCUMENT_NODES,
392            });
393        }
394        let tag = self.read(1)?[0];
395        match tag {
396            NULL => Ok(Value::Null),
397            FALSE => Ok(Value::Boolean(false)),
398            TRUE => Ok(Value::Boolean(true)),
399            INTEGER => Ok(Value::Integer(i64::from_le_bytes(copy_array(
400                self.read(8)?,
401            )))),
402            STRING => {
403                let bytes = self.length_prefixed()?;
404                let value = std::str::from_utf8(bytes).map_err(|_| DocumentError::InvalidUtf8)?;
405                Ok(Value::String(value.to_owned()))
406            }
407            BYTES => Ok(Value::Bytes(self.length_prefixed()?.to_vec())),
408            ARRAY => self.array(depth),
409            OBJECT => self.object(depth),
410            _ => Err(DocumentError::Invalid {
411                reason: "unknown value tag",
412            }),
413        }
414    }
415
416    fn array(&mut self, depth: usize) -> Result<Value, DocumentError> {
417        let count = self.length()?;
418        if count > MAX_DOCUMENT_NODES {
419            return Err(DocumentError::TooManyNodes {
420                maximum: MAX_DOCUMENT_NODES,
421            });
422        }
423        let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
424            maximum: MAX_DOCUMENT_DEPTH,
425        })?;
426        let mut values = Vec::with_capacity(count);
427        for _ in 0..count {
428            values.push(self.value(child_depth)?);
429        }
430        Ok(Value::Array(values))
431    }
432
433    fn object(&mut self, depth: usize) -> Result<Value, DocumentError> {
434        let count = self.length()?;
435        if count > MAX_DOCUMENT_NODES {
436            return Err(DocumentError::TooManyNodes {
437                maximum: MAX_DOCUMENT_NODES,
438            });
439        }
440        let child_depth = depth.checked_add(1).ok_or(DocumentError::TooDeep {
441            maximum: MAX_DOCUMENT_DEPTH,
442        })?;
443        let mut values = BTreeMap::new();
444        let mut previous: Option<String> = None;
445        for _ in 0..count {
446            let bytes = self.length_prefixed()?;
447            let key = std::str::from_utf8(bytes)
448                .map_err(|_| DocumentError::InvalidUtf8)?
449                .to_owned();
450            if previous.as_ref().is_some_and(|previous| previous >= &key) {
451                return Err(DocumentError::Invalid {
452                    reason: "object keys are not strictly sorted",
453                });
454            }
455            let value = self.value(child_depth)?;
456            previous = Some(key.clone());
457            values.insert(key, value);
458        }
459        Ok(Value::Object(values))
460    }
461
462    fn length_prefixed(&mut self) -> Result<&[u8], DocumentError> {
463        let length = self.length()?;
464        self.read(length)
465    }
466
467    fn length(&mut self) -> Result<usize, DocumentError> {
468        usize::try_from(u64::from_le_bytes(copy_array(self.read(8)?)))
469            .map_err(|_| DocumentError::LengthOverflow)
470    }
471
472    fn read(&mut self, length: usize) -> Result<&[u8], DocumentError> {
473        let end = self
474            .position
475            .checked_add(length)
476            .ok_or(DocumentError::LengthOverflow)?;
477        let Some(value) = self.payload.get(self.position..end) else {
478            return Err(DocumentError::Invalid {
479                reason: "truncated value payload",
480            });
481        };
482        self.position = end;
483        Ok(value)
484    }
485}
486
487fn encode_envelope(payload: &[u8]) -> Result<Vec<u8>, DocumentError> {
488    if payload.len() > MAX_DOCUMENT_BYTES {
489        return Err(DocumentError::TooLarge {
490            actual: payload.len(),
491            maximum: MAX_DOCUMENT_BYTES,
492        });
493    }
494    let payload_length = u64::try_from(payload.len()).map_err(|_| DocumentError::LengthOverflow)?;
495    let capacity = HEADER_LENGTH
496        .checked_add(payload.len())
497        .ok_or(DocumentError::LengthOverflow)?;
498    let mut encoded = vec![0_u8; capacity];
499    encoded[..8].copy_from_slice(&MAGIC);
500    encoded[8..10].copy_from_slice(&DOCUMENT_FORMAT_VERSION.to_le_bytes());
501    encoded[10..12].copy_from_slice(&0_u16.to_le_bytes());
502    encoded[12..20].copy_from_slice(&payload_length.to_le_bytes());
503    encoded[HEADER_LENGTH..].copy_from_slice(payload);
504    let checksum =
505        crc32c::crc32c_append(crc32c::crc32c(&encoded[..CHECKSUM_PREFIX_LENGTH]), payload);
506    encoded[20..24].copy_from_slice(&checksum.to_le_bytes());
507    let mut hasher = blake3::Hasher::new();
508    hasher.update(&encoded[..DIGEST_PREFIX_LENGTH]);
509    hasher.update(payload);
510    encoded[24..56].copy_from_slice(hasher.finalize().as_bytes());
511    Ok(encoded)
512}
513
514fn copy_array<const N: usize>(source: &[u8]) -> [u8; N] {
515    let mut output = [0_u8; N];
516    output.copy_from_slice(source);
517    output
518}
519
520#[cfg(test)]
521mod tests {
522    use std::collections::BTreeMap;
523
524    use crate::Value;
525
526    use super::{
527        DOCUMENT_FORMAT_VERSION, DocumentError, MAX_DOCUMENT_DEPTH, NULL, OBJECT, decode_document,
528        encode_document, encode_envelope, encoded_document_len,
529    };
530
531    #[test]
532    fn canonical_document_round_trips_binary_and_nested_values() -> Result<(), DocumentError> {
533        let value = Value::Object(BTreeMap::from([
534            ("bytes".to_owned(), Value::Bytes(vec![0, 255, 7])),
535            (
536                "nested".to_owned(),
537                Value::Array(vec![Value::Integer(-7), Value::Null]),
538            ),
539        ]));
540        let first = encode_document(&value)?;
541        let second = encode_document(&value)?;
542        assert_eq!(encoded_document_len(&value)?, first.len());
543        assert_eq!(first, second);
544        assert_eq!(decode_document(&first)?, value);
545        Ok(())
546    }
547
548    #[test]
549    fn corruption_and_future_versions_fail_before_decoding() -> Result<(), DocumentError> {
550        let mut corrupted = encode_document(&Value::Integer(7))?;
551        let last = corrupted.len() - 1;
552        corrupted[last] ^= 1;
553        assert_eq!(
554            decode_document(&corrupted),
555            Err(DocumentError::ChecksumMismatch)
556        );
557
558        let mut future = encode_document(&Value::Null)?;
559        future[8..10].copy_from_slice(&(DOCUMENT_FORMAT_VERSION + 1).to_le_bytes());
560        assert_eq!(
561            decode_document(&future),
562            Err(DocumentError::UnsupportedVersion {
563                found: DOCUMENT_FORMAT_VERSION + 1,
564                supported: DOCUMENT_FORMAT_VERSION
565            })
566        );
567        Ok(())
568    }
569
570    #[test]
571    fn depth_is_bounded_during_encoding() {
572        let mut value = Value::Null;
573        for _ in 0..=MAX_DOCUMENT_DEPTH {
574            value = Value::Array(vec![value]);
575        }
576        assert_eq!(
577            encode_document(&value),
578            Err(DocumentError::TooDeep {
579                maximum: MAX_DOCUMENT_DEPTH
580            })
581        );
582    }
583
584    #[test]
585    fn decoder_rejects_noncanonical_object_key_order() -> Result<(), DocumentError> {
586        let mut payload = vec![OBJECT];
587        payload.extend_from_slice(&2_u64.to_le_bytes());
588        payload.extend_from_slice(&1_u64.to_le_bytes());
589        payload.extend_from_slice(b"b");
590        payload.push(NULL);
591        payload.extend_from_slice(&1_u64.to_le_bytes());
592        payload.extend_from_slice(b"a");
593        payload.push(NULL);
594        let encoded = encode_envelope(&payload)?;
595        assert_eq!(
596            decode_document(&encoded),
597            Err(DocumentError::Invalid {
598                reason: "object keys are not strictly sorted"
599            })
600        );
601        Ok(())
602    }
603}
hyphae_query/document.rs

hyphae_query/
document.rs
