跳到内容

解析器内部原理

提示

本文档重点介绍 uv 解析器的内部工作原理。若需了解 uv 的使用方法，请参阅解析概念文档。

解析器

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

  • uv 解析中最耗时的部分是加载包和版本的元数据，即使这些数据已被缓存。
  • 虽然存在许多可能的解决方案，但有些方案优于其他方案。例如，我们通常倾向于使用包的最新版本。
  • 包的依赖关系很复杂，例如存在连续的版本范围（而非任意布尔包含/排除），相邻的发行版通常具有相同或相似的需求等。
  • 对于大多数解析任务，解析器不需要回溯，迭代地选择版本即已足够。如果之前已有解析产生的版本偏好，则几乎不需要进行额外工作。
  • 当解析失败时，仅仅返回“无解”的消息（如同 SAT 求解器那样）是不够的，还需要提供更多信息。解析器应当生成易于理解的错误追踪信息，说明涉及哪些包，以便用户能够解决冲突。
  • 性能和用户体验最重要的启发式方法是通过优先级排序来确定决策顺序。

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

  • 从部分解（partial solution）开始，声明哪些包的版本已被选中，哪些尚不确定。最初，仅确定一个虚拟的根包。
  • 从待定包中选择优先级最高的包。大致而言，带有 URL（包括 file、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 的基础算法外，我们还使用一种启发式方法：如果两个包冲突过于频繁，解析器会回溯并切换它们的处理顺序。

分叉（Forking）

Python 解析器历史上不支持回溯。即使支持回溯，解析通常也仅限于单一环境（特定的架构、操作系统、Python 版本和 Python 实现）。某些包针对不同环境使用矛盾的需求，例如：

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

由于 Python 只允许每个包存在一个版本，简单的解析器会报错。受 Poetry 的启发，uv 使用分叉解析器：每当一个包针对不同的标记（markers）有多个需求时，解析就会分叉。

在上述示例中，部分解将拆分为两个解析过程：一个针对 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 的 CPython 3.12（根据 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 标签和标记之间没有 1:1 的映射，但我们可以为知名平台（包括 Windows、Linux 和 macOS）进行映射。

元数据一致性

与 Poetry 类似，uv 要求特定索引中同一包的单一版本的所有 Wheel 必须具有相同的依赖项（METADATA 中的 Requires-Dist），包括从源代码发行版构建的 Wheel。更通俗地说，uv 假设每个 Wheel 在其 dist-info 目录中都有相同的 METADATA 文件。

以 numpy 2.3.2 为例，它有 73 个 Wheel。如果没有这个假设，uv 为了获取元数据将不得不发起 73 次网络请求，而不是一次。没有元数据一致性的另一个问题是标记与 Wheel 标签之间缺乏 1:1 的映射。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 中，依赖项可以是注册表依赖、带有版本说明符的包、纯包名，或者是 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 将每个具有给定包名的包表示为多个虚拟包，例如，为每个激活的额外功能、依赖组或标记设置一个包。虽然 PubGrub 需要为每个虚拟包选择版本，但 uv 的优先级排序是在包名级别上进行的。

每当我们遇到对某个包的需求时，就会为其匹配一个优先级。根包和 URL 需求具有最高优先级，其次是带有 == 运算符的单例需求（因为其版本可以直接确定），接着是高冲突包（下一段详述），最后是所有其他包。在每个类别内部，包按首次遇到的顺序排序，这创建了一种优先考虑直接依赖（包括工作空间依赖）而非传递依赖的广度优先搜索。

一个常见问题是：包 A 的优先级高于包 B，而 B 仅与 A 的旧版本兼容。我们确定了 A 的最新版本。每次我们为 B 确定版本时，它都会因与 A 的冲突而立即被丢弃。我们必须尝试 B 的所有可能版本，直到耗尽所有可能范围（速度慢）、选择一个不依赖 A 但很可能也不兼容项目的非常旧版本（糟糕），或者构建旧版本失败（糟糕）。一旦我们看到这种冲突发生五次，我们就将 A 和 B 设置为特殊的“高冲突”优先级级别，并设置使得 B 在 A 之前被决定。在下一次迭代中，我们会手动回溯到决定 A 之前的状态，改而先决定 B。参见 #8157 和 #9843 以获取包含实际案例的更详细说明。