1use std::cmp::Reverse;
2use std::collections::BinaryHeap;
3
4use triblespace_core::inline::RawInline;
5use triblespace_core::trible::Trible;
6
7use crate::{Automaton, GraphEdge, PathError, PathSummary};
8
9#[derive(Clone, Debug)]
10struct Csr {
11 offsets: Vec<usize>,
12 values: Vec<u32>,
13}
14
15impl Csr {
16 fn row(&self, ordinal: usize) -> &[u32] {
17 &self.values[self.offsets[ordinal]..self.offsets[ordinal + 1]]
18 }
19
20 fn transpose(&self, rows: usize, offset_count: usize) -> Self {
21 let mut counts = vec![0usize; rows];
22 for &target in &self.values {
23 counts[target as usize] += 1;
24 }
25 let mut offsets = Vec::with_capacity(offset_count);
26 offsets.push(0);
27 for count in counts {
28 offsets.push(offsets.last().copied().unwrap() + count);
29 }
30 let mut next = offsets[..rows].to_vec();
31 let mut values = vec![0u32; self.values.len()];
32 for source in 0..rows {
33 for &target in self.row(source) {
34 let slot = &mut next[target as usize];
35 values[*slot] = source as u32;
36 *slot += 1;
37 }
38 }
39 Self { offsets, values }
40 }
41}
42
43#[derive(Clone, Debug)]
49pub struct PathIndex {
50 summary: PathSummary,
51 forward: Csr,
52 reverse: Csr,
53 starts: Vec<u32>,
54 ends: Vec<u32>,
55 diagonal: Vec<u32>,
56}
57
58impl PathIndex {
59 pub fn from_edges(
61 automaton: Automaton,
62 edges: impl IntoIterator<Item = GraphEdge>,
63 ) -> Result<Self, PathError> {
64 Self::from_summary(PathSummary::from_edges(automaton, edges))
65 }
66
67 pub fn from_tribles<'a>(
69 automaton: Automaton,
70 tribles: impl IntoIterator<Item = &'a Trible>,
71 ) -> Result<Self, PathError> {
72 Self::from_summary(PathSummary::from_tribles(automaton, tribles))
73 }
74
75 pub fn from_summary(summary: PathSummary) -> Result<Self, PathError> {
77 let vertex_count = summary.vertices.len();
78 if vertex_count > u32::MAX as usize {
79 return Err(PathError::TooManyVertices {
80 count: vertex_count,
81 });
82 }
83 let offset_count = vertex_count
84 .checked_add(1)
85 .ok_or(PathError::CapacityOverflow)?;
86 let nullable = summary.automaton.accepts_empty();
87 let active_storage;
88 let active_vertices = if nullable {
89 active_storage = summary.active_vertices();
90 active_storage.as_slice()
91 } else {
92 debug_assert!(summary.has_canonical_domain());
93 summary.vertices.as_slice()
94 };
95 let active = materialize_active_relation(&summary, active_vertices)?;
96 let forward = expand_relation(&summary.vertices, active_vertices, active, nullable)?;
97
98 let starts = (0..vertex_count)
99 .filter(|&source| !forward.row(source).is_empty())
100 .map(|source| source as u32)
101 .collect();
102 let diagonal = (0..vertex_count)
103 .filter(|&source| forward.row(source).binary_search(&(source as u32)).is_ok())
104 .map(|source| source as u32)
105 .collect();
106 let reverse = forward.transpose(vertex_count, offset_count);
107 let ends = (0..vertex_count)
108 .filter(|&target| !reverse.row(target).is_empty())
109 .map(|target| target as u32)
110 .collect();
111
112 Ok(Self {
113 summary,
114 forward,
115 reverse,
116 starts,
117 ends,
118 diagonal,
119 })
120 }
121
122 pub fn summary(&self) -> &PathSummary {
124 &self.summary
125 }
126
127 pub fn automaton(&self) -> &Automaton {
129 self.summary.automaton()
130 }
131
132 pub fn vertex_count(&self) -> usize {
134 self.summary.vertices.len()
135 }
136
137 pub fn accepted_pair_count(&self) -> usize {
139 self.forward.values.len()
140 }
141
142 pub fn contains(&self, source: &RawInline, target: &RawInline) -> bool {
144 let (Ok(source), Ok(target)) = (
145 self.summary.vertices.binary_search(source),
146 self.summary.vertices.binary_search(target),
147 ) else {
148 return false;
149 };
150 self.forward
151 .row(source)
152 .binary_search(&(target as u32))
153 .is_ok()
154 }
155
156 pub fn accepted_pairs(&self) -> impl Iterator<Item = (RawInline, RawInline)> + '_ {
158 (0..self.vertex_count()).flat_map(move |source| {
159 let source_value = self.summary.vertices[source];
160 self.forward
161 .row(source)
162 .iter()
163 .map(move |&target| (source_value, self.summary.vertices[target as usize]))
164 })
165 }
166
167 pub fn reachable_from<'a>(
169 &'a self,
170 source: &RawInline,
171 ) -> impl Iterator<Item = RawInline> + 'a {
172 self.values(self.forward_ordinals(source))
173 }
174
175 pub fn reaching<'a>(&'a self, target: &RawInline) -> impl Iterator<Item = RawInline> + 'a {
177 self.values(self.reverse_ordinals(target))
178 }
179
180 pub fn starts(&self) -> impl Iterator<Item = RawInline> + '_ {
182 self.values(&self.starts)
183 }
184
185 pub fn ends(&self) -> impl Iterator<Item = RawInline> + '_ {
187 self.values(&self.ends)
188 }
189
190 pub fn diagonal(&self) -> impl Iterator<Item = RawInline> + '_ {
192 self.values(&self.diagonal)
193 }
194
195 pub fn merge(&self, other: &Self) -> Result<Self, PathError> {
197 Self::from_summary(self.summary.merge(&other.summary)?)
198 }
199
200 pub fn merge_all<'a>(indexes: impl IntoIterator<Item = &'a Self>) -> Result<Self, PathError> {
202 let summaries = indexes
203 .into_iter()
204 .map(|index| &index.summary)
205 .collect::<Vec<_>>();
206 Self::from_summary(PathSummary::merge_all(summaries)?)
207 }
208
209 pub(crate) fn values<'a>(
210 &'a self,
211 ordinals: &'a [u32],
212 ) -> impl Iterator<Item = RawInline> + 'a {
213 ordinals
214 .iter()
215 .map(|&ordinal| self.summary.vertices[ordinal as usize])
216 }
217
218 pub(crate) fn forward_ordinals(&self, source: &RawInline) -> &[u32] {
219 self.summary
220 .vertices
221 .binary_search(source)
222 .ok()
223 .map(|source| self.forward.row(source))
224 .unwrap_or(&[])
225 }
226
227 pub(crate) fn reverse_ordinals(&self, target: &RawInline) -> &[u32] {
228 self.summary
229 .vertices
230 .binary_search(target)
231 .ok()
232 .map(|target| self.reverse.row(target))
233 .unwrap_or(&[])
234 }
235
236 pub(crate) fn starts_ordinals(&self) -> &[u32] {
237 &self.starts
238 }
239
240 pub(crate) fn ends_ordinals(&self) -> &[u32] {
241 &self.ends
242 }
243
244 pub(crate) fn diagonal_ordinals(&self) -> &[u32] {
245 &self.diagonal
246 }
247
248 pub(crate) fn ordinal_in(&self, ordinals: &[u32], value: &RawInline) -> bool {
249 self.summary
250 .vertices
251 .binary_search(value)
252 .is_ok_and(|ordinal| ordinals.binary_search(&(ordinal as u32)).is_ok())
253 }
254}
255
256fn materialize_active_relation(
260 summary: &PathSummary,
261 vertices: &[RawInline],
262) -> Result<Csr, PathError> {
263 let vertex_count = vertices.len();
264 let offset_count = vertex_count
265 .checked_add(1)
266 .ok_or(PathError::CapacityOverflow)?;
267 let state_count = summary.automaton.state_count() as usize;
268 let product_count = vertex_count
269 .checked_mul(state_count)
270 .ok_or(PathError::CapacityOverflow)?;
271 if product_count > u32::MAX as usize {
272 return Err(PathError::ProductCarrierTooLarge {
273 vertices: vertex_count,
274 states: summary.automaton.state_count(),
275 });
276 }
277
278 let mut adjacency = vec![Vec::<u32>::new(); product_count];
279 for (source, target) in summary.ordinal_arcs_in(vertices) {
280 adjacency[source as usize].push(target);
281 }
282 for targets in &mut adjacency {
283 targets.sort_unstable();
284 targets.dedup();
285 }
286
287 let (component_of, component_count) = strongly_connected_components(&adjacency);
288 let condensation = condensation(&adjacency, &component_of, component_count);
289 let topological = topological_order(&condensation);
290
291 let row_words = vertex_count.div_ceil(u64::BITS as usize);
292 let reach_words = component_count
293 .checked_mul(row_words)
294 .ok_or(PathError::CapacityOverflow)?;
295 let mut accepting_reach = vec![0u64; reach_words];
296 for (product, &component) in component_of.iter().enumerate() {
297 let state = (product % state_count) as u32;
298 if summary.automaton.is_accepting(state) {
299 let component = component as usize;
300 set_bit(
301 &mut accepting_reach[component * row_words..(component + 1) * row_words],
302 product / state_count,
303 );
304 }
305 }
306 for &component in topological.iter().rev() {
307 for &successor in &condensation[component as usize] {
308 union_component_rows(
309 &mut accepting_reach,
310 row_words,
311 component as usize,
312 successor as usize,
313 );
314 }
315 }
316
317 let mut offsets = Vec::with_capacity(offset_count);
318 let mut values = Vec::new();
319 let mut row = vec![0u64; row_words];
320 offsets.push(0);
321 for source in 0..vertex_count {
322 row.fill(0);
323 for initial in summary.automaton.initial_states() {
324 let product = source * state_count + initial as usize;
325 let component = component_of[product] as usize;
326 let component_row =
327 &accepting_reach[component * row_words..(component + 1) * row_words];
328 for (target, source) in row.iter_mut().zip(component_row) {
329 *target |= source;
330 }
331 }
332 values.extend(
333 set_bits(&row)
334 .take_while(|&target| target < vertex_count)
335 .map(|target| {
336 u32::try_from(target).expect("active vertex count was checked against u32::MAX")
337 }),
338 );
339 offsets.push(values.len());
340 }
341 Ok(Csr { offsets, values })
342}
343
344fn expand_relation(
345 vertices: &[RawInline],
346 active_vertices: &[RawInline],
347 active: Csr,
348 add_identity: bool,
349) -> Result<Csr, PathError> {
350 if vertices == active_vertices {
351 return Ok(active);
352 }
353
354 let active_to_full = active_vertices
355 .iter()
356 .map(|vertex| {
357 vertices
358 .binary_search(vertex)
359 .expect("active path vertices belong to the summary domain")
360 })
361 .collect::<Vec<_>>();
362 let added_identity = if add_identity {
363 vertices.len().saturating_sub(active_vertices.len())
364 } else {
365 0
366 };
367 let capacity = active
368 .values
369 .len()
370 .checked_add(added_identity)
371 .ok_or(PathError::CapacityOverflow)?;
372 let mut offsets = Vec::with_capacity(
373 vertices
374 .len()
375 .checked_add(1)
376 .ok_or(PathError::CapacityOverflow)?,
377 );
378 let mut values = Vec::with_capacity(capacity);
379 let mut active_source = 0usize;
380 offsets.push(0);
381 for source in 0..vertices.len() {
382 if active_to_full.get(active_source).copied() == Some(source) {
383 let mut identity_written = false;
384 for &active_target in active.row(active_source) {
385 let target = active_to_full[active_target as usize];
386 if add_identity && !identity_written && source < target {
387 values.push(source as u32);
388 identity_written = true;
389 }
390 values.push(target as u32);
391 identity_written |= source == target;
392 }
393 if add_identity && !identity_written {
394 values.push(source as u32);
395 }
396 active_source += 1;
397 } else if add_identity {
398 values.push(source as u32);
399 }
400 offsets.push(values.len());
401 }
402 debug_assert_eq!(active_source, active_vertices.len());
403 Ok(Csr { offsets, values })
404}
405
406fn strongly_connected_components(adjacency: &[Vec<u32>]) -> (Vec<u32>, usize) {
407 let mut reverse = vec![Vec::new(); adjacency.len()];
408 for (source, targets) in adjacency.iter().enumerate() {
409 for &target in targets {
410 reverse[target as usize].push(source as u32);
411 }
412 }
413
414 let mut seen = vec![false; adjacency.len()];
415 let mut postorder = Vec::with_capacity(adjacency.len());
416 for root in 0..adjacency.len() {
417 if seen[root] {
418 continue;
419 }
420 seen[root] = true;
421 let mut stack = vec![(root as u32, 0usize)];
422 while let Some((node, next_edge)) = stack.last_mut() {
423 if *next_edge < adjacency[*node as usize].len() {
424 let target = adjacency[*node as usize][*next_edge];
425 *next_edge += 1;
426 if !seen[target as usize] {
427 seen[target as usize] = true;
428 stack.push((target, 0));
429 }
430 } else {
431 postorder.push(*node);
432 stack.pop();
433 }
434 }
435 }
436
437 let mut component_of = vec![u32::MAX; adjacency.len()];
438 let mut component_count = 0u32;
439 for &root in postorder.iter().rev() {
440 if component_of[root as usize] != u32::MAX {
441 continue;
442 }
443 component_of[root as usize] = component_count;
444 let mut stack = vec![root];
445 while let Some(node) = stack.pop() {
446 for &predecessor in &reverse[node as usize] {
447 if component_of[predecessor as usize] == u32::MAX {
448 component_of[predecessor as usize] = component_count;
449 stack.push(predecessor);
450 }
451 }
452 }
453 component_count += 1;
454 }
455 (component_of, component_count as usize)
456}
457
458fn condensation(adjacency: &[Vec<u32>], component_of: &[u32], count: usize) -> Vec<Vec<u32>> {
459 let mut result = vec![Vec::new(); count];
460 for (source, targets) in adjacency.iter().enumerate() {
461 let source_component = component_of[source];
462 for &target in targets {
463 let target_component = component_of[target as usize];
464 if source_component != target_component {
465 result[source_component as usize].push(target_component);
466 }
467 }
468 }
469 for targets in &mut result {
470 targets.sort_unstable();
471 targets.dedup();
472 }
473 result
474}
475
476fn topological_order(adjacency: &[Vec<u32>]) -> Vec<u32> {
477 let mut indegree = vec![0usize; adjacency.len()];
478 for targets in adjacency {
479 for &target in targets {
480 indegree[target as usize] += 1;
481 }
482 }
483 let mut ready = indegree
484 .iter()
485 .enumerate()
486 .filter(|(_, degree)| **degree == 0)
487 .map(|(component, _)| Reverse(component as u32))
488 .collect::<BinaryHeap<_>>();
489 let mut result = Vec::with_capacity(adjacency.len());
490 while let Some(Reverse(component)) = ready.pop() {
491 result.push(component);
492 for &target in &adjacency[component as usize] {
493 indegree[target as usize] -= 1;
494 if indegree[target as usize] == 0 {
495 ready.push(Reverse(target));
496 }
497 }
498 }
499 debug_assert_eq!(result.len(), adjacency.len());
500 result
501}
502
503fn union_component_rows(rows: &mut [u64], width: usize, target: usize, source: usize) {
504 for word in 0..width {
505 let source_word = rows[source * width + word];
506 rows[target * width + word] |= source_word;
507 }
508}
509
510fn set_bit(words: &mut [u64], bit: usize) {
511 words[bit / u64::BITS as usize] |= 1u64 << (bit % u64::BITS as usize);
512}
513
514fn set_bits(words: &[u64]) -> impl Iterator<Item = usize> + '_ {
515 words
516 .iter()
517 .copied()
518 .enumerate()
519 .flat_map(|(word_index, mut word)| {
520 std::iter::from_fn(move || {
521 if word == 0 {
522 return None;
523 }
524 let bit = word.trailing_zeros() as usize;
525 word &= word - 1;
526 Some(word_index * u64::BITS as usize + bit)
527 })
528 })
529}