🏠

Tree Sitter 的故事

Table of Contents

1. 树上的男爵

那时候在读卡尔维诺的小说集《我们的祖先》，译林出版社，吴正仪翻译。

calvino.jpg

Figure 1: Italo Calvino

《我们的祖先》是三部曲，包括

  1. 分成两半的子爵
  2. 树上的男爵
  3. 不存在的骑士

有人说这三个故事代表通向自由的三个阶段

  1. 摆脱不完整的人生
  2. 找到通向完整的道路
  3. 争取生存

我其实看不出来，只是单纯喜欢这种跳跃的语言。后来读作者晚年的《美国讲 稿》，卡尔维诺自己也说写的就是“轻”，“快”的感觉。

读卡尔维诺也是受王小波影响。王小波语言明快，是“初代程序员”，手搓汇编， 开发编辑器、输入法，是雷军的前辈，和求伯君平齐。

wangxiaobo.jpg

Figure 2: 王小波

2. 黑色的森林

而今一看到 Tree Sitter 就想到卡尔维诺《树上的男爵》。Tree Sitter 绑了 个软梯，而编辑器坐了上去。

tree-sitter-small.png

Figure 3: Tree Sitter

小小编辑器，爬到树上干什么？或者用妈妈的话讲，地大容不下你，非得爬到树 上。《树上的男爵》的经验，那是为了追求完整的人生。不上树人生就不完整。 十二岁上树，一辈子待在树上，更不能人生完整。人世间有多少种树？人世间有 多少树，计算机就有多少语言。其中有 C 语言。Tree Sitter 这架软梯，就是用 C 语言写的。当我们谈论 Tree Sitter 的时候，我们在谈论什么？几种情况吧

  1. tree-sitter 命令行，在 CachyOS 下 yay -S tree-sitter-cli 安装
    1. tree-sitter init - 生成语法库框架
    2. tree-sitter generate - 生成代码
    3. tree-sitter build - 构建，前三个命令用于生成新语言库
    4. tree-sitter parse - 解析
    5. tree-sitter query - 查询
    6. tree-sitter highlight - 语法加亮，Github 基于此实现
  2. tree-sitter 的库， tree-sitter 前面和后面可以加个语言，比如
    1. python-tree-sitter , 加在前面，表示可以在 python 语言里调用的 tree-sitter 库, 叫语言绑定 binding
    2. python-tree-sitter-python, 加在后面，表示解析 python 语言的 tree-sitter 插件库，由于还有前缀 python ，表示这个插件库插到 python-tree-sitter 里，叫语法 grammar。

支持的语法 Grammar 那就多了，世间多少树，计算机就有多少语言，Tree Sitter 就有多少 Grammar 。如果没有，那就用 tree-sitter 造一个。

tree-sitter 支持的语言绑定 binding

  1. C/C++
  2. Go
  3. Node
  4. Java
  5. Python
  6. Rust
  7. Swift
  8. Zig

语言绑定与语法 Grammar 叉乘一下，可望见一片磅礴的黑森林。

programming-languages-forest.png

3. 精神衣钵的枷锁

在这些语言里，有一门语言，具有最纯正的 C 语言血脉，甚至由 UNIX 之父亲 手打造，因此和 C 语言关系最差。

Ken_Thompson,_2019.jpg

Figure 4: Ken Thompson

Go 继承了 C 语言精神衣钵，却与 C 语言运行时关系最差。Go 语言与 C 语言 的桥梁是 Cgo——Cgo 允许 Go 程序直接调用 C 代码，在以下情况使用：

  • 需要重用已有的 C 库（如 libav, libcurl, openssl）
  • 需要 Go 未暴露的底层系统调用
  • C/C++ 遗留代码迁移到 Go
/*
#include <stdlib.h>
#include <string.h>

// Example C function
char* greet(const char* name) {
    char* buffer = malloc(100);
    snprintf(buffer, 100, "Hello %s", name);
    return buffer;
}
*/
import "C"

import "unsafe"

