Home | 性能 | 源码位置追踪

本文仍在一个 md内完成：前半部分是正文，只证明当前 full-parse 实现的复杂度命题；后半部分是同文附录，用来保留实现走查、分支矩阵、历史路径、经验常数与增量解析。这样既不把材料拆页，也把证明对象、证明边界与工程注记分开。

正文只证明两个命题，并且只针对当前实现的正常全量解析入口。

命题 S（parseStructural）

T_parseStructural(n) = Θ(n)

命题 R（parseRichText，库内部分）

T_parseRichText, library-owned(n) = Θ(n)

如果把用户 handler 自己追加的工作也并入总时间，则本文不把它偷写成库的结论，而是明确写成：

T_parseRichText,total(n) = Θ(n + T_user-handlers(n))

1. 输入规模：n = text.length，按 UTF-16 code units 计。
2. 证明对象：parseStructural(text, options) 与 parseRichText(text, options) 的正常 full-parse 入口；不包含 parseIncremental(...)、session.applyEdit(...)、session.applyEditWithDiff(...)。
3. 当前实现边界：正文命题只针对当前 structural / render / ownership / EOF recovery 实现成立；历史实现与版本演化全部移到附录，不在正文里与主命题混写。
4. render 命题边界：parseRichText 的正文结论只统计 library-owned render work，也就是 parser 产出的 structural tree 上、由库自身完成的遍历、materialize、degrade、trim、buffer 与 token 组装。
5. 显式排除项：用户 handler.inline/raw/block 函数体内部的复杂度、用户手工构造并注入的高度重叠外部树、以及调用方主动制造的额外输出膨胀，不被伪装成库的 Θ(n) 保证。

在这个边界内，正文要做的事只有四步：给出成本分解，给出当前实现维持这些成本项线性的原因，闭合 parseStructural 的 Θ(n) 上界与下界，再把同样的边界推广到 parseRichText。

下面不再沿着“分支表”叙述，而是直接给出正文使用的成本分解。目标是把库内工作拆成可求和的量，并说明这些量为什么不会对同一段源码发生无界重计。设输入源码长度为 n = |source|。

记：

• N_iter：while (stack.length > 0) 主循环总迭代次数；
• B_skip：findNextBoundaryChar(...) 推进掉的普通文本总字节数；
• B_escape：按 escape / literal-text 分支被消费的总字节数；
• B_head：tag head / end tag / separator / shorthand 头部识别时扫描到的总字节数；
• B_form：findTagArgClose(...) 这类 form-classification 扫描到的总字节数；
• B_close：raw / block close finder 扫描到的总字节数；
• B_probe：ownership 判定、ancestor owner 比较、close 归属 probe 触达的总字节数；
• B_replay：EOF malformed-inline recovery 中 replay / downgrade / attach child 涉及的总字节数；
• N_frame：parse frame 的创建/弹出/父子连接总次数。

那么 structural 阶段可先写成：

T_structural(n)
  = c0·N_iter
  + c1·B_skip
  + c2·B_escape
  + c3·B_head
  + c4·B_form
  + c5·B_close
  + c6·B_probe
  + c7·B_replay
  + c8·N_frame

关键不是把式子写出来，而是要证明这些项各自都不会在“同一段源码上反复失控重扫”。

findNextBoundaryChar(...) 负责把当前 frame 中连续的普通文本一口气跳过。不同迭代跳过的区间在源码坐标上互不重叠，因此：

B_skip = Σ length(skipped_run_i) <= n

escape 分支要么把 escapeChar + nextChar 当作一对消费掉，要么把当前字符按普通文本消费。无论哪种情况，frame.i 都前进，而且已消费的源码字节不会在同一 frame 上被 escape 分支重新消费，因此：

B_escape = Σ length(escape_chunk_i) <= n

B_head 看上去最容易被质疑，因为它包含 tag head、end tag、separator、shorthand 这些“看起来会反复试探”的路径。但这里真正能求和的是：

1. 成功识别的头部，本来就只对应源码里真实存在的某一段头部；
2. 失败识别的头部，在当前实现里失败后要么立即退化成 text，要么推动 frame.i 越过当前决策点，不会无限停在同一个 head 起点上反复完整重扫；
3. 当前 shorthand ownership 被拆成 push / close 两个方向，probe 不再把同一串 tail 在多个 frame 之间来回完整重判。

引理 H（head-attempt charging）. 对任意源码位置 p，它被计入 B_head 的次数受常数上界约束。

证明思路不是说“看起来不会重扫”，而是把一次 head-attempt 之后允许发生的事件类固定为有限个：

1. 识别成功。 该 head 区间随即归属于一个已创建的结构（full tag / shorthand child / end-tag-like dispatch），当前帧不会再以同一角色对同一起点做无限次完整尝试；
2. 识别失败并前进。 当前尝试失败后，要么立即退化成 text，要么使 frame.i 推进到严格更大的位置，因此同一 frame 不会永久停在同一 head 起点反复试探；
3. 恢复性 replay。 某个失败帧的 tag head 可能在 recovery 路径中被 replay 回父帧，但 replay 的对象只是一段失败帧 head，而且每个失败帧的 head 最多进入一次这样的 replay 计费。

因此，对每个位置 p 而言，它至多被 charge 到有限个事件类：一次来自正常识别/失败判定，外加常数次恢复性 replay；不存在“同一 offset 在无界多个 head-attempt 中反复完整计费”的路径。于是：

B_head <= C_head · n = O(n)

因此可把 B_head 理解为若干 head-scan 的总和，而每个 head 起点只会触发常数次有限长度扫描：

B_head = Σ length(head_scan_i) = O(n)

B_form 单独计 findTagArgClose(...) 这类 form-classification 扫描，而不再把它混进 B_close。原因很简单：它的语义不是“寻找 raw/block 的关闭位点”，而是“对一个新出现的 head 做一次 form 判定”。

更精确地说，每次 findTagArgClose(...) 都绑定到“某个新 head 的判型”这一事件：

1. 成功时，该 head 直接进入相应结构创建流程；
2. 失败时，该 head 要么退化、要么使当前 frame 前进；
3. 当前实现下，同一 frame 不会把同一起点无界次重新发起新的 form-classification window。

因此：

B_form = Σ length(form_scan_i) = O(n)

这里不能把所有扫描都笼统叫成“close-search”然后一句话带过。正文里真正要区分的是扫描族：

1. findRawClose：用于 raw 内容窗口的关闭搜索；
2. findBlockClose：用于 block 内容窗口的关闭搜索；其内部虽然维护 depth / nested-state，但对单次搜索窗口而言扫描指针仍单调前进；
3. shorthand ownership probe：不并入 B_close，而并入 B_probe，避免把不同扫描族偷并成一个量。

引理 C（close-scan family charging）. 对 findRawClose / findBlockClose 这两类关闭扫描，任一给定窗口都不会在同一父 frame 语境下被无界次重新发起完整搜索。

对应地：

• 对一次成功或失败的 findRawClose 搜索，内部扫描指针在目标 raw 窗口上单调前进；搜索结束后，要么得到 close 并令父帧推进到 nextI，要么退化当前结构，不会在同一父 frame 下对同一 raw 窗口无界次重开完整搜索；
• 对一次成功或失败的 findBlockClose 搜索，虽然内部会管理 block depth、跳过内层 raw / inline 区段，但该次调用内部的扫描指针在其检查窗口上仍单调前进；当前实现不会把同一 block 窗口在同一父 frame 下无界次重新发起完整搜索；

因此，B_close 的线性性不是“相信我它们都差不多”，而是“对 raw/block close 这两类真正的 close finder，各自都满足窗口级单调前进 + 无无界重发”的 charging 条件。于是：

因此：

B_close = Σ length(close_scan_i) = O(n)

这里先不给“摘要型证明”，只给 recovery 闭合所需的三座桥；真正有证明作用的是后文支撑引理里的：

1. E1：resolveShorthandOwnershipPush(...) 的 probe 为什么是摊还线性的；
2. E2：close 位点的 defer-parent 为什么是一次性降级，而不是把同一尾部整段回退多轮；
3. E3：EOF malformed-inline replay 为什么只额外引入一次恢复性重扫。

ancestorEndTagOwnerIndex、buildMalformedInlineReplayPlan(...)、replayMalformedInlineChainAtEof(...) 与 downgradeInlineIntoParent(...) 在这里的角色，是共同保证 E1/E2/E3 可以成立；正文此处不把这三座桥再压扁成一句“总之修好了”。

因此新实现中的恢复项更接近：

T_new-recovery(m)
  = Θ(number_of_frames)
  + Θ(total_replayed_head_bytes)
  + Θ(total_child_attach_ops)

而这三项都只对每个 frame / 每段 replay 头部 / 每个 child attachment 计一次，所以可合并进：

B_probe + B_replay = O(n)

更直白地写，就是：

T_new-recovery(m) = Σ Θ(1) + Σ replay_bytes_i + Σ attach_i = O(m) <= O(n)

这给出了当前实现中恢复项仍可并入线性上界的公式化来源。

把上面几项收束起来：

T_structural(n)
  = c0·N_iter
  + c1·B_skip
  + c2·B_escape
  + c3·B_head
  + c4·B_form
  + c5·B_close
  + c6·B_probe
  + c7·B_replay
  + c8·N_frame

而我们已经有：

N_iter  = O(n)
B_skip  <= n
B_escape <= n
B_head  = O(n)
B_form   = O(n)
B_close = O(n)
B_probe = O(n)
B_replay = O(n)
N_frame = O(n)

于是存在常数 C_s > 0，使得：

T_structural(n) <= C_s·n

再加上 structural 至少要读过输入中的边界相关字符、至少要完成与节点/frame 数同阶的基础工作，因此下界不是 o(n)，可写成：

T_structural(n) = Θ(n)

设：

• N_render_iter：render 显式栈主循环迭代次数；
• B_textbuf：bufferText(...) / flushTextBuf(...) 触达的 text-like 总字节数；
• B_raw_unescape：renderRawNode(...) 中 unescape raw content 时扫描到的总字节数；
• B_materialize：unknown tag passthrough / degrade 路径里被 materialize 成 TextToken[] 的总 token/字节量；
• B_trim：trimBlockBoundaryTokens(...) 等 trim helper 处理的总 token/字节量；
• N_dispatch：inline/raw/block/text/comment 节点分发总次数；
• T_user-handlers(n)：在长度为 n 的本次输入上，用户 handler 函数体内部自己做的额外工作。

则 render 侧可写成：

T_render(n)
  = d0·N_render_iter
  + d1·B_textbuf
  + d2·B_raw_unescape
  + d3·B_materialize
  + d4·B_trim
  + d5·N_dispatch
  + T_user-handlers(n)

这里必须把库内工作与用户 handler 体内工作分开，否则“Θ(n)”会被偷换概念。

1. N_render_iter = O(number_of_nodes) = O(n)：每个 structural node 只会被压栈/弹栈并分发有限次；
2. B_textbuf = O(n)：text-like 内容进入 buffer、flush 成 token，不会无界次重复拼接同一段源码对应的库内文本；
3. B_raw_unescape = O(n)：renderRawNode(...) 对 raw content 的 unescape 是单次顺扫，lazy parts 分配只影响常数；
4. B_materialize = O(n)：materializeTextTokens(...) 对同一 TextToken[] 的完全 materialization 只发生有限次；当前实现用“已 materialized 集合”避免对同一个数组对象反复完整展开；
5. B_trim = O(n)：trim 处理的只是 block 边界 token，累计规模受库内 token 总量约束。

于是，在只统计 library-owned work 时，有：

T_render, library-owned(n)
  = d0·N_render_iter
  + d1·B_textbuf
  + d2·B_raw_unescape
  + d3·B_materialize
  + d4·B_trim
  + d5·N_dispatch
  <= C_r·n

从而：

T_render, library-owned(n) = O(n)

而 render 至少也要遍历节点/输出 token 的线性规模部分，因此在库内输出规模与输入同阶这一正常前提下，可写成：

T_render, library-owned(n) = Θ(n)

因此真正完整、而不是口号式的总公式应写成：

T_parseStructural(n) = T_structural(n) = Θ(n)

T_parseRichText, library-owned(n)
  = T_structural(n) + T_render, library-owned(n)
  = Θ(n) + Θ(n)
  = Θ(n)

如果把用户 handler 自己的复杂逻辑也算进去，则更准确的写法只能是：

T_parseRichText,total(n) = Θ(n + T_user-handlers(n))

这也是为什么本文必须不断强调 library-owned Θ(n)： 不是为了回避问题，而是为了把“库保证的线性部分”和“调用方自己追加的复杂度”严格拆开。

