跳转至

解析器内部原理

Tip

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

解析器

正如教科书中所定义的，解析（即从给定的需求集合中找到一组要安装的版本）等同于SAT 问题，因此是 NP 完全问题：在最坏的情况下，你必须尝试所有包的所有版本的所有可能组合，而且不存在通用的快速算法。但在实际中，由于以下几个原因，这种说法具有误导性：

  • 在 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 中跟踪的不兼容性，构造一条错误消息来列举涉及的包。

提示

有关 PubGrub 算法的更多详细信息，请参阅 PubGrub 算法的内部原理。

除了 PubGrub 的基本算法外，我们还使用一种启发式方法，如果两个包冲突过多，则回溯并切换它们的顺序。

分支处理

从历史上看，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' 创建分支。

分支可以嵌套，例如，每个分支都依赖于之前出现的任何分支。具有相同软件包的分支会合并，以减少分支数量。

提示

在 uv lock -v 的日志中，通过查找 Splitting resolution on ...、Solving split ... (requires-python: ...) 和 Split ... resolution took ... 可以观察到分支处理情况。

分支解析器的一个难点在于，拆分发生的位置取决于软件包的查看顺序，而这又取决于偏好设置，例如来自 uv.lock 的设置。因此，解析器有可能使用特定分支解决需求并将其写入锁定文件，而当再次调用解析器时，由于偏好设置导致不同的分支点，会找到不同的解决方案。为避免这种情况，每个分支的 resolution-markers 以及分支间有差异的每个软件包都会写入锁定文件。执行新的解析时，会使用锁定文件中的分支来确保解析的稳定性。当需求发生变化时，新的分支可能会添加到已保存的分支中。

轮子标签

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

标记和 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 时，我们会分支到 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 应该选择哪种解决方案也有一定的预期。一般来说，理想的解决方案优先为直接依赖项使用比间接依赖项更高的版本，避免回溯到非常旧的版本，并且能够在目标机器上安装。

在内部，uv 将具有给定包名的每个包表示为多个虚拟包，例如，每个激活的额外功能、依赖组或带有标记的包各对应一个虚拟包。虽然 PubGrub 需要为每个虚拟包选择一个版本，但 uv 的优先级排序是在包名级别进行的。

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

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