GitHub用Tree-sitter理解代码仓库

在讨论 GitHub 之前，你需要先了解 Tree-sitter 是什么。

Tree-sitter 是一个免费开源的解析器生成器和增量解析库。它读取源代码并将其转换为具体语法树（CST）——一种结构化的层次化表示，反映代码的含义，而不仅仅是原始文本的样子。

当你编写代码时，普通的文本编辑器看到的是一系列字符。而 Tree-sitter 看到的要丰富得多：一个由命名节点组成的树，每个节点都有类型、位置以及与其他节点的关系。

这是一个简单的 Python 函数：

def greet(name):
    return "Hello, " + name

对 Tree-sitter 来说，它会变成这样的树：

function_definition
  name: identifier "greet"
  parameters: (name)
  body:
    return_statement
      binary_expression
        string "Hello, "
        identifier name

可以把它想象成英语课上的句子分析：把"猫坐在垫子上"分解为主语、谓语和介词短语。Tree-sitter 对代码做的是完全相同的事情，适用于几乎任何编程语言。

1、起源：诞生于 GitHub，源自 Atom

Tree-sitter 最初由 GitHub 开发，用于 Atom 文本编辑器，于 2018 年首次发布。它的创造者是 Max Brunsfeld，GitHub Atom 团队的工程师。白天推动 Atom 向 1.0 版本发布的同时，Max 在晚上和周末构建了 Tree-sitter。

Max 在 2018 年的 Strange Loop 大会上描述了他的动机：Atom 中现有的语法高亮工具依赖正则表达式，这在复杂代码上会产生不一致的结果并崩溃。他想要一个真正理解语法的解析器。

Tree-sitter 就是那个解析器。它使用广义 LR（GLR）解析算法，这意味着它可以处理大多数真实编程语言中存在 的歧义而不会卡住。当解析器遇到歧义点——比如一个表达式可以有两种不同的解读方式时——它会分叉成两个解析栈并同时跟踪两条路径，随着更多输入的到来丢弃无效的那条。

2、为什么 GitHub 需要大规模使用它

GitHub 是世界上最大的代码托管平台。每次你打开文件、搜索符号、点击"跳转到定义"或浏览差异时，GitHub 都需要理解文件中的内容，而不仅仅是将其作为文本渲染。

在 Tree-sitter 之前，语法高亮依赖正则表达式模式。正则表达式可以猜测被引号包围的单词可能是一个字符串，但它无法判断给定的标识符是函数名、变量、类，还是碰巧看起来像代码的注释。

以下是两种方法的基本区别：

根据 Tree-sitter 官方文档，tree-sitter-highlight 库现在被 GitHub.com 用于高亮多种语言编写的代码。而根据 GitHub 自己的公共代码导航仓库，GitHub 代码导航是使用 Tree-sitter 解析器生态系统实现的。

3、GitHub 实际使用 Tree-sitter 的三个用途

3.1 语法高亮

Tree-sitter 通过一个叫做 highlights 查询的系统来驱动高亮显示。每种语言的语法都附带一个 .scm 文件，使用类似 Scheme 的语法将语法树中的节点类型映射到命名的高亮类别，如 keyword、function、type、string 和 comment。

GitHub 的渲染器将这些类别映射到颜色。因为映射来自实际的语法树而非模式匹配，所以同一个标识符每次出现时都会被一致地着色，并且颜色在语义上是正确的。局部变量和函数调用会被着不同的颜色，即使它们共享相同的名称。

Tree-sitter 的高亮系统还跟踪局部作用域和变量定义。当它看到标记为 @local.reference 的节点时，它会检查该名称是否与外部作用域中较早的 @local.definition 匹配。如果匹配，引用和定义都会获得相同的颜色。这是正则表达式无法实现的精确度。

3.2 代码导航

GitHub 的代码导航——驱动"跳转到定义"和"查找所有引用"——完全通过 Tree-sitter 实现。根据 GitHub 的公共代码导航仓库，GitHub 代码导航使用代码搜索来查找整个仓库中的所有定义和引用，以找到具有给定名称的符号。

这种机制称为标记。每种语言的语法都附带一个 tags.scm 文件，其中包含识别和标记命名实体的查询：函数定义、类定义、方法定义以及对这些实体的引用。

以下是 Python 的一个 tags 查询示例：

(function_definition
  name: (identifier) @name) @definition.function

这告诉 GitHub：找到每个 function_definition 节点，捕获其 name 子节点，并将整个节点标记为函数定义。GitHub 在整个仓库中索引这些捕获，并使用该索引在浏览器中提供导航请求。

3.3 通过 Linguist 进行语言检测

