符号索引

背景

语言服务器的许多功能需要跨文件工作。用户在一个文件中触发"跳转到定义"，目标可能在项目的任意另一个文件里；"查找引用"需要扫描整个项目中所有可能提及该符号的文件；调用层次和类型层次更是涉及多个文件之间的符号关系链。要实现这些功能，语言服务器必须维护一份覆盖整个项目的符号索引，记录每个符号在哪些文件中出现、它们之间的语义关系（定义、引用、调用、继承等）。

C++ 让索引的构建和维护变得特别困难。

第一个层面是头文件的编译上下文问题。C++ 的 #include 是文本替换——头文件的内容在编译时被逐字插入到包含它的源文件中。这意味着同一个头文件在不同的编译上下文下可以产生完全不同的符号：

cpp

// crypto.h
#ifdef USE_OPENSSL
    using TLSContext = OpenSSLContext;
#else
    using TLSContext = BoringSSLContext;
#endif

当 crypto.h 被一个定义了 USE_OPENSSL 的源文件包含时，TLSContext 是 OpenSSLContext；被另一个源文件包含时，它是 BoringSSLContext。条件编译是最直观的例子，但 include 顺序和模板实例化也会导致头文件在不同上下文下产生不同的符号关系。如果索引只记录一个上下文的结果，用户切换上下文后就会看到错误的跳转目标或不完整的引用列表。

第二个层面是规模。一个中等规模的 C++ 项目（数千个源文件）编译后产生数十万个符号，大型项目（LLVM、Chromium）达到百万量级。索引系统需要在这个规模下保持合理的内存占用、构建时间和查询延迟。

clangd 在这两个层面的处理都有不足。在编译上下文方面，clangd 的后台索引对每个头文件只保留最后一次编译的结果——后编译的源文件会覆盖先前的索引数据。如果一个符号的引用只在某个特定的编译上下文下存在，而该上下文不是最后被索引的，这条引用就丢失了。

在跨文件查找方面，clangd 的后台索引将符号信息存储在符号声明所在文件对应的索引分片中。这种以声明文件为中心的存储方式导致引用计数无法正确跨文件累加（clangd #23）。用户也经常遇到"查找引用"结果不完整的情况——某些引用直到手动打开对应文件后才出现，因为动态索引此时才补上了缺失的数据（clangd #516、#802）。此外，编译命令发生变化时，clangd 的过期检测不会触发重新索引（clangd #199），导致索引数据与实际编译状态长期不一致。

clice 的索引系统针对这些问题做了重新设计：采用三级索引结构将全局符号目录与按文件分片的关系数据分离，通过内容寻址去重来合并不同编译上下文的索引结果，用 FlatBuffers 实现按需惰性加载来控制内存占用，并用打开文件的实时覆盖层保证编辑过程中查询结果的时效性。

设计

符号标识

索引系统需要一种跨文件、跨编译单元的方式来标识同一个符号。clice 使用 SymbolHash（一个 64 位整数）作为符号的唯一标识。

SymbolHash 基于 Clang 的 USR（Unified Symbol Resolution）生成。USR 是符号身份的规范字符串表示，编码了符号的完全限定名：命名空间、类名、函数签名、模板参数等信息。例如 std::vector<int>::push_back 和 std::vector<double>::push_back 产生不同的 USR。SymbolHash 是对 USR 字符串计算的哈希值。

SymbolHash 有两个关键特性。第一，跨文件一致：同一个符号无论在哪个文件中出现，SymbolHash 始终相同。文件 A 中的 std::string 和文件 B 中的 std::string 拥有相同的哈希值，通过它可以关联所有的定义和引用——这是跨文件导航的基础。第二，紧凑高效：64 位整数比可变长度的 USR 字符串更适合作为哈希表的键和序列化存储。

符号出现与符号关系

索引存储两种核心数据：符号出现（Occurrence）和符号关系（Relation）。