为了避免把同一个 Θ(n) 读成“两套并列证明”，这里把正文的依赖关系先固定下来：

1. 主证明主线是前一节的 charging scheme，也就是把 T_structural(n) 与 T_parseRichText, library-owned(n) 写成若干可求和成本项之和；
2. 下文不是第二套独立证明，而是专门用来证明这些成本项分别满足 O(n) 的支撑引理体系；
3. 闭合动作只有一次：把下文得到的各项上界代回前一节总公式，得到最终的 Θ(n) 结论。

更具体地说，下文各组引理与前文记号的对应关系是：

• I₁ + 主循环迭代分析：支撑 N_iter = O(n)，并支撑源码消费类项不会发生无界重叠；
• 辅助扫描覆盖引理 + 分支级分析：支撑 B_form = O(n) 与 B_close = O(n)，并与 B_head = O(n) 一起闭合 structural 扫描项；
• 恢复开销引理：支撑 B_probe = O(n) 与 B_replay = O(n)；
• render 侧的线性求和说明：支撑 T_render, library-owned(n) = O(n)。

因此，正确阅读顺序不是“前半证明一次、后半再证明一次”，而是：

charging scheme
  -> support lemmas for each charged term
  -> substitute bounds back into the total formula
  -> close the theorem

"每个字符只扫一次"这个直觉需要更紧的表述。以下是直接从源码推导的证明框架。

对当前实现，更准确的说法应拆成两层：

1. 源码消费层面：成功帧对源码位置的消费仍可做线性划分证明；
2. 主循环分支层面：真正进入分支树的迭代，主要只发生在边界位置；非边界文本 run 会被批量 appendBuf(...)。

因此，下文的任务不是重新给出另一套总证明，而是把前文 charging scheme 中各个成本项所需的上界逐项补齐；阅读时要把"字符消费"和"分支树入口"分开理解。

structural parser（parseNodesWithFactory，structural.ts 第 624 行起）维护一个显式 stack: ParseFrame[]。主循环 while (stack.length > 0) 的每次迭代恰好做以下之一：

1. 帧完成 — frame.i >= frame.textEnd：弹栈（不消费字符）。
2. 字符消费 — 所有其他分支：frame.i 至少前进 1。

定义。 称一个帧 f 为 成功帧，如果 f 通过 A2 路径完成 （flushBuffer + stack.pop() + completeChild，structural.ts 第 648–652 行）， 而非通过 A1 错误恢复（INLINE_NOT_CLOSED / SHORTHAND_NOT_CLOSED，第 629–646 行）被弹出。 根帧（returnKind === null）始终通过 A2 完成。

定义。 帧 f 的 消费区间 为 f 在主循环的字符消费型迭代中实际扫过的 [f.startPos, f.endPos) 区间（startPos = f.i 的初始值，endPos = f 完成或被弹出时 f.i 的值）。

不变量 I₁ 陈述。 在 parseNodesWithFactory 执行结束时，所有成功帧的消费区间 构成 [0, n) 的一个划分——即 (a) 并集 = [0, n)，(b) 两两不相交。

对主循环的迭代总次数 T 做强归纳。

基础情况 (T = 1). 输入为空字符串（n = 0）。根帧创建后 frame.i = 0 = textEnd， 立刻触发 A2 完成。唯一的成功帧消费区间为 [0, 0) = ∅，与 [0, 0) 一致。

归纳步骤。 假设对所有 T′ < T 次迭代的执行，I₁ 都成立。考虑第 T 次迭代到来时 栈顶帧 frame 进入哪个分支。以下逐一分析 8 个分支（A–H）对消费区间划分的影响：

(A) 帧完成 — frame.i >= frame.textEnd（第 628–652 行）。

• A1（未闭合 inline 错误恢复，第 629–646 行）： frame 不是成功帧，其消费区间 被丢弃。appendBuf(parent, frame.tagStartI, frame.argStartI) 把标签头文本 追加到父帧缓冲区；parent.i = frame.argStartI 使父帧从 argStartI 继续扫描。 这意味着 frame 曾扫过的 [argStartI, textEnd) 区间将被父帧（或其后续子帧） 重新扫描。由于 frame 本身不是成功帧，这一重叠不违反 I₁。但它引入了额外迭代—— 见下文 错误恢复开销。

• A2（正常完成，第 648–652 行）： frame 是成功帧。completeChild 把 parent.i 设为子帧消费区间的右端点：

  • inline：parent.i = closeStart + child.inlineCloseWidth（第 370 行）。完整 DSL inline 时 inlineCloseWidth = endTag.length；简写正常关闭时 inlineCloseWidth = tagClose.length。若与 full-form close 竞争，简写不会以 width=0 关闭，而是走 ownership 让步（降级并回到 argStart 重扫）。
  • rawArgs / blockArgs / blockContent：parent.i 在相应的 push 路径中已被设定 为 nextI（第 751、813 行），或子帧的 [contentStart, closeStart) 天然 不超出父帧所设的 textEnd。

  因此父帧在子帧完成后从子帧消费区间的右端继续，不重叠也不遗漏。

(B) 转义序列（第 659–672 行）。 frame.i = next，其中 next > i（readEscapedSequence 至少前进 1）。单帧内前进，无帧操作， 不影响区间划分。

(C) inline 帧的 argClose 检测（第 675–836 行）。 仅在 inlineCloseToken !== null 的帧中触发。帧模型使用两个字段——inlineCloseToken（关闭本帧的 token）和 inlineCloseWidth（关闭时消费的源码字符数）。子分支：

• C1（简写帧，inlineCloseToken === tagClose，第 678–684 行）： 先做同位点 ownership 判优：若当前位置是父级 full-form endTag，则简写让步并降级； 否则再按 startsWith(tagClose, i) 关闭简写帧： inlineCloseWidth = tagClose.length，flushBuffer + stack.pop() + completeChild。 仍为单次同位点判定，不做逐层前扫。

• C2（完整 DSL 帧，endTag 匹配 → inline 关闭，第 689–695 行）： startsWith(endTag, i) → inlineCloseWidth = endTag.length，flushBuffer + stack.pop() + completeChild。completeChild 设 parent.i = closeStart + inlineCloseWidth。

• C3（rawOpen )% 匹配，第 698–752 行）： 找到 raw 关闭后， parent.i = nextI（第 751 行），nextI = closeStart + rawClose.length。 子帧消费 [argStart, argClose)，raw 内容区间 [contentStart, closeStart) 不由任何帧按字符消费（直接作为字面量传给 factory.raw）。父帧跳过整个结构。 若 findRawClose 返回 -1（第 705 行），退化路径把整段标签头 + rawOpen 当文本， parent.i = contentStart。

• C4（blockOpen )* 匹配，第 760–815 行）： 类似 C3。 parent.i = nextI = closeStart + blockClose.length（第 813 行）。 push 一个 blockContent 子帧，其 textEnd = closeStart，与父帧不重叠。

• C5（普通 ) 后无识别后缀，第 835 行）： frame.i += tagClose.length。 单帧内前进。

(D) 非 inline 帧的意外 endTag（第 841–845 行）。 frame.i += endTag.length。纯文本消费，单帧内前进。

(E) 管道分隔符（第 850–858 行）。 frame.i += tagDivider.length。仅在 insideArgs 帧中触发。单帧内前进。

(F) 无标签匹配 / 普通字符（第 862–870 行）。 当 readTagStartInfo 返回 null 时：

• 若帧为 inline（inlineCloseToken !== null），尝试 readInlineShorthandStart。 如果简写匹配成功且 gating 允许，tryPushInlineShorthandChild push 一个 inlineCloseToken = tagClose、implicitInlineShorthand = true 的子帧——与 H1 的 push 语义相同，但用于简写形式。若无简写匹配，落入下方。
• 否则：appendBuf(frame, i, i + 1)，frame.i++。 这是最简单的分支——消费 1 个字符。

(G) 深度限制退化（第 876–890 行）。 frame.i = degradedEnd，其中 degradedEnd = skipTagBoundary(…) 返回标签边界 之后的位置。单帧内跳过整个标签头。不 push 子帧。

(H) 识别到标签头，确定形态并分发（第 862–1060 行）。

• H1（在 inline 帧内检测到嵌套标签，第 892–918 行）： 当在 inline 帧内（inlineCloseToken !== null）检测到完整 DSL 标签头时：

  • 当前实现不会在这里对简写帧做 inlineCloseWidth = 0 关闭。 竞争判优发生在 close 位点（分支 C1/C2），而不是“看到标签头就关闭简写”。
  • tryPushInlineChild 成功 → push 子帧（child.i = argStart， child.textEnd = frame.textEnd）。不调用 getTagCloserType。 父帧的 frame.i 不前进——由子帧接管。子帧完成后通过 completeChild 设 parent.i。 若 tryPushInlineChild 被 gating 拒绝 → 标签头通过 skipTagBoundary 跳过， 当文本处理。

