xref Cross-Reference Search Engine — 设计方案

1. 目标

构建一个基于 AST 的代码交叉引用搜索引擎，核心能力：

给定一个符号（类/方法/函数/变量），找到它的定义位置
找到所有调用者（谁调用了它）和被调用者（它调用了谁）
输出一棵调用树（call tree），支持向上和向下展开
支持目录级搜索缓存，增量更新，避免重复解析

2. 现有能力

组件	路径	作用
parser runtime	`parser.go`, `tree.go`	纯 Go tree-sitter 解析，输出 CST
structural grep	`internal/grep`	AST 模式匹配，支持 `$NAME` 变量化
taproot/walk	`internal/taproot/walk`	CST 游标遍历，语法感知
grammars	`internal/grammars`	206 种语言的 grammar blob
query engine	`query.go`, `query_matcher.go`	tree-sitter S-expression 查询执行
language adapters	`parser_result_*.go`	每种语言的 CST → 语义结构适配

缺失的部分：符号提取、引用解析、调用图构建、目录索引、缓存层。

3. 数据模型

┌─────────────────────────────────────────────────────┐
│                    SymbolIndex                       │
│                                                     │
│  symbols: map[SymbolKey]SymbolEntry                 │
│  references: map[SymbolKey][]Reference              │
│  fileIndex: map[string]FileEntry                    │
│  manifest: IndexManifest                            │
└─────────────────────────────────────────────────────┘

SymbolKey {
    Name      string   // "fmt.Println", "MyClass.method"
    Kind      SymbolKind // Func | Method | Class | Variable | Type
    Lang      string   // "go", "python", ...
    FileScope string   // package/module scope (optional)
}

SymbolEntry {
    Key        SymbolKey
    File       string   // 文件路径
    StartByte  uint32
    EndByte    uint32
    Line       int
    Signature  string   // 函数签名、类声明等
    Exported   bool
}

Reference {
    File      string
    StartByte uint32
    EndByte   uint32
    Line      int
    Kind      RefKind // Call | Assign | Import | TypeUse | Inherit
}

FileEntry {
    Path         string
    ModTime      int64
    ContentHash  [16]byte
    Symbols      []SymbolKey  // 此文件中定义的符号
    References   []Reference  // 此文件中的引用
}

IndexManifest {
    RootDir    string
    Version    int
    Files      map[string]FileEntry
    CreatedAt  time.Time
    UpdatedAt  time.Time
}

4. 核心流程

4.1 索引（Index）

walkDir(root)
  for each file with supported extension:
    if file not in cache OR mtime changed:
      parse(file) -> tree
      extractSymbols(tree, lang) -> []SymbolEntry
      extractReferences(tree, lang) -> []Reference
      updateFileEntry(file, symbols, references)
    else:
      reuse cached FileEntry
  rebuild manifest

符号提取策略：利用现有的 parser_result_*.go 适配器。每个语言适配器已经把 CST 节点转换为高级语义结构（函数声明、类声明、import 等）。提取器遍历这些结构：

语言	定义节点	引用节点
Go	`function_declaration`, `method_declaration`, `type_spec`	`call_expression`, `selector_expression`
Python	`function_definition`, `class_definition`, `assignment`	`call`, `attribute`, `identifier`
JS/TS	`function_declaration`, `class_declaration`, `variable_declarator`	`call_expression`, `member_expression`
Rust	`function_item`, `impl_item`, `struct_item`	`call_expression`, `field_expression`
Java	`method_declaration`, `class_declaration`, `field_declaration`	`method_invocation`, `field_access`

4.2 查询（Query）

xref.Lookup(symbolName) -> CallTree

CallTree {
    Symbol   SymbolEntry
    Callers  []CallEdge   // 谁调用了它
    Callees  []CallEdge   // 它调用了谁
}

CallEdge {
    From     SymbolEntry
    To       SymbolEntry
    Ref      Reference
    Line     int
    File     string
}

查询流程：

精确匹配：在 symbols map 中查找 SymbolKey
模糊匹配：支持 * 通配符，如 *.Parse 匹配所有 Parse 方法
调用者查询：扫描 references 找到所有 RefKind=Call 且目标匹配的引用
被调用者查询：解析函数体，找到内部所有 call_expression，解析被调用函数名
递归展开：对结果中的每个符号递归执行 3/4，构建树

4.3 缓存（Cache）

使用 modernc.org/sqlite（纯 Go SQLite，无 CGo）存储索引数据。

.xref-cache/
└── xref.db          # SQLite 数据库

数据库表结构：

