#Binary AST S1

中文标题：二进制 AST 提案

#二进制 AST 提案概述

Shu-yu Guo (Bloomberg)

David Teller, Kannan Vijayan (Mozilla)

Vladan Djeric (Facebook)

Ingvar Stepanyan (Cloudflare)

这是为 JS 提出的新二进制 AST 格式的解释性文档。

#动机

Web 平台上应用程序的性能越来越受到启动（加载）时间的瓶颈限制。更复杂的 Web 属性通过网络传输的 JS 代码量越来越大。虽然缓存有所帮助，但这些属性定期发布新代码，冷加载时间非常重要。

2017 年 7 月对桌面上和移动端一些流行 Web 应用程序的未压缩 JS 负载大小进行的简要调查：

启动性能会随着 JS 负载的增大而下降，即使只有一部分代码被实际执行。解析时间是重要组成部分，比字节码/初始 JIT 代码生成消耗更多的 CPU 时间。例如，在一台性能强大的笔记本电脑上，Chrome 在加载 facebook.com 时将 10% 到 15% 的 CPU 时间用于解析 JS。

我们提出一种新的 JS 在线传输格式，即 AST 的二进制编码。我们相信这种新格式将允许大幅加快解析速度。此外，Web 开发人员已经接受了构建工具，因此他们有条件采用新格式。

我们还实现了一个原型编码器和解码器，展示了在不增加文件大小的情况下令人鼓舞的性能改进。

#设计理念

首要的设计理念是保守，以便在实现和委员会中都是现实的。本提案旨在仅是表面语法的替代编码，并以最小可能的差异来实现高性能解析。通过设计，本提案不尝试任何语义级别的编码（例如，字节码、编码变量而不是标识符）。

话虽如此，本提案是非常雄心勃勃的。

#当前解析瓶颈

# 1. 信息在需要的地方不可用

使解析变慢的一个基本问题是，解析过程中做决策所需的信息通常尚未在输入流中需要它的点可用。当解析器需要来自它尚未解析的代码（如变量提升）或它不想解析的代码（如内部函数）的信息时，就会发生这种情况。

一个具体的例子是有效表示绑定问题。为了决定如何表示或分配变量，解析器需要知道该变量是否被闭包捕获，因此有必要解析任何嵌套函数。规范只说明 var x 这样的声明需要在哪里可达，而不是如何分配它——分配决策所需的信息既没有在变量声明处编码，也没有在需要分配的位置编码。

在以下示例中，由于变量提升，use_x 闭包捕获了 x，而在解析内部函数时，并不知道 x 在 f 中声明。引擎在 f 完全解析之前，无法在 use_x 内部对 x 的访问进行优化。

var x;
function f() {
  function use_x() {
    use(x); // 闭包捕获提升的变量 x。
  }

  var x;
}

在以下示例中，引擎的前端希望知道如何在解析 var 声明时有效地为其分配空间。如果不解析函数的其余部分，这是不可能的。

function g() {
  var x; // 未被闭包捕获，应放在函数帧上。
  var y; // 被闭包捕获，应放在激活对象上。

  return (function() { use(y); });
}

在以下示例中，在引擎需要决定 var x 是否可能被动态访问时，函数底部的 eval 存在性是未知的。

function h(input) {
  var x;

  (function() {
    eval(input);
  })();
}

# 2. 早期错误语义

JavaScript 的早期错误语义要求解析每个文件的全部内容。引擎采用惰性解析（也称为预解析）优化，通过跳过内部函数的初始代码生成直到首次调用时，来避免构建完整的 AST。这平均只快 50%，并且解析工作量仍然与文件大小成正比。更糟糕的是，这种优化可能适得其反。如果在应用程序启动期间恰好调用了被跳过代码生成的内部函数，那么引擎实际上必须重新解析整个函数。这种情况经常发生，以至于开发人员使用立即调用的函数表达式来完全绕过惰性解析。

考虑以下情况。目前，由于 innerWithSyntaxError 有早期错误，outer 也必须抛出早期错误。

function outer() {
  function innerWithSyntaxError() {
    var;
  }
}

提议的行为更改类似于用 eval 包装函数体，如下所示。

function outer() {
  function innerWithSyntaxError() {
    eval("var");
  }
}

# 3. 使用字符的低效率

在解析时，JavaScript 语法在字符级别上可能对编码的表达式类型存在歧义。例如，为了区分列表表达式和箭头函数的参数列表，解析器需要做额外的簿记工作，以考虑所有有效的解释，直到歧义解决，或者它们需要在解析时具备回溯能力。

