依赖扫描

背景

C++ 的 #include 指令在文件之间建立了依赖关系。语言服务器需要知道这些依赖关系，原因有三：

为头文件选择编译上下文。 头文件不在编译数据库（CDB）中，无法直接编译。语言服务器需要找到一个包含该头文件的源文件，借用它的编译命令来编译头文件。这要求知道"哪些源文件（直接或间接）包含了这个头文件"——即 include 关系的反向查询。如果没有这个信息，用户打开头文件时将无法获得正确的诊断、补全和导航。关于编译上下文的完整讨论见 编译上下文。

解析 C++20 模块依赖。 编译一个导入了模块的文件之前，必须先编译模块接口单元的 PCM。语言服务器需要知道"哪个文件提供了模块 foo"以及"这个文件导入了哪些模块"。这些信息只能通过扫描文件内容来发现，因为 CDB 不记录模块之间的依赖关系。关于模块编译的完整讨论见 模块编译。

优化后台索引顺序。 与用户当前打开的文件存在 include 关系的文件应该优先索引，这样用户能更快获得跨文件导航功能。include 图提供了文件之间的关联度信息。

问题在于：精确地获取 include 关系需要运行完整的 C 预处理器。C++ 的 #include 是文本替换——头文件的展开结果取决于包含它之前的预处理器状态。同一个头文件被不同源文件包含时，由于前面的 #define 和 #include 不同，可能走不同的条件编译分支，展开出不同的 include 列表：

// config.h
#ifdef USE_OPENSSL
#include <openssl/ssl.h>     // 源文件 A 看到
#else
#include <boringssl/ssl.h>   // 源文件 B 看到
#endif

这意味着每个 (源文件, 头文件) 的组合都必须独立预处理，无法共享结果。对于一个拥有上万个源文件、每个源文件平均包含数百个头文件的大型项目，工作量是 O(源文件数 × 平均头文件深度)——可能需要数百万次预处理操作，耗时数分钟，作为启动开销是不可接受的。

clangd 选择在后台索引过程中逐步构建 include 图——每编译一个翻译单元，就记录它的 include 关系。这个策略的问题在于，后台索引可能需要数十分钟才能覆盖整个项目。在此期间 include 图是不完整的，导致头文件的编译上下文选择只能依赖文件名匹配这类启发式方法。clangd #123 讨论了这个问题：后台索引积累的 include 信息可以改善头文件的编译命令选择，但这些信息直到索引完成才可用。在此之前，用户打开头文件时可能看到错误的诊断，或者根本无法跳转定义。

clice 通过在启动阶段运行一个快速依赖扫描器来解决这个问题。扫描器放弃预处理，使用纯词法分析来提取 include 信息——不展开宏、不求值条件表达式。这样做的结果是得到一个包含所有可能 include 关系的超集，但换取了数量级的速度提升：每个文件只需扫描一次（结果不依赖包含上下文），上万个文件在数秒内完成。

设计

超集扫描

依赖扫描的核心概念是超集扫描——放弃预处理以获得上下文无关的结果。

完整的预处理器在展开 include 时，会求值所有宏和条件表达式，因此只输出当前上下文下实际生效的 include。结果是精确的，但依赖于包含上下文——同一个头文件被不同源文件包含时，输出可能不同。这迫使每个 (源文件, 头文件) 组合都独立处理，工作量是 O(源文件数 × 平均头文件深度)。

快速扫描器跳过预处理，直接在词法层面识别 #include 指令和模块声明。它不知道哪些条件分支会生效，因此把所有分支中的 include 都记录下来。结果是一个超集——包含了所有可能被包含的头文件，可能多于任何单个编译上下文下的实际 include。但由于不依赖包含上下文，每个文件只需扫描一次，所有源文件共享同一个扫描结果，工作量降为 O(唯一文件数)。

这个超集对于依赖扫描的主要用途是安全的：查找宿主源文件时，超集意味着可能找到更多候选宿主，但不会遗漏正确的宿主；判断文件关联性时，超集意味着可能认为一些实际不相关的文件有关联，但不会错过真正相关的文件。