Occurrence 记录一个符号在源码中的出现位置，只包含源码范围和目标符号的 SymbolHash。它回答的问题是"光标位置下是什么符号"。

Relation 记录更丰富的语义信息，包含三个要素：关系类型（RelationKind）、源码位置、以及目标符号。关系类型涵盖了常见的符号间语义：

定义与声明（Definition、Declaration）
引用（Reference、WeakReference）
继承（Base、Derived）
调用（Caller、Callee）
类型关系（Interface、Implementation、TypeDefinition）
构造与析构（Constructor、Destructor）

两者分开存储是因为查询模式不同。Occurrence 按位置索引——给定一个字节偏移量，用二分查找快速定位光标下的符号。Relation 按 SymbolHash 索引——给定一个符号，查找它的所有定义、引用、调用关系。这两种查询对数据排序的要求相互矛盾，分开存储使两种查询都能高效执行。

三级索引层次

clice 的索引分为三个层次，每层有不同的生命周期和职责：

TUIndex        一次编译的原始产物，合并后丢弃
    ↓ 合并
ProjectIndex   全局符号目录（符号出现在哪些文件中），常驻内存
MergedIndex    按文件分片的关系数据（符号在文件中的具体位置和关系），按需加载
    ↑ 叠加
FileIndex      打开文件的实时覆盖层（来自内存中的 AST）

TUIndex 是编译一个翻译单元时产生的原始索引数据。SemanticVisitor 遍历 AST，对每个符号出现和关系生成记录，按文件分组组装成 TUIndex。由于一次编译涉及主文件和所有被 include 的头文件，TUIndex 内部为每个涉及的文件各维护一份独立的 FileIndex。TUIndex 还包含一份 SymbolTable（符号哈希到名称和种类的映射）和 IncludeGraph（这次编译中的 include 关系）。TUIndex 是临时数据，合并到持久索引后即被丢弃。

ProjectIndex 是全局的符号目录。它汇聚所有已索引翻译单元的符号信息，维护一张全局符号表：SymbolHash → 符号名称、符号种类、引用文件位图。其中引用文件位图记录了该符号出现在哪些文件中，使用 Roaring Bitmap 压缩存储。

ProjectIndex 不存储符号的具体位置（偏移量、行号）。它的角色是"目录"——告诉你一个符号存在于哪些文件中，然后你去对应文件的 MergedIndex 分片中查找具体位置。这种分离使 ProjectIndex 保持紧凑，可以常驻内存。

MergedIndex 是按文件分片的索引存储层。项目中的每个文件对应一个 MergedIndex 分片，存储该文件中所有符号的出现位置和关系信息。这是索引系统中体积最大的部分，也是实际承载查询的层。它支持从磁盘惰性加载——未被查询的分片不会加载到内存中。

MergedIndex 的核心能力是将同一个文件在不同编译上下文下产生的索引数据合并去重存储，具体机制在实现部分详述。

FileIndex（打开文件的覆盖层）存在于每个打开文件的 Session 中，来自最近一次内存编译的结果。它和 MergedIndex 分片存储相同类型的数据（Occurrence 和 Relation），但不写入全局状态——只在查询时作为叠加层使用，用当前编辑缓冲区的编译结果覆盖磁盘索引的数据。

符号表

SymbolTable 将 SymbolHash 映射到符号的元信息——名称和种类（Class、Function、Variable 等）。它出现在两个位置：ProjectIndex 中的全局符号表和 Session 中的局部符号表。查询符号名称时先查 Session（内容更新），找不到再查 ProjectIndex。

IncludeGraph

IncludeGraph 记录一次编译中所有文件的 include 关系。它包含两部分：路径列表（该编译涉及的所有文件路径）和 IncludeLocation 记录（每条记录表示一个文件在某一行被 include，以及 include 的来源文件）。

IncludeGraph 有两个用途。在 TUIndex 合并时，它提供编译单元内部的文件 ID 到项目全局路径 ID 的映射。在 MergedIndex 中，它作为编译上下文的一部分被存储，include 链用于过期检测。

