符号索引

背景

语言服务器的许多功能都需要跨文件工作。用户在一个文件中触发“跳转到定义”时，目标可能位于项目中的其他任意文件；“查找引用”需要扫描项目中所有可能提及该符号的文件；调用层次结构和类型层次结构则涉及跨多个文件的符号关系链。为了支持这些功能，语言服务器必须维护项目级的符号索引，记录每个符号出现在哪些文件中，以及符号之间的语义关系（定义、引用、调用、继承等）。

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

第一层困难来自头文件的编译上下文。C++ 的 #include 是文本替换——编译时，头文件的内容会被原样插入包含它的源文件中。这意味着同一个头文件在不同的编译上下文中可能产生完全不同的符号：

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

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

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

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

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

clice 重新设计了索引系统以解决这些问题：将全局符号目录与按文件分片的关系数据分离；通过对内容相同的变体去重，合并同一文件的不同编译上下文；将所有索引数据块存储在单个嵌入式数据库中，并支持零拷贝按需访问；为打开的文件叠加实时数据，确保编辑期间查询结果始终为最新状态。

设计

符号标识

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

SymbolHash 是符号实体（entity）的哈希值：实体是一份声明的描述，只由所有重声明共有的属性构成，因此在每个翻译单元、每个进程中都得到相同的结果。实体包含声明的上下文链（命名空间、外层的类和函数，其中类模板特化还带上自己的模板实参）、声明自身的名字，以及在语言允许同名共存时用来区分它们的信息：函数的参数类型和限定符、模板头及其约束、特化的模板实参。类型以规范形式进入哈希，因此 typedef 与它所命名的类型哈希相同。约束表达式和其他依赖表达式通过移植 Clang 自身的规范表达式 profile 进入哈希——Sema 正是用它判断两个模板是否相同——其中所有指针值的叶子节点都替换为稳定的值。具有内部链接的声明（static 函数和变量、匿名命名空间的成员）还会带上首次声明它的文件路径，匿名类型以及系统头文件之外的 typedef 名字也一样：头文件中的 static 辅助函数，在每个包含该头文件的翻译单元里都是同一个符号；两个源文件中同名的两个辅助函数，则是两个不同的符号。宏的实体是它的名字加上 #define 所在的位置；具名模块（named module）的实体则是它的完整名字。

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

符号出现与符号关系

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

Occurrence 记录符号在某个源码位置的出现，只包含源码范围和目标符号的 SymbolHash。它用于回答“光标处是什么符号”这一问题。

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

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

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

索引层次结构

clice 的索引采用分层组织，每层都有不同的生命周期和职责：

TUIndex        Raw artifact from one compilation, discarded after merging
    ↓ merge
ProjectIndex   Global directory: external symbols + which TUs contributed which files
Shard          Per-file variant storage (exact positions and relations), loaded on demand
    ↑ overlay
Live rows      The open buffer's latest compile results, owned by its published projection

TUIndex 是编译翻译单元时产生的原始索引数据，由编译期间构建的统一语义映射投影生成。由于一次编译涉及主文件及其包含的所有头文件，TUIndex 内部会为每个文件维护独立的行集。它还包含一份符号表以及本次编译的包含树：每进入一个文件就有一个节点，记录该文件、包含它的节点以及包含指令所在的行。TUIndex 是临时数据，合并到持久化索引后即被丢弃。

ProjectIndex 是全局目录。它有两个职责：为外部可见符号维护全局符号表，以及记录各翻译单元贡献了哪些文件（这是判断变体存活状态，以及翻译单元消失时重新核对数据的依据）。符号表的每一行记录的是符号“是什么”，而不是“在哪里”：符号自身的名字（bar，而绝不是 Foo::bar）、其父级的实体——外层的命名空间、类、枚举或函数，限定名就由此拼出——特化的模板实参、种类、一组标志（是否有某个翻译单元定义了它、是否为模板或特化、是否已弃用、是否为内联命名空间、是否匿名、名字是否由宏拼出、是否在系统头文件中声明、是否会出现在非限定补全中，以及名字的形式）、其规范声明所在的文件，以及引用文件位图，以 Roaring Bitmap 压缩。标志取所有见过该符号的翻译单元的并集。这些行不含任何位置——符号表只指明符号存在于哪些文件中，具体位置则保存在相应的分片中。这种分离使 ProjectIndex 足够紧凑，可以始终驻留在内存中。

Shard 是按文件划分的存储单元，也是实际提供查询服务的层。每个以不同方式预处理该文件的编译上下文都会贡献一个变体——由该文件的行数据按规范编码而成的自包含数据块。仅限于文件内的名称（具有内部链接的名称、函数内的局部名称、匿名命名空间成员）存放在分片自身的本地名称表中；只有外部名称会进入 ProjectIndex。分片按需加载——会话期间，大多数分片从不会被访问。

