Optimize Backtracking in Pip's Dependency Resolution By Prioritizing Direct Conflicts

[notatallshaw]

What's the problem this feature will solve?

In complex dependency resolution scenarios, Pip currently may backtrack inefficiently, especially when dealing with direct conflicts in requirements that are just a subset of the possible "causes" that resolvelib returns.

This inefficiency leads to real-world users experiencing "ResolutionTooDeep" issues, as seen in #12489, #12430, and #12395.

Describe the solution you'd like

The proposed solution introduces optimization techniques in Pip's dependency resolution logic that prioritize backtracking on direct conflicts. Inspired by conflict-driven clause learning (CDCL), a core principle in SAT solvers, the aim is to focus on the most impactful conflicts during backtracking, thereby streamlining the resolution process.

The goal is to prioritize direct conflicts within the identified backtracking causes. For example, two candidates specifying conflicting requirements like "numpy<2" and "numpy>2", or a situation where one candidate requires "pandas<2" while another has parent "pandas 2.1.0". By focusing on these critical conflict points, the algorithm can more efficiently navigate the complex dependency graph.

Alternative Solutions

Let users continue attempting to resolve these issues themselves by sufficiently restricting requirements. However, this approach provides very little context or help on how to do so effectively.

Additional context

Depends on #12497 to be performant for simple backtracking cases

Code of Conduct

• I agree to follow the PSF Code of Conduct.

[ichard26]

@notatallshaw is this done? I've lost track of all of the resolvelib PRs you've filed in the past few months 🙃

[notatallshaw]

No, but I am no longer finding significant performance improvement from this change after all the other fixes and performance improvements have gone in. The performance improvements I measured likely were the result of other things being fixed or improved.

Further significant resolution improvements are likely going to need a real CDCL or CDNL algorithm, rather than extending resolvelib. That said, I'm still open to new ideas, and we have the API (narrow requirement selection) now to do more expensive things.