语法高亮的优化

2017 年 2 月 8 日 - Alexandru Dima

Visual Studio Code 1.9 版包含了一项我们一直在努力的酷炫性能改进，我想讲述它的故事。

太长不看：在 VS Code 1.9 中，TextMate 主题的外观将更接近其作者的意图，同时渲染速度更快，内存消耗更少。

语法高亮

语法高亮通常包含两个阶段。将 token 分配给源代码，然后主题会针对这些 token 分配颜色，这样，您的源代码就以彩色渲染了。这是一项将文本编辑器转变为代码编辑器的重要功能。

VS Code（以及 Monaco 编辑器）中的 tokenization（词法分析）按行、从上到下进行，一次完成。tokenizer 可以在已词法分析行的末尾存储一些状态，该状态将在词法分析下一行时传回。这是包括 TextMate 语法在内的许多 tokenization 引擎使用的一种技术，它允许编辑器在用户进行编辑时仅对一小部分行重新进行词法分析。

大多数情况下，在某行上键入只会导致该行重新进行词法分析，因为 tokenizer 返回相同的结束状态，编辑器可以假定后续行不会获得新的 token

极少数情况下，在某行上键入会导致当前行及其下方某些行（直到遇到相同的结束状态为止）重新进行词法分析/重绘

我们过去如何表示 token

VS Code 中编辑器的代码早在 VS Code 存在之前就已经编写完成。它以 Monaco 编辑器 的形式随各种 Microsoft 项目一起发布，包括 Internet Explorer 的 F12 工具。我们当时的一个要求是减少内存使用。

过去，我们手动编写 tokenizer（即使是今天，在浏览器中解释 TextMate 语法也没有可行的方法，但这是另一个故事了）。对于下面这行，我们将从我们手动编写的 tokenizer 中获得以下 token

tokens = [
  { startIndex: 0, type: 'keyword.js' },
  { startIndex: 8, type: '' },
  { startIndex: 9, type: 'identifier.js' },
  { startIndex: 11, type: 'delimiter.paren.js' },
  { startIndex: 12, type: 'delimiter.paren.js' },
  { startIndex: 13, type: '' },
  { startIndex: 14, type: 'delimiter.curly.js' }
];

在 Chrome 中，保留该 token 数组占用 648 字节，因此存储此类对象在内存方面开销很大（每个对象实例必须预留空间用于指向其原型、其属性列表等）。我们当前的机器确实有很多 RAM，但为 15 个字符的行存储 648 字节是不可接受的。

因此，当时我们提出了一种二进制格式来存储 token，这种格式一直使用到 VS Code 1.8（含）。考虑到会存在重复的 token 类型，我们将它们收集在一个单独的 map 中（每个文件一个），做法如下

//     0        1               2                  3                      4
map = ['', 'keyword.js', 'identifier.js', 'delimiter.paren.js', 'delimiter.curly.js'];
tokens = [
  { startIndex: 0, type: 1 },
  { startIndex: 8, type: 0 },
  { startIndex: 9, type: 2 },
  { startIndex: 11, type: 3 },
  { startIndex: 12, type: 3 },
  { startIndex: 13, type: 0 },
  { startIndex: 14, type: 4 }
];

然后，我们将 startIndex（32 位）和 type（16 位）编码到 JavaScript 数字的 53 位尾数位 中的 48 位。我们的 token 数组最终将如下所示，并且 map 数组将在整个文件中重复使用

tokens = [
  //       type                 startIndex
  4294967296, // 0000000000000001 00000000000000000000000000000000
  8, // 0000000000000000 00000000000000000000000000001000
  8589934601, // 0000000000000010 00000000000000000000000000001001
  12884901899, // 0000000000000011 00000000000000000000000000001011
  12884901900, // 0000000000000011 00000000000000000000000000001100
  13, // 0000000000000000 00000000000000000000000000001101
  17179869198 // 0000000000000100 00000000000000000000000000001110
];

在 Chrome 中，保留该 token 数组占用 104 字节。元素本身应该只占用 56 字节（7 个 64 位数字），其余部分可能由 v8 随数组存储其他元数据，或者可能以 2 的幂次方分配支持存储来解释。然而，内存节省是显而易见的，并且随着每行 token 数量的增加而效果更好。我们对这种方法很满意，并且从那时起一直在使用这种表示形式。