三种扫描模式

系统提供三种扫描模式，面向不同的使用场景：

快速词法扫描 是启动阶段的默认模式。使用 Clang 内置的依赖指令扫描器（scanSourceForDependencyDirectives），只识别以 # 开头的预处理指令行和模块声明。输出原始的 include 名称（如 "foo.h" 或 <vector>），需要后续的路径解析步骤。每个文件的扫描时间在微秒级。

精确预处理扫描 运行完整的 Clang 预处理器。输出的是已解析的文件路径（不是原始 include 名称），准确反映特定编译配置下的实际 include 关系。用于需要精确依赖信息的场景——例如 CompileGraph 在惰性解析模块依赖时，需要知道一个模块文件实际导入了哪些模块。由于需要完整的编译参数和预处理器实例，成本远高于快速扫描。

轻量模块声明扫描 是一种介于快速和精确之间的回退模式。当快速扫描发现模块声明位于条件编译指令内部时——例如 #ifdef _WIN32 后面的 export module platform;——它无法确定哪个模块声明实际生效。此时触发轻量扫描：启动预处理器，但只词法分析到模块声明为止就停止，不处理整个文件。代价远低于完整的精确扫描，只应用于极少数文件（绝大多数模块声明在文件顶层，不在条件编译中）。

DependencyGraph

DependencyGraph 是依赖关系的存储结构，在启动阶段由扫描器构建，之后在整个服务器生命周期内被多个模块查询。

正向 include 边 记录"一个文件直接包含了哪些文件"。以 (文件, 编译配置) 为键——同一个文件在不同的编译配置下，由于搜索路径不同，可能解析出不同的 include 目标。每条 include 边附带一个标记位，标识该 include 是否位于条件编译指令内部。

反向 include 映射 记录"一个文件被哪些文件直接包含"。在所有正向边建立完成后批量构建。主要用于宿主源文件查找：从目标头文件出发，沿反向边向上 BFS，直到找到没有 includer 的根节点（即 CDB 中的源文件）。

模块名映射 记录模块名到模块接口单元文件的映射关系。只有接口单元（export module 声明的文件）被注册。一个模块名可能对应多个文件——当不同的编译配置中扫描到同名的模块接口单元时。

搜索配置

将原始 include 名称（如 <vector> 或 "foo.h"）解析为实际文件路径，需要知道头文件的搜索目录。SearchConfig 封装了从编译参数中提取的搜索配置。

搜索目录按照 Clang 的 InitHeaderSearch::Realize 布局分为四段：

[Quoted (-iquote)] [Angled (-I)] [System (-isystem)] [After (-idirafter)]

这个分段决定了 include 解析的搜索顺序。#include "foo.h"（双引号）从 Quoted 段开始搜索——先在包含者所在目录查找，然后依次搜索 Quoted、Angled、System、After 段。#include <foo.h>（尖括号）跳过 Quoted 段，直接从 Angled 段开始。#include_next 从当前文件被找到的搜索目录的下一个位置开始。这些规则与 Clang 的头文件搜索行为一致。关于搜索配置的提取过程见 命令解析。

条件 include 标记

快速扫描虽然不求值条件表达式，但通过跟踪 #if/#ifdef/#ifndef 的嵌套深度，为每条 include 标记是"无条件的"还是"条件性的"：

#include <vector>           // 无条件——嵌套深度 0
#ifdef USE_BOOST
#include <boost/any.hpp>    // 条件性——嵌套深度 1
#endif
#include <string>           // 无条件——嵌套深度 0

当合并一个文件在所有编译配置下的 include 结果时，如果同一个目标在某个配置下是无条件的、在另一个配置下是条件性的，无条件优先。这反映了"至少在一个配置下，它一定会被包含"的语义。这个信息对宿主选择有指导意义：通过无条件 include 链到达目标头文件的源文件，是比通过条件 include 链到达的源文件更可靠的宿主候选。

实现

波前 BFS

依赖扫描的核心流程是一个波前式 BFS。CDB 中只有源文件，头文件需要通过解析源文件的 include 来发现。每一波处理当前已知但尚未扫描的文件，发现新的头文件作为下一波的输入。

Wave 0:  CDB 中的源文件  ──→  扫描  ──→  解析 include  ──→  发现头文件
Wave 1:  上一波发现的头文件  ──→  扫描  ──→  解析 include  ──→  发现更深层的头文件
Wave 2:  ...
  ↓
直到没有新文件被发现

每一波分为两个阶段：

Phase 1（并行）：读取 + 词法扫描。 当前波次的所有文件被提交到线程池，并行执行文件读取和快速词法扫描。每个文件的输出是一个 ScanResult，包含原始 include 名称列表和模块声明信息。

Phase 2（串行）：include 路径解析 + 图构建。 遍历 Phase 1 的扫描结果，将每条原始 include 名称通过搜索配置解析为实际文件路径，检查文件是否存在，将解析成功的 include 记录为 DependencyGraph 中的边。同时收集新发现的文件（之前未见过的路径）作为下一波的输入。

两个阶段之间有两处流水线优化，使相邻波次的工作互相重叠：

1. Wave 0 的 Phase 1（文件扫描）和目录列表缓存的预填充在线程池上并行执行。目录列表缓存只在 Phase 2 的 include 解析中才被使用，因此两者可以完全重叠。
2. Phase 2 在发现新文件时，立刻将其提交到线程池预取和扫描。当下一波的 Phase 1 启动时，这些预取任务通常已经完成或正在运行，减少了等待时间。

编译配置分组

一个项目中上万个源文件可能有不同的编译参数，但大部分文件共享相同的 include 搜索路径和编译选项。CompilationDatabase 将共享相同 CompilationInfo（目录、规范选项、用户内容选项均相同）的文件归为一个 ConfigGroup。依赖扫描为每个 ConfigGroup 提取一份 SearchConfig，同一组内的所有文件共用同一份搜索配置。

这种分组还服务于工具链探测的去重：不同 ConfigGroup 可能使用相同的编译器和语义选项，只有 include 路径不同。工具链的 warm() 方法在内部进一步按编译器标识去重，使得上万个源文件可能只需要一两次编译器子进程调用。

Include 路径解析

将原始 include 名称解析为文件路径时，需要在搜索目录中查找文件是否存在。传统做法是对每个候选路径调用 stat() 系统调用。clice 使用目录列表缓存（DirListingCache）来替代——对搜索路径中的每个目录执行一次 readdir()，将结果缓存在内存中的字符串集合里，后续的文件存在性检查通过集合查找完成。

这种方式将 N 次 stat() 调用替换为 1 次 readdir() + N 次内存查找。在 Windows 上效果尤其显著，因为 Windows 的 stat() 调用开销约为 Linux 的 10 倍。

对于多级路径的 include（如 <llvm/Support/raw_ostream.h>），解析器使用快速拒绝优化：先检查搜索目录中是否存在第一级目录名（如 llvm），大多数搜索目录不包含这个子目录，因此可以跳过后续的完整路径构建和子目录解析。

尖括号 include（<...>）的解析结果可以跨文件缓存——相同编译配置下的相同头文件名总是解析到相同路径，包括解析失败的负缓存。双引号 include（"..."）依赖包含者所在目录，无法跨文件缓存。

与其他模块的协作

编译上下文选择。 当用户打开一个头文件时，Compiler 通过 DependencyGraph 查找宿主源文件。先调用 find_host_sources 沿反向 include 边 BFS 到达 CDB 中有编译命令的根源文件，然后调用 find_include_chain 沿正向边 BFS 找到从宿主到目标头文件的最短 include 链。这条链用于合成头文件的前缀代码——即还原它在宿主源文件中被包含时的预处理器状态。完整讨论见 编译上下文。

模块依赖解析。 CompileGraph 在惰性解析模块依赖时，通过 DependencyGraph 的模块名映射查找模块接口单元的文件路径。快速扫描在启动时就建立了模块名到文件的映射，CompileGraph 可以立即使用，无需等待任何编译完成。完整讨论见 模块编译。

Agent 接口。 DependencyGraph 的正向和反向查询通过 Agent 协议暴露给外部工具。Agent 可以查询一个文件的直接和传递 include/includer 关系，也可以请求影响分析——给定一个文件，返回所有直接和间接依赖它的文件。

FAQ

• 为什么选择超集而不是精确结果？ 精确的 include 关系需要运行完整的预处理器，对上万个文件来说需要数分钟。而依赖扫描的主要消费者——宿主源文件查找和文件关联性判断——都可以容忍多余的候选结果。超集在数秒内完成，对这些场景是安全的：多找到一些候选宿主比遗漏正确的宿主好得多。需要精确结果的场景（如模块依赖解析）使用精确预处理扫描单独处理。

• 为什么不完全依赖后台索引来构建 include 图？ 这是 clangd 的做法：后台索引编译每个翻译单元时顺带记录 include 关系。问题在于后台索引可能需要数十分钟才能覆盖整个项目，在此期间 include 图是不完整的，头文件体验很差。clice 用快速扫描保证启动后数秒内就有完整的 include 图，后台索引提供的精确信息作为补充。

• 快速扫描和精确扫描的关系是什么？ 两者不是替代关系，而是服务于不同场景。快速扫描在启动阶段对所有文件运行，构建全局的 DependencyGraph，为宿主查找和关联性判断提供即时可用的 include 图。精确扫描按需运行，用于需要准确依赖信息的特定操作（如模块编译时的依赖解析）。快速扫描是超集，精确扫描是子集——快速扫描可能包含实际不存在的 include 边，精确扫描的每条边都是真实的。

• 为什么用目录列表缓存而不是 stat 调用？ 因为 include 路径解析需要在多个搜索目录中查找文件是否存在。如果对每个候选路径调用 stat()，一个文件的 include 解析可能触发数十次系统调用——乘以上万个文件就是数十万次。目录列表缓存将这些替换为每个目录一次 readdir() 加上内存中的集合查找。在 Windows 上（stat() 开销远高于 Linux），这个优化带来的改善更加显著。

• 为什么用波前 BFS 而不是一次性扫描所有文件？ CDB 中只列出了源文件。头文件不在 CDB 中——它们的存在只能通过解析源文件的 include 指令来发现。因此无法一次性确定需要扫描哪些文件，只能通过 BFS 逐层发现。波前 BFS 是这种惰性发现的自然表达，同时通过流水线重叠最大化了并行度。

已知局限

• 宏化的 include 无法被快速扫描器识别。#include MACRO_NAME 需要宏展开才能得到实际的头文件名，而快速扫描不做宏展开。这种模式在实际项目中不常见，受影响的文件在精确编译时会被正确处理，但在 include 图中会缺失对应的边。

  #define PLATFORM_HEADER "platform_linux.h"
  #include PLATFORM_HEADER   // 快速扫描无法识别

• 条件编译的精确性丢失。 快速扫描记录了所有条件分支中的 include，导致 include 图比实际更大。对于宿主源文件查找这是安全的（不会遗漏），但可能导致关联性判断过于宽泛——将实际不相关的文件误认为相关。

  #ifdef _WIN32
  #include <windows.h>    // 仅 Windows 上生效
  #endif
  #ifdef __linux__
  #include <unistd.h>     // 仅 Linux 上生效
  #endif
  // 快速扫描会同时记录 windows.h 和 unistd.h

• 大小写敏感性。 在大小写不敏感的文件系统（macOS HFS+/APFS、Windows NTFS）上，#include 中的大小写可能与磁盘上的文件名不一致。目录列表缓存的文件名匹配是大小写敏感的，可能导致解析失败。

• macOS Framework 搜索路径。 尚未实现 macOS 的 Framework 目录搜索（-F、-iframework）。<Foo/Bar.h> 形式的 Framework include 应该在 Foo.framework/Headers/ 下查找 Bar.h，但目前的解析器不识别这种特殊的目录结构。