跳到内容

解析器内部原理

提示

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

解析器

正如教科书中定义的那样，解析，或者从给定的一组需求中找到要安装的版本集合，等同于SAT 问题，因此是 NP 完全问题：在最坏的情况下，你必须尝试所有软件包的所有版本的所有可能组合，并且没有通用的快速算法。 在实践中，由于以下几个原因，这具有误导性

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

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

  • 从一个部分解决方案开始，该解决方案声明已选择哪些软件包版本，哪些软件包版本未确定。 最初，仅确定虚拟根软件包。
  • 从未确定的软件包中选择优先级最高的软件包。 粗略地说，具有 URL 的软件包（包括文件、git 等）具有最高的优先级，然后是具有更精确说明符（例如 ==）的软件包，然后是具有不太严格说明符的软件包。 在每个类别中，软件包按首次看到它们的时间排序（即文件中的顺序），使解析具有确定性。
  • 为选定的软件包选择一个版本。 该版本必须适用于部分解决方案中所有要求的说明符，并且不得先前标记为不兼容。 解析器更喜欢来自锁定文件 (uv.lock 或 -o requirements.txt) 以及当前环境中安装的版本。 版本从最高到最低检查（除非使用替代解析策略）。
  • 选定软件包版本的所有要求都会添加到未确定的软件包中。 uv 在后台预取其元数据以提高性能。
  • 除非检测到冲突，否则该过程会与下一个软件包重复，在这种情况下，解析器将回溯。 例如，部分解决方案包含 a 2，然后是带有要求 a 2 -> c 1 和 b 2 -> c 2 的 b 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 会写入锁定文件。 当执行新的解析时，使用锁定文件中的分支来确保解析的稳定性。 当需求更改时，可以将新的分支添加到保存的分支中。

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 要求的约束，例如，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 标签和标记之间没有 1:1 的映射，但我们可以为众所周知的平台（包括 Windows、Linux 和 macOS）进行映射。

Requires-python

为了确保可以为包含的 Python 版本实际安装 requires-python = ">=3.9" 的解析，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 要求具有最高优先级，然后是带有 == 运算符的单例要求，因为可以直接确定其版本，然后是高度冲突的软件包（下一段），最后是所有其他软件包。 在每个类别中，软件包按首次遇到它们的时间排序，从而创建一个广度优先搜索，该搜索优先考虑直接依赖项（包括工作区依赖项）而不是传递依赖项。

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