注意：可能存在更紧凑的 token 存储方式，但将它们存储在可进行二分查找的线性格式中，可以在内存使用和访问性能方面实现最佳权衡。

Token <-> 主题匹配

我们认为遵循浏览器最佳实践是一个好主意，例如将样式留给 CSS 处理，因此在渲染上面这行时，我们将使用 map 解码二进制 token，然后使用 token 类型进行渲染，如下所示

  <span class="token keyword js">function</span>
  <span class="token">&nbsp;</span>
  <span class="token identifier js">f1</span>
  <span class="token delimiter paren js">(</span>
  <span class="token delimiter paren js">)</span>
  <span class="token">&nbsp;</span>
  <span class="token delimiter curly js">{</span>

然后我们将主题 用 CSS 编写（例如 Visual Studio 主题）

...
.monaco-editor.vs .token.delimiter          { color: #000000; }
.monaco-editor.vs .token.keyword            { color: #0000FF; }
.monaco-editor.vs .token.keyword.flow       { color: #AF00DB; }
...

结果相当不错，我们只需更改某个地方的类名，就能立即将新主题应用到编辑器。

TextMate 语法

对于 VS Code 的发布，我们有大约 10 个手动编写的 tokenizer，主要用于 Web 语言，这对于通用桌面代码编辑器来说肯定不够。于是引入了 TextMate 语法，这是一种描述性的 tokenization 规则规范形式，已被许多编辑器采用。然而，有一个问题是，TextMate 语法的工作方式与我们的手动编写的 tokenizer 不完全相同。

TextMate 语法通过使用 begin/end 状态或 while 状态，可以推入跨多个 token 的 scope。以下是同一个示例在 JavaScript TextMate 语法下的情况（为简洁起见忽略空格）

VS Code 1.8 中的 TextMate 语法

如果我们查看 scope 堆栈的某个部分，每个 token 基本上会得到一个 scope 名称数组，我们将从 tokenizer 中获得如下内容

tokens = [
  { startIndex: 0, scopes: ['source.js', 'meta.function.js', 'storage.type.function.js'] },
  { startIndex: 8, scopes: ['source.js', 'meta.function.js'] },
  {
    startIndex: 9,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.definition.function.js',
      'entity.name.function.js'
    ]
  },
  {
    startIndex: 11,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.parameters.js',
      'punctuation.definition.parameters.js'
    ]
  },
  { startIndex: 13, scopes: ['source.js', 'meta.function.js'] },
  {
    startIndex: 14,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.block.js',
      'punctuation.definition.block.js'
    ]
  }
];

所有的 token 类型都是字符串，我们的代码还没有准备好处理字符串数组，更不用说这对 token 的二进制编码意味着什么了。因此，我们采用以下策略将 scope 数组“近似化”*为单个字符串

• 忽略最不具体的 scope（即 source.js）；它很少能增加任何价值。
• 根据 "." 分割剩余的每个 scope。
• 去除重复的片段。
• 使用稳定的排序函数对剩余的片段进行排序（不一定是字典序排序）。
• 根据 "." 连接片段。

tokens = [
  { startIndex: 0, type: 'meta.function.js.storage.type' },
  { startIndex: 9, type: 'meta.function.js' },
  { startIndex: 9, type: 'meta.function.js.definition.entity.name' },
  { startIndex: 11, type: 'meta.function.js.definition.parameters.punctuation' },
  { startIndex: 13, type: 'meta.function.js' },
  { startIndex: 14, type: 'meta.function.js.definition.punctuation.block' }
];

*: 我们当时做的事情完全错了，“近似化”是对此的一种非常客气的说法 :)。

然后这些 token 会“适应”并遵循与手动编写的 tokenizer 相同的代码路径（进行二进制编码），然后也会以相同的方式进行渲染