类似地，由于 Unicode 编码和处理 Unicode 转义码等原因，词法分析很慢。例如，引擎需要检查某些文本是单字节还是双字节编码。

#提案

我们提出基于 JavaScript 语法的高效抽象语法树表示的二进制编码。这是表面语法的一种新的、替代的编码，与文本表示有相当紧密的双向映射。我们力求在引入新语义方面尽可能保守，目前仅限于：

• 延迟早期错误
• 更改 Function.prototype.toString 行为
• 要求使用 UTF-8

为了进一步加快解析速度，我们建议将静态语义编码为实现提示，并将它们作为延迟断言进行验证。

对于这种 AST 格式，我们目前不建议自动从 ECMA-262 语法派生，因为它对于高效的树形表示来说太冗长，因此需要大量的扁平化和内联。此外，这可能会通过有效地使语法成为二进制格式的规范性规范来限制 JavaScript 规范的演进。

相反，我们建议使用单独的树语法，并在 AST 节点上添加仅表达语法信息的注解。有几个现有的树语法可以作为起点，例如 Babylon 或 Shift AST。

（两种语法可能是一个有争议的问题；这个决定不是一成不变的，欢迎反馈。）

借鉴 WebAssembly 的方法，二进制编码将分为 3 层：

1. 使用基本原语（例如，字符串、数字、元组）对 AST 节点进行简单的二进制编码
2. 在前一层之上进行额外的结构压缩，利用关于文件格式和 AST 性质的知识（例如，常量表）
3. 像 gzip 或 Brotli 这样的通用压缩算法。

我们期望该格式由 Babel 和 TypeScript 等现有编译器以及 WebPack 等打包器输出。

#语法

树语法由原语（布尔值、字符串、数字）、列表和不相交联合组成。不相交联合带有标签，对于给定的文件，具有固定的、期望的结构（有序属性）。某些节点，如字符串和列表，与其编码的字节长度一起编码，允许解析器跳过节点的编码表示。

#语言演进和版本控制

语法提供了所有可能的节点种类及其有序属性的集合，我们预计该集合将单调增长。然而，并非所有供应商在任何给定时间都支持所有节点。为此，每个文件包含一个头部，其中包含文件期望使用的节点及其属性列表。例如，假设语法当前提供一个包含 isAsync 属性的 FunctionExpression 节点。如果文件期望支持异步函数，它将在属性列表中包含一个包含 isAsync 的 FunctionExpression 条目。如果实现不支持头部中的节点或属性，则会抛出错误。

头部解决了版本控制问题、前向兼容性和后向兼容性。它还维护了 JavaScript 解析器对新特性的预期行为，即如果解析器遇到引擎未实现的特性，则解析格式正确的文件将失败，而不是依赖单一的版本号。最后，它充当结构压缩：节点种类将通过其在头部中的索引而不是名称来引用。

为了节省文件空间，将支持预设（例如，ES2015）。

#静态语义作为注解

为了解决上述问题 1 信息在需要的地方不可用，关键见解是所有当前已知的“信息在需要的地方不可用”的情况都与绑定相关。作用域节点（如函数或词法作用域节点）能够编码关于 AST 属性的额外注解。

当前考虑的非详尽注解列表：

1. VarDeclaredNames
2. LexicallyDeclaredNames
3. ClosedOverNames (新)
4. AssignedToOutsideOfDeclarationNames (新)
5. Has CallExpression where the callee expression is IdentifierReference of string literal eval (新)

这些注解如果存在，则表现为延迟断言。当作用域节点完成遍历时（如果被跳过的内部函数从未被调用，这可以被任意延迟），如果编码的注解与节点实体相反，则会抛出运行时错误。例如，如果函数体被注解为“有 VarDeclaredNames x”，但实际不包含名称为 x 的 var 声明，则会抛出错误。

为了防止不同实现之间在时机上的分歧，要求在最内层封闭函数被调用或最内层封闭全局脚本被评估时抛出此类错误。

需要注意的是，这些注解必须被检查，并且严格来说，它们不是可以忽略的提示。它们是对语法树结构的断言，无论引擎是否选择将它们用作解析提示，都必须验证。

这些注解将被指定为现有或新的静态语义。

最终，这个列表是临时的，并且是各种引擎在解析过程中当前派生的属性的并集。通过这些注解，引擎可以在不完整解析函数的情况下，通过单次向前传递为函数生成代码。如果引擎进行单次传递快速路径所需的提示不存在，则回退到引擎已经实现的现有分析。如果出现对新注解的需求，我们期望它们被标准化为新的静态语义。

注解和作用域像任何其他节点属性一样嵌入在 AST 中，并使用相同的版本控制机制。