打开文件的**实时行（Live rows）**来自其最近一次内存编译，由文档已发布的投影持有。它们绝不会写入全局状态——只在查询时作为叠加层，使结果反映用户实际编辑的缓冲区内容。

符号表分层

符号元数据（名称、种类）按层次查找：先查打开文件的实时数据，再查 ProjectIndex 中用于外部名称的全局表，最后查分片中用于文件局部名称的本地名称表。存储位置取决于可见性——其他文件无法引用的符号绝不会进入全局表。

实现

索引构建

TUIndex 的构建是对统一语义映射的投影：每次编译执行一次 AST 遍历，记录所有需要关注的节点，再由索引投影按文件生成 Occurrence 和 Relation 记录。投影完成后，会对每个文件的记录进行规范化处理——去重并排序（出现记录按位置排序，以便进行二分查找；关系记录按类别和位置排序，以便过滤）——从而保证编码后的数据块具有确定性。

构建期间，主文件的记录与头文件的记录分开保存。这样可以在合并时区别处理——主文件作为翻译单元自身的贡献合并，头文件则作为上下文变体合并。

基于内容标识的变体去重

分片面临的核心问题是：同一个头文件被 N 个源文件包含，会产生 N 组记录。如果每组记录都完整存储，存储量将随翻译单元数量线性增长。但实际上，绝大多数头文件在不同编译上下文中产生的索引数据完全相同。只有上文 crypto.h 这类受条件编译影响的头文件，才会在不同上下文中产生不同内容。

clice 的解决办法是让编码后的字节本身成为标识。每个变体都以规范且确定的方式编码——相同的记录会产生相同的字节——其标识（RowsHash）就是这些字节的 xxh3 哈希。新的编译结果贡献变体时：

1. 将该文件的记录编码为规范数据块，并计算其哈希
2. 如果分片中已经存在具有该标识的变体，合并就只是更新记录——记下贡献该变体的 TU，无需解码或重写任何内容
3. 如果该标识是新的，则将该数据块添加为新变体

实践中，绝大多数合并都只需更新记录，这正是全项目索引开销很低的原因：重新索引未发生变化的头文件时，完全不需要触及分片中的任何字节。

哪些变体有效，由根据贡献记录生成的变体掩码决定：当翻译单元被移除或重新索引时，它不再认可的变体会退出有效集合，并从查询结果中过滤掉。

零拷贝存储

所有索引数据块——分片、清单和序列化的 ProjectIndex——都存储在同一个嵌入式 LMDB 数据库中。数据块采用规范的自描述编码；加载时只需验证一次，之后便可直接用作内存映射的零拷贝视图。读取路径中不存在先反序列化为结构体的步骤。

像 clice query 这样的读取方打开索引时，会从数据库的读快照中原地绑定全局表和搜索索引，某个分片要等到第一次有查询触及它时才取出来；整个过程不解码，也不复制任何一行。写入方则把自己的改动保存为同一份视图之上的内存增量——只有合并真正触及的行才会被复制——并在写出下一个数据块时将其并入；写入方还要负责协调清单与分片，因此会在启动时加载全部清单并校验每个分片。

每个 TU 的上下文

上下文信息——翻译单元看到了哪些文件，以及这些文件位于哪棵包含树中——按翻译单元存储在其清单中，而不会重复存入每个分片。清单中的包含树就是 envelope（一个翻译单元编码后的索引数据）里的那棵，只是每个节点的文件 id 从本次编译的路径表重新映射到了工作区的文件版本。分片只记录变体；清单则记录哪个 TU 为哪个文件贡献了哪个变体。是否过期以及如何协调状态（TU 从 CDB 中消失、命令发生变化、依赖发生变化），由清单和贡献记录决定。

查询流程

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

1. 在当前文件中，使用光标的字节偏移量对 Occurrence 记录进行二分查找，取得光标所在符号的 SymbolHash
2. 在 ProjectIndex 中查找该 SymbolHash 的引用文件位图，得到所有包含该符号的文件
3. 查询列表中的每个文件：
   • 如果文件已打开，则使用其有效记录（来自最近一次内存编译），前提是这些记录与缓冲区的当前内容一致
   • 对于打开的文件，只有当缓冲区内容与分片索引的内容逐字节一致时，才会查询磁盘数据——只要缓冲区经过编辑，就绝不会返回过期的磁盘位置
   • 未打开的文件使用其分片中的有效变体回答查询
