Overlapping variant markers are incompatible with universal resolution

[konstin]

Poetry, pdm (https://pdm-project.org/latest/usage/lock-targets/) and uv (https://docs.astral.sh/uv/reference/resolver-internals/) perform a universal resolution that works on all platforms. This is in contrast to pip, which only resolves for the current platform.

pip evaluates the markers on the requirements and ignores all that don't match the current platform. Universal resolution requires that for each (supported) possible set of markers, we can determine the subset of packages from the lockfile to install. Python packages or dependency trees can has incompatible requirements, as long they are for different markers. There's a more detailed explanation in https://docs.astral.sh/uv/reference/resolver-internals/, the short version is that we have to split the resolution into two if there are conflicting markers.

[project]
name = "myproject"
requires-python = ">=3.9"
dependencies = [
    "numpy<1.25; python_version < '3.10'",
    "numpy>=1.25; python_version >= '3.10'",
    "pandas"
]

[project]
name = "myproject"
requires-python = ">=3.9"
dependencies = [
    "numpy<1.25; sys_platform == 'linux'",
    "numpy>=1.25; sys_platform == 'darwin'",
    "pandas"
]

In the first case above, we do one resolution for python_version < '3.10' and one for python_version >= '3.10', resolving different numpy versions. In the second case, we perform one resolution for linux, one for darwin and one for not(linux or darwin). (You can run both of these examples with uv. The real forks are more complex, but the lockfile still shows the different version and their disjoint platform markers). In each of these so-called forks, there is only one version of a package. Forks don't overlap and all forks together are a universal resolution. We ensure those two properties so that at install time, we only need to determine the current environment and get a consistent set of packages to install.

Now consider the following requirements specification:

Requires-Dist: nvidia-cublas==12.6.4.1; platform_system == "Linux" and platform_machine == "x86_64" and "nvidia :: ctk :: 12.6" in variant_properties
Requires-Dist: nvidia-cublas==12.8.4.1; platform_system == "Linux" and platform_machine == "x86_64" and "nvidia :: ctk :: 12.8" in variant_properties
Requires-Dist: nvidia-cublas==12.9.1.4; platform_system == "Linux" and platform_machine == "x86_64" and "nvidia :: ctk :: 12.9" in variant_properties

If we try to perform a universal resolution, we run into a conflict between nvidia-cublas==12.6.4.1 and nvidia-cublas==12.8.4.1, since "nvidia :: ctk :: 12.6" in variant_properties and "nvidia :: ctk :: 12.8" in variant_properties is a reasonable environment in the eyes of a resolver. With our knowledge about the nvidia provider, we know that those markers are disjoint and there is no conflict.

There are different general strategies we could apply: One is that a resolver needs to allow overlapping forks and ensure at install time, that there is no overlap. The other is that a provider needs to communicate that markers are disjoint, e.g. it could state in variants.json that nvidia :: ctk always only has a single value. The third would be that neither of them changes and we push the problem down to users, so that users have to avoid conflicting versions or write something like:

Requires-Dist: nvidia-cublas==12.6.4.1; "nvidia :: ctk :: 12.6"     in variant_properties and "nvidia :: ctk :: 12.8" not in variant_properties and "nvidia :: ctk :: 12.9" not in variant_properties
Requires-Dist: nvidia-cublas==12.8.4.1; "nvidia :: ctk :: 12.6" not in variant_properties and "nvidia :: ctk :: 12.8"     in variant_properties and "nvidia :: ctk :: 12.9" not in variant_properties
Requires-Dist: nvidia-cublas==12.9.1.4; "nvidia :: ctk :: 12.6" not in variant_properties and "nvidia :: ctk :: 12.8" not in variant_properties and "nvidia :: ctk :: 12.9"     in variant_properties

A fourth, rather narrow optiona is to add more syntax:

Requires-Dist: nvidia-cublas==12.6.4.1; ["nvidia :: ctk :: 12.6"] == variant_properties
Requires-Dist: nvidia-cublas==12.8.4.1; ["nvidia :: ctk :: 12.8"] == variant_properties
Requires-Dist: nvidia-cublas==12.9.1.4; ["nvidia :: ctk :: 12.9"] == variant_properties

[mgorny]

Thanks for the detailed explanation.

Just a quick question for a start: do I understand correctly that even if we restored the restriction that each feature can have only one value, the more general problem would remain (though perhaps it'd be less likely to actually happen)?

I suppose this can also happen e.g. when using extras.

One is that a resolver needs to allow overlapping forks and ensure at install time, that there is no overlap.

Perhaps I'm missing something but doesn't that basically mean you'd just "lock" the valid environment marker combinations, and store a list of invalid combinations that are rejected at install time? That doesn't sound hard, though obviously it implies you can't validate up front that all combinations are installable, and with multiple values there could be quite a lot of combinations to consider.

The other is that a provider needs to communicate that markers are disjoint, e.g. it could state in variants.json that nvidia :: ctk always only has a single value.

I wouldn't go that way. We'd be creating a non-obvious corner case.

The third would be that neither of them changes and we push the problem down to users, so that users have to avoid conflicting versions or write something like […]

Likewise, it's non-obvious and hard on top of that.

[rgommers]

For anyone looking at the concrete example: they're about nvidia-cublas on https://variants-index.wheelnext.dev/. On PyPI, these requirements should map to nvidia-cublas-cu12, which has all the versions used above. https://pypi.org/project/nvidia-cublas is an empty dummy package at the moment.

Question: "nvidia :: ctk doesn't seem to exist in any branch of https://github.com/wheelnext/nvidia-variant-provider. Is the example above actually how we're expecting packages to depend on different cublas versions?

The current version of the variant properties spec is useful to look at; it explicitly states that a feature can have multiple values.

One is that a resolver needs to allow overlapping forks and ensure at install time, that there is no overlap. The other is that a provider needs to communicate that markers are disjoint, e.g. it could state in variants.json that nvidia :: ctk always only has a single value.

I think these are the main two choices to consider; pushing it down to the user or adding specific doesn't feel right. The first option (check for no overlap at install time) seems a bit more appealing, however I find it hard to judge without seeing the actual pyproject.toml content that we're expecting package authors to write. It feels like that is still quite cumbersome and not using the design we're creating here very well. In any other distro, the goal will be to depend on nvidia-cublas; cuda in system_features and let the "variant infrastructure" take care of picking matching versions of cuda toolkit components.

[konstin]

Just a quick question for a start: do I understand correctly that even if we restored the restriction that each feature can have only one value, the more general problem would remain (though perhaps it'd be less likely to actually happen)?

If we were to restrict both provider and package to one property per feature, this would go away, but I suspect we'd move the problem from the property to the feature level for more complex use cases.

I suppose this can also happen e.g. when using extras.

We haven't seen this with packages, I assume authors test installing all extras together.

One is that a resolver needs to allow overlapping forks and ensure at install time, that there is no overlap.

Perhaps I'm missing something but doesn't that basically mean you'd just "lock" the valid environment marker combinations, and store a list of invalid combinations that are rejected at install time? That doesn't sound hard, though obviously it implies you can't validate up front that all combinations are installable, and with multiple values there could be quite a lot of combinations to consider.

Unfortunately it's hard to implement 😅 Marker algebra and determining forks is complex, and this would add an extra layer of filtering markers, determining forks and change the lockfile format to accommodate overlaps and the the assumptions we made.

[mgorny]

We haven't seen this with packages, I assume authors test installing all extras together.

Yeah, I mean technically the following is valid and triggers the problem, is that correct?

numpy < 2; "old-numpy" in extras
numpy >= 2; "numpy" in extras

[konstin]

Yes, this fails to lock, too. I haven't seen any reports of that from users, probably because pip install ".[old-numpy,numpy]" already fails.

[mgorny]

Hmm, now I'm slightly confused. So uv doesn't resolve such a dependency specification the same way (i.e. considering all possible extra combinations) that it does variant properties?

[konstin]

If you try to lock this, you get an error:

[project]
name = "debug"
version = "1.0.0"
requires-python = ">=3.9"

[project.optional-dependencies]
old-numpy = ["numpy < 2"]
numpy = ["numpy >= 2"]

$ uv lock
  × No solution found when resolving dependencies for split (python_full_version >= '3.12' and sys_platform == 'linux'):
  ╰─▶ Because debug[old-numpy] depends on numpy<2 and debug[numpy] depends on numpy>=2, we can conclude that debug[numpy] and
      debug[old-numpy] are incompatible.
      And because your project requires debug[numpy] and debug[old-numpy], we can conclude that your project's requirements are
      unsatisfiable.

[zanieb]

We do allow you to declare those as conflicting explicitly though, to force the resolver to solve both separately and ban installing them at the same time; see https://docs.astral.sh/uv/concepts/resolution/#conflicting-dependencies

We don't solve for all possible extra combinations to avoid combinatorial explosion, rather we solve for them all together then use explicit conflict declaration to expand the combinations we need to resolve.

[rgommers]

Question: "nvidia :: ctk doesn't seem to exist in any branch of https://github.com/wheelnext/nvidia-variant-provider. Is the example above actually how we're expecting packages to depend on different cublas versions?

So now that we have draft docs for nvidia-variant-provider and a torch-2.8 config available, the answer (for now) is that :: ctk is gone and what is used is cuda_version_lower_bound. From this config file we see that the current workaround is the third option @konstin gave in the issue description:

    'nvidia-cublas==12.6.4.1; platform_system == "Linux" and platform_machine == "x86_64" and "nvidia :: cuda_version_lower_bound :: 12.6" in variant_properties and "nvidia :: cuda_version_lower_bound :: 12.8" not in variant_properties and "nvidia :: cuda_version_lower_bound :: 12.9" not in variant_properties',
    'nvidia-cublas==12.8.4.1; platform_system == "Linux" and platform_machine == "x86_64" and "nvidia :: cuda_version_lower_bound :: 12.6" not in variant_properties and "nvidia :: cuda_version_lower_bound :: 12.8" in variant_properties and "nvidia :: cuda_version_lower_bound :: 12.9" not in variant_properties',
    'nvidia-cublas==12.9.1.4; platform_system == "Linux" and platform_machine == "x86_64" and "nvidia :: cuda_version_lower_bound :: 12.6" not in variant_properties and "nvidia :: cuda_version_lower_bound :: 12.8" not in variant_properties and "nvidia :: cuda_version_lower_bound :: 12.9" in variant_properties',

It's pretty clear that the more variants one adds, the harder and more error-prone this gets. It also reminds me of the problem with ensuring markers are orthogonal in https://github.com/scipy/oldest-supported-numpy/blob/main/setup.cfg - it's really tricky to write that by hand and then verify that you don't have cases with 0 or >2 solutions, but always 1 for every platform/interpreter combo.

---

So for the four options on the table we are at:

1. Resolver needs to allow overlapping forks. Discussion above concludes that this places a lot of extra implementation complexity on the resolver.
2. Provider needs to communicate that markers are disjoint. Can't do this because the markers aren't disjoint according to the provider's rules (it's _lower_bound, not _equal). EDIT: see below
3. Push the problem down to users. Hard to write and error-prone, see the first half of this comment.
4. Add more syntax. No one is super enthusiastic about this one, but it's easier than option (3).

---

That said, I think that we misunderstood the problem, because of gh-65. This works and is unambiguous (leaving out the platform_system == "Linux" and platform_machine == "x86_64" from each line for clarity):

    'nvidia-cublas==12.6.4.1; "nvidia :: cuda_version_lower_bound :: 12.6" in variant_properties',
    'nvidia-cublas==12.8.4.1; "nvidia :: cuda_version_lower_bound :: 12.8" in variant_properties',
    'nvidia-cublas==12.9.1.4; "nvidia :: cuda_version_lower_bound :: 12.9" in variant_properties',

This is because the discussion in gh-65 clarified that variant_properties are those of the variant wheel itself. And those contain exactly one value for cuda_version_lower_bound, e.g.:

    "variants": {
        "00000000": {},
        "cu126": {
            "nvidia": {
                "cuda_version_lower_bound": [
                    "12.6"
                ],
                "sm_arch": [
                    "50_real",
                    "60_real",
                    "70_real",
                    "75_real",
                    "80_real",
                    "86_real",
                    "90_real"
                ]
            }
        },
        "cu128": {

So can we conclude that the installer should read variant.json in the wheel (or from variants.json served by the index server), and then can decide on markers overlapping yes or no?

[rgommers]

So can we conclude that the installer should read variant.json in the wheel (or from variants.json served by the index server), and then can decide on markers overlapping yes or no?

I should have put this sentence in a separate comment I think. @konstin do you agree that there's no problem here anymore now that we clarified that variant markers refer to wheel metadata?

[konstin]

I'm not sure that's sufficient, I'm still working through some problems we see in uv's universal resolver, for example when two packages with variant markers depend on the same package. I'd keep this open until we have at least some more examples and implementations to confirm whether or not the current design is sufficient on the package maintainer side and implementable on the tooling side.

[rgommers]

👍🏼 SGTM to leave it open for now, thanks

[mgorny]

I was thinking more about the potential for the other use case, i.e. markers that would correspond to the supported properties as grabbed from the plugin for the current environment. While technically it's an interesting use case, I think implementation would face a significant problem: we'd have to query the provider plugins every time we evaluate the dependencies, including on installed packages. So literally pip check would have to create new isolated environments, install provider plugins and run them to evaluate the markers.

It would also imply that changing provider output could result in broken dependencies. Say, a package has an optional CUDA support with a dep like:

mypackage-cuda ; "nvidia :: cuda_version_lower_bound" in variant_features

If you don't have CUDA when installing this package, you don't install mypackage-cuda. But if you install CUDA afterwards, the dependency strings would assume mypackage-cuda should already be installed — though it isn't.

[mgorny]

Though thinking about it even more, I suppose we could come up with something that works reasonably. A potential use case would be JAX, that currently uses e.g. jax[cuda12] to pull in the CUDA plugin. Instead, we could add another kind of environment marker, i.e. we could replace:

jax-cuda12-plugin[with-cuda]<=0.7.0,>=0.7.0; extra == "cuda12"

with:

jax-cuda12-plugin[with-cuda]<=0.7.0,>=0.7.0; "nvidia :: cuda_version_lower_bound :: 12.0" in system_variant_properties

(yes, the name sucks)

Then the assumption would be that:

1. pyproject.toml has variant.provider.* sections without actually using these providers to build variants.
2. When installing a wheel, the installer installs and uses plugins both from wheel's properties and from system_* markers — so we can evaluate these markers on wheel variants that don't use the specific provider.
3. When installing a wheel, the installer evaluates the current state of supported properties and stores them in the installed wheel metadata.
4. Said state is used to evaluate properties.

This would ensure consistent state and achieve the goal. However, I'm not convinced it's worth the effort, and it's probably not the most pretty solution to the problem. In the end, it might be a better solution to simply build "dummy" variants or introduce a variant-metapackage.

[DEKHTIARJonathan]

@konstin @charliermarsh is this something you plan on finding a solution or shall we design the PEP around this mandatory need (I would really prefer not having to).

How is this use-case being managed currently in uv (mutually exclusive extras) ?https://docs.google.com/document/d/1r3D2xtlVYqfb64HySHPw4wDUeon2vgJNbbRcqSi0Rks/edit?disco=AAABqAEQm8k