在 Tree-sitter 能做任何事情之前，GitHub 需要知道文件是用什么语言编写的。这个任务属于 Linguist——GitHub 的开源 Ruby 语言检测库。GitHub 使用开源 Linguist 库来确定文件语言，用于语法高亮和仓库统计。

Linguist 检查文件扩展名、文件内容和其他信号来识别每种文件的语言。一旦识别出语言，就会加载正确的 Tree-sitter 语法并开始解析。

4、增量解析的工作原理

Tree-sitter 最重要的特性之一是它是一个增量解析器。当文件发生变化时，Tree-sitter 不会丢弃现有的语法树并重新开始。它识别树的哪部分受到了更改的影响，并仅重新解析该子树。每个未受影响的节点都直接从之前的树中重用。

Tree-sitter 使用增量解析来实现编辑后的高效重新解析，并采用了一种新颖的错误恢复技术，使解析器即使在文件处于无效状态时也能产生有用的结果。

这对 GitHub 的索引管道很重要。当推送提交时，只有受影响文件的更改部分需要重新解析和重新索引。对于拥有数千个文件的大型仓库来说，这是一个显著的性能优势。

下图是当你修改了一个字符时，索引管道的单步处理：

5、语法系统：一个引擎，任何语言

Tree-sitter 将解析器引擎与语言语法分离。引擎用 Rust 和 C 编写。每种语言的语法由语法作者用 JavaScript 编写，Tree-sitter CLI 将其编译为 C 解析器。一个统一的引擎运行所有语言，只有语法文件因语言而异。

要在 GitHub 上获得代码导航支持，一种语言必须首先在 Linguist 中注册，然后该语言的成熟 Tree-sitter 解析器必须作为 Rust crate 发布，并且解析器必须包含有效的 tags.scm 查询。添加语言由 GitHub 决定。拒绝一种语言的常见原因包括解析器不成熟、解析所需资源过多，或在 GitHub 上使用率低。

Go、Haskell、Java、JavaScript、Kotlin、Lua、OCaml、Perl、Python、Ruby、Rust、Swift、Zig 等语言都有语言绑定。

6、完整的 GitHub 管道流程

当你在 GitHub 上打开任何文件时，从浏览器请求到你看到的高亮页面，以下是确切的序列。

7、现在让我们来构建它：逐步工作代码

理论讲够了。下面是如何在 Python 中使用 Tree-sitter 来解析真实代码并查询它，与 GitHub 使用的方式相同。

前提条件

pip install tree-sitter
pip install tree-sitter-python

第 1 步：设置解析器

from tree_sitter import Language, Parser
import tree_sitter_python as tspython

# 加载 Python 语法
PY_LANGUAGE = Language(tspython.language())
# 创建解析器并分配 Python 语法
parser = Parser(PY_LANGUAGE)

这里发生了什么： 我们导入 Tree-sitter 和预构建的 Python 语法包。Language() 包装编译后的语法二进制文件，Parser() 是使用该语法将源代码转换为语法树的引擎。

第 2 步：将源代码解析为语法树

source_code = b"""
def greet(name):
    return "Hello, " + name

def add(a, b):
    return a + b
class Calculator:
    def multiply(self, x, y):
        return x * y
"""
# Tree-sitter 始终处理字节，而不是字符串
tree = parser.parse(source_code)
root_node = tree.root_node
print(root_node.type)         # module
print(root_node.child_count)  # 3

这里发生了什么： 我们将原始字节传递给解析器。Tree-sitter 处理字节以获得性能和编码安全性。它返回一个 Tree 对象。root_node 是语法树的顶部。对于 Python 文件，根始终是一个 module 节点。三个子节点是两个顶级函数和一个类。

第 3 步：遍历语法树

def walk_tree(node, indent=0):
    preview = node.text.decode("utf8")[:30].replace("\n", " ")
    print(" " * indent + f"{node.type}: '{preview}'")
    for child in node.children:
        walk_tree(child, indent + 2)

walk_tree(root_node)
# 示例输出：
# module: ' def greet(name):     return "H'
#   function_definition: 'def greet(name):     return "He'
#     def: 'def'
#     identifier: 'greet'
#     parameters: '(name)'
#     block: '     return "Hello, " + name '
#   function_definition: 'def add(a, b):     return a + b'
#     ...
#   class_definition: 'class Calculator:     def multiply'
#     ...

这里发生了什么： 每个节点都有一个 .type，如 function_definition 或 identifier，以及一个 .text 属性，提供该节点的原始源字节。这是 GitHub 所做一切的基础：遍历树以提取结构。

第 4 步：查询树以查找所有函数

这就是 Tree-sitter 查询语言的用武之地。它使用从 Scheme 借用的 S 表达式语法。这正是驱动 GitHub 代码导航的 tags.scm 文件中使用的格式。