func main() {
    name := C.CString("Mehul")
    defer C.free(unsafe.Pointer(name))

    greeting := C.greet(name)
    defer C.free(unsafe.Pointer(greeting))

    fmt.Println(C.GoString(greeting))
}

tree-sitter 就是一个 C 语言的库，在 Go 语言中调用就叫 Go binding, 自然 使用 go-tree-sitter ^1 

package main

import (
    "fmt"

    tree_sitter "github.com/tree-sitter/go-tree-sitter"
    tsjs "github.com/tree-sitter/tree-sitter-javascript/bindings/go"
)

func main() {
    code := []byte("const foo = 1 + 2")

    parser := tree_sitter.NewParser()
    defer parser.Close()
    parser.SetLanguage(tree_sitter.NewLanguage(tsjs.Language()))

    tree := parser.Parse(code, nil)
    defer tree.Close()

    root := tree.RootNode()
    fmt.Println(root.ToSexp())
}

这样，你的 Go 程序就傍上 Cgo 了。你编译 Go 程序需要 C 编译器和运行时如影随形。

cgo01.png

Figure 5: cgo and host C compiler

你跨平台的时候得问问 Cgo 同意不同意。Cgo 要是不同意你就跨不了，在 Linux 上 编译出所有架构的日子一去不返 

# Build a single release binary, then gzip + sha256
define build-release
        GOOS=$(word 1,$(subst /, ,$(1))) \
        GOARCH=$(word 2,$(subst /, ,$(1))) \
        CGO_ENABLED=0 \
        go build -trimpath -ldflags="-s -w" -o $(RELEASE_DIR)/$(2) $(CMD_PATH)
        $(if $(HAVE_UPX),upx --best --lzma $(RELEASE_DIR)/$(2),true)
        gzip -fk $(RELEASE_DIR)/$(2)
        cd $(RELEASE_DIR) && $(SHA256_CMD) $(2).gz > $(2).gz.sha256
endef

.PHONY: release
release:
        @mkdir -p $(RELEASE_DIR)
        $(call build-release,linux/amd64,$(BINARY)-linux-amd64)
        $(call build-release,linux/arm64,$(BINARY)-linux-arm64)
        $(call build-release,darwin/amd64,$(BINARY)-darwin-amd64)
        $(call build-release,darwin/arm64,$(BINARY)-darwin-arm64)
        $(call build-release,windows/amd64,$(BINARY)-windows-amd64.exe)
        $(call build-release,windows/arm64,$(BINARY)-windows-arm64.exe)
        @echo "---"
        @echo "Release artifacts in $(RELEASE_DIR)/:"
        @ls -lh $(RELEASE_DIR)/

4. 沉重的自由

Tree Sitter Cgo Free 是说如何在 Go 语言中使用 Tree Sitter ，同时又不触 碰 Cgo。

比如基于 Python Tree Sitter 的方案。在 Python 里调用 Python Tree Sitter，在 Go 里调用 Python，从输入传参，从输出得结果。 


+-----+       +--------+    +---------------------+
|     +------>|        +--->| python-tree-sitter  |
|dscli|       |parse.py|    | -{c, go, java, zig, |
|(Go) |<------+        |<---+ markdown, rust,...} |
+-----+       +--------+    +---------------------+

这方案可以用到 Tree Sitter 又不触碰 Cgo，但一次 Tree Sitter 解析需要几秒 时间，同时又依赖：

  1. python
  2. python-tree-sitter
  3. python-tree-sitter-{python, go, c, html, markdown, …}

其中 Tree Sitter Markdown 是一个复合 Tree Sitter，一般 Markdown 里有代 码块，代码块的解析又会用到代码语言的 Tree Sitter。这样去了 Cgo 这头牛 又牵来 Python 这头象，委实沉重。

5. Ccgo 上树计划

ccgo ^2 说摆脱 Cgo 的办法可以把 C 语言转译为 Go 语言。这是 ccgo 心目中的 C 现代化之路，有几个成功的案例

  1. modernc.org/sqlite - Cgo free 的 Sqlite
  2. modernc.org/tk9.0 - CGo free 的跨平台 GUI 工具包