#延迟早期错误

为了解决上述问题 2 早期错误语义，早期错误（如注解验证）将被延迟到最内层封闭函数被调用或最内层封闭全局脚本被评估时。

这是对文本 JS 的破坏性更改。

由于此格式预期是编译器输出，因此早期错误在实践中会在编译时被捕获。

#无转义码的 UTF-8

为了解决上述问题 3 使用字符的低效率，字符串和标识符必须使用 UTF-8，且不支持转义码。同样，我们预计这是可行的，因为该格式将是编译器输出。

#验证

头部、注解和树结构本身（例如，其长度编码的节点、子节点的允许种类）的验证旨在 AST 解码时，以每个节点恒定工作量的单次向前传递完成。

#Function.prototype.toString()

此方法将返回类似 "[sourceless code]" 的内容。

#异常偏移

抛出的异常，将具有二进制 AST 文件中的字节偏移，而不是行号和列号。

#进一步改进

在此格式上分层添加额外改进以进一步提高解析速度或减小二进制文件大小是很容易的。例如，该格式可以允许字符串表，或允许函数体与函数声明分开存储，等等。

#原型

我们在 Mozilla 的 SpiderMonkey 引擎中实现了一个早期原型，使用基于内部 AST 格式的语法。这样做是为了实现速度，我们的下一个原型将基于 Babylon AST。

对于 facebook.com 静态新闻动态基准测试，二进制 AST 表示略小于原始 JavaScript。即使在两种表示都通过 gzip 压缩后，情况依然如此。大小的减少主要来自使用字符串表以及表中条目的可变长度标识符。它还使用可变长度编码来表示数字。通过利用特定领域的信息，如提取公共子树，可以获得额外的大小优势。

创建完整 AST（不验证注解）所需的时间减少了约 70-90%，这是一个相当大的减少，因为 SpiderMonkey 在基准测试中对于普通 JavaScript 的 AST 构建时间为 500-800 毫秒。

#FAQ

为什么不直接提供字节码？

在 Web 上，没有供应商会同意提供字节码。

1. 引擎不想被字节码版本束缚。
2. 验证字节码更难，因为字节码比语法更具表现力。
3. 这有使语言分叉的风险，因为字节码可能比结构化 JavaScript 源代码更具表现力。
4. 设计新的字节码是一项更具雄心的任务。

为什么不使用 WebAssembly？

存在大量现有的无类型 JS 代码库，并且没有简单的方法将像 JS 这样的无类型、垃圾收集的语言转换为 WebAssembly。鉴于目前使用 WebAssembly 来提供 JavaScript 很可能涉及捆绑 JS 运行时，目前尚不清楚这样的设置能否带来任何加载时间的性能改进。

为什么不使用语义图？或者为什么不更进一步？为什么不用类型？

我们不想通过添加新的前端语义来发明一种新语言，也不想对分析结果进行编码并需要更复杂的验证来确保这些信息正确。

这不会是一个巨大的维护负担吗？

解析二进制 AST 格式不会像解析现有 JavaScript 那样复杂。它无疑会增加实现的复杂性，但考虑到 Web 应用程序的复杂性和规模的轨迹，我们认为值得付出代价。

AST 格式不会使文件大小膨胀吗？

在我们上面描述的原型中，我们发现 AST 格式略小，即使在比较压缩后的大小也是如此。

性能提升有多大？

对于解析桌面版 facebook.com，10-15% 的客户端 CPU 时间用于解析 JavaScript。我们实现的原型将构建 AST 的时间减少了 70-90%。

此外，当今许多复杂网站会在用户与某些次要功能交互时按需获取 JavaScript（例如，当用户在 Facebook 上打开通知面板时）。这些交互路径上的长解析时间会降低站点的响应速度。

是否可以编写工具将序列化的 AST 转换回 JS？

是的，可以从 AST 格式自动生成人类可读的 JavaScript。由于语法树是抽象的而不是具体的，漂亮的打印机不会完美地重建输入的 JavaScript，但它在语义上是等价的。

此类序列化器对于提供引人注目的开发工具故事可能至关重要。

可编程缓存 API 是否会使这变得过时？

不。可编程缓存 API 极大地改善了热加载时间。本提案改善了冷加载时间。它与缓存 API 很好地组合。

这会与文本 JS 源代码一起使用吗？

是的。HTML 集成即将推出，但应用程序可以自由地混合加载文本源代码和二进制 AST 文件。

这会成为新的攻击面吗？

是的，但我们相信这是一个比字节码等替代方案更小、更可控、更可测试的攻击面。