the output of uv lock can change merely by changing the order of requirements in pyproject.toml

[BurntSushi]

The easiest way to reproduce this is with a packse index running, as I discovered this bug with one of our existing scenarios.

Note that this bug exists on main, but the output below might be different. The output below was generated with PR #5163.

For context, this is the packse scenario we're testing below, named fork-marker-selection (the description is perhaps misleading now):

name = "fork-marker-selection"
description = '''
This tests a case where the resolver forks because of non-overlapping marker
expressions on `b`. In the original universal resolver implementation, this
resulted in multiple versions of `a` being unconditionally included in the lock
file. So this acts as a regression test to ensure that only one version of `a`
is selected.
'''

[resolver_options]
universal = true

[expected]
satisfiable = true

[root]
requires = [
  "a",
  "b>=2 ; sys_platform == 'linux'",
  "b<2 ; sys_platform == 'darwin'",
]

[packages.a.versions."1.0.0"]
[packages.a.versions."2.0.0"]
requires = ["b>=2.0.0"]

[packages.b.versions."1.0.0"]
[packages.b.versions."2.0.0"]

First, spin up a packse index:

$ uv run --all-extras packse serve scenarios/ --no-hash

In another shell, create this pyproject.toml:

[project]
name = 'project'
version = '0.1.0'
dependencies = [
  "fork-marker-selection-a",
  "fork-marker-selection-b>=2 ; sys_platform == 'linux'",
  "fork-marker-selection-b<2 ; sys_platform == 'darwin'",
]
requires-python = '>=3.8'

And now lock it, being careful to specify the index URL so that we use packse:

$ rm -f uv.lock

$ uv cache clean
Clearing cache at: /home/andrew/.cache/uv
Removed 14 files (9.8KiB)

$ UV_INDEX_URL=http://localhost:3141 uv lock -p3.8
warning: `uv lock` is experimental and may change without warning.
Using Python 3.8.19 interpreter at: /home/andrew/.local/share/uv/python/cpython-3.8.19-linux-x86_64-gnu/bin/python3
Resolved 4 packages in 193ms

The relevant part of the lock file are the top-level dependencies for project:

[[distribution]]
name = "fork-marker-selection-a"
version = "0.1.0"

[[distribution]]
name = "project"
version = "0.1.0"
source = { editable = "." }
dependencies = [
    { name = "fork-marker-selection-a", marker = "sys_platform == 'darwin' or sys_platform == 'linux'" },
    { name = "fork-marker-selection-b", version = "1.0.0", source = { registry = "http://localhost:3141/" }, marker = "sys_platform == 'darwin'" },
    { name = "fork-marker-selection-b", version = "2.0.0", source = { registry = "http://localhost:3141/" }, marker = "sys_platform == 'linux'" },
]

Now, flip the order of the b dependencies so that pyproject.toml looks like this:

[project]
name = 'project'
version = '0.1.0'
dependencies = [
  "fork-marker-selection-a",
  "fork-marker-selection-b<2 ; sys_platform == 'darwin'",
  "fork-marker-selection-b>=2 ; sys_platform == 'linux'",
]
requires-python = '>=3.8'

Repeat the exact same steps as before to lock it:

$ rm -f uv.lock

$ uv cache clean
Clearing cache at: /home/andrew/.cache/uv
Removed 14 files (9.8KiB)

$ UV_INDEX_URL=http://localhost:3141 uv lock -p3.8
warning: `uv lock` is experimental and may change without warning.
Using Python 3.8.19 interpreter at: /home/andrew/.local/share/uv/python/cpython-3.8.19-linux-x86_64-gnu/bin/python3
Resolved 5 packages in 219ms

(The different number of resolved packages is indeed some ominous foreshadowing here.)

And the relevant part of the lock file now looks like this:

[[distribution]]
name = "project"
version = "0.1.0"
source = { editable = "." }
dependencies = [
    { name = "fork-marker-selection-a", version = "0.1.0", source = { registry = "http://localhost:3141/" }, marker = "sys_platform == 'darwin'" },
    { name = "fork-marker-selection-a", version = "0.2.0", source = { registry = "http://localhost:3141/" }, marker = "sys_platform == 'linux'" },
    { name = "fork-marker-selection-b", version = "1.0.0", source = { registry = "http://localhost:3141/" }, marker = "sys_platform == 'darwin'" },
    { name = "fork-marker-selection-b", version = "2.0.0", source = { registry = "http://localhost:3141/" }, marker = "sys_platform == 'linux'" },
]

In the former case, it is almost correct, except a is conditional on the platform being linux or darwin. I believe instead the marker shouldn't even be there (or should evaluate to true for all marker environments). This is possibly a bug in my fix for incomplete markers and likely unrelated to this specific issue of the output changing based on the order of requirements. The main point of the former case is that we select one version that works across all platforms.

In the latter, we select two different versions of a, each depending on the platform. I believe this also suffers from a similar bug as the first case where a 0.1.0's marker should actually be sys_platform != 'linux', or more likely, a third choice reflecting the part of the universe not covered by the existing marker expressions, which would be sys_platform != 'linux' and sys_platform != 'darwin'. And again, I think this problem occurs because of an issue in my fix for incomplete markers. That's tracked by #5162.

But the output depending on the ordering of the requirements is, I believe, a different issue. I haven't fully diagnosed why this is occurring yet. (I believe @konstin predicted the occurrence of this bug.)

[charliermarsh]

In theory, it seems ok if the resolution differs based on the order of requirements...

[konstin]

Our package prioritization is order dependent, so there are examples where this happens without forking too, e.g. given:

• a has 1, 2
• b has 1, 2
• a 2 -> c==1
• b 2 -> c==2

dependencies = ["a", "b"] will resolve a 2, b 1, while
dependencies = ["b", "a"] will resolve b 2, a 1. Forks specifically we can improve the situation by prioritizing specific forks to increase the changes of getting a more minimal resolution (#4926).