nocfbot-0005-cycle-detection-bitmap.patch

From 39fc31eca0cee7fe874aa4e0abfc7ebaaa69bc1e Mon Sep 17 00:00:00 2001
From: Henson Choi <assam258@gmail.com>
Date: Mon, 23 Feb 2026 13:02:06 +0900
Subject: [PATCH 5/6] Detect zero-consumption NFA cycles using elemIdx visited
 bitmap

---
 src/backend/executor/nodeWindowAgg.c  | 45 ++++++++++++++++-----------
 src/include/nodes/execnodes.h         |  4 +++
 src/test/regress/expected/rpr_nfa.out |  8 ++---
 src/test/regress/sql/rpr_nfa.sql      |  8 ++---
 4 files changed, 38 insertions(+), 27 deletions(-)

diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index 371439aad91..98546fb17f7 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -343,6 +343,10 @@ static void nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx,
 /* calculate shift bits */
 #define	NN_SHIFT(pos)	((pos) % NN_ITEM_PER_VAR) * NN_BITS_PER_MEMBER
 
+/* Bitmap macros for NFA cycle detection (cf. bitmapset.c, tidbitmap.c) */
+#define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
+#define BITNUM(x)	((x) % BITS_PER_BITMAPWORD)
+
 /*
  * initialize_windowaggregate
  * parallel to initialize_aggregates in nodeAgg.c
@@ -3016,11 +3020,15 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
 	/* Set up row pattern recognition PATTERN clause (compiled NFA) */
 	winstate->rpPattern = node->rpPattern;
 
-	/* Calculate NFA state size for allocation */
+	/* Calculate NFA state size and allocate cycle detection bitmap */
 	if (node->rpPattern != NULL)
 	{
 		winstate->nfaStateSize = offsetof(RPRNFAState, counts) +
 			sizeof(int32) * node->rpPattern->maxDepth;
+		winstate->nfaVisitedNWords =
+			(node->rpPattern->numElements - 1) / BITS_PER_BITMAPWORD + 1;
+		winstate->nfaVisitedElems = palloc0(sizeof(bitmapword) *
+											winstate->nfaVisitedNWords);
 	}
 
 	/* Set up row pattern recognition DEFINE clause */
@@ -6214,25 +6222,9 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx,
 
 		nfa_route_to_elem(winstate, ctx, state, jumpElem, currentPos, initialAdvance);
 	}