-- 文件元数据
CREATE TABLE files (
    path         TEXT PRIMARY KEY,
    mod_time     INTEGER NOT NULL,
    content_hash BLOB NOT NULL,
    lang         TEXT NOT NULL,
    updated_at   INTEGER NOT NULL
);

-- 符号定义
CREATE TABLE symbols (
    id         INTEGER PRIMARY KEY AUTOINCREMENT,
    file       TEXT NOT NULL,
    name       TEXT NOT NULL,
    kind       INTEGER NOT NULL,
    lang       TEXT NOT NULL,
    namespace  TEXT NOT NULL DEFAULT '',
    start_byte INTEGER NOT NULL,
    end_byte   INTEGER NOT NULL,
    line       INTEGER NOT NULL,
    signature  TEXT NOT NULL DEFAULT '',
    exported   INTEGER NOT NULL DEFAULT 0,
    doc        TEXT NOT NULL DEFAULT '',
    FOREIGN KEY (file) REFERENCES files(path) ON DELETE CASCADE
);

-- 引用记录
CREATE TABLE refs (
    id          INTEGER PRIMARY KEY AUTOINCREMENT,
    file        TEXT NOT NULL,
    symbol_name TEXT NOT NULL,
    lang        TEXT NOT NULL DEFAULT '',
    namespace   TEXT NOT NULL DEFAULT '',
    start_byte  INTEGER NOT NULL,
    end_byte    INTEGER NOT NULL,
    line        INTEGER NOT NULL,
    kind        INTEGER NOT NULL,
    FOREIGN KEY (file) REFERENCES files(path) ON DELETE CASCADE
);

差分增量更新策略：

扫描目录，获取所有源文件及其 mtime
查询 SQLite 中已缓存的文件列表和 mtime
对比差异：
- 新文件：解析并插入
- mtime 变化的文件：删除旧记录，重新解析并插入（在单个事务中）
- 已删除的文件：DELETE + CASCADE 自动清理关联的 symbols 和 refs
WAL 模式确保并发读性能

// 伪代码
func (idx *Indexer) Build() error {
    current := discoverFiles()        // 磁盘文件
    cached := loadCachedFromSQLite()  // 已缓存文件

    tx := db.Begin()
    for path := range removed(cached, current) {
        tx.Exec("DELETE FROM files WHERE path=?", path)  // CASCADE
    }
    for path := range addedOrModified(current, cached) {
        tree := parse(path)
        syms, refs := extract(tree)
        tx.Exec("DELETE FROM symbols/refs WHERE file=?", path)
        tx.Exec("INSERT INTO ...", syms, refs)
    }
    tx.Commit()
}

缓存失效条件：

文件 mtime 变化
文件被删除
手动 xref --clear-cache（删除整个 .xref-cache/ 目录）

5. API 设计

5.1 Go API

package xref

// Indexer manages a directory-level symbol index.
type Indexer struct { ... }

// NewIndexer creates an indexer for the given root directory.
func NewIndexer(root string, opts ...IndexOption) *Indexer

// Build (re)indexes the directory. Incremental: only re-parses changed files.
func (idx *Indexer) Build() error

// Lookup finds a symbol by name, returning its definition and call tree.
func (idx *Indexer) Lookup(name string, opts ...LookupOption) (*CallTree, error)

// Callers returns all call sites of the named symbol.
func (idx *Indexer) Callers(name string) ([]CallEdge, error)

// Callees returns all symbols called by the named symbol.
func (idx *Indexer) Callees(name string) ([]CallEdge, error)

// Def returns the definition site of the named symbol.
func (idx *Indexer) Def(name string) (*SymbolEntry, error)

// Grep does a structural pattern search across all indexed files.
func (idx *Indexer) Grep(pattern string) ([]grep.Result, error)

5.2 CLI

# 索引当前目录
xref index .

# 查找符号定义
xref def MyStruct.Parse

# 查找调用者（谁调用了 Parse）
xref callers MyStruct.Parse

# 查找被调用者（Parse 调用了谁）
xref callees MyStruct.Parse

# 完整调用树（向上 2 层，向下 2 层）
xref tree MyStruct.Parse --depth 2

# 结构化搜索
xref grep 'func $NAME($$$) error'

# 清除缓存
xref --clear-cache

6. 实现计划

Phase 1: 符号提取器（Symbol Extractor）

新建 internal/xref/ 包：

internal/xref/
├── symbol.go          # SymbolKey, SymbolEntry, Reference 类型定义
├── extract.go         # 从 CST 提取符号和引用的核心逻辑
├── extract_go.go      # Go 语言专用提取（复用 parser_result_go.go 的模式）
├── extract_python.go  # Python 专用提取
├── extract_js.go      # JS/TS 专用提取
├── extract_generic.go # 通用 fallback（基于节点类型名匹配）
├── extract_test.go
└── lang_pattern.go    # 每种语言的定义/引用节点类型注册表

