5.9.1 解析器
13 分钟阅读
原文链接: https://docs.astral.sh/uv/reference/internals/resolver/
5.9.1 解析器
提示
本文档聚焦 uv 解析器的内部工作机制。关于使用 uv，请参阅解析概念文档。
解析器
按教科书的定义，解析（即从一组要求中找出一组要安装的版本）等价于 SAT 问题，因而是 NP 完全的：最坏情况下你必须尝试所有包所有版本的所有可能组合，而且没有通用且快速的算法。实践中，由于若干原因这种说法具有误导性：
- uv 中解析最慢的部分是加载包和版本元数据，即使这些数据已缓存。
- 存在许多可能解，但有些比其他更可取。例如我们通常优先使用包的最新版本。
- 包的依赖很复杂，例如存在连续的版本范围 —— 而不是任意的布尔式版本包含/排除；相邻发布往往具有相同或相似的要求，等等。
- 对大多数解析而言，解析器不需要回溯，迭代式地挑选版本就足够了。如果已有上一次解析留下的版本偏好，几乎不需要做任何工作。
- 解析失败时，需要的信息比“无解”这一消息更多（SAT 求解器就是如此）。解析器应给出可理解的错误追踪，说明涉及哪些包，以便用户消除冲突。
- 对性能和用户体验最重要的启发式是通过优先级决定决策的顺序。
uv 使用 pubgrub-rs，即增量式版本求解器 PubGrub 的 Rust 实现。uv 中的 PubGrub 按以下步骤工作：
- 从一个部分解开始，它声明哪些包的版本已被选定、哪些尚未决定。初始时只确定了虚拟的根包。
- 从尚未决定的包中选出优先级最高的包。大致上，带 URL 的包（包括文件、git 等）优先级最高，其次是带更精确说明符（例如
==）的包，再次是说明符较宽松的包。每个类别内部，包按首次出现的顺序（即在文件中的顺序）排列，这使解析具有确定性。 - 为所选包挑选一个版本。该版本必须满足部分解中所有 requirement 的说明符，且不得先前被标记为不兼容。解析器优先使用来自锁文件（
uv.lock或-o requirements.txt）的版本，以及当前环境中已安装的版本。版本从高到低检查（除非使用了替代的解析策略）。 - 所选包版本的所有 requirement 会被加入尚未决定的包。uv 会在后台预取它们的元数据以提升性能。
- 该过程会用下一个包重复，除非检测到冲突，此时解析器会回溯。例如，部分解中包含
a 2、b 2，其要求为a 2 -> c 1和b 2 -> c 2。找不到c的兼容版本。PubGrub 可以判定这是由a 2和b 2造成的，并加入不兼容关系{a 2, b 2}，表示当选中其中一个时另一个不能被选中。部分解会被恢复为带该不兼容关系的a 2，解析器尝试为b挑选新版本。
最终，解析器要么为所有包挑选出兼容版本（解析成功），要么存在包含虚拟“根”包的不兼容关系（根包定义用户请求的版本）。与根包的不兼容表示无论挑选根依赖及其传递依赖的哪些版本，总会存在冲突。根据 PubGrub 中跟踪的不兼容关系，会构造一条错误消息列出涉及的包。
提示
关于 PubGrub 算法的更多细节，请参阅 PubGrub 算法内部机制。
除 PubGrub 的基础算法之外，我们还使用一种启发式：当两个包冲突次数过多时，回溯并交换它们的顺序。
分叉
历史上 Python 解析器不支持回溯，而且即使支持回溯，解析通常也只限于单一环境，即某一种特定架构、操作系统、Python 版本和 Python 实现。有些包对不同环境使用相互矛盾的要求，例如：
numpy>=2,<3 ; python_version >= "3.11"
numpy>=1.16,<2 ; python_version < "3.11"
由于 Python 只允许每个包存在一个版本，朴素的解析器在这里会报错。受 Poetry 启发，uv 使用分叉解析器：只要某个包存在带不同标记的多个 requirement，解析就会被拆分。
在上面的示例中，部分解会被拆成两个解析，一个针对 python_version >= "3.11"，一个针对 python_version < "3.11"。
如果标记重叠或缺少标记空间的某一部分，解析器会做更多次拆分 —— 每个包可能有许多分叉。例如，给定：
flask > 1 ; sys_platform == 'darwin'
flask > 2 ; sys_platform == 'win32'
flask
会为 sys_platform == 'darwin'、sys_platform == 'win32' 以及 sys_platform != 'darwin' and sys_platform != 'win32' 各创建一个分叉。
分叉可以嵌套，也就是说每个分叉都依赖于此前发生的任何分叉。包相同的分叉会被合并，以保持分叉数量较少。
提示
可以在
uv lock -v的日志中观察分叉，查找Splitting resolution on ...、Solving split ... (requires-python: ...)和Split ... resolution took ...。
分叉解析器的一个难点是：拆分发生的位置取决于包被看到的顺序，而后者又取决于偏好（例如来自 uv.lock 的偏好）。因此解析器可能以特定分叉求解出要求并写入锁文件，而再次调用解析器时，由于偏好导致不同的分叉点，会得到不同的解。为避免这种情况，每个分叉以及每个在分叉之间发生分歧的包的 resolution-markers 都会被写入锁文件。执行新的解析时，会使用锁文件中的分叉来确保解析稳定。当要求变化时，新的分叉可能会被加入已保存的分叉。
Wheel 标签
虽然 uv 的解析对环境标记是通用的，但这不适用于 wheel 标签。Wheel 标签可以编码 Python 版本、Python 实现、操作系统和架构。例如 torch-2.4.0-cp312-cp312-manylinux2014_aarch64.whl 只与 arm64 Linux 上 glibc>=2.17（按 manylinux2014 策略）的 CPython 3.12 兼容，而 tqdm-4.66.4-py3-none-any.whl 可用于任何操作系统和架构上的所有 Python 3 版本与解释器。大多数项目都有通用兼容的源码分发，在尝试安装没有兼容 wheel 的包时可以使用；但有些包（例如 torch）不发布源码分发。这种情况下，在（例如）Python 3.13、不常见的操作系统或架构上安装会失败，并报错找不到匹配的 wheel。
标记与 wheel 标签过滤
在每个分叉中，我们知道哪些标记是可能的。在非通用解析中，我们知道它们的确切取值。在通用模式下，我们至少知道 python requirement 的一个约束，例如 requires-python = ">=3.12" 意味着 importlib_metadata; python_version < "3.10" 可以被丢弃，因为它永远无法安装。如果还设置了 tool.uv.environments，我们可以过滤掉标记与这些环境不相交的 requirement。在每个分叉内部，我们还可以按分叉标记进一步过滤。
标记表达式中存在一些冗余：某个标记字段的取值蕴含另一个字段的取值。在内部，我们会把 python_version 与 python_full_version，以及 platform_system 与 sys_platform 的已知取值规范化到一个共享的规范表示，以便它们可以相互匹配。
当我们选中的版本带本地标签（例如 1.2.3+localtag），而 wheel 未覆盖对 Windows、Linux 和 macOS 的支持，同时存在一个不带标签的基础版本（例如 1.2.3）支持缺失的平台时，我们会尝试通过按平台分别使用带本地标签和不带本地标签的版本来扩展平台支持，从而分叉。这有助于处理像 torch 那样用本地标签区分不同硬件加速器的包。虽然 wheel 标签与标记之间没有一一对应关系，但我们可以为已知平台（包括 Windows、Linux 和 macOS）建立映射。
元数据一致性
与 poetry 类似，uv 要求特定索引中某个包的同一版本的所有 wheel 具有相同的依赖（METADATA 中的 Requires-Dist），包括从源码分发构建出的 wheel。更一般地说，uv 假定每个 wheel 在其 dist-info 目录中有相同的 METADATA 文件。
例如 numpy 2.3.2 有 73 个 wheel。没有这个假定，uv 就必须发出 73 次网络请求来获取其元数据，而不是一次。没有元数据一致性还会带来另一个问题：标记与 wheel 标签之间缺少一一对应关系。Wheel 标签可以包含 glibc 版本，而 PEP 508 标记无法表示它。如果各 wheel 的元数据不同，通用解析器就必须同时跟踪两个维度：PEP 508 标记和 wheel 标签。这会大幅增加复杂度，而两者之间的对应关系也没有被妥善规定。PEP 508 标记的引入正是为了允许不同平台之间有不同的依赖，即为所有 wheel 提供单一的依赖声明，例如 project.[optional-]dependencies。如果这些标记不够用，我们应当扩展 PEP 508 标记，而不是使用并行的 wheel 标签体系。
元数据一致性的另一方面是：源码分发必须构建出与 wheel 元数据相同的 wheel，或者在没有 wheel 时每次构建出相同的元数据。如果这一假定被违反，可靠的依赖锁定就变得不可能：设想包 A 有源码分发。解析期间我们构建 A v1 并得到依赖 B>=2,<3。我们锁定 A==1 和 B==2。在目标机器上安装该锁文件时，我们再次构建，得到依赖 B>=3,<4 和 C>=1,<2。锁文件安装失败：由于约束变化，锁定的 B 版本不兼容，而且没有为 C 锁定的候选。此后重新解析既带来可复现性问题（锁文件实际上被忽略），也带来安全担忧（C 未被审查，B==3 也没有）。发生这种情况时可以在安装阶段报错，但为时已晚的错误（可能发生在部署期间）用户体验很糟。已经存在一种 uv 在安装时报错的情况：包没有源码分发，只有与当前平台不兼容的特定平台 wheel。虽然 uv 有必需环境作为缓解，但它需要一个并不广为人知的配置选项，而关于（不）支持环境的问题正是 uv 用户最常见的问题之一。源码分发的类似情况应当避免。
虽然旧版本的 torch 和 tensorflow 元数据不一致，但所有近期版本元数据都是一致的，我们也不知道有任何主要包存在元数据不一致。不过 Python 打包标准并未要求元数据必须一致，要求在标准中强制执行这一点的提案也被拒绝了（https://discuss.python.org/t/enforcing-consistent-metadata-for-packages/50008）。
有些包包含与其他包中原生代码链接的原生代码，例如 torch。这些包可能支持针对一系列 torch 版本构建，但一旦构建完成，就被约束到特定的 torch 版本，运行时 torch 版本必须与构建时版本一致。这目前是所有包管理器的痛点，因为从 pip 到 uv 的所有主流包管理器都会缓存源码分发的构建结果。uv 通过 tool.uv.extra-build-dependencies 配合 match-runtime = true，支持根据已安装包的版本进行多种构建。这是一个变通方案，需要用户为每个受影响的包设置，而不是由库开发者声明该要求（后者在标准原生支持的情况下是可行的）。
Requires-python
为确保 requires-python = ">=3.9" 的解析能够真正安装到所包含的 Python 版本上，uv 要求所有依赖具有相同的最低 Python 版本。声明更高最低 Python 版本的包版本（例如 requires-python = ">=3.10"）会被拒绝，因为使用该版本的解析无法安装到 Python 3.9 上。这确保当你在较旧的 Python 版本上时能安装旧包，而不是得到需要更新 Python 语法或标准库特性的新包。
uv 忽略 requires-python 的上界，但对只有 ABI 特定 wheel 的包有特殊处理。例如，如果某个包声明 requires-python = ">=3.8,<4"，<4 部分会被忽略。关于缺点与替代方案的详细讨论见 #4022 和这个 DPO 讨论帖，本节只总结与 uv 设计最相关的方面。
对大多数项目来说，无法在某个新版本发布之前判断它们是否兼容，因此提前阻止更新的版本会阻止用户升级或测试更新的 Python 版本。例外是使用不稳定的 C ABI 或 CPython 内部实现（例如其字节码格式）的包。
为之前没有使用 requires-python 上界的项目引入上界，并不会阻止该项目在过于新的 Python 版本上被使用。解析器不会失败，而是会挑选一个不带该上界的旧版本，从而绕过该上界。
为使解析尽可能通用可安装，uv 确保所选的依赖版本与项目的 requires-python 范围兼容。例如对于 requires-python = ">=3.12" 的项目，uv 不会使用 requires-python = ">=3.13" 的依赖版本，否则解析无法安装到项目声明支持的 Python 3.12 上。把同样的逻辑应用到上界意味着：提高项目的 Python 上界会让它与更少的依赖版本兼容，可能在没有依赖版本支持所需范围时解析失败。（降低 Python 下界则相反，只会扩大受支持的依赖版本集合。）
注意这与 Conda 不同：Conda 的求解器也决定 Python 版本，因此它可以改为选择更低的 Python 版本。Conda 还可以在发布后修改元数据，从而为新 Python 版本更新兼容性，而 PyPI 上的元数据一经发布就无法修改。
忽略上界对 numpy 这类使用 CPython 版本相关 C API 的包是个问题。撰写本文时，每个 numpy 发布支持 4 个 Python 次要版本，例如 numpy 2.0.0 有 CPython 3.9 到 3.12 的 wheel 并声明 requires-python = ">=3.9"，而 numpy 2.1.0 有 CPython 3.10 到 3.13 的 wheel 并声明 requires-python = ">=3.10"。这意味着当 uv 在 requires-python = ">=3.9" 的项目中解析 numpy>=2,<3 要求时，它会选择 numpy 2.0.0，而锁文件无法安装到 Python 3.13 或更新版本上。为缓解这一点，每当 uv 拒绝一个要求更新 Python 版本的版本时，我们会按该 Python 版本拆分解析标记进行分叉。该行为可以通过 --fork-strategy 控制。在上述示例中，遇到 numpy 2.1.0 时我们会分叉为 Python 版本 >=3.9,<3.10 和 >=3.10，并解析出两个不同的 numpy 版本：
numpy==2.0.0; python_version >= "3.9" and python_version < "3.10"
numpy==2.1.0; python_version >= "3.10"
只有一种情况 uv 会考虑上界：当项目对 requires Python 使用上界时，例如只部署到 Python 3.13 的应用使用 requires-python = "==3.13.*"。uv 会在后处理步骤中从锁文件里裁剪掉该范围之外的 wheel（例如 cp312 和 cp314），这不影响解析本身。
URL 依赖
在 uv 中，依赖可以是仓库依赖（带版本说明符的包或纯包名），也可以是 URL 依赖。所有形如 {name} @ {url} 的要求都是 URL 依赖，所有具有 git、url、path 或 workspace 来源的依赖也是。
为包声明 URL 时，uv 会把该包固定到该 URL 以及该 URL 蕴含的版本。如果某个包有两个冲突的 URL，解析器会报错，因为 URL 只能像精确的 == 固定那样声明，而不能作为 URL 列表声明。URL 列表可以通过扁平索引支持。
uv 要求 URL 要么被直接声明（在项目中、在工作区成员中、在约束中，或在覆盖中，即任何被直接发现的位置），要么由其他 URL 依赖引入。uv 会在解析之前发现所有 URL 依赖及其传递 URL 依赖，并把所有包固定到这些 URL 及它们蕴含的版本。
uv 不允许索引包中出现 URL。原因有二：其一是安全与可预测性，禁止仓库分发指向非仓库分发，并有助于审计可以访问哪些 URL。例如，当只使用一个索引 URL 且没有 URL 依赖时，uv 不会从该索引之外安装任何包。
其二是 URL 会给解析添加额外版本。假设根包依赖 foo、bar 和 baz，它们都是仓库依赖。foo 依赖 bar >= 2，但 bar 在索引上只有版本 1。在这种增量方式下这是一个错误：foo 无法满足，出现解析器错误。如果允许索引包上的 URL，那么可能出现这种情况：某个 baz 版本声明依赖 baz-core，而后者有一个版本声明 bar @ https://example.com/bar-2-py3-none-any.whl，从而添加了一个使要求得以解析的 bar 版本。如果依赖可以添加新版本，那么在解析器中丢弃任何版本都需要考察所有直接和传递依赖的所有可能版本。这破坏了增量解析器的核心假定 —— 包的版本集合是静态的，并且会要求始终获取所有可能可达版本的元数据。
优先级
优先级对性能和更好的解析结果都很重要。
如果我们尝试了许多之后必须丢弃的版本，解析就会很慢，既因为我们要读取并不需要的元数据，也因为我们要为这棵被丢弃的子树跟踪大量（冲突）信息。
即使版本约束允许多个解，也存在关于 uv 应选择哪个解的预期。通常，理想的解优先为直接依赖而非间接依赖使用最高版本，避免回溯到非常旧的版本，并且能在目标机器上安装。
在内部，uv 把具有给定包名的每个包表示为一组虚拟包，例如为每个已激活的 extra、为依赖组，或为带有标记而各有一个包。PubGrub 需要为每个虚拟包选择版本，而 uv 的优先级工作在包名层面。
每当我们遇到对某个包的要求时，都会把它匹配到一个优先级。根包和 URL 要求优先级最高，其次是使用 == 运算符的单例要求（因为其版本可以直接确定），再次是高度冲突的包（见下一段），最后是所有其他包。每个类别内部，包按首次遇到的顺序排序，形成广度优先搜索，从而让直接依赖（包括工作区依赖）优先于传递依赖。
一个常见问题是：包 A 的优先级高于包 B，而 B 只与 A 的旧版本兼容。我们为包 A 确定了最新版本。每次我们为 B 确定版本时，它都会因与 A 冲突而立即被丢弃。我们必须尝试 B 的所有可能版本，直到穷尽可能的范围（慢）、选中一个不依赖 A 但很可能也不与项目兼容的非常旧的版本（糟），或无法构建某个非常旧的版本（糟）。一旦我们看到这种冲突发生五次，就会把 A 和 B 设为特殊的高冲突优先级，并设置成让 B 先于 A 被决定。然后我们手动回溯到决定 A 之前的状态，在下一次迭代中改为决定 B 而不是 A。更详细的描述和真实示例请参阅 #8157 和 #9843。