ccgo-logo.png

Figure 6: ccgo logo，把 C 吞到 Go 的肚子里

Go 中使用 Tree Sitter 还可以基于 ccgo 转译。 ccgo 把 C 语言转译为 Go 语言，结果也是 Cgo Free 的。 

go install -v modernc.org/ccgo/v4@latest

ccgo 由 cznic（捷克无名氏）长期维护。代表项目 modernc.org/sqlite 就是 由 sqlite c 转为 Go ，性能、稳定性、完备性都是很好的。

用 ccgo 转译 tree-sitter 需要转译以下内容：

  1. tree-sitter 库（ tree-sitter CLI 其实不需要转）， tree-sitter 库已 经转好了，
  2. tree-sitter-{grammar}，这就多了去了，我已经转的有
    1. tree-sitter-c
    2. tree-sitter-python

转换过程还算顺利，期间遇到几个 ccgo 小问题也已修复。捷克无名氏 （cznic）对外不发声音，对内代码的沟通极其详尽而顺畅。考虑 AI Editor 对 tree sitter 语言的要求基本是全要，算下来有将近 300 种，工程浩大。已转 的两个（C, Python）质量是可以的。

Tree Sitter Go 包设计 

treesitter -- tree-sitter
├── clang  -- tree-sitter-c
├── python -- tree-sitter-python

在这个设计下，每用到一种语言的 Tree Sitter，都要显式 import 。现在看这 不是一个好设计。因为代码加载解析是动态的，显式 import 很不方便。

6. 纯粹的刚烈

odvcencio 的 gotreesitter 让人惊艳 

go get github.com/odvcencio/gotreesitter

github.com/odvcencio/gotreesitter 是一个纯 Go 的 Tree Sitter，在功能上 与 tree-sitter 库， tree-sitter-cli , 以及 tree-sitter-{lang,...} 几百 种语言库等价。迄今 gotreesitter 支持 206 种语言。其开发动机是在 Go 里实现 Cgo Free

  1. 完全消除 C 依赖，
  2. 其中 parser, lexer，query engine, incremental reparsing，arena allocator, 外部 scanner, tree cursor 等用 Go 重新实现，而不是转译，
  3. 唯一导入的是从 parser.c 抽取的 grammar blob，用工具 ts2go

这是一个雄心勃勃的项目，技术品味高，手段刚烈，简单留给用户 

import (
    "fmt"

    "github.com/odvcencio/gotreesitter"
    "github.com/odvcencio/gotreesitter/grammars"
)

func main() {
    src := []byte(`package main

func main() {}
`)

    lang := grammars.GoLanguage()
    parser := gotreesitter.NewParser(lang)

    tree, _ := parser.Parse(src)
    fmt.Println(tree.RootNode())
}

查询引擎支持完整 S-expression pattern 

q, _ := gotreesitter.NewQuery(
   `(function_declaration name: (identifier) @fn)`, lang)
cursor := q.Exec(tree.RootNode(), lang, src)

for {
    match, ok := cursor.NextMatch()
    if !ok {
        break
    }
    for _, cap := range match.Captures {
        fmt.Println(cap.Node.Text(src))
    }
}

支持编辑（replace, insert, delete） 

rw := gotreesitter.NewRewriter(src)
rw.Replace(funcNameNode, []byte("newName"))
rw.InsertBefore(bodyNode, []byte("// added\n"))
rw.Delete(unusedNode)

newSrc, _ := rw.ApplyToTree(tree)
newTree, _ := parser.ParseIncremental(newSrc, tree)

7. 弹弓代码上树

GoTreeSitter 是我梦寐以求的，刚好满足我在 slingshot ^3规划的代码上树计划。

slingshot-code-mcp.png

基于 GoTreeSitter 实现，实现过程中参考了 codebase-memory-mcp ^4 

