markdown-it 强调解析最坏情况基准样例 inline-em-worst.md 深度解析：回溯压力测试与线性时间优化

• 开发工具
• CLI

本指南以 markdown-it 仓库中 benchmark/samples/inline-em-worst.md 这一基准测试样例文件为线索，讲解它为何被设计为强调（emphasis）解析的"最坏情况"输入，并深入其背后的两阶段内联解析架构、balance_pairs配对算法与线性复杂度优化技巧，以及它在基准测试与病态输入测试中的实际用途。读完本文，你将理解 markdown-it 在*、_等强调标记上的解析策略，并能自行运行、扩展针对该样例的性能测试。

样例文件内容与设计意图

该样例文件全文仅三组输入，每组一行，分别使用不同的强调标记：

*this *is *a *worst *case *for *em *backtracking __this __is __a __worst __case __for __em __backtracking ***this ***is ***a ***worst ***case ***for ***em ***backtracking

从表面看，这只是一段每个单词前都带一个强调标记的普通文本，但它被刻意命名为inline-em-worst（inline emphasis worst case），与同目录下的 inline-em-flat.md（*this* *is* *your* *basic* *boring* *emphasis*，每个标记都正确闭合）和 inline-em-nested.md（*this *is *a *bunch* of* nested* emphases*，存在交叉嵌套）形成三档压力梯度。其设计意图可以概括为两点：

