SpiderMonkey中一种新的RegExp引擎

2020-06-12 03:32:24

正则表达式(通常称为RegExp)是JavaScript中用于操作字符串的强大工具。它们提供了丰富的语法来描述和捕获字符信息。它们的使用率也很高,所以对SpiderMonkey(Firefox中的JavaScript引擎)来说,很重要的一点就是对它们进行优化。

多年来,我们有几种方法来实现RegExp。方便的是,RegExp引擎和SpiderMonkey的其余部分之间有一条相当清晰的分界线。更换RegExp引擎仍然不容易,但这可以在不对SpiderMonkey的其余部分造成太大影响的情况下完成。

在2014年,我们利用这种灵活性将Yarr(我们之前的RegExp引擎)替换为Irregexp的分支副本,Irregexp是V8中使用的引擎。这就提出了一个棘手的问题:如何让为一个引擎设计的代码在另一个引擎内部工作?Irregexp使用许多V8API,包括字符串表示、对象模型和垃圾收集器等核心概念。

当时,我们选择大量重写Irregexp以使用我们自己的内部API。这使得我们更容易使用,但从上游导入新更改要困难得多。RegExp的更改相对较少,因此这似乎是一个很好的权衡。起初,这对我们来说效果很好。当引入‘\u’标志等新功能时,我们将它们添加到Irregexp。然而,随着时间的推移,我们开始落后了。ES2018添加了四个新的RegExp功能:dotAll标志、命名捕获组、Unicode属性转义和回溯断言。V8团队添加了对这些特性的Irregexp支持,但是Irregexp的SpiderMonkey副本已经有了足够的差异,使得应用相同的更改变得困难。

我们开始重新考虑我们的方法。我们有没有办法在不增加持续维护负担的情况下支持现代RegExp功能?如果我们优先使RegExp引擎保持最新,它会是什么样子?我们离上游的Irregexp有多近?

事实证明,答案确实非常接近。在撰写本文时,SpiderMonkey使用的是从V8存储库中导入的最新版本的Irregexp,除了机械重写#include语句外没有任何更改。除了运行更新脚本之外,刷新导入只需要很少的工作。我们正在积极向上游提供错误报告和补丁。

我们是怎么走到这一步的?我们的方法是在SpiderMonkey和Irregexp之间构建填充层。这个填充程序为Irregexp提供了对它通常从V8获得的所有功能的访问:从内存分配到代码生成,再到各种实用函数和数据结构。

这花了一些功夫。这很大程度上是一件简单明了的事情,就是把事情联系在一起。例如,Irregexp解析器和编译器使用V8的Zone(一种Arena风格的内存分配器)来有效地分配临时对象并丢弃它们。SpiderMonkey的等价物被称为Lifoalloc,但它有一个非常相似的界面。我们的填充程序能够通过将对Zone方法的调用直接转发到它们的Lifoalloc等效项来实现对这些方法的调用。

Irregexp有两种执行RegExp的策略:字节码解释器和实时编译器。前者生成更密集的代码(使用更少的内存),并且可以在无法生成本机代码的系统上使用。后者生成运行速度更快的代码,这对于重复执行的RegExp很重要。SpiderMonkey和V8都在第一次使用时解释RegExp,然后在以后编译它们。

用于生成本机代码的工具是非常特定于引擎的。幸运的是,Irregexp有一个设计良好的代码生成API,称为RegExpMacroAssembler。在解析和优化RegExp之后,RegExpCompiler将对RegExpMacroAssembler进行一系列调用以生成代码。例如,要确定字符串中的下一个字符是否与特定字符匹配,编译器将调用CheckCharacter。要在反向引用不匹配时回溯,编译器将调用CheckNotBackReference。

总体而言,大约有40个可用操作。这些操作加在一起可以表示任何JavaScript RegExp。宏汇编器负责将这些抽象操作转换成最终的可执行形式。V8包含不少于9个RegExpMacroAssembler的独立实现:它支持的8个体系结构中的每一个都有一个,最后一个实现为解释器生成字节码。SpiderMonkey可以重用字节码生成器和解释器,但我们需要自己的宏汇编程序。幸运的是,有几件事对我们有利。

首先,SpiderMonkey的原生代码生成工具工作在比V8更高的级别,我们不需要为每个架构实现宏汇编器,我们只需要一个可以针对任何支持的机器的宏汇编程序。其次,使用SpiderMonkey的代码生成器实现RegExpMacroAssembler的大部分工作已经在我们第一次导入Irregexp时完成了。我们必须进行相当多的更改才能支持新功能(特别是回溯引用),但现有代码给了我们一个很好的起点。