// GetNode 按字节位置获取最小节点。
func (ed *Editor) GetNode(uri string, pos uint32) (NodeInfo, error) {
        doc, err := ed.getOrOpenDocument(uri)
        if err != nil {
                return NodeInfo{}, err
        }
        doc.Lock()
        defer doc.Unlock()
        ed.reloadIfExternalModified(doc)

        if doc.tree == nil {
                return NodeInfo{}, ErrDocumentNotReady
        }
        root := doc.tree.RootNode()
        node := root.DescendantForByteRange(pos, pos)
        if node == nil {
                return NodeInfo{}, ErrNodeNotFound
        }
        return nodeToInfo(node, doc.language, doc.source), nil
}

对外暴露 MCP 服务（stdio） 

// NewServer creates a new MCP server with the given store, analyzer, and options.
func NewServer(store *base.Store, analyzer *lsp.Analyzer, opts *Options) *Server {
        ed := edit.NewEditor(opts.ProjectRoot)
        return &Server{
                store:    store,
                analyzer: analyzer,
                ed:       ed,
                opts:     opts,
        }
}

数据库继续用 modernc.org/sqlite 

        _ "modernc.org/sqlite"
)

// Store provides SQLite-backed code graph storage.
// It manages projects, nodes, edges, ADRs, memos, and traces.
// All public methods are safe for concurrent use.
type Store struct {
        mu   sync.RWMutex
        db   *sql.DB
        path string
}

// OpenStore opens (or creates) a SQLite database at the given path.
// The schema is automatically initialized on first use.
func OpenStore(dbPath string) (*Store, error) {
        db, err := sql.Open("sqlite", 
        dbPath+"?_journal_mode=WAL&_cache_size=-65536")
        if err != nil {
                return nil, fmt.Errorf("open sqlite: %w", err)
        }

        // WAL mode + synchronous=NORMAL for better concurrency
        pragmas := []string{
                "PRAGMA journal_mode=WAL",
                "PRAGMA synchronous=NORMAL",
                "PRAGMA busy_timeout=5000",
                "PRAGMA foreign_keys=ON",

配置到 dscli ^5 

mcp-servers {
  code {
    name = code
    type = local
    command = slingshot
    args = ["code", "serve"]
    enabled = true
  }
}

dscli tool list --category code , mcp 工具列表 

名称分类描述
code_analysis           code   Analyze code complexity
code_delete_project     code   Delete a project from th
code_detect_changes     code   Detect code changes and
code_edit_body          code   Replace the body of a de
code_edit               code   Edit a file with write-t
code_find_references    code   Find all references to a
code_get_architecture   code   Get high-level architect
code_get_code_snippet   code   Read source code for a f
code_get_definitions    code   Get all definition tags 
code_get_graph_schema   code   Get the schema of the kn
code_get_node           code   Get AST nodes from a fil
code_get_project_root   code   Get the current project 
code_get_structure      code   Get the hierarchical cod
code_get_text           code   Get source text from a f
code_index_repository   code   Index a repository into 
code_index_status       code   Get the indexing status 
code_ingest_traces      code   Ingest runtime traces to
code_list_projects      code   List all indexed project
code_locate             code   Locate a symbol definiti
code_manage_adr         code   Create or update Archite
code_open_project       code   Switch to a different pr
code_query_ast          code   Execute a tree-sitter S-
code_query_graph        code   Execute a SQL query agai
code_save_memo          code   Save a persistent memory
code_search_code        code   Graph-augmented code sea
code_search_graph       code   Search the code knowledg
code_search_memos       code   Search persistent memori
code_trace_path         code   Trace paths through the 
code_validate           code   Validate a file's syntax

那这个 slingshot code mcp 工具就用起来了。除了在 dscli 用，在其他 Code Agent 原则上也可以用，因为标准 mcp 服务的缘故。

Footnotes:

1

参见：https://github.com/tree-sitter/go-tree-sitter

2

参见：https://gitlab.com/cznic/ccgo

3

参见：https://github.com/nanjj/slingshot

4

参见：https://github.com/deusdata/codebase-memory-mcp

5

参见: https://github.com/dscli/dscli