• H2（非 inline 帧，getTagCloserType 返回 null，第 923–941 行）： 即 findTagArgClose 在源码中找不到匹配的 )。整个标签头退化为文本： appendBuf(frame, i, info.argStart)，frame.i = info.argStart。 frame.i 前进了至少 1（info.argStart > i，因为标签名至少 1 字符 + (）。

• H3（inline 形态 closerInfo.closer === endTag，第 938–952 行）： 同 H1 的 push 逻辑。

• H4（raw 形态，第 946–995 行）： findRawClose 定位关闭标记。 frame.i = nextI（第 988 行），push rawArgs 子帧。rawArgs 子帧的 textEnd = argClose，与父帧的后续区间不重叠。

• H5（block 形态，第 998–1060 行）： 类似 H4。 frame.i = nextI（第 1046 行），先 push blockArgs 子帧（textEnd = argClose）， 后续 blockContent 子帧（textEnd = closeStart）。所有子帧区间均不超出父帧的 textEnd。

综合。 在上述所有分支中：

• push 子帧时，子帧的 [startPos, endPos) 始终是父帧尚未消费的子区间；
• 子帧完成后，completeChild 或 push 路径把 parent.i 设到子帧区间之后；
• 因此父帧和成功子帧的消费区间不重叠且无间隙。

根帧从 0 开始、textEnd = n。所有成功帧的消费区间构成 [0, n) 的划分。 ∎

注意。 此证明不涵盖 findTagArgClose / findBlockClose / findInlineClose 等辅助边界扫描——它们在主循环之外额外访问源码。辅助扫描的复杂度单独分析， 见 辅助扫描覆盖引理 一节。

这一节必须和 1.4.4 的 changelog 一起读，因为这里正是本次补丁版真正修掉的复杂度逃逸口。

在 1.4.4 之前，最危险的不是正常 inline 嵌套，而是损坏 shorthand / 未闭合 inline 链在 ownership 冲突和 EOF 恢复里形成的“逐帧弹出 → 回到父帧 → 再进主循环 → 再发现下一层也坏了” 的重入模式。那条路径的坏处不在于某个单一分支本身很重，而在于：同一段剩余 suffix 会沿着 嵌套链被重复带回主循环，于是工作量可以形成

k + (k - 1) + (k - 2) + ... + 1

这样的三角级数，总量为 O(k²)。1.4.4 的价值就在于把这条恢复链上的两个关键放大器同时拆掉：

1. 祖先 full-form close owner 现在显式携带在帧上。 ParseFrame.ancestorEndTagOwnerIndex 使 shorthand 在 push / close 两条路径上都能 O(1) 拿到最近的祖先 endTag owner，不再需要靠“退回父帧后重新观察同一 close 位点”来间接找 owner。
2. EOF 未闭合 inline 链现在先整体规划，再整体弹栈。 buildMalformedInlineReplayPlan(...) 先算出整条 malformed chain， replayMalformedInlineChainAtEof(...) 再一次性 emit error、一次性 pop，并且只做一次恢复性重扫。

也就是说，1.4.4 之后错误恢复的正确读法不再是“每一层都可能把尾巴重新拖回主循环”，而是：

• push 时能拒绝的 shorthand，直接在 push 时拒绝；
• close 位点要让位给祖先 full-form close 的 shorthand，直接在 close 位点降级；
• 到 EOF 才确认整条链都未闭合的情况，整链一次性 replay；
• 不会再出现按链长逐帧重入主循环的 N² 放大。

下面把这三种恢复路径分开分析。

tryPushInlineShorthandChild(...) 现在不再调用旧的统一 resolveShorthandOwnership(...)，而是 直接委托给 resolveShorthandOwnershipPush(...)（structuralOwnership.ts）。

该函数做的事可以拆成三层：

1. O(1) owner 快速判定

   • 如果当前父帧自己就是 full-form owner，且 argStart 与同位点 endTag 完全重叠，直接 defer-parent；
   • 如果最近祖先 owner 在该位点可匹配 endTag，也直接 defer-parent。

2. 仅在当前帧本身是 full-form owner 时，才做 forward probe

   • 从 argStart 向右扫描；
   • 遇到 escape 序列则整段跳过；
   • 遇到完整 DSL tag head 则停止，结论为 reject = false；
   • 遇到 tagClose 则停止，再检查该位点是不是 endTag 的起点。

3. probe 结果缓存到 shorthandProbe

   • 缓存键不是“全局位置”，而是“同一帧、同一 textEnd 版本下的 [startI, boundaryI] 探测窗口”；
   • 后续 shorthand 候选只要 argStart 仍落在该窗口内，就直接复用，不重跑整段前探。

因此，这条路径的关键不是“单次 probe 可能扫多远”，而是：同一窗口不会反复重建。 对固定帧、固定 textEnd 而言，某个源码位置要么：

• 被 probe 第一次扫到并写入缓存窗口；
• 要么后续直接由 currentProbe 复用命中。

所以 push 阶段 ownership 前探的总代价是“所有首次建窗 probe 长度之和”，属于线性摊还， 而不是“每遇到一个 shorthand 候选都从头再扫一遍尾巴”。

1.4.4 另一个真正关键的变化在 downgradeInlineIntoParent(...)。

当前实现的语义是：

1. flushBuffer(frame)：先把子帧里尚未落地的文本刷出；
2. appendBuf(parent, frame.tagStartI, frame.argStartI)：把 shorthand / inline 的 tag 头回退成父帧文本；
3. flushBuffer(parent)：把父帧当前文本状态固定下来；
4. appendNodesWithMergedText(parent.nodes, frame.nodes)：把已经在子帧里解析出来的正文节点直接挂回父帧；
5. parent.i = nextParentI：父帧直接从当前 close 位点之后继续。

这一步和旧的“回到 argStartI 再把整段尾巴重扫一遍”有本质区别：

• 旧读法：失败子帧之前解析出来的内容白做，父帧回退后再重新解析整段 suffix；
• 新读法：失败子帧的 tag 头退回文本，但其内部已经确认的子节点被保留并上挂，父帧只从 nextParentI 继续。

因此，每个发生 defer-parent 的 shorthand / inline 子帧：

• 最多被降级一次；
• 一旦降级就立即出栈，不会再次作为活跃帧参与 ownership 竞争；
• 已经产出的 frame.nodes 只会被 appendNodesWithMergedText(...) 搬运一次。

设一次 parse 中发生降级的帧数为 m_deg，被上挂节点总数为 N_deg_nodes，则这条路径的工作量满足：

T_defer-parent = O(m_deg + N_deg_nodes)

而 m_deg ≤ O(n)、N_deg_nodes ≤ O(n)，所以 close 位点 ownership 让步的总成本是 O(n)。

tryFinalizeFrameAtEof(...) 在 frame.inlineCloseToken !== null 时，不再按“当前帧报错 → 弹一帧 → 回主循环” 的模式处理，而是直接调用 replayMalformedInlineChainAtEof(frame)。

这条路径可以拆成三个阶段：

1. 建 replay plan

   • buildMalformedInlineReplayPlan(startFrame, getFrameByParentIndex) 只沿 parentIndex 链向上走；
   • 它不扫描源码字符，只遍历当前活跃帧链；
   • 因此成本是 O(h)，其中 h = 当前 malformed inline 链的长度。

2. 整链 emit + pop

   • replayPlan.chain 里的每一帧发一条错误；
   • 然后逐帧 stack.pop()；
   • 这一步同样只和链长成正比，仍是 O(h)。

3. 单次恢复性重扫

   • 如果上方存在第一个非 inline 容器，当前实现只把 replay plan 里最外层那一个 tag 头回退成文本： appendBuf(parent, resumeTagStartI, resumeArgStartI)；
   • 然后令 parent.i = resumeArgStartI；
   • 之后父帧继续主循环。

关键点就在这里：整条 malformed chain 只触发一次恢复性重扫。

EOF 在一次 parse 调用里只会到达一次，因此这种“从 resumeArgStartI 再扫一次剩余 suffix” 的成本上界就是：

T_eof-rescan ≤ parent.textEnd - resumeArgStartI ≤ n

它不再乘上链长，也不再形成

k + (k - 1) + ... + 1

那种逐帧重入的平方级累加。

对任意一次 parseNodesWithFactory(...) 调用，inline / shorthand ownership 与 EOF 恢复引入的额外工作量满足：

T_recovery-extra(n)
    = T_probe + T_defer-parent + T_replay-plan + T_eof-rescan
    ≤ O(n) + O(n) + O(h) + O(n)
    = O(n)

其中 h 为 EOF 时 malformed inline 链长度，且 h ≤ 当前活跃帧数 ≤ O(n)。

证明要点。

• T_probe：来自 resolveShorthandOwnershipPush(...) 的首次建窗 probe，总长度线性摊还；
• T_defer-parent：每个发生让步的子帧只降级一次，已产出节点只上挂一次；
• T_replay-plan：只沿父指针链走，不扫描源码；
• T_eof-rescan：EOF replay 后只恢复一次，不按链长重复恢复。

故 inline / shorthand 错误恢复不再带来平方级重入。 ∎

对 parseNodesWithFactory 的主 while 循环而言，1.4.4 之后应分四项计数：

1. 成功帧的源码消费型迭代 ≤ n

   • 由不变量 I₁ 直接给出。

2. 非边界文本 run 的批量追加总长 ≤ n

   • 1.4.3 起，普通文本不再逐字符穿过整棵分支树；
   • 但所有 run 长度求和仍然受源码总长上界约束。

3. ownership / downgrade / EOF replay 的额外工作 ≤ c_err · n

   • 由上面的引理 E₁ 给出；
   • 这里的 c_err 是实现相关常数，不再需要写成 2^D 这一类“逐层重入”的放大项。

4. 帧完成 / push / pop / 节点挂接等栈操作 ≤ O(帧数) ≤ O(n)

   • 每个帧至少对应一个标签头或一个已识别结构片段；
   • 入栈、出栈、completeChild(...)、appendNodesWithMergedText(...) 都只对这些帧做线性次操作。

因此主循环与恢复逻辑合并后的上界可以写成：

T_loop(n) ≤ c_scan · n + c_err · n + c_stack · n
         = C_loop · n

其中 C_loop 与实现常数、语法密度、输入形状有关，但与 n 无关。

对良性输入，c_err 接近 0； 对命中 1.4.4 旧坏路径的损坏输入，c_err 仍然是常数，而不再随嵌套链长形成乘法放大。

root / block 级帧在 Branch H 中调用 getTagCloserType，后者调用 findTagArgClose 来判定标签形态。与此同时，1.4.4 之后还需要把 shorthand ownership 的 probe 一并纳入辅助扫描分析； 否则“主循环线性，但 probe / replay 可能偷偷放大”这个问题就没有被完整回答。

因此，本节把辅助扫描拆成两类：

1. root / block 级 form 判定扫描：findTagArgClose、findBlockClose、findRawClose
2. inline shorthand ownership 扫描：resolveShorthandOwnershipPush(...) 里的 forward probe

引理 A₁。 对一次完整 parse，辅助扫描总量满足：

T_aux(n) = T_form-scan(n) + T_shorthand-probe(n) ≤ c_aux · n

其中 c_aux 与语法和输入形状有关，但与 n 无关。

证明要点。

• findTagArgClose / findBlockClose / findRawClose 仍只在 root / block 级形态判定路径中调用； inline 子帧不会对每一层嵌套都重新跑一遍 form 判定。
• 成功的 form 判定之后，要么子帧消费该区间，要么父帧直接把 i 跳到 nextI； 这些扫描区间会被后续消费 / 跳过逻辑吸收，不会在同一层无限回退。
• shorthand ownership probe 已在引理 E₁ 中证明为线性摊还：每个 (frame, textEnd) 窗口首次建窗后即缓存复用。
• 1.4.4 之前那种“辅助扫描本身不重，但会和逐帧 replay 相乘” 的 N² 放大器已经消失； 现在它们只和主循环形成加性组合，而不再形成乘性放大。

因此辅助扫描总量仍可写成 c_aux · n。 ∎

对 1.4.3+ 实现，这一节需要拆成三类成本：

1. 边界位点的分支树成本

   • 每次真正进入分支树时，执行一组固定的 startsWith / 比较级联；
   • 默认语法下最坏情况仍可用 k ≈ 15 次定长 token 检查来估算。

2. 非边界文本 run 的批量追加成本

   • appendBuf(...) 不应再简单写成"每次 O(1)"；
   • 更准确地说，单次 appendBuf 的成本是 O(run length)，其中 run length = 从当前 i 到下一个边界的距离；
   • 但所有非边界 run 的长度总和在良性输入下仍 ≤ n，因此总成本仍线性。

3. 辅助扫描与缓存成本

   • 非 inline 帧的 form 判定仍可能触发 findTagArgClose 前扫；
   • 1.4.3 起，大窗口会走 getTagCloserTypeWithCache(...)，缓存生命周期仅限单次 parse 调用；
   • 转义 token 集合按 SyntaxConfig 做 WeakMap 缓存，并按首字符分桶；因此首个新 config 会付一次初始化成本， 后续同一 config 的转义尝试更接近 O(同首字符候选数)。

因此，structural 的总工作量不能简化成"每个字符恰好只访问一次"；更准确的是：

• 成功帧消费 + 非边界批量追加 = O(n)
• root / block 级辅助扫描 = O(n) 摊还
• 额外缓存只改变常数，不改变上界

组合三个部分，可写成：

T_structural(n) ≤ k · n + s · n
                = C₁ · n

其中：

• k 表示主循环单字符分支预算（默认语法下经验上约为 3–15）。
• s 表示 root / block 级 form 判定、block/raw 关闭边界搜索等辅助扫描带来的摊还常数。

因此 C₁ = k + s 是一个与实现和输入形状有关、但与 n 无关的常数。

render 层的核心遍历（renderNodes）对每个 IndexedStructuralNode 恰好访问一次。 若 handler 进一步调用 materializeTextTokens，则在 WeakSet 命中去重的前提下， 每个同引用的 TextToken[] 数组对象至多被完整物化一次。

在固定 handler 实现且单次 handler 输出规模受输入线性约束时，有 nodes ≤ O(n)、tokens ≤ O(n)：

T_render(n) ≤ C₂ · n

前提条件。 上式依赖以下对 handler 实现的约束：

1. 每个 handler 调用的输出规模 ≤ α · (输入节点的源码跨度)，其中 α 是与 handler > 实现有关的常数。这保证了 handler 层的总输出 ≤ α · n。
2. handler 不执行与 n 成超线性关系的外部操作（如全文搜索、排序等）。 > 若 handler 包含 O(n log n) 或更高复杂度的逻辑，T_render 的上界将相应升高。
3. materializeTextTokens 的 WeakSet 去重是按数组对象身份生效的： > 同一个 TextToken[] 引用在单次 render 中至多被完整物化一次； > 若第三方 handler 重新创建了逻辑等价、但引用不同的数组，它们仍会各自物化。

这些条件在 yumeDSL 内置 handler 中均满足。第三方自定义 handler 需自行确保。

因此：

T_parseRichText(n) = T_structural(n) + T_render(n) ≤ (C₁ + C₂) · n = C · n

这就是形式化的 T(n) ≤ C · n 闭环。

上面证明了 T(n) ≤ C · n（上界）。为完整起见，说明 T(n) = Ω(n)（下界）也成立， 从而得出 T(n) = Θ(n)。

命题。 对于任意长度为 n > 0 的输入，parseRichText 的时间 T(n) ≥ n。

证明。 parseNodesWithFactory 的根帧 textEnd = n。主循环中， 根帧（或其后代帧）必须消费 [0, n) 中的每一个位置——否则某些源码内容不会出现在 输出 AST 中（根帧的 textEnd 覆盖全文，由 I₁ 保证所有位置被成功帧消费）。

但下界不能再写成“每次字符消费型迭代只跳常数个位置”，因为 1.4.3+ 的 fast skip 会一次跳过整段非边界文本 run。这里真正可用的下界是 source-touch lower bound：

1. 对任意位置 p ∈ [0, n)，它要么是某个成功帧最终消费的位置，要么处在一次 findNextBoundaryChar(...) 扫过的非边界文本 run 中；
2. 若 p 属于非边界文本 run，则解析器至少要读取/比较该位置，才能确认它不是当前 frame 的边界字符并把 fast-skip 指针继续向前推进；
3. 若 p 属于边界位置，则解析器至少要在该位置执行一次边界分支判定，才能决定它是 escape、tag head、close、separator 还是普通文本；
4. 因而，不论 p 落在哪一类位置，当前实现都必须对它发生至少一次库内 primitive source touch（读取、比较，或把它纳入一次单调前进的扫描）。

于是总 source-touch 次数至少与 n 同阶：

source_touches(n) >= n

而每次 primitive source touch 的成本为常数，因此：

T(n) = Ω(n)

综合： T(n) = O(n) ∧ T(n) = Ω(n) ⟹ T(n) = Θ(n)。 ∎

下文后半的“同文附录”继续保留实现走查、分支覆盖矩阵、历史坏路径对照、经验常数与增量解析分析。

以下内容与正文放在同一页面内：它们提供实现定位、历史对照与工程上下文，但不改变正文主命题的证明对象。

以下一节只解释历史恢复链为什么会产生平方项；正文主命题只证明当前实现。

真正制造平方项的不是主循环本身，而是历史上的 malformed shorthand / EOF recovery 会把同一条剩余尾部按“逐帧重入”的方式反复重新判定 ownership 与 close。

设一条坏样本链上有 m 个需要在 EOF 时回退/降级的嵌套 shorthand frame。旧路径可抽象成：

• 第 1 次回退时，重新检查长度约为 m 的剩余尾部；
• 第 2 次回退时，又对长度约为 m-1 的尾部做一次近似同类检查；
• ...
• 第 m 次回退时，再检查长度约为 1 的尾部。

于是旧行为中的额外恢复开销可写成：

T_old-recovery(m)
  = Θ(m) + Θ(m-1) + ... + Θ(1)
  = Σ_{k=1..m} Θ(k)
  = Θ(m²)

如果把 m 看成与输入规模同阶的坏样本深度，那么这条恢复支路就会把总体上界从线性拖到平方。

以下附录保留实现定位、逐迭代走查、版本演化、历史坏路径、经验常数与增量解析分析；它们用于补全工程上下文，不参与正文主命题的对象定义。

下面这张图按 parse.ts / resolveOptions.ts / structural.ts / scanner.ts / render.ts / builders.ts 当前实现，把 parseRichText("...", options) 真正会走的每一步都列出来。 没有省略号，也没有"诸如此类"——所有出现的函数名都对应一份可定位的源码。

1.4.3 读法提醒。 从 1.4.3 起，structural 主循环不再是"每个字符都走完整分支树"。 进入分支级联前会先跑 findNextBoundaryChar(...)，把连续的非边界文本 run 一次推进到下一个边界。 当前边界集合包括：tagPrefix、tagClose、tagDivider（仅 args 内）、escapeChar （仅该帧允许转义时）、当前 inlineCloseToken，以及 shorthand 开启时的 tagName.isTagStartChar(...)。 所以下面的分支图应该读成边界触发的控制流图，而不是"每个字符都必进一次完整分支树"。

flowchart TD
    A[text + ParseOptions] --> B[parseRichText parse.ts]
    B --> C{empty text?}
    C -->|yes| Z[return empty array]
    C -->|no| D[resolveParsePipelineBase parse.ts]

    subgraph BASE[Base Resolve]
        D --> D1[buildGatingContext resolveOptions.ts]
        D --> D2[resolveBlockTags parse.ts]
        D --> D3[resolveBaseOptions resolveOptions.ts]
        D3 --> D4[resolve syntax/tagName/tracker]
    end

    D --> E[createId seed or options.createId]
    E --> F[createRenderContextFromBase parse.ts]
    F --> G[withLegacyAmbientState compat wrapper]
    G --> H[parseStructuralWithResolved structural.ts]

    subgraph STRUCT[structural.ts main path]
        H --> H1[parseNodesWithFactory]
        H1 --> H2[prepare syntax closures]
        H2 --> H3[stack = makeFrame root]
        H3 --> H4[while stack.length > 0]
        H4 --> H4A[A frame-finish branch]
        H4 --> H4B[B escape branch]
        H4 --> H4C[C inline argClose branch]
        H4 --> H4D[D unexpected endTag branch]
        H4 --> H4E[E args separator branch]
        H4 --> H4F[F tag-head branch]
        H4 --> H4G[G inline shorthand branch]
        H4 --> H4H[H text fallback branch]
        H4F --> H5[getTagCloserType]
        H5 --> H6[findTagArgClose scanner.ts]
    end

    H1 --> I[StructuralNode array]

    subgraph SCAN[scanner.ts helpers]
        I --> I1[findBlockClose]
        I --> I2[findRawClose]
        I --> I3[findInlineClose compat-only]
    end

    I --> J[renderNodes render.ts]
    J --> J1[explicit stack traversal]
    J1 --> J2[mergeTextToken / handler dispatch]
    J2 --> J3[materializeTextTokens builders.ts]
    J3 --> J4[WeakSet hit => skip repeated materialization]
    J4 --> K[TextToken array]

上图对应的实际执行步骤，按源码阶段完整展开如下：

1. 入口阶段（parse.ts）

   • parseRichText(text, options) 先做空串短路：if (!text) return []。
   • 非空输入进入 resolveParsePipelineBase(text, options)。
   • 解析 createId：若未提供，则使用默认 rt-${seed++}。
   • 用 createRenderContextFromBase(...) 组装 render 上下文。
   • 最后通过 withLegacyAmbientState(...) 进入 structural + render 主链路（兼容旧 utility 对 ambient state 的依赖）。

2. base resolve 阶段（parse.ts + resolveOptions.ts）

   • buildGatingContext(handlers, allowForms)：
     • 把 handlers 按 form 拆成 inline/raw/block 分组；
     • 计算 registeredTags、allowInline 等 gating 索引。
   • resolveBlockTags(gating.handlers, options.blockTags)：
     • 先基于 handler.raw / handler.block 自动派生；
     • 若用户给 options.blockTags，对显式声明的 tag 做覆盖。
   • resolveBaseOptions(text, options)：
     • 解出最终 syntax / tagName；
     • 当位置追踪开启时构建或复用 tracker。

3. structural 主入口（structural.ts）

   • parseStructuralWithResolved(...) 进入 parseNodesWithFactory(...)。
   • parseNodesWithFactory 初始化：
     • 从 syntax 提前取出 endTag、escapeChar、tagPrefix、tagOpen、tagClose、tagDivider、rawOpen、rawClose、 blockOpen、blockClose；
     • 准备 pushNode / appendBuf / flushBuffer、pushChildFrame / completeChild、tryPushInlineChild 等内部工具；
     • 用显式栈 stack = [makeFrame(root)] 启动循环（不依赖 JS 递归栈）。

4. structural 主循环（while (stack.length > 0)）分支完整表

   • A frame.i >= frame.textEnd：
     • inline 子帧未闭合：报 INLINE_NOT_CLOSED（或简写帧报 SHORTHAND_NOT_CLOSED）并把头部降级回父帧文本；
     • 普通结束：flushBuffer，pop，completeChild 或 root 直接返回。
   • B readEscapedSequence(...) 命中：
     • flushBuffer 后 push escape 节点并推进 i。
   • C inline 帧 argClose 判定：
     • 当 inlineCloseToken !== null 时触发：简写帧（inlineCloseToken === tagClose）直接匹配 ) 关闭；完整 DSL 帧则按后缀区分 )$$ / )% / )*；
     • inline close：flushBuffer + pop + completeChild；
     • raw/block form：分别走 findRawClose / findBlockClose 与对应子帧流程；
     • 非法后缀则按普通字符处理。
   • D 非 inline 帧遇到 endTag：
     • 记 UNEXPECTED_CLOSE 类错误并跳过。
   • E insideArgs && tagDivider：
     • flushBuffer 后 push separator 节点。
   • F 标签头识别：
     • readTagStartInfo 命中后，在非 inline 帧里用 getTagCloserType 判 form；
     • 1.4.3 起，当剩余窗口较大时会走 getTagCloserTypeWithCache(...)，把同一次 parse 内的 argClose 扫描结果复用起来；短窗口仍走直接扫描，避免 Map 常数；
     • 根据 form 进入 inline/raw/block 子帧，或 gating 拒绝后降级文本。
   • G inline 简写识别：
     • 当在 inline 帧内且无标签头匹配时，readInlineShorthandStart 尝试匹配 name( 简写模式。
   • H 兜底文本：
     • 1.4.3 前可近似理解成普通字符 appendBuf + i++；
     • 1.4.3 起更准确的读法是：先用 findNextBoundaryChar(...) 找到下一个边界，再把整段非边界文本 一次 appendBuf 进去。

5. scanner 辅助路径（scanner.ts）

   • findTagArgClose：用于 getTagCloserType 的 form 判定；
   • findBlockClose：block 关闭边界搜索（自身管理嵌套深度）；
   • findRawClose：raw 关闭边界搜索；
   • findInlineClose：兼容路径（inline 主循环本身不依赖它做逐层前扫）。

6. render 阶段（render.ts + builders.ts）

   • renderNodes(structuralNodes, renderCtx, "root") 显式栈遍历 IndexedStructuralNode：
     • text：mergeTextToken 合并相邻文本；
     • escape：readEscaped 后输出文本 token；
     • inline/raw/block：查 handler 分发并产出 draft；
     • block 路径含 normalizeBlockTagContent / consumeBlockTagTrailingLineBreak。
   • handler 结果统一走 appendToken：
     • text 合并；
     • 非 text 直接 push。
   • materializeTextTokens(children, ctx) 在进入时先查 WeakSet(materializedArrays)：
     • 命中直接返回，避免重复物化同一子树（这一步是 render 层避免 O(n²) 的关键点）。

7. 输出阶段

   • parseRichText(...) 最终返回 TextToken[]。
   • 如果走 parseStructural(...) 入口，则在 structural 阶段结束直接返回 StructuralNode[]。

这张图有几个地方值得特别留意，因为它们正是把 1.1.2 之前的 O(n²) 改成 Θ(n) 的位置：

• 分支 C 的 inline argClose 判定完全在主循环里完成：看到 ) 后，检查帧的 inlineCloseToken 来原地决定： 简写帧（token = )）会先做 ownership 判优（full-form close 竞争时让步并回退给父帧）；完整 DSL 帧则按后缀（$$ / % / * ）区分 inline close、raw form 或 block form。 没有任何"再前扫一次找关闭符"的步骤。1.1.2 之前这里调的是 findInlineClose / findTagArgClose，每层 inline 嵌套都要重扫一遍尾巴，深度 d 时是 O(n·d)。
• 分支 F 里的 findTagArgClose 仍然存在，但只在"碰到一个新标签头"的瞬间跑一次 来判定 form。1.4.3 起，大窗口还会走 getTagCloserTypeWithCache(...)，把同一次 parse 里的重复 argClose 扫描折叠掉。它的调用次数仍 ≤ 标签数 ≤ O(n)，缓存只影响常数，不改变上界。
• 转义匹配也做了 1.4.3 常数优化：可转义 token 集合会按 SyntaxConfig 做 WeakMap 缓存， 并按首字符分桶；所以单次转义尝试更接近"只检查同首字符候选"，而不是每次遍历全部 token。
• render 层的 WeakSet 去重只保证同一个 TextToken[] 数组对象在单次 render pass 里 最多被 materializeTextTokens(...) 完整物化一次；如果不同 handler 重新造了逻辑上等价、但引用不同的数组， 仍会各自物化。

