Skip to content

Tags

Tags

v1.32.45-dev.250

Toggle v1.32.45-dev.250's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
bindings/python: +fix Trim the runtime dependencies, import pandas an…

…d networkx lazily, and publish wheels (#1058)

Installing libmata pulled coverage, cython, graphviz, ipykernel,
ipython, networkx, pandas,
papermill, pytest, pytest-cov, seaborn and tabulate as hard runtime
dependencies, and importing
libmata.nfa.nfa loaded pandas, networkx and tabulate even for code that
never plots or tabulates
anything.

## Change

- `pyproject.toml`: the runtime dependency list is empty and the
optional packages are offered as
the extras `pandas`, `plotting`, `notebooks`, `dev` and `all`;
`build-system.requires` asks for
`Cython>=3.0,<4` (the sources are Cython 3 only) and `cmake>=3.23`. The
build and test tools the
development shell needs (`cython`, `pytest`, `pytest-cov`, `coverage`)
join the `dev` dependency
group, so taking them out of the runtime list does not take them out of
`uv sync`; `uv.lock` is
  regenerated.
- pandas, networkx, tabulate, graphviz and IPython are imported inside
`to_dataframe()`,
`to_networkx_graph()`, `BinaryRelation.__str__()`,
`plot_using_graphviz()` and `display_inline()`,
  each raising an `ImportError` that names the extra to install.
- The remaining `make` prerequisite of an sdist build is documented at
`_build_mata()`; the unused
  `-DNO_THROW_DISPATCHER` is gone from `setup.py` and `CONTRIBUTING.md`.
- `deploy-pypi` builds wheels with cibuildwheel (manylinux x86_64 and
aarch64, macOS x86_64 and
arm64, CPython 3.13 and 3.14) and uploads them next to the sdist, so
installing does not need a C++
  toolchain.

## Verification

- The new `tests/test_lazy_imports.py` imports `libmata.nfa.nfa` and
`libmata.utils` in subprocesses
and finds none of pandas, networkx, tabulate and graphviz in
`sys.modules`.
- The bindings build with `make -C bindings/python`, and the Python
suite passes run from
  `bindings/python`: `173 passed, 3 skipped, 1 xfailed`.

Fixes #778.

## Relationship to #669

This reworks and extends the lazy-import/optional-extras changes
proposed in the open #669 on current devel; the `libmata.nft` package
declaration, dependency groups, and the now-Cython-3 extensions are
accounted for. #669 still conflicts and has not been updated since June,
so this PR can supersede it once reviewed.

This also includes the rest of #778: dropping the unused
`NO_THROW_DISPATCHER`, declaring build requirements, and adding wheel
publishing. Wheel builds use `cibuildwheel` with the standard manylinux
(`x86_64`, `aarch64`) and macOS (`x86_64`, `arm64`) CPython 3.13/3.14
configurations; the compiled library includes solvers etc. and should be
tested on their first Publishing actuation in a real runner (I can only
test the local binding build here).

## Verified here

- `make -C bindings/python`; then `pytest -q` from bindings/python: `173
passed, 3 skipped, 1 xfailed`.
- `uv lock --check`: `Resolved 96 packages in 9ms`.
- `tests/test_lazy_imports.py` runs two fresh interpreter probes and
confirms optional dependencies are not imported.


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->
<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **New Features**
* The base Python package installs without optional dependencies.
Install the relevant extras to use data, plotting, or notebook features.
* Optional packages load only when their related features are used. If a
required package is missing, the affected feature provides installation
guidance.
* PyPI releases include prebuilt wheels for Python 3.13 and 3.14 on
supported Linux and macOS platforms, alongside a source package.
* **Documentation**
* Clarified build requirements for source packages versus wheels, and
documented optional features and development setup.
<!-- end of auto-generated comment: release notes by coderabbit.ai -->

v1.32.45-dev.249

Toggle v1.32.45-dev.249's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
nfa,utils,docs: +test +docs Cover unify_targets and record rejected a…

…lternatives (fixes #752) (#1085)

# Summary

Fixes #752: this resolves every item of the issue. Items (a) and (b) and
the per-symbol tests are on `devel` or added here. Items (c) and (d) are
closed as measured rejections, recorded in EXP-3.

Finish #752 through two paths: the required `unify_targets()` coverage,
and documented, reproducible rejection of the two experimental
alternatives that would not improve devel's current implementation.


The target-union fast paths (#921), macrostate signature filtering
(#907), antichain node pool and parent links (#923/#963), and per-symbol
distance/finality tests are already on `devel`. Existing randomized
differential checks cover naive-versus-antichain inclusion in both
directions, counterexamples, and naive-versus-antichain universality.

## Production change: tests

Add `SynchronizedExistentialSymbolPostIterator::unify_targets()` tests
for:
- not currently synchronized;
- one and two synchronized posts;
- three or more posts;
- overlapping, disjoint, and duplicate targets;
- sparse sets that use gather/sort/unique and dense sets eligible for
bitset unification;
- targets next to `num_of_states()`.

No production implementation of the rejected alternatives is included.

## Rejected experiments: EXP-3

`docs/experiments/3-antichain-iterator-universality/` includes
applicable patches, probe sources, input lists, and the aggregate
results/reproduction commands.

| proposal | baseline | candidate | candidate / baseline |
|---|---:|---:|---:|
| Adaptive heap merge, 240 ARMC inclusion directions | 32501.0404 ms |
44388.1584 ms | 1.3657× |
| Adaptive heap merge, 180 Z3-Noodler determinizations | 2.6904 ms |
2.7368 ms | 1.0172× |
| Universality as Σ* inclusion, 40 random NFAs | 0.0875 ms | 0.1313 ms |
1.5006× |

Release GCC 16.2.0, `-O3 -DNDEBUG`, one pinned core, three interleaved
rounds on 40 ARMC pairs and 60 Z3-Noodler inputs, plus the separately
seeded universality corpus. All checked answers and counterexamples
agree. The heap alternative fails #752's explicit Z3-Noodler adoption
gate; the inclusion formulation adds work the dedicated algorithm
avoids.

## Verification

- New focused tests: **16,061 assertions in 10 cases passed**.
- Full Release suite: **531 cases; 525 passed, 2 skipped, 4 failed as
expected**.
- `nix fmt` applied.
- Both experiment patches pass `git apply --check`.


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->
<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **Documentation**
* Added a record of benchmark methods, results, and reproduction steps
for the evaluated iterator-merging and universality approaches.
* Updated the experiment index to mark the work as rejected; neither
tested alternative was adopted.
* **Tests**
* Added coverage for combining transition targets into a sorted,
deduplicated result, including targets near the maximum state number.
<!-- end of auto-generated comment: release notes by coderabbit.ai -->

v1.32.45-dev.248

Toggle v1.32.45-dev.248's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
nfa: +perf Append symbol posts without sorted insertion (#1078)

# Summary

Append symbol posts without a redundant sorted insert when builders
already emit increasing symbols, completing the remaining `Delta::add()`
and determinize part of #179.

Earlier `devel` work already removed the 32-slot first reservation
(#971), generalized direct post construction, added append helpers, and
optimized revert and trim. This PR adds the remaining moving `emplace`
insertion path, uses it in `Delta::add()`, and appends determinize posts
directly with a debug sortedness assertion.

Part of #179.

## Changes

- Add `OrdVector::emplace()` and expose it through `StatePost`.
- Use direct append in both `Delta::add()` append branches and for a
whole `SymbolPost`.
- Drop the reserve-and-resize pair when growing the state-post array; a
single resize suffices.
- Append determinize symbol posts directly; the existing randomized and
behavioral suites cover correctness.

## Verification

- New `OrdVector::insert()`/`emplace()` tests: appending, prepending,
middle insertion, duplicates, and move-only contents.
- Focused tests: **190 assertions in 3 cases passed**.
- Full Debug: **531 cases; 525 passed, 2 skipped; 4 failed as
expected**.
- Full Release: **532 cases; 526 passed, 2 skipped; 4 failed as
expected**.
- `nix fmt`: **0 files changed**.

## Performance

Release GCC 16.2.0, one pinned core; medians of four process medians
with 21 iterations each, old/new interleaved:

| operation | baseline | this PR |
|---|---:|---:|
| append-heavy Delta construction (256 × 1024 symbols) | 6.495 ms |
3.787 ms |
| `b-armc-incl-hard/aut1` determinize | 11.485 ms | 11.535 ms |

The append-heavy case is **1.715× faster**. Determinize is neutral on
this dense ARMC input (new/old ratio 1.0044, within noise); no
regression of the order warned about in #179 was observed.


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->
<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **Improvements**
* Ordered transition updates now preserve symbol ordering while
appending entries where appropriate. State storage grows directly to
accommodate newly requested states.
* Ordered-vector entries can be constructed during insertion, including
when working with move-only values.
* **Tests**
* Added coverage for sorted insertion, duplicate handling, and move-only
values.
<!-- end of auto-generated comment: release notes by coderabbit.ai -->

v1.32.45-dev.247

Toggle v1.32.45-dev.247's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
nft: +perf Build reachable projection with cached flat closures (#1083)

# Summary

Complete the reachable-output part of #753: `project_out()` no longer
constructs closures and posts for every useful input state before
trimming.

Also includes the separate optimization evaluating the projected-level
predicate once per closure state.

Part of #753. The default composition fast path, bounded membership
expansion, post-moving, closure search, level-predicate arrays, and
copy-avoiding jump unwinding are already on `devel`. Sharing one closure
helper with NFA ε removal remains a separate follow-up, so this is not a
claim to close every optional discussion point.

## Changes

- Start from `nft.initial` with a worklist and mark only the
output-reachable states.
- Compute projected-state closures lazily for reached sources, cached in
flat buffers with begin/end intervals.
- Collect moves into one flat buffer, sort and deduplicate them per
source, then densely renumber reachable old states and use
`DeltaBuilder` for the sorted result.
- Preserve copied retained posts, level/alphabet metadata, final-state
propagation, and the final trim of non-co-reachable states.
- Evaluate `is_projected_out` once per closure state.

## Correctness

- Regression coverage for a linear path across projected levels in both
jump modes, with wrapped projected levels and projection-discarded
paths.
- Existing projection tests and composition/projection differential
suites pass, including wrapped level cycles.
- Full Debug: **531 cases; 525 passed, 2 skipped, 4 failed as
expected**.
- Full Release: **532 cases; 526 passed, 2 skipped, 4 failed as
expected**.
- `nix fmt`: **0 files changed**.

## Performance

Projection of level 1 out of a 2000-state two-level chain. Release GCC
16.2.0, one pinned core; medians of four process medians, up to 15 runs
each, old/new interleaved:

| implementation | `project_out` time |
|---|---:|
| baseline | 7.358370 ms |
| this PR | 0.115238 ms |

**63.854× faster.** Both produce 1001 states and 1000 transitions. This
is the structured projection chain above, not a claim of the same factor
for all inputs.


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->

<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **Bug Fixes**
* Projection now correctly handles paths containing consecutive epsilon
transitions, producing equivalent results across supported jump modes.
* Projection processes reachable output states more efficiently, which
can reduce unnecessary work for larger state spaces.

<!-- end of auto-generated comment: release notes by coderabbit.ai -->

v1.32.45-dev.246

Toggle v1.32.45-dev.246's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
applications/strings: +perf Pool segmentation counts and concatenate …

…in one pass (#1082)

# Summary

Implement the remaining segmentation and n-ary ε-concatenation parts of
#207. The earlier #904 work already shares one simulation per final
state.

Part of #207.

## Changes

- Replace the segmentation worklist's one-`std::map`-per-target
representation with compact epsilon-count vectors shared through pool
indices. Materialize the public `VisitedEpsMap` once at the end.
- Iterate state posts by reference instead of copying them in the
segmentation traversal.
- Build the n-ary ε-concatenation in one pre-sized delta with all parts
appended shifted, avoiding the repeated copies of the accumulator made
by a left fold.
- Retain the existing fold's operand ordering, empty-result handling,
arithmetic overflow checks, and resulting language/noodle behavior.

## Correctness

- Additional segmentation tests for ordered epsilon-span indexing and
duplicate/shared epsilon-count pools.
- Additional n-ary-concatenation tests comparing structure and language
to a repeated `concatenate_eps()` fold, including empty operands.
- Focused tests in both Debug and Release: **100,489 assertions in 24
cases passed**, including randomized noodle/differential cases.
- Full Debug: **532 cases; 526 passed, 2 skipped, 4 failed as
expected**.
- Full Release: **533 cases; 527 passed, 2 skipped, 4 failed as
expected**.
- `nix fmt`: **333 files, 0 changed**.

## Performance

A 1000-state segmentation chain using 128 distinct ε symbols. Release
GCC 16.2.0, one pinned core; medians of four process medians, up to 25
runs each, old/new interleaved:

| implementation | Segmentation construction |
|---|---:|
| map-per-target baseline | 15.407600 ms |
| pooled-vector implementation | 4.458535 ms |

**3.456× faster.** Both produce 999 visited states over 999 depths.


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->

<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **Bug Fixes**
* Multi-part string concatenation now preserves the order of components
and delimiters, including in equation results.
* Concatenations involving an empty automaton now return no results
instead of producing an invalid result.
* Epsilon-transition counts are now tracked consistently when states are
reached through multiple paths.

<!-- end of auto-generated comment: release notes by coderabbit.ai -->

v1.32.45-dev.245

Toggle v1.32.45-dev.245's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
nfa: +perf Concatenate without materializing epsilon connectors (#1081)

# Summary

Complete the remaining #240 item (b): `concatenate(...,
use_epsilon=false)` now avoids materializing an ε-connected intermediate
and running global ε removal whenever it can do so without changing
semantics.

Also includes the still-missing connector optimization from #751: one
sorted ε post per lhs final rather than repeated insertion per target.

Fixes #240. Part of #751.

Already on `devel` before this PR: per-state ε-closures (#962/#1029),
shared closure handling, transition-count-based NFT ε removal (#856),
and binary-search `OrdVector::count()` (#1067).

## Changes

- Build the ordinary concatenation with the shifted rhs delta.
- Merge each shifted rhs-initial post into the corresponding lhs final
states; make a lhs final state final when any rhs initial is also final.
- Build the sorted shifted rhs-initial target vector once and insert one
ε post per lhs final for the ε-preserving path.
- Retain the old global ε-removal path when operands already contain the
connecting symbol: their pre-existing ε-transitions still need
closure/removal.
- Preserve empty-symbol-post, trailing-state, and final-state domain
behavior.

## Correctness

- Randomized connector-plus-global-removal reference checks in both
direct and fallback paths (96 pairs).
- Exact final-state, initial-state, delta, and state-count comparisons
for ε-free operands.
- Self-concatenation, empty languages, rhs initial that is final, custom
ε above and below other posts, merging into existing ε posts, trailing
states, and a 2000-state ε chain.
- Concatenation tests: **1,290 assertions in 27 cases passed**.
- Full Release suite: **537 cases; 531 passed, 2 skipped, 4 failed as
expected**.
- `nix fmt`: **0 files changed**.

## Performance

Two random 3000-state NFAs, five symbols, no ε on the inputs. Release
GCC 16.2.0, one pinned core; medians of four process medians, up to 15
runs per process, old/new interleaved:

| implementation | concatenate time |
|---|---:|
| connector + global `remove_epsilon` | 1.090 ms |
| direct construction | 0.849 ms |

**1.285× faster.** Both produce 6000 states and 51000 transitions.


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->

<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **Bug Fixes**
* Improved automaton concatenation when epsilon transitions are
disabled, including cases with existing epsilon transitions, empty
languages, and final states shared across operands.
* Results now retain the expected language while avoiding unused
trailing states in supported cases.
* **Tests**
* Expanded coverage for concatenation edge cases and comparisons with
epsilon-based concatenation.

<!-- end of auto-generated comment: release notes by coderabbit.ai -->

v1.32.45-dev.244

Toggle v1.32.45-dev.244's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
nfa,nft,alphabet: +perf Add each distinct delta symbol once (#1080)

# Summary

Implement the remaining alphabet-filling item from koniksedy's follow-up
comment in #754: avoid string conversion and hash insertion once per
symbol post when a symbol occurs in many posts.

The issue's headline mintermization, reverse-index, enumerated-naming,
and regex-conversion items are already on `devel`.

Part of #754.

## Changes

- `Delta::add_symbols_to()` now iterates `Delta::get_used_symbols()`
once, adding each distinct symbol once.
- `Nfa::fill_alphabet()` delegates to that helper.
- `Nft::fill_alphabet()` follows the same distinct-symbol route;
DONT_CARE and EPSILON remain excluded.
- Add NFA/NFT tests with a few symbols occurring across many posts.
EPSILON and DONT_CARE do not become alphabet letters.

## Verification

- Full Debug: **532 cases; 526 passed, 2 skipped; 4 failed as
expected**.
- Full Release: **533 cases; 527 passed, 2 skipped; 4 failed as
expected**.
- `nix fmt`: **0 files changed**.

## Performance

Random NFA with 2000 states and four symbols. Release GCC 16.2.0, one
pinned core, seven interleaved pairs, 100 alphabet fills per
measurement:

| implementation | median of seven |
|---|---:|
| per-symbol-post baseline | 9.410 ms |
| distinct symbols (this PR) | 6.702 ms |

**1.404× faster.**


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->
<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **Bug Fixes**
* Alphabet creation now includes each distinct ordinary symbol once,
even when it appears across multiple transitions.
* Epsilon and “don’t care” transitions are excluded from the generated
alphabet.
* NFA and NFT alphabets now consistently reflect the ordinary symbols
used by their transitions, including when transitions repeat a symbol
across states or levels.
<!-- end of auto-generated comment: release notes by coderabbit.ai -->

v1.32.45-dev.243

Toggle v1.32.45-dev.243's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
nfa: +perf Close the remaining items of #740 (reuse distances in equi…

…valence; CSR-based get_terminating_states) (#1074)

# Summary

Closes the remaining items of #740 on `devel`.

Two commits against `devel` (bc2f271):

1. **Item 4 — reuse distances in antichain equivalence.**
`are_equivalent` ran the antichain inclusion algorithm twice (once per
direction), and each call recomputed both automata's
`distances_to_final()`. Move the algorithm into an internal overload
that takes both distance vectors by reference, and have
`compute_equivalence` build each vector once. The public four-argument
`is_included_antichains` keeps its exact signature.

2. **Item 3 — `get_terminating_states` over predecessor CSR.** The
previous implementation was `reverted().get_reachable_states()`: one
sorted `Delta::add` per transition to build a reversed delta that the
backward BFS then only reads for predecessor lists. Replace with a
backward BFS over the existing `PredecessorIndex` (the helper
`get_useful_states()` already builds).

Items 1 and 2 (backward BFS over CSR for `distances_to_final()`) are
already on `devel` from #871.

Fixes #740.

## Verification

- New edge-case tests for `distances_to_final` and
`get_terminating_states`: no final states, self-loops, several finals,
unreachable finals, `num_of_states()` coming from initial/final rather
than delta.
- Randomized oracle over 60 seeds: `get_terminating_states()` equals the
previous implementation `revert(aut).get_reachable_states()`.
- Counterexample test where only the second direction of equivalence
finds a difference (`lhs = {a}`, `rhs = {a, b}`).
- Full C++ suite, Release + Debug, `JOBS=2`, memory-capped: **533 cases,
527 passed, 2 skipped, 4 failed as expected**. Assertions: 5,985,681 /
5,985,644 passed.

## Performance

Item 4 (equivalence reuse). ARMC pairs, Release GCC 16.2.0 -O3, one
pinned core, medians of 21 interleaved runs:

| pair | old ms | new ms |
|---|---:|---:|
| easy/aut1-aut2 | 2.212 | 2.034 (−8.1%) |
| easy/aut1-aut1 | 18.925 | 18.461 (−2.5%) |
| easiest, medium, medium-hard, hard | within noise |

Item 3 replaces whole-automaton revert (one sorted insert per
transition) with a CSR build + backward BFS, both O(|Q| + |Δ|). Measured
indirectly through trim-heavy ARMC inclusion inputs (within noise there,
structural win on large sparse automata).


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->
<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **Bug Fixes**
* Language-equivalence checks now return a counterexample when the
right-hand automaton accepts a word that the left-hand automaton does
not.
* **Performance**
* Equivalence checks reuse distance calculations, reducing repeated
work.
* Finding terminating states uses a backward traversal, avoiding
construction of a reversed automaton.
* **Reliability**
* Added checks for edge cases in final-state distances and
terminating-state results.
<!-- end of auto-generated comment: release notes by coderabbit.ai -->

v1.32.45-dev.242

Toggle v1.32.45-dev.242's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
nfa,nft: +perf Move chained in-place results out of rvalues (Fixes #745…

…) (#1077)

# Summary

Closes #745 by implementing item 5 (the only remaining item; items 1–4
landed separately via #906, #954, and `append_shifted` work in #751).

Chained in-place methods (`trim`, `unify_initial`, `unify_final`,
`concatenate`, `unite_nondet_with`, `complement_deterministic`,
`swap_final_nonfinal`) now have ref-qualified overloads. Lvalues return
`*this` by reference as before; rvalues mutate and then move the
complete automaton.

## Changes

- `Nfa& trim(...) &` keeps the old in-place signature; `Nfa trim(...)
&&` returns by value.
- Same pattern applied to all seven methods, and mirrored on `Nft` where
supported so that an `Nft` rvalue returns `Nft`, not `Nfa`. `Nft`
derives directly from `Automaton` (not `Nfa`), so the slicing pitfall
from the issue does not arise; tests assert complete levels survive.
- Existing call sites that relied on the previous explicit-argument
forwarding were corrected.

Items already on `devel` that cover items 1–4 of #745: chained deep
copies dropped (#906, #954), `Nft::operator=(Nft&&)` actually moves
(#745 precursor work), `renumber_targets`/`append_shifted` moved the
appended posts instead of copying three times.

## Verification

- New focused Debug rvalue tests: **502 assertions in 4 cases passed**.
- Focused ref-qualified tests: **83 assertions in 4 cases passed**.
- Full C++ suite, JOBS=4, memory-capped:
  - Debug: **534 cases; 528 passed, 2 skipped, 4 failed as expected**.
  - Release: **535 cases; 529 passed, 2 skipped, 4 failed as expected**.
- `nix fmt`: 0 files changed.

## Performance

Interleaved Release microbenchmark, 100k states / 800k transitions. The
old code path copies when binding a chainable method on a temporary; the
new rvalue overload moves instead:

| variant | median |
|---|---:|
| old copy | 47.330 ms |
| new move | 31.263 ms |
| **1.514× faster** | |

Fixes #745.


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->

<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **New Features**
* NFA and NFT operations such as trimming, unifying initial or final
states, concatenation, and nondeterministic union can now be chained on
temporary automata, returning the resulting automaton by value.
* NFA operations also support temporary automata for final/nonfinal
state swapping and deterministic complementation.
* **Compatibility**
* Operations on named automata continue to modify the original object
and return a reference. Concatenation and union retain support for
copying or consuming the operand.

<!-- end of auto-generated comment: release notes by coderabbit.ai -->

v1.32.45-dev.241

Toggle v1.32.45-dev.241's commit message

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature.
applications/strings: +perf Expand shortest words by prefix (#1079)

# Summary

Replace `ShortestWordsMap`'s reverted automaton and per-edge word-set
expansion with a forward layered expansion keyed by word prefix.

`Nfa::distances_to_final()` already provides the backward distances over
a predecessor CSR (#871). Start at the source states having the shortest
distance, and expand states only along transitions whose targets
approach a final state. All states with the same prefix share one
frontier entry; nondeterminism does not multiply paths that spell the
same word.

Part of #751. The bulk-Delta connectors are independent changes,
including the one-ε-post-per-lhs-final concatenation connector;
`get_terminating_states` and the predecessor-CSR/counting-sort
infrastructure are already implemented elsewhere.

## Correctness

- Deterministic tests for all shortest words per state, minimum across
multiple queried states, empty languages, out-of-range states, and
EPSILON as an ordinary counted symbol.
- A randomized oracle over **200 small NFAs** checks
`get_shortest_words()` and `ShortestWordsMap::get_shortest_words_from()`
for individual states, all pairs, and all states against a bounded
reference acceptor.
- Full Debug: **532 cases; 526 passed, 2 skipped; 4 failed as
expected**.
- Full Release: **533 cases; 527 passed, 2 skipped; 4 failed as
expected**.
- `nix fmt`: **0 files changed**.

## Performance

Dense 16-state-wide, 30-layer automaton where every state connects over
symbol 0 to all states of the next layer. Release GCC 16.2.0, one pinned
core; medians of four process medians, 50 repetitions each, old/new
interleaved:

| implementation | median |
|---|---:|
| baseline | 1.318815 ms |
| this PR | 0.550935 ms |

**2.394× faster.** Both variants return exactly one 29-symbol word.


<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->

<!-- coderabbit-ai-generated:v1 -->

## Summary by CodeRabbit

* **Bug Fixes**
* Shortest-word queries now return only accepted words with the minimum
length across the requested states.
* Queries correctly return no results when none of the requested states
can reach an accepting state, while still returning valid results if
some requested states are outside the automaton.
  * The `EPSILON` symbol is preserved when included in a returned word.

<!-- end of auto-generated comment: release notes by coderabbit.ai -->