JavaScript中的内存是自动管理的。当内存不足时,垃圾收集器(GC)遍历程序并清理所有不再使用的内存。如果您正在编写JavaScript,这将在幕后进行。但是,如果您正在实现JavaScript,这意味着您必须小心。当您正在处理可能被垃圾收集的东西时-比方说,您要与RegExp匹配的字符串-您需要通知GC。否则,如果您调用一个触发垃圾收集的函数,GC可能会将您的字符串移到其他地方(如果您是唯一剩余的引用,甚至完全删除它)。出于显而易见的原因,这是一件坏事。告诉GC您正在使用的对象的过程称为根。对于我们的填补实现来说,最有趣的挑战之一是SpiderMonkey和V8根之间的方式不同。

SpiderMonkey在C++堆栈上创建它的根。例如,如果您想要将一个字符串作为根,您可以创建一个位于本地堆栈帧中的带根的<;JSString*>;。当您的函数返回时,根目录消失,GC可以自由地收集您的JSString。在V8中,您将创建一个句柄。在幕后,V8创建一个根并将其存储在并行堆栈中。V8中根的生存期由HandleScope对象控制,这些对象在创建根堆栈时标记根堆栈上的一个点,并在销毁根堆栈时清除每个比标记点更新的根。

为了使填隙程序正常工作,我们实现了我们自己的V8的HandleScopes的微型版本。更复杂的是,某些类型的对象在V8中是垃圾收集的,但在SpiderMonkey中是常规的非GC对象。为了处理这些对象(不是双关语),我们添加了一个并行的“PseudoHandle”堆栈,它们看起来像Irregexp的普通句柄,但由(非GC)唯一指针支持。

如果没有V8团队的支持和建议,这一切都是不可能的。特别值得一提的是,雅各布·格鲁伯(Jakob Gruber)提供了特别的帮助。事实证明,这个项目很好地满足了V8团队的一个预先存在的愿望,即使Irregexp更加独立于V8。虽然我们试图使填隙尽可能完整,但在某些情况下,上游更改是最好的解决方案。其中许多变化都很小。有些更有趣。

在V8和Irregexp之间的接口上的一些代码被证明太难在SpiderMonkey中使用。例如,要执行编译的RegExp,Irregexp调用NativeRegExpMacroAssembler::Match。该函数与V8的字符串表示紧密相关。这两个引擎中的字符串实现惊人地接近,但还没有接近到我们可以共享代码的程度。我们的解决方案是将该代码完全移出Irregexp,并将其他无法使用的代码隐藏在特定于嵌入器的#ifdef后面。从技术角度来看,这些更改并不特别有趣,但是从软件工程的角度来看,它们让我们更清楚地了解在未来的项目中可能会在哪里划定API边界,以将Irregexp与V8分开。

当我们的原型实现接近完成时,我们意识到SpiderMonkey测试套件中剩余的失败之一在V8中也失败了。经过调查,我们发现Irregexp和JavaScript规范在不区分大小写、非Unicode RegExp方面存在细微的不匹配。我们在上游提供了一个补丁,用来重写Irregexp对具有非标准大小写折叠行为的字符的处理(如‘«’,拉丁文小写字母Sharp S,在大写时给出“SS”)。

我们帮助改进Irregexp的机会并没有止步于此。在我们将Irregexp的新版本登陆Firefox Nighly后不久,我们勇敢的模糊团队发现了一个令人费解的RegExp,它在SpiderMonkey和V8的调试版本中都崩溃了。幸运的是,经过进一步调查,这是一个过于严格的断言。然而,它确实激发了RegExp解释器中一些额外的代码质量改进。

除了JetStream2基准测试中一些改进的子分数之外,我们从所有这些工作中获得了什么?

最重要的是,我们获得了对所有RegExp新功能的全面支持。Unicode属性转义和回溯引用只会影响RegExp匹配,因此填充程序一完成它们就会起作用。支持dotAll标志只需要少量的额外工作。命名捕获涉及到来自SpiderMonkey其余部分的稍微多一点的支持,但在启用新引擎几周后,命名捕获也落地了。(在测试它们时,我们在等价的V8代码中发现了最后一个错误。)。这使得Firefox完全符合JavaScript的最新ECMAScript标准。

我们也为未来的RegExp支持奠定了更坚实的基础。在Irregexp上进行更多的协作是互惠互利的。SpiderMonkey可以更快地添加新的RegExp语法。V8获得了一组额外的眼睛和手来查找和修复bug。假设Irregexp的未来嵌入器有一个经过验证的起点。

新引擎在Firefox78中可用,它目前在我们的开发人员版浏览器版本中。希望这项工作将在未来几年成为Firefox中RegExp的基础。