How pip finds a compatible set of package versions

Add the following two dependencies to a project with uv.

$ uv add --no-sync "Django<=5.2.16" "asgiref==3.7.2"

$ uv tree --locked
resolver-example v0.1.0
├── asgiref v3.7.2
└── django v5.0.14
    ├── asgiref v3.7.2
    └── sqlparse v0.5.5

Django 5.2.16 is a possible choice under Django<=5.2.16, yet the lock result contains Django 5.0.14. Why 5.0.14 in particular?

Pinning asgiref to a specific version is uncommon, but this article uses the asgiref==3.7.2 constraint to explain a case where Django resolves to a lower version. (Installing these two dependencies with pip also selects Django 5.0.14, the same as uv.)

$ python -m pip install --dry-run --ignore-installed --no-cache-dir \
    "Django<=5.2.16" "asgiref==3.7.2"
...
Would install Django-5.0.14 asgiref-3.7.2 sqlparse-0.5.5

(uv’s resolver may handle the same case differently.)

Why Django 5.0.14 is selected

An expression that combines a package name with a version constraint, such as Django<=5.2.16, is called a requirement (the same sort of requirement that ends up in the requirements.txt you get from pip freeze). Versions such as Django 5.2.16 and 5.2.15 that satisfy the constraint are called candidates.

Django depends on asgiref and sqlparse. In this example, the package that affects which Django version gets selected is asgiref. The asgiref==3.7.2 the project specifies must also satisfy each Django candidate’s asgiref constraint.

The project pins asgiref to 3.7.2 with asgiref==3.7.2.
The range of asgiref versions allowed by Django varies by Django version.

Django and asgiref can therefore be installed together only if Django’s allowed asgiref range includes 3.7.2.

Comparing Django candidates against asgiref 3.7.2

Project requirementasgiref==3.7.2

specified

Django 5.2.16asgiref>=3.8.1

reject

Django 5.0.14asgiref>=3.7.0,<4

Django 5.2.16 requires asgiref>=3.8.1, so it cannot be installed alongside asgiref==3.7.2.
The remaining Django 5.2 and 5.1 candidates also do not allow asgiref 3.7.2 and are rejected.
Django 5.0.14 requires asgiref>=3.7.0,<4, a range that includes asgiref 3.7.2.

pip checks candidates from the highest version downward and settles on Django 5.0.14, the first candidate that satisfies both constraints.

Finding a combination that satisfies every dependency’s version constraints is called dependency resolution, and the code that handles it is the resolver.

How pip builds its candidate list

For each package version, PyPI may host multiple wheels built for different Python versions, operating systems, and CPU architectures, along with an sdist. pip keeps only the files it can install in the current environment, then turns the matching versions into candidates.

It first discards distribution files that do not match the current Python version, operating system, or CPU architecture.
It narrows the candidate list using the constraints collected so far and candidates that have already caused conflicts.
It reads Requires-Dist from a candidate’s metadata and adds that candidate’s dependencies.

pip checks candidates one at a time and fetches the metadata it needs. What it receives is not the original distribution file but a .whl.metadata file that briefly lists the version information and Requires-Dist entries. The default pip install output shows it like this.¹

  Downloading django-5.2.16-py3-none-any.whl.metadata (4.1 kB)
  Downloading asgiref-3.7.2-py3-none-any.whl.metadata (9.2 kB)
...
  Downloading Django-5.0.14-py3-none-any.whl.metadata (4.1 kB)

Once the candidates are ready, pip still has to find a combination that satisfies every constraint. It uses the resolvelib library for this search. pip’s Provider passes the candidates and each candidate’s dependencies to resolvelib, which searches for a valid combination. (resolvelib does not access PyPI or read wheel metadata itself.²)

Candidate selection and rounds

resolvelib divides the candidate search into rounds. In each round, it picks one package whose version has not yet been decided and checks its candidates in order against the constraints collected so far. When it finds a candidate with no conflict, it fixes that candidate as the version to install, an action called pinning. A round ends when one candidate is pinned or every candidate fails.

With PIP_RESOLVER_DEBUG=1 set as shown below, pip prints the dependency resolution process round by round.

$ PIP_RESOLVER_DEBUG=1 python -m pip install \
    --dry-run --ignore-installed --no-cache-dir \
    "Django<=5.2.16" "asgiref==3.7.2"

Keeping only the candidate pinned in each round gives the following trace.

pip install "Django<=5.2.16" "asgiref==3.7.2"

round 0asgiref 3.7.2fixed to an exact version
round 1Python 3.11.9checks asgiref's Requires-Python
round 2Django 5.0.14rejected 33checks candidates from 5.2.16 through the 5.1 releases
round 3sqlparse 0.5.5
round 4doneevery requirement is satisfied

