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#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
14pub struct GraphEdge {
15 pub source: RawInline,
17 pub attribute: RawId,
19 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#[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#[derive(Clone, Debug, Eq, PartialEq)]
67pub enum PathError {
68 EmptyInput,
70 DifferentAutomata,
72 TooManyVertices {
74 count: usize,
76 },
77 ProductCarrierTooLarge {
79 vertices: usize,
81 states: StateId,
83 },
84 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 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 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 pub fn automaton(&self) -> &Automaton {
197 &self.automaton
198 }
199
200 pub fn vertices(&self) -> &[RawInline] {
202 &self.vertices
203 }
204
205 pub fn direct_arc_count(&self) -> usize {
207 self.arcs.len()
208 }
209
210 pub fn merge(&self, other: &Self) -> Result<Self, PathError> {
212 Self::merge_all([self, other])
213 }
214
215 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}