Python/uv
1
0
Fork 0
mirror of https://github.com/astral-sh/uv synced 2026-01-23 22:40:10 -05:00
Code Issues Packages Projects Releases Wiki Activity
Files
0.5.10
uv/Cargo.toml
konsti 431ddc1d74 Change backtracking when packages conflict too much (#9843) 
Background reading: https://github.com/astral-sh/uv/issues/8157
Companion PR: https://github.com/astral-sh/pubgrub/pull/36
Requires for test coverage: https://github.com/astral-sh/packse/pull/230

When two packages A and B conflict, we have the option to choose a lower
version of A, or a lower version of B. Currently, we determine this by
the order we saw a package (assuming equal specificity of the
requirement): If we saw A before B, we pin A until all versions of B are
exhausted. This can lead to undesirable outcomes, from cases where it's
just slow (sentry) to others cases without lower bounds where be
backtrack to a very old version of B. This old version may fail to build
(terminating the resolution), or it's a version so old that it doesn't
depend on A (or the shared conflicting package) anymore - but also is
too old for the user's application (fastapi). #8157 collects such cases,
and the `wrong-backtracking` packse scenario contains a minimized
example.

We try to solve this by tracking which packages are "A"s, culprits, and
"B"s, affected, and manually interfering with project selection and
backtracking. Whenever a version we just chose is rejected, we give the
current package a counter for being affected, and the package it
conflicted with a counter for being a culprit. If a package accumulates
more counts than a threshold, we reprioritize: Undecided after the
culprits, after the affected, after packages that only have a single
version (URLs, `==<version>`). We then ask pubgrub to backtrack just
before the culprit. Due to the changed priorities, we now select package
B, the affected, instead of package A, the culprit.

To do this efficiently, we ask pubgrub for the incompatibility that
caused backtracking, or just the last version to be discarded (due to
its dependencies). For backtracking, we use the last incompatibility
from unit propagation as a heuristic. When a version is discarded
because one of its dependencies conflicts with the partial solution, the
incompatibility tells us the package in the partial solution that
conflicted.

We only backtrack once per package, on the first time it passes the
threshold. This prevents backtracking loops in which we make the same
decisions over and over again. But we also changed the priority, so that
we shouldn't take the same path even after the one time we backtrack (it
would defeat the purpose of this change).

There are some parameters that can be tweaked: Currently, the threshold
is set to 5, which feels not too eager with so me of the conflicts that
we want to tolerate but also changes strategies quickly. The relative
order of the new priorities can also be changed, as for each (A, B) pair
the priority of B is afterwards lower than that for A. Currently,
culprits capture conflict for the whole package, but we could limit that
to a specific version. We could discard conflict counters after
backtracking instead of keeping them eternally as we do now. Note that
we're always taking about pairs (A, B), but in practice we track
individual packages, not pairs.

A case that we wouldn't capture is when B is only introduced to the
dependency graph after A, but I think that would require cyclical
dependency for A and B to conflict? There may also be cases where
looking at the last incompatibility is insufficient.

Another example that we can't repair with prioritization is
urllib3/boto3/botocore: We actually have to check all the newer versions
of boto3 and botocore to identify the version that allows with the older
urllib3, no shortcuts allowed.

```
urllib3<1.25.4
boto3
```

All examples I tested were cases with two packages where we only had to
switch the order, so I've abstracted them into a single packse case.

This PR changes the resolution for certain paths, and there is the risk
for regressions.

Fixes #8157

---

All tested examples improved.

Input fastapi:
```text
starlette<=0.36.0
fastapi<=0.115.2
```

```
# BEFORE
$ uv pip --no-progress compile -p 3.11 --exclude-newer 2024-10-01 --no-annotate debug/fastapi.txt
annotated-types==0.7.0
anyio==4.6.0
fastapi==0.1.17
idna==3.10
pydantic==2.9.2
pydantic-core==2.23.4
sniffio==1.3.1
starlette==0.36.0
typing-extensions==4.12.2

# AFTER
$ cargo run --profile fast-build --no-default-features pip compile -p 3.11 --no-progress --exclude-newer 2024-10-01 --no-annotate debug/fastapi.txt 
annotated-types==0.7.0
anyio==4.6.0
fastapi==0.109.1
idna==3.10
pydantic==2.9.2
pydantic-core==2.23.4
sniffio==1.3.1
starlette==0.35.1
typing-extensions==4.12.2
```


