avatar
原创2025/06/20

Code Graph 底层实现原理

AI 总结

深入剖析 AI 编程助手中 Code Graph（代码图谱）的底层实现原理，涵盖 AST 解析、符号索引、调用图构建、SCIP/LSIF 协议、向量嵌入检索，以及代码图谱如何被整合进 LLM 的上下文窗口中提供精准代码感知能力。

ai·# ai# llm# compiler

Code Graph是对一个代码仓库的结构化表示，它将代码中的各种实体（函数、类、变量、模块）及其关系（调用、继承、引用、导入）建模为一张有向图：

┌──────────────────────────────────────────────┐
│                  Code Graph                  │
│                                              │
│  [Module A] ──import──> [Module B]           │
│      │                      │                │
│   [Class X] ──extends──> [Class Y]           │
│      │                      │                │
│  [method foo()] ──call──> [method bar()]     │
│      │                                       │
│  [variable z] ──ref──> [type interface Z]    │
└──────────────────────────────────────────────┘

与纯文本的向量检索（把代码当作字符串做 embedding）不同，Code Graph 保留了代码的语义结构，能精确回答"谁调用了谁""这个类型在哪里定义"等结构性问题。

AST 解析

构建 Code Graph 的第一步是将源代码解析为抽象语法树（AST，Abstract Syntax Tree）。

目前主流工具是 tree-sitter，它是一个增量解析库，支持 40+ 种编程语言，能在毫秒级完成文件级别的解析，且支持增量更新——只重解析变更的部分。

以下面这段 TypeScript 为例：

import { add } from './math'
 
function double(x: number): number {
  return add(x, x)
}

tree-sitter 解析后产生 AST 结构：

program
├── import_statement
│   ├── import_clause: { add }
│   └── source: './math'
└── function_declaration
    ├── name: double
    ├── parameters: (x: number)
    ├── return_type: number
    └── return_statement
        └── call_expression
            ├── function: add
            └── arguments: (x, x)

从 AST 中可以提取：符号定义（double 函数在当前文件第 3 行定义）、符号引用（add 在第 4 行被调用，来自 ./math 模块）、类型信息（参数 x 的类型是 number）。

符号索引

从 AST 提取的信息需要被组织成可快速查询的符号索引（Symbol Index）。符号索引本质上是一张哈希表，key 是符号的唯一标识符，value 包含其位置、类型、所属作用域等元数据：

interface SymbolEntry {
  id: string            // 唯一 ID，如 "file:src/math.ts#add"
  name: string          // 符号名
  kind: SymbolKind      // Function | Class | Variable | Interface ...
  location: {
    file: string
    line: number
    column: number
  }
  type?: string         // 类型注解
  scope: string         // 所在作用域
}

对于大型仓库，符号索引会被持久化到本地磁盘，并在文件变更时做增量更新，而不是每次都全量重建。

调用图与依赖图

有了符号索引，就可以构建两张关键的图：

调用图（Call Graph）

调用图记录函数之间的调用关系，是一张有向图：

foo() ──calls──> bar()
foo() ──calls──> baz()
bar() ──calls──> qux()

构建调用图需要解析每个函数体中的 call_expression 节点，并将其解析（resolve）到具体的符号定义。这一步需要处理同文件调用（直接在当前文件的符号表中查找）、跨文件调用（通过 import 语句解析模块路径再到对应文件中查找）和动态调用（如 obj[method]() 无法静态解析，通常标记为 unresolved）。

依赖图（Import/Module Graph）

依赖图记录模块之间的 import 关系，用于确定文件的加载顺序和影响范围。当一个文件发生变更时，依赖图可以快速计算出受影响的上游文件集合，只重新索引这些文件，而不是整个仓库。

SCIP 协议

手动从 AST 构建图谱的方式对每种语言都要单独实现。为了标准化这个过程，Sourcegraph 提出了 SCIP（Source Code Intelligence Protocol），作为 LSIF 的继任者。

SCIP 定义了一套与语言无关的 protobuf 格式，用于描述代码中的符号、引用和实现关系：

message Index {
  repeated Document documents = 1;
  repeated SymbolInformation external_symbols = 2;
}
 
message Document {
  string relative_path = 1;
  repeated Occurrence occurrences = 2;
  repeated SymbolInformation symbols = 3;
}
 
