Add new preference for "upper bound requirement" when backtracking (and make it more important than depth)

[notatallshaw]

What's the problem this feature will solve?

When looking at issues with pip gets "stuck" (either ResolutionTooDeep or backtracking to old requirements that don't build) backtracking during complicated resolutions, one of the most common issues related to upper bounds.

Here's a high level overview of what happens:

1. Resolution pins dependency A to version 2
2. A has a dependency on B
3. Resolution pins dependency B to version 1
4. Independently there is a dependency on C
5. Resolution pins dependency C to version 100
6. C has a dependency on "A<2"
7. Because A is already pinned, and it wasn't even the last pin, the resolution now checks every version of C (or worse, unrelated unsatified dependencies)

This leads to one of three problems:

1. Pip spends a lot of time trying every version of C, before backtracking on A - the impact is a slow resolution for users
2. Pip backtracks to a version of C which there is no wheel for and the sdist does not build - the impact is the user gets a confusing build error
3. Pip backtracks to a version of C which does not have a stated dependency on A<2 but that's because that version of C was released before A v2 was released, and it in practise this version of C does not work with A v2, leaving the user with functionally broken resolution

Describe the solution you'd like

With pip's current resolution algorithm this can be partially solved by adding a preference on upper bounds in the get_preference method of the PipProvider.

The one situation this can't currently be solved for is when C is discovered after pinning A. But in my testing adding this preference, especially making it more important than depth, greatly improved resolutions.

There actually 4 ways to express an upper bound, two explicit:

• foo < 1
• foo <= 1

And two implicit:

• foo ~= 1.0
• foo == 1.*

I believe all 4 should trigger this, as while the explicit upper bounds are the ones I generally see this problem with, the implicit upper bounds could also face this issue.

Alternative Solutions

Do nothing 😟

Additional context

I am going to make a PR, I am going to build it on top of #12982, so that I can expand the unit tests. I am also going to try and test it against a lot of real world scenarios, not sure how long it will take me to put this together, so PR might be later today, or could be in a week or two.

Code of Conduct

• I agree to follow the PSF Code of Conduct.