16 KiB
NGRA Regex 源生成 Checklist
本文件按一次扫描消耗的前缀 IR 数量分层，记录源生成器需要实现的形态。
消耗量从高到低排列，从整个 region 的识别一直降到单条 MATCH 指令。
为什么按 IR 消耗量分层
早期版本按正则语法分批（基础匹配 / 计数 / ALT / 捕获组……），这描述的是表达式形态。
但 EmitPrefix 之后，生成器面对的不再是表达式，而是带前缀的指令窗口：
a|b与(?<a>abcd|a(bc)c)在语法上分属两批，在前缀 IR 里却共用同一个 「region 链 +Prev_Fail切换」骨架；abc与a[abc]d在语法上同属一批，消耗的 IR 条数却不同；WorkingRegion/ExeCondition/ObserveMethod/PopCondition是横切在每条指令上的，任何按语法组织的清单都无法表达它们。
因此清单以「一个 TryGenerateXxx 一次吞掉几条 IR」为轴，与
RegexAnalyzer.PrefixEmit 里 TryEmitXxx 的调度链保持同构。
生成器统一约定
这些约定是所有层级的前提，先固定下来再写具体层：
- 返回值语义：所有
TryGenerateXxx返回本次消耗的 IR 条数，-1表示窗口不匹配。 不得返回 pattern 长度、字符数等其它含义的整数。 - 调度链顺序：调度链的
if / else if严格按 L1 → L2 → L3 → L4 排列， 层号即消耗量的递减顺序，高消耗形态优先尝试，落空后自然降级到单指令。 - 窗口约定：扫描窗口为
ir_sp[index..]，长度不足时由各TryGenerate自行短路返回-1。 窥探深度参照 IR 优化器的 8 条窗口。 - 前缀不参与消耗计数：前缀装饰（L5）不单独消耗 IR，它包裹在 L1–L4 产出的代码外层。
- 作用域归属：代码块的作用域由
Prefix.WorkingRegion决定，不由表达式嵌套决定。 - 控制流形态：region 一律生成
do { ... } while(false)+break， 不使用 .NET generated regex 的goto+ 标签方案。
正确性核心与纯优化的分界
- L2 + L4 + L5 + L1 的必需项是正确性核心：region 作用域、单指令主体、前缀装饰
三者支撑绝大多数形态；但
COUNT_COMPLEX与 FIND 系（L1.5–L1.9）的 body 不是独立 region， L2 接不住，没有降级路径，因此同样属于核心。 - L1 的压平项（L1.1–L1.4）与 L3 全部是纯优化：它们只把 L2/L4 会生成的嵌套结构
压平成更好的代码形状。未实现时必须干净地返回
-1，让窗口自然降级，不得影响正确性。
这条分界决定了实现顺序：先把 L2/L4/L5 打通拿到可运行基线，再补 L1 的必需项， 最后才是 L1.1–L1.4 与 L3。
记录模板
层级:
触发窗口:
消耗 IR 数:
覆盖样本:
期望代码形状:
Optimized IR:
IR -> Code 规则:
前缀交互:
备注:
L0 方法级
一次消耗整个 IR 列表 + RegexInfo，只产出骨架，不产出任何匹配逻辑。
| # | 触发 | 消耗 | 产出 | 状态 |
|---|---|---|---|---|
| L0.1 | TextRegexSource 入口 |
全部 | Match(ReadOnlySpan<char>) 签名与 MatchResult 返回 |
[ ] |
| L0.2 | RegionCount |
元数据 | 每个 region 的 start / end / success 槽 |
[ ] |
| L0.3 | SingleLineResultCount |
元数据 | Observe_Line 所需的行结果槽 |
[ ] |
| L0.4 | MinPredictLength |
元数据 | 入口处最小长度断言（可延后） | [ ] |
| L0.5 | — | — | 活动指针、锚点指针、SourceGenContext 按需变量声明 |
[ ] |
样本：任意，用 abc 验证骨架能编译即可。
关注点：region 槽是否必须全量分配、行结果槽能否按 ObserveSource 稀疏分配。
L1 Region 组合级（含必需项）
一次消耗多个 region + 尾部控制指令，是窗口消耗量最高的形态。
这些组合在 EmitPrefix 里已经被识别过一次
（TryEmitAltChain / TryEmitTryGroupTail / TryEmitComplexIR），生成器应与之一一对应。
除 L1.5–L1.9 外，本层全部是代码形状优化：不实现时窗口会降级到 L2 + L5， 生成出语义等价但嵌套更深的代码。
| # | 触发窗口 | 消耗 | 覆盖样本 | 性质 | 状态 |
|---|---|---|---|---|---|
| L1.1 | region 链，后继 region 带 Prev_Fail |
Σ region | a|b、ab|cd|ef、a|bc|def |
压平 | [ ] |
| L1.2 | 同上 + 公共后缀 | Σ region + 后缀 | (ab|[cd]|.)x |
压平 | [ ] |
| L1.3 | region + POP FAIL(Prev_Fail) + PACK SUCCESS(Prev_Success) |
region + 2 | (?<name>abc) |
压平 | [ ] |
| L1.4 | L1.3 且 region 内部是 ALT 链 | 嵌套 | (?<a>abcd|a(bc)c) |
压平 | [ ] |
| L1.5 | COUNT_COMPLEX + body |
CommandCount + 1 |
(ab){2,3} |
必需 | [ ] |
| L1.6 | COUNT_COMPLEX + body(含 ALT) + 线性后缀 |
嵌套 + 后缀 | (123(4|5)67){3,4}114514 |
必需 | [ ] |
| L1.7 | FIND_COMPLEX，CommandCount ≥ 0 |
CommandCount + 1 |
.*(ab|cd) |
必需 | [ ] |
| L1.8 | FIND_COMPLEX，CommandCount = -1 |
1 + region 剩余 | (?<name>.*)234 |
必需 | [ ] |
| L1.9 | FIND_SEQ / FIND_SET |
1 + region 剩余 | .*abc |
必需 | [ ] |
期望代码形状：L1.1/L1.2 压平为 if / else if / else 链；L1.3/L1.4 在 region 成功分支写捕获区间；
L1.5/L1.6 为计数循环包裹 body；L1.7–L1.9 为候选重试循环包裹 body（见下）。
CommandCount 必须按前缀化后的实际条数重算。
L1.5–L1.9 标记为必需，是因为它们的 body 都不是独立 region，L2 接不住，没有替代降级路径。
FIND 系的回溯语义
FIND 产出的不是一个位置，是一个按优先级排序的候选位置序列：
FURTHEST（贪婪.*）：从最远候选起，验证失败往前退NEAREST（惰性.*?）：从最近候选起，验证失败往后进
body 是候选的验证器。验证失败必须取下一个候选重来，候选耗尽才是真失败。
只做一次 LastIndexOf 就判定成败是错的——.*abcX 里最后一个 abc 后面没有 X 时，
必须退到倒数第二个 abc。
CommandCount = -1 的语义已被优化器坐实：TryReplaceDotStar 把 .* 直接产出
FindComplex(-1)，随后 TyrMergeFindRestTwice / TyrMergeFindRestTry 尽力把它收敛成确定长度，
收敛不掉的保持 -1，表示「body 是 region 剩余全部」。所以后端只需处理两种 body 长度：
确定值，和 -1。
FIND_SEQ / FIND_SET 没有 CommandCount 字段，语义等同 -1。只有当它恰好是 region
最后一条时才退化成单次搜索，此时消耗为 1。
期望代码形状：
int __bound = text.Length;
__ok = false;
while (true)
{
int __at = text[__cur..__bound].LastIndexOf("abc");
if (__at < 0) { __ok = false; break; } // 候选耗尽，唯一失败出口
int __save = __cur;
__cur = __cur + __at + 3;
// ── body / region 剩余指令内联展开在这里 ──
if (__ok) { break; } // 验证通过
__cur = __save;
__bound = __save + __at; // 退到前一个候选
}
FIND 与 POP 的冲突（必须处理）
POP 编译成 break 时跳出的是最近一层循环，而 FIND 的 while 比 region 的
do{}while(false) 更近。body 里的 POP 会跳出重试循环而不是 region，语义直接错。
不引入 goto 的解法是加一个 region 终结标志：
do // region N
{
bool __rN_done = false;
...
while (!__rN_done) // find retry
{
// 候选搜索
do // ← 隔离层，POP 的 break 落在这
{
// body，POP: __rN_ok = x; __rN_done = true; break;
} while (false);
if (__rN_done || __ok) { break; }
// 退候选
}
} while (false);
关注点：ALT 各 case 之间活动指针如何恢复、PACK 取哪一个成功结果作为捕获区间、
嵌套 FIND 会产生嵌套重试循环（复杂度是候选数的乘积，是灾难性回溯的来源）、
重试循环内 __ok 跨迭代被复写（Observe_Line 指向循环体内某条指令时，
读到的是最后一次迭代的值，当前前缀模型没有覆盖这个情形）。
L2 Region 级（正确性核心）
一次消耗 CommandCount + 1，即一个 TRY 归约出的完整 region。
决定作用域与失败复位策略，是所有嵌套结构的承载体。
| # | 触发窗口 | 消耗 | 覆盖样本 | 状态 |
|---|---|---|---|---|
| L2.1 | RegexTryIR + 其 body |
CommandCount + 1 |
(abc) |
[ ] |
| L2.2 | 同上，body 内含嵌套 region | 递归 | (a(bc)) |
[ ] |
| L2.3 | 单指令 region（被折叠的 TRY） | 1 | (a) |
[ ] |
期望代码形状：
__rN_begin = __cur;
__rN_ok = false;
do
{
// body，POP 在此 break
__rN_ok = __ok;
} while (false);
if (!__rN_ok) { __cur = __rN_begin; }
__ok = __rN_ok;
失败路径必须把活动指针复位到 region 入口。POP 直接编译为 break，不引入标签。
例外：当 region 内出现 FIND 系指令时，break 会被 FIND 的重试循环截获，
必须改用 L1 节里的 __rN_done 终结标志方案。
关注点：region 全部内联展开、嵌套 region 的指针复位链、break 只能跳出最近一层循环
（do{}while(false) 和 FIND 的 while 都算）。
L3 多指令定式（纯优化）
一次消耗 2–8 条，滑动窗口内的固定组合。全部属于代码质量优化，非正确性必需。 每条都必须能在窗口不匹配时干净地降级到 L4。
| # | 触发窗口 | 消耗 | 覆盖样本 | 状态 |
|---|---|---|---|---|
| L3.1 | FIND_COMPLEX FURTHEST COUNT:-1 + PACK + MATCH_SEQ |
3 | (?<name>.*)234 |
[ ] |
| L3.2 | 同上，锚点为单字符 | 3 | (?<name>.*)a |
[ ] |
| L3.3 | FIND_SEQ + MATCH_SEQ，把验证器折进搜索模式，消除回溯 |
2 | .*abc |
[ ] |
| L3.4 | MATCH_SEQ + COUNT_SEQ（a+、a{m,n} 展开形态） |
2 | a{3,5}、a+ |
[ ] |
| L3.5 | 连续 MATCH_SEQ / MATCH_SET，合流为单个 if 与表达式 |
2–8 | a[abc]d |
[ ] |
| L3.6 | 尾部 COUNT_SET .*，快速成功 |
1–2 | abc.* |
[ ] |
关注点：合并后失败诊断是否还能定位到原指令、合并是否破坏 Observe_Line 的行号引用。
L3.3 只有在合并后 region 剩余为空时才真正消除回溯，否则 L1.9 的重试循环仍然要保留。
L4 单指令级
一次消耗 1 条。这是调度链的兜底层，必须对每种 RegexIRCommand 都有实现。
| # | 指令 | 覆盖样本 | 状态 |
|---|---|---|---|
| L4.1 | MATCH_SEQ |
abc、\.、a\*b |
[ ] |
| L4.2 | MATCH_SET 离散 |
[abc]、[123abc]、[.] |
[ ] |
| L4.3 | MATCH_SET 范围 |
[1-9] |
[ ] |
| L4.4 | MATCH_SET 转义类 |
\w |
[ ] |
| L4.5 | MATCH_SET 任意字符 |
. |
[ ] |
| L4.6 | COUNT_SEQ |
a*、a? |
[ ] |
| L4.7 | COUNT_SET |
[abc]*、\w+、.{11,13}、[.]* |
[ ] |
| L4.10 | POP |
ALT 尾 | [ ] |
| L4.11 | PACK |
(abc) 默认序号组 |
[ ] |
L4.8 / L4.9 已移出本层。FIND_SEQ / FIND_SET 不存在单条形态——它们必须联动 region
剩余部分做候选重试，见 L1.9。只有 FIND 恰好是 region 末条时才退化成一次搜索，
那是 L1.9 的退化分支，不是独立的单指令生成器。编号保留空缺，避免打乱既有引用。
关注点：[.] 与 . 必须走不同后端语义；[.]* 不得被当作 .* 优化。
L5 前缀装饰（横切，消耗 0）
前缀不消耗 IR，而是包裹在 L1–L4 产出的代码外层。 这一层不实现，L1–L4 的产出就无法拼装成正确的控制流。
| # | 前缀字段 | 取值 | 生成形态 | 状态 |
|---|---|---|---|---|
| L5.1 | ExeCondition |
DEF |
无条件顺序执行 | [ ] |
| L5.2 | ExeCondition |
Prev_Success |
包裹 if (前驱成功) |
[ ] |
| L5.3 | ExeCondition |
Prev_Fail |
包裹 else / if (!前驱成功) |
[ ] |
| L5.4 | ExeCondition |
Always |
脱离条件链，始终执行 | [ ] |
| L5.5 | ObserveMethod |
NONE |
读紧邻前驱的隐式结果 | [ ] |
| L5.6 | ObserveMethod |
Observe_Line + ObserveSource |
读指定行结果槽 | [ ] |
| L5.7 | ObserveMethod |
Observe_Region + ObserveSource |
读指定 region 结果槽 | [ ] |
| L5.8 | PopCondition |
Pop_Success |
写回 region 成功并提前退出 | [ ] |
| L5.9 | PopCondition |
Pop_Fail |
写回 region 失败并提前退出 | [ ] |
| L5.10 | WorkingRegion |
任意 | 决定代码落入哪个 region 作用域 | [ ] |
关注点：Observe_Line 只读目标行结果，Observe_Region 只读目标 region 结果，
二者都不得退化成「读上一条」。行结果槽仅在被 Observe_Line 引用时才分配。
实现顺序
调度链按 L1 → L4 排列，但实现先拿正确性核心（L2/L4/L5），再补 L1 的必需项， 最后才是压平层（L1.1–L1.4 / L3）：
- L0 — 生成的空骨架能通过编译，
TextRegexSourceGen.GenFile的两处 TODO 闭合。 - L2.1 —
(abc)产出正确的do{}while(false)作用域与复位逻辑。 - L5.1–L5.3、L5.5 — 顺序与成功/失败链能拼装，此时 L2 的 region 才真正可用。
- L4 全部 — 兜底层补齐，任意线性表达式可端到端生成。
- L5.6–L5.9 — 跨行 / 跨 region 观察与提前退出，
a|b与(?<name>abc)自然跑通（嵌套形态）。 此时获得可运行基线，任何表达式都能生成正确代码。 - L1.5、L1.7–L1.9 — 复杂计数与 FIND 系，无降级路径，必须实现。
FIND 系要连带处理
POP与重试循环的break冲突。 - L1.1–L1.4 — 把 ALT 链与捕获组的嵌套形态压平。
- L3 全部 — 代码质量优化，可持续追加。
第一阶段验收口径（沿用原优先级）：MATCH_SEQ、MATCH_SET、COUNT_SEQ、COUNT_SET、
简单 ALT、PACK、FIND_COMPLEX COUNT:-1 全部稳定。
注：FIND_SEQ 已从原口径移除。TryReplaceDotStar 产出的是 FindComplex(-1)，
IROptimize 里没有 RegexFindSeqIR 的生成点，ngra-regex-ir.md 里写的
.*a → FIND_SEQ(a, last) 尚未落地。在生成点补上之前，L1.9 的 FIND_SEQ / FIND_SET
分支实际不可达，L3.3 也无从触发。
低优先级，暂不纳入 checklist：
- 逐 region 最短长度断言。
- 复杂字符集完全内联。
- 公共前缀提取和代码树生成。
- 对所有正则语义做完整兼容。
手写代码关注点
每个样本的手写代码都应尽量确认这些点：
- 活动指针如何推进。
- 失败时是否需要恢复活动指针。
- region result 和 single-line result 是否必须分配。
Observe_Line是否只读取目标行结果。Observe_Region是否只读取目标 region 结果。PACK使用哪一个成功结果作为捕获区间。- 最小长度检查是否值得在当前样本中生成。
- 本形态消耗几条 IR，落空时降级到哪一层。
- 前缀的执行条件与观察源是否被正确外提，而不是硬编码进指令主体。
已手写样本索引
test/SingleFile/regex.cs 中已有的样本与层级对应：
| 函数 | 表达式 | 对应层级 |
|---|---|---|
Match_ABC |
abc |
L4.1 |
Match_A_charset_ABC_C |
a[abc]d |
L3.5 / L4.1 / L4.2 |
Match_charset_ABC |
[abc] |
L4.2 |
Match_Dot |
. |
L4.5 |
Match_A_3_5 |
a{3,5} |
L3.4 |
Match_AB_2_3 |
(ab){2,3} |
L1.5 |
MatchDiffCase |
(ab|[cd]|.)x |
L1.2 |
MatchCountAnyGroup |
(?<name>.*)x |
L3.1 |
待补：L2.1 (abc)、L1.1 a\|b、L1.3 (?<name>abc)、L5 各前缀组合的最小样本。
其中 L5 的样本最关键：需要分别写出 Prev_Success / Prev_Fail 包裹、
Observe_Line / Observe_Region 读取、Pop_Success / Pop_Fail 写回三组最小代码形状。
综合验收样本
a*.[abc]*(?<a>abcd|a(bc)c)(?<name>.*)234
覆盖 L1.1、L1.3、L1.4、L3.1、L4.6、L4.7，作为全链路收口用例，最后再手写。