Repository navigation
Tags
Tags
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 -->
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 -->
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 -->
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 -->
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 -->
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 -->
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 -->
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 -->
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 -->
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 -->
PreviousNext