关键设计：提取器不重复 parser_result_*.go 的逻辑，而是复用 internal/taproot/walk.Walker 遍历 CST，按节点类型名匹配。对于已有 parser_result_* 适配器的语言，提取器可以调用其导出的辅助函数。

Phase 2: 索引与缓存（Index + Cache）

internal/xref/
├── index.go           # SymbolIndex 主结构，Build/Update/Save/Load
├── manifest.go        # IndexManifest 序列化
├── cache.go           # 基于文件 mtime 的增量更新
├── file_entry.go      # FileEntry 管理
└── cache_test.go

Phase 3: 调用图（Call Graph）

internal/xref/
├── callgraph.go       # CallTree, CallEdge, Caller/Callee 查询
├── resolve.go         # 引用 → 定义的解析（跨文件）
├── tree_builder.go    # 递归调用树构建
└── callgraph_test.go

Phase 4: CLI 入口

cmd/xref/
└── main.go            # cobra/标准库 CLI，子命令 index/def/callers/callees/tree/grep

Phase 5: 公开 API

将 internal/xref 的核心类型提升到顶层包，或保持 internal + 提供 thin wrapper：

// xref_index.go (顶层包)
func NewIndexer(root string, opts ...IndexOption) *internal.Indexer { ... }

7. 与现有代码的整合

现有组件	如何复用
`internal/grep.Match()`	用于 `xref grep` 子命令，在单文件内做模式匹配
`internal/taproot/walk.Walker`	符号提取器的 CST 遍历基础设施
`internal/grammars.DetectLanguage()`	根据文件扩展名自动选语言
`parser_result_*.go`	提取器参考其节点类型映射，直接复用辅助函数
`xref.Query`	用于 S-expression 模式的精确匹配
`xref.Parser`	底层解析器，Indexer 内部调用

8. 性能目标

指标	目标
1000 文件索引时间	< 10s（首次），< 2s（增量，10 文件变更）
单符号查询延迟	< 50ms
缓存命中率	> 95%（稳定代码库）
索引大小	< 源码总大小的 20%
内存占用	< 500MB（10k 文件项目）

9. 风险与权衡

跨文件引用解析：静态分析无法 100% 解析动态调用（反射、eval、动态 import）。初始版本只支持静态调用关系，对动态语言（Python/JS）标记为"可能不完整"。

同名符号消歧：不同包/模块中的同名符号需要 namespace 消歧。使用 package.Symbol 形式的 qualified name。

大型项目内存：10k+ 文件的项目可能产生大量符号数据。考虑：

冷数据落盘（badger/bolt）
只在内存中保留符号定义，引用按需从磁盘加载
分层索引：先索引文件级，再按需索引函数体内的引用

语言覆盖：206 种 grammar 不可能每种都有精确的符号提取器。采用分层策略：

Tier 1（精确）：Go, Python, JS/TS, Java, Rust, C/C++ — 专用提取器
Tier 2（通用）：基于节点类型名的 heuristic 匹配
Tier 3（仅 grep）：只支持 xref grep 模式搜索，不支持调用图

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

xref Cross-Reference Search Engine — 设计方案

1. 目标

2. 现有能力

3. 数据模型

4. 核心流程

4.1 索引（Index）

4.2 查询（Query）

4.3 缓存（Cache）

5. API 设计

5.1 Go API

5.2 CLI

6. 实现计划

Phase 1: 符号提取器（Symbol Extractor）

Phase 2: 索引与缓存（Index + Cache）

Phase 3: 调用图（Call Graph）

Phase 4: CLI 入口

Phase 5: 公开 API

7. 与现有代码的整合

8. 性能目标

9. 风险与权衡

Uh oh!

FilesExpand file tree

DESIGN.md

Latest commit

History

DESIGN.md

File metadata and controls

xref Cross-Reference Search Engine — 设计方案

1. 目标

2. 现有能力

3. 数据模型

4. 核心流程

4.1 索引（Index）

4.2 查询（Query）

4.3 缓存（Cache）

5. API 设计

5.1 Go API

5.2 CLI

6. 实现计划

Phase 1: 符号提取器（Symbol Extractor）

Phase 2: 索引与缓存（Index + Cache）

Phase 3: 调用图（Call Graph）

Phase 4: CLI 入口

Phase 5: 公开 API

7. 与现有代码的整合

8. 性能目标

9. 风险与权衡