<span class="token meta function js storage type">function</span>
<span class="token meta function js">&nbsp;</span>
<span class="token meta function js definition entity name">f1</span>
<span class="token meta function js definition parameters punctuation">()</span>
<span class="token meta function js">&nbsp;</span>
<span class="token meta function js definition punctuation block">{</span>

TextMate 主题

TextMate 主题使用 scope 选择器，这些选择器选择具有特定 scope 的 token，并对其应用主题信息，例如颜色、粗体等。

给定具有以下 scope 的 token

//            C                     B                             A
scopes = ['source.js', 'meta.definition.function.js', 'entity.name.function.js'];

以下是一些会匹配的简单选择器，按其排名（降序）排列

观察：entity 优先于 meta.definition.function，因为它匹配一个更具体的 scope（分别是 A 优于 B）。

观察：entity.name 优先于 entity，因为它们都匹配相同的 scope（A），但 entity.name 比 entity 更具体。

父选择器

为了让事情稍微复杂一些，TextMate 主题也支持父选择器。以下是一些同时使用简单选择器和父选择器的示例（同样按其排名降序排列）

观察：source entity 优先于 entity，因为它们都匹配相同的 scope（A），但 source entity 也匹配一个父 scope（C）。

观察：entity.name 优先于 source entity，因为它们都匹配相同的 scope（A），但 entity.name 比 entity 更具体。

注意：还有第三种选择器，涉及排除 scope，我们在这里不讨论。我们没有增加对这种选择器的支持，并且注意到它在实际应用中很少使用。

VS Code 1.8 中的 TextMate 主题

以下是两个 Monokai 主题规则（为了简洁起见，这里是 JSON 格式；原始格式是 XML）

...
// Function name
{ "scope": "entity.name.function", "fontStyle": "", "foreground":"#A6E22E" }
...
// Class name
{ "scope": "entity.name.class", "fontStyle": "underline", "foreground":"#A6E22E" }
...

在 VS Code 1.8 中，为了匹配我们“近似化”的 scope，我们会生成以下动态 CSS 规则

...
/* Function name */
.entity.name.function { color: #A6E22E; }
...
/* Class name */
.entity.name.class { color: #A6E22E; text-decoration: underline; }
...

然后我们让 CSS 根据“近似化”的规则匹配“近似化”的 scope。但是 CSS 匹配规则与 TextMate 选择器匹配规则不同，尤其是在排名方面。CSS 排名基于匹配的类名数量，而 TextMate 选择器排名有明确的 scope 特异性规则。

这就是为什么 VS Code 中的 TextMate 主题看起来还可以，但永远不会完全像其作者所期望的那样。有时差异很小，但有时这些差异会完全改变主题的感觉。

一些有利的因素

随着时间的推移，我们逐步淘汰了手动编写的 tokenizer（最后一个是针对 HTML 的，就在几个月前）。因此，今天的 VS Code 中，所有文件都使用 TextMate 语法进行 tokenization。对于 Monaco 编辑器，我们已将大多数支持的语言迁移到使用 Monarch（一种描述性的 tokenization 引擎，核心上类似于 TextMate 语法，但表达能力更强，可以在浏览器中运行），并且我们为手动 tokenizer 添加了一个包装器。总而言之，这意味着支持新的 tokenization 格式需要更改 3 个 token 供应商（TextMate、Monarch 和手动包装器），而不是超过 10 个。

几个月前，我们审查了 VS Code 核心中所有读取 token 类型的代码，我们注意到这些使用者只关心字符串、正则表达式或注释。例如，括号匹配逻辑会忽略包含 "string"、"comment" 或 "regex" scope 的 token。

最近，我们从内部合作伙伴（Microsoft 内部使用 Monaco 编辑器的其他团队）那里获得了许可，他们不再需要在 Monaco 编辑器中支持 IE9 和 IE10。

可能最重要的是，编辑器中最受好评的功能是 迷你地图支持。为了在合理的时间内渲染迷你地图，我们不能使用 DOM 节点和 CSS 匹配。我们可能会使用 canvas，并且我们需要知道每个 token 在 JavaScript 中的颜色，这样我们才能用正确的颜色绘制那些微小的字母。

也许我们取得的最大突破是，我们不需要存储 token 及其 scope，因为 token 仅在主题匹配它们或括号匹配跳过字符串方面产生影响。

最后，VS Code 1.9 的新功能

表示 TextMate 主题

一个非常简单的主题可能看起来像这样

theme = [
  {                                  "foreground": "#F8F8F2"                           },
  { "scope": "var",                  "foreground": "#F8F8F2"                           },
  { "scope": "var.identifier",       "foreground": "#00FF00", "fontStyle": "bold"      },
  { "scope": "meta var.identifier",  "foreground": "#0000FF"                           },
  { "scope": "constant",             "foreground": "#100000", "fontStyle": "italic"    },
  { "scope": "constant.numeric",     "foreground": "#200000"                           },
  { "scope": "constant.numeric.hex",                          "fontStyle": "bold"      },
  { "scope": "constant.numeric.oct",                          "fontStyle": "underline" },
  { "scope": "constant.numeric.dec", "foreground": "#300000"                           },
];

加载主题时，我们将为主题中出现的每个唯一颜色生成一个 ID，并将其存储到一个颜色 map 中（类似于我们上面为 token 类型所做的那样）

//                          1          2          3          4          5           6
colorMap = ["reserved", "#F8F8F2", "#00FF00", "#0000FF", "#100000", "#200000", "#300000"]
theme = [
  {                                  "foreground": 1                           },
  { "scope": "var",                  "foreground": 1,                          },
  { "scope": "var.identifier",       "foreground": 2, "fontStyle": "bold"      },
  { "scope": "meta var.identifier",  "foreground": 3                           },
  { "scope": "constant",             "foreground": 4, "fontStyle": "italic"    },
  { "scope": "constant.numeric",     "foreground": 5                           },
  { "scope": "constant.numeric.hex",                  "fontStyle": "bold"      },
  { "scope": "constant.numeric.oct",                  "fontStyle": "underline" },
  { "scope": "constant.numeric.dec", "foreground": 6                           },
];

然后，我们将根据主题规则生成一个 Trie 数据结构，其中每个节点都存储已解析的主题选项

观察：constant.numeric.hex 和 constant.numeric.oct 的节点包含将前景色更改为 5 的指令，因为它们继承了 constant.numeric 的此指令。

观察：var.identifier 的节点保留了额外的父规则 meta var.identifier，并将据此回答查询。

当我们想知道一个 scope 应该如何进行主题化时，我们可以查询这个 trie。

例如

tokenization 的更改

VS Code 中使用的所有 TextMate tokenization 代码都位于一个单独的项目 vscode-textmate 中，该项目可以独立于 VS Code 使用。我们更改了在 vscode-textmate 中表示 scope 堆栈的方式，使其成为一个也存储完全解析的 metadata 的不可变链表。

将新的 scope 推入 scope 堆栈时，我们将在主题 trie 中查找新的 scope。然后，我们可以根据从 scope 堆栈继承的内容以及主题 trie 返回的内容，立即计算出 scope 列表的完全解析的前景色或字体样式。

一些示例

从 scope 堆栈弹出时，无需计算任何内容，因为我们可以直接使用存储在前一个 scope 列表元素中的元数据。

以下是表示 scope 列表元素的 TypeScript 类

export class ScopeListElement {
    public readonly parent: ScopeListElement;
    public readonly scope: string;
    public readonly metadata: number;
    ...
}

我们存储 32 位的元数据

/**
 * - -------------------------------------------
 *     3322 2222 2222 1111 1111 1100 0000 0000
 *     1098 7654 3210 9876 5432 1098 7654 3210
 * - -------------------------------------------
 *     xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
 *     bbbb bbbb bfff ffff ffFF FTTT LLLL LLLL
 * - -------------------------------------------
 *  - L = LanguageId (8 bits)
 *  - T = StandardTokenType (3 bits)
 *  - F = FontStyle (3 bits)
 *  - f = foreground color (9 bits)
 *  - b = background color (9 bits)
 */

最后，不再从 tokenization 引擎以对象形式发出 token

// These are generated using the Monokai theme.
tokens_before = [
  { startIndex: 0, scopes: ['source.js', 'meta.function.js', 'storage.type.function.js'] },
  { startIndex: 8, scopes: ['source.js', 'meta.function.js'] },
  {
    startIndex: 9,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.definition.function.js',
      'entity.name.function.js'
    ]
  },
  {
    startIndex: 11,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.parameters.js',
      'punctuation.definition.parameters.js'
    ]
  },
  { startIndex: 13, scopes: ['source.js', 'meta.function.js'] },
  {
    startIndex: 14,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.block.js',
      'punctuation.definition.block.js'
    ]
  }
];