4. 汇总在各文件中找到的所有 Relation 记录（按目标 RelationKind 过滤），将其转换为 LSP 位置并返回给客户端

对于 Preamble 被编译进 PCH 的打开文件，配套的 Preamble 状态数据块（见下文）会提供被 PCH 吸收的那些记录。

将偏移量转换为 LSP 位置，需要知道文件中各行的起始位置。索引分片会存储行表（以及转换所需的文件内容），因此即使文件未打开，也能进行这种转换。

名称搜索

按名称搜索符号（workspace/symbol，以及 clice query 的名称查询）走的是一份搜索索引：它由全局符号表派生而来，并与符号表一同持久化。索引的每一行是一个可搜索的符号，按质量排序——质量分来自引用该符号的文件数量、符号的种类以及它的标志（已弃用、名字由宏拼出、位于系统头文件、只有声明）——索引中的所有位图都以这一行序为准：每个名称 Token 一个倒排列表，此外还有每个容器的成员、每个命名空间之下的子树、每个种类的行和每个文件的行。

Token 是模糊匹配在名称中可能走过的一条路径的 trigram，路径依照标识符到单词的拆分（getSymbolHash 拆成 get、Symbol、Hash）：从某个字符出发，匹配要么接着走同一个单词的下一个字符，要么跳到后面某个单词的词首，因此 gsh 和 symhash 都能走到 getSymbolHash。于是查询的 trigram 通过对倒排列表求交——再加上种类、文件和作用域位图——选出匹配器可能接受的全部候选，匹配器只为这些候选评分。各行本就按质量排序，且任何部分匹配都不会盖过完全匹配，因此一旦剩余的行已经进不了结果集，扫描即可停止。只有一两个字母的查询，只用名称的前两个单词建键。

索引由符号表在线程池上重建，时机有三个：自上次构建以来合并进来的符号多到超过索引本身、合并到一定数量后索引活动平息下来，以及退出时；这期间合并进来的符号直接扫描，打开文档自身的符号也是如此。打开持久化索引的读取方（clice query）把数据块映射进内存后即可作答。

过期检测

过期检测用于判断文件是否需要重新索引。每个索引产物都会记录其输入的标识以及观测到的内容版本；校验由主进程的共享文件表完成，它采用与其他各处相同的两层检查：先走 (size, mtime) stat 快速路径，再通过内容哈希确认，并修正状态标记（stamp）（见增量编译）。仅当输入内容确实发生变化时，才会触发重新索引；命令变更则通过清单中记录的条目标识哈希单独检测。

后台索引调度

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

• 带空闲延迟的队列：需要索引的文件先加入队列，只有编辑器空闲了一段可配置的时间后才开始处理。这样可以避免在用户快速编辑时触发索引任务。
• 前台感知配额：用户操作活跃时，后台索引任务只能使用 worker 池的一部分容量；前台任务空闲时，则可使用全部容量。内存压力还会进一步降低这一配额（见多进程架构）。
• 结果合并与持久化：每个索引任务都会在无状态子进程中编译一个文件并构建 TUIndex。结果经序列化后发回主进程，由主进程将其合并到项目索引和索引分片中。有变动的 blob 通过批量事务提交到数据库，以便下次启动时直接加载。

常见问题

• 为什么将 ProjectIndex 与索引分片分开，而不是使用单一的统一索引？

  如果位置信息也存入 ProjectIndex，它的体积会急剧膨胀，无法常驻内存。如果没有 ProjectIndex，每次跨文件查询都必须遍历所有索引分片，找出包含该符号的文件——对于拥有数万个文件的项目，加载如此多的索引分片是不可接受的。ProjectIndex 充当轻量级目录层，先将搜索范围缩小到少量特定文件，再在相应的索引分片中进行精确查找。

• 为什么已打开文件的索引不写入全局状态？

  用户正在编辑的缓冲区内容可能是带有语法错误的不完整代码。如果将这种临时状态写入全局索引，就会污染其他文件的查询结果。例如，正在编辑的头文件中某个符号定义暂时消失，会影响所有引用该符号的文件所得到的 find-references 结果。全局索引只接受已保存到磁盘的稳定状态；这些状态由后台索引根据磁盘文件构建。

• 基于内容标识的去重存在哈希冲突风险吗？

  Variant 的标识是编码后 blob 的 64 位哈希值，发生冲突的概率微乎其微，但在密码学意义上并非不可能。冲突会让两个确实不同的 Variant 共用一份存储副本，导致某个上下文返回错误的数据行，但不会损坏数据结构或导致服务器崩溃。这是有意做出的权衡，因为热点合并路径可以使用计算成本低得多的哈希。

