为低代码平台构建 LSIF 索引器
在过去 2.5 年的 Airkit 工作中，我一直在深入研究低代码的迷人领域。在这次令人大开眼界但又相当曲折的探险中，我开始欣赏抽象的美。通过检查 Airkit 的抽象语法树 (AST) 和我构建语言服务器索引格式 (LSIF) 索引器的旅程，我们将在低代码平台的上下文中探索抽象的力量。要了解什么是低代码，我们必须首先检查什么是计算机程序和编程语言。计算机程序是计算机的指令集，而编程语言是这些指令集的形式语言形式的抽象。提供给编程语言的抽象数量定义了它的“高级”程度。实际上，抽象使得用高级代码编写程序而不考虑低级代码、用 C 编写程序而不考虑汇编代码以及编写汇编代码而不考虑逻辑成为可能盖茨。在 Airkit，我们将低代码视为另一层抽象——一种碰巧是可视化的高级编程语言。与传统的基于文本的编程语言需要扫描和解析才能将源代码转换为解析树，然后将其转换为 AST（抽象语法树）不同，可视化编程语言具有直接构建 AST 的结构化编辑器。这说明了什么是低代码——一种可视化的编码方式。如本例所示，用户实际上可以在阅读和修改底层 AST 时在可视化编辑器模式和更传统的文本编辑器模式之间来回切换。本博客的目标不是深入研究 Airkit AST。然而，直观地了解 Airkit 应用程序的外观对于理解 Airkit 的工作原理非常有用。这个按钮是 Airkit Element 的一个实例，它是 Airkit 应用程序最原始的构建块。元素有很多种，复合元素是由更简单的元素构成的。我们可以看到按钮 AST 实际上是一个复合元素，由描述其文本、样式和事件的元素组成。图 1 中最右侧的面板是检查器。检查器是一组编辑器，允许用户修改元素及其子组件。我们可以看到按钮的检查器对于按钮元素的文本、样式和事件属性有相应的编辑器。我们之前已经看到构成 Airkit 工作室的可视化编辑器只是 Airkit 元素的语法糖。同样，在 React 中，JSX 只是 React 元素上的语法糖。例如，下面是我们如何使用 JSX 在 React 中声明一个按钮。
正如 JSX 只是构建 React 元素的视觉辅助工具一样，Airkit Studio 中的可视化编辑器只是构建 Airkit 元素的视觉辅助工具。这两个框架都是简单的抽象，允许用户使用高级编程语言构建低级元素。 Airkit Studio 是一个 IDE，就像 XCode、VSCode 和 IntelliJ 一样。 IDE 通常由源代码编辑器、调试器、导航/重构工具、错误托盘等组成。这些是帮助程序员编写语法和语义正确的程序的工具，并且都是我们正在开发的 Airkit Studio 中的功能。在剩下的文章中，我将揭开 Airkit 如何支持导航和重构工具（例如查找引用、重命名变量等）背后的奥秘。在我们深入研究技术细节之前，这里有一个重命名变量的快速演示。那么Airkit是如何在毫秒内为用户提供精准的代码导航和重构呢？答案在于语言服务器索引格式 (LSIF)。 LSIF 是编程工具（语言服务器、IDE 等）的标准格式，用于保存有关代码空间的知识。 LSIF 的一个很好的类比是数据库索引，它允许数据库查询有效地从数据库中检索数据，但需要额外的写入和存储空间来维护索引。 LSIF 是一种索引，允许代码查看客户端（例如，代码编辑器）提供自动完成或转到定义等功能，而无需语言分析器实时执行这些计算。如果您想知道 Visual Studio Code 等 IDE 如何为这么多不同的编程语言提供相同的重构/导航工具集，那是因为这些 IDE 的客户端由与语言无关的协议（如 LSIF）提供支持。所以只要有一个用于编程语言的 LSIF 索引器来将该语言的文件转换为 LSIF 数据格式，IDE 就可以使用该语言。选择 LSIF 作为 Airkit 的索引数据模型很容易。经过一些研究，我们认为与构建我们自己的内部协议或使用其他索引格式不同，LSIF 易于理解，支持多种语言，并且得到了 Sourcegraph 和 Github/Microsoft 等多家公司的持续支持。
为了说明 LSIF 如何支持高效的代码导航，我们将使用此代码片段作为示例（来自官方 LSIF 规范）。下面的 JSON 输出是上面 5 行 javascript 的 LSIF 格式： 如您所见，LSIF 只是节点和边的集合。下面的图 2 显示了生成的 LSIF 图的可视化表示。 bar 函数声明在可视化图中标记为 bar[def]。我们还可以在 JSON 输出中找到对应的节点：id 为 9 的节点。 bar[def] 节点是一个范围节点，因为它代表了程序中从第 0 行字符 9 到第 0 行字符 12 的符号。范围节点用开始和结束行/字符唯一标识。那么 VSCode se LSIF 索引如何让用户找到 bar 声明的所有引用呢？用户首先将鼠标悬停在栏声明上，然后单击“查找所有引用”按钮。请注意，将鼠标悬停在表示 bar 中的“b”和 bar 中的“r”的位置上将返回相同的范围节点。 VSCode 客户端将向语言服务器提交包含光标位置的语言服务器请求。查找节点的所有引用的算法如下： 使用光标位置通过行号和字符数来标识范围节点。标识的节点是 bar[def] 。通过取下一个边遍历到[结果集]。结果集具有与用户可以对节点进行的查询类型相对应的传出边，例如引用或定义。
将 textDocument/references 节点带到 referenceResult 节点。 referenceResult 节点包含一个或多个与节点的引用相对应的项目边。沿着两个项目边缘将我们带到 bar[def] 和 bar[ref]，这是 bar[def] 的两个引用。对于那些不熟悉 Airkit 工作室如何工作的人，我建议您看一下这个快速的 Airkit 101 视频。为了演示如何在 Airkit Studio 中使用 LSIF，我们将继续使用之前的按钮示例。首先，我们需要一对定义和引用来使用。我们将首先创建一个定义节点。在图 3 中，我们在 Web Page 下创建了一个名为 foo 的变量，它是 Button 的父元素。图 3 左侧的树是 Web Page 的 UI 层次结构。它还表示每个元素的范围。通常，任何子元素都在父元素的范围内，因此它将具有父元素声明的所有变量。因此，Button 现在可以访问我们刚刚创建的 foo 变量。接下来，让我们为 foo 变量创建一个引用节点。我们现在使用包含 foo 变量的动态表达式，而不是简单的“单击我”。现在我们有了变量定义和变量引用，LSIF 将连接两个范围节点，如图 5 所示。
整个应用程序模型被分成许多小的连接组件，如图 5 所示。每个连接的组件连接一个定义节点和一个参考节点列表。最后，现在我们有了一个连接 foo 定义和引用的 LSIF 索引，我们现在可以在 O(1) 时间内查询 foo 变量的引用。图 6 显示了用户如何进行 LSIF 查询以获取对 foo 变量的引用，图 7 显示了查询的输出。本博文的其余部分将重点介绍我们在实施 LSIF 时面临的有趣技术挑战。我们必须解决的第一个挑战是如何修改 LSIF 协议以使用非文本编程语言。 LSIF 是为基于文本的编程语言构建的：文件、行号和起始字符是节点的一流属性。相比之下，我们将应用程序的 AST 存储为一棵 JSON 树。不过这并不困难——我们只需要找到一种方法来唯一标识 JSON 树中的任何 Airkit 元素。虽然普通文件可以使用行号和字符数来唯一标识符号，但我们可以使用数据路径，它是从 JSON 树的根开始的绝对路径来唯一标识一个元素。在弄清楚协议之后，我们需要设计 LSIF 索引器。 LSIF 只是一种数据格式；没有关于如何构建 LSIF 索引的任何文档。以下是我们必须对索引器做出的一些主要决定： 我们的团队讨论了许多方法，以下是每种方法的一些权衡。目前，每个客户端都有一个状态管理器 (redux) 来保存应用程序定义。当用户编辑应用程序时，将向状态管理器分派命令以将命令应用于应用程序定义。我们最初的方法是让 LSIF 索引器也运行在客户端上。每当状态管理器收到命令时，它都会将新的应用程序定义传递给 LSIF 索引器以每次重建索引。
同步更新的优点是可以保证 LSIF 索引始终是最新的。图 8 显示了系统不同组件之间的通信：用户、状态管理器和 LSIF 索引器。时间从左向右流动。每个请求或响应消息由一个箭头表示。在示例中，对 LSIF 索引的更新是同步执行的。协调器在向用户报告成功之前等待索引器完成索引。这保证了当用户向 LSIF 索引器发出请求时，LSIF 索引器会更新用户提交的最新更改。这种方法的缺点是，由于状态管理器和 LSIF 索引器都驻留在客户端上，并且因为 javascript 是单线程的，所以每次用户对应用程序进行更改时，UI 线程都会被阻塞，直到状态管理器响应成功。为了在 LSIF 索引器更新索引时不阻塞 UI 线程，我们可以将 LSIF 索引器移到服务器上，从而异步更新 LSIF。对于异步更新，有一个问题。如图 9 所示，如果用户在写入后不久查询 LSIF，则数据更改可能尚未到达 LSIF 索引。如果用户查询LSIF索引，看起来他们提交的数据丢失了，所以他们会感到困惑。在这种情况下，我们需要写后读一致性，也称为 read-your-writes 一致性。这种一致性模型保证，如果用户对应用程序模型进行更改并随后向 LSIF 索引发出请求，则该索引将与用户所做的更改保持同步。有多种方法可以通过异步更新实现写后读一致性。一种方法是让客户端记住其最近写入的时间戳。然后我们只需要确保 LSIF 索引不会响应任何请求，直到它与请求的时间戳保持同步。我们可以使用逻辑时间戳代替实际的系统时钟，例如由用户提交给状态管理器的命令形成的日志序列号。异步更新的优点是状态管理器可以在 LSIF 索引器完成索引更新之前成功响应用户。缺点是服务器的额外成本和向服务器发出请求时的延迟。此外，我们需要使索引器具有容错能力。而且，如果我们想保护索引器免受单个节点故障或网络中断的影响，我们需要使索引器分布式。
服务器端索引的一种类似方法是在后台线程中存储和构建 LSIF 索引，例如 Web 工作线程（工作线程可以在不干扰用户界面的情况下执行任务）。这种方法的问题类似于服务器端索引的问题——如果系统不保证写后读的一致性，LSIF 可能会在一瞬间过时。用户向状态管理器提交重命名变量请求以将变量名称从 foo 更改为 bar 状态管理器重命名变量，然后向 LSIF 索引请求 foo 的所有引用 假设用户在状态管理器阶段更新 LSIF 之前查询 LSIF 4、那么用户会得到过时的数据。如图 10 所示，当用户将 foo 变量重命名为 bar，然后查询 bar 的引用，但没有得到重命名的 bar 变量作为回报。后台线程的好处是可以在一个单独的线程上进行繁琐的处理，让UI线程可以运行而不会被阻塞。 web worker 的缺点是额外的复杂性来保证写后读的一致性和额外的复杂性来防止内存泄漏等。而不是每次写入时重建 LSIF 索引，我们可以实时执行增量更新 -时间。这样，我们就可以同步更新 LSIF 索引。然而，增量更新带来了一些有趣的技术挑战。用户将 baz 变量（图 13）插入到数组（图 12）中。我们如何将 LSIF 索引增量更新为使我们从图 12 到图 13 所做的更改？
你可能会想，既然数组是一棵树，每个子节点都有它的索引作为它的键，我们不能只是遍历数组，将 foo 和 bar 的索引增加 1 并将 baz 变量插入图中吗？不幸的是，事情并不像看起来那么容易。虽然三个变量——baz、foo、bar——在语义上通过数组相连，但它们在 LSIF 图中实际上没有相连。图 14 显示 foo 和 bar 实际上是两个断开连接的组件。逐步构建 LSIF 的挑战在于，应用程序模型中具有语义连接的节点可能不会在 LSIF 图中连接。这使得当我们将它们插入数组时很难更新数据路径。当父节点被删除时，它也使得垃圾收集图变得棘手，因为我们需要递归地找到它的所有子节点并删除它们。为了解决这个问题，我们需要一个反向索引，我们可以通过带有前缀的数据路径搜索节点。在图 13 中提供的示例中，我们需要通过数据路径元素 / 搜索 foo 和 bar，并将它们移一。一个很好的数据结构是一个特里。 Tries 是字符串的有序树数据结构，每个节点都与从树中节点的位置推断出的字符串相关联。尝试也称为前缀树，可以通过前缀进行搜索。节点的所有后代都具有与该节点关联的字符串的公共前缀。搜索/插入/删除时间与 term 和 key 的长度成线性关系。使用 trie 可以让我们很容易地找到父节点的子节点给定父节点的数据路径。使用 trie 的缺点是索引它的时间和空间复杂性。此外，截至目前，我们决定不存储 LSIF 索引以缩小该项目的范围。这会将应用程序的初始加载时间增加 O(mn)，其中 m 是应用程序中的节点数。对于普通应用程序，应用程序的节点数可以在 200 到 1000 之间，这使得加载时间不重要。在理想的世界中，如果我们能够开发一个健壮且高效的增量更新算法，我们将能够通过快速、同步的更新来避免棘手的竞争条件。该方法的问题在于它容易出错并且难以实施和维护。此外，与某些项目可以在没有完全完成的情况下逐个交付的项目不同，LSIF 索引器要么有效，要么无效。因此，增量更新方法的风险更大。我们构建的初始原型是在每次用户更新后同步重建整个 LSIF 索引。在 KISS（保持简单，愚蠢）方法的推动下，我们决定测试这种方法能走多远。为了测试性能，我们使用 0.1 MB 到 4 MB 的 JSON 文件测试了应用程序。大多数应用程序都小于 1 MB，索引该大小的应用程序大约需要 10 到 100 毫秒，时间的顺序随着应用程序的大小大致增加。我们测试的最大应用程序是 4 MB，有超过 180,000 行 JSON 和超过 37,000 个 Airkit 元素。重建 LSIF 索引平均需要大约 600 毫秒。鉴于 Airkit 的核心价值之一是影响力，我们最终认为，就目前而言，朴素的 LSIF 索引器的性能对于大多数应用程序来说已经足够了。它还使我们不必处理竞争条件或维护额外的服务器/网络工作者。
我们可能已经探索了许多曲折的路径来构建 LSIF 索引器，但最终，我们能够找到一个实用的解决方案，使我们能够提供我们希望提供的功能。虽然这个解决方案在性能方面不是最佳的，但它使我们能够在相对较短的时间内产生最大的影响。在 Airkit 工作最令人兴奋的事情之一是我们可以构建我们自己作为程序员喜欢使用的工具和抽象，例如类型检查器、IDE 工具、UI 框架等。此外，构建可视化编程语言和分布式运行时使我们能够应用来自迷人的计算机科学领域的理论知识并深入研究这些领域，例如编译器、类型理论、分布式系统、数据库等。如果您对这些类型的技术挑战感兴趣，我们正在招聘！在此处查看我们的空缺职位。特别感谢 Ari、Fabian、Aria、Aaron、Joe、Sean、Warren 对内容的审阅和帮助！
