为什么 Tree-Sitter 不适合程序分析

# 为什么 Tree-Sitter 不适合程序分析 来源：https://www.cubix-framework.com/tree-sitter-limitations.html Cubix 的一大优点是它能很好地集成许多第三方解析器。在最新更新中：如果你的语言有 Tree-Sitter 语法，那么你可以相对快速地获得 Cubix 对该语言的支持。 所以你可能会看到这个并问：“我已经有了 Tree-Sitter 解析器，而且我只关心一种语言；为什么我不能直接使用 Tree-Sitter 呢？” 除非你在构建语法高亮工具：否则这是个极糟糕、极糟糕的选择。 这就是为什么构建 Cubix 的 Tree-Sitter 集成比预期困难得多，也是如果你选择将 Cubix 与 Tree-Sitter 解析器一起使用而不是直接使用 Tree-Sitter，你将避免的所有痛苦的缩影。 ## 你无法区分加法和乘法 考虑这段 Sui Move 代码： ``` let a = x + y; let b = x * y; ``` 用 Tree-Sitter 解析这两行。看右侧表达式的 AST。它们是**完全相同**的： ``` (binary_expression left: (identifier) right: (identifier)) ``` `+` 和 `*` 令牌消失了。Tree-Sitter 将它们归类为“匿名节点”，生态系统中的每个工具都默默地丢弃了它们。你无法编写一个能区分加法和乘法的重构工具、静态分析器或公式提取器——这是算术中最基本的语义区分——因为 Tree-Sitter 没有保留它。 这不是特定语法中的 bug。Tree-Sitter 充满了丢弃信息的构造，整个生态系统中的语法都在使用它们。毕竟，如果你只想要语法高亮或跳转定义，那么这些信息是浪费的。但任何更深层次的分析都需要这些。 想要更多例子？你也无法区分 `move x` 和 `copy x`。无法区分 `public`、`public(friend)` 和 `public(package)`。无法区分类型声明了四种能力——`copy`、`drop`、`store`、`key`——中的哪一种。你甚至无法区分 `true` 和 `false`。所有这些都依赖于 Tree-Sitter 丢弃的令牌。 ## 背景 Tree-Sitter 是一个流行的增量解析库，专为**语法高亮和编辑器功能**设计。它生成一个针对文本编辑器需求优化的具体语法树（CST）：快速增量重解析、对不完整输入的容错性，以及足以给令牌着色的结构。它从未设计用于语义分析、程序转换或往返源代码操作。 问题分为三类：主要问题（Tree-Sitter 主动破坏你需要的信息）、结构问题（CST 是该任务的错误表示）以及增加摩擦的次要问题。 本文将大量引用 Sui Move 语法，因为那是我们通过 Tree-Sitter 集成支持的第一种语言。但这里的问题出现在各种语言中。 ## 主要问题 ### 匿名节点被静默丢弃 Tree-Sitter 区分**命名节点**（如 `binary_expression`、`function_definition`）和**匿名节点**（运算符 `+`、`*`、`||`，标点 `(`、`)`、`,`，关键字 `let`、`if`）。所有主流的 Tree-Sitter 库——GitHub 的 semantic (https://github.com/github/semantic)、较新的 hs-Tree-sitter (https://github.com/wenkokke/hs-Tree-sitter)——只遍历命名节点。匿名令牌被丢弃。 这对于任何需要理解代码*做什么*的工具来说，这都是灾难性的： - **运算符消失。** `x + y` 和 `x * y` 变成相同的树。`a == b` 和 `a != b` 变成相同的树。你无法构建符号执行器、公式提取器，甚至是检查运算符用法的 linter。 - **往返所需的标点符号消失。** 圆括号、方括号、逗号、分号——全没了。你无法从 AST 重建源代码。 - **区分构造的关键字消失。** 在 Sui Move 中，`modifier` 是一个命名节点，但其中的关键字——`public`、`package`、`friend`、`entry`、`native`——都是匿名的。遍历命名子节点的工具会看到一个 `modifier` 节点，对于所有五个可见性级别都有零个子节点。同样的模式在整个语法中重复出现：`ability` 包装 `copy`/`drop`/`store`/`key` 没有命名子节点；`primitive_type` 包装九种不同类型（`u8` 到 `u256`、`bool`、`address`、`signer`）没有命名子节点；`move_or_copy_expression` 使 move 和 copy 语义无法区分；甚至 `bool_literal` 使 `true` 和 `false` 相同。 Sui Move 语法使运算符问题尤为严重。二元表达式在 `grammar.js` 中使用 JavaScript 展开语法定义，将每个运算符烘焙到一个单独的 alternative 中： ``` ...table.map(([operator, precedence, associativity]) => prec[associativity](precedence, seq( field('left', $._expression), field('operator', operator), // Anonymous token -- discarded! field('right', $._expression) )) ) ``` 二十种不同的二元运算符，都产生结构相同的 AST 节点。区分它们的*唯一*方法是通过每个库都丢弃的匿名令牌。 ### 没有美化打印机——无法往返 Tree-Sitter 是单行道。它将源代码解析为树。它提供**零**机制用于返回——从树到源代码。 往返属性 `parse(pretty(parse(text))) = parse(text)` 是任何程序转换工具的基本要求。如果你无法将修改后的树渲染回有效的源代码，你的工具就没用了。Tree-Sitter 不支持这个方程的 `pretty` 部分。 必须为每种语言从头编写自定义美化打印机，使用相同的语法定义但方向相反。Tree-Sitter 不提供任何帮助。 ### 邪恶的别名 出于某种原因，Tree-Sitter 支持 `alias()` 规则，允许一个语法规则在 CST 中以不同的名称出现。我们从未弄清楚这有什么用，但足够的语法都有它，所以它一定有用。 例如，Sui Move 语法使用别名给共享规则赋予上下文名称——通用的 `_variable_identifier` 在绑定位置被别名为 `bind_var`，让下游工具知道该标识符是用作绑定器而不是引用。 但别名无法被下游工具直接处理，因为它们引入了一层间接性，而这并没有清晰地反映在 `grammar.json` 中。 我们最终不得不使用一个简短的 `jq` 脚本来预处理语法以移除别名——这是我们唯一不得不更改 Tree-Sitter 语法的地方。 这意味着语法作者分配的每个上下文名称——每一次试图说明“这个标识符是 `bind_var`，而不仅仅是 `identifier`"——都在处理开始前被擦除。语法作者通过别名仔细编码的语义区分被破坏了。 ### FFI 内存安全隐患 所以我们在使用 Tree-Sitter 的 Haskell 绑定进行工作时已经相当深入了，这时我们遇到了段错误。呃哦。怎么回事？ 你看，Tree-Sitter 是一个 C 库。它的 `TSNode` 结构体包含指向创建它的 `TSTree` 和 `TSLanguage` 对象的原始指针。当从垃圾回收语言访问时，这些指针创建了一个隐藏依赖：如果运行时在节点引用仍然存在时垃圾回收了树，你会得到**非确定性段错误**。 标准 Haskell 绑定使用带有 finalizer 的 `ForeignPtr` 调用 `ts_tree_delete`。这意味着 GC 看不到节点和树之间的依赖关系，所以它在节点仍然持有悬空指针时释放了树。 resulting crashes 是间歇性的，似乎与不相关的代码更改相关，花费了数周时间诊断。 任何具有自动内存管理的语言在底层集成 Tree-Sitter 时都会面临这个问题的一个版本。 ## 你仍然想要 AST，而不是 CST 编译器、静态分析器和各种编程工具历来依赖于 AST（**抽象语法树**）。抽象语法树将程序浓缩为其核心有意义的语法。非语义差异，如额外的括号，或 `0xFF` 和 `255` 之间的差异，被剥离，以便工具处理更简单的东西。它们还可以执行其他规范化，例如移除没有 else 块的 if 语句与具有空 else 块的 if 语句之间的差异。 但 Tree-Sitter 不提供 AST。它生成的是 CST（**具体语法树**）。在 Tree-Sitter 引入之前，CST 在语言工程研究人员之外几乎无人知晓。由 Rascal 和 SDF 等工具生成的 CST 对于需要重建原始源代码的应用非常有用。它们也可以直接从语法生成，减少了对关于忽略语法哪些部分的额外信息的需求。与 AST 不同，它们还可以保留注释。 Tree-Sitter 在向更广泛的受众引入具体语法树时，做出了一些有趣的选择，使其非常有效地构建语法高亮器，同时降低了其对大多数其他应用的有用性。与传统的 CST 不同，Tree-Sitter 树损耗非常大（如上所述），这减少了内存消耗但破坏了其用于分析和转换的效用。它们还丢失了语法中的大量信息，这允许简化的 API 并进一步减少内存消耗，代价是使分析格外困难。 我的导师 Ira Baxter 构建程序转换工具已有约 40 年，他写道 (https://stackoverflow.com/a/1685297)“拥有一个解析器 [并获得 AST] 就像攀登喜马拉雅山山麓，而问题是攀登珠穆朗玛峰。”但今天，多亏了 Tree-Sitter，许多工具构建者甚至无法走到那一步。 这里还有更多关于 Tree-Sitter 的问题，与其缺乏 AST 生成有关。 ### 子节点只是一个扁平列表 Tree-Sitter 的语法定义编码了丰富的结构——`seq`、`repeat`、`optional`、`choice`——精确描述了子节点如何分组和排序。但 CST 丢弃了所有这些。每个节点的子节点只是一个扁平的、无类型的列表。 考虑 Sui Move 语法如何定义块： ``` block: $ => seq( '{', repeat($.use_declaration), repeat($.block_item), optional($._expression), '}' ) ``` 语法说：首先是 use 声明，然后是块项（以 `;` 结尾的语句），然后是可选的尾随表达式（块的返回值，没有 `;`）。但 Tree-Sitter 的 `node-types.json` 将 `block` 节点描述为具有 `"fields": {}` 和可以是 40 多种类型中任何一种且顺序任意的子节点。`repeat`/`optional`/`seq` 结构被完全擦除。 或者考虑函数签名，它允许最多三个可选修饰符： ``` _function_signature: $ => seq( optional($.modifier), optional($.modifier), optional($.modifier), 'fun', ... ) ``` 语法定义了三个不同的修饰符槽。CST 给你 0–3 个 `modifier` 子节点，没有关于每个子节点来自哪个槽的位置信息。 这意味着使用 CST 的工具必须**重新推导**语法的分组逻辑。给定一个 `block` 节点，你必须自己弄清楚语句在哪里结束，尾随返回表达式在哪里开始。给定一个函数，你必须通过检查内容而不是位置来弄清楚存在哪些修饰符。 正确的 AST（实际上，正确的 CST 也是）在类型中明确结构： ``` data Block e l where Block :: e [UseDeclarationL] -> e [BlockItemL] -> e (Maybe HiddenExpressionL) -> Block e BlockL ``` 语句和返回表达式在不同的字段中。模式匹配强制区分。运行时没有歧义需要解决。 ### 语法比解析输出更丰富 子节点扁平化问题是更深层次问题的症状：**Tree-Sitter 的语法定义编码的结构远多于其 CST 保留的结构。** 语法使用 `choice()` 定义 alternatives： ``` block_item: $ => seq( choice( $._expression, $.let_statement, ), ';' ) ``` 这说明块项要么是表达式，要么是 let 语句，后跟分号。但 CST 没有为 `choice()` 提供包装节点。你直接看到具体子节点——`let_statement` 或 `call_expression`——没有迹象表明这些是双向选择中的 alternatives。 正确的 AST 将其提取为命名的 sum type： ``` data BlockItemInner e l where BlockItemExpression :: e ExpressionL -> BlockItemInner e BlockItemInnerL BlockItemLetStatement :: e LetStatementL -> BlockItemInner e BlockItemInnerL ``` Tree-Sitter 的语法也使用隐藏规则（以 `_` 为前缀），如 `_expression`、`_type`、`_bind`。这些定义了重要的分类分组——“表达式是以下之一：call、binary、if、while... "——但 Tree-Sitter 在 CST 中**主动抑制**这些节点。语法说 `_expression` 的地方，CST 只显示具体子节点（`call_expression`、`binary_expression` 等），没有包装。 这意味着语法作者的意图——“这 16 种节点类型都是表达式”——丢失了。工具必须通过维护自己的表来重建这些类别，说明哪些具体节点类型属于哪些抽象类别。 ### 原始和字面信息在结构上不可见 Tree-Sitter 将数字字面量等叶节点表示为不透明的 `pattern` 节点——匹配正则表达式的文本。数字 `255`、十六进制字面量 `0xFF` 和分隔符格式化的 `1_000_000` 都只是一个 `pattern` 节点。没有结构区分。 对于语法高亮，这没问题——它们都是数字，把它们涂成蓝色。对于程序分析，这是个问题。需要规范化数字表示、验证字面量格式或保留程序员格式意图的工具无法从 Tree-Sitter CST 获取此信息，除非回退到原始文本匹配。AST 可以将这些表示为具有解析值的不同构造函数。 ## 次要问题 ### `sepBy` 不意味着 `sepBy` Tree-Sitter 的 `sep()`/`sep1()` 组合器，本应代表逗号分隔列表和类似模式，实际上实现了 `sepEndBy` 语义——它们**允许尾随分隔符**。文档没有指出这一点。 这看似次要，但在构建假设标准语义的工具时会导致真正的解析失败。参数列表 `(a, b, c)` 和 `(a, b, c,)` 解析结果相同，使用 Tree-Sitter 输出并应用标准 `sepBy` 逻辑的工具将在尾随逗号上失败。 ### 语法源是 JavaScript，而不是数据 Tree-Sitter 语法是在 JavaScript 文件中定义的，使用了语言的全部功能——高阶函数、展开运算符、计算表。Tree-Sitter 从中生成的 `grammar.json` 是一个扁平化、脱糖的版本，丢失了高级结构。 Sui Move 语法的二元表达式定义使用带有展开的 `table.map()`——在 JavaScript 中清晰易读，但生成的 `grammar.json` 包含 20 个几乎相同的 alternatives，没有表结构的痕迹。任何使用语法的工具都必须逆向工程源代码中显而易见的模式。 ## 底线 Tree-Sitter 旨在使编辑器快速且响应灵敏。它在这方面表现出色。但对于程序分析和转换，它实际上是敌对的： | 你需要的 | Tree-Sitter 给你的 | | :--- | :--- | | 运算符之间的语义区分 | 对于 `+`, `*`, `==`, `!=` 的相同节点 | | 往返解析/打印 | 仅单向解析 | | 结构化、类型的子节点 | 分组信息被擦除的扁平列表 | | 通过别名的上下文节点名称 | 必须移除才能处理语法的别名 | | 稳定 | |