• 为什么使用自定义规范编码，而不是通用序列化框架？

  有两个原因。第一，零拷贝：blob 只需校验一次，随后便可直接从映射内存中响应查询，而通用框架对零拷贝的支持程度不一。第二，也是更深层的原因——合并以字节同一性为准：由于编码结果严格且确定地由各行决定，“内容相同”与“字节相同”完全等价，去重只需比较哈希，而不必比较结构差异。如果框架的输出可能发生变化（字段顺序、填充、版本化传输格式），这种等价关系就会被破坏。

• 为什么将 Occurrence 和 Relation 分开存储？

  Occurrence 按位置索引——给定偏移量，可通过二分查找定位光标下的符号，因此数据必须按位置排序。Relation 按 SymbolHash 索引——给定符号，可查找其所有关系，因此数据必须按符号分组。将两者合并到同一个数据结构中，必然会牺牲至少一种查询模式的效率。

• 为什么跨文件查询在主进程而非子进程中执行？

  clice 采用多进程架构，每个打开的文件都在各自的有状态子进程中编译。跨文件查询（如查找引用）需要将所有打开文件的实时索引行与持久化索引合并。如果这些实时索引行分散在不同的子进程中，每次查询都需要与多个工作进程进行跨进程通信，再聚合结果——无论延迟还是复杂度都无法接受。因此，子进程会在编译完成后将索引行发回主进程，由主进程统一执行查询。主进程既能看到所有打开文件的实时索引行，也能看到项目索引和分片，从而在单个进程中完成整个查询流程。

  这一设计还涉及语义上的考虑：打开文件的查询结果应反映编辑器的缓冲区状态，而不是磁盘状态。即使磁盘上的文件已被外部工具修改，只要编辑器尚未发送 didChange 通知，查询结果就应以编辑器持有的版本为准。将实时索引行集中在主进程中，更容易维持这一语义不变量。

• 为什么索引使用嵌入式数据库存储，而 PCH/PCM 使用普通文件？

  它们的数据形态截然相反。索引数据块数量多（每个项目文件对应一个分片）、单个体积小，并且会在后台索引期间成批写入——这正是单个 LMDB 数据库占优的场景：支持批量原子提交，不会在规模扩大时产生逐文件目录项压力，内存映射读取还能保留零拷贝路径。PCH 和 PCM 文件则相反：数量少、体积大（数百 MB），由 Clang 自身直接进行内存映射，并且创建、读取和淘汰的生命周期很简单——文件系统配合制品存储的原子重命名提交就能很好地处理它们，而且 Clang 本来也无法直接使用数据库中的这类文件。如果所在文件系统（如网络挂载）无法让数据库安全运行，则会禁用索引持久化，而不是降级运行。

已知限制

• 内部链接符号的跨 TU 查询。 文件局部名称存储在分片的局部名称表中，但跨文件关系查询路径目前只能通过外部符号目录访问磁盘数据——因此，对 static 函数执行“查找引用”时，只会返回实时覆盖层能看到的结果。存储分层已经具备，但局部符号的查询路径尚未实现。

• PCH 导致的索引分裂（已解决）。使用 PCH 优化时，文件编译分为两个阶段：先将 Preamble 编译为 PCH，再使用 PCH 编译文件的其余部分。PCH 会屏蔽 Preamble 边界之前的所有内容——主文件的编译过程既看不到头文件的内容，也看不到 Preamble 区域自身的指令；此外，打开的缓冲区所对应的 Preamble 可能描述一种编译上下文，而磁盘上的翻译单元从未在该上下文中被索引。

  现在的解决方案是为每个 PCH 配套一个 Preamble 状态 blob，由同一个 worker 在构建过程中生成；此时新解析的 Preamble AST 仍在内存中，这是无需反序列化整个 PCH 即可获取其索引的唯一时机。该 blob 包含 Preamble 的完整符号索引——涵盖的所有头文件以及主文件的 Preamble 区域——还包含每个文件的内容和行表（用于位置映射）、文档链接、非活跃区域以及未闭合的条件栈。它与 PCH 一同存储、命中和淘汰，以内存映射的 FlatBuffer 形式打开，并且查询时无需反序列化。打开的文件会在索引查询上叠加这些 blob：集合查询与磁盘分片取并集（位置相同的记录会合并），单一答案查询优先使用该叠加层，缓冲区中的 Preamble 区域则通过 blob 的主文件条目解析。这样，即使后台索引器尚未（或无法）索引打开文件的翻译单元，代码导航仍能正常工作，结果也能准确反映尚未保存的 Preamble 编辑。