跳转至

解析器内部原理

Tip

本文档主要讲解 uv 解析器的内部工作原理。有关 uv 的使用，请参阅 解析概念 文档。

解析器

根据教科书的定义，解析或从给定的一组需求中找到要安装的版本集，相当于 SAT 问题，因此是 NP 完全问题： 在最坏的情况下，你必须尝试所有可能的版本组合，并且没有通用的、快速的算法。实际上，这种说法有很多误导之处，原因如下：

  • uv 解析中最慢的部分是加载包和版本的元数据，即使这些元数据已经被缓存。
  • 存在许多可能的解决方案，但其中一些方案比其他方案更优。例如，我们通常偏好使用最新版本的包。
  • 包依赖关系非常复杂，例如，存在连续的版本范围——并不是任意的布尔包含/排除版本，相邻的发布版本通常有相同或相似的需求等。
  • 对于大多数解析，解析器不需要回溯，逐步选择版本就足够了。如果之前的解析中有版本偏好，几乎不需要做任何工作。
  • 当解析失败时，所需的信息比 SAT 求解器中的“没有解决方案”的消息更多。解析器应该提供一条可理解的错误跟踪，明确指出哪些包涉及到冲突，从而允许用户解决冲突。

uv 使用 pubgrub-rs，这是 PubGrub 的 Rust 实现，是一个增量版本求解器。PubGrub 在 uv 中的工作步骤如下：

  • 从一个部分解决方案开始，声明哪些包的版本已被选定，哪些版本尚未决定。最初，只有一个虚拟的根包被确定。
  • 从未决定的包中选择优先级最高的包。带有 URL（包括文件、git 等）的包优先级最高，然后是那些带有更精确的版本说明符（如 ==）的包，再然后是那些带有较宽松说明符的包。在每个类别内部，包按首次出现的顺序排序（即文件中的顺序），使解析具有确定性。
  • 为选定的包选择一个版本。该版本必须与部分解决方案中的所有需求说明符兼容，并且不能被标记为不兼容。解析器优先使用来自锁文件（uv.lock 或 -o requirements.txt）的版本，以及当前环境中已安装的版本。版本会从最高到最低检查（除非使用了其他 解析策略）。
  • 选定包版本的所有需求会被加入到未决定的包中。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 中跟踪的不兼容项，会构建一条错误消息，列出相关的包。

Tip

要了解更多关于 PubGrub 算法的细节，请参阅 PubGrub 算法的内部实现。

分叉(Forking)

Python 解析器历史上不支持回溯，即便有回溯功能，解析通常也仅限于单一环境，一个特定的架构、操作系统、Python 版本和 Python 实现。一些包对于不同环境使用了相互矛盾的要求，例如：

numpy>=2,<3 ; python_version >= "3.11"
numpy>=1.16,<2 ; python_version < "3.11"

由于 Python 只允许每个包使用一个版本，一个简单的解析器在这里会出错。受到 Poetry 启发，uv 使用了分叉解析器：每当包有多个带有不同标记的要求时，解析会被分割。

在上面的例子中，部分解决方案将分成两个解析，一个用于 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' 分别创建一个分叉。

分叉可以是嵌套的，即每个分叉都依赖于任何先前发生的分叉。具有相同包的分叉会合并，以保持分叉数量较少。

Tip

可以通过查看 uv lock -v 日志中的 Splitting resolution on ...、Solving split ... (requires-python: ...) 和 Split ... resolution took ... 来观察分叉。

分叉解析器的一个难点是，分叉发生的位置依赖于包的出现顺序，而包的出现顺序又依赖于优先级，例如来自 uv.lock 的优先级。因此，解析器可能会根据特定的分叉解决需求，写入锁文件，当解析器再次被调用时，可能会找到不同的解决方案，因为优先级导致分叉点不同。为了避免这种情况，锁文件中会记录每个分叉的 resolution-markers 和每个在分叉间出现差异的包。进行新的解析时，会使用锁文件中的分叉信息来确保解析稳定。当需求发生变化时，可能会向已保存的分叉中添加新的分叉。

Requires-python

为了确保 requires-python = ">=3.9" 的解析能够在所包含的 Python 版本上正确安装，uv 要求所有依赖项有相同的最低 Python 版本。声明了更高最低 Python 版本的包版本，例如 requires-python = ">=3.10"，会被拒绝，因为该版本无法在 Python 3.9 上安装。为了简化和向前兼容，requires-python 中只会尊重下限。例如，如果一个包声明 requires-python = ">=3.8,<4"，则 <4 标记不会传播到整个解析过程中。

Wheel 标签

虽然 uv 的解析对于环境标记是通用的，但这并不扩展到轮子标签（wheel tags）。轮子标签可以编码 Python 版本、Python 实现、操作系统和架构。例如，torch-2.4.0-cp312-cp312-manylinux2014_aarch64.whl 仅与具有 glibc>=2.17 的 arm64 Linux 上的 CPython 3.12 兼容，而 tqdm-4.66.4-py3-none-any.whl 与所有 Python 3 版本和任何操作系统、架构兼容。大多数项目都有一个通用的源分发包，可以在安装没有兼容轮子的包时使用，但一些包，如 torch，并不发布源分发包。在这种情况下，例如在 Python 3.13、非主流操作系统或架构上进行安装时，将失败并报告没有匹配的轮子。