message Occurrence {
  repeated int32 range = 1;    // [startLine, startCol, endLine, endCol]
  string symbol = 2;           // 符号唯一 ID
  int32 symbol_roles = 3;      // Definition | Reference | ...
}

语言服务（如 TypeScript Language Server、rust-analyzer）可以直接输出 SCIP 格式的索引文件，AI 工具消费这个文件即可，无需再自己解析 AST。

向量嵌入与混合检索

纯符号图谱擅长处理结构性问题（"谁调用了 X"），但对于语义性问题（"找一个处理用户认证的函数"），需要引入向量嵌入（Vector Embedding）。

主流的做法是混合检索（Hybrid Retrieval）：

用户问题
    │
    ├── 关键字解析 ──> 符号图谱查询 ──> 精确符号匹配
    │
    └── 语义嵌入 ──> 向量数据库检索 ──> 语义相似片段
                                              │
                                    两路结果合并 + 重排序
                                              │
                                    注入 LLM Context

代码嵌入通常以代码块为单位（函数、类、方法），而不是以文件为单位，这样可以精确检索到最相关的代码段而不引入大量噪音。常见的代码嵌入模型有 voyage-code-3（Anthropic）、text-embedding-3-large（OpenAI）、codebert-base（Microsoft，开源）。

图谱查询与上下文组装

当用户发起一个请求时，AI 工具会执行一次图谱查询，收集与请求相关的代码片段，再将这些片段组装成 LLM 的上下文。

以"重构 UserService.login 方法"为例：

// 1. 定位目标符号
const target = symbolIndex.find('UserService.login')
 
// 2. 查找直接调用者（一跳）
const callers = callGraph.getCallers(target.id)
 
// 3. 查找目标函数内部调用的函数
const callees = callGraph.getCallees(target.id)
 
// 4. 查找相关类型定义
const types = typeIndex.getRelatedTypes(target.id)
 
// 5. 组装上下文
const context = [
  target.source,
  ...callers.map(c => c.source),
  ...callees.map(c => c.source),
  ...types.map(t => t.source),
]

这个过程通常使用 BFS 图遍历（广度优先搜索），从目标节点出发，按跳数向外扩展，直到收集足够的上下文或达到 token 预算上限。

最终组装成的 context 被注入 LLM 的 System Prompt 或 User Message 中：

<code_context>
// File: src/services/UserService.ts (lines 42-68)
async login(email: string, password: string) {
  ...
}
 
// Callers:
// File: src/controllers/AuthController.ts (line 15)
const result = await userService.login(req.body.email, req.body.password)
 
// Callees:
// File: src/utils/hash.ts (lines 3-8)
export function compareHash(plain: string, hashed: string): boolean {
  ...
}
</code_context>

增量更新策略

对于一个有数千个文件的仓库，全量重建 Code Graph 每次都要花费数分钟，这在实际使用中是不可接受的。因此增量更新是工程实现的关键。

通常的策略是：通过 fs.watch 或 chokidar 监听文件系统事件 → 文件变更时通过依赖图向上传播脏标记 → 只对有脏标记的文件重新解析 AST 和更新符号索引 → 删除旧的调用图边，插入新的调用图边。

fileWatcher.on('change', async (changedFile) => {
  const affected = importGraph.getAffected(changedFile)
 
  for (const file of affected) {
    const ast = await parser.parse(file)
    symbolIndex.update(file, extractSymbols(ast))
    callGraph.update(file, extractCalls(ast))
  }
})

总结

Code Graph 的完整构建流程：

源代码文件
    │
    ▼
tree-sitter AST 解析
    │
    ▼
符号提取 → 符号索引（哈希表）
    │
    ├──> 调用图（Call Graph）
    └──> 依赖图（Import Graph）
              │
              ▼
         向量嵌入（代码块级别）
              │
              ▼
    混合检索（符号图 + 向量库）
              │
              ▼
       BFS 图遍历 + Token 预算裁剪
              │
              ▼
        注入 LLM Context Window

Code Graph 本质上是将编译器前端的技术（词法分析、语法分析、符号解析）与信息检索技术（倒排索引、向量嵌入）结合，再对接到 LLM 的上下文注入管道。它让 AI 从"读文本"升级为"理解代码结构"，是现代 AI 编程助手具备跨文件感知能力的核心基础设施。

点击播放