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}
58
59impl NodeKind {
60    /// Map a raw kind byte.
61    pub const fn from_u8(b: u8) -> Option<NodeKind> {
62        Some(match b {
63            0x01 => NodeKind::DocumentExact,
64            0x02 => NodeKind::SourceSlice,
65            0x03 => NodeKind::PdfRevision,
66            0x04 => NodeKind::PdfObject,
67            0x05 => NodeKind::PdfStreamEncoded,
68            0x06 => NodeKind::PdfStreamDecoded,
69            0x07 => NodeKind::ContentOperators,
70            0x08 => NodeKind::TextRuns,
71            0x09 => NodeKind::PageContent,
72            0x0A => NodeKind::PagePreview,
73            0x0B => NodeKind::ResourceRef,
74            0x0C => NodeKind::Concat,
75            0x0D => NodeKind::Literal,
76            _ => return None,
77        })
78    }
79
80    /// Stable short name.
81    pub const fn name(self) -> &'static str {
82        match self {
83            NodeKind::DocumentExact => "DocumentExact",
84            NodeKind::SourceSlice => "SourceSlice",
85            NodeKind::PdfRevision => "PdfRevision",
86            NodeKind::PdfObject => "PdfObject",
87            NodeKind::PdfStreamEncoded => "PdfStreamEncoded",
88            NodeKind::PdfStreamDecoded => "PdfStreamDecoded",
89            NodeKind::ContentOperators => "ContentOperators",
90            NodeKind::TextRuns => "TextRuns",
91            NodeKind::PageContent => "PageContent",
92            NodeKind::PagePreview => "PagePreview",
93            NodeKind::ResourceRef => "ResourceRef",
94            NodeKind::Concat => "Concat",
95            NodeKind::Literal => "Literal",
96        }
97    }
98
99    /// Whether the output bytes are an exact, byte-identical observation of the
100    /// source (`true`) or a deterministic derived projection (`false`).
101    ///
102    /// This is the `Q_ref` / `Q_gen` boundary (ADR-0026).
103    pub const fn is_exact(self) -> bool {
104        matches!(
105            self,
106            NodeKind::DocumentExact
107                | NodeKind::SourceSlice
108                | NodeKind::PdfRevision
109                | NodeKind::PdfObject
110                | NodeKind::PdfStreamEncoded
111                | NodeKind::ResourceRef
112                | NodeKind::Concat
113                | NodeKind::Literal
114        )
115    }
116}
117
118/// A bounded resource envelope declared by a node.
119#[derive(Debug, Clone, Copy, PartialEq, Eq)]
120pub struct NodeLimits {
121    /// Maximum materialized output length this node may produce.
122    pub max_output_bytes: u64,
123    /// Maximum dependency depth permitted below this node.
124    pub max_depth: u16,
125    /// Maximum dependency fanout permitted.
126    pub max_fanout: u16,
127}
128
129impl NodeLimits {
130    /// Conservative defaults used by the PDF inverse compiler.
131    pub const DEFAULT: NodeLimits = NodeLimits {
132        max_output_bytes: 1 << 31,
133        max_depth: 64,
134        max_fanout: MAX_NODE_DEPS as u16,
135    };
136}
137
138/// One canonical procedural seed node.
139#[derive(Debug, Clone, PartialEq, Eq)]
140pub struct SeedNode {
141    /// Computation kind.
142    pub kind: NodeKind,
143    /// Materializer registry id (the kind value for v1).
144    pub materializer_id: u16,
145    /// Materializer semantics version.
146    pub materializer_version: u16,
147    /// Declared logical output length (a bound, checked on materialization).
148    pub logical_output_len: u64,
149    /// Kind-specific canonical parameters.
150    pub params: Vec<u8>,
151    /// Canonical dependency ids actually read (the dynamic read set).
152    pub deps: Vec<NodeId>,
153    /// Short provenance/basis string (adapter-supplied, advisory).
154    pub provenance: String,
155    /// Resource envelope.
156    pub limits: NodeLimits,
157}
158
159impl SeedNode {
160    /// Construct a node with the current materializer version.
161    pub fn new(
162        kind: NodeKind,
163        logical_output_len: u64,
164        params: Vec<u8>,
165        deps: Vec<NodeId>,
166        provenance: impl Into<String>,
167    ) -> Self {
168        SeedNode {
169            kind,
170            materializer_id: kind as u16,
171            materializer_version: MATERIALIZER_VERSION,
172            logical_output_len,
173            params,
174            deps,
175            provenance: provenance.into(),
176            limits: NodeLimits::DEFAULT,
177        }
178    }
179
180    /// Canonically encode this node. The encoding never includes the node id.
181    pub fn encode_canonical(&self) -> Vec<u8> {
182        let mut out = Vec::with_capacity(64 + self.params.len());
183        out.push(NODE_MAGIC);
184        out.push(crate::store::SEED_FORMAT_VERSION);
185        out.push(self.kind as u8);
186        out.push(0); // reserved
187        out.extend_from_slice(&self.materializer_id.to_le_bytes());
188        out.extend_from_slice(&self.materializer_version.to_le_bytes());
189        out.extend_from_slice(&self.logical_output_len.to_le_bytes());
190        out.extend_from_slice(&(self.deps.len() as u32).to_le_bytes());
191        out.extend_from_slice(&(self.params.len() as u32).to_le_bytes());
192        out.extend_from_slice(&self.limits.max_output_bytes.to_le_bytes());
193        out.extend_from_slice(&self.limits.max_depth.to_le_bytes());
194        out.extend_from_slice(&self.limits.max_fanout.to_le_bytes());
195        for dep in &self.deps {
196            out.extend_from_slice(dep.as_bytes());
197        }
198        out.extend_from_slice(&self.params);
199        let prov = self.provenance.as_bytes();
200        out.extend_from_slice(&(prov.len() as u32).to_le_bytes());
201        out.extend_from_slice(prov);
202        out
203    }
204
205    /// Parse a canonical node, enforcing structural bounds.
206    pub fn decode_canonical(bytes: &[u8]) -> Result<SeedNode> {
207        let mut r = Reader::new(bytes);
208        if r.u8()? != NODE_MAGIC {
209            return Err(Error::unsupported_version("seed node: bad magic"));
210        }
211        let version = r.u8()?;
212        if version != crate::store::SEED_FORMAT_VERSION {
213            return Err(Error::unsupported_version(format!(
214                "seed node format version {version} is not supported"
215            )));
216        }
217        let kind_byte = r.u8()?;
218        let kind = NodeKind::from_u8(kind_byte)
219            .ok_or_else(|| Error::unsupported_version(format!("unknown node kind {kind_byte}")))?;
220        let _reserved = r.u8()?;
221        let materializer_id = r.u16()?;
222        let materializer_version = r.u16()?;
223        let logical_output_len = r.u64()?;
224        let dep_count = r.u32()? as usize;
225        let param_len = r.u32()? as usize;
226        let max_output_bytes = r.u64()?;
227        let max_depth = r.u16()?;
228        let max_fanout = r.u16()?;
229        if dep_count > MAX_NODE_DEPS {
230            return Err(Error::resource_limit(format!(
231                "seed node declares {dep_count} deps (max {MAX_NODE_DEPS})"
232            )));
233        }
234        let mut deps = Vec::with_capacity(dep_count);
235        for _ in 0..dep_count {
236            let mut b = [0u8; 32];
237            b.copy_from_slice(r.bytes(32)?);
238            deps.push(NodeId::from_bytes(b));
239        }
240        let params = r.bytes(param_len)?.to_vec();
241        let prov_len = r.u32()? as usize;
242        let prov = r.bytes(prov_len)?;
243        let provenance = core::str::from_utf8(prov)
244            .map_err(|_| Error::usage("seed node provenance is not UTF-8"))?
245            .to_string();
246        if !r.at_end() {
247            return Err(Error::usage("seed node has trailing bytes"));
248        }
249        if materializer_id != kind as u16 {
250            return Err(Error::unsupported_version(
251                "seed node materializer id does not match its kind",
252            ));
253        }
254        Ok(SeedNode {
255            kind,
256            materializer_id,
257            materializer_version,
258            logical_output_len,
259            params,
260            deps,
261            provenance,
262            limits: NodeLimits {
263                max_output_bytes,
264                max_depth,
265                max_fanout,
266            },
267        })
268    }
269
270    /// The content id of this node's canonical encoding.
271    pub fn content_id(&self) -> NodeId {
272        NodeId::of_node(&self.encode_canonical())
273    }
274
275    /// Validate the declared envelope against the global [`Limits`].
276    pub fn check_limits(&self, limits: &Limits) -> Result<()> {
277        if self.logical_output_len > self.limits.max_output_bytes {
278            return Err(Error::resource_limit(format!(
279                "seed node declares output {} > its own cap {}",
280                self.logical_output_len, self.limits.max_output_bytes
281            )));
282        }
283        let _ = limits;
284        Ok(())
285    }
286}
287
288/// A tiny bounds-checked little-endian reader.
289struct Reader<'a> {
290    b: &'a [u8],
291    at: usize,
292}
293
294impl<'a> Reader<'a> {
295    fn new(b: &'a [u8]) -> Self {
296        Reader { b, at: 0 }
297    }
298    fn bytes(&mut self, n: usize) -> Result<&'a [u8]> {
299        let end = self
300            .at
301            .checked_add(n)
302            .ok_or_else(|| Error::usage("seed node read overflow"))?;
303        if end > self.b.len() {
304            return Err(Error::usage("truncated seed node"));
305        }
306        let s = &self.b[self.at..end];
307        self.at = end;
308        Ok(s)
309    }
310    fn u8(&mut self) -> Result<u8> {
311        Ok(self.bytes(1)?[0])
312    }
313    fn u16(&mut self) -> Result<u16> {
314        let b = self.bytes(2)?;
315        Ok(u16::from_le_bytes([b[0], b[1]]))
316    }
317    fn u32(&mut self) -> Result<u32> {
318        let b = self.bytes(4)?;
319        Ok(u32::from_le_bytes([b[0], b[1], b[2], b[3]]))
320    }
321    fn u64(&mut self) -> Result<u64> {
322        let b = self.bytes(8)?;
323        let mut a = [0u8; 8];
324        a.copy_from_slice(b);
325        Ok(u64::from_le_bytes(a))
326    }
327    fn at_end(&self) -> bool {
328        self.at == self.b.len()
329    }
330}
331
332/// Encode an `[offset, len]` parameter block.
333pub fn span_params(offset: u64, len: u64) -> Vec<u8> {
334    let mut p = Vec::with_capacity(16);
335    p.extend_from_slice(&offset.to_le_bytes());
336    p.extend_from_slice(&len.to_le_bytes());
337    p
338}
339
340/// Decode an `[offset, len]` parameter block.
341pub fn read_span_params(params: &[u8]) -> Result<(u64, u64)> {
342    if params.len() != 16 {
343        return Err(Error::usage("span params must be 16 bytes"));
344    }
345    let mut a = [0u8; 8];
346    a.copy_from_slice(&params[0..8]);
347    let offset = u64::from_le_bytes(a);
348    a.copy_from_slice(&params[8..16]);
349    let len = u64::from_le_bytes(a);
350    Ok((offset, len))
351}
352
353/// Encode a `(u32, u16, ...)` object-identity parameter block: `object`,
354/// `generation`, then a trailing kind-specific `u64`.
355pub fn object_params(object: u32, generation: u16, extra: u64) -> Vec<u8> {
356    let mut p = Vec::with_capacity(16);
357    p.extend_from_slice(&object.to_le_bytes());
358    p.extend_from_slice(&generation.to_le_bytes());
359    p.extend_from_slice(&0u16.to_le_bytes());
360    p.extend_from_slice(&extra.to_le_bytes());
361    p
362}
363
364/// Decode an object-identity parameter block.
365pub fn read_object_params(params: &[u8]) -> Result<(u32, u16, u64)> {
366    if params.len() != 16 {
367        return Err(Error::usage("object params must be 16 bytes"));
368    }
369    let object = u32::from_le_bytes([params[0], params[1], params[2], params[3]]);
370    let generation = u16::from_le_bytes([params[4], params[5]]);
371    let mut a = [0u8; 8];
372    a.copy_from_slice(&params[8..16]);
373    let extra = u64::from_le_bytes(a);
374    Ok((object, generation, extra))
375}
376
377/// Encode a single `u32` parameter.
378pub fn u32_params(v: u32) -> Vec<u8> {
379    v.to_le_bytes().to_vec()
380}
381
382/// Decode a single `u32` parameter.
383pub fn read_u32_params(params: &[u8]) -> Result<u32> {
384    if params.len() != 4 {
385        return Err(Error::usage("u32 params must be 4 bytes"));
386    }
387    Ok(u32::from_le_bytes([
388        params[0], params[1], params[2], params[3],
389    ]))
390}
391
392#[cfg(test)]
393mod tests {
394    use super::*;
395
396    #[test]
397    fn canonical_roundtrip_is_stable() {
398        let n = SeedNode::new(
399            NodeKind::PdfStreamDecoded,
400            4096,
401            span_params(100, 200),
402            vec![NodeId::from_bytes([7u8; 32])],
403            "pdf:stream-decoded",
404        );
405        let enc = n.encode_canonical();
406        let back = SeedNode::decode_canonical(&enc).unwrap();
407        assert_eq!(n, back);
408        assert_eq!(back.content_id(), n.content_id());
409        assert_eq!(n.encode_canonical(), enc);
410    }
411
412    #[test]
413    fn dependency_change_changes_id() {
414        let a = SeedNode::new(
415            NodeKind::Concat,
416            10,
417            vec![],
418            vec![NodeId::from_bytes([1u8; 32])],
419            "t",
420        );
421        let b = SeedNode::new(
422            NodeKind::Concat,
423            10,
424            vec![],
425            vec![NodeId::from_bytes([2u8; 32])],
426            "t",
427        );
428        assert_ne!(a.content_id(), b.content_id());
429    }
430
431    #[test]
432    fn unknown_kind_and_version_fail_closed() {
433        let mut n = SeedNode::new(NodeKind::Literal, 1, vec![9], vec![], "t").encode_canonical();
434        n[0] = 0x00;
435        assert!(SeedNode::decode_canonical(&n).is_err());
436        let mut n2 = SeedNode::new(NodeKind::Literal, 1, vec![9], vec![], "t").encode_canonical();
437        n2[1] = 0x7F;
438        assert!(SeedNode::decode_canonical(&n2).is_err());
439    }
440
441    #[test]
442    fn trailing_bytes_are_rejected() {
443        let mut enc = SeedNode::new(NodeKind::Literal, 1, vec![], vec![], "t").encode_canonical();
444        enc.push(0);
445        assert!(SeedNode::decode_canonical(&enc).is_err());
446    }
447
448    #[test]
449    fn param_helpers_roundtrip() {
450        let (o, l) = read_span_params(&span_params(5, 9)).unwrap();
451        assert_eq!((o, l), (5, 9));
452        let (ob, g, e) = read_object_params(&object_params(42, 3, 77)).unwrap();
453        assert_eq!((ob, g, e), (42, 3, 77));
454        assert_eq!(read_u32_params(&u32_params(1234)).unwrap(), 1234);
455    }
456}
vole_document/field/node.rs

vole_document/field/
node.rs
