Skip to main content

triblespace_paths/
path_summary_union.rs

1//! Canonical path-summary union, attached to a `SimpleArchive` root.
2//!
3//! One collection is fixed by its parent collection and one canonical path
4//! automaton. It is an attached collection: every host that holds a node
5//! computes that node's summary, so each host keeps its own, as `MAP`s of its
6//! own nodes, and none replicate. Its elements retain only the graph domain and direct
7//! product arcs required by that automaton; their join is exact set union.
8//! Lowering graph facts into those direct arcs is therefore a join
9//! homomorphism:
10//!
11//! ```text
12//! paths(a ∪ b) = paths(a) ⊔ paths(b)
13//! ```
14//!
15//! Transitive closure is deliberately absent from the collection law. It is
16//! performed once when a [`PathIndex`](crate::PathIndex) is materialized, so
17//! paths whose edges live in different source fragments remain discoverable.
18//! That is also what makes a reader's cover of attachments answer alike at
19//! any granularity: the members' arcs are unioned before closure, whether
20//! one node's summary holds a path or two nodes' summaries each hold half.
21//!
22//! Reading is split in three steps with different trust. Attaching a
23//! [`PathSummaryView`] is typed and structural: it keeps the resident members
24//! and the automaton they name and checks nothing but the 32-byte handle each
25//! member carries against the collection's. [`PathSummaryView::prepare`] is
26//! the query computation: it decodes the members structurally, merges the
27//! decoded summaries once and closes the union, so cross-member paths stay
28//! discoverable without encoding any intermediate join. The canonical audit
29//! is explicit: [`CollectionEncoding::validate_member`] and the producer's
30//! [`join_members`](CollectionEncoding::join_members) re-prove the bytes;
31//! a warm read never re-encodes or hashes to believe a stored equation.
32
33use 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/// Failure to lower one canonical source member through the regular-path mapping.
70#[derive(Clone, Debug, Eq, PartialEq)]
71pub enum RegularPathMappingError {
72    /// The source is not a canonical `SimpleArchive`.
73    Source(UnarchiveError),
74    /// Path-summary encoding failed.
75    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
96/// Stable identity of the canonical regular-path mapping algorithm.
97///
98/// Minted with `trible genid` on 2026-08-29.
99pub const REGULAR_PATH_MAPPING_V1: Id = id_hex!("EB6B81A38B71AC1B7EA0806A9A48DAB5");
100
101/// Self-description of the canonical `SimpleArchive -> PathSummaryBlob` mapping.
102pub 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
222/// Bind the canonical path-summary collection to the automaton named by its
223/// mapping while loading representation semantics from each member's exact
224/// immutable automaton child.
225impl 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
352/// A lazy logical path-summary value retaining its exact physical members.
353///
354/// Attaching one is typed and structural: the resident members are kept as
355/// stored, each checked only for naming the collection's automaton by the
356/// 32-byte handle it carries, and that automaton is decoded once from its
357/// content-addressed blob. Closure is intentionally not part of the
358/// collection law; [`prepare`](Self::prepare) computes it when a query needs
359/// the [`PathIndex`].
360pub 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    /// Exact typed physical cover represented by this view.
369    pub fn cover(&self) -> &Cover<PathSummaryBlob> {
370        &self.cover
371    }
372
373    /// The canonical automaton every member of this view is a summary for.
374    pub fn automaton(&self) -> &Automaton {
375        &self.automaton
376    }
377
378    /// Content handle of the automaton blob the members and descriptor name.
379    pub fn automaton_handle(&self) -> Inline<Handle<PathAutomatonBlob>> {
380        self.automaton_handle
381    }
382
383    /// Compute the exact endpoint relation over every member: the query
384    /// computation, kept out of attachment.
385    ///
386    /// Each member is decoded structurally, the decoded summaries are merged
387    /// once as sets, and the union is closed. Paths that take their edges from
388    /// several members are found because closure follows the join; nothing is
389    /// re-encoded on the way. An empty view closes the automaton's bottom.
390    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    /// Number of physical path-summary members retained by this view.
407    pub fn len(&self) -> usize {
408        self.segments.len()
409    }
410
411    /// Whether this view is the empty-cover bottom.
412    pub fn is_empty(&self) -> bool {
413        self.segments.is_empty()
414    }
415
416    /// Borrow the ordered resident physical summary members.
417    ///
418    /// Stored collection equations are trusted materialized work, so this
419    /// lazy view does not replay summary decoding merely to expose its shards.
420    /// Consumers which interpret path semantics validate while constructing
421    /// that interpretation, as the collection's path-index construction does.
422    pub fn segments(&self) -> &[(Inline<Handle<PathSummaryBlob>>, Blob<PathSummaryBlob>)] {
423        &self.segments
424    }
425
426    /// Consume the view into its ordered resident physical members.
427    pub fn into_segments(self) -> Vec<(Inline<Handle<PathSummaryBlob>>, Blob<PathSummaryBlob>)> {
428        self.segments
429    }
430
431    /// Consume just the physical summary blobs without forcing their union.
432    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        // The descriptor is the collection's admission expectation and names
449        // the automaton every member must be a summary for; a member's own
450        // header carries the same handle, compared as bytes, never rehashed.
451        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        // The automaton blob is a content-addressed representation dependency
473        // retained in the descriptor closure, so the empty cover has it too.
474        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/// Failure to close one realized path-summary cover into its endpoint index.
495#[derive(Debug)]
496pub enum PathIndexViewError {
497    /// The target descriptor did not name one regular-path automaton.
498    Descriptor(CollectionOperationError),
499    /// The named automaton blob was not canonically encoded.
500    Automaton(PathAutomatonBlobError),
501    /// A selected summary did not decode under its named automaton.
502    Summary(PathSummaryBlobError),
503    /// Closing the joined summary into the accepted endpoint relation failed.
504    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    /// The structural attach of a [`PathSummaryView`] followed by its
533    /// [`prepare`](PathSummaryView::prepare), for callers that want the
534    /// closed relation in one step.
535    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
703/// Canonically derive one path-summary element from a `SimpleArchive`.
704pub 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    /// Authority shared by these test collections.
749    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    /// The source collection these tests summarise.
761    fn source_collection() -> Fragment {
762        source_descriptor("edges", policy())
763    }
764
765    /// These tests only need identities to bind claims to; nothing stores the
766    /// descriptors they come from.
767    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        // A summary names the collection whose nodes it indexes, and carries
840        // no anchor and no policy of its own.
841        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        // The parent changes the collection but not the reusable mapping.
856        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        // The constructor gives different automata different content-derived
875        // mapping instances of the same algorithm.
876        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        // `metadata::tag` does not match the fixed label(7) transition.
979        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}