Add intelligent fallback from backjump to backtrack

sarugaku / resolvelib

Resolve abstract dependencies into concrete ones

ISC License

138 stars 31 forks source link

Add intelligent fallback from backjump to backtrack #144

Closed notatallshaw closed 2 months ago

notatallshaw commented 9 months ago

Fixes https://github.com/sarugaku/resolvelib/issues/134

Alternative to https://github.com/sarugaku/resolvelib/pull/142, fixes both the requirments mentioned here https://github.com/sarugaku/resolvelib/pull/142#issuecomment-1811627400

I beleive this strategy is fairly foolproof:

When backjumping make a backup of the states the first time backjumping skips over states further than backtracking would
If backjumping reaches resolution impossible and a backup state exists, fall back to that state and start backtracking

However, there are downsides, it could definetly cause a valid ResolutionImpossible to take much longer to produce. I have therefore give the calling library a choice on what to do, backjump with backtrack fallback, backjump only, or backtrack only.

If you want tests I need some small guidance, I don't really understand this repos tests.

Let me know what you think!

notatallshaw commented 9 months ago

Two thoughts now I've had time to sleep on this.

Firstly, adding the option for the calling library to choose a behavior is perhaps a bit too much. I'm thinking perhaps remove it and see if calling libraries notice an issue?

Secondly, this fallback approach could be extended further. It currently does: Backjumping -> Resolution Impossible -> Backtrack forever. It could do Backjumping -> Resolution Impossible -> Backtrack Once -> Backjumping. But I think it's better as it is now and if this lands and if we see real world instances where fallback causes significant slow downs it could be considered.

notatallshaw commented 8 months ago

Firstly, adding the option for the calling library to choose a behavior is perhaps a bit too much. I'm thinking perhaps remove it and see if calling libraries notice an issue?

I've created a seperate commit which applies this so the two versions can be compred. Depending on preference I can delete or squash the commit.

notatallshaw commented 7 months ago

FYI a seperate Pip PR (https://github.com/pypa/pip/pull/12459) I have removes all examples I have tested for backjumping incorrectly producing ResolutionImpossible, I think it's important to still remove or have a fallback for backjumping, I have a more detailed comment in the alternative PR https://github.com/sarugaku/resolvelib/pull/142#issuecomment-1880145310

notatallshaw commented 6 months ago

The implementation is a bit convoluted, need more comments to help successors understand what is happening.

I think to a certain extent that is the nature of this solution, it backs up states and only uses those backed up states under the right conditions.

But I have tried to improve the situation breaking up the code a little, adding more comments, and trying to pick better names. Let me know what you think.

notatallshaw commented 5 months ago

An further thoughts on this?

It would be good to fix this backjump issue somehow, as it breaks real world requirements for both pip and PDM.

notatallshaw commented 2 months ago

I am unhappy with this solution, I am working further on understanding the root cause of the problem: https://github.com/sarugaku/resolvelib/issues/134#issuecomment-2164347177

I may recreate this PR once I have a working test.