Rounds are numbered from 0. This run has rounds 0 through 4, and all 33 Django candidates are rejected in round 2.

Even though Django appears first on the command line, asgiref has higher priority because == fixes it to an exact version, so asgiref 3.7.2 is selected first. Python 3.11.9 appears in a separate round because pip also checks the Requires-Python constraint of the asgiref 3.7.2 candidate selected in the previous round.

Rejecting one candidate does not always move on to a new round. In round 2, asgiref 3.7.2 remains pinned while only the Django candidate changes, and the checks continue. The following pseudocode is a simplified version of pip’s internal implementation.

for candidate in candidates: # Iterate over the candidate list
    # Temporarily add the candidate's dependencies to the current constraints.
    conditions = add_dependencies(current_conditions, candidate)

    if has_conflict(conditions):
        # Reject only this candidate when the constraints conflict.
        reject(candidate)
        continue

    # With no conflict, pin this candidate as the version to install.
    pin(candidate, conditions)
    break
else:
    # If every candidate fails, revisit an earlier choice.
    backjump()

In round 2, as seen earlier, resolvelib walks down from Django 5.2.16, rejects the 33 candidates that do not fit asgiref 3.7.2, pins Django 5.0.14, and moves to the next round.

Order in which pip checks Django candidates during round 2

fixed by the projectasgiref==3.7.2

Django 5.2.16asgiref>=3.8.1rejected
Django 5.2.15asgiref>=3.8.1rejected
Django 5.2.14 through the 5.1 releases31 candidates rejected for the same reasonrejected
Django 5.0.14asgiref>=3.7.0,<4pin

Pip rejects incompatible candidates in order and pins Django 5.0.14, the first candidate that satisfies the requirements.

Candidate rejection and backjumping

pip’s documentation uses backtracking for the overall process of discarding a conflicting candidate and trying another one. Trying the next candidate for the same package is different from changing a package version selected earlier.

When one Django candidate conflicts, asgiref==3.7.2 remains pinned and the resolver tries the next Django version. Only the current candidate is rejected.
If every candidate for the package being considered fails, the resolver returns to an earlier choice involved in the conflict and tries another version. resolvelib calls this backjumping.

The difference is not how many candidates were rejected, but whether the resolver changed a version it had already selected.³

Take Django and Channels as an example.

$ PIP_RESOLVER_DEBUG=1 python -m pip install \
    --dry-run --ignore-installed --no-cache-dir \
    "Django>=2.2.28,<=3.0" "channels>=1.1.2,<2"

Django 3.0 requires asgiref~=3.2, while every Channels release from 1.1.2 through 1.1.8 requires asgiref~=1.1.⁴ The two ranges do not overlap, so every Channels candidate is rejected.

Backjump after all Channels candidates are rejected

Channels candidatesremaining

Channels 1.1.8asgiref~=1.1rejected
Channels 1.1.7asgiref~=1.1rejected
Channels 1.1.6 through 1.1.3asgiref~=1.1rejected
Channels 1.1.2asgiref~=1.1rejected

already pinned candidates

Python 3.11.9unrelated to the conflictskipped
Django 3.0asgiref~=3.2involved in the conflictundo

pin order after the backjump

Channels 1.1.8
asgiref 1.1.2
Django 2.2.28

After all Channels candidates are rejected, pip skips the Python 3.11.9 choice, which is unrelated to the conflict, and undoes the Django 3.0 choice.

The backjump returns to the point where Django 3.0 was selected. The resolver then pins Channels 1.1.8, asgiref 1.1.2, and Django 2.2.28 in that order, finding a combination in which all three can be installed together.

So a backjump does not necessarily return to the immediately preceding round. It skips choices unrelated to the conflict and returns to an earlier choice that can resolve it.

A combination pip cannot install

Fixing both Django and asgiref to exact versions leaves no other candidates to try, so pip raises ResolutionImpossible when those two versions cannot be installed together.

$ python -m pip install --dry-run --ignore-installed --no-cache-dir \
    "Django==5.2.16" "asgiref==3.7.2"
ERROR: Cannot install asgiref==3.7.2 and django==5.2.16 because
these package versions have conflicting dependencies.

The conflict is caused by:
    The user requested asgiref==3.7.2
    django 5.2.16 depends on asgiref>=3.8.1
...
ERROR: ResolutionImpossible: for help visit ...

The lines under The conflict is caused by in the error message show which constraints conflicted.

Why Django 5.0.14 is selected

How pip builds its candidate list

Candidate selection and rounds

Candidate rejection and backjumping

A combination pip cannot install

Further reading

Footnotes