search

sarugaku / resolvelib

Resolve abstract dependencies into concrete ones
ISC License
138 stars 31 forks source link

Implement Causes Narrowing #139

Closed notatallshaw closed 9 months ago

notatallshaw commented 11 months ago

I was looking at this issue here ( https://github.com/pypa/pip/issues/12305#issuecomment-1742127558) and realized that "causes" in the resolution step includes a lot of things which don't actually cause backtracking to occur.

The problem with having a large causes section is it creates expoential choice when backtracking, and it makes for a worse error message if printing out the causes at the end.

I think there are potentially some agressive strategies that one could implement to narrow causes, but at the very least it would make sense to go through each of the causes and see if it actually conflicts with any of the other causes.

For example in the linked example the requirement numpy from soxr=0.3.6 obviously does not conflict with any of the other causes, so resolvelib/Pip should not be trying to backtracking on it.

I write this issue in case anyone disagrees, wants to discuss a strategy, or wants to implement it themselves, I'm pretty busy next few weeks, but I can take a look at implementing it later this year.

notatallshaw commented 9 months ago

After working on this for a little bit I realized it needs to be changes from "Cause Narrowing" to "Prefer Conflicts", it's largely the same idea, the provider understands what causes conflict with each other and resolvelib doesn't and the causes that conflict should be preffered.

Once I have an actual PR ready I will make an issue/PR explaining how it works.