Skip to main content

triblespace_paths/
persistence.rs

1use std::collections::BTreeSet;
2use std::error::Error;
3use std::fmt;
4
5use triblespace_core::blob::{Blob, BlobEncoding};
6use triblespace_core::id::{ExclusiveId, Id};
7use triblespace_core::id_hex;
8use triblespace_core::inline::encodings::genid::GenId;
9use triblespace_core::inline::encodings::hash::{Blake3, Handle, Hash};
10use triblespace_core::inline::encodings::iu256::U256BE;
11use triblespace_core::inline::Inline;
12use triblespace_core::metadata::{self, MetaDescribe};
13use triblespace_core::prelude::{attributes, entity};
14use triblespace_core::trible::Fragment;
15
16use crate::{Automaton, GraphEdge, PathError, PathSummary, Step};
17
18const HEADER_LEN: usize = 48;
19const AUTOMATON_BLOB_HEADER_LEN: usize = 40;
20const AUTOMATON_BLOB_VERSION: u32 = 1;
21// The automaton blob domain separator is the bytes of the stable
22// path-summary-v2 algorithm anchor `341216BFE738E2D82BFFF96F52E7FE06`, minted
23// with `trible genid` on 2026-07-28 when canonical summaries were restricted
24// to matched support plus nullable identity. This is deliberately the exact
25// wire previously hashed by `automaton_fingerprint`: retaining those bytes as
26// a blob turns every existing fingerprint into its content handle without
27// changing one path-summary byte.
28const AUTOMATON_BLOB_DOMAIN: [u8; 16] = [
29    0x34, 0x12, 0x16, 0xbf, 0xe7, 0x38, 0xe2, 0xd8, 0x2b, 0xff, 0xf9, 0x6f, 0x52, 0xe7, 0xfe, 0x06,
30];
31
32attributes! {
33    /// Canonical BLAKE3 fingerprint of the fixed path automaton. Minted with
34    /// `trible genid` on 2026-07-28.
35    "77DF5A905CCE3B0643BB02999F73BE4C" unsafe as pub path_automaton_fingerprint: Hash<Blake3>;
36    /// Number of states in the canonical path automaton. Minted with
37    /// `trible genid` on 2026-08-29.
38    "562D157447DBE25FE8E6DCB95C5A5AB4" as pub path_automaton_state_count: U256BE;
39    /// Initial state of the canonical path automaton. Repeated on the
40    /// concrete mapping entity. Minted with `trible genid` on 2026-08-29.
41    "EE0D84553EB07FD3E75CD2709ED50E79" as pub path_automaton_initial_state: U256BE;
42    /// Accepting state of the canonical path automaton. Repeated on the
43    /// concrete mapping entity. Minted with `trible genid` on 2026-08-29.
44    "4D10E8C83A816E1D888AD243B1DBD5C7" as pub path_automaton_accepting_state: U256BE;
45    /// Intrinsic transition entity belonging to the canonical path automaton.
46    /// Repeated on the concrete mapping entity. Minted with `trible genid` on
47    /// 2026-08-29.
48    "4828A5918A259F89038041053EA720CC" as pub path_automaton_transition: GenId;
49    /// Source state of one path-automaton transition. Minted with
50    /// `trible genid` on 2026-08-29.
51    "15FBA850D9AC99B7CF8D7842FC5F77B3" as pub path_transition_from: U256BE;
52    /// Target state of one path-automaton transition. Minted with
53    /// `trible genid` on 2026-08-29.
54    "A8F46B12D94B7400F052C45ED579873E" as pub path_transition_to: U256BE;
55    /// Canonical transition opcode: forward, reverse, forward-except, or
56    /// reverse-except. Minted with `trible genid` on 2026-08-29.
57    "08B0B01EFE6E68AB85DF4F0967D914B8" as pub path_transition_kind: U256BE;
58    /// Attribute label carried by one transition. Exact forward/reverse
59    /// transitions have one; exclusion transitions have zero or more. Minted
60    /// with `trible genid` on 2026-08-29.
61    "FD88EA3256CD24545BEB7759E7DBA6FA" as pub path_transition_label: U256BE;
62}
63
64/// Canonical portable bytes of one fixed epsilon-free path automaton.
65///
66/// A [`PathSummaryBlob`] stores this blob's content handle in its first 32
67/// bytes. The automaton is therefore an immutable representation dependency,
68/// not descriptor-local decoding state. The canonical wire is byte-for-byte
69/// the input historically used by [`automaton_fingerprint`], preserving every
70/// existing summary handle.
71pub struct PathAutomatonBlob;
72
73impl BlobEncoding for PathAutomatonBlob {}
74
75impl MetaDescribe for PathAutomatonBlob {
76    fn describe() -> Fragment {
77        // Minted with `trible genid` on 2026-09-04:
78        // 5360AFD4486A38C31C5D73A290D8B54A
79        let id: Id = id_hex!("5360AFD4486A38C31C5D73A290D8B54A");
80        entity! { ExclusiveId::force_ref(&id) @
81            metadata::name: "path-automaton-v1",
82            metadata::description: "Canonical portable epsilon-free path automaton: fixed domain and version, state count, ordered initial and accepting state sets, and ordered labeled transitions. Its content handle is embedded by PathSummaryBlob as an immutable representation dependency.",
83            metadata::tag: metadata::KIND_BLOB_ENCODING,
84        }
85    }
86}
87
88/// Failure to decode one canonical [`PathAutomatonBlob`].
89#[derive(Clone, Debug, Eq, PartialEq)]
90pub enum PathAutomatonBlobError {
91    /// The fixed prefix or one count-delimited section is truncated.
92    BadLength,
93    /// The blob does not carry the canonical path-automaton domain.
94    WrongDomain,
95    /// The blob uses an unknown canonical wire version.
96    UnsupportedVersion(u32),
97    /// A transition carries an unknown step opcode.
98    InvalidOpcode(u8),
99    /// An exact forward or reverse transition does not carry one label.
100    InvalidExactLabelCount,
101    /// State numbers or mandatory state sets do not form an automaton.
102    InvalidAutomaton(crate::AutomatonError),
103    /// The decoded automaton re-encodes to different bytes.
104    NonCanonical,
105}
106
107impl fmt::Display for PathAutomatonBlobError {
108    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
109        match self {
110            Self::BadLength => formatter.write_str("path-automaton blob has an invalid length"),
111            Self::WrongDomain => formatter.write_str("path-automaton blob has the wrong domain"),
112            Self::UnsupportedVersion(version) => {
113                write!(
114                    formatter,
115                    "unsupported path-automaton blob version {version}"
116                )
117            }
118            Self::InvalidOpcode(opcode) => {
119                write!(
120                    formatter,
121                    "path-automaton transition has invalid opcode {opcode}"
122                )
123            }
124            Self::InvalidExactLabelCount => formatter
125                .write_str("an exact path-automaton transition must carry exactly one label"),
126            Self::InvalidAutomaton(source) => source.fmt(formatter),
127            Self::NonCanonical => {
128                formatter.write_str("path-automaton blob is not canonically encoded")
129            }
130        }
131    }
132}
133
134impl Error for PathAutomatonBlobError {
135    fn source(&self) -> Option<&(dyn Error + 'static)> {
136        match self {
137            Self::InvalidAutomaton(source) => Some(source),
138            Self::BadLength
139            | Self::WrongDomain
140            | Self::UnsupportedVersion(_)
141            | Self::InvalidOpcode(_)
142            | Self::InvalidExactLabelCount
143            | Self::NonCanonical => None,
144        }
145    }
146}
147
148/// Canonical direct-product summary bytes for one fixed automaton.
149pub struct PathSummaryBlob;
150
151impl BlobEncoding for PathSummaryBlob {}
152
153impl MetaDescribe for PathSummaryBlob {
154    fn describe() -> Fragment {
155        // Minted with `trible genid` on 2026-07-28 when canonical-domain
156        // validation changed to matched support plus nullable identity.
157        let id: Id = id_hex!("F15A8487F9372278E10F220DC37C2888");
158        entity! { ExclusiveId::force_ref(&id) @
159            metadata::name: "path-summary-v2",
160            metadata::description: "Canonical fixed-header path summary: the sorted graph-term domain required by one fixed automaton followed by sorted direct product arcs. Nullable automata retain the complete supplied endpoint universe; the 48-byte zero-vertex form is the canonical empty summary.",
161            metadata::tag: metadata::KIND_BLOB_ENCODING,
162        }
163    }
164}
165
166/// Canonical path-summary validation failure.
167#[derive(Clone, Debug, Eq, PartialEq)]
168pub enum PathSummaryBlobError {
169    /// The fixed header or payload length is invalid.
170    BadLength,
171    /// The blob belongs to a different fixed automaton.
172    DifferentAutomaton,
173    /// A non-nullable summary retained vertices outside matched-edge support.
174    NoncanonicalDomain,
175    /// Vertex values are not strictly increasing.
176    VertexOrder,
177    /// Product arcs are not strictly increasing.
178    ArcOrder,
179    /// A product ordinal lies outside the declared carrier.
180    ArcOutOfBounds,
181    /// An arc's source/destination state pair is absent from the automaton.
182    InvalidStatePair,
183    /// Two individually valid summaries could not be joined.
184    Join(PathError),
185    /// A length or carrier calculation overflowed its representation.
186    CapacityOverflow,
187}
188
189impl fmt::Display for PathSummaryBlobError {
190    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
191        if let Self::Join(source) = self {
192            return write!(f, "cannot join path summaries: {source}");
193        }
194        let message = match self {
195            Self::BadLength => "path-summary blob has an invalid length",
196            Self::DifferentAutomaton => "path-summary blob belongs to a different automaton",
197            Self::NoncanonicalDomain => {
198                "a non-nullable path summary contains vertices outside matched-edge support"
199            }
200            Self::VertexOrder => "path-summary vertices are not strictly ordered",
201            Self::ArcOrder => "path-summary arcs are not strictly ordered",
202            Self::ArcOutOfBounds => "path-summary arc is outside the product carrier",
203            Self::InvalidStatePair => "path-summary arc uses an impossible automaton state pair",
204            Self::CapacityOverflow => "path-summary dimensions overflow their representation",
205            Self::Join(_) => unreachable!("handled above"),
206        };
207        f.write_str(message)
208    }
209}
210
211impl Error for PathSummaryBlobError {
212    fn source(&self) -> Option<&(dyn Error + 'static)> {
213        match self {
214            Self::Join(source) => Some(source),
215            _ => None,
216        }
217    }
218}
219
220impl PathSummaryBlob {
221    /// Read the canonical automaton dependency embedded at offset zero.
222    ///
223    /// The 32 bytes were historically described as the automaton fingerprint.
224    /// Because that fingerprint hashes the exact canonical
225    /// [`PathAutomatonBlob`] bytes, it is also the typed content handle without
226    /// any format change.
227    pub fn automaton_handle(
228        blob: &Blob<Self>,
229    ) -> Result<Inline<Handle<PathAutomatonBlob>>, PathSummaryBlobError> {
230        if blob.bytes.len() < HEADER_LEN {
231            return Err(PathSummaryBlobError::BadLength);
232        }
233        Ok(Inline::new(
234            blob.bytes.as_ref()[..32]
235                .try_into()
236                .expect("checked 32-byte automaton handle"),
237        ))
238    }
239
240    /// Canonical bottom element for one fixed automaton.
241    pub fn empty(automaton: &Automaton) -> Blob<Self> {
242        let summary = PathSummary::from_edges(automaton.clone(), std::iter::empty::<GraphEdge>());
243        Self::encode(&summary).expect("the fixed empty path-summary construction cannot fail")
244    }
245
246    /// Encode one canonical constructional summary.
247    ///
248    /// Product arcs use full-domain `u32` ordinals on disk. A persisted
249    /// nullable summary therefore still requires `|U| * |Q| <= u32::MAX`,
250    /// even though materialization closes only the smaller matched support.
251    /// The empty summary is the fixed 48-byte header with zero vertices and
252    /// arcs; retaining it makes derivation a total join homomorphism.
253    pub fn encode(summary: &PathSummary) -> Result<Blob<Self>, PathSummaryBlobError> {
254        if !summary.has_canonical_domain() {
255            return Err(PathSummaryBlobError::NoncanonicalDomain);
256        }
257        let vertex_count = u32::try_from(summary.vertices().len())
258            .map_err(|_| PathSummaryBlobError::CapacityOverflow)?;
259        checked_product_count(summary.vertices().len(), summary.automaton().state_count())?;
260        let arcs = summary.ordinal_arcs().collect::<Vec<_>>();
261        let arc_count =
262            u64::try_from(arcs.len()).map_err(|_| PathSummaryBlobError::CapacityOverflow)?;
263        let vertex_bytes = summary
264            .vertices()
265            .len()
266            .checked_mul(32)
267            .ok_or(PathSummaryBlobError::CapacityOverflow)?;
268        let arc_bytes = arcs
269            .len()
270            .checked_mul(8)
271            .ok_or(PathSummaryBlobError::CapacityOverflow)?;
272        let capacity = HEADER_LEN
273            .checked_add(vertex_bytes)
274            .and_then(|length| length.checked_add(arc_bytes))
275            .ok_or(PathSummaryBlobError::CapacityOverflow)?;
276        let automaton = PathAutomatonBlob::encode(summary.automaton()).get_handle();
277
278        let mut bytes = Vec::with_capacity(capacity);
279        bytes.extend_from_slice(&automaton.raw);
280        bytes.extend_from_slice(&summary.automaton().state_count().to_le_bytes());
281        bytes.extend_from_slice(&vertex_count.to_le_bytes());
282        bytes.extend_from_slice(&arc_count.to_le_bytes());
283        for vertex in summary.vertices() {
284            bytes.extend_from_slice(vertex);
285        }
286        for (source, target) in arcs {
287            bytes.extend_from_slice(&source.to_le_bytes());
288            bytes.extend_from_slice(&target.to_le_bytes());
289        }
290        debug_assert_eq!(bytes.len(), capacity);
291        Ok(Blob::new(bytes.into()))
292    }
293
294    /// Decode stored canonical bytes structurally for one fixed automaton.
295    ///
296    /// A collection member is trusted materialized work, so a read checks only
297    /// what safe interpretation needs: the header's lengths, the automaton's
298    /// state count, and every arc inside the product carrier. The vertex
299    /// order, the arc order and the domain are taken as stored. Nothing is
300    /// re-encoded or hashed; the automaton handle in the header is the
301    /// caller's to compare against the collection's, as a typed view does.
302    /// [`audit`](Self::audit) is the explicit canonical check.
303    pub fn decode(
304        blob: Blob<Self>,
305        automaton: &Automaton,
306    ) -> Result<PathSummary, PathSummaryBlobError> {
307        let bytes = blob.bytes.as_ref();
308        let header = structural_header(bytes, automaton.state_count())?;
309        let vertex_count = header.vertex_count;
310        let vertex_bytes = header.vertex_bytes;
311        let product_count = header.product_count;
312
313        let mut vertices = Vec::with_capacity(vertex_count);
314        for chunk in bytes[HEADER_LEN..HEADER_LEN + vertex_bytes].chunks_exact(32) {
315            vertices.push(chunk.try_into().expect("chunks_exact yields 32 bytes"));
316        }
317        let mut arcs = Vec::with_capacity(header.arc_count);
318        for chunk in bytes[HEADER_LEN + vertex_bytes..].chunks_exact(8) {
319            let source = u32::from_le_bytes(chunk[..4].try_into().expect("four bytes"));
320            let target = u32::from_le_bytes(chunk[4..].try_into().expect("four bytes"));
321            if source as usize >= product_count || target as usize >= product_count {
322                return Err(PathSummaryBlobError::ArcOutOfBounds);
323            }
324            arcs.push((source, target));
325        }
326        PathSummary::from_canonical_ordinals(automaton.clone(), vertices, arcs)
327            .map_err(|_| PathSummaryBlobError::CapacityOverflow)
328    }
329
330    /// Audit canonical bytes against the expected automaton.
331    ///
332    /// Everything [`decode`](Self::decode) checks, and then the canonical law
333    /// itself: the header names exactly this automaton, vertices and arcs are
334    /// strictly ordered, every arc follows one of the automaton's transitions,
335    /// and the vertex domain is the canonical one for it. This is the
336    /// producer's, ingress's and offline auditor's check; a warm read of a
337    /// stored member does not run it.
338    pub fn audit(
339        blob: Blob<Self>,
340        automaton: &Automaton,
341    ) -> Result<PathSummary, PathSummaryBlobError> {
342        let bytes = blob.bytes.as_ref();
343        let header = validate_header(bytes, automaton)?;
344        let vertex_count = header.vertex_count;
345        let vertex_bytes = header.vertex_bytes;
346        let state_count = automaton.state_count();
347        let product_count = header.product_count;
348
349        let mut vertices = Vec::with_capacity(vertex_count);
350        for chunk in bytes[HEADER_LEN..HEADER_LEN + vertex_bytes].chunks_exact(32) {
351            vertices.push(chunk.try_into().expect("chunks_exact yields 32 bytes"));
352        }
353        if vertices.windows(2).any(|pair| pair[0] >= pair[1]) {
354            return Err(PathSummaryBlobError::VertexOrder);
355        }
356
357        let allowed_state_pairs = automaton
358            .transitions()
359            .iter()
360            .map(|transition| (transition.from, transition.to))
361            .collect::<BTreeSet<_>>();
362        let mut arcs = Vec::with_capacity(header.arc_count);
363        let mut previous = None;
364        for chunk in bytes[HEADER_LEN + vertex_bytes..].chunks_exact(8) {
365            let source = u32::from_le_bytes(chunk[..4].try_into().expect("four bytes"));
366            let target = u32::from_le_bytes(chunk[4..].try_into().expect("four bytes"));
367            if source as usize >= product_count || target as usize >= product_count {
368                return Err(PathSummaryBlobError::ArcOutOfBounds);
369            }
370            if !allowed_state_pairs.contains(&(source % state_count, target % state_count)) {
371                return Err(PathSummaryBlobError::InvalidStatePair);
372            }
373            let arc = (source, target);
374            if previous.is_some_and(|previous| previous >= arc) {
375                return Err(PathSummaryBlobError::ArcOrder);
376            }
377            previous = Some(arc);
378            arcs.push(arc);
379        }
380        let summary = PathSummary::from_canonical_ordinals(automaton.clone(), vertices, arcs)
381            .map_err(|_| PathSummaryBlobError::CapacityOverflow)?;
382        if !summary.has_canonical_domain() {
383            return Err(PathSummaryBlobError::NoncanonicalDomain);
384        }
385        Ok(summary)
386    }
387
388    /// Compute the exact canonical join of two summaries for one automaton.
389    ///
390    /// This is new work by a producer, so both inputs are audited; a reader
391    /// joining resident members decodes them structurally and merges the
392    /// decoded summaries instead, without encoding a growing prefix.
393    pub fn join(
394        left: &Blob<Self>,
395        right: &Blob<Self>,
396        automaton: &Automaton,
397    ) -> Result<Blob<Self>, PathSummaryBlobError> {
398        let left = Self::audit(left.clone(), automaton)?;
399        let right = Self::audit(right.clone(), automaton)?;
400        let joined = left.merge(&right).map_err(PathSummaryBlobError::Join)?;
401        Self::encode(&joined)
402    }
403}
404
405#[derive(Clone, Copy, Debug)]
406struct ValidatedHeader {
407    vertex_count: usize,
408    vertex_bytes: usize,
409    arc_count: usize,
410    product_count: usize,
411}
412
413/// The audit's header check: the canonical automaton handle, then the shape.
414fn validate_header(
415    bytes: &[u8],
416    automaton: &Automaton,
417) -> Result<ValidatedHeader, PathSummaryBlobError> {
418    if bytes.len() < HEADER_LEN {
419        return Err(PathSummaryBlobError::BadLength);
420    }
421    let expected_automaton = PathAutomatonBlob::encode(automaton).get_handle();
422    if bytes[..32] != expected_automaton.raw {
423        return Err(PathSummaryBlobError::DifferentAutomaton);
424    }
425    structural_header(bytes, automaton.state_count())
426}
427
428/// The shape a read needs: lengths that agree with the counts, and a product
429/// carrier the arcs can index. No hashing, no re-encoding.
430fn structural_header(
431    bytes: &[u8],
432    expected_state_count: u32,
433) -> Result<ValidatedHeader, PathSummaryBlobError> {
434    if bytes.len() < HEADER_LEN {
435        return Err(PathSummaryBlobError::BadLength);
436    }
437    let state_count = read_u32(bytes, 32);
438    if state_count != expected_state_count {
439        return Err(PathSummaryBlobError::DifferentAutomaton);
440    }
441    let vertex_count = read_u32(bytes, 36) as usize;
442    let arc_count =
443        usize::try_from(read_u64(bytes, 40)).map_err(|_| PathSummaryBlobError::CapacityOverflow)?;
444    let vertex_bytes = vertex_count
445        .checked_mul(32)
446        .ok_or(PathSummaryBlobError::CapacityOverflow)?;
447    let arc_bytes = arc_count
448        .checked_mul(8)
449        .ok_or(PathSummaryBlobError::CapacityOverflow)?;
450    let expected_length = HEADER_LEN
451        .checked_add(vertex_bytes)
452        .and_then(|length| length.checked_add(arc_bytes))
453        .ok_or(PathSummaryBlobError::CapacityOverflow)?;
454    if bytes.len() != expected_length {
455        return Err(PathSummaryBlobError::BadLength);
456    }
457    let product_count = checked_product_count(vertex_count, state_count)?;
458    Ok(ValidatedHeader {
459        vertex_count,
460        vertex_bytes,
461        arc_count,
462        product_count,
463    })
464}
465
466fn checked_product_count(
467    vertex_count: usize,
468    state_count: u32,
469) -> Result<usize, PathSummaryBlobError> {
470    let product_count = vertex_count
471        .checked_mul(state_count as usize)
472        .ok_or(PathSummaryBlobError::CapacityOverflow)?;
473    if product_count > u32::MAX as usize {
474        return Err(PathSummaryBlobError::CapacityOverflow);
475    }
476    Ok(product_count)
477}
478
479fn read_u32(bytes: &[u8], offset: usize) -> u32 {
480    u32::from_le_bytes(
481        bytes[offset..offset + 4]
482            .try_into()
483            .expect("checked header"),
484    )
485}
486
487fn read_u64(bytes: &[u8], offset: usize) -> u64 {
488    u64::from_le_bytes(
489        bytes[offset..offset + 8]
490            .try_into()
491            .expect("checked header"),
492    )
493}
494
495fn push_u32(bytes: &mut Vec<u8>, value: u32) {
496    bytes.extend_from_slice(&value.to_le_bytes());
497}
498
499fn push_u64(bytes: &mut Vec<u8>, value: u64) {
500    bytes.extend_from_slice(&value.to_le_bytes());
501}
502
503fn transition_wire(transition: &crate::Transition) -> Vec<u8> {
504    let (opcode, labels): (u8, &[triblespace_core::id::RawId]) = match &transition.step {
505        Step::Forward(label) => (0, std::slice::from_ref(label)),
506        Step::Reverse(label) => (1, std::slice::from_ref(label)),
507        Step::ForwardExcept(labels) => (2, labels),
508        Step::ReverseExcept(labels) => (3, labels),
509    };
510    let mut bytes = Vec::with_capacity(17 + labels.len() * 16);
511    push_u32(&mut bytes, transition.from);
512    push_u32(&mut bytes, transition.to);
513    bytes.push(opcode);
514    push_u64(
515        &mut bytes,
516        u64::try_from(labels.len()).expect("label vector length fits in u64"),
517    );
518    for label in labels {
519        bytes.extend_from_slice(label);
520    }
521    bytes
522}
523
524fn automaton_wire(automaton: &Automaton) -> Vec<u8> {
525    let initial = automaton.initial_states().collect::<Vec<_>>();
526    let accepting = automaton.accepting_states().collect::<Vec<_>>();
527    let mut transitions = automaton
528        .transitions()
529        .iter()
530        .map(transition_wire)
531        .collect::<Vec<_>>();
532    transitions.sort_unstable();
533
534    let mut wire = Vec::new();
535    wire.extend_from_slice(&AUTOMATON_BLOB_DOMAIN);
536    push_u32(&mut wire, AUTOMATON_BLOB_VERSION);
537    push_u32(&mut wire, automaton.state_count());
538    push_u32(
539        &mut wire,
540        u32::try_from(initial.len()).expect("automaton state count is u32"),
541    );
542    push_u32(
543        &mut wire,
544        u32::try_from(accepting.len()).expect("automaton state count is u32"),
545    );
546    push_u64(
547        &mut wire,
548        u64::try_from(transitions.len()).expect("transition vector length fits in u64"),
549    );
550    for state in initial {
551        push_u32(&mut wire, state);
552    }
553    for state in accepting {
554        push_u32(&mut wire, state);
555    }
556    for transition in transitions {
557        wire.extend_from_slice(&transition);
558    }
559    wire
560}
561
562struct AutomatonWireReader<'a> {
563    bytes: &'a [u8],
564    offset: usize,
565}
566
567impl<'a> AutomatonWireReader<'a> {
568    fn new(bytes: &'a [u8]) -> Self {
569        Self { bytes, offset: 0 }
570    }
571
572    fn take(&mut self, length: usize) -> Result<&'a [u8], PathAutomatonBlobError> {
573        let end = self
574            .offset
575            .checked_add(length)
576            .ok_or(PathAutomatonBlobError::BadLength)?;
577        let bytes = self
578            .bytes
579            .get(self.offset..end)
580            .ok_or(PathAutomatonBlobError::BadLength)?;
581        self.offset = end;
582        Ok(bytes)
583    }
584
585    fn u8(&mut self) -> Result<u8, PathAutomatonBlobError> {
586        Ok(self.take(1)?[0])
587    }
588
589    fn u32(&mut self) -> Result<u32, PathAutomatonBlobError> {
590        Ok(u32::from_le_bytes(
591            self.take(4)?.try_into().expect("four checked bytes"),
592        ))
593    }
594
595    fn u64(&mut self) -> Result<u64, PathAutomatonBlobError> {
596        Ok(u64::from_le_bytes(
597            self.take(8)?.try_into().expect("eight checked bytes"),
598        ))
599    }
600
601    fn remaining(&self) -> usize {
602        self.bytes.len() - self.offset
603    }
604
605    fn is_empty(&self) -> bool {
606        self.offset == self.bytes.len()
607    }
608}
609
610impl PathAutomatonBlob {
611    /// Encode one canonical automaton into its portable content-addressed form.
612    pub fn encode(automaton: &Automaton) -> Blob<Self> {
613        Blob::new(automaton_wire(automaton).into())
614    }
615
616    /// Decode one automaton blob structurally.
617    ///
618    /// The bytes are a content-addressed representation dependency of every
619    /// summary that names them; a read takes them as stored and builds the
620    /// automaton they describe. [`audit`](Self::audit) additionally proves
621    /// they are the canonical wire for that automaton.
622    pub fn decode(blob: &Blob<Self>) -> Result<Automaton, PathAutomatonBlobError> {
623        let bytes = blob.bytes.as_ref();
624        if bytes.len() < AUTOMATON_BLOB_HEADER_LEN {
625            return Err(PathAutomatonBlobError::BadLength);
626        }
627
628        let mut wire = AutomatonWireReader::new(bytes);
629        if wire.take(AUTOMATON_BLOB_DOMAIN.len())? != AUTOMATON_BLOB_DOMAIN {
630            return Err(PathAutomatonBlobError::WrongDomain);
631        }
632        let version = wire.u32()?;
633        if version != AUTOMATON_BLOB_VERSION {
634            return Err(PathAutomatonBlobError::UnsupportedVersion(version));
635        }
636        let state_count = wire.u32()?;
637        let initial_count = wire.u32()? as usize;
638        let accepting_count = wire.u32()? as usize;
639        let transition_count =
640            usize::try_from(wire.u64()?).map_err(|_| PathAutomatonBlobError::BadLength)?;
641
642        let state_bytes = initial_count
643            .checked_add(accepting_count)
644            .and_then(|count| count.checked_mul(4))
645            .ok_or(PathAutomatonBlobError::BadLength)?;
646        if state_bytes > wire.remaining() {
647            return Err(PathAutomatonBlobError::BadLength);
648        }
649        let mut initial = Vec::with_capacity(initial_count);
650        for _ in 0..initial_count {
651            initial.push(wire.u32()?);
652        }
653        let mut accepting = Vec::with_capacity(accepting_count);
654        for _ in 0..accepting_count {
655            accepting.push(wire.u32()?);
656        }
657
658        // Every transition needs at least from, to, opcode, and label count.
659        // Bound the allocation before trusting the count from untrusted bytes.
660        if transition_count > wire.remaining() / 17 {
661            return Err(PathAutomatonBlobError::BadLength);
662        }
663        let mut transitions = Vec::with_capacity(transition_count);
664        for _ in 0..transition_count {
665            let from = wire.u32()?;
666            let to = wire.u32()?;
667            let opcode = wire.u8()?;
668            let label_count =
669                usize::try_from(wire.u64()?).map_err(|_| PathAutomatonBlobError::BadLength)?;
670            let label_bytes = label_count
671                .checked_mul(16)
672                .ok_or(PathAutomatonBlobError::BadLength)?;
673            if label_bytes > wire.remaining() {
674                return Err(PathAutomatonBlobError::BadLength);
675            }
676            let mut labels = Vec::with_capacity(label_count);
677            for _ in 0..label_count {
678                labels.push(wire.take(16)?.try_into().expect("sixteen checked bytes"));
679            }
680            let step = match (opcode, labels.as_slice()) {
681                (0, [label]) => Step::Forward(*label),
682                (1, [label]) => Step::Reverse(*label),
683                (0 | 1, _) => return Err(PathAutomatonBlobError::InvalidExactLabelCount),
684                (2, labels) => Step::ForwardExcept(labels.to_vec()),
685                (3, labels) => Step::ReverseExcept(labels.to_vec()),
686                (opcode, _) => return Err(PathAutomatonBlobError::InvalidOpcode(opcode)),
687            };
688            transitions.push(crate::Transition::new(from, to, step));
689        }
690        if !wire.is_empty() {
691            return Err(PathAutomatonBlobError::BadLength);
692        }
693
694        Automaton::new(state_count, initial, accepting, transitions)
695            .map_err(PathAutomatonBlobError::InvalidAutomaton)
696    }
697
698    /// Decode one automaton blob and prove its bytes are the canonical wire.
699    pub fn audit(blob: &Blob<Self>) -> Result<Automaton, PathAutomatonBlobError> {
700        let automaton = Self::decode(blob)?;
701        if automaton_wire(&automaton) != blob.bytes.as_ref() {
702            return Err(PathAutomatonBlobError::NonCanonical);
703        }
704        Ok(automaton)
705    }
706}
707
708/// Content handle of the canonical automaton wire, exposed under its historic
709/// fingerprint schema.
710///
711/// The raw bytes are also an `Inline<Handle<PathAutomatonBlob>>`; the Hash
712/// return type is retained because this function and the existing mapping fact
713/// predate the retained automaton blob.
714pub fn automaton_fingerprint(automaton: &Automaton) -> Inline<Hash<Blake3>> {
715    Inline::new(PathAutomatonBlob::encode(automaton).get_handle().raw)
716}
717
718#[cfg(test)]
719mod tests {
720    use super::*;
721
722    use triblespace_core::inline::RawInline;
723
724    use crate::{GraphEdge, Transition};
725
726    fn vertex(byte: u8) -> RawInline {
727        [byte; 32]
728    }
729
730    fn label(byte: u8) -> [u8; 16] {
731        [byte; 16]
732    }
733
734    fn edge(source: u8, attribute: u8, target: u8) -> GraphEdge {
735        GraphEdge {
736            source: vertex(source),
737            attribute: label(attribute),
738            target: vertex(target),
739        }
740    }
741
742    fn plus(attribute: u8) -> Automaton {
743        let attribute = label(attribute);
744        Automaton::new(
745            2,
746            [0],
747            [1],
748            [
749                Transition::new(0, 1, Step::Forward(attribute)),
750                Transition::new(1, 1, Step::Forward(attribute)),
751            ],
752        )
753        .unwrap()
754    }
755
756    #[test]
757    fn automaton_blob_retains_the_historic_fingerprint_wire() {
758        let automaton = Automaton::new(
759            3,
760            [0, 1],
761            [1, 2],
762            [
763                Transition::new(0, 1, Step::Forward(label(7))),
764                Transition::new(1, 2, Step::ReverseExcept(vec![label(9), label(8)])),
765            ],
766        )
767        .unwrap();
768        let blob = PathAutomatonBlob::encode(&automaton);
769
770        assert_eq!(blob.get_handle().raw, automaton_fingerprint(&automaton).raw);
771        assert_eq!(PathAutomatonBlob::decode(&blob).unwrap(), automaton);
772
773        let summary = PathSummary::from_edges(automaton, [edge(1, 7, 2)]);
774        let summary = PathSummaryBlob::encode(&summary).unwrap();
775        assert_eq!(
776            PathSummaryBlob::automaton_handle(&summary).unwrap(),
777            blob.get_handle()
778        );
779    }
780
781    #[test]
782    fn automaton_blob_rejects_noncanonical_and_trailing_bytes() {
783        let automaton = Automaton::new(3, [0, 1], [2], []).unwrap();
784        let canonical = PathAutomatonBlob::encode(&automaton);
785
786        let mut noncanonical = canonical.bytes.as_ref().to_vec();
787        noncanonical[40..44].copy_from_slice(&1u32.to_le_bytes());
788        noncanonical[44..48].copy_from_slice(&0u32.to_le_bytes());
789        let noncanonical = Blob::<PathAutomatonBlob>::new(noncanonical.into());
790        // A structural read takes the wire as stored; only the audit re-encodes.
791        assert_eq!(PathAutomatonBlob::decode(&noncanonical).unwrap(), automaton);
792        assert_eq!(
793            PathAutomatonBlob::audit(&noncanonical).unwrap_err(),
794            PathAutomatonBlobError::NonCanonical,
795        );
796
797        let mut trailing = canonical.bytes.as_ref().to_vec();
798        trailing.push(0);
799        assert_eq!(
800            PathAutomatonBlob::decode(&Blob::new(trailing.into())).unwrap_err(),
801            PathAutomatonBlobError::BadLength,
802        );
803    }
804
805    #[test]
806    fn canonical_bytes_are_input_order_invariant_and_golden() {
807        let automaton = Automaton::new(
808            1,
809            [0, 0],
810            [0],
811            [
812                Transition::new(0, 0, Step::Forward(label(9))),
813                Transition::new(0, 0, Step::Forward(label(9))),
814            ],
815        )
816        .unwrap();
817        let first = PathSummary::from_edges(automaton.clone(), [edge(1, 9, 2), edge(1, 9, 2)]);
818        let second = PathSummary::from_edges(automaton, [edge(1, 9, 2)]);
819        let first_blob = PathSummaryBlob::encode(&first).unwrap();
820        let second_blob = PathSummaryBlob::encode(&second).unwrap();
821
822        assert_eq!(first_blob.bytes, second_blob.bytes);
823        assert_eq!(first_blob.get_handle(), second_blob.get_handle());
824        assert_eq!(
825            hex(first_blob.bytes.as_ref()),
826            "5f73d0cf0230edf0512144e14a5e96132e661e1925556060b8036f217dc9b7f801000000020000000100000000000000010101010101010101010101010101010101010101010101010101010101010102020202020202020202020202020202020202020202020202020202020202020000000001000000"
827        );
828
829        let ordered = plus(7);
830        let reversed = Automaton::new(
831            2,
832            [0],
833            [1],
834            [
835                Transition::new(1, 1, Step::Forward(label(7))),
836                Transition::new(0, 1, Step::Forward(label(7))),
837            ],
838        )
839        .unwrap();
840        assert_eq!(
841            automaton_fingerprint(&ordered),
842            automaton_fingerprint(&reversed)
843        );
844    }
845
846    #[test]
847    fn malformed_length_fingerprint_order_bounds_and_state_pair_are_rejected() {
848        let automaton = plus(9);
849        let summary = PathSummary::from_edges(automaton.clone(), [edge(1, 9, 2)]);
850        let blob = PathSummaryBlob::encode(&summary).unwrap();
851
852        // The shape a read needs is checked by both the read and the audit.
853        let mut bad = blob.bytes.as_ref().to_vec();
854        bad.pop();
855        let bad = Blob::<PathSummaryBlob>::new(bad.into());
856        assert_eq!(
857            PathSummaryBlob::decode(bad.clone(), &automaton).unwrap_err(),
858            PathSummaryBlobError::BadLength
859        );
860        assert_eq!(
861            PathSummaryBlob::audit(bad, &automaton).unwrap_err(),
862            PathSummaryBlobError::BadLength
863        );
864
865        let arc_offset = HEADER_LEN + 2 * 32;
866        let mut bad = blob.bytes.as_ref().to_vec();
867        bad[arc_offset + 4..arc_offset + 8].copy_from_slice(&4u32.to_le_bytes());
868        let bad = Blob::<PathSummaryBlob>::new(bad.into());
869        assert_eq!(
870            PathSummaryBlob::decode(bad.clone(), &automaton).unwrap_err(),
871            PathSummaryBlobError::ArcOutOfBounds
872        );
873        assert_eq!(
874            PathSummaryBlob::audit(bad, &automaton).unwrap_err(),
875            PathSummaryBlobError::ArcOutOfBounds
876        );
877
878        // The canonical law is the audit's alone: a read takes the automaton
879        // handle, the orders and the transitions as stored.
880        let mut bad = blob.bytes.as_ref().to_vec();
881        bad[0] ^= 1;
882        let bad = Blob::<PathSummaryBlob>::new(bad.into());
883        assert!(PathSummaryBlob::decode(bad.clone(), &automaton).is_ok());
884        assert_eq!(
885            PathSummaryBlob::audit(bad, &automaton).unwrap_err(),
886            PathSummaryBlobError::DifferentAutomaton
887        );
888
889        let mut bad = blob.bytes.as_ref().to_vec();
890        bad[48..80].copy_from_slice(&vertex(2));
891        let bad = Blob::<PathSummaryBlob>::new(bad.into());
892        assert!(PathSummaryBlob::decode(bad.clone(), &automaton).is_ok());
893        assert_eq!(
894            PathSummaryBlob::audit(bad, &automaton).unwrap_err(),
895            PathSummaryBlobError::VertexOrder
896        );
897
898        let mut bad = blob.bytes.as_ref().to_vec();
899        bad[arc_offset + 4..arc_offset + 8].copy_from_slice(&2u32.to_le_bytes());
900        let bad = Blob::<PathSummaryBlob>::new(bad.into());
901        assert!(PathSummaryBlob::decode(bad.clone(), &automaton).is_ok());
902        assert_eq!(
903            PathSummaryBlob::audit(bad, &automaton).unwrap_err(),
904            PathSummaryBlobError::InvalidStatePair
905        );
906
907        let mut bad = blob.bytes.as_ref().to_vec();
908        let first_arc = bad[arc_offset..arc_offset + 8].to_vec();
909        bad[arc_offset + 8..arc_offset + 16].copy_from_slice(&first_arc);
910        let bad = Blob::<PathSummaryBlob>::new(bad.into());
911        assert!(PathSummaryBlob::decode(bad.clone(), &automaton).is_ok());
912        assert_eq!(
913            PathSummaryBlob::audit(bad, &automaton).unwrap_err(),
914            PathSummaryBlobError::ArcOrder
915        );
916    }
917
918    #[test]
919    fn a_read_and_an_audit_agree_on_canonical_bytes() {
920        let automaton = plus(9);
921        let summary = PathSummary::from_edges(automaton.clone(), [edge(1, 9, 2), edge(2, 9, 3)]);
922        let blob = PathSummaryBlob::encode(&summary).unwrap();
923        let read = PathSummaryBlob::decode(blob.clone(), &automaton).unwrap();
924        let audited = PathSummaryBlob::audit(blob, &automaton).unwrap();
925        assert_eq!(read, summary);
926        assert_eq!(audited, summary);
927    }
928
929    #[test]
930    fn product_carrier_dimensions_are_checked_before_ordinal_lowering() {
931        assert_eq!(checked_product_count(2, 3).unwrap(), 6);
932        assert_eq!(
933            checked_product_count(u32::MAX as usize, 2).unwrap_err(),
934            PathSummaryBlobError::CapacityOverflow
935        );
936        assert_eq!(
937            checked_product_count(usize::MAX, 2).unwrap_err(),
938            PathSummaryBlobError::CapacityOverflow
939        );
940    }
941
942    fn hex(bytes: &[u8]) -> String {
943        const TABLE: &[u8; 16] = b"0123456789abcdef";
944        let mut out = String::with_capacity(bytes.len() * 2);
945        for byte in bytes {
946            out.push(TABLE[(byte >> 4) as usize] as char);
947            out.push(TABLE[(byte & 0xf) as usize] as char);
948        }
949        out
950    }
951}