-	else if ((elem->max != RPR_QUANTITY_INF && count >= elem->max) ||
-			 (count == 0 && elem->min == 0))
+	else if (elem->max != RPR_QUANTITY_INF && count >= elem->max)
 	{
-		/*----------
-		 * Must exit: either reached max iterations, or group matched empty.
-		 *
-		 * FIXME: The (count == 0 && min == 0) condition is insufficient for
-		 * cycle prevention. Cycles can occur at any count value when loop back
-		 * happens without consuming rows. For example:
-		 *   Pattern: (A*)*
-		 *   After matching 3 A's (count=3), loop back at a B row
-		 *   Inner A* matches 0 times (skip path) → same (elemIdx, count=3)
-		 *   Infinite cycle at count=3, not count=0
-		 *
-		 * Currently, cycles are silently prevented by nfa_add_state_unique
-		 * detecting duplicate states, but this is implicit and not guaranteed
-		 * for all code paths. Explicit cycle detection is needed.
-		 *----------
-		 */
+		/* Must exit: reached max iterations. */
 		RPRPatternElement *nextElem;
 
 		state->counts[depth] = 0;
@@ -6452,6 +6444,17 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx,
 	RPRPatternElement *elem;
 
 	Assert(state->elemIdx >= 0 && state->elemIdx < pattern->numElements);
+
+	/* Cycle detection: if this elemIdx was already visited in this DFS, bail */
+	if (winstate->nfaVisitedElems[WORDNUM(state->elemIdx)] &
+		((bitmapword) 1 << BITNUM(state->elemIdx)))
+	{
+		nfa_state_free(winstate, state);
+		return;
+	}
+	winstate->nfaVisitedElems[WORDNUM(state->elemIdx)] |=
+		((bitmapword) 1 << BITNUM(state->elemIdx));
+
 	elem = &pattern->elements[state->elemIdx];
 
 	switch (elem->varId)
@@ -6506,6 +6509,10 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos,
 	{
 		RPRNFAState *savedMatchedState = ctx->matchedState;
 
+		/* Clear visited bitmap before each state's DFS expansion */
+		memset(winstate->nfaVisitedElems, 0,
+			   sizeof(bitmapword) * winstate->nfaVisitedNWords);
+
 		state = states;
 		states = states->next;
 		state->next = NULL;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 9a1561fce7e..3681d905bde 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2651,6 +2651,10 @@ typedef struct WindowAggState
 	Size		nfaStateSize;	/* pre-calculated RPRNFAState size */
 	bool	   *nfaVarMatched;	/* per-row cache: varMatched[varId] for varId
 								 * < numDefines */
+	bitmapword *nfaVisitedElems;	/* elemIdx visited bitmap for cycle
+									 * detection */
+	int			nfaVisitedNWords;	/* number of bitmapwords in
+									 * nfaVisitedElems */
 	int64		nfaLastProcessedRow;	/* last row processed by NFA (-1 =
 										 * none) */
 
diff --git a/src/test/regress/expected/rpr_nfa.out b/src/test/regress/expected/rpr_nfa.out
index a2a257329b7..8ac375cfe86 100644
--- a/src/test/regress/expected/rpr_nfa.out
+++ b/src/test/regress/expected/rpr_nfa.out
@@ -30,7 +30,7 @@
 --   Special Partition Cases
 --   DEFINE Special Cases
 --   Absorption Dynamic Flags
---   FIXME Issues (Known Limitations)
+--   Zero-Consumption Cycle Detection
 --
 -- Responsibility:
 --   - NFA runtime execution paths
@@ -2945,9 +2945,9 @@ WINDOW w AS (
 (5 rows)
 
 -- ============================================================
--- FIXME Issues - Known Limitations
+-- Zero-Consumption Cycle Detection
 -- ============================================================
--- FIXME 2 - Cycle prevention at count > 0
+-- Cycle prevention at count > 0: (A*)* inner skip cycles at count=3
 WITH test_cycle_nonzero AS (
     SELECT * FROM (VALUES
         (1, ARRAY['A']),
@@ -2976,7 +2976,7 @@ WINDOW w AS (
   4 | {B}   |             |          
 (4 rows)
 
--- FIXME 2 - Cycle with mixed nullables
+-- Cycle with mixed nullables: (A* B*)* multiple nullable paths
 WITH test_cycle_mixed AS (
     SELECT * FROM (VALUES
         (1, ARRAY['A']),
diff --git a/src/test/regress/sql/rpr_nfa.sql b/src/test/regress/sql/rpr_nfa.sql
index 0e853ca753b..be78ab760a9 100644
--- a/src/test/regress/sql/rpr_nfa.sql
+++ b/src/test/regress/sql/rpr_nfa.sql
@@ -30,7 +30,7 @@
 --   Special Partition Cases
 --   DEFINE Special Cases
 --   Absorption Dynamic Flags
---   FIXME Issues (Known Limitations)
+--   Zero-Consumption Cycle Detection
 --
 -- Responsibility:
 --   - NFA runtime execution paths
@@ -2190,10 +2190,10 @@ WINDOW w AS (
 );
 
 -- ============================================================
--- FIXME Issues - Known Limitations
+-- Zero-Consumption Cycle Detection
 -- ============================================================
 
--- FIXME 2 - Cycle prevention at count > 0
+-- Cycle prevention at count > 0: (A*)* inner skip cycles at count=3
 WITH test_cycle_nonzero AS (
     SELECT * FROM (VALUES
         (1, ARRAY['A']),
@@ -2215,7 +2215,7 @@ WINDOW w AS (
         A AS 'A' = ANY(flags)
 );
 
--- FIXME 2 - Cycle with mixed nullables
+-- Cycle with mixed nullables: (A* B*)* multiple nullable paths
 WITH test_cycle_mixed AS (
     SELECT * FROM (VALUES
         (1, ARRAY['A']),
-- 
2.50.1 (Apple Git-155)