实现

索引构建

TUIndex 的构建由 SemanticVisitor 完成：给定一个编译单元，遍历 AST，为每个命名声明和宏生成 Occurrence 和 Relation 记录。遍历完成后，对每个文件的数据进行去重和排序——Occurrence 按位置排序以支持二分查找，Relation 按类型和位置排序以支持过滤。

构建过程中，主文件（源文件）的 FileIndex 被单独提取出来。这使得合并阶段可以区分处理——主文件作为源文件上下文合并，其余文件作为头文件上下文合并。

索引合并

TUIndex 合并到持久索引分两步进行。

第一步，将符号信息合并到 ProjectIndex。TUIndex 中的所有符号插入全局符号表，同时更新每个符号的引用文件位图——将本次编译涉及的文件加入位图。这一步同时完成路径映射：TUIndex 内部使用的路径 ID 转换为 ProjectIndex 的全局路径 ID。

第二步，将各文件的 FileIndex 合并到对应的 MergedIndex 分片。对于主文件，附带编译上下文信息（编译时间戳、include 链）；对于头文件，附带头文件上下文信息（include 位置标识）。

编译上下文去重

MergedIndex 面对的核心问题是：同一个头文件被 N 个源文件包含，会产生 N 份 FileIndex。如果每份都完整存储，空间会随编译单元数量线性增长。但实际上，绝大多数头文件在不同编译上下文下产生的索引是完全一样的——相同的符号出现在相同的位置，产生相同的关系。只有像上面 crypto.h 那样受条件编译影响的头文件，才会在不同上下文下产生不同的索引内容。

MergedIndex 用内容寻址去重来解决这个问题。每份 FileIndex 在合并前计算 SHA-256 内容哈希。哈希相同的 FileIndex 内容一定相同，它们共享同一个 canonical ID（一个自增的整数标识）。

具体来说，MergedIndex 中的 Occurrence 和 Relation 不是简单的列表，而是每条记录关联一个 Roaring Bitmap，标记该记录属于哪些 canonical ID。合并一份新的 FileIndex 时：

计算其 SHA-256 哈希
查缓存：如果这个哈希已存在，说明数据完全相同，直接复用对应的 canonical ID，递增引用计数
如果是新哈希，分配新的 canonical ID，将所有 Occurrence 和 Relation 记录插入，并关联到这个新 ID

当编译上下文被移除时（例如源文件从项目中删除），对应 canonical ID 的引用计数递减。引用计数归零的 canonical ID 被标记进"已移除"集合。查询时，属于已移除集合的数据会被过滤掉。

这种设计使得存储量取决于索引内容的种类数而非编译上下文的数量。对于大多数头文件，无论被多少源文件包含，只存储一份数据。

编译上下文类型

MergedIndex 内部区分两类编译上下文：

CompilationContext：文件作为源文件被直接编译时产生。记录编译时间戳和 include 链（用于过期检测），以及对应的 canonical ID。一个文件可以有多个 CompilationContext，对应编译数据库中不同的编译命令。
HeaderContext：文件作为头文件被其他源文件包含时产生。记录包含它的源文件和 include 位置，以及对应的 canonical ID。

这两类上下文配合编译上下文系统工作。查询时不需要区分上下文类型——所有上下文的数据已经通过 canonical ID 的 Bitmap 统一管理。过期检测时，CompilationContext 的 include 链用于判断是否需要重新索引。

惰性加载

MergedIndex 使用 FlatBuffers 序列化。FlatBuffers 的设计允许直接在序列化数据上执行查询，无需反序列化到内存结构。MergedIndex 利用这一特性实现两层访问模式：

只读路径：从磁盘加载后，MergedIndex 保持为原始的内存映射缓冲区，查询操作直接在 FlatBuffers 数据上执行，没有反序列化开销。
读写路径：需要修改时（合并新数据或移除旧上下文），先将 FlatBuffers 数据反序列化到内存结构，后续操作在内存结构上进行。修改后的分片保存时重新序列化。

