Repository: pypa/pip
Pull request #13273 (2025-03-08 20:28:33)

Prefer requirements with upper bounds
Fixes: https://github.com/pypa/pip/issues/12993
Fixes: https://github.com/pypa/pip/issues/12990

This is the last PR related to `get_preference` I am making this release cycle, this one provides significant performance improvements for some pathological resolutions, and I don't have any examples where it makes the resolution worse.

There are a number of intuitive ways to think about why this would help find a resolution faster, but the one I most like is  operators that do not allow versions *after* a certain version limit the possible versions to some finite set (ignoring that technically a package could never bump their major/minor version number) where as other operators still allow for unbounded future versions to be selected.

Checking against the scenarios in [Pip-Resolution-Scenarios-and-Benchmarks](https://github.com/notatallshaw/Pip-Resolution-Scenarios-and-Benchmarks), there are two problematic scenarios that go from failing to succeeding compared to master branch:

```
Difference for scenario scenarios/problematic.toml - autogluon:
    	Success: False -> True
    	Failure Reason: Build Failure -> None
    	Distinct Sdists visisted: 1 -> 2 (200.00%)
    	Distinct Wheels visisted: 162 -> 259 (159.88%)
    	Total visisted packages: 2398 -> 1254 (52.29%)
    	Total visisted requirements: 23945 -> 13006 (54.32%)
    	Total rejected requirements: 12791 -> 4101 (32.06%)
    	Total pinned packages: 729 -> 536 (73.53%)
    	Total rounds: 1283 -> 768 (59.86%)

Difference for scenario scenarios/problematic.toml - sphinx:
    	Success: False -> True
    	Failure Reason: Resolution Too Deep -> None
    	Distinct Sdists visisted: 1 -> 0 (0.00%)
    	Distinct Wheels visisted: 124 -> 79 (63.71%)
    	Total visisted packages: 97707 -> 80 (0.08%)
    	Total visisted requirements: 225360 -> 225 (0.10%)
    	Total rejected requirements: 137840 -> 6 (0.00%)
    	Total pinned packages: 8113 -> 82 (1.01%)
    	Total rounds: 15005 -> 82 (0.55%)
```

Note, for the latter scenario I have the benchmark tool stop at ~15k rounds, where as normally pip won't stop till 200k rounds.


Patch:
diff --git a/.github/workflows/update-rtd-redirects.yml b/.github/workflows/update-rtd-redirects.yml
index c1f05cced..0beb2b84b 100644
--- a/.github/workflows/update-rtd-redirects.yml
+++ b/.github/workflows/update-rtd-redirects.yml
@@ -3,9 +3,6 @@ name: Update documentation redirects
 on:
   push:
     branches: [main]
-    paths:
-      - ".readthedocs-custom-redirects.yml"
-      - ".readthedocs.yml"
   schedule:
     - cron: 0 0 * * MON # Run every Monday at 00:00 UTC
 
@@ -25,6 +22,7 @@ jobs:
       - uses: actions/setup-python@v5
         with:
           python-version: "3.11"
-      - run: pipx run tools/update-rtd-redirects.py
+      - run: pip install httpx pyyaml rich
+      - run: python tools/update-rtd-redirects.py
         env:
           RTD_API_TOKEN: ${{ secrets.RTD_API_TOKEN }}
diff --git a/docs/html/topics/more-dependency-resolution.md b/docs/html/topics/more-dependency-resolution.md
index c0afd3a4e..c048acd85 100644
--- a/docs/html/topics/more-dependency-resolution.md
+++ b/docs/html/topics/more-dependency-resolution.md
@@ -160,16 +160,22 @@ Pip's current implementation of the provider implements
 
 * If Requires-Python is present only consider that
 * If there are causes of resolution conflict (backtrack causes) then
-  only consider them until there are no longer any resolution conflicts
-
-Pip's current implementation of the provider implements `get_preference` as
-follows:
-
-* Prefer if any of the known requirements is "direct", e.g. points to an
-    explicit URL.
-* If equal, prefer if any requirement is "pinned", i.e. contains
-    operator ``===`` or ``==``.
-* Order user-specified requirements by the order they are specified.
-* If equal, prefers "non-free" requirements, i.e. contains at least one
-    operator, such as ``>=`` or ``<``.
-* If equal, order alphabetically for consistency (helps debuggability).
+    only consider them until there are no longer any resolution conflicts
+
+Pip's current implementation of the provider implements `get_preference`
+for known requirements with the following preferences in the following order:
+
+* Any requirement that is "direct", e.g., points to an explicit URL.
+* Any requirement that is "pinned", i.e., contains the operator ``===``
+    or ``==`` without a wildcard.
+* Any requirement that imposes an upper version limit, i.e., contains the
+    operator ``<``, ``<=``, ``~=``, or ``==`` with a wildcard. Because
+    pip prioritizes the latest version, preferring explicit upper bounds
+    can rule out infeasible candidates sooner. This does not imply that
+    upper bounds are good practice; they can make dependency management
+    and resolution harder.
+* Order user-specified requirements as they are specified, placing
+    other requirements afterward.
+* Any "non-free" requirement, i.e., one that contains at least one
+    operator, such as ``>=`` or ``!=``.
+* Alphabetical order for consistency (aids debuggability).
diff --git a/news/13273.feature.rst b/news/13273.feature.rst
new file mode 100644
index 000000000..ad3177ec3
--- /dev/null
+++ b/news/13273.feature.rst
@@ -0,0 +1,1 @@
+Improved heuristics for determining the order of dependency resolution.
diff --git a/src/pip/_internal/resolution/resolvelib/provider.py b/src/pip/_internal/resolution/resolvelib/provider.py
index afdffe819..617a993cb 100644
--- a/src/pip/_internal/resolution/resolvelib/provider.py
+++ b/src/pip/_internal/resolution/resolvelib/provider.py
@@ -161,14 +161,20 @@ class PipProvider(_ProviderBase):
 
         Currently pip considers the following in order:
 
-        * Prefer if any of the known requirements is "direct", e.g. points to an
-          explicit URL.
-        * If equal, prefer if any requirement is "pinned", i.e. contains
-          operator ``===`` or ``==``.
-        * Order user-specified requirements by the order they are specified.
-        * If equal, prefers "non-free" requirements, i.e. contains at least one
-          operator, such as ``>=`` or ``<``.
-        * If equal, order alphabetically for consistency (helps debuggability).
+        * Any requirement that is "direct", e.g., points to an explicit URL.
+        * Any requirement that is "pinned", i.e., contains the operator ``===``
+          or ``==`` without a wildcard.
+        * Any requirement that imposes an upper version limit, i.e., contains the
+          operator ``<``, ``<=``, ``~=``, or ``==`` with a wildcard. Because
+          pip prioritizes the latest version, preferring explicit upper bounds
+          can rule out infeasible candidates sooner. This does not imply that
+          upper bounds are good practice; they can make dependency management
+          and resolution harder.
+        * Order user-specified requirements as they are specified, placing
+          other requirements afterward.
+        * Any "non-free" requirement, i.e., one that contains at least one
+          operator, such as ``>=`` or ``!=``.
+        * Alphabetical order for consistency (aids debuggability).
         """
         try:
             next(iter(information[identifier]))
@@ -193,12 +199,17 @@ class PipProvider(_ProviderBase):
 
         direct = candidate is not None
         pinned = any(((op[:2] == "==") and ("*" not in ver)) for op, ver in operators)
+        upper_bounded = any(
+            ((op in ("<", "<=", "~=")) or (op == "==" and "*" in ver))
+            for op, ver in operators
+        )
         unfree = bool(operators)
         requested_order = self._user_requested.get(identifier, math.inf)
 
         return (
             not direct,
             not pinned,
+            not upper_bounded,
             requested_order,
             not unfree,
             identifier,
diff --git a/tools/update-rtd-redirects.py b/tools/update-rtd-redirects.py
index 8d53f0183..2aa90e467 100644
--- a/tools/update-rtd-redirects.py
+++ b/tools/update-rtd-redirects.py
@@ -3,11 +3,6 @@
 Relevant API reference: https://docs.readthedocs.io/en/stable/api/v3.html#redirects
 """
 
-# /// script
-# requires-python = ">=3.11"
-# dependencies = ["httpx", "rich", "pyyaml"]
-# ///
-
 import operator
 import os
 import sys


Test patch:
diff --git a/tests/unit/resolution_resolvelib/test_provider.py b/tests/unit/resolution_resolvelib/test_provider.py
index 690217e85..8db40ddc2 100644
--- a/tests/unit/resolution_resolvelib/test_provider.py
+++ b/tests/unit/resolution_resolvelib/test_provider.py
@@ -42,7 +42,7 @@ def build_req_info(
             {"pinned-package": [build_req_info("pinned-package==1.0")]},
             [],
             {},
-            (False, False, math.inf, False, "pinned-package"),
+            (False, False, True, math.inf, False, "pinned-package"),
         ),
         # Star-specified package, i.e. with "*"
         (
@@ -50,7 +50,7 @@ def build_req_info(
             {"star-specified-package": [build_req_info("star-specified-package==1.*")]},
             [],
             {},
-            (False, True, math.inf, False, "star-specified-package"),
+            (False, True, False, math.inf, False, "star-specified-package"),
         ),
         # Package that caused backtracking
         (
@@ -58,7 +58,7 @@ def build_req_info(
             {"backtrack-package": [build_req_info("backtrack-package")]},
             [build_req_info("backtrack-package")],
             {},
-            (False, True, math.inf, True, "backtrack-package"),
+            (False, True, True, math.inf, True, "backtrack-package"),
         ),
         # Root package requested by user
         (
@@ -66,15 +66,15 @@ def build_req_info(
             {"root-package": [build_req_info("root-package")]},
             [],
             {"root-package": 1},
-            (False, True, 1, True, "root-package"),
+            (False, True, True, 1, True, "root-package"),
         ),
         # Unfree package (with specifier operator)
         (
             "unfree-package",
-            {"unfree-package": [build_req_info("unfree-package<1")]},
+            {"unfree-package": [build_req_info("unfree-package!=1")]},
             [],
             {},
-            (False, True, math.inf, False, "unfree-package"),
+            (False, True, True, math.inf, False, "unfree-package"),
         ),
         # Free package (no operator)
         (
@@ -82,7 +82,47 @@ def build_req_info(
             {"free-package": [build_req_info("free-package")]},
             [],
             {},
-            (False, True, math.inf, True, "free-package"),
+            (False, True, True, math.inf, True, "free-package"),
+        ),
+        # Upper bounded with <= operator
+        (
+            "upper-bound-lte-package",
+            {
+                "upper-bound-lte-package": [
+                    build_req_info("upper-bound-lte-package<=2.0")
+                ]
+            },
+            [],
+            {},
+            (False, True, False, math.inf, False, "upper-bound-lte-package"),
+        ),
+        # Upper bounded with < operator
+        (
+            "upper-bound-lt-package",
+            {"upper-bound-lt-package": [build_req_info("upper-bound-lt-package<2.0")]},
+            [],
+            {},
+            (False, True, False, math.inf, False, "upper-bound-lt-package"),
+        ),
+        # Upper bounded with ~= operator
+        (
+            "upper-bound-compatible-package",
+            {
+                "upper-bound-compatible-package": [
+                    build_req_info("upper-bound-compatible-package~=1.0")
+                ]
+            },
+            [],
+            {},
+            (False, True, False, math.inf, False, "upper-bound-compatible-package"),
+        ),
+        # Not upper bounded, using only >= operator
+        (
+            "lower-bound-package",
+            {"lower-bound-package": [build_req_info("lower-bound-package>=1.0")]},
+            [],
+            {},
+            (False, True, True, math.inf, False, "lower-bound-package"),
         ),
     ],
 )