正則表達(dá)式這玩意兒寫(xiě)的時(shí)候感覺(jué)自己就是語(yǔ)言學(xué)家調(diào) bug 的時(shí)候又覺(jué)得自己像個(gè)算命先生。尤其面對(duì)那種一長(zhǎng)串(?...)、(?!...)、嵌套分組、堆了七八個(gè)量詞的老古董正則你很難說(shuō)清楚它到底在干什么、為什么這一段匹配上了、那一段又吞了字符。去年我就在這種狀態(tài)里憋了很久最后決定動(dòng)手寫(xiě)一個(gè)工具叫ReaRegular Expression Assistant。它的核心能力不是幫你“驗(yàn)證正則對(duì)不對(duì)”而是把正則從字符串到匹配結(jié)果的每一步都拆開(kāi)以語(yǔ)法樹(shù)、匹配軌跡、回溯路徑的方式攤在眼前。這篇文章就把 Rea 的設(shè)計(jì)思路、解析器實(shí)現(xiàn)、執(zhí)行引擎可視化以及我實(shí)測(cè)中踩過(guò)的幾個(gè)深坑完整梳理一遍。如果你也經(jīng)常被復(fù)雜正則困住或者想做一個(gè)類似的“看得見(jiàn)執(zhí)行過(guò)程”的開(kāi)發(fā)者工具這篇應(yīng)該能給你不少能直接用的方案。1. 為什么我動(dòng)手寫(xiě) Rea市面上沒(méi)有講清楚正則的調(diào)試工具1.1 正則難讀的本質(zhì)你不是不會(huì)寫(xiě)是看不到它的結(jié)構(gòu)很多人覺(jué)得正則難是因?yàn)橹苯影岩淮址?dāng)成了“規(guī)則本身”。但正則其實(shí)是一門(mén)微型語(yǔ)言它從用戶輸入到最終匹配至少要經(jīng)過(guò)兩層解釋第一層是字符串層也就是你肉眼看到的那串字符第二層是語(yǔ)法層它要把*、、{}、[]、()、^、$這些東西識(shí)別成量詞、字符組、分組、斷言第三層才是執(zhí)行層也就是用語(yǔ)法樹(shù)去和目標(biāo)文本做狀態(tài)匹配。問(wèn)題在于市面上絕大多數(shù)正則工具只給你輸入框、測(cè)試文本、匹配結(jié)果列表三個(gè)東西。你看到的是“匹配了”或者“沒(méi)匹配”但看不到匹配引擎在中間到底走了哪條路。比如這個(gè)很常見(jiàn)的密碼校驗(yàn)正則^(?.*\d)(?.*[a-z])(?.*[A-Z]).{8,16}$它能在大多數(shù)工具里正常工作但如果你想知道“為什么第二個(gè)斷言失敗”工具只會(huì)在原地轉(zhuǎn)一圈給個(gè)淡淡的“無(wú)匹配”。正則本身成了一個(gè)黑盒調(diào)試就變成了盲猜。Rea 想解決的就是這件事把黑盒打開(kāi)。它會(huì)把正則解析成語(yǔ)法樹(shù)按分組、量詞、斷言的邏輯層級(jí)展開(kāi)然后按執(zhí)行引擎的每一步把當(dāng)前匹配位置、捕獲組快照、嘗試過(guò)的分支、回溯跳轉(zhuǎn)都記錄下來(lái)最后在界面上用“步驟列表 文本進(jìn)度條 回溯連線”的方式回放。這樣一來(lái)正則不再是猜謎而是有跡可循的調(diào)試對(duì)象。1.2 一個(gè)案例說(shuō)明現(xiàn)有工具的不足我在某個(gè)日志清洗項(xiàng)目里遇到過(guò)一條線上規(guī)則^(?:[^,]),(\d{4}-\d{2}-\d{2}),(.*)$意圖是從逗號(hào)分隔的日志行里取出日期和剩余內(nèi)容。工具測(cè)試時(shí)規(guī)則是通的但到了生產(chǎn)里有一批行死活匹配不上。后來(lái)逐行看發(fā)現(xiàn)某些日志的時(shí)間字段里多了個(gè)空格比如2024-01-02 03:04:05更關(guān)鍵的是前面有個(gè)字段本身包含逗號(hào)導(dǎo)致[^,]把后面的結(jié)構(gòu)全打亂了。這種問(wèn)題用現(xiàn)成工具很難定位。你看到“沒(méi)匹配”三個(gè)字但到底是因?yàn)槿掌诟袷藉e(cuò)了、字段分隔符不對(duì)、還是分組量詞吃掉了不該吃的字符沒(méi)有執(zhí)行軌跡你只能繼續(xù)加日志、改正則、再測(cè)反復(fù)試錯(cuò)。Rea 的定位就是把這個(gè)調(diào)試過(guò)程從“試”變成“看”讓引擎每走一步都留痕。1.3 Rea 的目標(biāo)用戶和使用方式Rea 主要面向幾類人常年寫(xiě)復(fù)雜正則的后端、數(shù)據(jù)開(kāi)發(fā)需要在規(guī)則提交前快速確認(rèn)執(zhí)行路徑做爬蟲(chóng)、日志解析、網(wǎng)絡(luò)安全策略的工程師正則往往就是核心邏輯搞錯(cuò)一次就全線崩帶新人的團(tuán)隊(duì)可以把 Rea 當(dāng)教學(xué)工具展示什么是回溯、什么是零寬斷言、為什么貪婪匹配會(huì)“吞掉”后面的部分想自己實(shí)現(xiàn)迷你正則引擎的人Rea 的解析和執(zhí)行代碼本身就是一份可以拆著看的參考。它不是用來(lái)替代常規(guī)正則測(cè)試器的。常規(guī)工具負(fù)責(zé)“結(jié)果對(duì)不對(duì)”Rea 負(fù)責(zé)“為什么對(duì)、為什么錯(cuò)、瓶頸在哪”。在實(shí)際使用里這兩者配合起來(lái)效率最高。2. Rea 的架構(gòu)設(shè)計(jì)為什么我要自己寫(xiě)一個(gè)解析器而不是復(fù)用現(xiàn)成正則引擎2.1 四層架構(gòu)詞法層、語(yǔ)法層、執(zhí)行層、渲染層Rea 的整體結(jié)構(gòu)分成四層每一層職責(zé)單一數(shù)據(jù)傳輸方向也很明確。層級(jí)主要職責(zé)輸入輸出詞法層把正則字符串切成有意義的最小單元正則源字符串Token 數(shù)組語(yǔ)法層把 Token 按優(yōu)先級(jí)組裝成 ASTToken 數(shù)組語(yǔ)法樹(shù)節(jié)點(diǎn)執(zhí)行層用 AST 模擬正則匹配過(guò)程并記錄步驟AST 待測(cè)文本步驟記錄數(shù)組渲染層把 AST 和步驟記錄可視化步驟記錄 AST界面交互展示這樣分層的好處是每一層都可以單獨(dú)測(cè)試。詞法層不關(guān)心語(yǔ)法對(duì)不對(duì)語(yǔ)法層不關(guān)心文本匹配執(zhí)行層只關(guān)心狀態(tài)遷移渲染層只關(guān)心怎么把數(shù)據(jù)畫(huà)出來(lái)。后面我排查引擎行為不一致的問(wèn)題時(shí)基本都能快速定位到具體某層而不是整鍋粥一塊煮。2.2 為什么選 TypeScript 而不是 Python 后端 網(wǎng)頁(yè)前端一開(kāi)始我確實(shí)想過(guò)用 Python 做解析引擎再包一層 Web 接口前端用 Canvas 畫(huà)軌跡。但很快否了。原因有三個(gè)第一Rea 的核心交互發(fā)生在瀏覽器里從輸入正則到看到軌跡最好是在一個(gè)頁(yè)面內(nèi)完成不要有網(wǎng)絡(luò)往返。純前端的 TypeScript 方案最干凈打開(kāi)頁(yè)面即用也能直接做成離線工具。第二正則的方言差異很大。JavaScript 自己就有 ECMAScript 正則語(yǔ)義如果后端用 Python 的regex庫(kù)做解析那 Rea 展示的行為和用戶瀏覽器里的實(shí)際行為就會(huì)出現(xiàn)差異。干脆直接用 TypeScript 按 ECMAScript 語(yǔ)義實(shí)現(xiàn)一個(gè)小型引擎反而能讓“工具行為”和“用戶環(huán)境行為”保持更近。第三調(diào)試工具本身得容易調(diào)試。TypeScript 有完整的類型定義AST 節(jié)點(diǎn)的結(jié)構(gòu)、步驟記錄的數(shù)據(jù)結(jié)構(gòu)都可以用類型約束起來(lái)改起來(lái)不容易改出隱蔽的運(yùn)行時(shí)錯(cuò)誤。2.3 為什么不直接復(fù)用現(xiàn)成的解析庫(kù)社區(qū)里確實(shí)有很好的正則解析庫(kù)比如regexpp、regexp-tree這些能生成標(biāo)準(zhǔn) AST也省很多事。但我最終還是自己寫(xiě)了解析器。原因很實(shí)際現(xiàn)成庫(kù)給出的 AST 偏向“規(guī)范正確”但不太照顧“可視化友好”。Rea 的語(yǔ)法樹(shù)既要做結(jié)構(gòu)展示又要和執(zhí)行引擎的步驟一一對(duì)應(yīng)。我希望每個(gè)節(jié)點(diǎn)上都掛著stepIndex、capturesAffected這類執(zhí)行期信息還要在渲染時(shí)能給分組、量詞、斷言分別上色。自己生成 AST意味著我能完全控制節(jié)點(diǎn)類型和副作用標(biāo)注。當(dāng)然自己寫(xiě)解析器不是逞能。我的實(shí)現(xiàn)目標(biāo)很明確覆蓋 ECMAScript 正則的常見(jiàn)語(yǔ)法子集包括字符類、分組、命名捕獲、非捕獲分組、前瞻斷言、后顧斷言、量詞和分支就好。像復(fù)雜的vflag Unicode 集合運(yùn)算這種極少數(shù)用到的特性我直接選擇不支持并在界面上給出“暫不支持”的提示。與其做個(gè)半吊子支持不如明確邊界把核心路徑打磨穩(wěn)。2.4 執(zhí)行引擎的定位不是追求性能而是追求“可觀察”Rea 的執(zhí)行引擎不需要像原生 V8 正則引擎那樣快它的核心指標(biāo)是每個(gè)決策都要能記錄下來(lái)。所以我實(shí)現(xiàn)的是基于 AST 的遞歸回溯模擬器每個(gè)節(jié)點(diǎn)進(jìn)入、嘗試、成功、失敗、回溯都會(huì)產(chǎn)生一條步驟記錄。這種實(shí)現(xiàn)方式在很短文本上性能完全夠用。因此我在 Rea 里留了一條默認(rèn)保護(hù)線待測(cè)文本長(zhǎng)度超過(guò) 5000 字符或者步驟數(shù)超過(guò) 5 萬(wàn)步就停止執(zhí)行并給出提示。這個(gè)限制不是偷懶是考慮到瀏覽器渲染壓力同時(shí)也是為了讓用戶意識(shí)到一個(gè)正則跑出幾萬(wàn)步本身就是需要警惕的信號(hào)。3. 解析器實(shí)現(xiàn)從一串字符串到一棵語(yǔ)法樹(shù)3.1 詞法層先切出最小單元詞法層做的事情很簡(jiǎn)單把源字符串掃一遍根據(jù)當(dāng)前字符是不是\、是不是[、是不是(來(lái)切出不同類型 token。我定義的基礎(chǔ) token 類型大概是這樣的type TokenType | char // 普通字符 | escape // \d \w \s \n \uXXXX 等轉(zhuǎn)義 | classStart // [ | classEnd // ] | groupStart // ( | groupEnd // ) | charClassEnd? // 用不到 | quantifier // * ? { | alternation // | | anchor // ^ $ | lookahead // (? (?! 等 | lookbehind // (? (?!詞法需要特別注意轉(zhuǎn)義字符。比如\d應(yīng)該作為一個(gè)Escapetoken它的值是d類型是“數(shù)字類”\.也是一個(gè)Escapetoken但語(yǔ)義是“轉(zhuǎn)義后的點(diǎn)字符”。轉(zhuǎn)義后面跟著什么字符決定了這個(gè) token 到底代表一類字符還是代表一個(gè)普通字面字符這個(gè)判斷放到語(yǔ)法層再做會(huì)更清晰。3.2 語(yǔ)法層用遞歸下降處理優(yōu)先級(jí)正則的優(yōu)先級(jí)從高到低大約是原子字符、字符類、分組 量詞 連接順序拼接 分支|。因此我用了遞歸下降解析器四個(gè)方法互相調(diào)用class RegexParser { private tokens: Token[]; private pos: number 0; parse(): Node { const expr this.parseAlternation(); if (this.pos ! this.tokens.length) { throw new Error(Unexpected token at position ${this.pos}); } return expr; } private parseAlternation(): Node { const children [this.parseSequence()]; while (this.match(alternation)) { children.push(this.parseSequence()); } return children.length 1 ? children[0] : { type: Alternation, children, captures: [] }; } private parseSequence(): Node { const children: Node[] []; while (!this.check(groupEnd) !this.check(alternation) !this.isEnd()) { children.push(this.parseRepeat()); } return children.length 1 ? children[0] : { type: Sequence, children }; } private parseRepeat(): Node { const atom this.parseAtom(); if (this.check(quantifier)) { const q this.eat(quantifier) as QuantifierToken; return { type: Repeat, atom, min: q.min, max: q.max, greedy: q.greedy, }; } return atom; } private parseAtom(): Node { const token this.peek(); // 根據(jù) token 類型分別處理普通字符、轉(zhuǎn)義類、字符類、分組、斷言 } }這個(gè)結(jié)構(gòu)很經(jīng)典但對(duì)正則來(lái)說(shuō)有幾個(gè)容易寫(xiě)錯(cuò)的地方。最典型的是分組解析左括號(hào)(后面可能是?、?!、?:、?name、?、?!這些尾巴必須在同一層處理干凈。我把所有分組入口都集合在parseAtom里private parseGroup(): GroupNode { this.eat(groupStart); const start this.prevToken(); let type: GroupType capturing; let name: string | undefined; if (this.peek().type flag) { const flag this.eat(flag); if (flag.value ?:) type noncapturing; if (flag.value ?) type lookahead; // 肯定前瞻 if (flag.value ?!) type negativeLookahead; if (flag.value ?) type lookbehind; if (flag.value ?!) type negativeLookbehind; // ?name 要單獨(dú)解析 } const body this.parseAlternation(); this.eat(groupEnd); return { type: Group, groupType: type, name, body, // 捕獲組編號(hào)在整棵 AST 構(gòu)建完成后統(tǒng)一分配 }; }這里有一個(gè)非常容易踩的坑命名捕獲組(?name...)的前綴?和后顧斷言(?...)的前綴?只差一個(gè)字符。詞法層如果分開(kāi)處理必須做到最長(zhǎng)的匹配優(yōu)先。我在詞法掃描時(shí)看到?會(huì)把后面的字符一起拿到看第三個(gè)字符是、!還是別的。如果是或!就是后顧斷言否則就當(dāng)作命名分組開(kāi)始。3.3 捕獲組編號(hào)的分配時(shí)機(jī)正則里捕獲組編號(hào)有其固定規(guī)則按(在正則字符串中出現(xiàn)的順序編號(hào)從左到右遇到普通捕獲組就遞增。非捕獲組(?:...)不參與編號(hào)但后顧斷言、前瞻斷言里的捕獲組卻參與編號(hào)。Rea 的做法是先完整生成 AST然后做一次后序遍歷給分組節(jié)點(diǎn)統(tǒng)一分配捕獲組索引。索引分配的信息會(huì)保存在 AST 節(jié)點(diǎn)上執(zhí)行引擎在記錄捕獲組快照時(shí)直接讀取。這個(gè)設(shè)計(jì)避免了在解析過(guò)程中動(dòng)態(tài)編號(hào)造成的狀態(tài)混亂尤其當(dāng)分組嵌套很深時(shí)后序遍歷比邊解析邊編號(hào)要穩(wěn)得多。3.4 字符類內(nèi)部的“第二套語(yǔ)法”字符類[...]內(nèi)部和外部的語(yǔ)法規(guī)則完全不同。普通上下文里.就是任意字符就是量詞但在[]里大部分元字符都失去特殊含義只是加號(hào)本身-在中間是范圍連接符在首尾或轉(zhuǎn)義后是普通字符。^出現(xiàn)在[后面第一個(gè)位置表示取反出現(xiàn)在其他地方就是普通字符。Rea 的詞法層會(huì)單獨(dú)維護(hù)一個(gè)“字符類上下文模式”。進(jìn)入[后詞法不再識(shí)別量詞、分支、分組而只識(shí)別普通字符、轉(zhuǎn)義字符、范圍符號(hào)-、以及結(jié)尾的]。這樣函數(shù)雖然多了一個(gè)狀態(tài)分支但后續(xù)解析邏輯清爽很多。4. 可視化執(zhí)行引擎把回溯變成看得見(jiàn)的軌跡4.1 回溯的本質(zhì)是選擇點(diǎn)的撤銷回溯是正則引擎最核心、也最讓人頭疼的機(jī)制。很多人的概念是“匹配失敗了就回溯”其實(shí)回溯發(fā)生在“當(dāng)前路徑匹配不下去時(shí)回到最近一個(gè)還能選其他路的選擇點(diǎn)”。想理解回溯可以把正則匹配想象成走迷宮。你到了一個(gè)岔路口左邊墻上有標(biāo)記“這是分叉點(diǎn)”你選擇走左岔路。走了幾十米發(fā)現(xiàn)是死胡同于是退回到岔路口撿起沒(méi)走過(guò)的右岔路再走。回溯的成本不一定高但如果在同一個(gè)分叉點(diǎn)反復(fù)試、試完又回到上個(gè)分叉點(diǎn)、疊了好幾層量詞路徑數(shù)量就會(huì)爆炸。Rea 的可視化引擎核心就是記錄每個(gè)分叉點(diǎn)的“打開(kāi)/關(guān)閉”動(dòng)作。每當(dāng)一個(gè)節(jié)點(diǎn)嘗試一個(gè)分支就產(chǎn)生一條try步驟如果分支失敗就產(chǎn)生一條backtrack步驟。這樣用戶能看到引擎到底做了幾次選擇、每次選擇消耗了什么字符。4.2 步驟記錄器的數(shù)據(jù)結(jié)構(gòu)執(zhí)行引擎在遞歸回溯過(guò)程中會(huì)產(chǎn)生海量中間信息但如果全部記錄性能會(huì)很差。Rea 對(duì)記錄內(nèi)容做了取舍不記錄每一次字符比較而是記錄“節(jié)點(diǎn)級(jí)事件”。一個(gè)CharNode的比較只記錄一次成功或失敗一個(gè)量詞的每次重復(fù)循環(huán)都記錄為一次迭代一個(gè)斷言節(jié)點(diǎn)記錄其成功/失敗以及結(jié)束位置。核心步驟類型如下interface Step { type: enter | try | match | fail | backtrack | end; nodeId: number; // AST 節(jié)點(diǎn)唯一 id nodeLabel: string; // 便于展示的節(jié)點(diǎn)描述 position: number; // 進(jìn)入該節(jié)點(diǎn)時(shí)的文本位置 nextPosition: number; // 離開(kāi)該節(jié)點(diǎn)后的文本位置 captureSnapshot: CaptureSnapshot; // 當(dāng)前捕獲組快照 stepIndex: number; // 全局遞增步驟號(hào) depth: number; // 遞歸深度渲染時(shí)用來(lái)做縮進(jìn) }捕獲組快照不能每次都深拷貝整個(gè)對(duì)象那樣文本稍長(zhǎng)就會(huì)內(nèi)存爆炸。我采用了“按需記錄”的方式只在進(jìn)入捕獲組失敗、退出捕獲組、或者回溯發(fā)生時(shí)記錄當(dāng)前捕獲組狀態(tài)。每一步事件都帶一個(gè)引用指向“上一次發(fā)生了捕獲變化的快照”渲染層再按需合并出完整狀態(tài)。這個(gè)優(yōu)化在回放幾千步的匹配過(guò)程時(shí)非常關(guān)鍵。4.3 執(zhí)行器代碼骨架執(zhí)行器本質(zhì)上就是遍歷 AST 的遞歸函數(shù)。以一個(gè)簡(jiǎn)化版為例function tryNode(node: Node, pos: number, ctx: MatchContext): number | null { switch (node.type) { case Char: { const ok ctx.text[pos] node.value; recordStep(try, node, pos, ok ? pos 1 : pos, ctx); return ok ? pos 1 : null; } case Star: case Plus: case Repeat: { return tryQuantifier(node, pos, ctx); } case Sequence: { let cur pos; for (const child of node.children) { const next tryNode(child, cur, ctx); if (next null) { recordStep(backtrack, node, cur, cur, ctx); return null; } cur next; } return cur; } case Group: { if (node.groupType capturing) { ctx.captureStart(node.index); } const endPos tryNode(node.body, pos, ctx); if (node.groupType capturing endPos ! null) { ctx.captureEnd(node.index, endPos); } return endPos; } default: return null; } }注意這里Sequence一旦遇到子節(jié)點(diǎn)失敗直接返回失敗由上層決定是否回溯。真正選擇點(diǎn)的管理放在Alternation和Repeat節(jié)點(diǎn)里。比如Alternation需要依次嘗試每個(gè)子分支失敗后記錄一次backtrack再試下一個(gè)分支case Alternation: { for (const child of node.children) { const result tryNode(child, pos, ctx); if (result ! null) return result; recordStep(backtrack, node, pos, pos, ctx); } return null; }量詞的邏輯更麻煩。因?yàn)樨澙妨吭~會(huì)先盡可能多匹配匹配到上限后再逐漸讓出字符做后續(xù)匹配。這個(gè)“讓出字符”就是回溯在量詞上的表現(xiàn)。Rea 在tryQuantifier里用一個(gè)循環(huán)先按貪婪策略吞字符吞到吞不下為止然后把一次次的“吞入”和后續(xù)“回吐”都記錄下來(lái)function tryQuantifier(node: RepeatNode, pos: number, ctx: MatchContext): number | null { let count 0; let cur pos; const attempts: number[] []; while (count (node.max ?? Infinity) (node.min 0 || count node.min)) { const next tryNode(node.atom, cur, ctx); if (next null) break; attempts.push(cur); cur next; count; } // 貪婪時(shí)先嘗試?yán)^續(xù)多匹配 while (count (node.max ?? Infinity)) { const next tryNode(node.atom, cur, ctx); if (next null) break; attempts.push(cur); cur next; count; } // 回退嘗試減少重復(fù)次數(shù) while (count node.min) { if (node.min 0 || count node.min) { const rest tryNode(node.next, cur, ctx); // 簡(jiǎn)化真實(shí)的遞歸結(jié)構(gòu)需要掛載 next 指針 if (rest ! null) return rest; recordStep(backtrack, node, cur, cur, ctx); } count--; cur count 0 ? attempts[count - 1] : pos; } return null; }實(shí)際引擎里node.next不像上面這么簡(jiǎn)單因?yàn)?AST 是樹(shù)結(jié)構(gòu)處理量詞時(shí)需要把“匹配完重復(fù)內(nèi)容后的剩余部分”作為 continuation 傳入否則很難正確回溯。我在實(shí)現(xiàn)里給每個(gè)節(jié)點(diǎn)增加next指針結(jié)構(gòu)上變成一個(gè)“AST 鏈?zhǔn)?continuation”的組合執(zhí)行器在量詞回退時(shí)就能把當(dāng)前位置交給后續(xù)節(jié)點(diǎn)繼續(xù)嘗試。node.next這個(gè)概念是 Rea 能正確可視化回溯的關(guān)鍵。如果不做 continuation只靠遞歸返回值來(lái)回退那么一旦量詞內(nèi)部失敗上層就傻眼了根本不知道還有“少吞一個(gè)字符再試后續(xù)”這一條路。4.4 一個(gè)完整案例的回放拿a(b|c)*d匹配abccd來(lái)演示。這個(gè)正則的邏輯是先匹配a然后(b|c)*可以匹配零個(gè)或多個(gè)b或c最后匹配一個(gè)d。在 Rea 步驟列表里你會(huì)看到近似這樣的事件序列步驟事件節(jié)點(diǎn)位置說(shuō)明0enterSequence0進(jìn)入整個(gè)表達(dá)式1matchChara0 - 1成功消耗 a2enterRepeat (bc)*13tryGroup (bc)1 - 24tryGroup (bc)2 - 35tryGroup (bc)3 - 46tryGroup (bc)4 - 57backtrackRepeat (bc)*5 - 48matchChard4 - 5后續(xù) d 匹配成功9endSequence5整體匹配完成這里第 7 步就是關(guān)鍵。用戶從前到后看會(huì)覺(jué)得“明明文本第三個(gè)字符就是 d為什么引擎還要先吞掉再回退”因?yàn)檎齽t里的貪婪量詞在不了解后續(xù)節(jié)點(diǎn)的情況下只能先盡可能多吞吞到吞不動(dòng)了再交還。這個(gè)“交還”動(dòng)作就是回溯也是很多正則性能問(wèn)題的來(lái)源。通過(guò) Rea 的步驟列表新手能直觀看到*在*和后面如果還跟著其他必須匹配的內(nèi)容很容易出現(xiàn)“先多吃再吐出來(lái)”的現(xiàn)象。如果后續(xù)內(nèi)容很多回溯次數(shù)會(huì)呈指數(shù)級(jí)增長(zhǎng)。5. 實(shí)測(cè)中的坑正則語(yǔ)義和 Rea 表現(xiàn)不一致的五個(gè)修復(fù)5.1 斷言和普通節(jié)點(diǎn)對(duì)“當(dāng)前匹配位置”的處理完全不同剛開(kāi)始實(shí)現(xiàn)斷言時(shí)我的執(zhí)行器統(tǒng)一用“節(jié)點(diǎn)結(jié)束位置”來(lái)推進(jìn)position。這在普通字符、分組、量詞上沒(méi)問(wèn)題但碰到(?...)、(?...)就錯(cuò)了。斷言不會(huì)消耗字符它從左到右檢查內(nèi)部子表達(dá)式能不能匹配能匹配就返回成功但匹配位置始終保持在斷言開(kāi)始的位置。我第一次實(shí)測(cè)時(shí)發(fā)現(xiàn)a(?b)c匹配abc的時(shí)候Rea 展示的步驟是“a 之后斷言 b 成功c 直接從位置 2 開(kāi)始匹配”而斷言的內(nèi)部匹配“從位置 1 到位置 2 消耗了 b”也被記錄成了普通消耗。這就導(dǎo)致用戶看到的位置推進(jìn)和實(shí)際引擎行為對(duì)不上。修復(fù)方式是給斷言節(jié)點(diǎn)單獨(dú)立一條規(guī)則內(nèi)部執(zhí)行完成后位置必須恢復(fù)為斷言入口位置。Rea 的步驟記錄里還會(huì)額外標(biāo)記“零寬斷言不消耗字符”讓用戶一眼看懂為什么斷言里的 b 沒(méi)有影響后面的 c。5.2 捕獲組編號(hào)在非捕獲組和后顧斷言里的偏移正則里有一個(gè)新手極其容易寫(xiě)錯(cuò)的地方(?:...)不算捕獲組編號(hào)但前瞻/后顧斷言里的(...)要算。比如(?(a))\1中\(zhòng)1指的是前瞻里的捕獲組(?:(b))\2則是非法的因?yàn)榉遣东@組里即便有(b)編號(hào)也只會(huì)是 1不存在 2。Rea 的后序遍歷編號(hào)時(shí)只是在普通Group節(jié)點(diǎn)上遞增編號(hào)。但我一開(kāi)始把斷言內(nèi)部的Group和后顧斷言內(nèi)部的子表達(dá)式也統(tǒng)一編號(hào)了這導(dǎo)致(?(a))b的捕獲組編號(hào)和原生引擎不一致。測(cè)試時(shí)我拿一個(gè)帶后顧斷言的復(fù)雜正則一對(duì)一對(duì)比連續(xù)錯(cuò)了幾十步才意識(shí)到問(wèn)題。后來(lái)我把“編號(hào)分配”和“執(zhí)行路徑”分開(kāi)考慮只要 AST 節(jié)點(diǎn)是Group且類型為capturing無(wú)論它出現(xiàn)在斷言內(nèi)部還是普通分支都參與編號(hào)但執(zhí)行時(shí)斷言內(nèi)部的捕獲組快照要臨時(shí)保存斷言失敗時(shí)恢復(fù)原狀。這才能和原生語(yǔ)義保持一致。5.3 指數(shù)級(jí)回溯不能被當(dāng)成普通步驟Rea 做到一半時(shí)我拿(a)$配一個(gè)aaaaaaaaaaaaaaaaaaaaaaaaX。這個(gè)正則自己會(huì)跑出天文數(shù)字一樣的步驟因?yàn)閍可以分成很多組又可以讓每組重復(fù)多次幾乎每一種分組方式都要試一遍。如果引擎老老實(shí)實(shí)把所有步驟都記錄到數(shù)組里頁(yè)面直接卡死。這里我設(shè)置了一個(gè)非常務(wù)實(shí)的保護(hù)步驟數(shù)超過(guò) 50000 就中止執(zhí)行并且單獨(dú)標(biāo)記“檢測(cè)到疑似災(zāi)難性回溯”。用戶看到的現(xiàn)象不是普通的失敗列表而是一條醒目的警告當(dāng)前正則可能在更長(zhǎng)文本上導(dǎo)致嚴(yán)重性能問(wèn)題。這個(gè)警告本身就是調(diào)試結(jié)論遠(yuǎn)比“無(wú)匹配”三個(gè)字有價(jià)值。從實(shí)現(xiàn)上講50000 步的保護(hù)閾值并不是隨便定的。我實(shí)測(cè)過(guò)普通復(fù)雜正則在一個(gè)幾十字符的文本上通常只跑幾百到幾千步50000 足以覆蓋絕大多數(shù)正常場(chǎng)景超過(guò)這個(gè)數(shù)大概率是正則本身出了問(wèn)題。5.4 字符類中]和-的邊界沒(méi)有想象中簡(jiǎn)單我一開(kāi)始處理[]時(shí)過(guò)于想當(dāng)然在字符類里遇到]就結(jié)束遇到-就當(dāng)作范圍連接符。但實(shí)際測(cè)[]-]這種正則時(shí)徹底翻車。這個(gè)正則是匹配]或-兩個(gè)字符之一的。它的結(jié)構(gòu)是[開(kāi)始第一個(gè)字符是]但因?yàn)閉緊跟在[后面所以它不應(yīng)該被視為結(jié)束符然后-是普通字符最后一個(gè)]才是結(jié)束符。詞法層必須知道“當(dāng)前是不是緊跟在[或[^之后”。只有在跟在開(kāi)始位置的字符才是普通字符否則才會(huì)作為結(jié)束符處理。類似地[a-]里的-在結(jié)尾沒(méi)有構(gòu)成范圍也只是普通字符。這些邊界情況在正則文檔里只有一兩句話在 Rea 里卻是一整組測(cè)試用例。5.5 命名分組和反向引用的映射關(guān)系Rea 支持(?name...)和\kname。一開(kāi)始我把名字和編號(hào)映射關(guān)系存在一個(gè)全局 Map 里解析一個(gè)正則、清空一次。結(jié)果遇到命名分組在后顧斷言里、并且正則主體里還有同名分組時(shí)Map 被覆蓋了。雖然 ECMAScript 規(guī)范不允許同一個(gè)正則里出現(xiàn)重復(fù)的命名分組但執(zhí)行到斷言內(nèi)部時(shí)捕獲組狀態(tài)是嵌套的不能簡(jiǎn)單使用同一個(gè)對(duì)象。我最后改成每個(gè)捕獲組快照包含兩份信息一份是編號(hào)索引到字符串位置的數(shù)組另一份是名字到編號(hào)的 Map。斷言執(zhí)行時(shí)這兩份數(shù)據(jù)一起進(jìn)入獨(dú)立棧幀。這樣即使斷言內(nèi)部和外部都有命名分組回退時(shí)也不會(huì)互相污染。5.6 與原生正則行為對(duì)齊的驗(yàn)證方法做這個(gè)工具最大的風(fēng)險(xiǎn)是自己實(shí)現(xiàn)了一個(gè)“看起來(lái)挺對(duì)”的引擎但實(shí)際行為和瀏覽器里的new RegExp不一致。那 Rea 不但沒(méi)用還會(huì)誤導(dǎo)人。所以 Rea 里內(nèi)置了一組對(duì)照測(cè)試把用戶輸入的正則先交給原生RegExp執(zhí)行一次拿到結(jié)果同時(shí)讓 Rea 自己的引擎執(zhí)行再比較兩者的匹配區(qū)間、捕獲組內(nèi)容是否一致。不一致時(shí)Rea 會(huì)在界面右下角彈出一條“與原生行為不一致”的提示并標(biāo)出第一個(gè)出現(xiàn)差異的步驟位置。這個(gè)機(jī)制幫我在開(kāi)發(fā)階段發(fā)現(xiàn)了很多隱蔽問(wèn)題。比如$在 ECMAScript 里默認(rèn)只匹配到文本末尾但如果設(shè)置了多行模式它還會(huì)匹配換行符之前的位置比如\b的“單詞邊界”邏輯在中文文本里和英文文本里的表現(xiàn)完全不同。這些如果不做對(duì)照測(cè)試靠人眼很難發(fā)現(xiàn)。6. Rea 在實(shí)際項(xiàng)目里的用法日志巡檢和新人培訓(xùn)6.1 用步驟回放定位日志正則的誤判我們后端有一段時(shí)間日志告警規(guī)則老出問(wèn)題。有一條規(guī)則要過(guò)濾掉所有包含SECRET關(guān)鍵字的日志行正則寫(xiě)成了^(?!.*SECRET).*$這條正則單獨(dú)的匹配結(jié)果看起來(lái)沒(méi)錯(cuò)但它有一個(gè)隱藏性能問(wèn)題負(fù)向前瞻里有個(gè).*SECRET如果失敗后續(xù)的.*還要繼續(xù)跑。在幾萬(wàn)行的日志流上跑正則引擎的回溯開(kāi)銷會(huì)被放大。用 Rea 把一條幾百字符的日志樣本放進(jìn)去回放會(huì)看到步驟數(shù)到了幾千步。原因就是負(fù)向前瞻在每個(gè)字符位置都做一次“往后找 SECRET”的嘗試找不到再前進(jìn)一個(gè)字符重復(fù)執(zhí)行?？吹竭@個(gè)軌跡之后我們把規(guī)則改成了先用indexOf做快速排除再在數(shù)據(jù)流里跑正則日志處理速度立刻上來(lái)一個(gè)數(shù)量級(jí)。Rea 不能直接替你優(yōu)化正則但老實(shí)地把每一步選擇攤開(kāi)來(lái)看優(yōu)化點(diǎn)會(huì)自己浮出來(lái)。6.2 在代碼評(píng)審和規(guī)則變更前做“執(zhí)行軌跡審查”以前評(píng)審正則改動(dòng)只能看 diff 里的正則字符串憑經(jīng)驗(yàn)判斷“這樣改應(yīng)該沒(méi)問(wèn)題”。有了 Rea 之后我們形成了一個(gè)小流程任何涉及復(fù)雜正則的改動(dòng)都要附帶一張 Rea 生成的步驟概覽截圖至少包括分支嘗試次數(shù)、最大回溯深度、捕獲組命中次數(shù)這幾個(gè)指標(biāo)。這樣做的好處是評(píng)審人不用逐字讀正則直接看數(shù)字就能判斷這次改動(dòng)是不是引入了新的性能隱患。如果一次改動(dòng)讓步驟數(shù)從 200 漲到 8000哪怕功能測(cè)試全過(guò)我也會(huì)打回去重新設(shè)計(jì)因?yàn)椴襟E數(shù)暴漲意味著后面文本一旦變長(zhǎng)引擎遲早卡死。6.3 拿 Rea 給新人講清楚“貪婪與懶惰”的區(qū)別我經(jīng)常拿 Rea 給組里新人演示貪婪量詞和懶惰量詞的區(qū)別。比如.*?這個(gè)經(jīng)典寫(xiě)法。很多測(cè)試器只告訴新人“懶惰量詞盡量少匹配”但說(shuō)不清“盡量少”到底是怎么做到的。在 Rea 里跑a.*?b匹配axxbyyb能看到引擎先讓.*?匹配零個(gè)字符然后立刻嘗試匹配b失敗于是回退讓.*?多匹配一個(gè)字符再嘗試匹配b……重復(fù)這個(gè)過(guò)程直到找到第一個(gè)能接上b的位置。這個(gè)逐步“擠牙膏”的過(guò)程在步驟列表里一目了然比任何文字說(shuō)明都直觀。6.4 可擴(kuò)展的方向從匹配軌跡到自動(dòng)生成解釋Rea 現(xiàn)在的核心是“展示軌跡”但后續(xù)可以往“解釋軌跡”方向走。語(yǔ)法樹(shù)已經(jīng)結(jié)構(gòu)化了執(zhí)行步驟也已經(jīng)標(biāo)注了節(jié)點(diǎn)語(yǔ)義完全可以再加一個(gè)自然語(yǔ)言生成模塊把“當(dāng)前位置嘗試匹配數(shù)字字符失敗回溯到量詞分支”翻譯成人話。如果能生成一句話“這個(gè)正則失敗在第 12 步因?yàn)榈?3 個(gè)捕獲組沒(méi)有匹配到預(yù)期格式”那才是真正的正則老師。另一個(gè)擴(kuò)展方向是正則簡(jiǎn)化。通過(guò) AST 分析出冗余的嵌套分組、重復(fù)的字符類、不可能匹配到的分支然后給出提示。這個(gè)方向有挑戰(zhàn)但對(duì)日常維護(hù)歷史正則的人來(lái)說(shuō)價(jià)值巨大。7. 最后分享一點(diǎn)使用經(jīng)驗(yàn)Rea 開(kāi)發(fā)到現(xiàn)在我自己最深的體會(huì)是正則調(diào)試工具真正的價(jià)值不在于“多炫”而在于“把不確定性變成確定性”。以前遇到一個(gè)復(fù)雜正則我習(xí)慣先猜猜錯(cuò)就再改改完再測(cè)循環(huán)往復(fù)。現(xiàn)在我會(huì)先把正則丟進(jìn) Rea看一眼它的執(zhí)行軌跡很多時(shí)候問(wèn)題根源就在前 50 步里。如果你也想做個(gè)類似的東西我建議從一個(gè)小得多的范圍開(kāi)始先支持字符、字符類、量詞、分組這四類把可視化做好再慢慢加斷言和反向引用。不要一上來(lái)就想著完整實(shí)現(xiàn) ECMAScript 全部特性否則大概率會(huì)被邊界情況拖死。再給一個(gè)小技巧Rea 的步驟記錄里我最?？吹牟皇恰捌ヅ涑晒Α钡哪切┎襟E而是backtrack步驟?；厮菰蕉嗾f(shuō)明正則的“決策”質(zhì)量越差越值得優(yōu)化。一個(gè)正則如果回溯步驟超過(guò)總步驟的 30%基本就該重寫(xiě)了。這句話扔給團(tuán)隊(duì)里的新人比講十分鐘理論都好用。