Repository navigation
Description
Severity: High · Effort: Medium/Large · Expected effect: 2–100× target when future synchronization labels are disjoint; little change on compatible inputs
Scope: SynchronizationType and exist_synchronization(), SynchronizationProperties::get_synchronization_types(), and its two uses in compose_fast_no_jump(): the pruning test in copy_transition and the zero-level decision in the main loop, plus the assertion at L1033-L1039.
Problem
SynchronizationProperties stores two bits per state: whether some path inside the current block reaches the synchronization level with an EPSILON, and whether some path reaches it with a symbol. exist_synchronization(lhs, rhs) only requires that neither side is ONLY_ON_EPSILON. It never asks whether both sides can read the same symbol, how DONT_CARE changes that, or whether the pair can still reach a final state. An lhs whose only synchronization label is a and an rhs whose only label is b are both ONLY_ON_SYMBOL, so every pair of their branches is built, and the projected result's trim() removes the grid only after it has been allocated and traversed.
A family where lhs branches into n paths that all synchronize on a and rhs into n paths that all synchronize on b has an empty relation. Local Release probe (GCC 15.2, -O3 -DNDEBUG, f874bae):
| Branches per side | Raw states / transitions (project_out_sync_levels = false) |
Projected and trimmed |
|---|---|---|
| 16 | 273 / 272 | empty |
| 32 | 1,057 / 1,056 | empty |
| 64 | 4,161 / 4,160 | empty |
| 128 | 16,513 / 16,512 | empty |
At 128 branches the raw build took about 3 ms and the projected one about 4 ms. The grid is created in copy_transition: the test at L624-L631 passes because both sync types are ONLY_ON_SYMBOL. A label-aware test rejects the family at the initial pair, where the lhs labels {a} and the rhs labels {b} do not intersect.
UNDEFINED also means two different things. States past the synchronization level get it, and so do states before it that cannot reach it at all (no successors, or only dead ends). Both are allowed by the tests at L629-L630.
The enum comments are swapped: ONLY_ON_SYMBOL (L49) says "Synchronization on EPSILON" and ONLY_ON_EPSILON (L50) says "Synchronization on symbol". The bit values are used consistently with the names.
Proposed change
- Pin the current truth table of
exist_synchronization,exist_intersectionandexist_epsilonwith tests and fix the two comments. - Replace or supplement the two-bit type with a per-state synchronization frontier:
Compute it in the same post-order traversal as
struct SyncFrontier { bool has_epsilon; // still drives the waiting simulations bool has_dont_care; // kept as a flag, never expanded over the alphabet SymbolSet explicit_symbols; // ordinary symbols only SyncBlock next_block; // needed once several synchronization blocks are traversed bool can_finish_after_block; };
get_synchronization_types(): a state on the synchronization level contributes its own labels, every other state takes the union over its in-block successors, and fast EPSILON edges are skipped. Levels strictly increase inside a block, so this is a DAG pass. Keep "past the synchronization level" (always allowed) separate from "cannot reach it" (an empty frontier, which can be rejected). - Choose the representation adaptively: small sorted inline vectors for a few labels, interned shared sets when many states have the same frontier, and a dense bitset only for a small dense alphabet.
- Add
may_synchronize(lhs_frontier, rhs_frontier):EPSILON is outside this test. Whether one side may advance on an EPSILON stays with the waiting logic (explicit(lhs) ∩ explicit(rhs) ≠ ∅ OR lhs.has_dont_care AND (explicit(rhs) ≠ ∅ OR rhs.has_dont_care) OR rhs.has_dont_care AND explicit(lhs) ≠ ∅perform_wait_on_lhs/rhs) and later with the epsilon filter (NFT composition: add an epsilon-filter state so each epsilon interleaving is built once #812). DONT_CARE follows the fast path's current rule, which matches every symbol except EPSILON (L538-L542). If CanDONT_CAREmatch withEPSILON? #561 or NFT: revert, add_state and Nft = Nfa lose levels; is_universal, complement and DONT_CARE matching are wrong on multi-level NFTs #763 item 7 change that rule, the predicate changes with it. - Use
may_synchronizeinstead ofexist_synchronizationat the two existing pruning points (L628 and L1014) and update the assertion at L1033. Both points stop only the exploration of inner successors or of the step after a zero-level pair. Zero-level pairs, final states, fast EPSILON processing and the waiting simulations are unchanged. - For lookahead past the next zero-level state (fast EPSILON edges, cycles through zero-level states, several synchronization blocks), compute over the SCC condensation or return
unknown. Never reject on incomplete information. - Optionally cache pair results in a tri-state (
unknown,no,yes) table or hash map. - Evaluate deeper lookahead: pairs of next-block signatures and backward reachability of final pairs. Keep only variants whose pruning pays for their preprocessing.
Explanation and worked example
What the summary answers now. The current summary asks "can lhs eventually read some symbol at the synchronization level?" and "can rhs?". For lhs a and rhs b both answers are yes, so composition explores both branch trees. The useful question is "can they eventually read the same symbol?", and at the initial pair the answer is no.
The probe family. lhs has 2 levels and synchronizes on level 1; rhs has 3 levels and synchronizes on level 1:
lhs: r0 -xᵢ-> mᵢ -a-> f i = 1..n, f final
rhs: s0 -yⱼ-> tⱼ -b-> uⱼ -z-> g j = 1..n, g final
compose(lhs, rhs, 1, 1, project, JumpMode::NoJump, CompositionMode::FastNoJump)
From (r0, s0) lhs steps to every (mᵢ, s0). lhs now waits at its synchronization level, and rhs steps from s0 to every tⱼ, creating all n² pairs (mᵢ, tⱼ). Only there does synchronize() find that a and b never match. That gives 1 + n + n² states, all dead. With frontiers, frontier(r0) = {a} and frontier(s0) = {b}, so the main loop stops at the initial pair.
DONT_CARE. If lhs had DONT_CARE instead of a, the pair is compatible although the explicit sets do not intersect, and the relation is non-empty. This is the control case: lookahead must not change it. DONT_CARE against DONT_CARE is also compatible, since the synchronized iterator matches it as an equal symbol.
EPSILON is not a wildcard. An EPSILON on one side's synchronization level makes the other side wait. That is decided by the waiting simulations today and by the epsilon filter later. The frontier keeps has_epsilon so this logic still sees it, and the label test only prunes the branch that synchronizes on a symbol.
Why not store all reachable labels for every state? A separate full set per state can take O(states × alphabet) memory, and repeated unions can dominate runtime. Most frontiers in layered NFTs are small or repeated, so interning and an adaptive representation keep the precise test cheap.
Why not trim the operands first? Trimming an operand removes states that cannot reach its own final states. Two individually productive paths can still have incompatible synchronization labels. Compatibility is a property of the pair.
Step-by-step execution plan
Read first: SynchronizationProperties, the DONT_CARE handling in synchronize() and in product()'s process_dont_care() (src/nft/intersection.cc), the level invariants of the fast path, and #561 / #763 item 7 for DONT_CARE against EPSILON. Write examples for explicit/explicit, wildcard/explicit, wildcard/wildcard, epsilon/ordinary and empty frontiers.
- Add counters: frontier construction time and bytes, compatibility queries, definite rejects, unknowns, and states avoided.
- Add the
aversusbbranch family above as a test and benchmark, plus the DONT_CARE control that must stay non-empty. - Implement an immutable
SyncFrontierwith the simplest small-vector representation. Do not optimize storage before correctness data exists. - Compute frontiers for the acyclic in-block regions. For invalid or cyclic structure return
maybeand keep the old behavior. - Insert the check at the two pruning points. Verify by exhaustive trace enumeration on tiny NFTs that no rejected pair belongs to an accepted run.
- Add set interning and adaptive dense storage only after measuring frontier sizes on Mata and z3-noodler inputs.
- Benchmark disjoint labels, partial overlap, wildcard-heavy, full overlap and large alphabets. Count preprocessing in the total time.
Dependencies and hand-off: The one-block frontier works on today's fast path and does not need the epsilon filter (#812). Its EPSILON handling must be revisited when that filter lands, and multi-block frontiers belong to direct general composition (#814). Configuration interning (#813) is unaffected, because rejected pairs never get a key. The fast-versus-general differential tests from #770 are the oracle.
Definition of done: the disjoint branch family is rejected at the initial pair; DONT_CARE and EPSILON have focused positive and negative tests; unknown always falls back to exploration; exhaustive tiny-NFT enumeration finds no false negative; and small fully compatible cases regress by at most 5%.
Expected result and validation
Target 2–100× where future label incompatibility is common, as in failed combinations of string constraints, with little output change on compatible cases.
- The disjoint branch family is rejected near the root and never builds the quadratic grid.
- Wildcard and epsilon semantics have focused positive and negative tests.
- Lookahead never causes a false negative:
unknownfalls back to exploration. - Preprocessing must not slow small or fully compatible cases by more than 5%; a dispatch threshold may disable it below a measured size.
Related: #561 and #763 item 7 (DONT_CARE against EPSILON), #770 (differential tests for the composition modes), #743 (the pair map is still allocated for rejected inputs).
Part of the composition work tracked in (#790).
Activity
nft: +fix Correct the swapped comments of the composition synchroniza…
nft: +feat Normalize the states the fast composer generates on request
nft: +feat Normalize the states the fast composer generates on request (
nft: +fix Correct the swapped comments of the composition synchroniza…
nft: +feat Compose by a direct traversal of the aligned configuration…
nft: +feat Skip the pairs of the fast composition whose synchronizati…