启动时只需加载 ProjectIndex（体积较小），MergedIndex 分片按需加载，且大多数分片在一次会话中不会被访问。

查询流程

以"查找引用"为例，说明跨文件查询的完整流程：

在当前文件中，用光标的字节偏移量在 Occurrence 列表中二分查找，得到光标下符号的 SymbolHash
在 ProjectIndex 中查找该 SymbolHash 的引用文件位图，得到所有包含该符号的文件列表
对列表中的每个文件分别查询：
- 如果该文件已打开（有活跃的 Session），使用 Session 的 FileIndex，跳过对应的 MergedIndex 分片
- 如果该文件未打开，加载对应的 MergedIndex 分片并在其中查找
汇总所有文件中找到的 Relation（按目标 RelationKind 过滤），转换为 LSP 位置返回给客户端

第 3 步中，打开文件优先使用 Session 的 FileIndex 而非 MergedIndex，因为缓冲区内容可能与磁盘不一致。Session 的 FileIndex 来自内存中的编译结果，更准确地反映用户当前看到的代码。当 Session 的 AST 处于脏状态（用户编辑后尚未重新编译）时，才回退到 MergedIndex。

偏移量到 LSP 位置的转换需要文件内容和行首偏移表。MergedIndex 分片中存储了对应文件的内容和行首偏移表，因此即使文件未打开也能完成转换。

过期检测

过期检测决定一个文件是否需要重新索引。MergedIndex 分片中存储了编译时间戳和 include 链。检测时，遍历 include 链中每个文件的最后修改时间（mtime），如果任何一个文件的 mtime 晚于编译时间戳，说明依赖已更新，需要重新索引。

这种检测是保守的——mtime 变化不一定意味着内容变化（例如 touch 操作、分支切换）。但误判只会导致多执行一次索引，不会遗漏需要更新的文件。

后台索引调度

后台索引的调度需要平衡索引的及时性和对用户交互的干扰。索引模块采用以下策略：

队列与空闲延迟：需要索引的文件加入队列，在编辑器空闲一段时间后才开始处理。这避免了用户快速编辑时频繁触发索引任务。
并发控制与内存监控：同时运行的索引任务数有上限。索引过程中动态监控系统内存占用——内存紧张时自动降低并发数，内存恢复后逐步提升回基线值。
优先级管理：用户主动触发的操作（如编译打开的文件）会暂停后台索引。操作完成后恢复，确保用户请求的响应延迟不受后台索引影响。
结果合并与持久化：每个索引任务在无状态子进程中编译文件并构建 TUIndex，结果序列化后传回主进程，由主进程合并到 ProjectIndex 和 MergedIndex 中。索引完成后，修改过的分片被写回磁盘，下次启动时可以直接加载。

FAQ

