Repurpose backtracking hook

[astrojuanlu]

See discussion at https://github.com/pypa/pip/pull/10937. The idea is to change the place where the backtracking hook is called, and add extra parameters so more detailed info messages about conflicting dependencies can be printed.

[astrojuanlu]

Woops, all tests ran locally but probably I did something wrong. Will fix them later.

[astrojuanlu]

Been staring at this line trying to make sense of it:

https://github.com/sarugaku/resolvelib/blob/ebf6c51ec338e6a4d947bc04db4de6fad1078f25/tests/conftest.py#L14

If I understand correctly, with this change the backtracking might happen even before any dependency is pinned, so the assert does not hold anymore. Let me know if I'm misunderstanding something.

[pradyunsg]

Instead of removing it, I'd move it above the -= 1.

[astrojuanlu]

This makes the tests fail too. Excerpt:

_ test_resolver[three_way_conflict] _
...
self = <conftest.TestReporter object at 0x7f70f4864a30>
criterion = Criterion((Requirement(name='AFNetworking', spec=<SpecifierSet('>=1.3,~=1.3')>), via=Candidate(name='AFOAuth2Client', ...name='CargoBay', ver=<Version('2.0.1')>, deps=[Requirement(name='AFNetworking', spec=<SpecifierSet('>=2.0,~=2.0')>)])))
candidate = Candidate(name='CargoBay', ver=<Version('2.0.1')>, deps=[Requirement(name='AFNetworking', spec=<SpecifierSet('>=2.0,~=2.0')>)])

    def backtracking(self, criterion, candidate):
>       assert self._indent >= 0
E       assert -1 >= 0
E        +  where -1 = <conftest.TestReporter object at 0x7f70f4864a30>._indent

tests/conftest.py:13: AssertionError
------------------------------------------------------------------------------------------------------------ Captured stdout call ------------------------------------------------------------------------------------------------------------
Pin  Candidate(name='AFOAuth2Client', ver=<Version('0.1.2')>, deps=[Requirement(name='AFNetworking', spec=<SpecifierSet('>=1.3,~=1.3')>)])
 Pin  Candidate(name='AFNetworking', ver=<Version('1.3.4')>, deps=[])
 Back Candidate(name='AFAmazonS3Client', ver=<Version('2.0.0')>, deps=[Requirement(name='AFNetworking', spec=<SpecifierSet('>=2.0,~=2.0')>)])
 Pin  Candidate(name='AFAmazonS3Client', ver=<Version('1.0.1')>, deps=[Requirement(name='AFNetworking', spec=<SpecifierSet('>=1.3,~=1.3')>)])
 Back Candidate(name='CargoBay', ver=<Version('2.1.0')>, deps=[Requirement(name='AFNetworking', spec=<SpecifierSet('>=2.2,~=2.2')>)])
Back Candidate(name='CargoBay', ver=<Version('2.0.3')>, deps=[Requirement(name='AFNetworking', spec=<SpecifierSet('>=2.1,~=2.1')>)])
Back Candidate(name='CargoBay', ver=<Version('2.0.2')>, deps=[Requirement(name='AFNetworking', spec=<SpecifierSet('>=2.0,~=2.0')>)])

[pradyunsg]

Oh right, because we might not pin something that we backtrack on!

[pradyunsg]

It might make sense to rename backtracking to something related to rejection instead then? Or actually keep this as a separate hook?

I'm a bit wary of adding too many hook points (there's a decent performance impact from each of them, in the hot loop) so... 🤷🏽

[astrojuanlu]

I'm fine renaming or adding a separate hook. IIUC, in both cases we'd be calling a function in the hot loop, regardless of whether we keep the current backtracking hook or not, right?

Apart from the performance question, maybe it doesn't hurt to keep the current backtracking hook and make this PR add a new one with a better name.

[notatallshaw]

I can't test right now but I seem to remember the loop you've moved in to tends to be hotter for situations of heavy backtracking.

In particular when it's not just that there are two conflicting requirements but there is a third conflicting requirement that was pinned much earlier in the resolution steps then the resolver can get in to a situation where it struggles to find any candidate to pin.

If I get a chance I will try some heavy backtracking examples but my next 2 weeks is fairly busy.

[pradyunsg]

Let's do this:

• remove the existing backtracking hook in this PR.
• add a new rejecting_candidate hook in this PR, with the tests adapted accordingly.

If someone feels strongly that the backtracking hook is valuable on its own, they can open an issue about that. I don't think that it's particularly useful. :)

[astrojuanlu]

Not sure who else should approve this PR or who has merge rights here, but if there are any blockers by other folks I'll happily look into those :)

[frostming]

@astrojuanlu please add a news fragment in the news/ directory.

[pradyunsg]

I'm not aware of anyone -- IIUC pip doesn't really use it either.

[astrojuanlu]

News fragment added, version prebumped 👍🏽

[astrojuanlu]

Thanks! Is a new release here needed to update the vendoring in pip?

[pradyunsg]

Sort of. For merging the PR, yes. For experimenting with these changes, no.

If you want to experiment with this before a release, you can use a resolvelib @ git+https://... style reference in the vendor.txt file in pip, run nox -s vendoring, commit that change and move on to the pip side change. We won't merge a PR with such a reference, but it's fairly straightforward to do an interactive-rebase to replace that commit, once the resolvelib release happens.

[uranusjr]

Let’s experiement this a bit in pip first and see if we could further improve the interface before cutting a release here.