================================================================================ PostgreSQL Row Pattern Recognition: Flat-Array Stream NFA 解説書 ================================================================================ 対象読者: PostgreSQLエグゼキュータ(executor)およびプランナー(planner)の構造に 基本的な理解がある開発者 範囲: PATTERN/DEFINE節のパースからNFAランタイム実行までの全工程 関連コード: - src/backend/parser/parse_rpr.c (パーサーフェーズ) - src/backend/optimizer/plan/rpr.c (オプティマイザフェーズ) - src/backend/executor/nodeWindowAgg.c (エグゼキュータフェーズ) - src/include/nodes/plannodes.h (プランノード定義) - src/include/nodes/execnodes.h (実行状態定義) - src/include/optimizer/rpr.h (型および定数) ================================================================================ Flat-Array Stream NFA とは？ 本実装の NFA は、従来の状態遷移グラフではなく、16バイト固定サイズの 要素によるフラット配列(flat array)で表現される。実行時には行ストリームを 前方専用(forward-only)で処理し、バックトラックなしで イプシロン遷移を即時展開する方式で動作する。 - Flat-Array: パターンをグラフではなくフラット配列に コンパイル (第IV章) - Stream: 行を一方向に順次消費し、 後戻りしない (第XII章) - NFA: 一つのコンテキスト内に複数状態が共存する 非決定的実行 (第VI章) 第I章 Row Pattern Recognition 概要 ================================================================================ Row Pattern Recognition(以下 RPR)はSQL:2016で導入された機能であり、 順序付きの行集合に対して正規表現ベースのパターンをマッチングする。 SQL標準は二つの形態を定義する: Feature R010: MATCH_RECOGNIZE (FROM 節) - 専用テーブル演算子 - MATCH_NUMBER(), CLASSIFIER() 等の専用関数を提供 - ONE ROW PER MATCH / ALL ROWS PER MATCH を選択可能 Feature R020: RPR in a window (WINDOW 節) - 既存ウィンドウ関数フレームワークに統合 - ALL ROWS PER MATCH のみサポート - MATCH_NUMBER() なし 本実装は Feature R020 を対象とする。 基本構文は以下のとおりである: SELECT ... OVER ( PARTITION BY ... ORDER BY ... ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING [INITIAL | SEEK] -- SEEKは標準で定義されているが未実装 AFTER MATCH SKIP TO NEXT ROW | SKIP PAST LAST ROW PATTERN ( <正規表現> ) DEFINE <変数> AS <条件>, ... ) PATTERN 節は行変数の正規表現である。 DEFINE 節は各変数が現在行において真(true)かどうかを判別するブール条件である。 例: PATTERN (A+ B) DEFINE A AS price > PREV(price), B AS price < PREV(price) このパターンは「価格が連続して上昇した後に下落する区間」をマッチングする。 第II章 全体処理パイプライン ================================================================================ RPR処理は三つのフェーズに分かれる: ┌─────────────────────────────────────────────────────────┐ │ 1. パース (Parser) │ │ SQLテキスト → PATTERN AST + DEFINE 式ツリー │ │ │ │ 2. コンパイル (Optimizer/Planner) │ │ PATTERN AST → 最適化 → フラットNFA要素配列 │ │ │ │ 3. 実行 (Executor) │ │ NFAシミュレーションによる行単位マッチング │ └─────────────────────────────────────────────────────────┘ 各フェーズは独立したデータ構造を使用し、フェーズ間のインターフェースは明確である: パーサー → プランナー: WindowClause.rpPattern (RPRPatternNode ツリー) WindowClause.defineClause (TargetEntry リスト) プランナー → エグゼキュータ: WindowAgg.rpPattern (RPRPattern 構造体) WindowAgg.defineClause (TargetEntry リスト) 第III章 パースフェーズ ================================================================================ III-1. 進入点 transformWindowDefinitions() (parse_clause.c) └─ transformRPR() (parse_rpr.c) transformRPR()はRPCommonSyntaxが存在する場合に呼ばれ、以下を実行する: (1) フレームオプションの検証 - ROWS のみ許可 (RANGE, GROUPS は不可) - 開始境界は CURRENT ROW のみ許可 - EXCLUDE オプションは不許可 (2) WindowClause への情報転写 - rpPattern, rpSkipTo, initial フィールドをコピー (3) DEFINE 節の変換 (transformDefineClause) III-2. PATTERN AST パーサーは PATTERN 節を RPRPatternNode ツリーへ変換する。 各ノードの型は以下の四種類である: RPR_PATTERN_VAR 変数参照。varName フィールドに名前を格納。 RPR_PATTERN_SEQ 連結(concatenation)。children に子ノードリスト。 RPR_PATTERN_ALT 選択(alternation)。children に分岐ノードリスト。 RPR_PATTERN_GROUP グループ(括弧)。children に本文ノードリスト。 すべてのノードに min/max フィールドがあり、量化子を表現する: A → VAR(A, min=1, max=1) A+ → VAR(A, min=1, max=INF) A* → VAR(A, min=0, max=INF) A? → VAR(A, min=0, max=1) A{3,5} → VAR(A, min=3, max=5) reluctant フィールドが -1 でなければ非貪欲(reluctant)量化子である。 例: PATTERN ((A+ B) | C*) ALT ├─ SEQ │ ├─ VAR(A, 1, INF) │ └─ VAR(B, 1, 1) └─ VAR(C, 0, INF) III-3. DEFINE 節の変換 transformDefineClause()は各 DEFINE 変数について: (1) 変数名の重複チェック (2) 式を通常のSQL式へ変換 (3) Boolean 型への強制 (coerce_to_boolean) (4) TargetEntry にラップし、resname に変数名を設定 PATTERN で使用されているが DEFINE に定義されていない変数は、 暗黙的に TRUE として評価される (すべての行にマッチング)。 第IV章 コンパイルフェーズ ================================================================================ IV-1. 進入点 create_windowagg_plan() (createplan.c) ├─ collectPatternVariables() 変数名収集 ├─ filterDefineClause() 未使用 DEFINE 除去 └─ buildRPRPattern() NFA コンパイル (6フェーズ) IV-2. buildRPRPattern() の6フェーズ Phase 1: AST 最適化 (optimizeRPRPattern) Phase 2: 統計収集 (scanRPRPattern) Phase 3: メモリ割り当て (allocateRPRPattern) Phase 4: NFA 要素充填 (fillRPRPattern) Phase 5: 最終化 (finalizeRPRPattern) Phase 6: 吸収可能性分析 (computeAbsorbability) IV-3. Phase 1: AST 最適化 パーサーが生成したASTをコピーした後、以下の最適化を適用する: (a) SEQ 平坦化: ネストされた SEQ を展開 SEQ(A, SEQ(B, C)) → SEQ(A, B, C) (b) 連続変数のマージ: 同じ変数の連続出現を単一量化子へ A A → A{2} A{2,3} A{1,2} → A{3,5} (c) 連続グループのマージ: 同一グループの繰り返しをマージ (A B)+ (A B)+ → (A B){2,INF} (d) 連続 ALT のマージ: 同一 ALT の繰り返しをマージ (A | B) (A | B) (A | B) → (A | B){3} (e) プレフィックス/サフィックスの吸収: グループ前後の同一シーケンスを吸収 A B (A B)+ → (A B){2,INF} (f) ALT の平坦化および重複除去 (A | (B | C)) → (A | B | C) (A | B | A) → (A | B) (g) 量化子の乗算: 安全な場合にネストした量化子を単一化 (A+)+ → A+ (A{2,3}){5} → A{10,15} (h) 単一子のアンラップ SEQ(A) → A, (A){1,1} → A IV-4. Phase 4: NFA 要素配列の生成 最適化されたASTをRPRPatternElementのフラット配列へ変換する。 これがランタイムでのNFAシミュレーションに使用される核心データ構造である。 RPRPatternElement 構造体 (16バイト): フィールド サイズ 説明 ───────────────────────────────────────────────────── varId 1B 変数ID (0-251) または制御コード (252-255) depth 1B グループのネスト深さ flags 1B ビットフラグ (下記参照) reserved 1B パディング min 4B 量化子の最小値 max 4B 量化子の最大値 next 2B 次の要素インデックス (順次フロー) jump 2B 分岐先インデックス (ALT/GROUP 用) 制御コード: RPR_VARID_BEGIN (252) グループ開始マーカー RPR_VARID_END (253) グループ終了マーカー RPR_VARID_ALT (254) 選択開始マーカー RPR_VARID_FIN (255) パターン完了マーカー 要素フラグ (1バイト、ビットマスク): ビット 定数 設定対象 説明 -------------------------------------------------------------------------- 0x01 RPR_ELEM_RELUCTANT VAR, BEGIN, 非貪欲(non-greedy)量化子。 END 短いマッチを優先：ループ脱出を 先に試行してから繰り返す。 単純変数(A+?)はVARに、 グループ((...)+?)はBEGIN+ENDに設定 0x02 RPR_ELEM_EMPTY_LOOP END グループ本体が空マッチを生成 可能（全子要素がnullable）。 通常ループバックと共に早送り 脱出クローンを生成し、サイクル 検出が正当なマッチを除去しない よう保証。(IV-4b) 0x04 RPR_ELEM_ABSORBABLE_BRANCH VAR, BEGIN, 吸収可能領域内の要素マーカー。 END, ALT 実行時に現在のNFA状態が 吸収可能コンテキスト内にあるか 追跡するために使用 0x08 RPR_ELEM_ABSORBABLE VAR, END 吸収判定ポイント。 連続反復間の吸収比較を 行う位置を表示。 - 単純無限VAR (A+): VAR要素自体に設定 - 無限GROUP ((A B)+): END要素のみに設定 アクセサマクロ: RPRElemIsReluctant(e) (e)->flags & 0x01 RPRElemCanEmptyLoop(e) (e)->flags & 0x02 RPRElemIsAbsorbableBranch(e) (e)->flags & 0x04 RPRElemIsAbsorbable(e) (e)->flags & 0x08 例: PATTERN (A+ B | C) AST: ALT(SEQ(VAR(A,1,INF), VAR(B,1,1)), VAR(C,1,1)) コンパイル結果: idx varId depth min max next jump 説明 ─────────────────────────────────────────────────── 0 ALT 0 1 1 1 -1 選択開始 1 A(0) 1 1 INF 2 3 分岐1: A+ 2 B(1) 1 1 1 4 -1 分岐1: B → FIN 3 C(2) 1 1 1 4 -1 分岐2: C → FIN 4 FIN 0 1 1 -1 -1 パターン完了 - idx 0: ALT マーカー。next(=1) は最初の分岐の開始 - idx 1: A 変数。next(=2) は B、jump(=3) は二番目の分岐の開始 - idx 2: B 変数。next(=4) は FIN - idx 3: C 変数。next(=4) は FIN - idx 4: FIN マーカー。マッチング成功シグナル next と jump の役割: - next: 現在の要素を「消費した後」に移動する次の要素。 VAR の場合はマッチング成功後の次の位置。 BEGIN/END の場合はグループ内部/外部の次の位置。 - jump: 「スキップする」対象の要素。 ALT の各分岐から次の分岐へのジャンプ。 BEGIN から END+1 へのスキップ経路 (min=0 のグループ)。 END からグループ本文先頭へのループバック。 例: PATTERN ((A B)+) idx varId depth min max next jump 説明 ─────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 4 グループ開始 1 A(0) 1 1 1 2 -1 A 2 B(1) 1 1 1 3 -1 B 3 END 0 1 INF 4 1 グループ終了 4 FIN 0 1 1 -1 -1 パターン完了 - idx 0: BEGIN。next(=1) はグループ本文への進入。 jump(=4) は END の次 = FIN へのスキップ (min=0 の場合に使用)。 - idx 3: END。next(=4) はグループ外への脱出。 jump(=1) はグループ本文先頭へのループバック。 IV-4a. Reluctantフラグ (RPR_ELEM_RELUCTANT) Reluctantフラグは Phase 4（fillRPRPattern）において、ASTノードの reluctant フィールドが非負の場合（reluctant >= 0）に設定される。ランタイムでの量化子 展開の優先順位を反転させる: 貪欲（デフォルト）: ループバックを先に試行し、その後脱出 （長いマッチ優先） 非貪欲: 脱出を先に試行し、その後ループバック （短いマッチ優先） 量化子を担う全ての要素にフラグが設定される: 単純VAR (A+?): VAR要素に RPR_ELEM_RELUCTANT を設定 グループ ((...)+?): BEGIN と END 要素に RPR_ELEM_RELUCTANT を設定 ランタイム（nfa_advance）においてフラグが DFS 探索順序を制御する: 量化子付きVAR: 貪欲: 優先パス = next（継続）、クローン = jump（スキップ） 非貪欲: 優先パス = jump（スキップ）、クローン = next（継続） END要素: 貪欲: 優先パス = jump（ループバック）、クローン = next（脱出） 非貪欲: 優先パス = next（脱出）、クローン = jump（ループバック） BEGIN（min=0）: 貪欲: 優先パス = next（グループ進入）、クローン = jump（スキップ） 非貪欲: 優先パス = jump（スキップ）、クローン = next（グループ進入） 吸収最適化には貪欲量化子が必要である。非貪欲量化子は 吸収可能性分析から除外される（IV-5 参照）。 IV-4b. Empty Loopフラグ (RPR_ELEM_EMPTY_LOOP) Empty-loopフラグは Phase 4（fillRPRPatternGroup）において、グループ本体が nullableの場合 -- すなわち、本体の全パスが0行マッチ可能な場合 （全子要素がnullable）-- END要素に設定される。 このフラグが設定されるパターン例: (A?)* Aがnullable（min=0）なのでグループ本体がnullable -> ENDにフラグ設定 (A? B?)+ 全子要素がnullable -> 本体nullable -> ENDにフラグ設定 (A | B*) B*がnullableなのでALTがnullable -> ENDにフラグ設定 このフラグはゼロ消費サイクル検出（elemIdx訪問ビットマップ）と連動して 動作する。このフラグがなければ、サイクル検出だけでは正当なマッチが 失敗する場合がある。 問題の例: (A*){2,3} - 反復1: A*が利用可能な全行を消費 -> count=1、END到達 - 反復2へループバック: A*が0行マッチ -> END再到達 - サイクル検出が同一行で同じelemIdxの再訪問を検出 -> 状態除去 - countがmin(2)に未到達 -> マッチ失敗（不正） RPR_ELEM_EMPTY_LOOP フラグがあれば、nfa_advance_end は2つのパスを生成する: 通常のループバック（サイクル検出が最終的に除去）と、ループを完全に バイパスする早送り脱出クローン。 （詳細なランタイム動作は IX-4(c) 参照。） IV-5. 吸収可能性分析 (RPR_ELEM_ABSORBABLE) コンテキスト吸収(Context Absorption)は O(n²) → O(n) の最適化手法である。 (ランタイムの動作は第VIII章で説明する。) このフェーズでは、パターンが吸収最適化に適した構造かどうかを判別し、 該当する要素にフラグを設定する: RPR_ELEM_ABSORBABLE 吸収比較地点 RPR_ELEM_ABSORBABLE_BRANCH 吸収可能領域の要素 適合条件: (1) SKIP PAST LAST ROW (NEXT ROW でない場合) (2) フレーム末尾が UNBOUNDED FOLLOWING 構造的条件 (isUnboundedStart + computeAbsorbabilityRecursive): Case 1: 単純 VAR+ (例: A+) → VAR に ABSORBABLE | ABSORBABLE_BRANCH を設定 Case 2: GROUP+ の内部が {1,1} の VAR のみで構成 (例: (A B)+) → 子要素に ABSORBABLE_BRANCH、 END に ABSORBABLE | ABSORBABLE_BRANCH を設定 Case 3: GROUP+ の本文が VAR+ で開始 (例: (A+ B)+) → BEGIN から本文へ再帰し Case 1 を適用。 A に ABSORBABLE | ABSORBABLE_BRANCH を設定。 B、END にはフラグなし → B へ進むと吸収停止。 吸収可能性はパターン単位ではなく要素(element)単位で判定される。 RPR_ELEM_ABSORBABLE フラグが設定された要素に状態がある場合のみ 吸収比較が実行され、当該領域を離れると吸収は永久に停止する。 このメカニズムにより、ランタイムにて 「先に開始したコンテキストが後から開始したコンテキストを常に包含する」 という単調性(monotonicity)を保証する。 第V章 NFAランタイムデータ構造 ================================================================================ V-1. RPRNFAState — NFA状態 一つのNFA状態は「パターンのどこまで進んだか」を表す。 フィールド 説明 ───────────────────────────────────────────────────── elemIdx 現在位置するパターン要素のインデックス counts[] 各グループ深さごとの繰り返し回数 isAbsorbable 吸収可能領域にあるかどうか next 連結リストの次の状態 counts 配列のサイズは (maxDepth + 1) であり、構造体末尾に可変長で 割り当てられる (flexible array member)。 例: PATTERN ((A B)+ C) で3回目の反復の B を待機する状態 要素配列: [0:BEGIN(d0) 1:A(d1) 2:B(d1) 3:END(d0) 4:C(d0) 5:FIN] elemIdx = 2 (B, depth 1) counts[0] = 2 (depth 0: END の深さ。グループ2回反復完了) counts[1] = 1 (depth 1: B の深さ。現在の反復で A マッチング) カウントは elemIdx ではなく depth でインデックスされる。 counts[0] は END(depth 0) 通過時に増加し、 状態が B(depth 1) にあってもグループ反復回数を保持する。 二つの状態が「同じ(equal)」である定義: elemIdx が同じで、当該要素の depth までの counts が同じであれば同一である。 nfa_states_equal() において counts[0..elem->depth] を memcmp で比較する。 現在の要素の深さ以下のカウントのみが意味を持つためである。 V-2. RPRNFAContext — マッチングコンテキスト 一つのコンテキストは「特定の開始行から始まったマッチング試行」を表す。 フィールド 説明 ───────────────────────────────────────────────────── states 活性NFA状態の連結リスト matchStartRow マッチングが開始された行番号 matchEndRow マッチングが完了した行番号 (-1 は未完了) lastProcessedRow 最後に処理した行 matchedState FIN に到達した状態 (greedy フォールバック用) hasAbsorbableState このコンテキストが他のコンテキストを吸収できるか allStatesAbsorbable このコンテキストが吸収されうるか next, prev 双方向連結リスト NFAは非決定的(nondeterministic)であるため、一つのコンテキスト内に 複数の状態が同時に存在できる。 例: PATTERN (A | B) C において、最初の行が A と B の両方にマッチングされる場合 コンテキスト内に二つの状態が共存する: 状態1: elemIdx=3 (C を待機、A 分岐経由) 状態2: elemIdx=3 (C を待機、B 分岐経由) この場合、二つの状態の (elemIdx, counts) が同じであるため nfa_add_state_unique() によって先に追加された状態1 (A 分岐) のみが維持される。 DFS が ALT の最初の分岐から処理するため、A 経由の状態が先に登録され、 B 経由の状態は重複として破棄される。これが優先性 (preferment) の保証である。 V-3. WindowAggState の RPR フィールド nfaContext / nfaContextTail 活性コンテキストの双方向連結リスト nfaContextFree 再利用コンテキストプール nfaStateFree 再利用状態プール nfaVarMatched 行別キャッシュ: varMatched[varId] nfaVisitedElems サイクル検出用ビットマップ nfaStateSize RPRNFAState の事前計算サイズ メモリ管理: 状態とコンテキストは自前のフリーリストで管理される。 palloc の代わりに再利用プールから取得し、解放時にプールへ返却する。 これは頻繁な割り当て/解放のオーバーヘッドを削減する。 第VI章 NFA実行: 3フェーズモデル ================================================================================ VI-1. 進入点と全体フロー ウィンドウ関数が各行を処理する際、row_is_in_reduced_frame() が呼ばれる。 この関数は現在行がマッチングされたフレームに属するかどうかを判別し、 必要であれば update_reduced_frame() を呼び出してNFAを駆動する。 update_reduced_frame() のフロー: (1) 対象行のコンテキストを検索または新規作成 (2) 行処理ループに進入 (3) ループ終了後、結果を reduced_frame_map に記録 行処理ループの疑似コード: targetCtx = nfa_get_head_context(pos) if targetCtx == NULL: targetCtx = nfa_start_context(pos) for currentPos = startPos ... if not nfa_evaluate_row(currentPos): -- 行が存在しない場合 nfa_finalize_all_contexts() -- すべてのコンテキストを完了処理 break nfa_process_row(currentPos) -- 3フェーズ処理 nfa_start_context(currentPos + 1) -- 次の開始点を先行作成 nfa_cleanup_dead_contexts() -- 無効なコンテキストを除去 if targetCtx->states == NULL: -- 対象コンテキスト消尽 break 核心: 一つの行を処理するために複数の行を先行処理することがある。 ウィンドウ関数の特性上、行 N のフレームを確定するには N 以降の行も 参照する必要があるためである。 VI-2. コンテキスト作成: nfa_start_context() 新しいコンテキストを作成し、初期 advance を実行する。 (1) nfa_context_alloc() でコンテキストを割り当て (2) matchStartRow = pos を設定 (3) 初期状態を作成: elemIdx=0 (パターンの最初の要素)、counts=すべてゼロ (4) nfa_advance(initialAdvance=true) を呼び出し 初期 advance はパターン先頭部分のイプシロン遷移を展開する。 例えば PATTERN ((A | B) C) の初期 advance: 開始: elemIdx=0 (ALT) → ALT 分岐を展開 → elemIdx=1 (A) — VAR であるため状態を追加、ここで停止 → elemIdx=2 (B) — VAR であるため状態を追加、ここで停止 結果: コンテキストに二つの状態 {A を待機、B を待機} 初期 advance では FIN に到達してもマッチングとして記録しない。 これは空マッチ(zero-length match)を防ぐためである。 VI-3. 行評価: nfa_evaluate_row() 現在行に対して DEFINE 節のすべての変数条件を一度に評価する。 for each defineClause[i]: result = ExecEvalExpr(defineClause[i]) varMatched[i] = (not null and true) PREV(), NEXT() 等の行ナビゲーション演算子をサポートするため、 前行、現在行、次行をそれぞれ異なるスロットに設定する: ecxt_scantuple = 前行 (PREV 参照用) ecxt_outertuple = 現在行 (デフォルト参照) ecxt_innertuple = 次行 (NEXT 参照用) varMatched 配列はその後の Phase 1 (Match) で参照される。 VI-4. nfa_process_row(): 3フェーズ処理 一行に対するNFA処理は三つのフェーズに分かれる: ┌─────────────────────────────────────────────┐ │ Phase 1: MATCH (収束) │ │ 現在行と各 VAR 状態を照合。 │ │ マッチング失敗した状態を除去。 │ │ │ │ Phase 2: ABSORB (吸収) │ │ 重複コンテキストをマージして状態爆発防止。 │ │ │ │ Phase 3: ADVANCE (展開) │ │ イプシロン遷移を展開して次の行を準備。 │ └─────────────────────────────────────────────┘ この順序が重要である: - Match が最初に実行されて「現在行を消費」する。 - Absorb は Match の直後、状態が更新された時点で実行する。 - Advance は最後に実行して「次の行を待機する状態」を準備する。 第VII章 Phase 1: Match ================================================================================ nfa_match() はコンテキストの各状態を巡回しながら: (1) 状態の elemIdx が VAR 要素かどうかを確認 (2) nfa_eval_var_match() で現在行と照合 (3) マッチング成功: 繰り返しカウントを増加、状態を維持 (4) マッチング失敗: 状態を除去 マッチング判定 (nfa_eval_var_match): varId が defineVariableList の範囲内であれば: varMatched[varId] の値を使用 varId が範囲を超える場合 (DEFINE に定義されていない変数): 無条件 true (すべての行にマッチング) 単純 VAR の即時 advance: min=1, max=1 の VAR であり次の要素が END の場合、 Match フェーズで直接 END まで処理する。 これは Phase 2 (Absorb) における正確な状態比較のために必要である。 例: PATTERN ((A B)+) において A がマッチングされると即座に B へ advance し、 B がマッチングされると即座に END まで進んでグループカウントを完了する。 そうすることで他のコンテキストとの吸収比較が可能になる。 第VIII章 Phase 2: Absorb (コンテキスト吸収) ================================================================================ VIII-1. 問題 現在の実装では、処理する各行ごとに新しいコンテキストを開始する。 PATTERN (A+) を10行に適用すると10個のコンテキストが生成され、 各コンテキストは独立して状態を追跡する。 行が N 個であれば総状態数は O(N²) となる: コンテキスト1 (行1 開始): A を N 回マッチング可能 コンテキスト2 (行2 開始): A を N-1 回マッチング可能 ... コンテキストN (行N 開始): A を 1 回マッチング可能 VIII-2. 解法: コンテキスト吸収 核心的観察: 先に開始したコンテキストは後から開始したコンテキストの すべてのマッチングを包含する (単調性の原理)。 コンテキスト1が行1から開始してAを5回マッチングした場合、 コンテキスト2(行2開始)がAを4回マッチングした状態は コンテキスト1にすでに包含されている。 したがってコンテキスト2はコンテキスト1に「吸収」されうる。 VIII-3. 吸収条件 (1) パターンが isAbsorbable としてマーク済み (IV-5 参照) (2) 対象コンテキストの allStatesAbsorbable が true (3) より以前のコンテキストが対象のすべての状態を「カバー」する カバー条件 (nfa_states_covered): より以前のコンテキストに同じ elemIdx の状態が存在し、 当該深さのカウントが等しいかそれ以上であればカバーされる。 VIII-4. 二重フラグ設計 二つのブールフラグで吸収判定を効率化する: hasAbsorbableState (単調的: true→false のみ可能) 「このコンテキストが他のコンテキストを吸収する能力を持つか?」 吸収可能な状態が一つでもあれば true。 状態が除去されて吸収可能な状態がなくなると false に転換。 一度 false になると再び true にはならない。 allStatesAbsorbable (動的: 変動可能) 「このコンテキストが吸収されうるか?」 すべての状態が吸収可能領域にあれば true。 非吸収状態が追加されると false、それが除去されると再び true。 VIII-5. 吸収順序 nfa_absorb_contexts() はテール(最新)からヘッド(最古)へ巡回する。 for ctx = tail to head: if ctx.allStatesAbsorbable: for older = ctx.prev to head: if older.hasAbsorbableState: if nfa_states_covered(older, ctx): free(ctx) -- 吸収済み break 最新のコンテキストから検査するため、最も最近に開始された (= 最も短いマッチングを持つ) コンテキストが先に吸収される。 第IX章 Phase 3: Advance (イプシロン遷移展開) ================================================================================ IX-1. 概要 nfa_advance() は Match 後の各状態からイプシロン遷移を展開して、 「次の行を待機する新しい状態群」を生成する。 イプシロン遷移とは行を消費せずに移動する遷移である: - ALT: 各分岐へ分岐 - BEGIN: グループへの進入 (または min=0 であればスキップ) - END: グループのループバック (または条件充足時に脱出) - FIN: マッチング完了を記録 - VAR の loop/exit: 量化子による繰り返し/脱出 VAR 要素に到達すると展開を停止して状態を追加する。 VAR は「次の行を消費する」要素であるためである。 IX-2. 処理順序: DFS と優先性(Preferment) advance は状態を辞書式順序(lexicographic order)で処理し、 各状態に対して深さ優先探索(DFS)を実行する。 この DFS 順序こそが SQL 標準の「優先性(preferment)」を保証する: PATTERN テキストで先に現れる分岐が優先する。 例: PATTERN (A | B) C ALT の最初の分岐 A が二番目の分岐 B より優先する。 A と B がともにマッチング可能な場合、A 経由のマッチングが選択される。 nfa_add_state_unique() が同じ状態の重複追加を防ぐため、 先に追加された (= 優先分岐の) 状態が維持される。 IX-3. ルーティング関数: nfa_route_to_elem() advance フェーズにおけるすべての要素間遷移は nfa_route_to_elem() を経由する。 この関数は次の要素の型に応じて動作を分岐する: 次の要素が VAR であれば: (1) 状態をコンテキストに追加 (nfa_add_state_unique) (2) VAR の min=0 であればスキップ経路も追加 (next で再帰) → ここで展開が停止する (VAR は「次の行を消費する」要素) 次の要素が非 VAR (ALT, BEGIN, END, FIN) であれば: → nfa_advance_state() を再帰呼び出しして展開を継続 この構造により advance は VAR に到達するまでイプシロン遷移を 再帰的に追跡し、VAR においてのみ停止する一貫した動作を示す。 IX-4. 要素別 advance 動作 (a) ALT (nfa_advance_alt) ALT 要素に遭遇するとすべての分岐を順番に展開する。 各分岐の最初の要素は jump ポインタで接続されている。 idx=0 (ALT) → 分岐1 開始(next) → 分岐2 開始(jump) → ... 各分岐に対して nfa_advance_state() を再帰呼び出しする。 (b) BEGIN (nfa_advance_begin) グループへの進入を処理する。 jump は END の次の要素（= グループ外の最初の要素）を指す。 Greedy (デフォルト): (1) グループ本文へ進入 (next で移動、当該 depth のカウントをリセット) (2) min=0 であればグループスキップ経路も追加 (jump で移動) Reluctant: 順序を反転 — スキップ経路を先に、グループ進入を後に。 スキップ経路が FIN に到達するとグループ進入経路は生成しない (最短マッチング優先)。 (c) END (nfa_advance_end) グループ終了を処理する。繰り返しロジックの核心である。 現在の深さのカウントを count とすると: count < min: ループバック (jump で移動、グループ本文を繰り返す) RPR_ELEM_EMPTY_LOOP フラグが設定されている場合: ループバックに加えて fast-forward 脱出経路も追加する。 これは本文が空マッチを生成して count が永遠に min に 到達できない可能性があるためである。fast-forward は counts[depth] を 0 にリセットして next で脱出する （残りの必要反復を空マッチとして扱う）。 min <= count < max: Greedy: ループバック優先、脱出を後に Reluctant: 脱出優先、ループバックを後に 脱出経路が FIN に到達するとループバックを省略。 count >= max: 無条件脱出 (next で移動) 脱出時: counts[depth] = 0 にリセットし、次の要素が外部 END であれば 外部 depth のカウントを増加させる。 (d) VAR (nfa_advance_var) 量化子を持つ VAR 要素の繰り返し/脱出を処理する。 現在の深さのカウントを count とすると: count < min: 無条件ループ (同じ elemIdx に留まり、次の行を待機) min <= count < max: Greedy: ループ優先、脱出(next) を後に Reluctant: 脱出優先、ループを後に 脱出経路が FIN に到達するとループを省略。 count >= max: 無条件脱出 (next で移動) 脱出時: counts[depth] = 0 にリセットする。 (e) FIN マッチング成功。matchedState に現在の状態を移動して記録し、 matchEndRow を現在行に設定する。 FIN に到達するとまだ処理されていない残りの状態をすべて除去する (早期終了)。DFS 順序により FIN に最初に到達した経路が 最も高い優先性を持つため、残りは劣位の経路である。 これが優先性(preferment)保証の核心メカニズムである。 SKIP PAST LAST ROW モードでは FIN 到達時、マッチング範囲内で 開始された後続コンテキストを即座に枝刈りする。 IX-5. 状態重複除去: nfa_add_state_unique() 新しい状態をコンテキストに追加する際、既存の状態と比較して 同一の状態がすでに存在する場合は追加しない。 比較基準: elemIdx + counts[0..elem->depth]（V-1 参照） この重複除去がNFAの状態爆発を抑制する核心メカニズムである。 DFS 順序によって優先分岐の状態が先に追加されるため、 後順位分岐の同一状態は自動的に破棄される。 IX-6. サイクル検出: nfaVisitedElems グループ本文が空マッチ(zero consumption)を生成しうる場合、 END からループバックすると無限ループが発生する可能性がある。 例: PATTERN ((A?)*) A? は min=0 であるためマッチングなしに通過可能。 外部グループが繰り返すと: BEGIN → A? skip → END → BEGIN → ... これを防ぐために: (1) コンパイル時: 本文が nullable なグループの END に RPR_ELEM_EMPTY_LOOP フラグを設定。 このフラグのランタイム効果は IX-4(c) 参照: count < min の時 fast-forward 脱出経路を追加し、 空マッチで count が増加しないデッドロックを解消する。 (2) ランタイム時: advance 内の各状態の DFS 展開直前に nfaVisitedElems ビットマップを初期化する (状態ごとに1回)。 DFS 中に各要素を訪問する際、当該 elemIdx のビットを設定。 すでに訪問した elemIdx に再訪問した場合、その経路を中断。 注意: ビットマップは elemIdx のみを追跡し、counts は考慮しない。 したがって同じ elemIdx だが異なる counts を持つ正当な再訪問も 遮断される可能性がある。これはグループ本体が nullable(すべての 経路が空マッチ可能)である場合にのみ発生し、 END -> loop-back -> skip -> END が単一 DFS 内で循環する。 この場合 END 要素に RPR_ELEM_EMPTY_LOOP フラグが設定されて いるため、fast-forward exit(IX-4(c))が循環を迂回する 代替経路を提供する。 第X章 マッチング結果処理 ================================================================================ X-1. Reduced Frame Map RPR マッチング結果は reduced_frame_map というバイト配列に記録される。 各行に対して一つのバイトが割り当てられ、値は以下のいずれかである: RF_NOT_DETERMINED (0) まだ処理されていない RF_FRAME_HEAD (1) マッチングの開始行 RF_SKIPPED (2) マッチング内部行 (フレームでスキップ) RF_UNMATCHED (3) マッチング失敗 ウィンドウ関数はこのマップを参照して各行のフレーム包含可否を決定する。 X-2. AFTER MATCH SKIP マッチング成功後、次のマッチング試行の開始点を決定する: SKIP TO NEXT ROW: マッチング開始行の次の行から新しいマッチング試行。 重複するマッチングが可能である。 SKIP PAST LAST ROW: マッチング終了行の次の行から新しいマッチング試行。 重複しないマッチングのみ可能である。 X-3. INITIAL vs SEEK 標準の定義（6.12節）: INITIAL: 最初の行が R であるマッチを探す。 SEEK: R からフルウィンドウフレーム末尾まで、 どこからでも最初のマッチを探索する。 いずれの場合も、マッチがなければ縮小ウィンドウフレームは空となる。 デフォルトは INITIAL である。 現在の実装: SEEK は未サポート（パーサがエラーを発生させる）。 INITIAL のみサポートしており、各行 pos から始まるマッチのみを探索する。 第XI章 具体的な例: 全工程の追跡 ================================================================================ XI-1. クエリ SELECT company, tdate, price, first_value(price) OVER w AS start_price, last_value(price) OVER w AS end_price FROM stock WINDOW w AS ( PARTITION BY company ORDER BY tdate ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW PATTERN (A+ B) DEFINE A AS price > PREV(price), B AS price < PREV(price) ); XI-2. データ 行番号 tdate price ────────────────────────── 0 2024-01-01 100 1 2024-01-02 110 2 2024-01-03 120 3 2024-01-04 115 4 2024-01-05 130 XI-3. コンパイル結果 PATTERN (A+ B) → 最適化後そのまま idx varId depth min max next jump ────────────────────────────────────────── 0 A(0) 0 1 INF 1 -1 A+ 1 B(1) 0 1 1 2 -1 B 2 FIN 0 1 1 -1 -1 DEFINE: A → "price > PREV(price)", B → "price < PREV(price)" isAbsorbable = true (A+ は単純無制限 VAR) XI-4. 実行トレース --- 行 0 (price=100) --- update_reduced_frame(0) 呼び出し。 コンテキスト C0 を作成 (matchStartRow=0)。 初期 advance: elemIdx=0(A) → VAR であるため状態を追加。 C0.states = [{elemIdx=0, counts=[0]}] nfa_evaluate_row(0): A: price(100) > PREV(price) → PREV なし → false B: price(100) < PREV(price) → PREV なし → false varMatched = [false, false] nfa_process_row(0): Phase 1 (Match): A(0) 状態 vs varMatched[0]=false → 状態を除去 C0.states = [] (空の状態) Phase 2 (Absorb): 省略 (状態なし) Phase 3 (Advance): 省略 (状態なし) C0.states が空であるためループ終了。 matchEndRow < matchStartRow → RF_UNMATCHED。 register_reduced_frame_map(0, RF_UNMATCHED)。 --- 行 1 (price=110) --- update_reduced_frame(1) 呼び出し。 コンテキスト C1 を作成 (matchStartRow=1)。 初期 advance: C1.states = [{elemIdx=0, counts=[0]}] nfa_evaluate_row(1): A: 110 > PREV(100) → true B: 110 < PREV(100) → false varMatched = [true, false] nfa_process_row(1): Phase 1 (Match): A(0) マッチング成功 → counts[0]++ → counts=[1] C1.states = [{elemIdx=0, counts=[1]}] Phase 3 (Advance): 状態 {elemIdx=0, counts=[1]}: A+ (min=1, count=1, max=INF) count >= min であるため: Greedy → ループ優先: {elemIdx=0, counts=[1]} を維持 脱出: counts[0]=0 リセット、next(=1) → {elemIdx=1, counts=[0]} C1.states = [{elemIdx=0, counts=[1]}, {elemIdx=1, counts=[0]}] --- 行 2 (price=120) --- コンテキスト C2 を作成 (matchStartRow=2)。 初期 advance: C2.states = [{elemIdx=0, counts=[0]}] nfa_evaluate_row(2): A: 120 > PREV(110) → true B: 120 < PREV(110) → false varMatched = [true, false] C1 nfa_process_row(2): Phase 1 (Match): {elemIdx=0, counts=[1]}: A マッチング → counts=[2] {elemIdx=1, counts=[0]}: B 不マッチング → 除去 C1.states = [{elemIdx=0, counts=[2]}] C2 nfa_process_row(2): Phase 1 (Match): {elemIdx=0, counts=[0]}: A マッチング → counts=[1] C2.states = [{elemIdx=0, counts=[1]}] Phase 2 (Absorb): C1(先に開始)は C2 をカバーするか? C1: {elemIdx=0, counts=[2]}, C2: {elemIdx=0, counts=[1]} 同じ elemIdx、C1.counts >= C2.counts → カバーされる C2 吸収済み。→ 除去。 Phase 3 (Advance): {elemIdx=0, counts=[2]}: Greedy → ループ + 脱出 ループ: {elemIdx=0, counts=[2]} 脱出: counts[0]=0 リセット、next(=1) → {elemIdx=1, counts=[0]} C1.states = [{elemIdx=0, counts=[2]}, {elemIdx=1, counts=[0]}] コンテキスト C3 を作成 (matchStartRow=3)。 --- 行 3 (price=115) --- nfa_evaluate_row(3): A: 115 > PREV(120) → false B: 115 < PREV(120) → true varMatched = [false, true] nfa_process_row(3): Phase 1 (Match): {elemIdx=0, counts=[2]}: A 不マッチング → 除去 {elemIdx=1, counts=[0]}: B マッチング → counts=[1] C1.states = [{elemIdx=1, counts=[1]}] Phase 3 (Advance): {elemIdx=1, counts=[1]}: B (min=1, max=1) count(1) >= max(1) → 無条件脱出 counts[0]=0 リセット、next = 2 (FIN) FIN 到達 → matchEndRow = 3、matchedState を記録。 早期終了: 残りの状態なしのため即座に完了。 C1.states = [] (FIN 到達後、空の状態) C1.states が空で matchEndRow=3 >= matchStartRow=1 → マッチング成功。 register_reduced_frame_map(1, RF_FRAME_HEAD) register_reduced_frame_map(2, RF_SKIPPED) register_reduced_frame_map(3, RF_SKIPPED) --- 行 4 (price=130) --- update_reduced_frame(4) 呼び出し。 C3 はすでに作成されているが matchStartRow=3 であるため対象外。 新しいコンテキスト C4 を作成 (matchStartRow=4)。 nfa_evaluate_row(4): A: 130 > PREV(115) → true B: 130 < PREV(115) → false ... 以降に行がないため nfa_finalize_all_contexts() を呼び出し。 マッチング未完了 → RF_UNMATCHED。 XI-5. 最終結果 行0: RF_UNMATCHED → フレーム = 自分自身 行1: RF_FRAME_HEAD → フレーム = 行1〜行3 行2: RF_SKIPPED → 行1のマッチング内部 行3: RF_SKIPPED → 行1のマッチング内部 行4: RF_UNMATCHED → フレーム = 自分自身 第XII章 核心設計決定のまとめ ================================================================================ XII-1. フラット配列 vs ツリーベース NFA 選択: フラット配列 (RPRPatternElement[]) 理由: - キャッシュフレンドリー: 16バイト固定サイズ、連続メモリ - インデックスベース参照: ポインタの代わりに2バイトインデックス - シリアライズが容易: プランノードとして渡す際に memcpy 可能 XII-2. Forward-only 実行 vs バックトラック 選択: Forward-only (状態集合追跡) 理由: - バックトラックは最悪の場合に指数的時間 - NFAシミュレーションは多項式時間を保証 - DFS 順序が優先性(preferment)を自然に保証。 量化子ごとの greedy/reluctant は DFS 探索順序の反転のみで実装 - ウィンドウ関数はソート済みの行を逐次的に受け取る。 Forward-only はこのパイプラインにそのまま適合するが、 バックトラックは以前の行の再訪問（re-fetch）が必要になる - DEFINE 条件は SQL 式（PREV、RUNNING 集計等）であり 再評価コストが高い。Forward-only は行あたり1回の評価で十分 XII-3. コンテキスト単位管理 選択: 開始行別の独立コンテキスト 理由: - SKIP TO NEXT ROW における重複マッチングのサポート - 各行のフレームを独立して決定 - 吸収最適化により重複コンテキストを O(n) で除去可能 XII-4. メモリプール管理 選択: 自前のフリーリスト 理由: - NFA 状態は行ごとに大量生成/消滅 - palloc/pfree のオーバーヘッドを回避 - 状態サイズは可変 (counts 配列) だが、一つのクエリ内では maxDepth が固定であるためすべての状態が同じサイズ XII-5. 実行最適化の総合 以下の最適化により NFA シミュレーションを実用的にする。 ── コンパイル時 ── (1) AST 最適化 (IV-3) パターンを NFA に変換する前に AST を単純化する。 連続変数のマージ（A A → A{2}）、SEQ フラット化、 量化子の乗算等により NFA 要素数を削減する。 意義: 要素数の削減は状態空間の縮小に直結し、 以降のすべてのランタイム段階（マッチング、吸収、advance）の コストが減少する。 ── ランタイム: advance 段階 ── (2) グループスキップ (IX-4(b)) min=0 のグループの BEGIN で jump によりグループ全体を スキップする。グループ本文を探索せず、直接グループ外の 最初の要素へ移動。Greedy は進入後スキップ、 Reluctant はスキップ後進入の順序。 意義: 選択的グループ（min=0）で本文探索なしに即座に スキップ経路を生成し、不要な DFS 展開を回避する。 (3) 状態の重複除去 (IX-5) advance で DFS が同一の (elemIdx, counts) 組み合わせの 状態を複数の経路で生成する場合がある。 また VAR 反復と異なりグループ反復では VAR 状態のままでは 吸収比較が不可能なため Phase 1 マッチ後 END まで inline advance するが、この過程でも 同一の END に到達する重複状態が発生しうる。 nfa_add_state_unique() が両方のケースで 同一状態の重複追加を遮断する。 意義: ALT 分岐や量化子展開における状態数の指数的増加を 防止する。DFS 順序により優先分岐の状態が先に登録されるため、 後順位分岐の同一状態は自動的に破棄され、 優先性（preferment）も同時に保証される。 (4) サイクル検出および fast-forward (IX-6, IX-4(c)) nullable なグループ本文（例: A?）が空マッチを繰り返すと、 END → BEGIN ループバックが無限に続く可能性がある。 二つのメカニズムで解決する: - visited ビットマップ（nfaVisitedElems）で同一要素の 再訪問を遮断し、無限ループを防止（安全性） - RPR_ELEM_EMPTY_LOOP フラグが設定された END で count < min の時、残りの必要反復を空マッチとして扱い グループ外へ脱出する fast-forward 経路を追加（正確性） 意義: サイクル検出が終了を保証し、fast-forward が min 条件の充足を保証する。これがなければ nullable グループを 含むパターンが無限ループに陥るかマッチングに失敗する。 (5) マッチプルーニング (IX-4(e)) advance 中に状態が FIN に到達すると、当該コンテキストの 残りの未処理状態をすべて除去する。DFS 順序により FIN に 先に到達した経路が最も高い優先性を持つため、残りは 劣等な経路である。 意義: 最善のマッチングが確定すれば、劣等な経路の探索を 即座に中断する。優先性保証と性能最適化を同時に達成する。 ── ランタイム: コンテキスト間 ── (6) Early Termination (SKIP PAST LAST ROW) SKIP PAST LAST ROW モードでマッチングが確定すると、 マッチング範囲内に開始行がある後続コンテキストを 追加処理なしで即座にプルーニングする。 SKIP TO NEXT ROW モードでは各行が独立したマッチングを 必要とするため、重複するコンテキストは維持される。 意義: 先行マッチング範囲と開始行が重複する後続 コンテキストをプルーニングし、不要な処理を回避する。 (7) コンテキスト吸収 (第VIII章) 各行ごとに独立コンテキストを生成すると O(n²) の状態が 蓄積される。先に開始したコンテキストが後発コンテキストの 状態を包含する単調性を利用し、重複コンテキストを早期に除去する。 吸収可能性は要素(element)単位で判定される。 RPR_ELEM_ABSORBABLE フラグが設定された要素でのみ 比較が実行される (IV-5 参照)。 意義: アクティブなコンテキスト数を定数レベルに維持し、 O(n²) → O(n) の時間計算量を達成する。 これがなければ長いパーティションで性能が急激に低下する。 付録 A. 主要関数インデックス ================================================================================ 関数名 ファイル 役割 ────────────────────────────────────────────────────────────────────── transformRPR parse_rpr.c パーサー進入点 transformDefineClause parse_rpr.c DEFINE 変換 collectPatternVariables rpr.c 変数収集 filterDefineClause rpr.c DEFINE フィルタリング buildRPRPattern rpr.c NFA コンパイルメイン optimizeRPRPattern rpr.c AST 最適化 fillRPRPattern rpr.c NFA 要素生成 finalizeRPRPattern rpr.c 最終化 computeAbsorbability rpr.c 吸収分析 update_reduced_frame nodeWindowAgg.c 実行メインループ nfa_start_context nodeWindowAgg.c コンテキスト作成 nfa_process_row nodeWindowAgg.c 3フェーズ処理 nfa_evaluate_row nodeWindowAgg.c DEFINE 評価 nfa_match nodeWindowAgg.c Phase 1 nfa_absorb_contexts nodeWindowAgg.c Phase 2 nfa_advance nodeWindowAgg.c Phase 3 nfa_advance_state nodeWindowAgg.c 状態別分岐 nfa_route_to_elem nodeWindowAgg.c 要素ルーティング nfa_advance_alt nodeWindowAgg.c ALT 処理 nfa_advance_begin nodeWindowAgg.c BEGIN 処理 nfa_advance_end nodeWindowAgg.c END 処理 nfa_advance_var nodeWindowAgg.c VAR 処理 nfa_add_state_unique nodeWindowAgg.c 重複除去 nfa_states_covered nodeWindowAgg.c 吸収カバー判定 付録 B. データ構造関係図 ================================================================================ パーサー階層 ──────── RPCommonSyntax ├─ rpSkipTo: RPSkipTo ├─ initial: bool └─ rpPattern: RPRPatternNode* (ツリー) ├─ nodeType: VAR | SEQ | ALT | GROUP ├─ min, max: 量化子 ├─ varName: 変数名 (VAR のみ) └─ children: List* (SEQ/ALT/GROUP のみ) プランナー階層 ────────── WindowAgg (プランノード) ├─ rpSkipTo: RPSkipTo ├─ defineClause: List └─ rpPattern: RPRPattern* ├─ numVars: int ├─ varNames: char** ├─ maxDepth: RPRDepth ├─ isAbsorbable: bool ├─ numElements: int └─ elements: RPRPatternElement[] (フラット配列) ├─ varId (1B) ├─ depth (1B) ├─ flags (1B) ├─ reserved (1B) ├─ min, max (4B + 4B) └─ next, jump (2B + 2B) エグゼキュータ階層 ────────── WindowAggState ├─ rpPattern: RPRPattern* (プランからコピー) ├─ defineClauseList: List ├─ nfaVarMatched: bool[] (行別キャッシュ) ├─ nfaVisitedElems: bitmapword* (サイクル検出) ├─ nfaContext ←→ nfaContextTail (双方向リスト) │ └─ RPRNFAContext │ ├─ states: RPRNFAState* (連結リスト) │ │ ├─ elemIdx │ │ ├─ counts[] │ │ └─ isAbsorbable │ ├─ matchStartRow, matchEndRow │ ├─ matchedState (FIN 到達時に複製) │ ├─ hasAbsorbableState │ └─ allStatesAbsorbable ├─ nfaContextFree (再利用プール) └─ nfaStateFree (再利用プール) 付録 C. NFA 要素配列の例集 ================================================================================ C-1. PATTERN (A B C) idx varId depth min max next jump ────────────────────────────────────────── 0 A 0 1 1 1 -1 1 B 0 1 1 2 -1 2 C 0 1 1 3 -1 3 FIN 0 1 1 -1 -1 C-2. PATTERN (A+ B*) idx varId depth min max next jump flags ───────────────────────────────────────────────── 0 A 0 1 INF 1 -1 ABSORBABLE | ABSORBABLE_BRANCH 1 B 0 0 INF 2 -1 2 FIN 0 1 1 -1 -1 A+ のみが吸収ポイント (Case 1)。A を超えると その状態の吸収は永続的に無効化される。 C-3. PATTERN (A | B | C) idx varId depth min max next jump ────────────────────────────────────────── 0 ALT 0 1 1 1 -1 選択開始 1 A 1 1 1 4 2 分岐1 → FIN、jump → 分岐2 2 B 1 1 1 4 3 分岐2 → FIN、jump → 分岐3 3 C 1 1 1 4 -1 分岐3 → FIN 4 FIN 0 1 1 -1 -1 C-4. PATTERN ((A B)+ C) idx varId depth min max next jump flags ─────────────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 4 ABSORBABLE_BRANCH 1 A 1 1 1 2 -1 ABSORBABLE_BRANCH 2 B 1 1 1 3 -1 ABSORBABLE_BRANCH 3 END 0 1 INF 4 1 ABSORBABLE | ABSORBABLE_BRANCH 4 C 0 1 1 5 -1 5 FIN 0 1 1 -1 -1 Case 2: {1,1} 本文 VAR の GROUP+。A、B はブランチ; END が吸収ポイント。C-6 (Case 3) と比較。 C-5. PATTERN ((A | B)+? C) idx varId depth min max next jump flags ─────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 5 RELUCTANT、グループ開始 1 ALT 1 1 1 2 -1 選択開始 2 A 2 1 1 4 3 分岐1 3 B 2 1 1 4 -1 分岐2 4 END 0 1 INF 5 1 RELUCTANT、グループ終了 5 C 0 1 1 6 -1 6 FIN 0 1 1 -1 -1 C-6. PATTERN ((A+ B)+ C) — 吸収可能性フラグの例 idx varId depth min max next jump flags ────────────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 4 ABSORBABLE_BRANCH、グループ開始 1 A 1 1 INF 2 -1 ABSORBABLE | ABSORBABLE_BRANCH 2 B 1 1 1 3 -1 3 END 0 1 INF 4 1 グループ終了 4 C 0 1 1 5 -1 5 FIN 0 1 1 -1 -1 BEGIN から本文へ再帰 → A が Case 1 (単純 VAR+) に適用。 A に ABSORBABLE | ABSORBABLE_BRANCH、BEGIN に ABSORBABLE_BRANCH。 B、END にはフラグなし → 状態が B へ進むと吸収停止。 (IV-5 Case 3 参照) C-7. PATTERN ((A+ B | C*)+ D) -- ALT 分岐別吸収の例 idx varId depth min max next jump flags ────────────────────────────────────────────────────────── 0 BEGIN 0 1 INF 1 6 ABSORBABLE_BRANCH 1 ALT 1 1 1 2 -1 ABSORBABLE_BRANCH 2 A 2 1 INF 3 4 ABSORBABLE | ABSORBABLE_BRANCH 3 B 2 1 1 5 -1 4 C 2 0 INF 5 -1 ABSORBABLE | ABSORBABLE_BRANCH 5 END 0 1 INF 6 1 EMPTY_LOOP 6 D 0 1 1 7 -1 7 FIN 0 1 1 -1 -1 ALT 分岐は独立して吸収可能性を判定する。 分岐 1: A+ が Case 1 → A に ABSORBABLE。B にはフラグなし。 分岐 2: C* が Case 1 → C に ABSORBABLE。 A と C は各分岐経路の一部として ABSORBABLE_BRANCH を受ける。 END に EMPTY_LOOP: 分岐 2（C*）が nullable → グループ本体が nullable。 BEGIN、ALT には ABSORBABLE_BRANCH（吸収可能要素への経路）。 ================================================================================ 文書終わり ================================================================================