为什么将 ProjectIndex 和 MergedIndex 分开，而不是用一个统一的索引？
如果将位置信息也存入 ProjectIndex，它的体积会急剧膨胀，无法常驻内存。而如果没有 ProjectIndex，每次跨文件查询都需要遍历所有 MergedIndex 分片来定位符号所在的文件——在一个上万文件的项目中，加载上万个分片是不可接受的。ProjectIndex 作为轻量的目录层，先缩小搜索范围到具体的几个文件，再到对应分片中精确查找。
为什么打开文件的索引不写入全局状态？
用户正在编辑的缓冲区内容可能是不完整的、有语法错误的代码。如果将这些临时状态写入全局索引，会污染其他文件的查询结果。例如，一个正在编辑的头文件中某个符号的定义临时消失，会导致所有引用该符号的文件的查找引用结果受到影响。全局索引只接受保存到磁盘的稳定状态，通过后台索引从磁盘文件构建。
内容寻址去重是否有哈希冲突的风险？
理论上 SHA-256 存在冲突可能，但概率可以忽略（2^-128 量级）。实践中将 SHA-256 冲突视为"不会发生"是标准做法。即使发生冲突，后果也只是两份不同的 FileIndex 共享了数据，不会导致崩溃或数据损坏。
为什么使用 FlatBuffers 而不是 Protocol Buffers 或自定义格式？
FlatBuffers 允许直接在序列化数据上查询，不需要反序列化。对于 MergedIndex 这样可能有数千个分片的数据，大多数分片在一次会话中不会被访问。FlatBuffers 的零拷贝特性使得加载一个分片的开销接近于零——只需要内存映射文件，实际访问的数据才被读入内存。Protocol Buffers 需要完整的反序列化步骤，不适合这种按需加载模式。
为什么 Occurrence 和 Relation 要分开存储？
Occurrence 按位置索引——给定偏移量，二分查找定位光标下的符号，需要按位置排序。Relation 按 SymbolHash 索引——给定符号，查找它的所有关系，需要按符号分组。如果合并为一种数据结构，无法同时满足两种排序需求，必然在其中一种查询上损失效率。
为什么跨文件查询在主进程而非子进程中完成？
clice 采用多进程架构，打开的文件各自在有状态子进程中编译。跨文件查询（如查找引用）需要遍历所有打开文件的 Session，汇总它们的 FileIndex 结果。如果这些 Session 分散在不同的子进程中，每次查询都需要跨多个进程通信再聚合结果，延迟和复杂度都不可接受。因此，子进程编译完成后会将 FileIndex 传回主进程，由主进程统一完成查询——既可以访问所有打开文件的 FileIndex，也可以直接访问 ProjectIndex 和 MergedIndex，在一个进程内完成完整的查询流程。
这个设计还有一个语义上的考虑：打开文件的查询结果应该反映编辑器中的缓冲区状态，而非磁盘状态。即使磁盘上的文件已被外部工具修改，只要编辑器没有发送 didChange，查询结果仍应基于编辑器持有的版本。将所有 FileIndex 集中在主进程中管理使得这一语义约束更容易维护。
为什么不用数据库存储索引？
clice 需要持久化多种缓存文件：索引分片、PCH、PCM 等。PCH 和 PCM 文件体积大（可达上百 MB）但数量少（大致与打开文件数或模块数成正比），生命周期也很简单——创建、读取、过期后删除，没有复杂的查询或事务需求。数据库擅长的能力（事务、索引、复杂查询）对这类文件没有意义，用文件系统管理足够了。
索引分片是唯一可能从数据库中获益的部分：数量多（等于项目文件数）、体积小，可能受益于原子写入和自动 LRU 淘汰。但目前基于文件系统的方案已经能满足这些需求。为了索引分片一个场景引入数据库依赖，增加的复杂度是否值得，需要等实际遇到瓶颈再评估。对于大型项目（数万个文件），同一目录下存放大量索引分片可能带来文件系统层面的压力，未来可以考虑分层存储或引入轻量数据库来缓解。

已知局限

