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;
21const 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 "77DF5A905CCE3B0643BB02999F73BE4C" unsafe as pub path_automaton_fingerprint: Hash<Blake3>;
36 "562D157447DBE25FE8E6DCB95C5A5AB4" as pub path_automaton_state_count: U256BE;
39 "EE0D84553EB07FD3E75CD2709ED50E79" as pub path_automaton_initial_state: U256BE;
42 "4D10E8C83A816E1D888AD243B1DBD5C7" as pub path_automaton_accepting_state: U256BE;
45 "4828A5918A259F89038041053EA720CC" as pub path_automaton_transition: GenId;
49 "15FBA850D9AC99B7CF8D7842FC5F77B3" as pub path_transition_from: U256BE;
52 "A8F46B12D94B7400F052C45ED579873E" as pub path_transition_to: U256BE;
55 "08B0B01EFE6E68AB85DF4F0967D914B8" as pub path_transition_kind: U256BE;
58 "FD88EA3256CD24545BEB7759E7DBA6FA" as pub path_transition_label: U256BE;
62}
63
64pub struct PathAutomatonBlob;
72
73impl BlobEncoding for PathAutomatonBlob {}
74
75impl MetaDescribe for PathAutomatonBlob {
76 fn describe() -> Fragment {
77 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#[derive(Clone, Debug, Eq, PartialEq)]
90pub enum PathAutomatonBlobError {
91 BadLength,
93 WrongDomain,
95 UnsupportedVersion(u32),
97 InvalidOpcode(u8),
99 InvalidExactLabelCount,
101 InvalidAutomaton(crate::AutomatonError),
103 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
148pub struct PathSummaryBlob;
150
151impl BlobEncoding for PathSummaryBlob {}
152
153impl MetaDescribe for PathSummaryBlob {
154 fn describe() -> Fragment {
155 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#[derive(Clone, Debug, Eq, PartialEq)]
168pub enum PathSummaryBlobError {
169 BadLength,
171 DifferentAutomaton,
173 NoncanonicalDomain,
175 VertexOrder,
177 ArcOrder,
179 ArcOutOfBounds,
181 InvalidStatePair,
183 Join(PathError),
185 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 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 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 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 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 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 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
413fn 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
428fn 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 pub fn encode(automaton: &Automaton) -> Blob<Self> {
613 Blob::new(automaton_wire(automaton).into())
614 }
615
616 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 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 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
708pub 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 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 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 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}