Skip to content

Comments

Add method for incompatibilities between virtual and base packages#45

Merged
konstin merged 1 commit intomainfrom
konsti/main/add_proxy_package
Nov 13, 2025
Merged

Add method for incompatibilities between virtual and base packages#45
konstin merged 1 commit intomainfrom
konsti/main/add_proxy_package

Conversation

@konstin
Copy link
Member

@konstin konstin commented Aug 27, 2025

Add a new method to add a single custom incompatibility that requires the base package and the proxy package share the same version range.

This intended for cases where proxy packages (also known as virtual packages) are used. Without this information, pubgrub does not know that these packages have to be at the same version. In cases where the base package is already to an incompatible version, this avoids going through all versions of the proxy package. In cases where there are two incompatible proxy packages, it avoids trying versions for both of them. Both improve performance (we don't need to check all versions when there is a conflict) and error messages (report a conflict of version ranges instead of enumerating the conflicting versions).

There's several usage patterns for this method. The basic one is upon encountering a dependency on a proxy package with a range, using this method with its base package and that range.

@codspeed-hq
Copy link

codspeed-hq bot commented Aug 27, 2025

CodSpeed Performance Report

Congrats! CodSpeed is installed 🎉

🆕 6 new benchmarks were detected.

You will start to see performance impacts in the reports once the benchmarks are run from your default branch.

Detected benchmarks

konstin added a commit to astral-sh/uv that referenced this pull request Sep 22, 2025
Add an incompatibility that lets pubgrub skip of marker packages when
the base package already has an incompatible version to improve the
error messages (#15199).

The change is also a small perf improvement. Overall this should be able
to improve performance in slow cases by avoiding trying proxy package
versions that are impossible anyway, for a (ideally very small cost) for
tracking the additional incompatibility and tracking the base package
for each proxy package.

```
$ hhyperfine --warmup 2 "uv pip compile --universal scripts/requirements/airflow.in" "target/release/uv pip compile --universal scripts/requirements/airflow.in"
Benchmark 1: uv pip compile --universal scripts/requirements/airflow.in
  Time (mean ± σ):     145.5 ms ±   3.9 ms    [User: 154.7 ms, System: 140.7 ms]
  Range (min … max):   139.2 ms … 153.4 ms    20 runs
 
Benchmark 2: target/release/uv pip compile --universal scripts/requirements/airflow.in
  Time (mean ± σ):     128.7 ms ±   5.5 ms    [User: 141.9 ms, System: 137.3 ms]
  Range (min … max):   121.8 ms … 142.0 ms    23 runs
 
Summary
  target/release/uv pip compile --universal scripts/requirements/airflow.in ran
    1.13 ± 0.06 times faster than uv pip compile --universal scripts/requirements/airflow.in
```

This implementation is the basic version: When we see a proxy
`foo{...}>=x,<y` we add a dependency edge `foo{...}>=x,<y` ->
`foo>=x,<y`. There are several way to extend this, which likely help
more with performance than with error messages.

One idea is that if we see `foo{...}>=x,<y` but we already made a
selection for `foo==z` outside that range, we can insert a dependency
`foo{...}!=z` -> `foo!=z`. This avoids trying any version of the proxy
package except the version that matches our previous selection.

Another is that if we see a dependency `foo>=x,<y`, we also add
`foo{...}>=x,y` -> `foo>=x,<y`. This allows backtracking beyond `foo`
immediately if all version of `foo{...}>=x,<y` are incompatible, since
`foo{...}>=x,<y` incompatible -> `foo>=x,<y` incompatible -> the package
that depended of `foo>=x,<y` is incompatible.

The cost for each of these operations is tracking an additional
incompatibility per virtual package. An alternative approach is to only
add the incompatibility lazily, only when we've tried several version of
the virtual package already. This needs to be weighed of with the better
error messages that the incompatibility gives, we unfortunately have
only few large reference examples.

Requires astral-sh/pubgrub#45

Closes #15199
Add a new method to add a single custom incompatibility that requires the base package and the proxy package share the same version range.

This intended for cases where proxy packages (also known as virtual packages) are used. Without this information, pubgrub does not know that these packages have to be at the same version. In cases where the base package is already to an incompatible version, this avoids going through all versions of the proxy package. In cases where there are two incompatible proxy packages, it avoids trying versions for both of them. Both improve performance (we don't need to check all versions when there is a conflict) and error messages (report a conflict of version ranges instead of enumerating the conflicting versions).

There's several usage patterns for this method. The basic one is upon encountering a dependency on a proxy package with a range, using this method with its base package and that range.
@konstin konstin force-pushed the konsti/main/add_proxy_package branch from a73b321 to c98bede Compare November 13, 2025 14:30
@konstin
Copy link
Member Author

konstin commented Nov 13, 2025

(This should have merged before)

@konstin konstin merged commit e212f1a into main Nov 13, 2025
6 checks passed
konstin added a commit that referenced this pull request Nov 21, 2025
Add a new method to add a single custom incompatibility that requires
the base package and the proxy package share the same version range.

This intended for cases where proxy packages (also known as virtual
packages) are used. Without this information, pubgrub does not know that
these packages have to be at the same version. In cases where the base
package is already to an incompatible version, this avoids going through
all versions of the proxy package. In cases where there are two
incompatible proxy packages, it avoids trying versions for both of them.
Both improve performance (we don't need to check all versions when there
is a conflict) and error messages (report a conflict of version ranges
instead of enumerating the conflicting versions).

There's several usage patterns for this method. The basic one is upon
encountering a dependency on a proxy package with a range, using this
method with its base package and that range.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant