Skip to main content

triblespace_paths/
index.rs

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/// Exact accepted endpoint relation for one summary snapshot.
44///
45/// The forward CSR is the canonical denotation. Reverse fibers and the three
46/// domain views are derived from it. The constructional [`PathSummary`] is
47/// retained so independently built indexes can still be merged exactly.
48#[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    /// Builds an index directly from graph edges.
60    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    /// Builds an index directly from tribles.
68    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    /// Materializes one exact endpoint relation from a constructional summary.
76    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    /// Exact constructional summary retained by this index.
123    pub fn summary(&self) -> &PathSummary {
124        &self.summary
125    }
126
127    /// Fixed automaton defining this relation.
128    pub fn automaton(&self) -> &Automaton {
129        self.summary.automaton()
130    }
131
132    /// Number of graph terms in the canonical endpoint domain.
133    pub fn vertex_count(&self) -> usize {
134        self.summary.vertices.len()
135    }
136
137    /// Number of distinct accepted endpoint pairs.
138    pub fn accepted_pair_count(&self) -> usize {
139        self.forward.values.len()
140    }
141
142    /// Whether the automaton accepts a path from `source` to `target`.
143    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    /// Sorted, duplicate-free accepted endpoint pairs.
157    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    /// Sorted accepted targets for one source.
168    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    /// Sorted accepted sources for one target.
176    pub fn reaching<'a>(&'a self, target: &RawInline) -> impl Iterator<Item = RawInline> + 'a {
177        self.values(self.reverse_ordinals(target))
178    }
179
180    /// Sorted sources having at least one accepted target.
181    pub fn starts(&self) -> impl Iterator<Item = RawInline> + '_ {
182        self.values(&self.starts)
183    }
184
185    /// Sorted targets having at least one accepted source.
186    pub fn ends(&self) -> impl Iterator<Item = RawInline> + '_ {
187        self.values(&self.ends)
188    }
189
190    /// Sorted vertices accepted from themselves.
191    pub fn diagonal(&self) -> impl Iterator<Item = RawInline> + '_ {
192        self.values(&self.diagonal)
193    }
194
195    /// Closes the canonical union of two retained summaries.
196    pub fn merge(&self, other: &Self) -> Result<Self, PathError> {
197        Self::from_summary(self.summary.merge(&other.summary)?)
198    }
199
200    /// Closes the canonical union of any nonempty index collection.
201    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
256/// Close only the endpoints that occur in a direct product arc. Every
257/// positive-length accepted path lies in this carrier. A nullable automaton's
258/// identity over the larger supplied domain is added by [`expand_relation`].
259fn 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}