如果想看这张图在一段具体输入上每一步真正怎么走，请往下翻"简单导视 2"。

1.4.3 注。 从 1.4.3 起，主循环在进入分支判定前会先跑 findNextBoundaryChar(...) 做快速文本跳跃—— 连续的非边界字符会被批量跳过（appendBuf 一次推进到下一个边界首字符处），实际迭代次数低于下表。 当前边界包括：tagPrefix、tagClose、tagDivider（仅 args 内）、escapeChar、当前 inlineCloseToken， 以及 shorthand 开启时的 tagName.isTagStartChar(...)。下表保留 1.4.2 及以前的逐字符展开， 仅用于解释每个分支的语义；快速跳跃不改变任何分支的正确性或渐进复杂度。

为了不靠"省略号"糊弄读者，下面把 parseNodesWithFactory 主循环的每一次迭代都列出来。 取一段同时包含标签头、inline 嵌套、文本字符、inline 关闭三连击的输入（n = 23）：

索引: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
字符: h  i        $  $  b  (  w  o  $  $  i  (  r  l  d  )  $  $  )  $  $  !

默认语法下相关 token：tagPrefix = "$$"、tagOpen = "("、tagClose = ")"、 endTag = ")$$"（长度 3）。inline 帧的关闭判定先匹配 tagClose，再以同一 i 起点 匹配 endTag。在当前实现里，这是先做同位点 scanEndTagAt(...) 判定，再在完整 DSL inline 帧里按同位点后缀分流。

