universal-lock: non-conflicting requirements with non-overlapping marker expressions provoke a fork

[BurntSushi]

Consider these requirements:

a >= 1 ; sys_platform == 'linux'
a < 2 ; sys_platform == 'darwin'

with a==1.0.0 and a==2.0.0 available in the registry.

(These are captured in this packse test.)

Even though the version constraints are non-conflicting, because the marker expressions are non-overlapping, this will actually provoke a fork in the universal resolver. The fork means that the a >= 1 requirement is free to choose, say, a==2.0.0 if it's available because the fork exists in isolation from the a < 2 requirement. However, if no fork were to happen, then both the a >= 1 and a < 2 requirements would be active simultaneously such that a==2.0.0 couldn't be chosen. So in this case, there exists a resolution without forking, but it is distinct from the resolution we get if we fork.

I think we could detect this case by looking at whether the version constraints themselves are conflicting. That is, if there exists an overlap in the version constraints, then we don't fork even if the marker expressions are non-overlapping. I think a decision like that would be predicated on the idea that it could be possible to find one resolution that works across multiple platforms. But it might not be possible. It feels like forking in this case, even if it isn't always necessary, results in more freedom for the resolver to find a resolution. But... maybe it's surprising to users in real cases.

I'm overall not quite sure what the right behavior is here. My sense of things right now is that this shouldn't block shipping, but I'm happy to have my mind changed on that!

Original discussion: #4339 (comment)

[BurntSushi]

For reference, if we run the corresponding packse scenario with uv, we get this lock file (current main is e264637b63b29b5e9a99ef9ac64594a8b827b611):

version = 1
requires-python = ">=3.12"

[[distribution]]
name = "fork-allows-non-conflicting-non-overlapping-dependencies"
version = "0.0.0"
source = "registry+http://localhost:3141/"
sdist = { url = "http://localhost:3141/packages/fork-allows-non-conflicting-non-overlapping-dependencies/fork_allows_non_conflicting_non_overlapping_dependencies-0.0.0.tar.gz#sha256=a715415043cafef783fd4d6d3adcbfb0e823663f9af3e2a6e73810da9269e472", hash = "sha256:a715415043cafef783fd4d6d3adcbfb0e823663f9af3e2a6e73810da9269e472" }

[[distribution.dependencies]]
name = "fork-allows-non-conflicting-non-overlapping-dependencies-a"
version = "1.0.0"
source = "registry+http://localhost:3141/"
marker = "sys_platform == 'darwin'"

[[distribution.dependencies]]
name = "fork-allows-non-conflicting-non-overlapping-dependencies-a"
version = "2.0.0"
source = "registry+http://localhost:3141/"
marker = "sys_platform == 'linux'"

[[distribution]]
name = "fork-allows-non-conflicting-non-overlapping-dependencies-a"
version = "1.0.0"
source = "registry+http://localhost:3141/"
sdist = { url = "http://localhost:3141/packages/fork-allows-non-conflicting-non-overlapping-dependencies/fork_allows_non_conflicting_non_overlapping_dependencies_a-1.0.0.tar.gz#sha256=dd40a6bd59fbeefbf9f4936aec3df6fb6017e57d334f85f482ae5dd03ae353b9", hash = "sha256:dd40a6bd59fbeefbf9f4936aec3df6fb6017e57d334f85f482ae5dd03ae353b9" }
wheels = [{ url = "http://localhost:3141/packages/fork-allows-non-conflicting-non-overlapping-dependencies/fork_allows_non_conflicting_non_overlapping_dependencies_a-1.0.0-py3-none-any.whl#sha256=37c13aa13cca009990929df08bed3d9de26e1d405a5ebd16ec0c3baef6899b23", hash = "sha256:37c13aa13cca009990929df08bed3d9de26e1d405a5ebd16ec0c3baef6899b23" }]

