clice.io

简体中文

English

简体中文

English

外观

符号索引 ​

背景 ​

跳转到定义、查找引用、调用层次结构与类型层次结构都需要跨文件工作，因此语言服务器需要维护全项目范围的索引，记录每个符号出现的位置以及符号之间的关系。C++ 从两方面增加了这套索引的难度。

上下文。 同一个头文件对不同的包含方可能意味着不同的内容：

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

只保留某一个包含方视角的索引会丢失另一个包含方的引用。clangd 的后台索引对每个头文件只保留最后一次编译的结果，因此哪个翻译单元最后建立索引，就以哪个为准。

规模。 包含几千个源文件的项目就有数十万个符号，LLVM 或 Chromium 更达数百万个。内存占用、构建耗时与查询延迟都必须在这一规模下保持可控。clangd 将符号数据随声明该符号的文件一同存储，导致跨文件引用计数无法累加（clangd#23），也有部分引用要等到打开所在文件后才会出现（clangd#516、clangd#802）；编译命令变更还不会触发重新索引（clangd#199）。

clice 将紧凑的全局符号目录与单文件数据分离，把文件的每个编译上下文存为按内容去重的变体，将全部数据存入单个原地读取的嵌入式数据库，并在其上叠加已打开文件自身的编译结果，使查询结果始终紧跟正在编辑的缓冲区。

设计 ​

符号标识 ​

符号表示为由其实体（entity）计算出的 64 位哈希：实体只包含所有重声明共有的信息，因此在每个翻译单元、每个进程中算出的哈希完全相同。它由外层作用域链、名称，以及区分同名声明的要素构成——函数的参数类型、模板头与约束、特化的模板实参。类型按规范形式参与哈希，因此 typedef 的哈希与它所指代的类型一致。具有内部链接的声明还会带上声明它的文件：头文件中的 static 辅助函数在所有包含该头文件的翻译单元中是同一个符号，而两个源文件中的同名辅助函数则是两个不同的符号。项目内的文件按相对于项目根目录的相对路径参与哈希，因此移动源码检出目录后所有符号哈希均保持不变。

符号出现与关系 ​

索引存储两类条目。符号出现（occurrence）由源码范围和该处书写的符号组成，通过对位置做二分查找来回答“光标下是什么符号”。关系（relation）由关系种类、源码范围和目标符号组成：涵盖定义、声明、引用、调用、基类与派生类、重写、类型定义、特化等种类，用来回答“该符号在哪里定义、使用和调用”。两类条目分开存储，因为前者按位置查找，后者按符号查找。

分层结构 ​

unit index        what one compile produced, discarded once merged
    ↓ merge
project index     the directory: external symbols, and which units contributed which files
shard             one file's entries, a variant per context, loaded on demand
instantiations    what instantiations and macro expansions resolve in one file
    ↑ overlay
live index        the open buffer's latest compile
  • 项目索引（project index）为每个外部可见符号保存一条小记录——只记“是什么”，不记“在哪里”：名称、父级、种类、标志，以及引用、声明和定义该符号的文件集合——同时记录哪些翻译单元贡献了哪些文件。一次查询只读取寥寥几条记录；打开索引时只需读取数据库头部和名称搜索索引。
  • 分片（shard）保存单个文件的条目，为每种预处理结果不同的上下文各存一个变体。文件局部名称（内部链接符号、函数局部变量）将元数据留在分片内；被多个文件提及的局部名称（如头文件中的 static 辅助函数）则会在项目索引中多一条记录，列出存有其条目的文件。
  • 已打开文件的实时索引（live index）来自其最近一次编译，从不写入全局索引：正在输入的不完整代码不应改变其他文件看到的结果。只要缓冲区文本仍与分片建立索引时一致，当前编译上下文跳过的代码就会由分片代为作答，使头文件的其他编译上下文也能正常呈现。

按内容去重的变体 ​

被 N 个源文件包含的头文件会产生 N 组条目，其中绝大多数完全相同。每个变体都采用规范编码——条目相同则字节相同——并以这串字节的哈希作为标识。合并翻译单元时，若对应的变体已经存在，只需登记该翻译单元，无需解码或写入任何数据。绝大多数合并走的都是这条路径，全项目索引的开销因此得以保持低廉。哪些变体仍然有效，则取决于当前还有哪些翻译单元为它们背书。

实例化与宏展开 ​

模板自身的条目只记录在未知任何模板实参时其定义体所指向的符号：在 Box<T>::show 中，value.print() 不指向任何符号，因为 value 的类型是 T。它实际指向什么取决于实例化——对应 A::print（Box<A>）还是 B::print（Box<B>）——若将任一结果写入头文件的分片，都会让该分片随索引它的翻译单元而变化。宏体也是如此：#define AREA (WIDTH * WIDTH) 实际指向展开位置处的 WIDTH。

因此，每个实例化定义与每次宏展开都会单独投影到模板或 #define 所在的源码位置，只保留该处字面条目尚未确定的关系。这些记录构成文件的实例化记录（instantiations），存放在其分片旁边；查找引用、调用层次结构与重命名都会把它们当作代码通过实例化或宏展开到达的位置。在每个翻译单元中重复遍历所有实例化会让索引耗时翻倍；由于同一实例化在各个翻译单元中含义相同，翻译单元会跳过其他未过期翻译单元已经遍历过的实例化。

