`is_backtrack_cause` is very expensive to evaluate

[jbylund]

What's the problem this feature will solve?

The provider's is_backtrack_cause method is currently pretty expensive to evaluate (44% inclusive, profile) https://github.com/pypa/pip/blob/e46888b468a42a3bc52518aaef7f351b39131499/src/pip/_internal/resolution/resolvelib/provider.py#L239-L248 Conceptually it's "is this identifier in this set of names & parent's names", but because it drives a sort (in part) we scan the entire list many times (additionally, the .name property of some of these objects is expensive).

Describe the solution you'd like

I'd like to implement is_backtrack_cause in a way that we can ask identifier in constant_time_lookup_datastructure. Draft of an idea in #10621.

Alternative Solutions

I looked at implementing this in resolvelib a little bit, but my impression is that resolvelib doesn't want to be so opinionated about what these objects are?

Code of Conduct

• [X] I agree to follow the PSF Code of Conduct.