Input xarray:
```text
xarray[accel]
```

```
# BEFORE
$ uv pip --no-progress compile -p 3.11 --exclude-newer 2024-10-01 --no-annotate debug/xarray-accel.txt
bottleneck==1.4.0
flox==0.9.13
llvmlite==0.36.0
numba==0.53.1
numbagg==0.8.2
numpy==2.1.1
numpy-groupies==0.11.2
opt-einsum==3.4.0
packaging==24.1
pandas==2.2.3
python-dateutil==2.9.0.post0
pytz==2024.2
scipy==1.14.1
setuptools==75.1.0
six==1.16.0
toolz==0.12.1
tzdata==2024.2
xarray==2024.9.0

# AFTER
$ cargo run --profile fast-build --no-default-features pip compile -p 3.11 --no-progress --exclude-newer 2024-10-01 --no-annotate debug/xarray-accel.txt
bottleneck==1.4.0
flox==0.9.13
llvmlite==0.43.0
numba==0.60.0
numbagg==0.8.2
numpy==2.0.2
numpy-groupies==0.11.2
opt-einsum==3.4.0
packaging==24.1
pandas==2.2.3
python-dateutil==2.9.0.post0
pytz==2024.2
scipy==1.14.1
six==1.16.0
toolz==0.12.1
tzdata==2024.2
xarray==2024.9.0
```


Input sentry: The resolution is identical, but arrived at much faster:
main tries 69 versions (sentry-kafka-schemas: 63), PR tries 12 versions
(sentry-kafka-schemas: 6; 5 times conflicting, then once the right
version).

```text
python-rapidjson<=1.20,>=1.4
sentry-kafka-schemas<=0.1.113,>=0.1.50
```

```
# BEFORE
$ uv pip --no-progress compile -p 3.11 --exclude-newer 2024-10-01 --no-annotate debug/sentry.txt
fastjsonschema==2.20.0
msgpack==1.1.0
python-rapidjson==1.8
pyyaml==6.0.2
sentry-kafka-schemas==0.1.111
typing-extensions==4.12.2

# AFTER
$ cargo run --profile fast-build --no-default-features pip compile -p 3.11 --no-progress --exclude-newer 2024-10-01 --no-annotate debug/sentry.txt
fastjsonschema==2.20.0
msgpack==1.1.0
python-rapidjson==1.8
pyyaml==6.0.2
sentry-kafka-schemas==0.1.111
typing-extensions==4.12.2
```


Input apache-beam
```text
# Run on Python 3.10
dill<0.3.9,>=0.2.2
apache-beam<=2.49.0
```

```
# BEFORE
$ uv pip --no-progress compile -p 3.10 --exclude-newer 2024-10-01 --no-annotate debug/apache-beam.txt
  × Failed to download and build `apache-beam==2.0.0`
  ╰─▶ Build backend failed to determine requirements with `build_wheel()` (exit status: 1)

# AFTER
$ cargo run --profile fast-build --no-default-features pip compile -p 3.10 --no-progress --exclude-newer 2024-10-01 --no-annotate debug/apache-beam.txt
apache-beam==2.49.0
certifi==2024.8.30
charset-normalizer==3.3.2
cloudpickle==2.2.1
crcmod==1.7
dill==0.3.1.1
dnspython==2.6.1
docopt==0.6.2
fastavro==1.9.7
fasteners==0.19
grpcio==1.66.2
hdfs==2.7.3
httplib2==0.22.0
idna==3.10
numpy==1.24.4
objsize==0.6.1
orjson==3.10.7
proto-plus==1.24.0
protobuf==4.23.4
pyarrow==11.0.0
pydot==1.4.2
pymongo==4.10.0
pyparsing==3.1.4
python-dateutil==2.9.0.post0
pytz==2024.2
regex==2024.9.11
requests==2.32.3
six==1.16.0
typing-extensions==4.12.2
urllib3==2.2.3
zstandard==0.23.0
```
2024-12-16 11:39:50 +01:00