[[distribution]]
name = "fork-allows-non-conflicting-non-overlapping-dependencies-a"
version = "2.0.0"
source = "registry+http://localhost:3141/"
sdist = { url = "http://localhost:3141/packages/fork-allows-non-conflicting-non-overlapping-dependencies/fork_allows_non_conflicting_non_overlapping_dependencies_a-2.0.0.tar.gz#sha256=0b4ca63d060f4daa2269c08b7083f594e096b94e1bcbde53d212c65b52378358", hash = "sha256:0b4ca63d060f4daa2269c08b7083f594e096b94e1bcbde53d212c65b52378358" }
wheels = [{ url = "http://localhost:3141/packages/fork-allows-non-conflicting-non-overlapping-dependencies/fork_allows_non_conflicting_non_overlapping_dependencies_a-2.0.0-py3-none-any.whl#sha256=35168196ad80d0f2822191a47e3a805b4ad527280c8b84e7eed77b7fee505497", hash = "sha256:35168196ad80d0f2822191a47e3a805b4ad527280c8b84e7eed77b7fee505497" }]

[[distribution]]
name = "project"
version = "0.1.0"
source = "editable+."
sdist = { path = "." }

[[distribution.dependencies]]
name = "fork-allows-non-conflicting-non-overlapping-dependencies"
version = "0.0.0"
source = "registry+http://localhost:3141/"

And if we run it with poetry 1.8.2, we get this lock file:

# This file is automatically @generated by Poetry 1.8.2 and should not be changed by hand.

[[package]]
name = "fork-allows-non-conflicting-non-overlapping-dependencies"
version = "0.0.0"
description = "This test ensures that multiple non-conflicting but also non-overlapping dependency specifications with the same package name are allowed and supported.  At time of writing, this provokes a fork in the resolver, but it arguably shouldn't since the requirements themselves do not conflict with one another. However, this does impact resolution. Namely, it leaves the `a>=1` fork free to choose `a==2.0.0` since it behaves as if the `a<2` constraint doesn't exist."
optional = false
python-versions = ">=3.8"
files = [
    {file = "fork_allows_non_conflicting_non_overlapping_dependencies-0.0.0.tar.gz", hash = "sha256:a715415043cafef783fd4d6d3adcbfb0e823663f9af3e2a6e73810da9269e472"},
]

[package.dependencies]
fork-allows-non-conflicting-non-overlapping-dependencies-a = [
    {version = "<2", markers = "sys_platform == \"darwin\""},
    {version = ">=1", markers = "sys_platform == \"linux\""},
]

[package.source]
type = "legacy"
url = "http://localhost:3141"
reference = "packse"

[[package]]
name = "fork-allows-non-conflicting-non-overlapping-dependencies-a"
version = "1.0.0"
description = ""
optional = false
python-versions = ">=3.8"
files = [
    {file = "fork_allows_non_conflicting_non_overlapping_dependencies_a-1.0.0-py3-none-any.whl", hash = "sha256:37c13aa13cca009990929df08bed3d9de26e1d405a5ebd16ec0c3baef6899b23"},
    {file = "fork_allows_non_conflicting_non_overlapping_dependencies_a-1.0.0.tar.gz", hash = "sha256:dd40a6bd59fbeefbf9f4936aec3df6fb6017e57d334f85f482ae5dd03ae353b9"},
]

[package.source]
type = "legacy"
url = "http://localhost:3141"
reference = "packse"

[[package]]
name = "fork-allows-non-conflicting-non-overlapping-dependencies-a"
version = "2.0.0"
description = ""
optional = false
python-versions = ">=3.8"
files = [
    {file = "fork_allows_non_conflicting_non_overlapping_dependencies_a-2.0.0-py3-none-any.whl", hash = "sha256:35168196ad80d0f2822191a47e3a805b4ad527280c8b84e7eed77b7fee505497"},
    {file = "fork_allows_non_conflicting_non_overlapping_dependencies_a-2.0.0.tar.gz", hash = "sha256:0b4ca63d060f4daa2269c08b7083f594e096b94e1bcbde53d212c65b52378358"},
]

[package.source]
type = "legacy"
url = "http://localhost:3141"
reference = "packse"

[metadata]
lock-version = "2.0"
python-versions = "^3.11"
content-hash = "fa3f7ba6b95fa7787a5a362f6373095804b9e6ab1ce0a4608ebd5adb23d36999"

So here, it seems like both poetry and uv are forking since both a==1.0.0 and a==2.0.0 show up in the lock file.

But notice what happens if we try the packse test fork-allows-non-conflicting-repeated-dependencies. It looks a lot like the one above, but both requirements are unconditional so no forking happens:

a >= 1
a < 2

So locking with uv gets us:

version = 1
requires-python = ">=3.12"

