GraalVM TRegex 版本演进与语言集成指南：从 Changelog 到源码的完整解读

GraalVM TRegex 版本演进与语言集成指南从 Changelog 到源码的完整解读【免费下载链接】graalGraalVM compiles applications into native executables that start instantly, scale fast, and use fewer compute resources 项目地址: https://gitcode.com/gh_mirrors/gr/graalTRegex 是 GraalVM 中基于有限状态自动机的通用正则表达式引擎为 Truffle 语言如 JavaScript、Python、Ruby提供正则表达式支持。本文以 regex/CHANGELOG.md 为主线结合 TRegex 源码regex/README.md、RegexLanguage.java、RegexOptions.java深入讲解其架构原理、API 演进、配置选项与集成方式帮助语言实现者与引擎维护者全面理解 TRegex 的能力边界与演进脉络。TRegex 核心架构为什么选择自动机而不是回溯从 NFA 到 DFA 的编译流程TRegex 与大多数基于回溯的正则引擎不同其核心思路是编译而非匹配正则表达式被解析为语法树语法树被翻译成非确定性有限状态自动机NFA通过 powerset 构造子集构造法将 NFA 展开为确定性有限状态自动机DFA匹配输入串时执行该 DFA并借助 GraalVM 编译器与 Truffle API 将 DFA 解释执行编译为高效的机器码。从源码看这一流程在 RegexLanguage.java 的解析入口中体现RegexParser负责解析与构造 ASTTRegexCompiler负责生成执行节点RegexObject.java 中的getLabel()方法按执行节点类型返回literal、backtracker、nfa或dfa直观展示了 TRegex 内部可选择的多种执行路径。线性时间匹配的优势与代价自动机方案的显著优势是判断是否匹配只需对输入串做单次扫描所有可行的备选匹配路径被同时考虑运行时稳定可预测与输入长度线性相关避免了回溯引擎在对抗性输入下可能出现的指数级执行时间。其代价是无法覆盖回溯引擎的某些高级特性例如反向引用backreference如/([a-z])\1/和非字面量的 lookbehind如/(?a.)b/。因此 TRegex 只处理 ECMAScript 正则的子集其余特性必须交给回溯引擎处理TRegex 自带 ECMAScript 回溯 fallback 引擎其他语言可能需要自行提供自定义 fallback 引擎详见 regex/README.md 的 Feature Support 一节。从测试代码可以印证这一边界例如 JsTests.java 中的testForceLinearExecution(a*)b\1含反向引用在ForceLinearExecution选项下被拒绝expectUnsupported.*a{1,200000}.*的大数量词被拒绝.*b(?!a_)的负向先行断言被拒绝。语言集成通过 Truffle interop 使用 TRegex解析正则表达式TRegex 的 API 通过 Truffle 的 interop 机制暴露TruffleObject和 AST 节点归属于一个新的 Truffle 语言 RegexLanguageID 为regexMIME 类型为application/tregex。解析一个正则时TRegex 返回一个CallTarget调用后可能产生三种结果TruffleNull对象表示 TRegex 无法处理该正则应回退到其他引擎已编译正则RegexObject可用于后续匹配RegexSyntaxExceptionAbstractTruffleException异常类型为PARSE_ERROR表示语法错误。解析示例来自 RegexLanguage.java 的 javadocObject regex; try { regex getContext().getEnv().parseInternal( Source.newBuilder(regex, FlavorECMAScript/(a|(b))c/i, myRegex) .mimeType(application/tregex).internal(true).build()).call(); } catch (AbstractTruffleException e) { if (InteropLibrary.getUncached().getExceptionType(e) ExceptionType.PARSE_ERROR) { // handle parser error } else { // fatal error, this should never happen } } if (InteropLibrary.getUncached().isNull(regex)) { // regex is not supported by TRegex, fall back to a different regex engine }TRegex 从 Graal JavaScript 实现中独立出来现在可以供其他语言的实现者直接使用详见 regex/README.md。语言集成时可参考 Graal JavaScript 的接入方式通过RegexCompilerInterface#compile发起编译请求在JSRegExpExecBuiltinNode中执行已编译正则TRegexUtil则展示了如何为 TruffleLanguage 对象的成员编写 interop 访问包装。已编译正则对象 RegexObject 的成员RegexObjectRegexObject.java暴露以下只读成员KEYS常量成员类型说明patternString已编译正则的源字符串flagsTruffleObject传给编译器的标志集合类型随 flavor 不同而异RegexFlags/JavaFlags/OracleDBFlags/PythonFlags/RubyFlagsgroupCountint捕获组数量含组 0groupsTruffleObject具名捕获组名到组号的映射无具名组时为 null。Ruby 等允许重名时值为数组execexecutable执行匹配的方法返回RegexResultexecBooleanexecutable布尔匹配模式下的执行方法只返回是否匹配isBacktrackingboolean该正则是否使用回溯执行可能带来指数级运行时间exec方法支持两种签名exec(TruffleString, int)与exec(TruffleString, int, int, int, int)后者的参数依次为input、fromIndex搜索起始位置lookbehind 允许越过该索引回看至regionFrom、toIndex搜索终止位置当前必须等于regionTo、regionFrom硬起始边界^/\A会匹配该索引、regionTo硬结束边界$/\Z/\z会匹配该索引。利用regionFrom/regionTo可将搜索限制在输入串的子串范围内。所有索引参数都会转换为int。exec的首次调用可能因为按需编译而出现较长的延迟。结果对象 RegexResult 的成员RegexResult表示一次匹配的结果来自exec的返回值boolean isMatch是否找到匹配int getStart(int groupNumber)捕获组起始位置无匹配时未定义组 0 表示整个表达式某组未匹配时返回-1int getEnd(int groupNumber)捕获组结束位置语义同getStart。匹配用法伪代码示例regex matcher from previous example assert(regex.pattern (a|(b))c) assert(regex.flags.ignoreCase true) assert(regex.groupCount 3) result regex.exec(xacy, 0) assert(result.isMatch true) assertEquals([result.getStart(0), result.getEnd(0)], [ 1, 3]) assertEquals([result.getStart(1), result.getEnd(1)], [ 1, 2]) assertEquals([result.getStart(2), result.getEnd(2)], [-1, -1]) result2 regex.exec(xxx, 0) assert(result2.isMatch false) // result2.getStart(...) and result2.getEnd(...) are undefinedRegexOptions 配置体系从源码选项到 Source 内嵌选项RegexOptionsRegexOptions.java定义 TRegex 如何解释一次解析请求。除了源码中的Option注解可通过regexDummyLang.Xxx等引擎选项配置外还有一部分选项可以内嵌在正则源码字符串中。Source 内嵌选项格式的演进TRegex 期望的源码格式为options/regex/flags其中options是逗号分隔的键值对列表/regex/flags等价于 JavaScript/Ruby 中常见的正则字面量格式。重要演进Version 25.0.0TRegex 新增了对 Truffle Source Options 的支持内嵌在正则源码字符串中的选项被标记为废弃。源码格式相应地从options/regex/flags变为/regex/flags——也就是说不带内嵌选项头的普通正则字面量成为推荐形式而选项改由 Truffle 的 Source Options / 引擎选项机制提供。从 RegexOptions.java 的Builder.parseOptions()可以看出兼容性处理当src以/开头时直接走新路径所有布尔选项从optionValuesTruffle OptionValues读取否则仍解析旧的内嵌keyvalue语法。旧式内嵌选项的解析逻辑支持如下前缀源码parseOptions()的 switch 分支A(AlwaysEager)、B(BooleanMatch)、D(DumpAutomata)、E(Encoding)、F(Flavor)、G(GenerateDFAImmediately/GenerateInput)、I(IgnoreAtomicGroups)、J(JavaJDKVersion)、M(MaxBackTrackerJITSize/MaxDFASize/MatchingMode/MustAdvance)、P(PythonMethod/PythonLocale)、R(RegressionTestMode)、S(StepExecution)、U(U180EWhitespace/UTF16ExplodeAstralSymbols)、V(Validate)。布尔选项取true/false数值选项如MaxDFASize、JavaJDKVersion有范围校验如 JavaJDKVersion 必须 ≥ 21短整型不超过Short.MAX_VALUE。选项清单以下选项除Flavor、Encoding外均为布尔型且默认false用户选项OptionCategory.USER选项取值说明FlavorECMAScript默认、Python、Ruby、OracleDB、JavaUtilPattern指定正则方言从FlavorOption枚举及FLAVOR_CACHE可见其实现位于 flavor 目录下的各*FlavorProviderJS、Python、Ruby、OracleDB、JavaEncodingUTF-8、UTF-16、UTF-16-RAW默认、UTF-32、BYTES、LATIN-1指定匹配的字符串编码BYTES等价于LATIN-1。注意EncodingOption的默认值源码中为UTF_16_RAWMatchingModesearch默认、match、fullmatch隐式锚定模式search在输入任意位置搜索match锚定在起始索引fullmatch同时锚定起始与结束索引。其前身为 Python 方言下的PythonMethodBooleanMatchtrue/false不报告捕获组只返回布尔结果对应execBoolean与isBooleanMatch()ForceLinearExecutiontrue/falseVersion 25.0.0 新增实验性对 TRegex 无法线性时间执行的正则一律 bailout 拒绝。测试见 JsTests.java 与 PythonTests.javaJavaJDKVersion21-25默认24Java flavor 的 JDK 兼容版本专家/性能选项OptionCategory.EXPERTValidate不生成匹配器仅检查语法错误isValidate()U180EWhitespace将0x180E MONGOLIAN VOWEL SEPARATOR视为\s的一部分兼容 Unicode 6.3 之前的旧标准如 ECMAScript 6 及更早仅适用于 ECMAScript flavorAlwaysEager不生成惰性匹配器惰性指可能延迟计算RegexResult的属性IgnoreAtomicGroups将原子组视为普通组Ruby 正则中常见见 Version 21.3.0 的变更记录GenerateDFAImmediately解析后立即生成 DFA 匹配器默认 DFA 是惰性生成MaxDFASizeDFA bailout 阈值默认TRegexOptions.TRegexMaxDFATransitionsMaxBackTrackerJITSize回溯器 JIT 编译 bailout 阈值默认TRegexMaxBackTrackerMergeExplodeSizeMaxParserTreeSize解析树 bailout 阈值默认TRegexParserTreeMaxSizeQuantifierUnrollLimitSingleCC/QuantifierUnrollLimitGroup单字符类量词 / 组量词展开上限PythonLocalePython flavor 的区域敏感特性使用的 locale实验性默认空字符串。调试/内部选项OptionCategory.INTERNALRegressionTestMode运行所有支持的匹配器变体并校验结果一致内部测试用DumpAutomata将解析树、NFA、DFA 以 JSON、GraphViz、LaTeX 格式导出到磁盘内部测试用StepExecution导出所有 DFA 匹配器运行的追踪信息MustAdvance强制匹配器至少前进一个字符——要么找到非零宽匹配要么跳过至少一个字符后再匹配。该选项在 RegexOptions.java 中有isMustAdvance()说明Python 测试 PythonTests.java 中通过regexDummyLang.MustAdvancetrue使用Python 正则中对应re模块的匹配必须推进语义GenerateInput尝试生成该正则能匹配的字符串并返回用于内部测试。已废弃选项UTF16ExplodeAstralSymbols在源码中标记为 deprecatedisUTF16ExplodeAstralSymbols()仍有实现含义是为每个 16 位char生成 DFA 状态而非每个码点可能提升特定场景性能但增加状态爆炸风险。调试日志器Version 1.0.0 RC10 引入编译器动作日志能力regex命名空间下的日志器定义在 Loggers.java可通过如下方式启用对应 RC10 中的--log.regex.Phases.levelALL形式-Dpolyglot.log.regex.SwitchToEager.levelALL -Dpolyglot.log.regex.TotalCompilationTime.levelALL -Dpolyglot.log.regex.Phases.levelALL -Dpolyglot.log.regex.BailoutMessages.levelALL -Dpolyglot.log.regex.AutomatonSizes.levelALL -Dpolyglot.log.regex.CompilerFallback.levelALL -Dpolyglot.log.regex.InternalErrors.levelALL -Dpolyglot.log.regex.TRegexCompilations.levelALL这些日志器LOG_SWITCH_TO_EAGER、LOG_TOTAL_COMPILATION_TIME、LOG_BAILOUT_MESSAGES、LOG_AUTOMATON_SIZES、LOG_COMPILER_FALLBACK、LOG_INTERNAL_ERRORS、LOG_TREGEX_COMPILATIONS等分别对应切换到 eager 模式、总编译耗时、编译阶段、bailout 消息、自动机规模、编译器回退、内部错误、编译事件等调试维度是排查 TRegex 编译行为的重要工具。语言特性演进时间线按版本解读以下按 regex/CHANGELOG.md 梳理对语言实现者integrator有影响的 API 与能力变更25.xUnicode 17 与线性执行保障25.1.3JS 与 Python 正则 flavor 更新至 Unicode 17.0。25.0.0布尔匹配模式下 DFA 匹配器支持有界量词嵌套有界量词及与部分 lookaround 的组合仍不支持新增 Truffle Source Options 支持源码内嵌选项废弃源码格式从options/regex/flags变为/regex/flags新增ForceLinearExecution选项对无法线性时间执行的正则 bailout。24.x正则修饰符与原子组24.2.0实现 ECMAScript 正则的模式修饰符Regular Expression Pattern Modifiers提案即内联修饰符(?ims-ims:...)之类能力。24.0.0Python 正则支持原子组atomic groups与占有量词possessive quantifiers。23.xUnicode Sets 与具名捕获组23.1.0ECMAScript 正则支持 Unicode sets 模式v标志支持重复的具名捕获组。23.0.0Unicode 数据大小写折叠、字符属性更新至 Unicode 15FlavorPythonStr/FlavorPythonBytes废弃改用FlavorPython,EncodingUTF-32与FlavorPython,EncodingLATIN-1移除execBytes(byte[] input, int fromIndex)入口点移除将TruffleObject的字符/码点作为数组元素的支持Python 与 Ruby 正则支持条件反向引用如(foo)(?(1)bar|no_foo)与大小写不敏感反向引用支持区域敏感的 Python 正则TRegex 不再默认包含在 GraalVM 发行版中需通过gu install regex作为组件安装。22.x回溯引擎能力扩展与布尔匹配22.2.0Ruby 正则通过回溯支持原子组与占有量词。22.1.0RegexResult新增lastGroup字段Python 方言下跟踪表示最后匹配的捕获组测试见 PythonTests.java 的lastGroupNotSet与 lookbehind 交互用例新增布尔匹配模式execBoolean在确定不会查询捕获组时省去RegexResult对象新增MustAdvance与PythonMode选项Python 支持具名字符转义Ruby 支持有限的\G锚点移除 Python 正则的 sticky 标志Ruby 支持非递归子表达式调用。21.x 及更早从结果对象重构到 ECMAScript 202022.0.0新增ASCII编码将码点匹配范围限制在[0x00, 0x7f]Unicode 数据更新至 Unicode 14。21.3.0Ruby 正则支持大小写不敏感匹配新增IgnoreAtomicGroups选项编译后的正则导出isBacktracking布尔成员用于判断该正则是否可能回溯并导致指数级运行时间。21.2.0ECMAScript 正则支持hasIndicesd标志。20.2.0引入 UTF-16 字符串的即时解码on-the-fly decoding。20.1.0通过新的内置回溯引擎完整支持 ECMAScript 2020 正则特性。1.0.0 RC15从结果对象中移除regex、input、start、end属性改用getStart(groupNumber)/getEnd(groupNumber)方法正则语法异常改为普通TruffleException语言实现者不应再对 TRegex 引入源码级依赖groupCount属性从结果对象移至已编译正则对象。1.0.0 RC10新增编译器动作日志见上文调试日志器一节。实用建议与版本迁移要点升级到 25.x 前检查语言实现中是否依赖源码内嵌选项语法options/regex/flags若依赖则需迁移到 Truffle Source Options 方式新源码格式为/regex/flags。Python 集成旧式FlavorPythonStr/FlavorPythonBytes已废弃应改为FlavorPython配合EncodingUTF-32/LATIN-1若需要execBytes能力需寻找替代方案该入口点已在 23.0.0 移除注意lastGroup仅在 Python 方言下被跟踪。安全性如需保证匹配耗时可控可启用ForceLinearExecution25.0.0对含反向引用、负向 lookaround、超大数量词等无法线性执行的正则直接拒绝对于已有正则可通过isBacktracking成员21.3.0在运行时判断其是否走回溯路径。安装方式自 23.0.0 起 TRegex 不再是 GraalVM 默认组件需要执行gu install regex安装后再集成。以上能力均可通过 regex 测试目录下的JsTests、PythonTests、RubyTests、JavaUtilPatternTests、RegexOptionsTest等测试用例进一步验证它们是理解 TRegex 行为边界的第一手资料。【免费下载链接】graalGraalVM compiles applications into native executables that start instantly, scale fast, and use fewer compute resources 项目地址: https://gitcode.com/gh_mirrors/gr/graal创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考