337 lines
13 KiB
TOML
Raw Permalink Blame History

[workspace]
members = ["crates/*"]
exclude = [
"scripts",
# Needs nightly
"crates/uv-trampoline",
# Only used to pull in features, allocators, etc. — we specifically don't want them
# to be part of a workspace-wide cargo check, cargo clippy, etc.
"crates/uv-performance-memory-allocator",
"crates/uv-performance-flate2-backend",
]
resolver = "2"
[workspace.package]
edition = "2021"
rust-version = "1.83"
homepage = "https://pypi.org/project/uv/"
documentation = "https://pypi.org/project/uv/"
repository = "https://github.com/astral-sh/uv"
authors = ["uv"]
license = "MIT OR Apache-2.0"
[workspace.dependencies]
uv-auth = { path = "crates/uv-auth" }
uv-build-backend = { path = "crates/uv-build-backend" }
uv-build-frontend = { path = "crates/uv-build-frontend" }
uv-cache = { path = "crates/uv-cache" }
uv-cache-info = { path = "crates/uv-cache-info" }
uv-cache-key = { path = "crates/uv-cache-key" }
uv-cli = { path = "crates/uv-cli" }
uv-client = { path = "crates/uv-client" }
uv-configuration = { path = "crates/uv-configuration" }
uv-console = { path = "crates/uv-console" }
uv-dirs = { path = "crates/uv-dirs" }
uv-dispatch = { path = "crates/uv-dispatch" }
uv-distribution = { path = "crates/uv-distribution" }
uv-distribution-filename = { path = "crates/uv-distribution-filename" }
uv-distribution-types = { path = "crates/uv-distribution-types" }
uv-extract = { path = "crates/uv-extract" }
uv-fs = { path = "crates/uv-fs", features = ["serde", "tokio"] }
uv-git = { path = "crates/uv-git" }
uv-globfilter = { path = "crates/uv-globfilter" }
uv-install-wheel = { path = "crates/uv-install-wheel", default-features = false }
uv-installer = { path = "crates/uv-installer" }
uv-macros = { path = "crates/uv-macros" }
uv-metadata = { path = "crates/uv-metadata" }
uv-normalize = { path = "crates/uv-normalize" }
uv-once-map = { path = "crates/uv-once-map" }
uv-options-metadata = { path = "crates/uv-options-metadata" }
uv-pep440 = { path = "crates/uv-pep440", features = ["tracing", "rkyv", "version-ranges"] }
uv-pep508 = { path = "crates/uv-pep508", features = ["non-pep508-extensions"] }
uv-platform-tags = { path = "crates/uv-platform-tags" }
uv-publish = { path = "crates/uv-publish" }
uv-pypi-types = { path = "crates/uv-pypi-types" }
uv-python = { path = "crates/uv-python" }
uv-requirements = { path = "crates/uv-requirements" }
uv-requirements-txt = { path = "crates/uv-requirements-txt" }
uv-resolver = { path = "crates/uv-resolver" }
uv-scripts = { path = "crates/uv-scripts" }
uv-settings = { path = "crates/uv-settings" }
uv-shell = { path = "crates/uv-shell" }
uv-state = { path = "crates/uv-state" }
uv-static = { path = "crates/uv-static" }
uv-trampoline-builder = { path = "crates/uv-trampoline-builder" }
uv-tool = { path = "crates/uv-tool" }
uv-types = { path = "crates/uv-types" }
uv-version = { path = "crates/uv-version" }
uv-virtualenv = { path = "crates/uv-virtualenv" }
uv-warnings = { path = "crates/uv-warnings" }
uv-workspace = { path = "crates/uv-workspace" }
anstream = { version = "0.6.15" }
anyhow = { version = "1.0.89" }
async-channel = { version = "2.3.1" }
async-compression = { version = "0.4.12", features = ["bzip2", "gzip", "xz", "zstd"] }
async-trait = { version = "0.1.82" }
async_http_range_reader = { version = "0.9.1" }
async_zip = { git = "https://github.com/charliermarsh/rs-async-zip", rev = "c909fda63fcafe4af496a07bfda28a5aae97e58d", features = ["deflate", "tokio"] }
axoupdater = { version = "0.8.2", default-features = false }
backoff = { version = "0.4.0" }
base64 = { version = "0.22.1" }
bitflags = { version = "2.6.0" }
boxcar = { version = "0.2.5" }
bytecheck = { version = "0.8.0" }
cachedir = { version = "0.3.1" }
cargo-util = { version = "0.2.14" }
clap = { version = "4.5.17", features = ["derive", "env", "string", "wrap_help"] }
clap_complete_command = { version = "0.6.1" }
configparser = { version = "3.1.0" }
console = { version = "0.15.8", default-features = false }
csv = { version = "1.3.0" }
ctrlc = { version = "3.4.5" }
dashmap = { version = "6.1.0" }
data-encoding = { version = "2.6.0" }
dotenvy = { version = "0.15.7" }
dunce = { version = "1.0.5" }
either = { version = "1.13.0" }
encoding_rs_io = { version = "0.1.7" }
etcetera = { version = "0.8.0" }
flate2 = { version = "1.0.33", default-features = false }
fs-err = { version = "3.0.0", features = ["tokio"] }
fs2 = { version = "0.4.3" }
futures = { version = "0.3.30" }
glob = { version = "0.3.1" }
globset = { version = "0.4.15" }
globwalk = { version = "0.9.1" }
goblin = { version = "0.9.0", default-features = false, features = ["std", "elf32", "elf64", "endian_fd"] }
hashbrown = { version = "0.15.1" }
hex = { version = "0.4.3" }
home = { version = "0.5.9" }
html-escape = { version = "0.2.13" }
http = { version = "1.1.0" }
indexmap = { version = "2.5.0" }
indicatif = { version = "0.17.8" }
indoc = { version = "2.0.5" }
itertools = { version = "0.13.0" }
jiff = { version = "0.1.14", features = ["serde"] }
junction = { version = "1.2.0" }
krata-tokio-tar = { version = "0.4.2" }
mailparse = { version = "0.15.0" }
md-5 = { version = "0.10.6" }
memchr = { version = "2.7.4" }
miette = { version = "7.2.0", features = ["fancy-no-backtrace"] }
nanoid = { version = "0.4.0" }
nix = { version = "0.29.0" }
owo-colors = { version = "4.1.0" }
path-slash = { version = "0.2.1" }
pathdiff = { version = "0.2.1" }
petgraph = { version = "0.6.5" }
platform-info = { version = "2.0.3" }
proc-macro2 = { version = "1.0.86" }
procfs = { version = "0.17.0", default-features = false, features = ["flate2"] }
pubgrub = { git = "https://github.com/astral-sh/pubgrub", rev = "05e8d12cea8d72c6d2d017900e478d0abd28fef4" }
quote = { version = "1.0.37" }
rayon = { version = "1.10.0" }
reflink-copy = { version = "0.1.19" }
regex = { version = "1.10.6" }
regex-automata = { version = "0.4.8", default-features = false, features = ["dfa-build", "dfa-search", "perf", "std", "syntax"] }
reqwest = { version = "0.12.7", default-features = false, features = ["json", "gzip", "stream", "rustls-tls", "rustls-tls-native-roots", "socks", "multipart", "http2", "blocking"] }
reqwest-middleware = { version = "0.4.0", features = ["multipart"] }
reqwest-retry = { version = "0.7.0" }
rkyv = { version = "0.8.8", features = ["bytecheck"] }
rmp-serde = { version = "1.3.0" }
rust-netrc = { version = "0.1.2" }
rustc-hash = { version = "2.0.0" }
rustix = { version = "0.38.37", default-features = false, features = ["fs", "std"] }
same-file = { version = "1.0.6" }
schemars = { version = "0.8.21", features = ["url"] }
seahash = { version = "4.1.0" }
self-replace = { version = "1.5.0" }
serde = { version = "1.0.210", features = ["derive", "rc"] }
serde-untagged = { version = "0.1.6" }
serde_json = { version = "1.0.128" }
sha2 = { version = "0.10.8" }
smallvec = { version = "1.13.2" }
spdx = { version = "0.10.6" }
syn = { version = "2.0.77" }
sys-info = { version = "0.9.1" }
tar = { version = "0.4.43" }
target-lexicon = { version = "0.13.0" }
tempfile = { version = "3.14.0" }
textwrap = { version = "0.16.1" }
thiserror = { version = "2.0.0" }
tl = { git = "https://github.com/astral-sh/tl.git", rev = "6e25b2ee2513d75385101a8ff9f591ef51f314ec" }
tokio = { version = "1.40.0", features = ["fs", "io-util", "macros", "process", "rt", "signal", "sync"] }
tokio-stream = { version = "0.1.16" }
tokio-util = { version = "0.7.12", features = ["compat", "io"] }
toml = { version = "0.8.19" }
toml_edit = { version = "0.22.21", features = ["serde"] }
tracing = { version = "0.1.40" }
tracing-durations-export = { version = "0.3.0", features = ["plot"] }
tracing-subscriber = { version = "0.3.18", features = ["env-filter", "json", "registry"] }
tracing-tree = { version = "0.4.0" }
unicode-width = { version = "0.1.13" }
unscanny = { version = "0.1.0" }
url = { version = "2.5.2", features = ["serde"] }
urlencoding = { version = "2.1.3" }
version-ranges = { git = "https://github.com/astral-sh/pubgrub", rev = "05e8d12cea8d72c6d2d017900e478d0abd28fef4" }
walkdir = { version = "2.5.0" }
which = { version = "7.0.0", features = ["regex"] }
windows-registry = { version = "0.3.0" }
windows-result = { version = "0.2.0" }
windows-sys = { version = "0.59.0", features = ["Win32_Foundation", "Win32_Security", "Win32_Storage_FileSystem", "Win32_System_Ioctl", "Win32_System_IO"] }
winreg = { version = "0.52.0" }
winsafe = { version = "0.0.22", features = ["kernel"] }
wiremock = { version = "0.6.2" }
xz2 = { version = "0.1.7" }
zip = { version = "0.6.6", default-features = false, features = ["deflate"] }
[workspace.metadata.cargo-shear]
ignored = ["flate2", "xz2"]
[workspace.lints.rust]
unsafe_code = "warn"
unreachable_pub = "warn"
[workspace.lints.clippy]
pedantic = { level = "warn", priority = -2 }
# Allowed pedantic lints
char_lit_as_u8 = "allow"
collapsible_else_if = "allow"
collapsible_if = "allow"
implicit_hasher = "allow"
map_unwrap_or = "allow"
match_same_arms = "allow"
missing_errors_doc = "allow"
missing_panics_doc = "allow"
module_name_repetitions = "allow"
must_use_candidate = "allow"
similar_names = "allow"
too_many_arguments = "allow"
too_many_lines = "allow"
used_underscore_binding = "allow"
# Disallowed restriction lints
print_stdout = "warn"
print_stderr = "warn"
dbg_macro = "warn"
empty_drop = "warn"
empty_structs_with_brackets = "warn"
exit = "warn"
get_unwrap = "warn"
rc_buffer = "warn"
rc_mutex = "warn"
rest_pat_in_fully_bound_structs = "warn"
if_not_else = "allow"
[profile.release]
strip = true
lto = "fat"
# This profile is meant to mimic the `release` profile as closely as
# possible, but using settings that are more beneficial for iterative
# development. That is, the `release` profile is intended for actually
# building the release, where as `profiling` is meant for building `uv`
# for running benchmarks.
#
# The main differences here are to avoid stripping debug information
# and disabling lto. This does result in a mismatch between our release
# configuration and our benchmarking configuration, which is unfortunate.
# But compile times with `lto = true` are completely untenable:
#
# $ cargo b --profile profiling -p uv
# Compiling uv-cli v0.0.1 (/home/andrew/astral/uv/crates/uv-cli)
# Compiling uv v0.2.34 (/home/andrew/astral/uv/crates/uv)
# Finished `profiling` profile [optimized + debuginfo] target(s) in 3m 47s
#
# Using `lto = "thin"` brings a massive improvement, but it's still slow:
#
# $ cargo b --profile profiling -p uv
# Compiling uv v0.2.34 (/home/andrew/astral/uv/crates/uv)
# Finished `profiling` profile [optimized + debuginfo] target(s) in 53.98s
#
# But with `lto = false`:
#
# $ cargo b --profile profiling -p uv
# Compiling uv v0.2.34 (/home/andrew/astral/uv/crates/uv)
# Finished `profiling` profile [optimized + debuginfo] target(s) in 30.09s
#
# We get more reasonable-ish compile times. At least, it's not enough
# time to get up and get a cup of coffee before it completes.
#
# This setup does risk that we are measuring something in benchmarks
# that we are shipping, but in order to make those two the same, we'd
# either need to make compile times way worse for development, or take
# a hit to binary size and a slight hit to runtime performance in our
# release builds.
[profile.profiling]
inherits = "release"
strip = false
debug = "full"
lto = false
[profile.fast-build]
inherits = "dev"
debug = 0
strip = "debuginfo"
# The profile that 'cargo dist' will build with.
[profile.dist]
inherits = "release"
# Config for 'dist'
[workspace.metadata.dist]
# The preferred dist version to use in CI (Cargo.toml SemVer syntax)
cargo-dist-version = "0.25.2-prerelease.3"
# CI backends to support
ci = "github"
# The installers to generate for each app
installers = ["shell", "powershell"]
# The archive format to use for windows builds (defaults .zip)
windows-archive = ".zip"
# The archive format to use for non-windows builds (defaults .tar.xz)
unix-archive = ".tar.gz"
# Target platforms to build apps for (Rust target-triple syntax)
targets = [
"aarch64-apple-darwin",
"aarch64-unknown-linux-gnu",
"aarch64-unknown-linux-musl",
"arm-unknown-linux-musleabihf",
"armv7-unknown-linux-gnueabihf",
"armv7-unknown-linux-musleabihf",
"i686-pc-windows-msvc",
"i686-unknown-linux-gnu",
"i686-unknown-linux-musl",
"powerpc64-unknown-linux-gnu",
"powerpc64le-unknown-linux-gnu",
"s390x-unknown-linux-gnu",
"x86_64-apple-darwin",
"x86_64-pc-windows-msvc",
"x86_64-unknown-linux-gnu",
"x86_64-unknown-linux-musl",
]
# Whether to auto-include files like READMEs, LICENSEs, and CHANGELOGs (default true)
auto-includes = false
# Whether dist should create a Github Release or use an existing draft
create-release = true
# Which actions to run on pull requests
pr-run-mode = "skip"
# Whether CI should trigger releases with dispatches instead of tag pushes
dispatch-releases = true
# Which phase dist should use to create the GitHub release
github-release = "announce"
# Whether CI should include auto-generated code to build local artifacts
build-local-artifacts = false
# Local artifacts jobs to run in CI
local-artifacts-jobs = ["./build-binaries", "./build-docker"]
# Publish jobs to run in CI
publish-jobs = ["./publish-pypi"]
# Post-announce jobs to run in CI
post-announce-jobs = ["./publish-docs"]
# Custom permissions for GitHub Jobs
github-custom-job-permissions = { "build-docker" = { packages = "write", contents = "read" } }
# Whether to install an updater program
install-updater = false
# Path that installers should place binaries in
install-path = ["$XDG_BIN_HOME/", "$XDG_DATA_HOME/../bin", "~/.local/bin"]
Reference in New Issue View Git Blame Copy Permalink