1. 制造大量"无法闭合"的开启标记：每个单词前的*/__/***后紧跟字母，其后所有后续标记都处于"无配对可寻"或"只能与前文开启标记尝试匹配"的状态，解析器必须穷举大量无效的配对尝试才能得出"没有闭合"的结论；
2. 作为基准测试的对照样本：让 benchmark 套件能测量解析器在面对这类"回溯陷阱"输入时的真实吞吐量，检验配对算法是否退化为平方级复杂度。

为什么这是强调解析的"最坏情况"：从 CommonMark 规则说起

要理解"最坏"在哪里，需要先明白 markdown-it 处理强调标记的两阶段模型。根据 docs/examples/text_decoration.md 的说明，所有"成对匹配"的内联标记（matched-pair inline marker）都遵循两遍处理：

• Tokenization（分词阶段）：只负责在源码中识别出强调标记，把每个标记字符作为独立的 text token 推入state.tokens，并在state.delimiters中登记对应的 delimiter 记录——它完全不关心标记之间是否成对；
• Post Processing（后处理配对阶段）：由balance_pairs等规则遍历 delimiter 列表，为每个开启标记寻找匹配的关闭标记，最终把 text token 改写为em_open/em_close（或strong_open/strong_close）标签。

在 tokenization 阶段，emphasis规则（见 src/rules_inline/emphasis.ts）只接受*（0x2A）和_（0x5F）两种标记，并调用state.scanDelims判断当前标记串能否作为开启或关闭标记。scanDelims的实现位于 src/rules_inline/state_inline.ts，其核心逻辑是：

• 统计从当前位置起连续相同标记的个数（count）；
• 取出标记前一字符与后一字符，判断它们是否是空白、标点或 Unicode 代理对；
• 依据 CommonMark 的 left-flanking / right-flanking 规则计算出can_open与can_close。

对于*this *is *a ...这样的输入，每个*前面是空白、后面是字母，因此每个*都被判定为"可以开启强调"（can_open为真），但整行中除最后一个标记前是空白、后是行尾（视作空白）外，其余标记都不能关闭任何已开启的强调。于是balance_pairs必须为这一长串开启标记逐一尝试寻找关闭标记，最终全部失败——这就是回溯压力的来源。

配对的线性化：balance_pairs 的两大优化

真正决定"最坏情况"是否真的最坏的地方，在 src/rules_inline/balance_pairs.ts 的processDelimiters函数中。它同时维护两个关键数据结构：

1.openersBottom（开启标记下界缓存）

const openersBottom: Record<number, number[]> = {} // 每个 marker 对应一个长度为 6 的数组，下标 = (closer.open ? 3 : 0) + (closer.length % 3)

正如源码注释所指出的，这是"此前匹配失败的较低边界"（previously calculated lower bounds, previous fails）。当某个关闭标记在扫描开启标记时全部匹配失败，它会把本次失败扫描到达的最远位置记录下来；之后遇到相同 marker、相同length % 3条件的关闭标记时，直接从该下界之上开始查找，而不是从当前 delimiter run 的头部重新扫描。这样，重复发生的"失败尝试"不会反复遍历同一个前缀区间。

2.jumps（跳转表）

const jumps: number[] = []

当一对 opener/closer 成功匹配时，算法会计算jumps[closerIdx] = closerIdx - openerIdx + lastJump，将整段已匹配区间"压缩"为一次跳跃；后续扫描可以直接越过这些已消耗的区间。源码注释特别点名了*_*_*_*_*_...这类输入——正是inline-em-worst.md所代表的模式——并说明"这是保证算法具有线性复杂度的必要条件"（This is required to make sure algorithm has linear complexity）。

此外，函数开头还维护了headerIdx与lastTokenIdx，用于判断相邻且 marker 相同的 delimiter 是否属于同一个 run：只有当标记字符相同且 token 相邻时才共享同一 header，否则把当前 closer 视为新 run 的起点。这些设计让最坏情况输入从理论上可能出现的 O(n²) 配对尝试被压制到接近 O(n)。

另一个与"最坏情况"直接相关的细节是 CommonMark 的"3 的规则"（rule of 3）：如果开启与关闭标记的长度之和是 3 的倍数，且两者长度不都是 3 的倍数，则配对非法。processDelimiters中通过(opener.length! + closer.length) % 3 === 0实现该判定，而第三组***this ***is ...（每个标记长度为 3）正是触发这条规则的高频输入。

与同目录其他样例的梯度对比

将三个强调样例放在一起看，可以清晰地识别出压力梯度设计：

benchmark.mjs会按文件名排序后依次加载samples目录下的所有样例（见 benchmark/benchmark.mjs），因此这三份文件会作为三个独立的 benchmark 任务分别测量，可以直接对比"正常输入"与"最坏输入"之间的吞吐差距，从而量化配对优化的收益。

如何在基准测试中运行该样例

仓库根目录 package.json 中定义了相关脚本，运行方式如下：

# 首次运行前安装 benchmark 依赖（tinybench 等） npm run benchmark-deps # 运行全部样例 node benchmark/benchmark.mjs # 仅运行强调相关样例（支持正则过滤，不区分大小写） node benchmark/benchmark.mjs inline-em node benchmark/benchmark.mjs worst node benchmark/benchmark.mjs em-worst

benchmark.mjs会把命令行参数转换为正则表达式，通过select()函数过滤样例（见 benchmark/benchmark.mjs）；无参数时则运行全部 27 个样例。每个样例会被依次喂给 benchmark/implementations 目录下的所有实现：

• current：默认预设，html、linkify、typographer全部开启（见 benchmark/implementations/current/index.mjs）；
• current-commonmark：commonmark预设，并替换了链接归一化函数以做"更诚实的对比"（见 benchmark/implementations/current-commonmark/index.mjs）；
• commonmark-reference与marked：外部参考实现。

输出形如：

Sample: inline-em-worst.md (126 bytes) > current x NNN ops/sec ±x.xx% (NN runs sampled) > current-commonmark x NNN ops/sec ±x.xx% (NN runs sampled)

吞吐单位 ops/sec 表示每秒可渲染该样例的次数，±后为相对误差（RME），括号内为采样次数，均由 tinybench 统计得出（见 benchmark/benchmark.mjs）。需要说明的是，实际数字取决于运行机器、Node.js 版本与 JIT 状态，建议在同一台机器上做相对对比而非跨机器比较。基准测试的更多背景可参考 docs/benchmark.md，其中指出 markdown-it 通过"单形态风格（monomorphic style）与 JIT 内联缓存"换取灵活性而不牺牲速度。

病态输入测试：从最坏样例到自动化防线

inline-em-worst.md这类输入不仅仅是 benchmark 的静态样本，其背后的回溯风险还被系统性地纳入了自动化测试。仓库在 test/markdown-it/pathological.test.mjs 中维护了一组"病态序列速度"测试，其中大量用例正是对inline-em-worst模式的极端化：

• '*'.repeat(60000) + 'a' + '*'.repeat(60000)（nested inlines）；
• '*a **a '.repeat(5000) + 'b' + ' a** a*'.repeat(5000)（nested strong emph）；
• '*a_ '.repeat(50000)（mismatched openers and closers）；
• 'a**b' + ('c* '.repeat(50000))（openers and closers multiple of 3）；
• '**_* '.repeat(50000)（emphasis**_*pattern，markdown-it 专有用例）。

这些用例会在独立的 worker 线程中运行，并设置 5 秒超时——超时即视为失败（见 test/markdown-it/pathological.test.mjs），以此防止任何改动把强调配对重新引入平方级复杂度。这些用例大部分移植自 cmark 上游的pathological_tests.py，仓库通过 support/track-ref-pathological.mjs 跟踪上游文件的 MD5 哈希（记录于 support/track-ref-pathological.json），配合pathological:track-ref与pathological:update-hash两个 npm 脚本，在上游测试集变化时给出提示。测试通过npm run test:markdown-it即可执行。

从最坏样例到自定义插件开发

理解inline-em-worst.md背后的配对机制，对编写 markdown-it 插件也有直接帮助。由于*与_的配对由内建的emphasis+balance_pairs组合完成，任何新增的成对内联标记（例如把^^text^^渲染为<small>）都应仿照这一模式，在 tokenization 规则中正确构造delimiters数组（含marker、length、end、open、close字段），并把配对工作交给balance_pairs。正如 docs/examples/text_decoration.md 所强调的："只要在 tokenization 阶段把delimiters数组构造好，开发者就不必担心balance_pairs内部的复杂性"；同时要记得在ruler2（后处理 ruler）中注册对应的 post-process 规则，因为balance_pairs只会填写end指针，真正的标签生成仍需自己的后处理函数完成。而"3 的规则"等长度判定逻辑（length属性）仅对强调类标记生效，非强调类插件可以通过把length置 0 来跳过这些检查——这一点在processDelimiters的注释中有明确说明。

结语

benchmark/samples/inline-em-worst.md 虽然只有四行文本，却是 markdown-it 性能设计的一块重要试金石：它用最简洁的输入，直击强调解析中最容易退化为平方复杂度的配对回溯问题，并促使balance_pairs实现了openersBottom缓存与jumps跳转两项线性化优化。无论是想验证解析器在极端输入下的表现、对比不同实现的速度，还是希望为自己的插件写出同样健壮的成对标记处理，这份样例及其背后的 src/rules_inline/balance_pairs.ts、src/rules_inline/emphasis.ts、test/markdown-it/pathological.test.mjs 都是值得反复研读的参考实现。

• 开发工具
• CLI