// Every even index is the token start index, every odd index is the token metadata.
// We get fewer tokens because tokens with the same metadata get collapsed
tokens_now = [
  // bbbbbbbbb fffffffff FFF TTT LLLLLLLL
  0,
  16926743, // 000000010 000001001 001 000 00010111
  8,
  16793623, // 000000010 000000001 000 000 00010111
  9,
  16859159, // 000000010 000000101 000 000 00010111
  11,
  16793623 // 000000010 000000001 000 000 00010111
];

并使用以下方式渲染

<span class="mtk9 mtki">function</span>
<span class="mtk1">&nbsp;</span>
<span class="mtk5">f1</span>
<span class="mtk1">()&nbsp;{</span>

token 直接从 tokenizer 作为 Uint32Array 返回。我们保留了支持的 ArrayBuffer，对于上面的示例，在 Chrome 中占用 96 字节。元素本身应该只占用 32 字节（8 个 32 位数字），但同样，我们可能观察到一些 v8 元数据开销。

一些数据

为了获得以下测量结果，我选择了三个具有不同特性和不同语法的文件

我在 Windows 上的一台性能尚可的台式机上运行了测试（该机器使用 Electron 32 位）。

我不得不对源代码进行一些更改，以便进行公平比较，例如确保在两个 VS Code 版本中使用完全相同的语法，关闭两个版本中的富语言特性，或者解除 VS Code 1.8 中已在 VS Code 1.9 中不再存在的 100 堆栈深度限制等。我还不得不将 bootstrap.min.css 分割成多行，以使每行字符数少于 2 万。

Tokenization 时间

Tokenization 在 UI 线程上以让步方式运行，因此我不得不添加一些代码强制其同步运行，以测量以下时间（显示 10 次运行的中位数）

虽然 tokenization 现在也进行主题匹配，但时间节省可以通过对每行进行一次遍历来解释。而之前，需要进行一次 tokenization 遍历，第二次遍历将 scope“近似化”为字符串，第三次遍历将 token 二进制编码，现在 token 直接从 TextMate tokenization 引擎以二进制编码的方式生成。需要进行垃圾回收的生成对象数量也大幅减少。

内存使用

代码折叠消耗大量内存，特别是对于大文件（这是以后要优化的内容），因此我在关闭代码折叠的情况下收集了以下堆快照数据。这显示了模型占用的内存，不包括原始文件字符串

内存使用减少的原因可以解释为不再保留 token map，具有相同元数据的连续 token 的合并，以及使用 ArrayBuffer 作为支持存储。我们可以在这里进一步改进，始终将仅包含空白字符的 token 合并到前一个 token 中，因为空白字符渲染成什么颜色都无关紧要（空白字符是不可见的）。

新的 TextMate Scope Inspector 小部件

我们添加了一个新的小部件来帮助编写和调试主题或语法：您可以在命令面板中运行 Developer: Inspect Editor Tokens and Scopes (⇧⌘P (Windows, Linux Ctrl+Shift+P))。

验证更改

对编辑器中的这个组件进行更改存在一些严重风险，因为我们方法中的任何错误（新的 trie 创建代码、新的二进制编码格式等）都可能导致用户可见的巨大差异。

在 VS Code 中，我们有一套集成测试，它验证我们在五种主题（Light、Light+、Dark、Dark+、High Contrast）中提供的所有编程语言的颜色。这些测试对于修改我们的某个主题以及更新某个语法都非常有帮助。73 个集成测试中的每一个都包含一个固定文件（例如 test.c）和五种主题的预期颜色（test_c.json），并且它们在我们 CI 构建 的每次提交时运行。

为了验证 tokenization 更改，我们使用旧的基于 CSS 的方法，从这些测试中收集了我们随 VS Code 提供的所有 14 种主题（不仅仅是我们编写的五种主题）的着色结果。然后，在每次更改后，我们使用新的基于 trie 的逻辑运行相同的测试，并使用自定义的可视化差异（和补丁）工具，我们会查看每一个颜色差异，找出颜色更改的根本原因。我们使用这种技术至少发现了 2 个 bug，并且能够更改我们的五种主题，以使不同 VS Code 版本之间的颜色变化最小。

之前和之后

以下是各种颜色主题在 VS Code 1.8 和现在的 VS Code 1.9 中的外观

Monokai 主题

Quiet Light 主题

Red 主题

总结

希望您会赞赏升级到 VS Code 1.9 后获得的额外 CPU 时间和内存，并且我们将继续赋能您以高效愉快的方式编写代码。

愉快地编程！

Alexandru Dima，VS Code 团队成员 @alexdima123