语法高亮中的优化

2017 年 2 月 8 日 - Alexandru Dima

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

TL;DR TextMate 主题在 VS Code 1.9 中将更符合作者的意图，同时渲染速度更快，内存消耗更少。

语法高亮

语法高亮通常包括两个阶段。令牌被分配给源代码，然后它们被主题定位，分配颜色，瞧，你的源代码就用颜色渲染出来了。它是将文本编辑器变成代码编辑器的唯一功能。

VS Code（和 Monaco Editor）中的分词是逐行、从上到下、单次通过的方式进行的。分词器可以在分词行的末尾存储一些状态，当分词下一行时，该状态将被传回。这是许多分词引擎（包括 TextMate 语法）使用的一种技术，它允许编辑器在用户进行编辑时只对一小部分行进行重新分词。

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

更少见的情况是，在某行输入会导致当前行及其下方某些行（直到遇到相同的结束状态）的重新分词/重新绘制

我们过去如何表示令牌

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

过去，我们手工编写分词器（即使在今天，也无法可行地解释 TextMate 语法，但那是另一个故事）。对于下面的行，我们会从手工编写的分词器中获得以下令牌

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 中，保留这个令牌数组需要 648 字节，因此存储这样一个对象在内存方面相当昂贵（每个对象实例必须为指向其原型、其属性列表等保留空间）。我们目前的机器确实有很多 RAM，但对于 15 个字符的行存储 648 字节是不可接受的。

因此，当时我们提出了一种二进制格式来存储令牌，这种格式一直被使用到包括 VS Code 1.8。鉴于会有重复的令牌类型，我们把它们收集在一个单独的映射（每个文件）中，做法如下

//     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 位。我们的令牌数组最终会看起来像这样，并且该映射数组将在整个文件中重复使用。

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 中，保留这个令牌数组需要 104 字节。元素本身应该只占用 56 字节（7 个 64 位数字），其余部分可能是由于 v8 存储了数组的其他元数据，或者可能以 2 的幂次分配了后端存储。然而，内存节省是显而易见的，并且每行令牌越多，效果越好。我们对这种方法很满意，并且从那时起一直使用这种表示方式。

注意：可能存在更紧凑的令牌存储方式，但将其以可进行二进制搜索的线性格式存储，在内存使用和访问性能方面为我们提供了最佳权衡。

令牌 <-> 主题匹配

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

  <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 个手工编写的分词器，主要用于 Web 语言，这对于一个通用桌面代码编辑器来说肯定是不够的。于是，TextMate 语法应运而生，这是一种描述性地指定分词规则的形式，已被众多编辑器采用。不过有一个问题，TextMate 语法的工作方式与我们手工编写的分词器不太一样。

TextMate 语法通过使用 begin/end 状态或 while 状态，可以推送跨越多个令牌的作用域。以下是 JavaScript TextMate 语法下的相同示例（为简洁起见，忽略了空白）

VS Code 1.8 中的 TextMate 语法

如果我们要对作用域堆栈进行切片，每个令牌基本上都会获得一个作用域名称数组，并且我们会从分词器中得到如下结果

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'
    ]
  }
];

所有令牌类型都是字符串，我们的代码还没有准备好处理字符串数组，更不用说对令牌二进制编码的影响了。因此，我们按照以下策略将作用域数组“近似”*为一个字符串

• 忽略最不具体的作用域（即 `source.js`）；它很少增加任何价值。
• 将每个剩余作用域按“.”分割。
• 去除重复的唯一部分。
• 使用稳定的排序函数（不一定是字典序排序）对剩余部分进行排序。
• 将各部分用“.”连接起来。

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' }
];

*: 我们所做的完全是错误的，“近似”是一个非常客气的说法 :)

这些令牌随后将“适配”并遵循与手动编写的分词器相同的代码路径（进行二进制编码），然后也会以相同的方式渲染

<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 主题使用作用域选择器，这些选择器会选择具有特定作用域的令牌，并对其应用主题信息，例如颜色、粗体等。

给定一个具有以下作用域的令牌

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

以下是一些将匹配的简单选择器，按其等级（降序）排序

观察：`entity` 胜过 `meta.definition.function`，因为它匹配了一个更具体的作用域（分别是 `A` 对 `B`）。

观察：`entity.name` 胜过 `entity`，因为它们都匹配相同的作用域（`A`），但 `entity.name` 比 `entity` 更具体。

父选择器