# 与 GitHub 的 tags.scm 文件中使用的相同类型的查询
query = PY_LANGUAGE.query("""
(function_definition
  name: (identifier) @function.name)
""")

captures = query.captures(root_node)
print("找到的函数：")
for node, capture_name in captures:
    line = node.start_point[0] + 1
    print(f"  {node.text.decode()} 在第 {line} 行")

# 输出：
# 找到的函数：
#   greet 在第 2 行
#   add 在第 5 行
#   multiply 在第 9 行

这里发生了什么： 该模式的含义是：找到任何具有 name 子节点（类型为 identifier）的 function_definition 节点，并在标签 @function.name 下捕获该子节点。captures() 调用返回整个树中的每个匹配项。注意它也在 Calculator 类中找到了 multiply。查询递归地遍历整个树。这正是 GitHub 构建驱动代码搜索和导航的符号索引的方式。

第 5 步：编辑后的增量重新解析

# 模拟将 "greet" 重命名为 "greet_user"
new_source = b"""
def greet_user(name):
    return "Hello, " + name
"""

# 告诉 Tree-sitter 具体改变了什么
tree.edit(
    start_byte=5,
    old_end_byte=10,
    new_end_byte=15,
    start_point=(1, 4),
    old_end_point=(1, 9),
    new_end_point=(1, 14),
)
# 传递旧树以启用增量解析
# Tree-sitter 重用未被编辑触及的每个节点
new_tree = parser.parse(new_source, tree)
# 验证结果
query2 = PY_LANGUAGE.query("(function_definition name: (identifier) @fn)")
for node, _ in query2.captures(new_tree.root_node):
    print(node.text.decode())  # greet_user

这里发生了什么： 我们通过提供旧字节范围和新字节范围，以及等效的行和列位置来描述编辑。通过将旧 tree 作为第二个参数传递给 parser.parse()，Tree-sitter 重用每个未更改的节点。只有函数名的 identifier 节点被重新解析。其他所有内容都来自缓存。这就是使系统快速的增量解析。

整合起来：一个迷你 GitHub 符号提取器

from tree_sitter import Language, Parser
import tree_sitter_python as tspython

def extract_symbols(source: str) -> dict:
    PY_LANGUAGE = Language(tspython.language())
    parser = Parser(PY_LANGUAGE)
    tree = parser.parse(source.encode())
    root = tree.root_node
    fn_query = PY_LANGUAGE.query(
        "(function_definition name: (identifier) @fn)"
    )
    cls_query = PY_LANGUAGE.query(
        "(class_definition name: (identifier) @cls)"
    )
    functions = [
        {"name": n.text.decode(), "line": n.start_point[0] + 1}
        for n, _ in fn_query.captures(root)
    ]
    classes = [
        {"name": n.text.decode(), "line": n.start_point[0] + 1}
        for n, _ in cls_query.captures(root)
    ]
    return {"functions": functions, "classes": classes}

code = """
class UserService:
    def create_user(self, name, email):
        pass
    def delete_user(self, user_id):
        pass
def health_check():
    return True
"""
print(extract_symbols(code))
# 输出：
# {
#   'functions': [
#     {'name': 'create_user', 'line': 3},
#     {'name': 'delete_user', 'line': 6},
#     {'name': 'health_check', 'line': 9}
#   ],
#   'classes': [
#     {'name': 'UserService', 'line': 2}
#   ]
# }

这是 GitHub 在每个仓库的每个文件上运行的简化版本。原理是相同的：解析为树，运行查询，提取符号，构建索引。

8、同样使用 Tree-sitter 的编辑器

Tree-sitter 的影响力远不止 GitHub。具有官方 Tree-sitter 集成的文本编辑器包括 GNU Emacs、Neovim、Lapce、Zed、Helix 和 Atom。Zed 编辑器由 Max Brunsfeld 和其他离开 GitHub 的 Atom 校友创立，它将 Tree-sitter 作为编辑基础设施的核心部分。

9、关键要点

Tree-sitter 不是魔法。它是一个精心设计的解析库，具有三个使其成为 GitHub 规模的正确工具的属性。

正确性。 它解析为真实的语法树，而不是基于模式匹配的猜测。输出代表代码在结构上是什么。

速度。 增量解析意味着在第一次解析之后，后续的重新解析只触及受编辑影响的节点。其他所有内容都被重用。

通用性。 一个引擎运行所有语言。只有语法文件因语言而异。这使得用单一统一基础设施支持数十种语言成为可能。

下次你在 GitHub 上点击"跳转到定义"或按名称搜索函数时，一个 Tree-sitter 语法树正在幕后静静地使这成为可能。

原文链接：How GitHub Uses Tree-sitter to Understand Millions of Repos

汇智网翻译整理，转载请标明出处