算法与数据结构 / regex · Unicode 字符模型与一个自研引擎 / 有状态的全局匹配:g 与 lastIndex 待审核 31 / 36
g · lastIndex · 有状态匹配

有状态的全局匹配:g 与 lastIndex

g 不只是「找全部」,它让一个 regex 对象背上一个可变状态 lastIndex。这个藏在对象里的游标是一连串经典 bug 的源头,也藏着两个「为什么」的答案:空匹配为什么不会死循环,matchAll 为什么强制要 g

1 · 游标带来的跳变

g(或 y)时,testexeclastIndex 处往后找,并把它推到这次命中的末尾;找不到了就归零。于是同一个对象、同一个字符串,连续调用的结果会在真假之间循环跳变。把 g 关掉,游标恒为 0,结果就稳定了。

图 1-1 · 复用同一个 regex 对象反复调用 exec,逐次给出游标的前后变化与命中区间。可改 pattern、flags 与输入。

警示 · 把带 g 的 regex 提到循环外当常量复用、在循环里拿它做布尔判断,会因残留的 lastIndex 产生间歇性误判。只想判断是否包含就别加 g,用 includes 或不带 gtest;真要复用带 g 的对象做迭代,每轮自己把 lastIndex 复位。

2 · 空匹配为什么不死循环

a* 能匹配零个 a,也就是能匹配空。全局替换靠不停 exec 推进游标来扫完整串,可一旦某次命中是空的,游标原地不动,下次仍在同一处命中空,随即死循环。规范的破法是:命中空匹配后强制把 lastIndex 再加一。"aaabc".replace(/a*/g, "|") 得到 ||b|c|,开头那个双竖线正是空匹配留下的。

图 2-1 · /a*/g 全局替换的单步回放:纸带上标出命中区间与空匹配处,右侧代码面板高亮本步执行的行。可改输入或自动播放。

注 · 空匹配加一不是 hack 而是规范行为。RegExp.prototype[Symbol.replace]matchAll 内部都有「若本次匹配长度为 0 则游标前进一格」这条推进规则,否则任何能匹配空的 pattern(a*\b(?=))都会让全局操作卡死。空匹配本身的来历见 零宽匹配

3 · g 与 y 的分别

两者都用 lastIndex,区别只在失配时怎么办:g 允许从游标处往后扫、跳过不匹配的字符去找下一处;y 要求必须正好在游标处命中,差一个字符就直接失败并归零。

图 3-1 · 同一条 pattern 在 g 与 y 两种标志下跑满 exec 循环的命中对照。可改 pattern 与输入。

建议 · 写词法分析器时用 y:token 必须首尾相连,不许中间跳过任何字符。y 锚定游标的特性正好表达了「当前位置要么接上一个合法 token,要么就是语法错误」;用 g 反而会悄悄跳过非法字符、把错误吞掉。本仓库 自研引擎 的 token 推进就是这个语义。

4 · matchAll 取代手写循环

要拿到全部命中含捕获组,老写法是手动 while ((m = re.exec(s))):得自己管游标、自己处理空匹配加一,还共享着那个有状态的对象。matchAll 把这些全托管了,每次产出一个独立的 match,且不污染传入对象的状态。

图 4-1 · 手写 exec 循环与 matchAll 的结果对照,下方现场抓一次缺 g 时 matchAll 抛出的错误。可改 pattern 与输入。

5 · 别的语言怎么选

Raku 把推进策略直接做成可选副词::g 全局不重叠,等于 JS 的默认;:ov 重叠,每个起点都试一次;:ex 穷举,每个起点配每种长度。JS 没有后两个,但它们本质就是「起点怎么挪、长度收不收」,几行代码即可现写。

图 5-1 · 同一条 pattern 在三种推进策略下的命中集合对照。可改 pattern 与输入。

注 · lastIndex 是 JS 把「全局推进」这个本可有多种选择的策略,固化成了一个挂在对象上的可变游标。好用,但记得它有状态。当 pattern 带回溯结构时,单次 exec 本身还可能炸开成指数级步数,那是 灾难性回溯 的主题。

6 · 参考文献

  1. Ecma International. ECMA-262: RegExpBuiltinExec. lastIndex 的读写时机、globalsticky 的分工,以及空匹配的推进规则。tc39.es
  2. Ecma International. ECMA-262: String.prototype.matchAll. 缺 g 时抛 TypeError 的规范依据。tc39.es
  3. MDN. RegExp.prototype.lastIndex. 游标的语义与常见陷阱。developer.mozilla.org
  4. Raku. Adverbs. :g / :ov / :ex 三种推进策略的定义,本页第 5 节的对照来源。docs.raku.org