Skip to main content

triblespace_paths/
summary.rs

1use std::collections::BTreeSet;
2use std::error::Error;
3use std::fmt;
4
5use triblespace_core::id::RawId;
6use triblespace_core::inline::encodings::UnknownInline;
7use triblespace_core::inline::RawInline;
8use triblespace_core::trible::Trible;
9
10use crate::{Automaton, StateId};
11
12/// One directed, attribute-labeled graph edge.
13#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
14pub struct GraphEdge {
15    /// Edge source.
16    pub source: RawInline,
17    /// Edge label.
18    pub attribute: RawId,
19    /// Edge target. It may be an ID or any other inline value.
20    pub target: RawInline,
21}
22
23impl From<&Trible> for GraphEdge {
24    fn from(trible: &Trible) -> Self {
25        Self {
26            source: RawInline::from(*trible.e()),
27            attribute: RawId::from(*trible.a()),
28            target: trible.v::<UnknownInline>().raw,
29        }
30    }
31}
32
33impl From<Trible> for GraphEdge {
34    fn from(trible: Trible) -> Self {
35        Self::from(&trible)
36    }
37}
38
39#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
40struct ProductNode {
41    vertex: RawInline,
42    state: StateId,
43}
44
45#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
46struct ProductArc {
47    source: ProductNode,
48    target: ProductNode,
49}
50
51/// Canonical, unionable constructional summary for one fixed automaton.
52///
53/// Nullable automata retain both endpoints of every supplied graph edge so
54/// their zero-hop identity has the correct graph domain. Non-nullable
55/// automata retain only endpoints of edges matching at least one transition:
56/// every positive-length path lies entirely in that support. The retained
57/// arcs are direct product arcs, never a transitive closure.
58#[derive(Clone, Debug, Eq, PartialEq)]
59pub struct PathSummary {
60    pub(crate) automaton: Automaton,
61    pub(crate) vertices: Vec<RawInline>,
62    arcs: Vec<ProductArc>,
63}
64
65/// Failure to compose or materialize path data.
66#[derive(Clone, Debug, Eq, PartialEq)]
67pub enum PathError {
68    /// An operation needing a defining automaton received no summaries.
69    EmptyInput,
70    /// Every composed summary must use the same canonical automaton.
71    DifferentAutomata,
72    /// Vertex ordinals no longer fit in the production `u32` representation.
73    TooManyVertices {
74        /// Number of distinct graph terms.
75        count: usize,
76    },
77    /// Product ordinals no longer fit in the production `u32` representation.
78    ProductCarrierTooLarge {
79        /// Number of distinct graph terms.
80        vertices: usize,
81        /// Number of automaton states.
82        states: StateId,
83    },
84    /// A checked allocation dimension overflowed `usize`.
85    CapacityOverflow,
86}
87
88impl fmt::Display for PathError {
89    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
90        match self {
91            Self::EmptyInput => write!(f, "cannot combine an empty path-summary list"),
92            Self::DifferentAutomata => write!(f, "path summaries use different automata"),
93            Self::TooManyVertices { count } => {
94                write!(f, "{count} path vertices do not fit in u32 ordinals")
95            }
96            Self::ProductCarrierTooLarge { vertices, states } => write!(
97                f,
98                "the {vertices} by {states} product carrier does not fit in u32 ordinals"
99            ),
100            Self::CapacityOverflow => write!(f, "path-index allocation dimensions overflow usize"),
101        }
102    }
103}
104
105impl Error for PathError {}
106
107impl PathSummary {
108    pub(crate) fn from_canonical_ordinals(
109        automaton: Automaton,
110        vertices: Vec<RawInline>,
111        arcs: Vec<(u32, u32)>,
112    ) -> Result<Self, PathError> {
113        let state_count = automaton.state_count();
114        let product_count = vertices
115            .len()
116            .checked_mul(state_count as usize)
117            .ok_or(PathError::CapacityOverflow)?;
118        let mut product_arcs = Vec::with_capacity(arcs.len());
119        for (source, target) in arcs {
120            if source as usize >= product_count || target as usize >= product_count {
121                return Err(PathError::ProductCarrierTooLarge {
122                    vertices: vertices.len(),
123                    states: state_count,
124                });
125            }
126            product_arcs.push(ProductArc {
127                source: ProductNode {
128                    vertex: vertices[source as usize / state_count as usize],
129                    state: source % state_count,
130                },
131                target: ProductNode {
132                    vertex: vertices[target as usize / state_count as usize],
133                    state: target % state_count,
134                },
135            });
136        }
137        Ok(Self {
138            automaton,
139            vertices,
140            arcs: product_arcs,
141        })
142    }
143
144    /// Lowers a SET of graph edges into canonical direct product arcs.
145    pub fn from_edges(automaton: Automaton, edges: impl IntoIterator<Item = GraphEdge>) -> Self {
146        let edges = edges.into_iter().collect::<BTreeSet<_>>();
147        let mut vertices = if automaton.accepts_empty() {
148            edges
149                .iter()
150                .flat_map(|edge| [edge.source, edge.target])
151                .collect::<BTreeSet<_>>()
152        } else {
153            BTreeSet::new()
154        };
155        let mut arcs = BTreeSet::new();
156        for edge in edges {
157            for transition in automaton.transitions() {
158                if !transition.step.matches(&edge.attribute) {
159                    continue;
160                }
161                let (source, target) = if transition.step.is_reverse() {
162                    (edge.target, edge.source)
163                } else {
164                    (edge.source, edge.target)
165                };
166                vertices.insert(source);
167                vertices.insert(target);
168                arcs.insert(ProductArc {
169                    source: ProductNode {
170                        vertex: source,
171                        state: transition.from,
172                    },
173                    target: ProductNode {
174                        vertex: target,
175                        state: transition.to,
176                    },
177                });
178            }
179        }
180        Self {
181            automaton,
182            vertices: vertices.into_iter().collect(),
183            arcs: arcs.into_iter().collect(),
184        }
185    }
186
187    /// Lowers tribles directly into a summary.
188    pub fn from_tribles<'a>(
189        automaton: Automaton,
190        tribles: impl IntoIterator<Item = &'a Trible>,
191    ) -> Self {
192        Self::from_edges(automaton, tribles.into_iter().map(GraphEdge::from))
193    }
194
195    /// Fixed automaton defining this summary.
196    pub fn automaton(&self) -> &Automaton {
197        &self.automaton
198    }
199
200    /// Sorted graph-term domain required by this fixed automaton.
201    pub fn vertices(&self) -> &[RawInline] {
202        &self.vertices
203    }
204
205    /// Number of canonical direct product arcs.
206    pub fn direct_arc_count(&self) -> usize {
207        self.arcs.len()
208    }
209
210    /// Canonical set union of two summaries.
211    pub fn merge(&self, other: &Self) -> Result<Self, PathError> {
212        Self::merge_all([self, other])
213    }
214
215    /// Canonical set union of any nonempty collection of summaries.
216    pub fn merge_all<'a>(summaries: impl IntoIterator<Item = &'a Self>) -> Result<Self, PathError> {
217        let summaries = summaries.into_iter().collect::<Vec<_>>();
218        let Some(first) = summaries.first() else {
219            return Err(PathError::EmptyInput);
220        };
221        if summaries
222            .iter()
223            .any(|summary| summary.automaton != first.automaton)
224        {
225            return Err(PathError::DifferentAutomata);
226        }
227        let vertices = summaries
228            .iter()
229            .flat_map(|summary| summary.vertices.iter().copied())
230            .collect::<BTreeSet<_>>()
231            .into_iter()
232            .collect();
233        let arcs = summaries
234            .iter()
235            .flat_map(|summary| summary.arcs.iter().copied())
236            .collect::<BTreeSet<_>>()
237            .into_iter()
238            .collect();
239        Ok(Self {
240            automaton: first.automaton.clone(),
241            vertices,
242            arcs,
243        })
244    }
245
246    pub(crate) fn ordinal_arcs(&self) -> impl Iterator<Item = (u32, u32)> + '_ {
247        self.ordinal_arcs_in(&self.vertices)
248    }
249
250    pub(crate) fn active_vertices(&self) -> Vec<RawInline> {
251        self.arcs
252            .iter()
253            .flat_map(|arc| [arc.source.vertex, arc.target.vertex])
254            .collect::<BTreeSet<_>>()
255            .into_iter()
256            .collect()
257    }
258
259    pub(crate) fn has_canonical_domain(&self) -> bool {
260        self.automaton.accepts_empty() || self.vertices == self.active_vertices()
261    }
262
263    pub(crate) fn ordinal_arcs_in<'a>(
264        &'a self,
265        vertices: &'a [RawInline],
266    ) -> impl Iterator<Item = (u32, u32)> + 'a {
267        let states = self.automaton.state_count();
268        self.arcs.iter().map(move |arc| {
269            let source_vertex = vertices
270                .binary_search(&arc.source.vertex)
271                .expect("summary arc source belongs to the requested product carrier")
272                as u32;
273            let target_vertex = vertices
274                .binary_search(&arc.target.vertex)
275                .expect("summary arc target belongs to the requested product carrier")
276                as u32;
277            (
278                source_vertex * states + arc.source.state,
279                target_vertex * states + arc.target.state,
280            )
281        })
282    }
283}