为了让事情变得更复杂一点，TextMate 主题也支持父选择器。以下是一些同时使用简单选择器和父选择器的示例（同样按等级降序排序）

观察：`source entity` 优于 `entity`，因为它们都匹配相同的作用域（`A`），但 `source entity` 也匹配父作用域（`C`）。

观察：`entity.name` 胜过 `source entity`，因为它们都匹配相同的作用域（`A`），但 `entity.name` 比 `entity` 更具体。

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

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 中，为了匹配我们“近似”的作用域，我们会生成以下动态 CSS 规则

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

然后，我们会将“近似”作用域与“近似”规则的匹配留给 CSS 处理。但是 CSS 匹配规则与 TextMate 选择器匹配规则不同，尤其是在排名方面。CSS 排名基于匹配的类名数量，而 TextMate 选择器排名对作用域特异性有明确的规则。

这就是为什么 TextMate 主题在 VS Code 中看起来还行，但从未完全符合其作者的意图。有时，差异很小，但有时这些差异会完全改变主题的感受。

一些好运降临

随着时间的推移，我们已经逐步淘汰了手工编写的分词器（最后一个是 HTML，仅在几个月前）。因此，在今天的 VS Code 中，所有文件都使用 TextMate 语法进行分词。对于 Monaco Editor，我们已迁移到为大多数支持的语言使用 Monarch（一种描述性分词引擎，其核心与 TextMate 语法相似，但更具表达性，并且可以在浏览器中运行），并且我们为手动分词器添加了一个包装器。总而言之，这意味着支持一种新的分词格式将需要更改 3 个令牌提供程序（TextMate、Monarch 和手动包装器），而不是 10 个以上。

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

最近，我们得到了内部合作伙伴（Microsoft 内部使用 Monaco Editor 的其他团队）的同意，他们不再需要在 Monaco Editor 中支持 IE9 和 IE10。

也许最重要的是，编辑器排名第一的最受欢迎功能是迷你地图支持。为了在合理的时间内渲染迷你地图，我们不能使用 DOM 节点和 CSS 匹配。我们可能会使用画布，并且我们需要在 JavaScript 中知道每个令牌的颜色，以便可以用正确的颜色绘制这些小字母。

我们最大的突破可能是我们不需要存储令牌，也不需要存储它们的作用域，因为令牌只在主题匹配它们或括号匹配跳过字符串方面产生效果。

最后，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，并将其存储到一个颜色映射中（与我们上面处理令牌类型的方式类似）

//                          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`，并将相应地回答查询。

当我们需要知道一个作用域应该如何设置主题时，我们可以查询这个 Trie。

例如

分词的变化

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

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

一些例子

从作用域堆栈中弹出时，无需计算任何内容，因为我们只需使用存储在先前作用域列表元素中的元数据。

以下是表示作用域列表中元素的 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)
 */

最后，不再从分词引擎中将令牌作为对象发出

// 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>

令牌直接从分词器以 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 分成多行，以使每行字符数少于 20k。

分词时间

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

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

内存使用

折叠消耗大量内存，特别是对于大文件（这是另一个时间的优化），所以我收集了以下关闭折叠时的堆快照数字。这显示了模型持有的内存，不包括原始文件字符串。

内存使用量减少的原因是：不再保留令牌映射，连续具有相同元数据的令牌进行了合并，并使用 `ArrayBuffer` 作为后端存储。我们还可以通过始终将仅包含空格的令牌合并到前一个令牌中来进一步改进，因为空格的颜色渲染无关紧要（空格是不可见的）。

新的 TextMate 作用域检查器小部件

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

验证变更

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

在 VS Code 中，我们有一个集成套件，用于断言我们发布的所有编程语言在五个我们编写的主题（Light、Light+、Dark、Dark+、High Contrast）中的颜色。这些测试在更改我们的某个主题以及更新某个语法时都非常有用。每个 73 个集成测试都包含一个夹具文件（例如 test.c）和五个主题的预期颜色（test_c.json），它们会在我们 CI 构建的每次提交时运行。

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

前后对比

以下是各种颜色主题在 VS Code 1.8 和现在 VS Code 1.9 中的显示效果

Monokai 主题

静谧之光主题

红色主题

总结

希望您能体会到升级到 VS Code 1.9 所带来的额外 CPU 时间和内存优势，我们也将继续努力，让您以高效愉悦的方式编写代码。

编码愉快！

Alexandru Dima, VS Code 团队成员 @alexdima123