系统头文件的函数体及其模板的实例化默认略过，除非规则通过 index_function_body 显式开启：std::vector 的内部实现属于标准库自身，否则每个包含它的翻译单元都要重复遍历一遍。

存储 ​

所有索引数据——记录、分片、翻译单元清单、名称搜索索引——均存放在同一个 LMDB 数据库中。每个数据块采用紧凑的规范编码，读取时只校验一次，随后直接从内存映射中原地访问，省去反序列化步骤。数据库对项目内的文件一律记录相对于项目根目录的路径，因此移动检出目录后原有索引依然有效。每次保存通过单个事务批量写入改动；记录校验失败意味着存储损坏，下一次保存会丢弃整个数据库并重新建立索引。LMDB 从不向文件系统归还已释放的页，因此待索引空闲且文件中空闲空间较多时，写入方会生成一份紧凑副本替换原文件。

每个翻译单元的清单（manifest）集中记录一份上下文——编译时见到了哪些文件、经过了哪棵包含树——各分片无需重复保存。过期检测与状态核对（翻译单元从编译数据库中移除、编译命令变更、依赖文件变更）都直接基于清单执行。

查询 ​

以查找引用为例：先从光标下的符号出现条目拿到目标符号；由符号记录查出直接引用它的文件以及通过实例化引用它的文件；每个文件若已打开且实时索引为最新，则由实时索引作答，否则由分片的有效变体与实例化记录作答；最后收集目标种类的关系条目并转换为源码位置。分片自带行表，无需打开文件即可完成位置转换。Preamble 已编译为 PCH 的打开文件，还会由一份随 PCH 一同构建（趁其 AST 仍在内存中时生成）的 Preamble 索引补充作答。

按名称搜索（workspace/symbol 与 clice query 定位符）运行在一份由符号记录派生的搜索索引之上，该索引分段持久化在符号记录旁边。其检索词项是模糊匹配沿标识符各单词可能走过路径上的 trigram（gsh 和 symhash 都能通向 getSymbolHash），对查询词的 trigram 求交即可筛出匹配器可能接受的全部候选，只对这些候选评分；较短的查询以名称开头的单词为键，结果不足时还会再跑一轮允许一处拼写错误的查找来补齐。段内条目按质量顺序排列，一旦剩余条目已不可能进入结果集即可提前终止扫描。每次保存都会把新增改动写成新的一批段，并将小批逐步归并为大批，使单个符号被重写的次数保持在对数级。

过期检测 ​

每个索引产物都会记录各输入文件的内容版本，由共享的新鲜度检查统一核验（参见增量编译）。仅当输入文件的实际内容发生更改，或命令哈希发生更改时，翻译单元才会重新建立索引。启动时，写入方会将每条文件记录与磁盘核对，并将待更新的翻译单元排入队列；在重新索引完成前，已存储的分片继续提供查询服务。

常见问题 ​

  • 为什么要拆成全局目录和分片，而不是做成单一索引？ 把位置信息放进目录会让每条记录大幅膨胀，导致每次查询读取远超所需的数据；而没有目录的话，每次查询又不得不打开所有分片才能找出哪些文件含有目标符号。
  • 为什么使用规范编码，而不用通用序列化框架？ 因为去重比对的就是字节一致性：编码结果严格由条目内容决定，内容相同意味着字节完全相同，合并时只需比对哈希。同时这也让数据块能够直接从内存映射中响应查询。
  • 哈希碰撞会有风险吗？ 64 位哈希一旦碰撞，会让两个不同的变体共用同一份拷贝——导致某个上下文读到错误的条目——但不会破坏数据库或导致服务器崩溃。合并热路径上选用开销低廉的哈希是有意权衡的结果。
  • 为什么跨文件查询在主进程中执行？ 跨文件查询需要把所有已打开文件的实时索引与持久化索引结合起来。若分散在各个 worker 中，每次查询都得跨进程询问多个 worker 再合并结果；放在主进程中只需一次本地读取，而且主进程正是掌握各缓冲区版本号的地方。
  • 为什么索引用数据库存储，而 PCH 和模块用普通文件？ 索引数据块数量多、体积小且成批写入，批量事务与单一内存映射在此场景下优势明显。PCH 和 PCM 则数量少、体积大，且由 Clang 自身直接做内存映射，Clang 无法直接从数据库中读取它们。

已知限制 ​

  • 实例化的解析结果以遍历它的翻译单元为准。 翻译单元在单一定义规则（one-definition rule）成立的前提下，会跳过其他翻译单元已遍历过的实例化；违反该规则的程序——例如实参依赖查找（argument-dependent lookup）命中的重载位于仅部分翻译单元包含的头文件中——会按实际遍历它的那个翻译单元所见的结果作答。
  • 实例化记录不保存模板实参。 索引只记录实例化中依赖代码解析到了什么符号，不记录使用了哪些实参，也不记录在何处实例化。
  • Preamble 中宏展开的结果由后台索引作答：已打开文件 Preamble 头文件中宏体所拼出的名称，要等后台索引遍历过这些头文件后才能回答。