Skip to content

NFT composition: prune state pairs whose future synchronization labels cannot match #816

Open

Description

@koniksedy

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

  1. Pin the current truth table of exist_synchronization, exist_intersection and exist_epsilon with tests and fix the two comments.
  2. Replace or supplement the two-bit type with a per-state synchronization frontier:
    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;
    };
    Compute it in the same post-order traversal as 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).
  3. 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.
  4. Add may_synchronize(lhs_frontier, rhs_frontier):
    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) ≠ ∅
    
    EPSILON is outside this test. Whether one side may advance on an EPSILON stays with the waiting logic (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 Can DONT_CARE match with EPSILON? #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.
  5. Use may_synchronize instead of exist_synchronization at 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.
  6. 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.
  7. Optionally cache pair results in a tri-state (unknown, no, yes) table or hash map.
  8. 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.

  1. Add counters: frontier construction time and bytes, compatibility queries, definite rejects, unknowns, and states avoided.
  2. Add the a versus b branch family above as a test and benchmark, plus the DONT_CARE control that must stay non-empty.
  3. Implement an immutable SyncFrontier with the simplest small-vector representation. Do not optimize storage before correctness data exists.
  4. Compute frontiers for the acyclic in-block regions. For invalid or cyclic structure return maybe and keep the old behavior.
  5. 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.
  6. Add set interning and adaptive dense storage only after measuring frontier sizes on Mata and z3-noodler inputs.
  7. 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: unknown falls 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).

Metadata

Metadata

Assignees

No one assigned

    Labels

    For:libraryThe issue is related to library (c++ implementation)Module:nftThe issue is related to Nondeterministic Finite Transducerstype:optimizationThis issue is related to a possible optimization of an algorithm, improving the performance of Mata.

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions