依赖扫描
背景
C++ 语言服务器需要知道文件之间的 include 关系。这一需求来自几个方面：
头文件的编译上下文：头文件不在编译数据库（CDB）中，因此语言服务器必须为每个头文件选择一个宿主源文件，以获取编译命令。这需要知道“哪些源文件包含这个头文件”——即反向 include 关系。没有这些信息，用户打开头文件时就无法获得正确的诊断、代码补全或代码导航功能。
模块依赖解析：编译 C++20 模块需要知道模块之间的依赖关系。必须通过扫描文件内容来确定模块名到文件的映射以及模块之间的 import 关系。
优先级调度：后台索引需要确定文件的索引顺序。与用户当前打开的文件存在 include 关系的文件应该优先索引。include 关系图可以用来跟踪这种相关性。
问题在于，精确确定 include 关系需要运行完整的 C 预处理器——展开所有宏并对所有条件编译指令求值。对于大型 C++ 项目（包含数万个文件），启动时对每个文件运行预处理器需要数分钟，这是不可接受的。
clangd 的做法是在后台索引期间逐步构建 include 关系图——每次编译文件时，都记录其 include 关系。这意味着在后台索引完成之前（可能需要数十分钟），include 关系图并不完整。在此期间打开头文件时，可能无法找到正确的宿主源文件，从而产生错误的诊断。clangd 社区的用户曾多次报告，启动后很长一段时间内，头文件会显示错误的诊断，必须等到后台索引完成才能正常工作。
clice 使用专门设计的快速依赖扫描器解决了这个问题——牺牲精度来换取足够好的结果，并能在启动时于数秒内扫描数万个文件。
设计
核心思想
依赖扫描的核心权衡是用精度换取速度。完整的预处理器可以精确确定哪些 include 会生效、哪些会被条件编译排除，但它存在一个根本性的性能问题：同一个头文件在不同的源文件上下文中可能产生不同的展开结果，因此每个（源文件，头文件）组合都必须单独进行预处理——结果无法共享。快速扫描器不进行预处理，使扫描结果不受包含上下文影响——每个文件只需扫描一次，结果便可在所有上下文中共享。代价是所有条件分支中的 include 都会被视为生效，从而得到所有可能 include 关系的超集。虽然这个超集比实际的 include 关系更大，但对于依赖扫描的主要用例而言是安全的：
- 查找宿主源文件时，超集可能会得到更多候选宿主，但绝不会遗漏正确的宿主。
- 判断文件相关性时，超集可能会将一些不相关的文件视为相关，但绝不会遗漏真正相关的文件。
为什么这么快
快速扫描器的速度源于一项根本性的设计选择和几项关键优化：
根本优势：跨上下文共享结果
这是快速扫描器比完整预处理快几个数量级的根本原因。进行完整预处理时，不同源文件包含同一个头文件之前出现的 #define 和 #include 各不相同，因此预处理结果可能截然不同。这意味着每个（源文件，头文件）组合都必须单独进行预处理——工作量为 O（源文件数量 × 平均头文件包含深度）。对于包含数万个源文件的大型项目，如果每个源文件平均包含数百个头文件，就会产生数百万次预处理操作。
快速扫描器不进行预处理，因此扫描结果与包含上下文无关——无论同一个头文件被哪个源文件包含，得到的 #include 列表都相同。这意味着每个头文件只需扫描一次，结果可供所有源文件共享。工作量降至 O(唯一文件数)——通常只涉及几千到几万个文件，而非数百万次操作。
轻量级词法扫描
扫描器使用 Clang 的依赖指令扫描器（scanSourceForDependencyDirectives），它只识别以 # 开头的预处理指令行，不执行宏展开、条件表达式求值或 include 展开。扫描每个文件只需微秒量级的时间。
扫描结果是原始 include 名称（例如 "foo.h" 或 <vector>），需要在后续的路径解析阶段将其映射到实际文件路径。
对于条件编译中的 include，扫描器通过跟踪 #if/#ifdef/#ifndef 的嵌套深度进行标记：在深度大于 0 时遇到的 include 会被标记为“条件 include”。虽然该标记无法反映条件的具体求值结果，但仍能提供有用的元数据。
独立的路径解析阶段
将 include 名称映射到实际文件路径是一个独立阶段。解析器使用目录列表缓存——预先读取搜索路径中各目录的文件列表，然后通过内存中的字符串集合检查文件是否存在，从而避免大量 stat 系统调用。
尖括号 include（例如 <vector>）的解析结果可以跨文件缓存——在相同的编译配置下，同一个头文件名总是解析到同一路径。双引号 include 的解析结果取决于包含它的文件所在的目录，无法跨文件缓存，但每个文件通常只有很少的双引号 include。
波前式 BFS 发现
扫描不会一次性处理所有文件，而是分波次展开：
- 第 0 波：扫描编译数据库中的所有源文件（并行 I/O + 词法扫描）
- 路径解析：将发现的 include 名称映射到文件路径，并识别新发现的头文件
- 第 1 波：扫描新发现的头文件，继续发现其中的 include……
- 重复上述过程，直到找不到新文件
一项关键优化是：当前波次进行路径解析（串行）时，已经可以开始预取和扫描下一波次的文件（并行）。这种流水线式的重叠执行隐藏了大部分 I/O 延迟。
DependencyGraph 存储结构
DependencyGraph 存储文件之间的 include 关系，并支持正向和反向查询：
正向 include：给定文件和编译配置，返回该文件直接包含的所有文件。每条边都会通过位标志记录它是否为条件 include。同一个文件在不同编译配置下可能具有不同的 include 集合（因为搜索路径不同），因此键是（文件，配置）对。
反向 include：给定文件，返回所有直接包含该文件的文件。这是在所有正向 include 建立后批量构建的反向索引。它用于“查找宿主源文件”——从目标头文件出发，沿反向边向上进行 BFS，直到找到具有 CDB 条目的源文件。
模块映射：从模块名到模块接口单元文件路径的映射，用于解析 C++20 模块依赖关系。只有接口单元（export module）会被注册到映射中。同一个模块名可能映射到多个路径（当同一个模块在不同编译配置中被发现时）。
处理条件 include
扫描器不对条件表达式求值，而是通过跟踪嵌套深度，将 include 标记为“条件 include”或“无条件 include”：
#include <vector> // unconditional (depth 0)
#ifdef USE_BOOST
#include <boost/any.hpp> // conditional (depth 1)
#ifdef BOOST_HAS_X
#include <boost/x.hpp> // conditional (depth 2)
#endif
#endif
#include <string> // unconditional (depth 0)查询一个文件在所有配置下的 include 并集时，如果同一个头文件在一种配置下是无条件 include，而在另一种配置下是条件 include，则以无条件 include 为准——这反映了“它至少在一种配置下一定会被包含”的语义。
处理模块声明
C++20 模块声明（export module foo;、module foo:bar;）通常出现在文件顶部，快速扫描器可以直接识别它们。然而，如果模块声明出现在条件编译块（#ifdef）内部，快速扫描器无法确定哪个声明实际生效。
在这种情况下，扫描器会设置 need_preprocess 标志，触发精确回退机制——仅对文件开头部分（截至模块声明）运行预处理器，并对条件表达式求值，以确定实际的模块名。这个回退机制只影响极少数文件（绝大多数模块声明位于顶层），不会影响整体扫描速度。
缓存与增量更新
扫描结果在多个层级进行缓存：
- 扫描结果缓存：每个文件的扫描结果（include 列表、模块声明）按 master 的文件表中的文件标识和内容版本记录，只要内容版本仍然匹配，就会在多次重扫中复用——保存后的重扫只重新读取内容实际发生变化的文件。缓存只存在于内存中；服务器重启后从零开始扫描。
- 目录列表缓存：搜索路径中每个目录的文件列表缓存在内存中，在初始扫描期间通过并发的 readdir 任务填充。
- include 解析缓存：尖括号 include 的解析结果按（配置，头文件名）缓存，包括解析失败的负缓存。
与宿主源文件查找的协作
依赖扫描的核心用途之一是为头文件查找宿主源文件。过程如下：
- 从目标头文件出发，沿反向 include 索引向上遍历
- 找到所有传递包含目标头文件的根文件（没有被任何其他文件包含的文件）
- 筛选出在 CDB 中有编译命令的源文件作为候选宿主
- 选择第一个具有有效 include 链的候选宿主作为默认宿主
include 链查找使用 BFS，以保证找到最短路径。编译上下文系统随后使用这条 include 链构建头文件的编译环境。
作为补充的精确扫描与后台索引
快速扫描在启动阶段提供近似结果。随着服务器运行，后台索引系统逐步编译项目中的每个翻译单元，在编译过程中获得精确的 include 关系（执行完整预处理，对所有宏和条件编译进行求值）。这些精确的 include 关系记录在索引数据（TUIndex/MergedIndex）中。需要注意的是，后台索引目前不会更新启动时构建的 DependencyGraph——在服务器的整个生命周期内，宿主源文件查找和文件依赖查询仍会使用快速扫描生成的 include 图。
此外，系统提供精确扫描模式（scan_precise）——对需要准确依赖信息的特定场景运行完整的 Clang 预处理器，例如模块编译期间的惰性依赖解析（通过 CompileGraph 的 resolve_fn）。精确扫描结果是解析后的文件路径（而非原始 include 名称），能够准确反映特定编译配置下的实际 include 关系。
快速扫描和后台索引是互补的：快速扫描保证启动后数秒内就能获得可用的 include 图（因此用户可以立即获得头文件支持），而后台索引在随后的几分钟内逐步补充精确信息。两者不是替代关系——即使后台索引完成之后，快速扫描结果仍用于初始文件发现和构建初始依赖图。
设计决策与权衡
为什么用超集而不是精确结果？ 精确结果需要运行预处理器，对上万个文件需要数分钟。超集可在数秒内生成，用于宿主查找和相关性判断也很稳妥——多找到几个候选宿主远比遗漏正确的宿主好。
为什么不完全依赖后台索引来构建精确的 include 图？ clangd 完全依赖后台索引来构建 include 关系，但后台索引可能需要数十分钟才能完成。在此期间，头文件的使用体验并不完整——用户打开头文件时会看到错误的诊断，而这些诊断需要很长时间才能自行纠正。clice 使用快速扫描来保证启动后数秒内即可获得可用的 include 图，随后由后台索引逐步补充精确信息。两者结合，既保证了即时可用性，也保证了最终的精确性。
为什么逐波展开，而不是一次性扫描所有文件？ 系统事先不知道需要扫描哪些头文件——它们不在 CDB 中，只能通过解析源文件中的 include 来发现。波前展开是惰性发现的自然模式，而流水线重叠可最大限度提高并行度。
为什么条件 include 标记有用？ 虽然具体的条件求值结果未知，但区分“一定会被包含”和“可能被包含”能为宿主选择提供依据。与通过条件 include 链连接的源文件相比，通过无条件 include 链包含目标头文件的源文件是更可靠的宿主候选。
已知限制
- 宏形式的 include：形如
#include MACRO_NAME的 include 无法由快速扫描器解析——必须进行宏展开才能确定实际的头文件名。这种模式在实际项目中相对少见；受影响的文件会在精确编译期间得到正确处理。 - 条件编译的精确性：所有条件分支中的 include 都会被记录，因此 include 图会比实际情况更大。这对于宿主查找是安全的（不会遗漏），但可能导致相关性判断过于宽泛。
- 大小写敏感性：在大小写不敏感的文件系统（macOS、Windows）上，如果 include 中的大小写与文件名不一致，解析可能会失败。
- Framework 搜索路径：尚不支持 macOS 的 Framework 目录（
-F、-iframework）；形如<Foo/Bar.h>的 Framework include 无法正确解析。