跳转至

解析器内部原理

Tip

本文档重点介绍 uv 解析器的内部工作原理。有关 uv 的使用，请参阅解析概念文档。

解析器

根据教科书的定义，解析（resolution），即从一组给定的需求中找出一组要安装的版本，等同于SAT 问题，因此是 NP-complete 的：在最坏的情况下，你必须尝试所有包的所有版本的所有可能组合，并且没有通用的快速算法。在实践中，由于多种原因，这种说法具有误导性：

  • uv 解析中最慢的部分是加载包和版本元数据，即使它已被缓存。
  • 有许多可能的解决方案，但有些方案比其他方案更可取。例如，我们通常更喜欢使用最新版本的包。
  • 包依赖关系很复杂，例如，存在连续的版本范围——而不是任意的布尔版本包含/排除，相邻的版本通常具有相同或相似的需求等。
  • 对于大多数解析，解析器不需要回溯，迭代地选择版本就足够了。如果存在来自先前解析的版本偏好，则几乎不需要做任何工作。
  • 当解析失败时，需要的信息不仅仅是一条没有解决方案的消息（如在 SAT 求解器中看到的那样）。相反，解析器应该生成一个可理解的错误跟踪，说明哪些包参与其中，以便用户消除冲突。
  • 性能和用户体验最重要的启发式方法是通过优先级排序来确定做出决策的顺序。

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

  • 从一个部分解决方案开始，该方案声明了已选择哪些包版本以及哪些尚未确定。最初，只确定了一个虚拟的根包。
  • 从未确定的包中选择优先级最高的包。粗略地说，带有 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 使用了一个分叉解析器：每当一个包有多个带有不同标记 (marker) 的需求时，解析就会被拆分。

在上面的例子中，部分解决方案将被拆分为两个解析，一个用于 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 以及在分叉之间存在差异的每个包都会被写入锁文件。在执行新的解析时，会使用锁文件中的分叉来确保解析的稳定性。当需求发生变化时，新的分叉可能会被添加到已保存的分叉中。

Wheel 标签

虽然 uv 的解析在环境标记方面是通用的，但这并不扩展到 wheel 标签。Wheel 标签可以编码 Python 版本、Python 实现、操作系统和体系结构。例如，torch-2.4.0-cp312-cp312-manylinux2014_aarch64.whl 仅与 arm64 Linux 上的 CPython 3.12 兼容，且要求 glibc>=2.17（根据 manylinux2014 策略），而 tqdm-4.66.4-py3-none-any.whl 则适用于任何操作系统和体系结构上的所有 Python 3 版本和解释器。大多数项目都有一个通用的源码发行版，可以在尝试安装没有兼容 wheel 的包时使用，但有些包，如 torch，不发布源码发行版。在这种情况下，在例如 Python 3.13、不常见的操作系统或体系结构上安装将会失败，并提示没有匹配的 wheel。

标记和 wheel 标签过滤

在每个分叉中，我们都知道哪些标记是可能的。在非通用解析中，我们知道它们的确切值。在通用模式下，我们至少知道 python 需求的约束，例如，requires-python = ">=3.12" 意味着 importlib_metadata; python_version < "3.10" 可以被丢弃，因为它永远无法安装。如果另外设置了 tool.uv.environments，我们可以过滤掉与这些环境不相交的标记的需求。在每个分叉内部，我们还可以按分叉标记进行过滤。

标记表达式中存在一些冗余，其中一个标记字段的值暗示了另一个字段的值。在内部，我们将 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）进行映射。

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 标记不会传播到整个解析。

这个默认设置对于使用 CPython 版本相关 C API 的包（如 numpy）来说是个问题。每个 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"。这意味着当我们在一个 requires-python = ">=3.9" 的项目中解析 numpy>=2,<3 的需求时，我们会解析出 numpy 2.0.0，而锁文件无法在 Python 3.13 或更新版本上安装。为了缓解这个问题，每当我们因为 Python 需求过高而拒绝一个版本时，我们就会在该 Python 版本上进行分叉。此行为由 --fork-strategy 控制。在示例中，遇到 numpy 2.1.0 时，我们会分叉为 >=3.9,<3.10 和 >=3.10 两个 Python 版本，并解析出两个不同的 numpy 版本：

numpy==2.0.0; python_version >= "3.9" and python_version < "3.10"
numpy==2.1.0; python_version >= "3.10"

优先级排序

优先级排序对于性能和更好的解析结果都很重要。

如果我们尝试了很多版本，后来又不得不丢弃，解析就会很慢，这既是因为我们必须读取我们不需要的元数据，也是因为我们必须为这个被丢弃的子树跟踪大量的（冲突）信息。

即使版本约束允许多个解决方案，对于 uv 应该选择哪个解决方案也存在期望。通常，一个理想的解决方案会优先为直接依赖项使用最高版本，而不是间接依赖项，它会避免回溯到非常旧的版本，并且可以在目标机器上安装。

在内部，uv 将每个具有给定包名的包表示为多个虚拟包，例如，每个激活的 extra、每个依赖组或每个带有标记的包都有一个虚拟包。虽然 PubGrub 需要为每个虚拟包选择一个版本，但 uv 的优先级排序在包名级别上工作。

每当我们遇到对一个包的需求时，我们都会将其与一个优先级匹配。根包和 URL 需求具有最高优先级，其次是带有 == 运算符的单例需求，因为它们的版本可以直接确定，然后是高度冲突的包（下一段），最后是所有其他包。在每个类别中，包按首次遇到的顺序排序，创建一个广度优先搜索，优先处理直接依赖项（包括工作区依赖项）而不是传递依赖项。

一个常见的问题是，我们有一个包 A 的优先级高于包 B，而 B 只与 A 的旧版本兼容。我们为包 A 决定了最新版本。每次我们为 B 决定一个版本时，它都会因为与 A 的冲突而立即被丢弃。我们必须尝试 B 的所有可能版本，直到我们耗尽了可能的范围（慢），或者选择了一个不依赖于 A 的非常旧的版本，但很可能也与项目不兼容（坏），或者无法构建一个非常旧的版本（坏）。一旦我们看到这种冲突发生五次，我们就会将 A 和 B 设置为特殊的高度冲突优先级，并设置它们以便在 A 之前决定 B。然后我们手动回溯到决定 A 之前的状态，在下一次迭代中现在决定 B 而不是 A。有关更详细的描述和真实世界的示例，请参阅 #8157 和 #9843。