符号表的局部性。目前所有符号（包括函数内的局部变量）都被合并到 ProjectIndex 的全局符号表中。这导致大量只在单个文件内部有意义的符号被全局存储，增加了合并时的哈希表插入开销和内存占用。
改进方向是引入多级符号表——不只 ProjectIndex 有 SymbolTable，MergedIndex 分片也应该有自己的 SymbolTable。判断一个符号属于哪一级的规则是：符号定义在哪个文件，就属于哪个文件的 SymbolTable，前提是该符号是内部的（不会被其他文件引用）。例如：
cpp
```
// utils.h
inline int helper(int x) {
    auto temp = x * 2;    // temp 是 utils.h 的局部符号
    return temp + 1;
}
```
cpp
```
// main.cpp
#include "utils.h"
static int counter = 0;    // counter 是 main.cpp 的局部符号

int main() {
    counter = helper(42);
}
```
temp 定义在 utils.h 中，不会被任何其他文件引用，它应该在 utils.h 对应的 MergedIndex 分片的 SymbolTable 中，而不是 ProjectIndex 的全局符号表中。counter 是 main.cpp 的静态变量，同理应该在 main.cpp 的 MergedIndex 分片中。注意 temp 虽然出现在头文件中，但它属于头文件的 SymbolTable 而非包含它的源文件的 SymbolTable，因为它定义在头文件中。只有 helper、main 这样可能被跨文件引用的符号才需要进入 ProjectIndex。
这样做的目的是最小化 ProjectIndex 的体积和合并开销，同时避免同一个局部符号因出现在多个编译单元中而被重复存储。
过期检测的精度。当前的过期检测只使用 mtime——只要依赖文件的 mtime 晚于编译时间戳就触发重新索引。这在 touch、分支切换、CI 还原等场景下会产生不必要的重新索引（文件 mtime 变了但内容没变）。改进方向是 mtime + 内容哈希双层检测：第一层用 mtime 快速判断，mtime 未变则跳过（零 I/O）；第二层对 mtime 变化的文件计算内容哈希，哈希不变说明内容未改，同样跳过。这种方案已在编译产物（PCH、AST）的过期检测中使用，索引的过期检测应当对齐。
模糊符号搜索。当前的全局符号搜索（workspace/symbol）是简单的子串匹配，对 ProjectIndex 中所有符号做线性扫描。在大型项目中效率不够，且不支持模糊匹配。
C++ 符号名有结构性：getSymbolHash 是 camelCase，get_symbol_hash 是 snake_case，std::vector<int>::push_back 带命名空间限定。用户搜索时通常只输入缩写或片段（如 symhash、gSH、vec_pb），期望匹配到完整符号名。子串匹配无法处理这类查询。
改进方向是为符号名建立专门的搜索索引。需要一个分词器将符号名按命名约定拆分为词元（getSymbolHash → [get, Symbol, Hash]，push_back → [push, back]），然后基于词元建立倒排索引。例如使用 trigram（三字符组）作为索引键，查询时取 trigram 交集得到候选集，再精确评分排序。clangd 的 Dex 索引采用了这种 trigram posting list 方案，是一个可参考的实现。另一个方向是引入成熟的全文搜索库，但需要评估引入外部依赖的代价。
~~PCH 导致的索引分裂~~（已解决）。使用 PCH 优化时，一个文件的编译被分成两个阶段：先把 preamble 编译成 PCH，再用 PCH 编译文件的其余部分。PCH 吞掉了 bound 之前的一切——主文件的编译既看不到头文件的内容，也看不到 preamble 区自身的指令；而且打开缓冲区的 preamble 可能描述一个任何磁盘翻译单元都未曾以之索引过的编译上下文。
现在的方案是为每个 PCH 配对一个 preamble 状态 blob，由同一次 worker 构建在刚解析完的 preamble AST 仍在内存时产出（这是唯一无需完整反序列化 PCH 就能获得其索引的时机）。blob 携带 preamble 的完整符号索引——覆盖的每个头文件加上主文件的 preamble 区——以及每文件的内容与行表（用于位置换算）、document links、非活跃区域和未闭合条件栈。它与 PCH 一同存储、一同命中、一同淘汰，以内存映射 FlatBuffer 形式打开，查询无需反序列化。打开文件把这些 blob 作为 overlay 叠加到索引查询上：集合查询与磁盘分片取并集（相同行按位置坍缩），单答案查询优先 overlay，缓冲区 preamble 区的游标经 blob 的主文件条目解析。这使得后台索引尚未（或无法）覆盖其翻译单元的打开文件仍能正常导航，查询结果也忠实于未保存的 preamble 编辑。

符号索引 ​

背景 ​

设计 ​

符号标识 ​

符号出现与符号关系 ​

三级索引层次 ​

符号表 ​

IncludeGraph ​

实现 ​

索引构建 ​

索引合并 ​

编译上下文去重 ​

编译上下文类型 ​

惰性加载 ​

查询流程 ​

过期检测 ​

后台索引调度 ​

FAQ ​

已知局限 ​