解析器内部机制

Resolver

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

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

uv 使用 pubgrub-rs，这是 Rust 实现的 PubGrub，一种增量式版本求解器。在 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的基础算法外，我们还采用了一种启发式方法：当两个包频繁发生冲突时，会进行回溯并调整它们的优先级顺序。

Forking

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的配置。因此，解析器可能会用特定的分叉来满足需求，并将其写入锁文件，当再次调用解析器时，由于偏好导致不同的分叉点，可能会找到不同的解决方案。为了避免这种情况，每个分叉以及分叉间产生分歧的每个包的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。

标记和滚轮标签过滤

在每一个分支中，我们知道哪些标记是可能的。在非通用解析中，我们知道它们的确切值。在通用模式下，我们至少知道一个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）且该版本不提供对Windows、Linux和macOS的支持时，如果存在不带标签的基础版本（例如1.2.3）能支持缺失的平台，我们会尝试通过根据平台选择使用带本地标签或不带本地标签的版本来扩展平台支持。这有助于处理那些为不同硬件加速器（如torch）使用本地标签的软件包。虽然wheel标签与标记之间不存在1:1的映射关系，但我们可以为常见平台（包括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，声明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将每个具有给定包名称的包表示为多个虚拟包，例如，每个激活的额外功能、依赖组或具有标记的包都会对应一个虚拟包。虽然PubGrub需要为每个虚拟包选择版本，但uv的优先级排序是在包名称级别上进行的。

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

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