初始状态：stack = [root]，root 由 makeFrame(text, 0, false, 0) 构造， textEnd = 23，inlineCloseToken = null。

下表中：

• frame 是栈顶帧（b / i 表示 inline 子帧的 tag，root 用 R）。
• stack 给出该次迭代开始时的整个栈（栈顶在右）。
• i₀ → i₁ 是 frame.i 在本次迭代前后的值。
• branch 标注主循环里实际命中的源码分支（行号对应当前 structural.ts）。
• buf / nodes 给出这次迭代后该帧的累积状态。

主循环一共 14 次迭代消费了 23 个源码字符位置 + 2 次 inline pop。可以验证：

• 字符消费型迭代（#1–#3、#5–#6、#8–#10、#13）= 9 次，恰好对应 9 个文本字符 h i ␠ w o r l d !，每次 i 严格 +1。
• 标签头跳跃型迭代（#4、#7）共 2 次，每次让父帧的 i 一步跳过整个 $$X( 头部（4 字符）。这两次的 i 跳跃量等于 4，正好等于子帧将在自己的扫描里把这 4 个 位置归还给"子帧消费"——所以从最终解析帧层面看仍然每个位置只属于一个帧。
• inline 关闭迭代（#11、#12）共 2 次，每次让 i 跳过 )$$ 三个字符；同样， 这 3 个字符在父帧重新计入"父帧消费"，与其它帧不重叠。
• 帧完成迭代（#14）= 1 次，不消费字符。

把"父帧 push 时的 4 字符跳跃 + 子帧后续逐字符扫描"加在一起，每个源码位置在最终 解析帧层面恰好被一个帧消费一次。这正是下面形式化部分要证明的不变量。

主循环之外，本输入触发了以下辅助扫描（全部来自 scanner.ts，只在 root/block 级调用）：

第二次 findTagArgClose 在更内层（frame b 已经是 inline 子帧），但调用它的不是 inline 帧本身——是 getTagCloserType 在为 $$i( 这个新标签判定 form。它在物理上 位于 inline 帧上下文里，但语义上仍属于 root/block 级 form 判定，因为 getTagCloserType 是从 readTagStartInfo 触发的"对一个新出现的标签做一次性判定"。这与"在每层 inline 嵌套里前扫一遍关闭符"是两件事：前者每个标签头一次（O(标签数)），后者每个嵌套层一次 （O(深度·n) → 旧版 O(n²)）。

辅助扫描覆盖的区间总长 12 + 3 = 15 字符，与主循环消费的 23 个位置部分重叠；总工作量 保持在 n + Σ(辅助扫描长度) = O(n) 的范围内，与下面"形式化上界 → 单次迭代工作量上界" 小节给出的 T_structural(n) ≤ k·n + s·n 闭合公式一致。

上面的例子只包含完整 DSL 结构（$$name(...)$$）。从 1.3 起解析器支持 inline 参数区 内的简写形式 name(...)——省略前后缀，用裸 ) 关闭。下面用一段同时包含 完整 DSL 和简写嵌套的输入，把主循环的每一次迭代列出来，展示简写帧的 push / close / 被完整 DSL 打断三类行为。

输入（n = 27）：

索引: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
字符: $  $  b  o  l  d  (  h  e  l  l  o     b  o  l  d  (  w  o  r  l  d  )  )  $  $

含义：$$bold(hello bold(world))$$——外层是完整 DSL 的 bold，参数区里包含 一个简写形式的 bold(world)。

相关 token 与上例相同：tagPrefix = "$$"、tagOpen = "("、tagClose = ")"、 endTag = ")$$"。简写帧的 inlineCloseToken = tagClose（即 )）， 完整 DSL 帧的 inlineCloseToken = endTag（即 )$$）。

主循环一共 16 次迭代，消费 27 个源码位置 + 2 次 pop。

• 字符消费型迭代（#2–#7、#9–#13）= 11 次，对应 11 个文本字符 h e l l o ␠ w o r l d。
• 标签头跳跃型迭代（#1、#8）= 2 次。#1 跳过完整 DSL 头部 $$bold(（7 字符）； #8 跳过简写头部 bold(（5 字符）。简写头部同样由子帧在自己的扫描里归还这些位置。
• 帧关闭迭代（#14、#15）= 2 次。#14 的简写关闭只消费 1 字符 )； #15 的完整 DSL 关闭消费 3 字符 )$$。
• 帧完成迭代（#16）= 1 次。

除了上例已有的 findTagArgClose，简写模式引入了一个额外的辅助扫描——歧义防护前探 （tryPushInlineShorthandChild(...)，当前实现中内部委托给 resolveShorthandOwnershipPush(...)）。

当父帧是完整 DSL 帧（inlineCloseToken === endTag）时，解析器需要确认简写参数区 内找到的第一个"边界"不会让简写误吃父帧的 endTag。前探逐字符向前扫描，在以下三种 情况之一停止：

1. 遇到 escape 序列——跳过，继续扫描。
2. 遇到完整 DSL 标签头（readTagStartInfo 命中 $$name(）——以该位置为边界， reject = false（简写帧会在遇到完整 DSL 时被打断，不存在歧义）。
3. 遇到 tagClose（)）——以该位置为边界，检查 startsWith(endTag, boundary)： 若该 ) 是 endTag（)$$）的开头则 reject = true，简写被拒绝。

本例中（#8），前探从 18 扫到 23 找到 )（boundary=23），startsWith(")$$", 23) → false → reject = false → 前探通过。若边界恰好落在 textEnd 末端，scanEndTagAt 可能返回 truncated-prefix，该状态按“非 full”处理。前探结果被缓存在 shorthandProbe: ShorthandProbeState | null 中（按需创建， 包含 textEnd / startI / boundaryI / reject 四个字段）， 且仅在同一 textEnd 扫描边界版本下复用，避免跨窗口复用脏结论。

辅助扫描覆盖总长 16 + 5 = 21 字符，与主循环消费的 27 个位置部分重叠；总工作量 保持在 n + Σ(辅助扫描长度) = O(n) 范围内。

下面把 1.3.x 最容易误判的样本按主循环逐迭代展开。它和上面的 2b 一样， 但会额外触发两次“降级 + 回到 argStart 重扫”。

输入（n = 45，自定义语法）：

=bold<天気がbold<いlink<baidu.com|い>=>から>=散歩しましょう

本例语法（与 tests/shorthandBehavior.test.ts 一致）：

• tagPrefix = "="
• tagOpen = "<"
• tagClose = ">"
• tagDivider = "|"
• endTag = ">="

索引展开：

索引: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
字符: =  b  o  l  d  <  天 気 が b  o  l  d  <  い l  i  n  k  <  b  a  i  d  u  .  c  o  m  |  い  >  =  >  か  ら  >  =  散 歩 し  ま  し  ょ  う

栈记号：

• R：root 帧
• Bf：外层 full-form =bold<...>= 帧（inlineCloseToken = ">="）
• Bs：中层 shorthand bold<...> 候选帧（inlineCloseToken = ">"）
• Ls：内层 shorthand link<...> 候选帧（inlineCloseToken = ">"）

输出（implicitInlineShorthand=false/true 一致）：

天気がbold<いlink<baidu.com|い>から>=散歩しましょう

说明：这里的 | 在扫描阶段确实进入“管道分隔符处理”，不是普通文本字符分支；最终看到 | 被保留，是因为该路径后续发生降级重扫并以文本形态落地。

这个样本的关键是：push、close、fallback 三个 phase 都只调用同一个 ownership 判定。 因此不会出现“某一段被局部救活导致外层 close ownership 漂移”的分裂行为。

当简写关闭位点与完整 DSL 的 endTag 竞争时，解析器先做 ownership 判优： 若当前位置可完整匹配 endTag，则简写让步（降级为文本并回到 argStart 重扫）， 由父帧消费同一 close token。这保证了完整 DSL 语法始终优先于简写形式。

1. i 严格单调。两个例子的所有迭代里，frame.i 要么不变（帧完成弹栈）要么严格 增加。没有任何分支把 i 拉回去。
2. inline 关闭无前扫。完整 DSL 帧命中 ) 后，仅做同位点 token 判定（endTag / rawOpen / blockOpen），不调用 findInlineClose。简写帧在匹配 ) 前会做同位点 ownership 判优（full-form close 优先）。这仍保持单次迭代 O(1)，是 1.1.2 起 inline 嵌套维持 O(n) 的关键。
3. 辅助扫描可枚举。两个例子的辅助扫描次数都与 inline 嵌套深度 无关——findTagArgClose 由 root/block 级 form 判定触发，简写前探由歧义防护 触发且结果可缓存。这是渐进上界保持线性的根本原因。

把这张表横向拉长到 n = 200,000 时，迭代行数与辅助扫描覆盖区间的总和都线性增长—— 这就是下面形式化部分要严格证明的事。

从 1.1.2 起，两条解析入口的最坏路径均为 Θ(n)：

消除了两个独立的 O(n²) 瓶颈：

1. Structural 层 — 去掉了 inline 前扫。 1.1.2 之前，每一层 inline 嵌套都调用 findInlineClose / findTagArgClose（scanner.ts） 前扫匹配关闭符。d 层嵌套各扫 ~n 字符，最坏 O(n·d) = O(n²)。

   现在：inline 子帧使用 inlineCloseToken 字段记录关闭所需的 token——完整 DSL 帧为 endTag（即 )$$），简写帧为 tagClose（即 )）。帧在当前扫描位置检查自己的关闭 token 就地判定 form（structural.ts push 处注释："不需要预扫 findTagArgClose … 纯 inline 深嵌套保持 O(n)"）。 旧的 findInlineClose / findTagArgClose 仍存在于 scanner.ts，但只在 getTagCloserType（root/block 级 form 判定）和 findBlockClose（block 关闭边界搜索）中被 调用；inline 帧内部不会进入这两条路径。

2. Render 层 — 消除 materializeTextTokens 重复遍历。 之前每次 handler 调用都递归遍历整棵子树。现在用模块级 WeakSet（builders.ts 中的 materializedArrays）标记已处理数组，后续调用命中同一数组直接跳过（builders.ts 第 87–97 行）， O(n²) → O(n)。

两处修复的详细说明见性能页的深嵌套章节。

getTagCloserType / getTagCloserTypeWithCache 仍在 root/block 级调用 findTagArgClose 来判断标签是 inline / raw / block 形态。1.4.3 起按剩余文本长度分流：≤ 256 字符走无缓存的 getTagCloserType，> 256 字符走 getTagCloserTypeWithCache（共享 argClose 扫描结果的 Map 缓存， 且该 Map 延迟创建）。这不会重新引入 O(n²)，原因：

• 它只在顶层帧或 block 内容帧中执行——不在每层嵌套中执行。
• findBlockClose（scanner.ts）内部自行管理嵌套 block 深度，跳过内层 raw 段（findRawClose） 和内层 inline 段（findInlineClose）。对单次 findBlockClose 调用而言，扫描指针始终单调前进， 不会重新引入逐层回退前扫，因此其总工作量仍为 O(n)。

仅说明“主循环是 Θ(n)”并不等于“当前实现里的所有库内分支都已经被覆盖”。 这一节把库自己拥有的控制流按函数层级拆开，逐项说明：

• 分支在什么地方触发；
• 单次命中的局部成本是什么；
• 它最终并入哪一条总上界；
• 哪些地方已经超出“库自身复杂度保证”的边界，进入用户 handler / 用户输出规模的问题域。

这里的“覆盖”特指：

1. parseStructural(...) / parseRichText(...) 正常入口；
2. 使用当前实现里的 structural + render 管线；
3. 不把用户自定义 handler 函数体内部的复杂度算进“库自身 Θ(n)”保证。

这一组恢复分支需要单独列出，因为它们决定了恢复路径是否会重新引入超线性开销。当前覆盖的恢复分支包括：

更精确地说，本文现在覆盖的是：

1. structural parser 自己的顶层分支与子分支；
2. 1.4.4 ownership / EOF recovery 的新增与历史坏路径；
3. render 主循环、节点分发、text buffer、raw/block trim/degrade/materialize 这些库内分支；
4. 但不把用户 handler 函数体内部复杂度伪装成库的 Θ(n) 保证。

因此，当前更准确的总表述应为：

T_library-owned(parseRichText, n) = Θ(n)

其中 “library-owned” 明确排除了用户 handler 自己写出来的额外工作； 在这个限定下，当前实现的 structural / render / recovery / helper 分支都已经被纳入本文复杂度覆盖。

