跳转至

解析器内部机制

Tip

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

解析器

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

  • uv 解析过程中最慢的部分是加载包和版本元数据，即使这些元数据已被缓存。
  • 存在许多可能的解，但某些解优于其他解。例如，我们通常倾向于使用包的最新版本。
  • 包的依赖关系是复杂的，例如，存在连续的版本范围——而非任意的布尔包含/排除关系，相邻版本通常具有相同或相似的需求，等等。
  • 对于大多数解析过程，解析器不需要回溯，逐版本迭代选择就已足够。如果存在来自先前解析的版本偏好，几乎不需要做任何额外工作。
  • 当解析失败时，需要的不仅仅是"无解"这样的消息（如 SAT 求解器所示）。相反，解析器应生成可理解的错误追踪，说明涉及哪些包，以便用户能够消除冲突。
  • 对于性能和用户体验而言，最重要的启发式方法是：通过优先级排序来决定决策顺序。

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

  • 从一个部分解（partial solution）开始，该部分解声明了哪些包版本已被选定，哪些尚未确定。最初，只有一个虚拟根包被确定。
  • 从尚未确定的包中选择优先级最高的包。大致来说，带有 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 算法内部机制。

除了 PubGrub 的基础算法之外，我们还使用了一种启发式方法：如果两个包冲突过于频繁，则回溯并交换它们的顺序。

分叉

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 上使用 glibc>=2.17（根据 manylinux2014 策略）的 CPython 3.12 兼容，而 tqdm-4.66.4-py3-none-any.whl 适用于所有 Python 3 版本和解释器，在任何操作系统和架构上都能工作。大多数项目都有一个通用兼容的源代码分发包（source distribution），当尝试安装没有兼容 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 的已知值规范化为共享的规范表示，以便它们可以相互匹配。

当我们选择了一个带有本地标签（local tag）的版本（例如 1.2.3+localtag）且其 wheel 不覆盖 Windows、Linux 和 macOS 的支持，而存在一个不带标签的基础版本（例如 1.2.3）支持缺失的平台时，我们会进行分叉，尝试通过根据平台同时使用带本地标签和不带本地标签的版本来扩展平台支持。这对于使用本地标签区分不同硬件加速器（如 torch）的包很有帮助。虽然 wheel 标签和标记之间没有一对一的映射关系，但我们可以对已知平台（包括 Windows、Linux 和 macOS）进行映射。

元数据一致性

uv 与 poetry 类似，要求特定索引中包的单个版本的所有 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 中，依赖可以是注册表依赖（registry dependency），即带有版本指定符或纯包名的包，也可以是 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 的依赖，而 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。