vole_document/field/
node.rs

1//! Canonical procedural seed nodes (Phase 11, ADR-0025).
2//!
3//! A [`SeedNode`] describes one **computation**, not one storage slot: a bounded,
4//! versioned materializer over zero or more dependencies, producing a declared
5//! output kind and logical length. Nodes are canonically encoded (little-endian,
6//! length-prefixed, no serde) so that the same computation always hashes to the
7//! same [`NodeId`] regardless of platform or insertion order.
8//!
9//! The node's `content_id` is **not** stored inside the node: it is
10//! `NodeId::of_node(canonical_bytes)`, which is what makes the graph
11//! content-addressed and immutable. Changing a dependency's bytes yields a
12//! different dependency id, hence a different node id; there is no mutation.
13
14use crate::error::{Error, Result};
15use crate::limits::Limits;
16use crate::store::NodeId;
17
18/// Canonical header byte for the node encoding.
19pub const NODE_MAGIC: u8 = 0xB1;
20/// Recommended maximum canonical node size (framing discipline).
21pub const MAX_NODE_BYTES: usize = 64 * 1024;
22/// Maximum dependency fanout of a single node.
23pub const MAX_NODE_DEPS: usize = 256;
24/// The materializer semantics version for v1.
25pub const MATERIALIZER_VERSION: u16 = 1;
26
27/// What a node computes. The numeric values are part of the canonical encoding.
28#[derive(Debug, Clone, Copy, PartialEq, Eq)]
29#[repr(u8)]
30pub enum NodeKind {
31    /// The whole exact source, materialized from the descriptor blob.
32    DocumentExact = 0x01,
33    /// An exact byte span of the source.
34    SourceSlice = 0x02,
35    /// An exact physical revision span.
36    PdfRevision = 0x03,
37    /// An exact indirect-object byte span (`n g obj … endobj`).
38    PdfObject = 0x04,
39    /// The exact encoded bytes of a stream object's data.
40    PdfStreamEncoded = 0x05,
41    /// The decoded (inflated) bytes of a lone `/FlateDecode` stream.
42    PdfStreamDecoded = 0x06,
43    /// A decoded content stream's operator token span.
44    ContentOperators = 0x07,
45    /// A deterministic text-run projection of content operators.
46    TextRuns = 0x08,
47    /// A page's concatenated decoded content stream.
48    PageContent = 0x09,
49    /// A deterministic structured page preview.
50    PagePreview = 0x0A,
51    /// A physical byte span of one resource object referenced by a page.
52    ResourceRef = 0x0B,
53    /// Concatenation of dependency outputs (exact).
54    Concat = 0x0C,
55    /// A raw exact literal held in the seed store.
56    Literal = 0x0D,
57    /// The whole exact package (ZIP/OCF/OPC) source, materialized through the
58    /// descriptor (`serve_document`). Exact (Phase 12.2).
59    PackageRoot = 0x0E,
60    /// One package member's exact raw compressed/stored span (a `SourceSlice`
61    /// with package provenance). Exact (Phase 12.2).
62    PackageMemberRaw = 0x0F,
63    /// One package member's decoded bytes: raw-DEFLATE inflate (method 8) or the
64    /// stored identity (method 0). Derived, never exact (Phase 12.2).
65    PackageMemberDecoded = 0x10,
66    /// The canonical generic-OPC package graph (content types, parts, package and
67    /// part relationships) derived on demand from the exact package source.
68    /// Derived, never exact (Phase 12.3).
69    PackageOpcModel = 0x11,
70    /// The canonical DOCX discovery model (main part, styles part, stories)
71    /// derived on demand from the canonical OPC model. Derived, never exact
72    /// (Phase 12.4).
73    DocxModel = 0x12,
74    /// One WordprocessingML story parsed into its canonical [`crate::adapter::docx::wml::StoryModel`],
75    /// honoring a declared extraction profile. Derived, never exact (Phase 12.4).
76    DocxStory = 0x13,
77    /// The canonical EPUB (OCF) discovery model: `mimetype` conformance facts,
78    /// container rootfiles, and the Package Document metadata/manifest/spine,
79    /// derived on demand from the exact package source. Derived, never exact
80    /// (Phase 12.5).
81    EpubModel = 0x14,
82    /// One spine item's XHTML content document parsed into its bounded native
83    /// content model (headings/paragraphs/lists/tables/links/resources), honoring
84    /// a declared extraction profile. Derived, never exact (Phase 12.6).
85    EpubContent = 0x15,
86    /// A byte-identical shareable resource (image/font/attachment) held inline and
87    /// addressed by **content identity** (Phase 12.8, ADR-0034). Its canonical
88    /// encoding embeds the exact bytes, so two documents carrying the same resource
89    /// share one node id (and one persisted blob) with no second identity scheme.
90    /// Exact (a resource's bytes are the source bytes).
91    ResourceBlob = 0x16,
92    /// The canonical ODT (ODF) discovery model: `mimetype` conformance facts and the
93    /// parsed `META-INF/manifest.xml` file entries with the main content part resolved
94    /// semantically, derived on demand from the exact package source. Derived, never
95    /// exact (Phase 13.3).
96    OdtModel = 0x17,
97    /// The OpenDocument main part (`content.xml`, `office:text`) parsed into its
98    /// bounded native content model (paragraphs/headings/spans/lists/tables/links/
99    /// bookmarks/notes/resources/tracked changes/sections), honoring a declared
100    /// extraction profile. Derived, never exact (Phase 13.3).
101    OdtContent = 0x18,
102    /// The PDF **revision lineage** (Phase 17): a compact JSON projection of the
103    /// physical incremental revision chain (count, ordered indices, byte spans,
104    /// resolved `startxref`/`/Prev`, and per-revision object/stream membership),
105    /// computed once at ingest from the byte-authoritative scan. Derived, never
106    /// exact. There is one document-level node (the whole lineage) and one
107    /// per-revision node.
108    PdfRevisionLineage = 0x19,
109}
110
111impl NodeKind {
112    /// Map a raw kind byte.
113    pub const fn from_u8(b: u8) -> Option<NodeKind> {
114        Some(match b {
115            0x01 => NodeKind::DocumentExact,
116            0x02 => NodeKind::SourceSlice,
117            0x03 => NodeKind::PdfRevision,
118            0x04 => NodeKind::PdfObject,
119            0x05 => NodeKind::PdfStreamEncoded,
120            0x06 => NodeKind::PdfStreamDecoded,
121            0x07 => NodeKind::ContentOperators,
122            0x08 => NodeKind::TextRuns,
123            0x09 => NodeKind::PageContent,
124            0x0A => NodeKind::PagePreview,
125            0x0B => NodeKind::ResourceRef,
126            0x0C => NodeKind::Concat,
127            0x0D => NodeKind::Literal,
128            0x0E => NodeKind::PackageRoot,
129            0x0F => NodeKind::PackageMemberRaw,
130            0x10 => NodeKind::PackageMemberDecoded,
131            0x11 => NodeKind::PackageOpcModel,
132            0x12 => NodeKind::DocxModel,
133            0x13 => NodeKind::DocxStory,
134            0x14 => NodeKind::EpubModel,
135            0x15 => NodeKind::EpubContent,
136            0x16 => NodeKind::ResourceBlob,
137            0x17 => NodeKind::OdtModel,
138            0x18 => NodeKind::OdtContent,
139            0x19 => NodeKind::PdfRevisionLineage,
140            _ => return None,
141        })
142    }
143
144    /// Stable short name.
145    pub const fn name(self) -> &'static str {
146        match self {
147            NodeKind::DocumentExact => "DocumentExact",
148            NodeKind::SourceSlice => "SourceSlice",
149            NodeKind::PdfRevision => "PdfRevision",
150            NodeKind::PdfObject => "PdfObject",
151            NodeKind::PdfStreamEncoded => "PdfStreamEncoded",
152            NodeKind::PdfStreamDecoded => "PdfStreamDecoded",
153            NodeKind::ContentOperators => "ContentOperators",
154            NodeKind::TextRuns => "TextRuns",
155            NodeKind::PageContent => "PageContent",
156            NodeKind::PagePreview => "PagePreview",
157            NodeKind::ResourceRef => "ResourceRef",
158            NodeKind::Concat => "Concat",
159            NodeKind::Literal => "Literal",
160            NodeKind::PackageRoot => "PackageRoot",
161            NodeKind::PackageMemberRaw => "PackageMemberRaw",
162            NodeKind::PackageMemberDecoded => "PackageMemberDecoded",
163            NodeKind::PackageOpcModel => "PackageOpcModel",
164            NodeKind::DocxModel => "DocxModel",
165            NodeKind::DocxStory => "DocxStory",
166            NodeKind::EpubModel => "EpubModel",
167            NodeKind::EpubContent => "EpubContent",
168            NodeKind::ResourceBlob => "ResourceBlob",
169            NodeKind::OdtModel => "OdtModel",
170            NodeKind::OdtContent => "OdtContent",
171            NodeKind::PdfRevisionLineage => "PdfRevisionLineage",
172        }
173    }
174
175    /// Whether the output bytes are an exact, byte-identical observation of the
176    /// source (`true`) or a deterministic derived projection (`false`).
177    ///
178    /// This is the `Q_ref` / `Q_gen` boundary (ADR-0026).
179    pub const fn is_exact(self) -> bool {
180        matches!(
181            self,
182            NodeKind::DocumentExact
183                | NodeKind::SourceSlice
184                | NodeKind::PdfRevision
185                | NodeKind::PdfObject
186                | NodeKind::PdfStreamEncoded
187                | NodeKind::ResourceRef
188                | NodeKind::Concat
189                | NodeKind::Literal
190                // Package physical leaves are exact source spans; a decoded
191                // member (`PackageMemberDecoded`) is derived and is **not** exact.
192                | NodeKind::PackageRoot
193                | NodeKind::PackageMemberRaw
194                // A shared resource is the exact embedded bytes.
195                | NodeKind::ResourceBlob
196        )
197    }
198}
199
200/// A bounded resource envelope declared by a node.
201#[derive(Debug, Clone, Copy, PartialEq, Eq)]
202pub struct NodeLimits {
203    /// Maximum materialized output length this node may produce.
204    pub max_output_bytes: u64,
205    /// Maximum dependency depth permitted below this node.
206    pub max_depth: u16,
207    /// Maximum dependency fanout permitted.
208    pub max_fanout: u16,
209}
210
211impl NodeLimits {
212    /// Conservative defaults used by the PDF inverse compiler.
213    pub const DEFAULT: NodeLimits = NodeLimits {
214        max_output_bytes: 1 << 31,
215        max_depth: 64,
216        max_fanout: MAX_NODE_DEPS as u16,
217    };
218}
219
220/// One canonical procedural seed node.
221#[derive(Debug, Clone, PartialEq, Eq)]
222pub struct SeedNode {
223    /// Computation kind.
224    pub kind: NodeKind,
225    /// Materializer registry id (the kind value for v1).
226    pub materializer_id: u16,
227    /// Materializer semantics version.
228    pub materializer_version: u16,
229    /// Declared logical output length (a bound, checked on materialization).
230    pub logical_output_len: u64,
231    /// Kind-specific canonical parameters.
232    pub params: Vec<u8>,
233    /// Canonical dependency ids actually read (the dynamic read set).
234    pub deps: Vec<NodeId>,
235    /// Short provenance/basis string (adapter-supplied, advisory).
236    pub provenance: String,
237    /// Resource envelope.
238    pub limits: NodeLimits,
239}
240
241impl SeedNode {
242    /// Construct a node with the current materializer version.
243    pub fn new(
244        kind: NodeKind,
245        logical_output_len: u64,
246        params: Vec<u8>,
247        deps: Vec<NodeId>,
248        provenance: impl Into<String>,
249    ) -> Self {
250        SeedNode {
251            kind,
252            materializer_id: kind as u16,
253            materializer_version: MATERIALIZER_VERSION,
254            logical_output_len,
255            params,
256            deps,
257            provenance: provenance.into(),
258            limits: NodeLimits::DEFAULT,
259        }
260    }
261
262    /// Canonically encode this node. The encoding never includes the node id.
263    pub fn encode_canonical(&self) -> Vec<u8> {
264        let mut out = Vec::with_capacity(64 + self.params.len());
265        out.push(NODE_MAGIC);
266        out.push(crate::store::SEED_FORMAT_VERSION);
267        out.push(self.kind as u8);
268        out.push(0); // reserved
269        out.extend_from_slice(&self.materializer_id.to_le_bytes());
270        out.extend_from_slice(&self.materializer_version.to_le_bytes());
271        out.extend_from_slice(&self.logical_output_len.to_le_bytes());
272        out.extend_from_slice(&(self.deps.len() as u32).to_le_bytes());
273        out.extend_from_slice(&(self.params.len() as u32).to_le_bytes());
274        out.extend_from_slice(&self.limits.max_output_bytes.to_le_bytes());
275        out.extend_from_slice(&self.limits.max_depth.to_le_bytes());
276        out.extend_from_slice(&self.limits.max_fanout.to_le_bytes());
277        for dep in &self.deps {
278            out.extend_from_slice(dep.as_bytes());
279        }
280        out.extend_from_slice(&self.params);
281        let prov = self.provenance.as_bytes();
282        out.extend_from_slice(&(prov.len() as u32).to_le_bytes());
283        out.extend_from_slice(prov);
284        out
285    }
286
287    /// Parse a canonical node, enforcing structural bounds.
288    pub fn decode_canonical(bytes: &[u8]) -> Result<SeedNode> {
289        let mut r = Reader::new(bytes);
290        if r.u8()? != NODE_MAGIC {
291            return Err(Error::unsupported_version("seed node: bad magic"));
292        }
293        let version = r.u8()?;
294        if version != crate::store::SEED_FORMAT_VERSION {
295            return Err(Error::unsupported_version(format!(
296                "seed node format version {version} is not supported"
297            )));
298        }
299        let kind_byte = r.u8()?;
300        let kind = NodeKind::from_u8(kind_byte)
301            .ok_or_else(|| Error::unsupported_version(format!("unknown node kind {kind_byte}")))?;
302        let _reserved = r.u8()?;
303        let materializer_id = r.u16()?;
304        let materializer_version = r.u16()?;
305        let logical_output_len = r.u64()?;
306        let dep_count = r.u32()? as usize;
307        let param_len = r.u32()? as usize;
308        let max_output_bytes = r.u64()?;
309        let max_depth = r.u16()?;
310        let max_fanout = r.u16()?;
311        if dep_count > MAX_NODE_DEPS {
312            return Err(Error::resource_limit(format!(
313                "seed node declares {dep_count} deps (max {MAX_NODE_DEPS})"
314            )));
315        }
316        let mut deps = Vec::with_capacity(dep_count);
317        for _ in 0..dep_count {
318            let mut b = [0u8; 32];
319            b.copy_from_slice(r.bytes(32)?);
320            deps.push(NodeId::from_bytes(b));
321        }
322        let params = r.bytes(param_len)?.to_vec();
323        let prov_len = r.u32()? as usize;
324        let prov = r.bytes(prov_len)?;
325        let provenance = core::str::from_utf8(prov)
326            .map_err(|_| Error::usage("seed node provenance is not UTF-8"))?
327            .to_string();
328        if !r.at_end() {
329            return Err(Error::usage("seed node has trailing bytes"));
330        }
331        if materializer_id != kind as u16 {
332            return Err(Error::unsupported_version(
333                "seed node materializer id does not match its kind",
334            ));
335        }
336        Ok(SeedNode {
337            kind,
338            materializer_id,
339            materializer_version,
340            logical_output_len,
341            params,
342            deps,
343            provenance,
344            limits: NodeLimits {
345                max_output_bytes,
346                max_depth,
347                max_fanout,
348            },
349        })
350    }
351
352    /// The content id of this node's canonical encoding.
353    pub fn content_id(&self) -> NodeId {
354        NodeId::of_node(&self.encode_canonical())
355    }
356
357    /// Validate the declared envelope against the global [`Limits`].
358    pub fn check_limits(&self, limits: &Limits) -> Result<()> {
359        if self.logical_output_len > self.limits.max_output_bytes {
360            return Err(Error::resource_limit(format!(
361                "seed node declares output {} > its own cap {}",
362                self.logical_output_len, self.limits.max_output_bytes
363            )));
364        }
365        let _ = limits;
366        Ok(())
367    }
368}
369
370/// A tiny bounds-checked little-endian reader.
371struct Reader<'a> {
372    b: &'a [u8],
373    at: usize,
374}
375
376impl<'a> Reader<'a> {
377    fn new(b: &'a [u8]) -> Self {
378        Reader { b, at: 0 }
379    }
380    fn bytes(&mut self, n: usize) -> Result<&'a [u8]> {
381        let end = self
382            .at
383            .checked_add(n)
384            .ok_or_else(|| Error::usage("seed node read overflow"))?;
385        if end > self.b.len() {
386            return Err(Error::usage("truncated seed node"));
387        }
388        let s = &self.b[self.at..end];
389        self.at = end;
390        Ok(s)
391    }
392    fn u8(&mut self) -> Result<u8> {
393        Ok(self.bytes(1)?[0])
394    }
395    fn u16(&mut self) -> Result<u16> {
396        let b = self.bytes(2)?;
397        Ok(u16::from_le_bytes([b[0], b[1]]))
398    }
399    fn u32(&mut self) -> Result<u32> {
400        let b = self.bytes(4)?;
401        Ok(u32::from_le_bytes([b[0], b[1], b[2], b[3]]))
402    }
403    fn u64(&mut self) -> Result<u64> {
404        let b = self.bytes(8)?;
405        let mut a = [0u8; 8];
406        a.copy_from_slice(b);
407        Ok(u64::from_le_bytes(a))
408    }
409    fn at_end(&self) -> bool {
410        self.at == self.b.len()
411    }
412}
413
414/// Encode an `[offset, len]` parameter block.
415pub fn span_params(offset: u64, len: u64) -> Vec<u8> {
416    let mut p = Vec::with_capacity(16);
417    p.extend_from_slice(&offset.to_le_bytes());
418    p.extend_from_slice(&len.to_le_bytes());
419    p
420}
421
422/// Decode an `[offset, len]` parameter block.
423pub fn read_span_params(params: &[u8]) -> Result<(u64, u64)> {
424    if params.len() != 16 {
425        return Err(Error::usage("span params must be 16 bytes"));
426    }
427    let mut a = [0u8; 8];
428    a.copy_from_slice(&params[0..8]);
429    let offset = u64::from_le_bytes(a);
430    a.copy_from_slice(&params[8..16]);
431    let len = u64::from_le_bytes(a);
432    Ok((offset, len))
433}
434
435/// Encode a `(u32, u16, ...)` object-identity parameter block: `object`,
436/// `generation`, then a trailing kind-specific `u64`.
437pub fn object_params(object: u32, generation: u16, extra: u64) -> Vec<u8> {
438    let mut p = Vec::with_capacity(16);
439    p.extend_from_slice(&object.to_le_bytes());
440    p.extend_from_slice(&generation.to_le_bytes());
441    p.extend_from_slice(&0u16.to_le_bytes());
442    p.extend_from_slice(&extra.to_le_bytes());
443    p
444}
445
446/// Decode an object-identity parameter block.
447pub fn read_object_params(params: &[u8]) -> Result<(u32, u16, u64)> {
448    if params.len() != 16 {
449        return Err(Error::usage("object params must be 16 bytes"));
450    }
451    let object = u32::from_le_bytes([params[0], params[1], params[2], params[3]]);
452    let generation = u16::from_le_bytes([params[4], params[5]]);
453    let mut a = [0u8; 8];
454    a.copy_from_slice(&params[8..16]);
455    let extra = u64::from_le_bytes(a);
456    Ok((object, generation, extra))
457}
458
459/// Encode a single `u32` parameter.
460pub fn u32_params(v: u32) -> Vec<u8> {
461    v.to_le_bytes().to_vec()
462}
463
464/// Decode a single `u32` parameter.
465pub fn read_u32_params(params: &[u8]) -> Result<u32> {
466    if params.len() != 4 {
467        return Err(Error::usage("u32 params must be 4 bytes"));
468    }
469    Ok(u32::from_le_bytes([
470        params[0], params[1], params[2], params[3],
471    ]))
472}
473
474#[cfg(test)]
475mod tests {
476    use super::*;
477
478    #[test]
479    fn canonical_roundtrip_is_stable() {
480        let n = SeedNode::new(
481            NodeKind::PdfStreamDecoded,
482            4096,
483            span_params(100, 200),
484            vec![NodeId::from_bytes([7u8; 32])],
485            "pdf:stream-decoded",
486        );
487        let enc = n.encode_canonical();
488        let back = SeedNode::decode_canonical(&enc).unwrap();
489        assert_eq!(n, back);
490        assert_eq!(back.content_id(), n.content_id());
491        assert_eq!(n.encode_canonical(), enc);
492    }
493
494    #[test]
495    fn dependency_change_changes_id() {
496        let a = SeedNode::new(
497            NodeKind::Concat,
498            10,
499            vec![],
500            vec![NodeId::from_bytes([1u8; 32])],
501            "t",
502        );
503        let b = SeedNode::new(
504            NodeKind::Concat,
505            10,
506            vec![],
507            vec![NodeId::from_bytes([2u8; 32])],
508            "t",
509        );
510        assert_ne!(a.content_id(), b.content_id());
511    }
512
513    #[test]
514    fn unknown_kind_and_version_fail_closed() {
515        let mut n = SeedNode::new(NodeKind::Literal, 1, vec![9], vec![], "t").encode_canonical();
516        n[0] = 0x00;
517        assert!(SeedNode::decode_canonical(&n).is_err());
518        let mut n2 = SeedNode::new(NodeKind::Literal, 1, vec![9], vec![], "t").encode_canonical();
519        n2[1] = 0x7F;
520        assert!(SeedNode::decode_canonical(&n2).is_err());
521    }
522
523    #[test]
524    fn trailing_bytes_are_rejected() {
525        let mut enc = SeedNode::new(NodeKind::Literal, 1, vec![], vec![], "t").encode_canonical();
526        enc.push(0);
527        assert!(SeedNode::decode_canonical(&enc).is_err());
528    }
529
530    #[test]
531    fn param_helpers_roundtrip() {
532        let (o, l) = read_span_params(&span_params(5, 9)).unwrap();
533        assert_eq!((o, l), (5, 9));
534        let (ob, g, e) = read_object_params(&object_params(42, 3, 77)).unwrap();
535        assert_eq!((ob, g, e), (42, 3, 77));
536        assert_eq!(read_u32_params(&u32_params(1234)).unwrap(), 1234);
537    }
538}
vole_document/field/node.rs

vole_document/field/
node.rs