以下内容只做历史对照：它解释旧坏路径为何出现，以及当前实现具体切断了哪一类逐帧重入放大。它不参与正文主命题的证明对象定义。

这一版 changelog 里所谓“发现了一条 N² 路径”，说的不是正常 well-formed 文档，也不是一般意义上的所有 malformed 输入， 而是深层 shorthand / inline 发生 ownership 竞争并一路拖到 EOF 恢复的那条组合路径。

把旧行为和新行为并排写出来，更容易看清这次修复的复杂度意义：

所以，这次 1.4.4 的复杂度修复不是“把某个常数调小了”，而是把一条真实存在的恢复路径复杂度类别从平方级拉回了线性级。

上面给出的，是 1.4.4 之后的现行读法。 但如果这页要承担“论文 / 设计说明”的角色，旧模型本身也不该被抹掉，因为：

1. 你需要知道为什么 changelog 里会出现“发现了一条 N² 路径”这种措辞；
2. 你需要知道旧路径究竟坏在什么地方，而不是只知道“现在修好了”；
3. 你需要把 旧推导中的放大器 和 新实现中对应被切断的环节 一一对上。

因此，这里把旧模型再单独保留一次，不把它删进脚注里。

旧模型的放大点可以抽象成下面这条链：

深层 shorthand / inline 竞争 close
    → 当前层无法稳定归属
    → 退回父层重新观察同一 suffix
    → 父层又把部分 suffix 带回主循环
    → 下一层继续重复

如果把某一时刻仍待处理的尾部长度记作 k，那么旧路径的累计工作量可以写成：

W_old(k) = k + (k - δ1) + (k - δ1 - δ2) + ...

其中每个 δi > 0 代表“这次至少前进了一点”，但只要“回父层之后仍然要重新看那段尾巴”的事实成立， 这就是典型的三角级数；在最坏均匀情形下退化成：

W_old(k) = k + (k - 1) + (k - 2) + ... + 1 = Θ(k²)

换句话说，旧模型的问题不是“有一个 O(n) 的扫描函数”，而是：

• 同一 suffix 被放回主循环太多次；
• ownership 信息不够局部，必须借助父层重入来重新确认；
• EOF 恢复不是一次把整条 malformed chain 结算清楚，而是让链式状态继续把尾巴拖着走。

而 1.4.4 正好一一切断这三个放大器：

所以，保留旧推导的意义不是说“现在还会这样跑”，而是让读者看见：

• 旧复杂度是怎样长出来的；
• 新实现究竟把哪条因果链掐断了；
• 为什么 changelog 里说的是‘恢复线性保证’，而不是单纯‘优化常数’。

常数 C 不是均匀的——不同输入形状压测不同分支。以下是三个最坏轴及其对应的具体输入。

\z\z\z\z\z\z\z\z\z\z...

每个 \ 触发转义前缀命中路径。readEscapedSequence 匹配到转义字符后，按长度降序检查全部 9 个 escapableTokens（默认语法：)$$、)%、)*、%%、**、(、)、|、\）。 由于 z 不以任何 token 开头，9 个全部 miss，\ 被当作普通字符（不构成转义）。 这是单字符分支计数最高的输入：k ≈ 12–15。

