1use std::convert::Infallible;
34use std::error::Error;
35use std::fmt;
36use std::sync::Arc;
37use triblespace_core::prelude::entity;
38
39use triblespace_core::attribute::Attribute;
40use triblespace_core::blob::encodings::simplearchive::{SimpleArchive, UnarchiveError};
41use triblespace_core::blob::Blob;
42use triblespace_core::collection::descriptor;
43use triblespace_core::collection::records::{mapping_algorithm, KIND_COLLECTION_MAPPING};
44use triblespace_core::collection::simplearchive_union;
45use triblespace_core::collection::{
46 CollectionAttachment, CollectionData, CollectionEncoding, CollectionOperationError, Cover,
47 TryFromCover, TryFromCoverError,
48};
49use triblespace_core::id::{ExclusiveId, Id};
50use triblespace_core::id_hex;
51use triblespace_core::inline::encodings::genid::GenId;
52use triblespace_core::inline::encodings::hash::{Blake3, Handle, Hash};
53use triblespace_core::inline::encodings::iu256::U256BE;
54use triblespace_core::inline::{Inline, TryFromInline};
55use triblespace_core::metadata::{self, MetaDescribe};
56use triblespace_core::trible::{Fragment, Trible, TribleSet, TRIBLE_LEN};
57
58use crate::persistence::{
59 path_automaton_accepting_state, path_automaton_fingerprint, path_automaton_initial_state,
60 path_automaton_state_count, path_automaton_transition, path_transition_from,
61 path_transition_kind, path_transition_label, path_transition_to, PathAutomatonBlob,
62 PathAutomatonBlobError,
63};
64use crate::{
65 Automaton, GraphEdge, PathError, PathIndex, PathSummary, PathSummaryBlob, PathSummaryBlobError,
66 Step, Transition,
67};
68
69#[derive(Clone, Debug, Eq, PartialEq)]
71pub enum RegularPathMappingError {
72 Source(UnarchiveError),
74 Summary(PathSummaryBlobError),
76}
77
78impl fmt::Display for RegularPathMappingError {
79 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
80 match self {
81 Self::Source(source) => write!(formatter, "invalid SimpleArchive source: {source}"),
82 Self::Summary(source) => write!(formatter, "invalid path-summary element: {source}"),
83 }
84 }
85}
86
87impl Error for RegularPathMappingError {
88 fn source(&self) -> Option<&(dyn Error + 'static)> {
89 match self {
90 Self::Source(source) => Some(source),
91 Self::Summary(source) => Some(source),
92 }
93 }
94}
95
96pub const REGULAR_PATH_MAPPING_V1: Id = id_hex!("EB6B81A38B71AC1B7EA0806A9A48DAB5");
100
101pub struct RegularPathMappingV1;
103
104impl MetaDescribe for RegularPathMappingV1 {
105 fn describe() -> Fragment {
106 let id = REGULAR_PATH_MAPPING_V1;
107 entity! {
108 ExclusiveId::force_ref(&id) @
109 metadata::name: "regular-path-mapping-v1",
110 metadata::description: "Canonical join-preserving conversion from a SimpleArchive trible set to the direct-product summary of one concrete epsilon-free regular-path automaton. The content-derived mapping instance carries the complete automaton and its checked fingerprint.",
111 metadata::tag: metadata::KIND_COLLECTION_MAPPING_ALGORITHM,
112 }
113 }
114}
115
116fn mapping_fragment(automaton: &Automaton) -> Fragment {
117 let automaton_blob = PathAutomatonBlob::encode(automaton);
118 let fingerprint = Inline::new(automaton_blob.get_handle().raw);
119 let mut fragment = mapping_fragment_with_fingerprint(automaton, fingerprint);
120 let attached = fragment.put::<PathAutomatonBlob, _>(automaton_blob);
121 debug_assert_eq!(attached.raw, fingerprint.raw);
122 fragment
123}
124
125fn mapping_fragment_with_fingerprint(
126 automaton: &Automaton,
127 fingerprint: Inline<Hash<Blake3>>,
128) -> Fragment {
129 let transitions = automaton
130 .transitions()
131 .iter()
132 .map(transition_fragment)
133 .fold(Fragment::empty(), |mut transitions, transition| {
134 transitions += transition;
135 transitions
136 });
137 entity! { _ @
138 metadata::tag: KIND_COLLECTION_MAPPING,
139 mapping_algorithm*: <RegularPathMappingV1 as MetaDescribe>::describe(),
140 path_automaton_fingerprint: fingerprint,
141 path_automaton_state_count: automaton.state_count(),
142 path_automaton_initial_state*: automaton.initial_states(),
143 path_automaton_accepting_state*: automaton.accepting_states(),
144 path_automaton_transition*: transitions,
145 }
146}
147
148fn transition_fragment(transition: &Transition) -> Fragment {
149 let (kind, labels): (u32, &[triblespace_core::id::RawId]) = match &transition.step {
150 Step::Forward(label) => (0, std::slice::from_ref(label)),
151 Step::Reverse(label) => (1, std::slice::from_ref(label)),
152 Step::ForwardExcept(labels) => (2, labels),
153 Step::ReverseExcept(labels) => (3, labels),
154 };
155 let labels = labels
156 .iter()
157 .copied()
158 .map(u128::from_be_bytes)
159 .collect::<Vec<_>>();
160 entity! { _ @
161 path_transition_from: transition.from,
162 path_transition_to: transition.to,
163 path_transition_kind: kind,
164 path_transition_label*: labels,
165 }
166}
167
168fn descriptor_automaton_handle(
169 descriptor_fragment: &Fragment,
170) -> Result<Inline<Handle<PathAutomatonBlob>>, CollectionOperationError> {
171 let raw =
172 descriptor::mapping_argument(descriptor_fragment.facts(), path_automaton_fingerprint.id())
173 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?
174 .ok_or_else(|| {
175 CollectionOperationError::Fatal(
176 "regular-path mapping is missing path_automaton_fingerprint".to_owned(),
177 )
178 })?;
179 Ok(Inline::new(raw))
180}
181
182fn require_member_automaton(
183 descriptor: &Fragment,
184 member: &Blob<PathSummaryBlob>,
185) -> Result<Inline<Handle<PathAutomatonBlob>>, CollectionOperationError> {
186 let expected = descriptor_automaton_handle(descriptor)?;
187 let actual = PathSummaryBlob::automaton_handle(member)
188 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?;
189 if actual != expected {
190 return Err(CollectionOperationError::Fatal(
191 "path-summary member names an automaton outside its collection".to_owned(),
192 ));
193 }
194 Ok(actual)
195}
196
197fn resident_automaton<R>(
198 handle: Inline<Handle<PathAutomatonBlob>>,
199 reader: &R,
200) -> Result<Automaton, CollectionOperationError>
201where
202 R: triblespace_core::repo::BlobStoreGet + triblespace_core::repo::BlobStoreMeta,
203{
204 let resident = reader
205 .metadata(handle)
206 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?
207 .is_some();
208 if !resident {
209 return Err(CollectionOperationError::MissingDependency(Handle::<
210 PathAutomatonBlob,
211 >::to_hash(
212 handle
213 )));
214 }
215 let blob: Blob<PathAutomatonBlob> = reader
216 .get(handle)
217 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?;
218 PathAutomatonBlob::audit(&blob)
219 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))
220}
221
222impl CollectionEncoding for PathSummaryBlob {
226 fn validate_descriptor(descriptor: &Fragment) -> Result<(), CollectionOperationError> {
227 let parents = descriptor::parents(descriptor.facts())
228 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?;
229 if parents.is_empty() {
230 return Err(CollectionOperationError::Fatal(
231 "path-summary descriptor is missing its parent collection".to_owned(),
232 ));
233 }
234 automaton_from_descriptor(descriptor).map(|_| ())
235 }
236
237 fn validate_member<R>(
238 descriptor: &Fragment,
239 member: &Blob<Self>,
240 reader: &R,
241 ) -> Result<(), CollectionOperationError>
242 where
243 R: triblespace_core::repo::BlobStoreGet + triblespace_core::repo::BlobStoreMeta,
244 {
245 let handle = require_member_automaton(descriptor, member)?;
246 let automaton = resident_automaton(handle, reader)?;
247 PathSummaryBlob::audit(member.clone(), &automaton)
248 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?;
249 Ok(())
250 }
251
252 fn missing_representation_dependencies<R>(
253 member: CollectionData,
254 reader: &R,
255 ) -> Result<Vec<CollectionData>, CollectionOperationError>
256 where
257 R: triblespace_core::repo::BlobStoreGet + triblespace_core::repo::BlobStoreMeta,
258 {
259 let root = reader
260 .get::<Blob<Self>, Self>(Handle::<Self>::from_hash(member))
261 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?;
262 let automaton = PathSummaryBlob::automaton_handle(&root)
263 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?;
264 let resident = reader
265 .metadata(automaton)
266 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?
267 .is_some();
268 Ok(if resident {
269 Vec::new()
270 } else {
271 vec![Handle::<PathAutomatonBlob>::to_hash(automaton)]
272 })
273 }
274
275 fn join_members<R>(
276 descriptor: &Fragment,
277 low: &Blob<Self>,
278 high: &Blob<Self>,
279 reader: &R,
280 ) -> Result<Blob<Self>, CollectionOperationError>
281 where
282 R: triblespace_core::repo::BlobStoreGet + triblespace_core::repo::BlobStoreMeta,
283 {
284 let low_automaton = require_member_automaton(descriptor, low)?;
285 let high_automaton = require_member_automaton(descriptor, high)?;
286 if low_automaton != high_automaton {
287 return Err(CollectionOperationError::Fatal(
288 "cannot join path summaries for different automata".to_owned(),
289 ));
290 }
291 let automaton = resident_automaton(low_automaton, reader)?;
292 PathSummaryBlob::join(low, high, &automaton).map_err(summary_operation_error)
293 }
294}
295
296impl CollectionAttachment for PathSummaryBlob {
297 type Argument = Automaton;
298
299 fn fragment(automaton: &Self::Argument) -> Fragment {
300 mapping_fragment(automaton)
301 }
302
303 fn bind(
304 _parent: &Fragment,
305 target: &Fragment,
306 ) -> Result<Self::Argument, CollectionOperationError> {
307 require_regular_path_mapping(target)?;
308 automaton_from_descriptor(target)
309 }
310
311 fn map<R>(
312 automaton: &Self::Argument,
313 source: &Blob<SimpleArchive>,
314 _siblings: &[CollectionData],
315 reader: &R,
316 ) -> Result<Blob<Self>, CollectionOperationError>
317 where
318 R: triblespace_core::repo::StoreRead,
319 {
320 let automaton_handle = PathAutomatonBlob::encode(automaton).get_handle();
321 let resident = reader
322 .metadata(automaton_handle)
323 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?
324 .is_some();
325 if !resident {
326 return Err(CollectionOperationError::MissingDependency(Handle::<
327 PathAutomatonBlob,
328 >::to_hash(
329 automaton_handle,
330 )));
331 }
332 derive_element(source, automaton).map_err(|source| match source {
333 RegularPathMappingError::Summary(PathSummaryBlobError::CapacityOverflow) => {
334 CollectionOperationError::Capacity(source.to_string())
335 }
336 RegularPathMappingError::Source(_) | RegularPathMappingError::Summary(_) => {
337 CollectionOperationError::Fatal(source.to_string())
338 }
339 })
340 }
341}
342
343fn summary_operation_error(source: PathSummaryBlobError) -> CollectionOperationError {
344 match source {
345 PathSummaryBlobError::CapacityOverflow => {
346 CollectionOperationError::Capacity(source.to_string())
347 }
348 _ => CollectionOperationError::Fatal(source.to_string()),
349 }
350}
351
352pub struct PathSummaryView {
361 cover: Cover<PathSummaryBlob>,
362 segments: Vec<(Inline<Handle<PathSummaryBlob>>, Blob<PathSummaryBlob>)>,
363 automaton_handle: Inline<Handle<PathAutomatonBlob>>,
364 automaton: Automaton,
365}
366
367impl PathSummaryView {
368 pub fn cover(&self) -> &Cover<PathSummaryBlob> {
370 &self.cover
371 }
372
373 pub fn automaton(&self) -> &Automaton {
375 &self.automaton
376 }
377
378 pub fn automaton_handle(&self) -> Inline<Handle<PathAutomatonBlob>> {
380 self.automaton_handle
381 }
382
383 pub fn prepare(&self) -> Result<PathIndex, PathIndexViewError> {
391 let mut summaries = Vec::with_capacity(self.segments.len());
392 for (_, blob) in &self.segments {
393 summaries.push(
394 PathSummaryBlob::decode(blob.clone(), &self.automaton)
395 .map_err(PathIndexViewError::Summary)?,
396 );
397 }
398 let summary = if summaries.is_empty() {
399 PathSummary::from_edges(self.automaton.clone(), std::iter::empty::<GraphEdge>())
400 } else {
401 PathSummary::merge_all(&summaries).map_err(PathIndexViewError::Index)?
402 };
403 PathIndex::from_summary(summary).map_err(PathIndexViewError::Index)
404 }
405
406 pub fn len(&self) -> usize {
408 self.segments.len()
409 }
410
411 pub fn is_empty(&self) -> bool {
413 self.segments.is_empty()
414 }
415
416 pub fn segments(&self) -> &[(Inline<Handle<PathSummaryBlob>>, Blob<PathSummaryBlob>)] {
423 &self.segments
424 }
425
426 pub fn into_segments(self) -> Vec<(Inline<Handle<PathSummaryBlob>>, Blob<PathSummaryBlob>)> {
428 self.segments
429 }
430
431 pub fn into_blobs(self) -> impl ExactSizeIterator<Item = Blob<PathSummaryBlob>> {
433 self.segments.into_iter().map(|(_, blob)| blob)
434 }
435}
436
437impl TryFromCover<PathSummaryBlob> for PathSummaryView {
438 type Error = PathIndexViewError;
439
440 fn try_from_cover<R>(
441 cover: &Cover<PathSummaryBlob>,
442 descriptor: &Fragment,
443 snapshot: &R,
444 ) -> Result<Self, TryFromCoverError<R::GetError<Infallible>, Self::Error>>
445 where
446 R: triblespace_core::repo::BlobStoreGet,
447 {
448 let automaton_handle = descriptor_automaton_handle(descriptor)
452 .map_err(PathIndexViewError::Descriptor)
453 .map_err(TryFromCoverError::View)?;
454 let mut segments = Vec::with_capacity(cover.len());
455 for handle in cover.members() {
456 let member = Handle::<PathSummaryBlob>::to_hash(handle);
457 let blob = snapshot
458 .get(handle)
459 .map_err(|source| TryFromCoverError::MemberGet { member, source })?;
460 let named = PathSummaryBlob::automaton_handle(&blob)
461 .map_err(PathIndexViewError::Summary)
462 .map_err(TryFromCoverError::View)?;
463 if named != automaton_handle {
464 return Err(TryFromCoverError::View(PathIndexViewError::Descriptor(
465 CollectionOperationError::Fatal(
466 "path-summary member names an automaton outside its collection".to_owned(),
467 ),
468 )));
469 }
470 segments.push((handle, blob));
471 }
472 let automaton_member = Handle::<PathAutomatonBlob>::to_hash(automaton_handle);
475 let automaton_blob =
476 snapshot
477 .get(automaton_handle)
478 .map_err(|source| TryFromCoverError::MemberGet {
479 member: automaton_member,
480 source,
481 })?;
482 let automaton = PathAutomatonBlob::decode(&automaton_blob)
483 .map_err(PathIndexViewError::Automaton)
484 .map_err(TryFromCoverError::View)?;
485 Ok(Self {
486 cover: cover.clone(),
487 segments,
488 automaton_handle,
489 automaton,
490 })
491 }
492}
493
494#[derive(Debug)]
496pub enum PathIndexViewError {
497 Descriptor(CollectionOperationError),
499 Automaton(PathAutomatonBlobError),
501 Summary(PathSummaryBlobError),
503 Index(PathError),
505}
506
507impl fmt::Display for PathIndexViewError {
508 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
509 match self {
510 Self::Descriptor(source) => source.fmt(formatter),
511 Self::Automaton(source) => source.fmt(formatter),
512 Self::Summary(source) => source.fmt(formatter),
513 Self::Index(source) => source.fmt(formatter),
514 }
515 }
516}
517
518impl Error for PathIndexViewError {
519 fn source(&self) -> Option<&(dyn Error + 'static)> {
520 match self {
521 Self::Descriptor(source) => Some(source),
522 Self::Automaton(source) => Some(source),
523 Self::Summary(source) => Some(source),
524 Self::Index(source) => Some(source),
525 }
526 }
527}
528
529impl TryFromCover<PathSummaryBlob> for Arc<PathIndex> {
530 type Error = PathIndexViewError;
531
532 fn try_from_cover<R>(
536 cover: &Cover<PathSummaryBlob>,
537 descriptor: &Fragment,
538 snapshot: &R,
539 ) -> Result<Self, TryFromCoverError<R::GetError<Infallible>, Self::Error>>
540 where
541 R: triblespace_core::repo::BlobStoreGet,
542 {
543 let view = PathSummaryView::try_from_cover(cover, descriptor, snapshot)?;
544 view.prepare()
545 .map(Arc::new)
546 .map_err(TryFromCoverError::View)
547 }
548}
549
550fn automaton_from_descriptor(
551 descriptor_fragment: &Fragment,
552) -> Result<Automaton, CollectionOperationError> {
553 let facts = descriptor_fragment.facts();
554 let mapping = descriptor::mapping(facts)
555 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?
556 .ok_or_else(|| {
557 CollectionOperationError::Fatal(
558 "path-summary descriptor is missing its regular-path mapping".to_owned(),
559 )
560 })?;
561 let state_count = exactly_one_u32(
562 facts,
563 mapping,
564 &path_automaton_state_count,
565 "path_automaton_state_count",
566 )?;
567 let initial = u32_values(facts, mapping, &path_automaton_initial_state)?;
568 let accepting = u32_values(facts, mapping, &path_automaton_accepting_state)?;
569 let transition_ids = id_values(facts, mapping, &path_automaton_transition)?;
570 let mut transitions = Vec::with_capacity(transition_ids.len());
571 for transition in transition_ids {
572 let from = exactly_one_u32(
573 facts,
574 transition,
575 &path_transition_from,
576 "path_transition_from",
577 )?;
578 let to = exactly_one_u32(facts, transition, &path_transition_to, "path_transition_to")?;
579 let kind = exactly_one_u32(
580 facts,
581 transition,
582 &path_transition_kind,
583 "path_transition_kind",
584 )?;
585 let labels = u128_values(facts, transition, &path_transition_label)?
586 .into_iter()
587 .map(u128::to_be_bytes)
588 .collect::<Vec<_>>();
589 let step = match (kind, labels.as_slice()) {
590 (0, [label]) => Step::Forward(*label),
591 (1, [label]) => Step::Reverse(*label),
592 (2, labels) => Step::ForwardExcept(labels.to_vec()),
593 (3, labels) => Step::ReverseExcept(labels.to_vec()),
594 (0 | 1, _) => {
595 return Err(CollectionOperationError::Fatal(
596 "exact path transition requires exactly one label".to_owned(),
597 ));
598 }
599 _ => {
600 return Err(CollectionOperationError::Fatal(format!(
601 "unknown path transition kind {kind}"
602 )));
603 }
604 };
605 transitions.push(Transition::new(from, to, step));
606 }
607 let automaton = Automaton::new(state_count, initial, accepting, transitions)
608 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?;
609 let expected = PathAutomatonBlob::encode(&automaton).get_handle();
610 let actual = descriptor_automaton_handle(descriptor_fragment)?;
611 if actual != expected {
612 return Err(CollectionOperationError::Fatal(
613 "regular-path mapping automaton facts do not match its fingerprint".to_owned(),
614 ));
615 }
616 Ok(automaton)
617}
618
619fn require_regular_path_mapping(target: &Fragment) -> Result<(), CollectionOperationError> {
620 let algorithm = descriptor::mapping_algorithm(target.facts())
621 .map_err(|source| CollectionOperationError::Fatal(source.to_string()))?;
622 if algorithm == Some(REGULAR_PATH_MAPPING_V1) {
623 return Ok(());
624 }
625 Err(CollectionOperationError::Fatal(format!(
626 "path-summary mapping algorithm {:?} does not match regular-path mapping {REGULAR_PATH_MAPPING_V1:X}",
627 algorithm.map(|id| format!("{id:X}")),
628 )))
629}
630
631fn exactly_one_u32(
632 facts: &TribleSet,
633 entity: Id,
634 attribute: &Attribute<U256BE>,
635 field: &'static str,
636) -> Result<u32, CollectionOperationError> {
637 let mut values = u32_values(facts, entity, attribute)?.into_iter();
638 let value = values.next().ok_or_else(|| {
639 CollectionOperationError::Fatal(format!("regular-path mapping is missing {field}"))
640 })?;
641 if values.next().is_some() {
642 return Err(CollectionOperationError::Fatal(format!(
643 "regular-path mapping repeats {field}"
644 )));
645 }
646 Ok(value)
647}
648
649fn u32_values(
650 facts: &TribleSet,
651 entity: Id,
652 attribute: &Attribute<U256BE>,
653) -> Result<Vec<u32>, CollectionOperationError> {
654 facts
655 .iter()
656 .filter(|fact| fact.e() == &entity && fact.a() == &attribute.id())
657 .map(|fact| {
658 u32::try_from_inline(fact.v::<U256BE>()).map_err(|source| {
659 CollectionOperationError::Fatal(format!(
660 "regular-path mapping integer does not fit u32: {source:?}"
661 ))
662 })
663 })
664 .collect()
665}
666
667fn u128_values(
668 facts: &TribleSet,
669 entity: Id,
670 attribute: &Attribute<U256BE>,
671) -> Result<Vec<u128>, CollectionOperationError> {
672 facts
673 .iter()
674 .filter(|fact| fact.e() == &entity && fact.a() == &attribute.id())
675 .map(|fact| {
676 u128::try_from_inline(fact.v::<U256BE>()).map_err(|source| {
677 CollectionOperationError::Fatal(format!(
678 "regular-path mapping label does not fit u128: {source:?}"
679 ))
680 })
681 })
682 .collect()
683}
684
685fn id_values(
686 facts: &TribleSet,
687 entity: Id,
688 attribute: &Attribute<GenId>,
689) -> Result<Vec<Id>, CollectionOperationError> {
690 facts
691 .iter()
692 .filter(|fact| fact.e() == &entity && fact.a() == &attribute.id())
693 .map(|fact| {
694 Id::try_from_inline(fact.v::<GenId>()).map_err(|source| {
695 CollectionOperationError::Fatal(format!(
696 "regular-path mapping transition has an invalid id: {source:?}"
697 ))
698 })
699 })
700 .collect()
701}
702
703pub fn derive_element(
705 source: &Blob<SimpleArchive>,
706 automaton: &Automaton,
707) -> Result<Blob<PathSummaryBlob>, RegularPathMappingError> {
708 simplearchive_union::validate_element(source).map_err(RegularPathMappingError::Source)?;
709 let edges = source.bytes.as_ref().chunks_exact(TRIBLE_LEN).map(|chunk| {
710 let raw: &[u8; TRIBLE_LEN] = chunk
711 .try_into()
712 .expect("validated SimpleArchive chunks have fixed trible length");
713 let trible = Trible::as_transmute_force_raw(raw)
714 .expect("validated SimpleArchive contains valid tribles");
715 GraphEdge::from(trible)
716 });
717 let summary = PathSummary::from_edges(automaton.clone(), edges);
718 PathSummaryBlob::encode(&summary).map_err(RegularPathMappingError::Summary)
719}
720
721#[cfg(test)]
722mod tests {
723 use super::*;
724
725 use ed25519_dalek::SigningKey;
726 use ed25519_dalek::VerifyingKey;
727 use triblespace_core::blob::IntoBlob;
728 use triblespace_core::capability::policy::resource_policy;
729 use triblespace_core::collection::records::{
730 collection_mapping, collection_name, collection_parent, collection_representation,
731 CollectionHandle, KIND_COLLECTION_DESCRIPTOR,
732 };
733 use triblespace_core::collection::{AdmissionPolicy, CollectionPolicy};
734 use triblespace_core::id::ExclusiveId;
735 use triblespace_core::inline::RawInline;
736 use triblespace_core::metadata;
737 use triblespace_core::prelude::entity;
738 use triblespace_core::repo::{BlobStoreGet, SnapshotSource};
739 use triblespace_core::trible::Fragment;
740 use triblespace_core::trible::TribleSet;
741
742 use crate::{PathIndex, Step, Transition};
743
744 fn id(byte: u8) -> Id {
745 Id::new([byte; 16]).unwrap()
746 }
747
748 fn authority() -> VerifyingKey {
750 SigningKey::from_bytes(&[1; 32]).verifying_key()
751 }
752
753 fn policy() -> CollectionPolicy {
754 CollectionPolicy::new(
755 AdmissionPolicy::direct(authority()),
756 AdmissionPolicy::direct(authority()),
757 )
758 }
759
760 fn source_collection() -> Fragment {
762 source_descriptor("edges", policy())
763 }
764
765 fn collection_of(descriptor: &Fragment) -> CollectionHandle {
768 IntoBlob::<SimpleArchive>::to_blob(descriptor.facts().clone()).get_handle()
769 }
770
771 fn source_descriptor(name: &str, policy: CollectionPolicy) -> Fragment {
772 entity! { _ @
773 metadata::tag: KIND_COLLECTION_DESCRIPTOR,
774 collection_name: name.to_owned(),
775 resource_policy*: policy.fragment(),
776 collection_representation*: <SimpleArchive as MetaDescribe>::describe(),
777 }
778 }
779
780 fn summary_descriptor(parent: CollectionHandle, automaton: &Automaton) -> Fragment {
781 entity! { _ @
782 metadata::tag: KIND_COLLECTION_DESCRIPTOR,
783 collection_parent: parent,
784 collection_representation*: <PathSummaryBlob as MetaDescribe>::describe(),
785 collection_mapping*: mapping_fragment(automaton),
786 }
787 }
788
789 fn summary_descriptor_with_fingerprint(
790 parent: CollectionHandle,
791 automaton: &Automaton,
792 fingerprint: Inline<Hash<Blake3>>,
793 ) -> Fragment {
794 entity! { _ @
795 metadata::tag: KIND_COLLECTION_DESCRIPTOR,
796 collection_parent: parent,
797 collection_representation*: <PathSummaryBlob as MetaDescribe>::describe(),
798 collection_mapping*: mapping_fragment_with_fingerprint(automaton, fingerprint),
799 }
800 }
801
802 fn label(byte: u8) -> [u8; 16] {
803 [byte; 16]
804 }
805
806 fn plus(attribute: [u8; 16]) -> Automaton {
807 Automaton::new(
808 2,
809 [0],
810 [1],
811 [
812 Transition::new(0, 1, Step::Forward(attribute)),
813 Transition::new(1, 1, Step::Forward(attribute)),
814 ],
815 )
816 .unwrap()
817 }
818
819 fn edge_facts(source_byte: u8, target_byte: u8) -> TribleSet {
820 let source = id(source_byte);
821 let target = id(target_byte);
822 entity! { ExclusiveId::force_ref(&source) @ metadata::tag: target }.into_facts()
823 }
824
825 fn archive(facts: &TribleSet) -> Blob<SimpleArchive> {
826 facts.to_blob()
827 }
828
829 #[test]
830 fn descriptor_identity_includes_parent_representation_and_automaton() {
831 let first_automaton = plus(label(7));
832 let second_automaton = plus(label(8));
833 let source = source_collection();
834 let first = summary_descriptor(collection_of(&source), &first_automaton);
835 let repeated = summary_descriptor(collection_of(&source), &first_automaton);
836 let second = summary_descriptor(collection_of(&source), &second_automaton);
837
838 assert_eq!(first, repeated);
839 assert_eq!(
842 descriptor::parents(first.facts()),
843 Ok(vec![collection_of(&source)])
844 );
845 assert_eq!(descriptor::source(first.facts()), Ok(None));
846 assert!(
847 descriptor::name(first.facts()).unwrap().is_none(),
848 "an attachment needs no anchor"
849 );
850 assert!(descriptor::policy(first.facts()).is_err());
851 let other_source = summary_descriptor(
852 collection_of(&source_descriptor("other-edges", policy())),
853 &first_automaton,
854 );
855 assert_ne!(collection_of(&first), collection_of(&other_source));
857 assert_eq!(
858 descriptor::mapping(first.facts()),
859 descriptor::mapping(other_source.facts())
860 );
861 assert_eq!(
862 descriptor::representation(first.facts()).unwrap(),
863 <PathSummaryBlob as MetaDescribe>::id()
864 );
865 assert_ne!(
866 descriptor::representation(first.facts()),
867 descriptor::representation(source.facts())
868 );
869 assert_eq!(descriptor::mapping(source.facts()), Ok(None));
870 assert_eq!(
871 descriptor::mapping_algorithm(first.facts()),
872 Ok(Some(REGULAR_PATH_MAPPING_V1))
873 );
874 assert_ne!(
877 descriptor::mapping(first.facts()),
878 descriptor::mapping(second.facts())
879 );
880 assert_ne!(
881 descriptor::mapping_argument(first.facts(), path_automaton_fingerprint.id()),
882 descriptor::mapping_argument(second.facts(), path_automaton_fingerprint.id())
883 );
884 assert_eq!(
885 descriptor::argument(first.facts(), path_automaton_fingerprint.id()),
886 Ok(None),
887 "automaton parameters belong to the mapping, not the descriptor root",
888 );
889 assert_ne!(collection_of(&first), collection_of(&second));
890 }
891
892 #[test]
893 fn descriptor_round_trips_automaton_and_rejects_fingerprint_mismatch() {
894 let automaton = Automaton::new(
895 3,
896 [0, 1],
897 [1, 2],
898 [
899 Transition::new(0, 1, Step::Forward(label(7))),
900 Transition::new(1, 2, Step::ReverseExcept(vec![label(8), label(9)])),
901 ],
902 )
903 .unwrap();
904 let source = collection_of(&source_collection());
905 let descriptor = summary_descriptor(source, &automaton);
906
907 let expected_automaton = PathAutomatonBlob::encode(&automaton);
908 let expected_handle = expected_automaton.get_handle();
909 let historical_mapping =
910 mapping_fragment_with_fingerprint(&automaton, Inline::new(expected_handle.raw));
911 let attached_mapping = <PathSummaryBlob as CollectionAttachment>::fragment(&automaton);
912 assert_eq!(attached_mapping.facts(), historical_mapping.facts());
913 assert_eq!(attached_mapping.root(), historical_mapping.root());
914
915 let mut attachments = descriptor.blobs().clone();
916 let attachment_snapshot = attachments.snapshot().unwrap();
917 let attached: Blob<PathAutomatonBlob> = attachment_snapshot.get(expected_handle).unwrap();
918 assert_eq!(attached.bytes, expected_automaton.bytes);
919
920 assert_eq!(
921 descriptor::mapping(descriptor.facts()),
922 Ok(mapping_fragment(&automaton).root()),
923 "the canonical constructor links its concrete mapping subtree",
924 );
925 assert_eq!(automaton_from_descriptor(&descriptor).unwrap(), automaton);
926 <PathSummaryBlob as CollectionEncoding>::validate_descriptor(&descriptor).unwrap();
927
928 let mut annotated = descriptor.clone();
929 let mapping = descriptor::mapping(annotated.facts())
930 .unwrap()
931 .expect("attached descriptor has a mapping");
932 let predecessor: Inline<GenId> =
933 triblespace_core::inline::IntoInline::to_inline(REGULAR_PATH_MAPPING_V1);
934 annotated.facts_mut().insert(&Trible::force(
935 &mapping,
936 &metadata::supersedes.id(),
937 &predecessor,
938 ));
939 assert_eq!(
940 automaton_from_descriptor(&annotated).unwrap(),
941 automaton,
942 "annotations do not change a mapping's operational meaning",
943 );
944
945 let mismatched =
946 summary_descriptor_with_fingerprint(source, &automaton, Inline::new([0xA5; 32]));
947 assert!(matches!(
948 <PathSummaryBlob as CollectionEncoding>::validate_descriptor(&mismatched),
949 Err(CollectionOperationError::Fatal(reason))
950 if reason.contains("do not match its fingerprint")
951 ));
952 }
953
954 #[test]
955 fn canonical_empty_is_total_derived_bottom_and_join_identity() {
956 let automaton = plus(label(7));
957 let source_empty = archive(&TribleSet::new());
958 let canonical_empty = PathSummaryBlob::empty(&automaton);
959
960 assert_eq!(canonical_empty.bytes.len(), 48);
961 let mut expected_empty = Vec::with_capacity(48);
962 expected_empty.extend_from_slice(&crate::automaton_fingerprint(&automaton).raw);
963 expected_empty.extend_from_slice(&automaton.state_count().to_le_bytes());
964 expected_empty.extend_from_slice(&0u32.to_le_bytes());
965 expected_empty.extend_from_slice(&0u64.to_le_bytes());
966 assert_eq!(canonical_empty.bytes.as_ref(), expected_empty);
967 assert_eq!(
968 canonical_empty.get_handle(),
969 PathSummaryBlob::empty(&automaton).get_handle()
970 );
971 let decoded = PathSummaryBlob::decode(canonical_empty.clone(), &automaton).unwrap();
972 assert!(decoded.vertices().is_empty());
973 assert_eq!(decoded.direct_arc_count(), 0);
974
975 let derived_empty = derive_element(&source_empty, &automaton).unwrap();
976 assert_eq!(derived_empty.bytes, canonical_empty.bytes);
977
978 let unmatched_source = archive(&edge_facts(2, 3));
980 let derived_unmatched = derive_element(&unmatched_source, &automaton).unwrap();
981 assert_eq!(derived_unmatched.bytes, canonical_empty.bytes);
982
983 let matching_automaton = plus(metadata::tag.id().into());
984 let matching = derive_element(&archive(&edge_facts(4, 5)), &matching_automaton).unwrap();
985 let matching_empty = PathSummaryBlob::empty(&matching_automaton);
986 let left_identity =
987 PathSummaryBlob::join(&matching_empty, &matching, &matching_automaton).unwrap();
988 let right_identity =
989 PathSummaryBlob::join(&matching, &matching_empty, &matching_automaton).unwrap();
990 let idempotent = PathSummaryBlob::join(&matching, &matching, &matching_automaton).unwrap();
991 for joined in [left_identity, right_identity, idempotent] {
992 assert_eq!(joined.bytes, matching.bytes);
993 assert_eq!(joined.get_handle(), matching.get_handle());
994 }
995 }
996
997 #[test]
998 fn derive_and_merge_commute_and_close_cross_fragment_paths() {
999 let automaton = plus(metadata::tag.id().into());
1000 let left = archive(&edge_facts(1, 2));
1001 let right = archive(&edge_facts(2, 3));
1002
1003 let source_union = simplearchive_union::join(&left, &right).unwrap();
1004 let derive_after_source_join = derive_element(&source_union, &automaton).unwrap();
1005 let derived_left = derive_element(&left, &automaton).unwrap();
1006 let derived_right = derive_element(&right, &automaton).unwrap();
1007 let join_after_derive =
1008 PathSummaryBlob::join(&derived_left, &derived_right, &automaton).unwrap();
1009
1010 assert_eq!(derive_after_source_join.bytes, join_after_derive.bytes);
1011 assert_eq!(
1012 derive_after_source_join.get_handle(),
1013 join_after_derive.get_handle()
1014 );
1015
1016 let summary = PathSummaryBlob::decode(join_after_derive, &automaton).unwrap();
1017 let index = PathIndex::from_summary(summary).unwrap();
1018 assert!(index.contains(&RawInline::from(id(1)), &RawInline::from(id(3)),));
1019 }
1020
1021 #[test]
1022 fn nullable_unmatched_domain_obeys_the_same_mapping_law() {
1023 let automaton = Automaton::new(1, [0], [0], []).unwrap();
1024 let left = archive(&edge_facts(1, 2));
1025 let right = archive(&edge_facts(2, 3));
1026 let source_union = simplearchive_union::join(&left, &right).unwrap();
1027
1028 let derive_after_source_join = derive_element(&source_union, &automaton).unwrap();
1029 let derived_left = derive_element(&left, &automaton).unwrap();
1030 let derived_right = derive_element(&right, &automaton).unwrap();
1031 let join_after_derive =
1032 PathSummaryBlob::join(&derived_left, &derived_right, &automaton).unwrap();
1033
1034 assert_eq!(derive_after_source_join.bytes, join_after_derive.bytes);
1035 let summary = PathSummaryBlob::decode(join_after_derive, &automaton).unwrap();
1036 assert_eq!(summary.vertices().len(), 3);
1037 assert_eq!(summary.direct_arc_count(), 0);
1038 let index = PathIndex::from_summary(summary).unwrap();
1039 assert_eq!(index.accepted_pair_count(), 3);
1040
1041 let joined_with_empty = PathSummaryBlob::join(
1042 &PathSummaryBlob::empty(&automaton),
1043 &derived_left,
1044 &automaton,
1045 )
1046 .unwrap();
1047 assert_eq!(joined_with_empty.bytes, derived_left.bytes);
1048 }
1049}