[[distribution]]
name = "fork-allows-non-conflicting-repeated-dependencies"
version = "0.0.0"
source = "registry+http://localhost:3141/"
sdist = { url = "http://localhost:3141/packages/fork-allows-non-conflicting-repeated-dependencies/fork_allows_non_conflicting_repeated_dependencies-0.0.0.tar.gz#sha256=f71a547328d8616fddcc6ac173a242690d754e0d42427edd7d1f4df34b41d073", hash = "sha256:f71a547328d8616fddcc6ac173a242690d754e0d42427edd7d1f4df34b41d073" }

[[distribution.dependencies]]
name = "fork-allows-non-conflicting-repeated-dependencies-a"
version = "1.0.0"
source = "registry+http://localhost:3141/"

[[distribution]]
name = "fork-allows-non-conflicting-repeated-dependencies-a"
version = "1.0.0"
source = "registry+http://localhost:3141/"
sdist = { url = "http://localhost:3141/packages/fork-allows-non-conflicting-repeated-dependencies/fork_allows_non_conflicting_repeated_dependencies_a-1.0.0.tar.gz#sha256=45ca30f1f66eaf6790198fad279b6448719092f2128f23b99f2ede0d6dde613b", hash = "sha256:45ca30f1f66eaf6790198fad279b6448719092f2128f23b99f2ede0d6dde613b" }
wheels = [{ url = "http://localhost:3141/packages/fork-allows-non-conflicting-repeated-dependencies/fork_allows_non_conflicting_repeated_dependencies_a-1.0.0-py3-none-any.whl#sha256=b08be7896afa7402a2650dd9ebf38e32cf65d5bf86956dc23cf793c5f1f21af2", hash = "sha256:b08be7896afa7402a2650dd9ebf38e32cf65d5bf86956dc23cf793c5f1f21af2" }]

[[distribution]]
name = "project"
version = "0.1.0"
source = "editable+."
sdist = { path = "." }

[[distribution.dependencies]]
name = "fork-allows-non-conflicting-repeated-dependencies"
version = "0.0.0"
source = "registry+http://localhost:3141/"

And locking with poetry gets us:

# This file is automatically @generated by Poetry 1.8.2 and should not be changed by hand.

[[package]]
name = "fork-allows-non-conflicting-repeated-dependencies"
version = "0.0.0"
description = "This test ensures that multiple non-conflicting dependency specifications with the same package name are allowed and supported.  This test exists because the universal resolver forks itself based on duplicate dependency specifications by looking at package name. So at first glance, a case like this could perhaps cause an errant fork. While it's difficult to test for \"does not create a fork\" (at time of writing, the implementation does not fork), we can at least check that this case is handled correctly without issue. Namely, forking should only occur when there are duplicate dependency specifications with disjoint marker expressions."
optional = false
python-versions = ">=3.8"
files = [
    {file = "fork_allows_non_conflicting_repeated_dependencies-0.0.0.tar.gz", hash = "sha256:f71a547328d8616fddcc6ac173a242690d754e0d42427edd7d1f4df34b41d073"},
]

[package.dependencies]
fork-allows-non-conflicting-repeated-dependencies-a = ">=1,<2"

[package.source]
type = "legacy"
url = "http://localhost:3141"
reference = "packse"

[[package]]
name = "fork-allows-non-conflicting-repeated-dependencies-a"
version = "1.0.0"
description = ""
optional = false
python-versions = ">=3.8"
files = [
    {file = "fork_allows_non_conflicting_repeated_dependencies_a-1.0.0-py3-none-any.whl", hash = "sha256:b08be7896afa7402a2650dd9ebf38e32cf65d5bf86956dc23cf793c5f1f21af2"},
    {file = "fork_allows_non_conflicting_repeated_dependencies_a-1.0.0.tar.gz", hash = "sha256:45ca30f1f66eaf6790198fad279b6448719092f2128f23b99f2ede0d6dde613b"},
]

[package.source]
type = "legacy"
url = "http://localhost:3141"
reference = "packse"

[metadata]
lock-version = "2.0"
python-versions = "^3.11"
content-hash = "8b88e3e9187c6b396033abe10456761aceb0847dcdb391fd7a2cf091ab6a5bfb"

So both tools behave the same on this example too. No forking happens, and as a result, a==2.0.0 is completely excluded from the lock file.

[konstin]

This has been fixed by #4662: We fork, but since we use the resolution of the first fork as preference for the next fork, we end up with only a==1.0.0