合法转义如 \(\(\(\(... 在第 6 次检查才命中 (（前 5 个长 token 不以 ( 开头）， 单次 \ 的开销稍低但仍可观。

两种情况下都没有回退扫描——指针每次迭代仍至少前进 1，因此总工作量仍保持线性。

$$a($$a($$a($$a($$a($$a(x)$$)$$)$$)$$)$$)$$

每个 $$a( 向显式栈 push 一帧。默认语法下最小标签开销 4 字符（$$ + 1 名字字符 + (）， 所以最大栈深度 ≤ n/4。1.1.2 起使用数组栈而非调用栈，任意深度都不会爆栈，只受堆内存限制。

性能页的 5000 万层压力测试已实证。

$$a(x)$$$$a(x)$$$$a(x)$$$$a(x)$$...

所有标签处于 root 级，每个都触发 getTagCloserType → findTagArgClose。form 判定扫描与 后续子帧解析覆盖的区间重叠，因此这些区域会承担额外的常数倍线性开销；但这不会改变 Θ(n) 结论。

没有任何单一输入能同时最大化这三个轴。下面给出形式化论证。

命题。 设长度为 n 的输入中，转义序列占 E 个字符，标签结构（标签头 + 参数 + 尾标签） 占 T 个字符，纯文本（非转义、非标签）占 P 个字符。则 E + T + P = n。

轴 1 与轴 2 的互斥。 每个转义序列 \x 占 2 个字符且不被识别为标签头（转义检查 在标签头检查之前执行，structural.ts 第 659 行）。因此 E 增大时，留给标签结构的字符数 T ≤ n − E 减小。最大栈深度 ≤ T/4（每个标签头 ≥ 4 字符），故：

栈深度 ≤ (n − E) / 4

轴 2 与轴 3 的互斥。 深嵌套要求标签以 inline 形态递归嵌入。在 inline 帧内 （H1 路径），不调用 getTagCloserType（structural.ts 第 892–918 行）， 因此不产生 form 判定开销。只有 root / block 级帧的标签才触发 getTagCloserType。 设嵌套深度为 d，则同一段区间内 root 级标签数 ≤ n / (4d)，form 判定总扫描 ≤ n · (n/(4d)) / n = n/(4d)。 即深嵌套越深，form 判定总量越少。

轴 1 与轴 3 的互斥。 转义字符不构成标签头，因此不触发 form 判定。E 越大，form 判定次数越少。

结论。 三轴开销的凸组合受线性约束：

C_total = c₁ · E + c₂ · T + c₃ · P ≤ max(c₁, c₂, c₃) · n = O(n)

其中 c₁, c₂, c₃ 分别是转义分支预算、标签处理（含栈操作 + form 判定）单位开销、 纯文本分支预算。三者都是不依赖 n 的常数。 因此实际最坏情况总是三者之间的权衡，总量始终在 C · n 以内。 ∎

主循环在每个字符位置 i 执行固定的级联检查。以下是从源码精确计数的完整序列：

1.4.3 变化。 step 0 的快速文本跳跃会把连续非边界字符批量跳过，使得纯文本区段不再逐字符走 step 1–6b。 step 2b 的 escapable 扫描从"遍历全部 E 个 token"改为"按首字符分桶后只测试对应桶"——\z 等不以 任何 token 首字符开头的序列现在直接返回，不再测试全部 9 个 token。

按输入类型汇总（默认语法）：

1.4.3 的 fast skip 主要改善纯文本和转义密集两端；标签密集输入的 k 值基本不变。 对主流场景（常规富文本），k ≈ 4–6。

n = text.length          // UTF-16 code units

本库的基准 fixture 基本是 ASCII DSL 语法，bytes ≈ code units ≈ characters。各基准的输入规模：

深嵌套基准里的测试参数是嵌套层数 d，但每层只增加常数个源码字符，所以 n = c · d + O(1)，Θ(n) = Θ(d)。

这一节保留的是 v1.1.9 时代的历史常数基线，主要用来帮助理解"Θ(n) 成立时，常数大致会落在哪个量级"。 它不是 1.4.3 的当前 release 数字，也不应该拿来和 性能 页里的最新表格直接对照。

如果你关心 1.4.3 的当前实测，请直接看 性能 页；这里保留的是同方法学下的旧基线。

环境：鲲鹏 920 / aarch64 / Node v24.14.0。下面这一组全部出自同一份基准脚本（.tmp/bench-pos-single.mjs）：

• 输入：固定 fixture，n = 204,803 字节（≈ 200 KB）
• 每个格子 = 20 次独立 node 进程冷启动；进程之间不共享 JIT / heap 状态，且全程串行 执行，没有任何并发
• 每个进程内：100 次 warmup（让 V8 把 parser 完整 tier-up，避免第 31 调用恰好命中 优化阈值导致的双峰）→ 再跑 15 次测量取进程内中位数作为该进程的代表样本
• 表中的 ms = 20 个进程中位数的算术平均；ns/cu = ms × 10⁶ / n

这一组与之前 wiki 上"30.6 / 23.3 ms"那张表数字偏低，原因是两件事一起改了：当前 workspace 已经在 1.1.9，比那张表对应的版本多吃了若干轮 render / scanner 常数优化； 同时这次的方法学（100 warmup + 15 中位数 × 20 冷进程）比旧版本"3 warmup + 20 in-process 样本一次性测完 4 个 case"更稳定，旧版的 in-process 共享 JIT 状态会让先跑的 case 略 吃亏。要复现这张表，直接 node .tmp/bench-pos-single.mjs <target> 即可。

数据为 5 次独立进程运行（每次包含 50 次内部采样）的平均值。

buildZones 只遍历顶层 StructuralNode[] 数组（zones.ts），成本跟顶层节点数成正比，不直接 跟源码长度挂钩。上面折算出的 ~3.7 ns/char 是这组基准下的派生值，不应外推到节点/字符比差异较大的 输入上。

这些常数和具体机器、具体基准绑定，不同组之间不能横向比较。

两条解析入口（parseStructural、parseRichText）和 materializeTextTokens 已全部改为 显式栈迭代（while + 手动栈）。所有工具函数也已改为显式栈迭代：

对典型文档深度（几百层以内）没有影响。即使在达到数万层的病理输入时也不会溢出。

复杂度始终是 Θ(n)，但同样的 n 实际花多少时间，取决于 每个源码字符背后引发多少工作。四个维度起主导作用：

扫描器命中标签前缀、进入 open/close/gating 逻辑的频率。

每字符产出的节点越多 → 对象分配越多、children 数组操作越多、parseRichText 路径上 token 物化越多。

structural 扫描器的 flushBuffer 对常见的 1–2 段文本使用 segment-pair 直拼优化 （structural.ts 第 312–315 行），避免分配临时数组，使得典型输入下单次 flush 的常数很小。

dense siblings 和 deep chain 在 n 相近时有不同的 cache 行为和 children 挂接模式。 性能页的内存画像已经证明：200 KB dense inline 和 20k nested inline 在相近输入规模 下的 heap/RSS 差异明显。

parseRichText = structural 扫描 + render 物化，所以同一输入下它的常数永远高于 parseStructural。

工程估算时，总成本可拆解为：

T ≈ α · n_chars + β · n_tags + γ · n_nodes + δ · depth_max

parseRichText 再加 + ε · n_tokens。

这几个派生量都被 n_chars 上界住，所以渐进类别仍为 Θ(n)。 但在实际运行中，决定快慢的正是这几项。

n 始终是源码长度；不同输入之间变化的是单位字符的工作密度 —— 由标签密度、节点密度、嵌套深度和 render 路径共同决定。

增量解析（内部核心是 updateIncrementalInternal(...)，公开更新入口以 createIncrementalSession(...).applyEdit(...) 为主）遵循一套与全量 parseStructural 完全不同的成本模型。 全量解析每次调用都是 Θ(n)；增量解析的目标是让单次编辑的代价尽量正比于变更区域而非整个文档。 本节给出形式化推导。

这一节的证明对象固定为调用时成本，不是“所有后续懒操作都自动算进一次更新调用里”。

命题 U（单次增量更新路径调用）

T_update-call(n) = O(n)

这里的 T_update-call(n) 指一次增量更新路径调用自身的最坏时间（核心对应 updateIncrementalInternal(...)）； 它包含：

1. assertValidEdit(...)
2. fingerprint 比对
3. findDirtyRange(...)
4. reparseDirtyWindowUntilStable(...)
5. isSafeRightReuse(...)
6. deferShiftZone(...)
7. 文档拼接与 installLazyDocument(...)
8. 在增量路径真正提交后发生的 cloneParseOptions(...)

它不包含两类额外工作：

1. 延迟物化：返回后的 doc.tree / doc.zones 首次读取触发的 lazy materialization；
2. 增量 diff：session.applyEditWithDiff(...) 在更新完成后追加的 diff 计算。

命题 S（session 调用）

T_session-applyEdit-call(n) = O(n)

因为 createIncrementalSession(...).applyEdit(...) 只是在 updateIncrementalInternal(...) 外层 再包一层常数级策略门控、采样记录与 fallback 编排。

这一节也沿用“先给成本分解，再给支撑引理，最后闭合”的写法。主线不是逐段流程描述，而是：

T_edit-call
  = T_validate
  + T_fingerprint
  + T_dirtyFind
  + T_reparse
  + T_probe
  + T_shift
  + T_assemble
  + T_clone

后文各小节分别证明这些项的上界；闭合时再利用 Δ <= n、Z <= n、Z_right <= Z <= n， 以及 H 对文档长度 n 不增长这一边界，得到最坏 O(n)。

这里的线性保证先只覆盖 增量更新本身（session.applyEdit(...) 对应的更新路径）：

applyEditWithDiff(...) 不是独立导出的顶层函数，而是 createIncrementalSession(...) 返回对象上的方法。它在更新完成后还会额外跑结构化 diff；那部分从 1.3.8 起属于单独的复杂度模型， 不应和 parser / updater 的 Θ(n) / O(n) 保证混为一谈。

变量约定

n       = newSource.length          （编辑后文档总长度）
Δ       = edit.newText.length       （插入文本长度）
d_old   = edit.oldEndOffset - edit.startOffset   （被删除区间长度）
Z       = 上一快照的 zone 总数
z_dirty = 脏窗扩展后涉及的 zone 数
H       = handler 数据总量 + syntax 字段 + allowForms 元素数（parseOptions 规模）
Z_right = 右侧复用 zone 数
W_probe = seam probe 重新解析窗口宽度

下面依次分析 updateIncrementalInternal(...) 的每一步。

flowchart LR
    subgraph INCR["updateIncrementalInternal 流水线"]
        direction LR
        S1["① assertValidEdit<br/>O(Δ)"]
        S2["② fingerprint check<br/>O(H) / O(1)"]
        S3["③ zone 守卫<br/>O(1)"]
        S4["④ findDirtyRange<br/>O(Z)"]
        S5["⑤ reparseDirtyWindow<br/>≤ O(n)"]
        S6["⑥ seam probe<br/>O(W_probe)"]
        S7["⑦ deferShiftZone<br/>O(Z_right)"]
        S8["⑧ assemble<br/>O(Z)"]
        S1 --> S2 --> S3 --> S4 --> S5 --> S6 --> S7 --> S8
    end

    S2 -. " 指纹不匹配 " .-> FB["fullRebuild Θ(n)"]
    S3 -. " 空 zone / 低 zone / 尾部间隙 " .-> FB
    S5 -. " 预算耗尽 " .-> FB
    S6 -. " 签名不匹配 " .-> FB

updateIncrementalInternal 可拆成七个串行阶段（加上 zone 守卫共八步）：

1. Edit validation（assertValidEdit，incremental.ts:941–965）： 执行 newSource.slice(edit.startOffset, edit.startOffset + edit.newText.length) 并与 edit.newText 做字符串比较。 slice + === 的开销 = O(Δ)。

2. Fingerprint check（buildParseOptionsFingerprint，incremental.ts:346–369）： 对 handlers shape、allowForms、syntax、tagName 做 FNV-1a hash。 字段数量 = |handlers keys| + |syntaxKeys|(8) + |allowForms| + 2 个函数标识 = O(H)。 首次调用 O(H)；getCachedOptionsFingerprint（WeakMap）命中时 O(1)。 对于前一文档（doc），fingerprint 必然已缓存，所以上一侧为 O(1)。 当 options 参数为 undefined（session 常见路径），直接复用旧值，O(1)。

3. Dirty range finding（findDirtyRange，incremental.ts:840–872）： 单遍线性扫描所有 zone，同时追踪 overlap 区间和插入点索引。循环上界 = Z，每步 O(1) 比较。 T_dirtyFind(Z) = O(Z)。

4. Dirty window reparse（reparseDirtyWindowUntilStable，incremental.ts:877–935）： 关键路径，下一节单独分析。

5. Seam probe（isSafeRightReuse，incremental.ts:613–660）： 验证右侧 zone 可安全复用。下文 §seam probe 单独分析。

6. Lazy delta shifting（deferShiftZone，incremental.ts:768–782）： 对每个右侧 zone 创建一个新 Zone 对象、一次 WeakMap.get、一次 WeakMap.set、 可选拷贝签名缓存 → 每个 zone O(1)。 T_shift = O(Z_right) = O(Z - z_dirty)。

7. Document assembly（incremental.ts:1145）： [...leftZones, ...dirtyZones, ...rightZones] — 数组展开 + installLazyDocument。 总元素 = 最终 zone 数 ≤ Z + O(z_dirty)，所以 T_assemble = O(Z)。

reparseDirtyWindowUntilStable（incremental.ts:877–935）是增量路径上唯一可能 放大到 O(n) 的环节。

不变量 1：每轮扩展恰好多纳入 1 个 zone。 循环体（incremental.ts:897–933）在右边界未稳定时执行 nextDirtyTo += 1（incremental.ts:933），即每轮扩展 1 个 zone。设扩展次数为 k，则 k ≤ Z（最多把所有 zone 都纳入脏窗）。

不变量 2：每轮重解析的窗口字节 = dirtyEndNew − dirtyStartNew。 每轮解析的 slice 长度 = reparsedWindowSize，并累加到 nextCumulativeReparsedBytes（incremental.ts:905）。

窗口是单调递增的（每轮右端多一个 zone），设第 i 轮窗口宽度 W_i。 各轮总开销：

Σ_{i=1}^{k} W_i

最坏情况下 W_i 可以逐轮递增，导致 Σ 趋于二次方——这正是 budget 守卫要防止的。

不变量 3：内部累计重解析预算固定为 Math.max(newSource.length * 2, 1024)。

这是当前实现里的硬编码内部常量，不是 IncrementalParseOptions 或 IncrementalSessionOptions 里的用户可调参数。

nextCumulativeReparsedBytes > cumulativeBudget 时 （incremental.ts:906），函数立即返回 budgetExceeded = true， 调用方（incremental.ts:1119）执行 fullRebuild()——即 parseIncremental(newSource)， 复杂度 Θ(n)。

因此存在两条路径：

路径 A（budget 未耗尽）：Σ W_i ≤ 2n  →  T_reparse ≤ O(n)
路径 B（budget 耗尽）  ：fallback to full rebuild  →  T_fullRebuild = Θ(n)

结论： T_reparse ≤ O(n) 在所有情况下成立。

isSafeRightReuse（incremental.ts:613–660）在右侧 zone 非空时执行。

Probe 窗口宽度： 当前实现使用硬编码常量 RIGHT_REUSE_PROBE_ZONES = 2、RIGHT_REUSE_PROBE_EXTRA_ZONES = 1， 因此 probe 最多覆盖 3 个旧 zone。这也是实现常数，不是公开可调参数。

probe 重解析的 slice 长度 = probeEndOld − probeStartOld（映射到 newSource 偏移）， 即 probe 窗口覆盖的 3 个 zone 在旧文档中的总跨度 W_probe。

Signature 比对：

• budget = RIGHT_REUSE_PROBE_SIGNATURE_NODE_BUDGET = 4096（incremental.ts:436）。
• 每个节点调用 nodeSignature（incremental.ts:500–560），其中文本内容使用 hashTextBounded（incremental.ts:479–481），底层为 fnvFeedStringBounded（hash.ts:36–49）：只取首 BOUNDED_HEAD=32 字符和 尾 BOUNDED_TAIL=32 字符，最多 64 字符 → O(1) 每节点。
• 签名预算耗尽 → 返回 ok: false → 调用方 full rebuild。
• 总签名比对开销 ≤ O(4096) = O(1)（常数上界）。

Probe 重解析开销： W_probe 由 3 个 zone 的宽度决定。绝大多数文档中 zone 宽度远小于 n，所以 probe 开销 远小于 n。但如果文档仅有极少巨型 zone（极端情况），W_probe 可接近 n。即便如此， probe 重解析的字节数也计入 probeSliceBytes 且受 cumulativeBudget 约束—— 不会突破 O(n) 上界。

T_probe ≤ O(W_probe) + O(4096)
        ≤ O(W_probe)
        ≤ O(n)            （最坏；典型 ≪ n）

cloneParseOptions（incremental.ts:258–284）在 updateIncrementalInternal 中仅当确定走增量拼接路径后才执行（1.2.5+）。若任一 early guard 触发 full rebuild， 不发生克隆——parseIncrementalInternal 内部会自行 clone。

• 顶层展开 { ...options } = O(|fields|) = O(1)（字段数固定）。
• cloneHandlersSnapshot（incremental.ts:239–251）：遍历 handlers keys， 每个 key 做一次 cloneSnapshotValue（结构化深拷贝）。总开销 = O(H)。
• syntax、tagName、allowForms 各做浅拷贝 / 数组展开 → O(H)。

Session 路径优化： 在 createIncrementalSession(...) 中，session.applyEdit(...) 的 nextOptions 参数通常为 undefined（用户不改配置），此时直接复用旧快照，不发生克隆。

T_clone = O(H)    （H 独立于 n，且常见路径为 O(1)）

deferShiftZone（incremental.ts:768–782）创建新 Zone 对象并把 delta 累积到 zonePendingDeltaMap（WeakMap）。操作序列：

1. WeakMap.get(zone)       → O(1)
2. 创建 Zone 字面量         → O(1)
3. WeakMap.set(newZone, δ) → O(1)
4. 复制签名缓存（可选）       → O(1)

每个右侧 zone 恒定开销 → T_shift = O(Z_right)。

物化（materializeZone，incremental.ts:786–797） 在消费者首次访问 doc.tree 或 doc.zones 时按需触发。它对每个待物化 zone 调用 shiftNode （incremental.ts:710–745），后者使用显式栈（incremental.ts:712）迭代 遍历所有子节点，开销 = O(该 zone 内节点数)。

全部 zone 物化总开销 = O(全文档节点数) = O(n)。但此开销是 lazy 的：

• 如果消费者只读 doc.source（常见的"仅需文本"路径），物化成本 = 0。
• 如果消费者在连续 k 次编辑后才读 doc.tree，累积 delta 在一次物化中一并应用—— k 次编辑仍只付 O(n) 物化成本，而非 k·O(n)。

T_materialize_total = O(n)    （lazy，一次性，跨编辑摊还）

聚合摊还分析。 设在一个编辑 session 中连续执行 k 次编辑（applyEdit 调用 k 次）， 然后消费者读取 doc.tree 触发一次物化。

• 每次 applyEdit 开销 ≤ O(W_dirty_i + Z + H)，其中 W_dirty_i 是第 i 次编辑的 脏窗宽度。物化标记被设置（dirty = true），但不执行物化。
• 最终一次物化遍历所有节点，执行 shiftNode 的显式栈迭代：每个节点访问 1 次。 总开销 = O(节点数) = O(n)。

因此 k 次编辑 + 1 次物化的总开销：

Σᵢ T_edit(i) + T_materialize = Σᵢ O(W_dirty_i + Z + H) + O(n)

若每次编辑是局部的（W_dirty_i ≪ n），则编辑总开销 ≤ k · O(W_dirty_max + Z + H)， 物化开销 O(n) 只付一次。将物化的 O(n) 摊还到 k 次编辑上：

摊还每次编辑开销 = O(W_dirty + Z + H) + O(n/k)

当 k ≥ n / W_dirty 时，摊还物化开销 ≤ O(W_dirty)，与编辑开销同阶。 这正式证明了 lazy 物化的经济性：频繁编辑 + 延迟读取 = 最优摊还。

将各阶段合并：

T_edit(n, Δ, Z, H)
    ≤ T_validate(Δ) + T_fingerprint(H) + T_dirtyFind(Z)
      + T_reparse(n) + T_probe(n) + T_shift(Z) + T_assemble(Z)
    ≤ O(Δ) + O(H) + O(Z) + O(n) + O(n) + O(Z) + O(Z)
    = O(n + Z + H)

因为 Z ≤ n（zone 数不超过文档长度）、H 独立于 n：

T_edit(n) ≤ O(n)      （最坏情况，被 reparse budget 或 full-rebuild fallback 支配）

典型局部编辑时，reparse budget 不会被触发，脏窗宽度 W_dirty 远小于 n：

T_edit_typical ≤ O(W_dirty + Z_right + H)

其中 W_dirty 正比于编辑局部性（与 n 无关），Z_right 个 zone 的 lazy shift 各 O(1)。 对于光标附近的单字符插入，W_dirty 通常为几百字节级别，Z_right ≈ Z， H 在 session 路径为 O(1) → 整体亚线性。

"典型局部编辑"的形式化条件。 上式中 W_dirty ≪ n 并非对所有编辑都成立。 以下给出触发亚线性行为的充分条件：

1. 编辑跨度有界： 编辑操作的替换区间 [replaceStart, replaceEnd) 满足 > replaceEnd − replaceStart ≤ δ，其中 δ 是与 n 无关的常数（如单字符插入 δ=0， > 单行替换 δ ≤ 行宽上界）。
2. 编辑不跨越 zone 边界： 替换区间完全落入某个 zone z_i 内部。这保证 > findDirtyRange 只需检查 z_i 及其相邻 zone，脏窗 W_dirty ≤ |z_i| + |z_{i±1}|。
3. 编辑不破坏标签闭合结构： 若编辑插入或删除了标签分隔符（$$、(、) 等）， > 可能导致大范围重解析。"典型"编辑指文本区域内的字符修改，不涉及语法边界字符。
4. reparse budget 未耗尽： cumulativeBudget = Math.max(newSource.length * 2, 1024)（incremental.ts） > 未被单次重解析用完。若脏窗内的重解析超过此预算，将退化为全量重建（O(n)）。

在这四个条件下： W_dirty ≤ |z_max| + |z_max| = 2 · |z_max|， 其中 |z_max| 由 softZoneNodeCap（默认 64 个节点；非法用户输入会被规范回默认值）间接约束—— 每个 zone 至多 64 个节点，每个节点的源码跨度在典型文档中有实际上界。 因此 W_dirty = O(1) 相对于 n，整体 T_edit_typical = O(Z + H) = O(Z)。

上面的闭合公式清楚地表明：findDirtyRange、deferShiftZone、assemble 三步的开销都是 O(Z)。Z 越大，这些"骨架开销"占总时间的比例就越高。 当编辑局部性很好（W_dirty ≪ n）时，Z 反而成为主导项。

Zone 切分改变了 Z 的来源。 1.2.4 之前，Z 完全由文档中 raw / block 节点（"硬 zone breaker"）的分布决定。1.2.4 引入 softZoneNodeCap （默认 64）后，非 breaker 节点每累积到上限就切出一个新 zone；非法或非正的用户值会被规范回默认值， 所以这个上限默认无法被"关掉"。 因此：

Z ≈ N_breaker + ⌈N_nonbreaker / softNodeCap⌉

其中 N_breaker 是 raw/block 节点数，N_nonbreaker 是 text/inline/escape/separator 节点数。同一篇文档，softNodeCap 越小 → Z 越大 → 脏窗更窄（W_dirty ↓）但 骨架开销更高（Z ↑）。

实测数据（1 MB 文档，鲲鹏 920，Node v24.14.0，头部单字符替换）：

头部编辑是最坏方向（Z_right ≈ Z），尾部编辑更快。

甜区：几百到几千 zone。 在此范围内，脏窗足够窄而骨架开销尚可忽略， 能拿到 ~10× 加速。超过万级后，骨架开销（主要是 findDirtyRange 的单遍线性扫描和 deferShiftZone 的逐 zone 创建）吃掉了大部分收益。

这就是为什么 SOFT_ZONE_NODE_CAP 默认值为 64 而非更小——它在典型文档上 把 Z 控制在几百到几千的范围，正好落在甜区。

当 prevZones.length ≤ 1（updateIncrementalInternal(...) 入口守卫）时，增量路径没有可复用的 zone 分界点——脏窗就是整篇文档。此时增量路径的 findDirtyRange + seam probe + assemble 开销纯属浪费。

1.2.4 在 updateIncrementalInternal(...) 入口加了守卫：prevZones.length ≤ 1 直接走 fullRebuild()，跳过整个增量管线。这保证了单 zone 文档（纯文本、 纯 inline、无 handler 等场景）不会比裸全量更慢。

createIncrementalSession（src/incremental/incremental.ts）在 updateIncrementalInternal 之上增加自适应策略层。

这里也要澄清一次 API 形态：

• applyEdit(...) / applyEditWithDiff(...) 是 createIncrementalSession(...) 返回对象上的方法；
• session 层的自适应切换（incremental / full-fallback）发生在 updateIncrementalInternal(...) 外层， 但不会改变"更新路径最坏 O(n)"这一结论。

applyEdit 的策略门控：

1. strategy === "full-only"                         → runRebuild   O(1) 判断
2. strategy === "auto" && editRatio > maxEditRatio   → runRebuild   O(1) 判断
3. strategy === "auto" && preferFullMode && cooldown  → runRebuild   O(1) 判断
4. 否则：tryUpdateIncrementalInternal                → 正常增量路径

每条分支内部的额外操作：

• editRatio 计算：2 次减法 + 1 次除法 = O(1)。 maxEditRatioForIncremental 默认 0.2。
• 计时：2 次 now() 调用 = O(1)。
• recordBounded：向有界数组 push + 可能的 shift。 数组长度 ≤ sampleWindowSize（默认 24）。 push = O(1)；shift = O(sampleWindowSize) = O(24) = O(1)。

maybeAdaptPolicy：

• average(fallbackMarks)：遍历 ≤ sampleWindowSize 元素 → O(24) = O(1)。
• average(incrementalDurations) 和 average(fullDurations) 同理。
• 仅在 incrementalDurations.length ≥ minSamplesForAdaptation（默认 6）时执行。
• 若 fallback rate > maxFallbackRate（默认 0.35）或增量均值 > 全量均值 × switchToFullMultiplier（默认 1.1），进入 enterFullPreference（O(1)）。

T_session_overhead = O(sampleWindowSize) = O(1)   （常数，独立于 n）
T_session_edit = T_edit + O(1) = 与裸更新内核路径相同渐近类

applyEditWithDiff(...) 的总成本分成两段：

T_applyEditWithDiff = T_applyEdit + T_diff

其中 T_applyEdit 已在上文证明最坏 O(n)。真正新增的是 T_diff。

1.4.0+ 之后，这条 diff 路径还额外受一组默认预算约束：

• refinementDepthCap = 64
• maxComparedNodes = 20_000
• maxAnchorCandidates = 128
• maxOps = 512
• maxSubtreeNodes = 256
• maxMilliseconds = 8

另外，当 session 已经走到 full-fallback 且文档长度超过 MAX_FULL_FALLBACK_DIFF_REFINEMENT_SOURCE_LENGTH = 20_000 时，当前实现会直接跳过深度细化， 转入 conservative diff。

这些预算和 cutoff 的作用是限制退化成本并允许结果变粗，不是把 applyEditWithDiff(...) 变成线性保证。

当 diff 精化抛错，或已经走到 full-fallback 且文档过大时，session 会直接走 buildConservativeTokenDiff(...)。

这条路径只做三件事：

1. 读取 previousDoc.tree.length / nextDoc.tree.length → O(1)
2. 构造整树级 patches / ops 外壳 → O(1)
3. 对 oldNodes / newNodes 做一次 slice() → O(N_old + N_new)

设：

N_old = previousDoc.tree.length
N_new = nextDoc.tree.length
N_root = N_old + N_new

则：

T_diff_conservative = O(N_root)

也就是说，保守 diff 仍是线性的。

细粒度 diff 由 diffNodeArrays(...) + processNestedNodeArrayDiffs(...) 组成。 它不是简单的"从左到右扫一遍"；会在容器数组上做 anchor 检测、分段、再递归/迭代细化。

记：

M = 本次 diff 真正参与细化比较的 old/new 节点总数
P = 最终产出的 structural diff ops 数量

对任意一个容器范围（combined length = m），diffNodeArrays(...) 的单轮工作包括：

1. 前后缀裁剪：prefix + suffix trim，各自线性推进，总计 O(m)
2. anchor 搜索：findAnchors(...)
   • 建 old/new 两张 signature 计数表：O(m)
   • 候选排序：O(a log a)，其中 a ≤ m
   • LIS 稳定岛提取：O(a log a)
   • 故单次 anchor 阶段上界 O(m log m)
3. 无 anchor 时
   • 等长分支：逐项比对 + 可能排入 nested task，O(m)
   • 非等长分支：直接 splice，复制该段 old/new nodes，O(m)

因此，单个范围的上界可写成：

R(m) ≤ O(m log m) + 子范围递归/迭代成本

最坏情况下，anchor 每轮只能切出一个很小的稳定岛，剩下一个规模 m-1 的大区间继续进入下一轮。 此时满足递推：

R(m) = R(m - 1) + O(m log m)

展开可得：

R(m) = O(Σ_{i=1..m} i log i) = O(m² log m)

这说明 细粒度 diff 的最坏情况不是 Θ(n)。
它的设计目标是"局部编辑时尽量给出高质量结构 diff"，而不是像 parser 那样提供严格线性上界。

• diffRefinementDepthCap 只限制向更深 children/args 继续细化的深度； 深度超限后会退化为当前容器上的 splice。
• 这能限制深链场景下的 refinement 成本，但不消除宽范围 anchor 分段带来的最坏 O(m² log m)。
• 最终 ops 还会执行一次排序：

T_sort_ops = O(P log P)

因此，对 applyEditWithDiff(...)：

T_applyEditWithDiff
    = T_applyEdit + T_diff
    ≤ O(n) + min(
          O(N_root),                 // conservative diff
          O(M² log M + P log P)      // refined diff
      )

在典型局部编辑下，M 往往只覆盖少量 root 范围和少量嵌套容器，所以实际远好于这个上界； 但文档层面的严格线性保证只能归属于 parser / incremental updater，不包括细粒度 diff。

关键区分：

• 首次解析没有旧快照可复用，必须扫全文 → Θ(n)。
• 增量更新在局部编辑时只重解析脏窗，Z_right 个 zone 的 shift 各 O(1) → 实际开销远低于 n。
• 物化是 lazy 的：多次编辑只在消费者读 tree/zones 时一次性付 O(n)，

默认 session diff 路径额外带有硬预算：root 层一旦超限会直接 whole-tree conservative fallback；nested 细化阶段超限则保留 root patch 形状并退化成 root splice ops。也就是说，最坏情况不再继续为“更小 patch”支付无界代价。 这些预算由内部 DiffBudgetState 显式累计；超限不是异常，而是正常控制流上的“立即粗化”分支。 另外，当本次编辑命中增量路径时，root 级精细 diff 也会先限缩到增量 dirty zone 对应的 source window，再在这个局部窗口内做 anchor / nested refinement；因此默认常态成本更接近 O(W_dirty + T_diff_local)，而不是对整棵 root tree 继续细化。 如果你关心这是从哪个版本开始成为默认行为，见 版本语义说明。 不读则不付。

• Session 开销是纯常数——不论文档多长，策略门控和采样都在 O(1) 内完成。

三个与增量解析特有的最坏轴：

1. 最坏脏窗扩展：每次扩展都刚好不稳定

构造方式：每个 zone 的右边界在编辑后恰好与下一个 zone 的解析结果不一致， 导致 reparsedEnd ≠ dirtyEndNew，每轮扩展 1 个 zone。

设 Z 个 zone 全部被纳入脏窗，第 i 轮窗口宽度 W_i 单调递增。 若无 budget 守卫，总成本 = Σ W_i = O(Z · W_max) → 可达 O(n²)。

但 cumulativeBudget = max(2n, 1024) 保证 Σ W_i ≤ 2n 后立即 bail out：

路径 A：Σ W_i ≤ 2n              → T ≤ O(n)
路径 B：Σ W_i > 2n → full rebuild → T = Θ(n)

结论：脏窗扩展的最坏开销 = O(n)，不会出现二次方。

2. 最坏 seam probe：巨型 zone 使 probe 窗口接近 n

构造方式：文档只有 1–3 个 zone（如一段超长纯文本），probe 窗口 probeEndOld − probeStartOld 接近 n。

1.2.4 注： 低 zone 守卫（prevZones.length ≤ 1，updateIncrementalInternal(...)） 会在 zone 数 ≤ 1 时直接走全量重建，跳过增量路径。因此"仅 1 个巨型 zone" 的极端情况在实践中不再命中 seam probe——而是在守卫处就被截断。但若 zone 数 = 2–3， probe 窗口仍可能很大。

probe 重解析开销 = O(n)，签名比对 ≤ O(4096) = O(1)。

即使 probe 重解析了整个文档，probeSliceBytes 仅是信息上报， 不累加到 cumulativeReparsedBytes——但 probe 重解析本身就是对 newSource 子串的全量 parse，开销 Θ(W_probe)。 在 W_probe → n 时，probe 开销 = O(n)，与 full rebuild 同量级。

此情景下增量解析不比全量快——但也不比全量慢（O(n) vs Θ(n)）。 这是合理的退化：zone 太少意味着文档结构缺乏可复用的分界点。

3. 最坏 fingerprint 失配：每次编辑都带新 options

构造方式：每次 applyEdit 传入一个 handlers/syntax/allowForms 不同的 options， 使 previousOptionsFingerprint !== nextOptionsFingerprint （incremental.ts:1076），直接触发 fullRebuild()。

每次 full rebuild = parseIncremental(newSource) = Θ(n)。 这是设计预期行为——options 变化意味着解析规则改变，旧 zone 不可信， 必须重建。Session 的 maybeAdaptPolicy 会检测到高 fallback rate 并切换 到 full-only 策略（incremental.ts:1307），避免无意义的增量尝试开销。