Re: Row pattern recognition

Hi Ishii-san,

I'm sending a patch that refactors the NFA context absorption logic
for Row Pattern Recognition (RPR).

== Overview ==

This patch fixes a flawed NFA execution model where interleaved
match/advance
logic prevented correct context absorption. The new design reorganizes
execution into a clear three-phase cycle: "match → absorb → advance",
enabling proper state synchronization for absorption.

== Major Changes ==

1. NFA Execution Flow Redesign (nodeWindowAgg.c)

Previously, match and advance logic were interleaved in
nfa_step_single().
This interleaved approach prevented proper state synchronization needed
for absorption - states would scatter to different positions before
absorption could compare them. Now they are clearly separated:

- nfa_match(): Convergence phase. Evaluates all waiting states against
the current row. Checks VAR elements' DEFINE conditions and removes
failed states.

- nfa_absorb_contexts(): Absorbs redundant contexts. Performs absorption
checks at synchronized points after matching completes.

- nfa_advance(): Divergence phase. Expands epsilon transitions.
Handles ALT (alternation), END (group termination), and optional
elements.

Advantages of three-phase design:
- Correct absorption: All states evaluate the same row first, ensuring
synchronized positions for meaningful absorption comparison.
- Clear semantics: Each phase has single responsibility - convergence,
optimization, divergence - making the logic easier to understand.
- Predictable state positions: After match phase, all states are at
known positions, enabling reliable absorption decisions.

2. Two-flag Absorption Design (rpr.c)

At planning time, analyzes absorption eligibility and sets two flags:

- RPR_ELEM_ABSORBABLE: Absorption judgment point (WHERE to compare).
Set on the VAR element itself for simple unbounded VAR (A+),
or on END only for groups ((A B)+).

- RPR_ELEM_ABSORBABLE_BRANCH: Marks the absorbable region.
Set on ALL elements within the region. Used at runtime to track
state.isAbsorbable.

Example - Pattern "(A B)+ C":
Element 0 (A): ABSORBABLE_BRANCH
Element 1 (B): ABSORBABLE_BRANCH
Element 2 (END): ABSORBABLE | ABSORBABLE_BRANCH <- judgment point
Element 3 (C): (none)

Advantages of two-flag design:
- Correctness: Ensures absorption comparison happens only at
synchronized
points (e.g., END for groups), not at arbitrary positions.
- Efficiency: All analysis done at planning time; runtime uses simple
O(1) flag checks instead of pattern structure analysis.
- Simplicity: Runtime logic is just monotonic flag propagation -
once state leaves absorbable region, it stays non-absorbable.

3. Context-level Absorption Flags (execnodes.h)

Added two flags to RPRNFAContext structure:

- hasAbsorbableState: True if at least one state is absorbable.
Indicates whether this context can absorb other contexts.

- allStatesAbsorbable: True if ALL states are absorbable.
Indicates whether this context can be absorbed.

Absorption condition: Ctx1.hasAbsorbableState && Ctx2.allStatesAbsorbable

Advantages of asymmetric two-flag design:
- Fast pre-filter: O(1) flag check eliminates most context pairs before
expensive state-by-state comparison.
- Flexible absorption: Ctx1 can have extra non-absorbable states and
still absorb Ctx2, as long as Ctx1 covers all of Ctx2's absorbable
states.
- Optimized updates: hasAbsorbableState is monotonic (true→false only),
skipping recalculation once false. allStatesAbsorbable can recover
(false→true) when non-absorbable states die.

4. State-level isAbsorbable Flag (execnodes.h)

Added isAbsorbable field to RPRNFAState structure:

- Computed at creation: sourceAbsorbable && (elem->flags &
ABSORBABLE_BRANCH)
- Monotonic property: once false, stays false forever
- Cannot re-enter the absorbable region once left

5. Advance Function Separation

Split the monolithic processing into per-element-type functions:

- nfa_advance_alt(): Expands ALT branches. Processes all branches in
DFS order to preserve lexical priority.

- nfa_advance_end(): END group repetition logic. Decides loop/exit
based on count vs min/max constraints.

- nfa_advance_var(): VAR repetition/exit transitions.

- nfa_route_to_elem(): Routes to next element. If VAR, adds to waiting
states; otherwise, recursively expands epsilon transitions.

6. VAR→END Inline Transition

When a simple VAR (min=max=1) matches and the next element is END,
we transition to END immediately in the match phase. This is necessary
for correct absorption: states must be at END to be marked absorbable
before the absorption check occurs.

7. EXPLAIN Output Improvements (explain.c)

Changed average length statistics from integer to float with 1 decimal:
- ExplainPropertyInteger → ExplainPropertyFloat
- "%.0f" → "%.1f"

== Performance Impact ==

For patterns like "A+ B", context absorption achieves O(n²) → O(n)
complexity improvement.

Example: Input A A A A A B
- Row 0: Ctx1 at A (count=1)
- Row 1: Ctx1 at A (count=2), Ctx2 at A (count=1)
→ Ctx1.count >= Ctx2.count, so Ctx2 is absorbed
- Row 2: Ctx1 at A (count=3), Ctx3 at A (count=1)
→ Ctx3 is absorbed
- ...

Only one context is maintained throughout, achieving O(n).

== Algorithm Details ==

The absorption algorithm works as follows:

For each pair (older Ctx1, newer Ctx2):
1. Pre-check: Ctx1.hasAbsorbableState && Ctx2.allStatesAbsorbable
→ If false, skip (fast filter)
2. Coverage check: For each Ctx2 state with isAbsorbable=true,
find Ctx1 state with same elemIdx and count >= Ctx2.count
3. If all Ctx2 absorbable states are covered, absorb Ctx2

The asymmetric design (Ctx1 needs hasAbsorbable, Ctx2 needs allAbsorbable)
allows absorption even when Ctx1 has extra non-absorbable states.

== Key Design Decisions ==

- VAR→END transition in match phase: When a simple VAR (max=1) matches
and the next element is END, we transition immediately in the match
phase rather than waiting for advance. This ensures states are at END
(marked absorbable) before the absorption check.

- Optional VAR skip paths: When advance lands on a VAR with min=0,
we create both a waiting state AND a skip state (like ALT branches).
This ensures patterns like "A B? C" work correctly.

- END→END count increment: When transitioning from one END to another
END within advance, we must increment the outer END's count. This
handles nested groups like "((A|B)+)+" correctly.

- initialAdvance flag: The first advance after context creation must
skip FIN recording. Reaching FIN without evaluating any VAR would
create a zero-length match, which is invalid.

== Future Work ==

- Reluctant quantifiers: Currently rejected at parse time with error
"reluctant quantifiers are not yet supported". The semantics for mixed
patterns (e.g., A+? B+) and the optimal implementation approach need
further clarification.

- State pruning: May be required for reluctant quantifiers (enables early
match finalization) and context absorption (increases absorption
eligibility by removing competing states).

- No more large-scale refactoring is planned. Future work will focus on
quality verification through additional test cases, comprehensive test
coverage, and memory leak checks.

Please review.

Best regards,
Henson