QuickJS正则引擎解剖15KiB代码如何实现完整ES2020正则支持【免费下载链接】QuickJSQuickJS is a small and embeddable Javascript engine. QuickJS sources are copyright Fabrice Bellard and Charlie Gordon.项目地址: https://gitcode.com/gh_mirrors/quick/QuickJSQuickJS 是一款小巧可嵌入的 JavaScript 引擎它内置的QuickJS 正则引擎libregexp是其中最精巧的模块之一仅约 2750 行 C 代码编译优化后体积约 16KiB却独立实现了支持命名捕获组、Unicode 属性转义和 6 大标志位的完整 JavaScript 正则。本文带你拆解libregexp.c源码看懂这个麻雀虽小、五脏俱全的正则引擎是如何工作的。 第一个问题为什么要自己造一个正则引擎大多数 JS 引擎如 V8的正则能力来自庞大的 ICU 库而 QuickJS 的设计目标是极小体积 零外部依赖常跑在路由器、智能手表、嵌入式设备等资源受限的环境里甚至被 QEMU 虚拟机直接嵌入。因此 Fabrice Bellard 手写了一个完全独立的正则引擎只用了 3 个文件文件行数职责libregexp.c2602 行编译器 回溯解释器核心libregexp.h92 行对外公共 API 与标志位定义libregexp-opcode.h58 行完整指令集仅 29 条操作码 实测用gcc -Os编译libregexp.c生成的代码段约 16228 字节≈15.8KiB——15KiB的说法由此而来。️ 架构总览正则 → 字节码 → 回溯执行QuickJS 正则引擎采用经典的三段式流水线① 解析Parselre_compile()用递归下降解析器把/abc(\d)/g这样的正则字符串读入产出字节码② 字节码Bytecode一段紧凑的uint8_t数组头部 7 个字节依次存放标志位、捕获组数量、最大栈深、代码长度③ 执行Execlre_exec()用回溯解释器逐条执行字节码返回匹配结果和所有捕获组。为什么中间要加一层字节码因为正则往往编译一次、匹配千万次——字节码可以跨字符串复用还能序列化存储、离线预编译。这与 QuickJS 编译 JS 生成QjscByteCode的思路一脉相承。29 条操作码正则引擎的指令集全部指令定义在libregexp-opcode.h中一个DEF宏表同时生成了枚举、大小表和调试名表Bellard 常用的一表三用技巧。按功能分组类别操作码作用字符匹配char/char32/dot/any单字符、32位码点、.、.*用通配分支跳转goto/split_goto_first/split_next_first/match跳转、分叉|、结束捕获组save_start/save_end/save_reset记录/重置分组边界量词支持loop/push_i32/drop循环计数器与虚拟栈字符类range/range32变长的区间表[a-z]零宽断言lookahead/negative_lookahead/word_boundary前瞻与\b后向引用back_reference\1匹配已捕获文本性能快车道simple_greedy_quant17 字节胖指令贪婪量词免回溯专用 编译阶段正则字符串如何变成字节流解析入口是re_parse_disjunction()libregexp.c第 1733 行按 JS 语法规则递归下降disjunction交替 a|b→ alternative序列→ term原子 量词整个过程维护在一个REParseState结构里——它既是解析工作台也是字节码发射器每解析出一个原子就立刻re_emit_*()追加字节码无需先构建 AST这是省内存的关键。几个值得学习的细节字符类用区间表CharRange把[a-f0-9]、[\p{L}]等统一合并成有序的码点区间range/range32指令直接携带这张表隐式.*? 前缀技巧非 sticky 正则会在开头自动发射 3 条指令split_goto_firstanygoto模拟.*?(...)让引擎从每个位置尝试匹配——但不用显式循环源码注释特意说明这是为了给未来的锁步lock step并行执行优化留后路静态栈深分析compute_stack_size()第 1765 行在编译期扫一遍字节码算出虚拟栈最大深度超过 255 直接报错 too many imbricated quantifiers把运行期内存变成编译期可确定的固定值。⚙️ 执行阶段回溯但不是递归回溯lre_exec_backtrack()第 2081 行是整个引擎的心脏一个for(;;)大循环 switch(opcode)逐条执行。回溯靠的是显式状态栈而非函数递归遇到分叉指令split_*、前瞻、贪婪量词时push_state()把当前 PC、字符指针、所有捕获组指针和虚拟栈完整快照压栈匹配成功走到match即返回匹配失败时逐个pop_state()回滚从上一个分叉点换条路继续尝试。为什么不直接递归深度嵌套的正则如(a)可能导致调用栈无限增长。显式状态栈让引擎完全掌控内存并通过lre_check_stack_overflow()回调把栈溢出检测交给宿主环境决定——嵌入式场景下这可能是栈空间、也可能是别的资源。前瞻的巧妙实现前瞻不消耗文本执行时压入RE_EXEC_STATE_LOOKAHEAD状态子模式匹配完只影响成功/失败判定随后回滚字符指针负前瞻则逻辑取反捕获组的恢复也区分保留与回滚两种模式。 Unicode 支持u 标志与 Emoji 的幕后机制QuickJS 正则引擎从设计之初就是Unicode 原生的UTF-16 代理对自动拼接GET_CHAR/PEEK_CHAR宏第 1916 行起在读字符时检测0xd800-0xdbff高位代理自动与低位代理拼成完整码点——所以\p{...}和字符类能正确匹配 这类 4 字节 EmojiUnicode 大小写折叠i标志下调用lre_canonicalize()做 Unicode 规范化而非简单 ASCII tolowerİ、ß等复杂情况也能正确处理\p{...}Unicode 属性转义parse_unicode_property()第 613 行解析\p{ScriptHan}、\p{scxLatin}、\p{General_CategoryLetter}及二元属性底层数据来自配套的libunicode.c与libunicode-table.h——编译期就把属性展开成码点区间表运行期零查表开销。引擎完整支持 ES 规范的 6 大标志位定义于libregexp.h标志含义标志位g全局匹配LRE_FLAG_GLOBALi忽略大小写Unicode 折叠LRE_FLAG_IGNORECASEm多行模式^$匹配行边界LRE_FLAG_MULTILINEs.匹配换行符dotallLRE_FLAG_DOTALLuUTF-16/Unicode 模式LRE_FLAG_UTF16ysticky 粘连匹配LRE_FLAG_STICKY⚡ 性能技巧16KiB 里藏了哪些优化simple_greedy_quant胖指令编译期能证明这个贪婪量词后续无需回溯时re_is_simple_quantifier()判定直接发射一条 17 字节的专用指令走快车道跳过状态压栈前进性检查re_check_advance()第 950 行在编译期验证每个循环分支至少消费一个字符从根上杜绝*空模式死循环字符类区间表所有字符类在编译期完成归一化、合并与取反运行期只需顺序比较TODO 中预告的线性时间模式源码开头第 40 行写明针对不含后向引用的简单正则计划支持锁步执行保证线性时间复杂度——指令集已为此预留了设计。⚖️ 它没做什么客观说明以当前仓库版本VERSION 文件2020-09-06为准尚未实现后向断言 lookbehind(?…)/(?!…)ES2018 引入源码中无任何相关实现捕获组上限255 个CAPTURE_COUNT_MAX这是典型的体积优先取舍——在15KiB 全能与特性全量之间QuickJS 选择了前者核心语法交替、分组、量词、字符类、前瞻、后向引用、命名捕获组、Unicode 属性一个不少。 如何上手在自己的 C 项目中调用 QuickJS 正则引擎整个引擎完全独立不依赖 QuickJS 虚拟机libregexp.h只暴露 5 个函数宿主仅需实现lre_realloc内存分配和lre_check_stack_overflow栈检查两个回调int len; char err[128]; uint8_t *bc lre_compile(len, err, sizeof(err), ab(c), 6, LRE_FLAG_UTF16, opaque); uint8_t *capture[8]; int hit lre_exec(capture, bc, (uint8_t *)input, 0, input_len, 2, opaque); /* 2 UTF-16 输入 */QuickJS 自身的调用点在quickjs.c第 41744 行JS 源码解析器遇到/…/字面量时js_parse_regexp()第 20441 行即调用lre_compile()。另外libregexp.c自带main()定义TEST宏编译后还是一个可打印字节码的反汇编调试工具。总结一份值得研读的极简范本回顾 QuickJS 正则引擎的设计亮点指令集先行——先用 58 行头文件定好 29 条操作码编译器、解释器、调试器共用一张表无 AST 编译——边解析边发射字节码内存占用近乎常数显式状态栈回溯——把最危险的递归变成可控的堆内存并开放给宿主做资源检查Unicode 原生——代理对拼接、码点区间表、属性转义全部编译期解决。如果你想深入建议按顺序阅读libregexp-opcode.h指令集→lre_compile()编译第 1813 行→lre_exec_backtrack()执行第 2081 行2750 行代码足以在一个下午读懂是学习从零实现 JavaScript 正则引擎的最佳教材。【免费下载链接】QuickJSQuickJS is a small and embeddable Javascript engine. QuickJS sources are copyright Fabrice Bellard and Charlie Gordon.项目地址: https://gitcode.com/gh_mirrors/quick/QuickJS创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考