criteria compatibility check while backtracking includes dependencies for version we're backtracking on #91
Comments
sanderr
changed the title
|
This came up first in pypa/pip#10568, which OP seems to have not found prior to opening this issue. Closing as per pypa/pip#10568 (comment), since there isn't much more that |
|
I see this is indeed a duplicate, my apologies, I hadn't though to search for flake8, as I considered it specific to my example, not the actual issue. |
|
However, the discussion on that ticket or the comment you linked however don't go into why it rejects |
|
@pradyunsg I think the suggested solution of removing the item being back-tracked-on from the set of criteria may indeed be 'the breakthrough solution`, if the analysis of the situation is correct. It would seem to me that the very essence of backtracking is to replace the item being back-tracked on by an alternative, not merely adding an alternative while maintaining the original? |
|
I'm also very interested in this, and was about to comment on my original report of this issue when I saw this. PIP is downloading 24 versions of flake8 and then discarding them all because of "reasons". It seems worthwhile to figure out what those reasons are, because it seems wasteful and the resulting conflict resolution is far from ideal. I don't dispute that the dependency resolving is technically valid. It's just that pip seems to skip a much easier/quicker/better solution in favor of a much more convoluted/worse one. |
|
One thing I think we potentially can do is to add a final phase after everything is picked up to try to "maximise" the chosen version of each package, by going back to those candidates previously marked as incompatible and try if they can actually be individually upgraded without affecting any other packages. This should probably not be done by default (for the vast majority of cases it is just wasting time), but the user can opt into it if they are fine with that additional overhead. This also ties back to the conversation where I proposed we might want to add some "resolution strategy" flags to pip so people can tweak the behaviour for specific situations, e.g. choosing minimum version instead of maximum. |
|
@uranusjr while I see how your suggestion could be useful, I'm not sure it applies to the issue I'm trying to highlight. As far as I'm concerned, this issue is not about optimizing the chosen state among all candidates. It is about correctness when determining whether a certain candidate version is compatible with the current criteria. The examples along with the exception snippet I provided very much seem to indicate that the current implementation rejects some valid states. If I interpret this correctly this means that the I am definitely willing to accept that I'm missing something, I'm not as familiar with this logic or this code base as you are after all. But up till now I get the impression I'm just not getting my point across. For me this is not about optimization, it is about correctness, and to me the current compatibility check seems to be incorrect in cases where the older versions' dependency constraints do not overlap with the version being backtracked on. The Does the above help in clarifying what exactly I mean and in differentiating between the optimization problem and the correctness of validating a given candidate given the current criteria? |
|
@sanderr Personally, I get what you're saying, but I feel that if things were as incorrect as you suggest, we'd have hit more problems. So I suspect there's a flaw in your logic, I just don't know what it is yet. I'm willing to do some digging, but it's hard to find the time to work through the example you give, which involves pip and some quite long lists of candidates. If you were able to trim your example down to something smaller, preferably not using pip but with a standalone bit of code that "drives" resolvelib directly (there are examples in the |
|
All right, I'll have a look at that. I'm not sure when I'll find the time to do so though, perhaps this weekend. Thanks for your suggestion. |
|
Add me to the list of people that wants to look into how exactly this is triggered. I'd also like to look into the following example. When pip (or resolvelib, I'm not sure who exactly is responsible for what) is instructed to install |
|
Reopening, since there seems to be active discussion. |
|
The following test case reproduces the behavior I'm seeing with a simple from pkg_resources import Requirement
from resolvelib import (
AbstractProvider,
BaseReporter,
Resolver,
)
def test_poc():
all_candidates = {
"parent": [("parent", "1", ["child<2"])],
"child": [
("child", "2", ["grandchild>=2"]),
("child", "1", ["grandchild<2"]),
],
"grandchild": [
("grandchild", "2", []),
("grandchild", "1", []),
],
}
class Provider(AbstractProvider):
def identify(self, requirement_or_candidate):
req = Requirement.parse(requirement_or_candidate)
assert req.key in all_candidates
return req.key
def get_preference(self, *, identifier, **_):
# prefer child over parent (alphabetically)
return identifier
def get_dependencies(self, candidate):
return candidate[2]
def find_matches(self, identifier, requirements, incompatibilities):
return (
candidate
for candidate in all_candidates[identifier]
if all(
candidate[1] in Requirement.parse(req)
for req in requirements[identifier]
)
if candidate not in incompatibilities[identifier]
)
def is_satisfied_by(self, requirement, candidate):
return candidate[1] in Requirement.parse(requirement)
resolver = Resolver(Provider(), BaseReporter())
result = resolver.resolve(["child", "parent"])
assert set(result.mapping) == {"parent", "child", "grandchild"}
assert result.mapping["parent"][1] == "1"
assert result.mapping["child"][1] == "1"
assert result.mapping["grandchild"][1] == "1"The test succeeds because there are no assertions against this behavior yet. It does manage to install the expected versions, but at some point it rejects a valid version. I believe it eventually backtracks and accepts that version then, but I believe the initial rejection is incorrect. Like I said, this needs some refinement still. At the moment, if you want to observe the rejection, I'd suggest adding a breakpoint at resolvelib/src/resolvelib/resolvers.py Line 215 in 62c56b5 Interesting to note is that in this scenario (like with the flake8, flake8-isort issue), the rejection does not occur when you revert preference order. I'll expand on this, making the test provide more valuable information to definitely prove/refute the presence of undesired behavior, perhaps digging a bit more into
If anything's unclear, please let me know. |
|
Many thanks for putting this together. I'll take a proper look at it in the next few days. |
|
Attached the debugging reporter from inside pip. Here's the output of that. Reporter.starting()
Reporter.adding_requirement('child', None)
Reporter.adding_requirement('parent', None)
Reporter.starting_round(0)
Reporter.adding_requirement('grandchild>=2', ('child', '2', ['grandchild>=2']))
Reporter.pinning(('child', '2', ['grandchild>=2']))
Reporter.ending_round(0, state)
Reporter.starting_round(1)
Reporter.pinning(('grandchild', '2', []))
Reporter.ending_round(1, state)
Reporter.starting_round(2)
Reporter.adding_requirement('child<2', ('parent', '1', ['child<2']))
Reporter.pinning(('parent', '1', ['child<2']))
Reporter.ending_round(2, state)
Reporter.starting_round(3)
Reporter.adding_requirement('grandchild<2', ('child', '1', ['grandchild<2']))
Reporter.backtracking(('parent', '1', ['child<2']))
Reporter.backtracking(('grandchild', '2', []))
Reporter.backtracking(('child', '2', ['grandchild>=2']))
Reporter.ending_round(3, state)
Reporter.starting_round(4)
Reporter.adding_requirement('grandchild<2', ('child', '1', ['grandchild<2']))
Reporter.pinning(('child', '1', ['grandchild<2']))
Reporter.ending_round(4, state)
Reporter.starting_round(5)
Reporter.pinning(('grandchild', '1', []))
Reporter.ending_round(5, state)
Reporter.starting_round(6)
Reporter.adding_requirement('child<2', ('parent', '1', ['child<2']))
Reporter.pinning(('parent', '1', ['child<2']))
Reporter.ending_round(6, state)
Reporter.starting_round(7)
Reporter.ending(State(mapping=OrderedDict([('child', ('child', '1', ['grandchild<2'])), ('grandchild', ('grandchild', '1', [])), ('parent', ('parent', '1', ['child<2']))]), criteria={'child': Criterion(('child', via=None), ('child<2', via=('parent', '1', ['child<2']))), 'parent': Criterion(('parent', via=None)), 'grandchild': Criterion(('grandchild<2', via=('child', '1', ['grandchild<2'])))}, backtrack_causes=[RequirementInformation(requirement='grandchild>=2', parent=('child', '2', ['grandchild>=2'])), RequirementInformation(requirement='grandchild<2', parent=('child', '1', ['grandchild<2']))]))To be clear, could you clarify which of |
|
Thanks for that. I'll have a look at that soon. |
|
AFAICT, the backtracking here is happening since the resolver is creating a state of (child=2, parent=1, grandchild=2) -- something that's clearly invalid -- in the first three rounds. It realises that the choices are all wrong, and then moves on to another combination -- which is an older version of child, leading to (child=1, parent=1, grandchild=1) which it creates over the next three rounds, succeeds and is returned in the 7th round. It's unclear to me what the issue here is? Is it the fact that it rejected a set of requirements containing parent=1 in the first round? The problem there isn't parent=1 alone, but that in combination with the other choices, it does not make sense. |
|
So... consider me nerd-sniped for looking into this. Here's a consistent reproducer that should work for the forseeable future, that (with pip 21.3) has enough debug logging to tell you what the resolver's doing. Run it in a clean environment, ideally; so that you don't need the In case anyone couldn't be arsed to run this but is still interested in looking at a very verbose log of the resolver's operation, see: https://gist.github.com/pradyunsg/070a7fefb7eaefa5ecf5523279b0f503 |
|
As far as I can tell, the state that gets rejected is the same as the final one. It is child=1 that is considered as a candidate, and it appears to fail because it is considered in combination with the criteria set by child=2. At least, that's how I interpret the criterion attached to the exception. |
|
So, I've been thinking about the possible implications of this some more. The example I gave above does not result in an undesired end state, so it might not be best suited to illustrate the undesired behavior that I think is going on. I've made one small adjustment that makes this come more to the foreground. If we add a third child version, lowest of all, which depends on def test_poc():
all_candidates = {
"parent": [("parent", "1", ["child<2"])],
"child": [
("child", "2", ["grandchild>=2"]),
("child", "1", ["grandchild<2"]),
("child", "0.1", ["grandchild"]),
],
"grandchild": [
("grandchild", "2", []),
("grandchild", "1", []),
],
}
class Provider(AbstractProvider):
def identify(self, requirement_or_candidate):
req = Requirement.parse(requirement_or_candidate)
assert req.key in all_candidates
return req.key
def get_preference(self, *, identifier, **_):
# prefer child over parent (alphabetically)
return identifier
def get_dependencies(self, candidate):
return candidate[2]
def find_matches(self, identifier, requirements, incompatibilities):
return (
candidate
for candidate in all_candidates[identifier]
if all(
candidate[1] in Requirement.parse(req)
for req in requirements[identifier]
)
if candidate not in incompatibilities[identifier]
)
def is_satisfied_by(self, requirement, candidate):
return candidate[1] in Requirement.parse(requirement)
resolver = Resolver(Provider(), BaseReporter())
result = resolver.resolve(["child", "parent"])
assert set(result.mapping) == {"parent", "child", "grandchild"}
assert result.mapping["parent"][1] == "1"
assert result.mapping["child"][1] == "1"
assert result.mapping["grandchild"][1] == "1"(The test fails now.) |
Actually, it's even worse: suppose there exist many newer versions of child between 1 and 2 (with the same constraint on |
|
I've extended the test case a bit more, adding a check for what I believe to be the undesired behavior. I've also added a POC fix. I can't comment on the stability of the fix yet but I believe it's quite naive at the moment. In any case, it makes the test succeed and I hope it will help illustrate exactly what I think is going wrong. from pkg_resources import Requirement
from typing import List, Sequence, Set
from resolvelib import (
AbstractProvider,
BaseReporter,
)
from resolvelib.resolvers import (
Criterion,
Resolution,
Resolver,
RequirementInformation,
RequirementsConflicted,
)
def test_poc(monkeypatch):
all_candidates = {
"parent": [("parent", "1", ["child<2"])],
"child": [
("child", "2", ["grandchild>=2"]),
("child", "1", ["grandchild<2"]),
("child", "0.1", ["grandchild"]),
],
"grandchild": [
("grandchild", "2", []),
("grandchild", "1", []),
],
}
class Provider(AbstractProvider):
def identify(self, requirement_or_candidate):
result: str = (
Requirement.parse(requirement_or_candidate).key
if isinstance(requirement_or_candidate, str)
else requirement_or_candidate[0]
)
assert result in all_candidates
return result
def get_preference(self, *, identifier, **_):
# prefer child over parent (alphabetically)
return identifier
def get_dependencies(self, candidate):
return candidate[2]
def find_matches(self, identifier, requirements, incompatibilities):
return (
candidate
for candidate in all_candidates[identifier]
if all(
candidate[1] in Requirement.parse(req)
for req in requirements[identifier]
)
if candidate not in incompatibilities[identifier]
)
def is_satisfied_by(self, requirement, candidate):
return candidate[1] in Requirement.parse(requirement)
# patch Resolution._get_updated_criteria to collect rejected states
rejected_criteria: List[Criterion] = []
get_updated_criterion_orig = Resolution._get_updated_criteria
def get_updated_criterion_patch(self, candidate) -> None:
try:
return get_updated_criterion_orig(self, candidate)
except RequirementsConflicted as e:
rejected_criteria.append(e.criterion)
raise
monkeypatch.setattr(
Resolution, "_get_updated_criteria", get_updated_criterion_patch
)
resolver = Resolver(Provider(), BaseReporter())
result = resolver.resolve(["child", "parent"])
def get_child_versions(information: Sequence[RequirementInformation]) -> Set[str]:
return {
inf[1][1]
for inf in information
if inf[1][0] == "child"
}
# verify that none of the rejected criteria are based on more than one candidate for
# child
# this check fails without the patch below
assert not any(
len(get_child_versions(criterion.information)) > 1
for criterion in rejected_criteria
)
assert set(result.mapping) == {"parent", "child", "grandchild"}
assert result.mapping["parent"][1] == "1"
# this check fails without the patch below
assert result.mapping["child"][1] == "1"
assert result.mapping["grandchild"][1] == "1"diff --git a/src/resolvelib/resolvers.py b/src/resolvelib/resolvers.py
index 787681b..458c2c8 100644
--- a/src/resolvelib/resolvers.py
+++ b/src/resolvelib/resolvers.py
@@ -199,7 +199,23 @@ class Resolution(object):
)
def _get_updated_criteria(self, candidate):
- criteria = self.state.criteria.copy()
+ # copy current state's criteria, filtering out any information with this
+ # candidate's other versions as parent
+ criteria = {
+ name: Criterion(
+ criterion.candidates,
+ [
+ information
+ for information in criterion.information
+ if (
+ information[1] is None
+ or self._p.identify(information[1]) != self._p.identify(candidate)
+ )
+ ],
+ criterion.incompatibilities,
+ )
+ for name, criterion in self.state.criteria.items()
+ }
for requirement in self._p.get_dependencies(candidate=candidate):
self._add_to_criteria(criteria, requirement, parent=candidate)
return criteriaI might be willing to work on an actual fix (I'll need to make sure I can find the time for it first) but for now I'll await some response on the above. I think it should provide sufficient input for you to determine with some confidence whether you agree with my assessment of the situation and the general direction of the fix or whether I'm way off. |
Yes. |
|
So the resolution goes:
I agree that looks weird. We're looking for conflicts, but we should never be able to have child 1 and child 2 in the resolution together, so conflicts between them can't be relevant. And the approach you're proposing to fix this seems reasonable.
It does, and I do agree with your assessment here. Thanks for your patience in explaining what you'd spotted. |
|
I was trying to test the patch given in #91 (comment) But one thing I found when running I dug a little deeper and found that for some reason when assessing |
Oh no. We should probably fix that and add a test to make sure that doesn't happen. Maybe we should also add a check in |
|
I'm cleaning up my fix to open up a pull request. I'm wondering about the last two comments. If I understand the situation correctly @uranusjr are you suggesting we should not have |
Bumps [resolvelib](https://github.com/sarugaku/resolvelib) from 0.8.1 to 1.0.1. <details> <summary>Changelog</summary> <p><em>Sourced from <a href="https://github.com/sarugaku/resolvelib/blob/main/CHANGELOG.rst">resolvelib's changelog</a>.</em></p> <blockquote> <h1>1.0.1 (2023-03-09)</h1> <h2>Bug Fixes</h2> <ul> <li>Fix calls to opaque objects and use provider interface calls instead. <code>[#126](sarugaku/resolvelib#126) <https://github.com/sarugaku/resolvelib/issues/126></code>_</li> </ul> <h1>1.0.0 (2023-03-08)</h1> <h2>Features</h2> <ul> <li>Implement backjumping to significantly speed up the resolution process by skipping over irrelevant parts of the resolution search space. <code>[#113](sarugaku/resolvelib#113) <https://github.com/sarugaku/resolvelib/issues/113></code>_</li> </ul> <h1>0.9.0 (2022-11-17)</h1> <h2>Features</h2> <ul> <li>A new reporter hook <code>rejecting_candidate</code> is added, replacing <code>backtracking</code>. The hook is called every time the resolver rejects a conflicting candidate before trying out the next one in line. <code>[#101](sarugaku/resolvelib#101) <https://github.com/sarugaku/resolvelib/issues/101></code>_</li> </ul> <h2>Bug Fixes</h2> <ul> <li>Some valid states that were previously rejected are now accepted. This affects states where multiple candidates for the same dependency conflict with each other. The <code>information</code> argument passed to <code>AbstractProvider.get_preference</code> may now contain empty iterators. This has always been allowed by the method definition but it was previously not possible in practice. <code>[#91](sarugaku/resolvelib#91) <https://github.com/sarugaku/resolvelib/issues/91></code>_</li> </ul> </blockquote> </details> <details> <summary>Commits</summary> <ul> <li><a href="https://github.com/sarugaku/resolvelib/commit/c9ef371ad96e698bf3e0bb09acc682bd43e39bd7"><code>c9ef371</code></a> Release 1.0.1</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/fb97e4c71fe520ae6d1704b7be8bd742430cd6e6"><code>fb97e4c</code></a> Add missing news fragment for patch release</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/34bb1a7474e6a45103eeb08d9bbfd1a48e1b1cd3"><code>34bb1a7</code></a> Merge pull request <a href="https://redirect.github.com/sarugaku/resolvelib/issues/127">#127</a> from sarugaku/avoid-intermediate-set</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/409bcf753074ba5b03ffd259511bf12b5d181fde"><code>409bcf7</code></a> Use itertools.chain to avoid intermediate set</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/e8fecf776aafab9104eb0d101c4de08ce3c37eaf"><code>e8fecf7</code></a> Merge pull request <a href="https://redirect.github.com/sarugaku/resolvelib/issues/126">#126</a> from sarugaku/fix-</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/5ede4c4bd205e5c61d339ba957deb44c4f5400f9"><code>5ede4c4</code></a> use set comprehension</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/7e8adca961b96c159d3391049e6a6a37e25ed525"><code>7e8adca</code></a> fix: use the protocol method instead of .name attribute</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/02fb73619d536b14b621ecddb98ad24ccd6093d2"><code>02fb736</code></a> Merge pull request <a href="https://redirect.github.com/sarugaku/resolvelib/issues/125">#125</a> from sarugaku/release/1.0</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/69ae3253545a1da31a0096686693eed5c2dee08c"><code>69ae325</code></a> Update release process</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/40c867a2b7d12e3736ccf6c621a44a1b0dbefbc7"><code>40c867a</code></a> Prebump to 1.0.1.dev0</li> <li>Additional commits viewable in <a href="https://github.com/sarugaku/resolvelib/compare/0.8.1...1.0.1">compare view</a></li> </ul> </details> <br /> [](https://docs.github.com/en/github/managing-security-vulnerabilities/about-dependabot-security-updates#about-compatibility-scores) You can trigger a rebase of this PR by commenting `@dependabot rebase`. [//]: # (dependabot-automerge-start) [//]: # (dependabot-automerge-end) --- <details> <summary>Dependabot commands and options</summary> <br /> You can trigger Dependabot actions by commenting on this PR: - `@dependabot rebase` will rebase this PR - `@dependabot recreate` will recreate this PR, overwriting any edits that have been made to it - `@dependabot merge` will merge this PR after your CI passes on it - `@dependabot squash and merge` will squash and merge this PR after your CI passes on it - `@dependabot cancel merge` will cancel a previously requested merge and block automerging - `@dependabot reopen` will reopen this PR if it is closed - `@dependabot close` will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually - `@dependabot ignore this major version` will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this minor version` will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this dependency` will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself) </details>> **Note** > Automatic rebases have been disabled on this pull request as it has been open for over 30 days.
Bumps [resolvelib](https://github.com/sarugaku/resolvelib) from 0.8.1 to 1.0.1. <details> <summary>Changelog</summary> <p><em>Sourced from <a href="https://github.com/sarugaku/resolvelib/blob/main/CHANGELOG.rst">resolvelib's changelog</a>.</em></p> <blockquote> <h1>1.0.1 (2023-03-09)</h1> <h2>Bug Fixes</h2> <ul> <li>Fix calls to opaque objects and use provider interface calls instead. <code>[#126](sarugaku/resolvelib#126) <https://github.com/sarugaku/resolvelib/issues/126></code>_</li> </ul> <h1>1.0.0 (2023-03-08)</h1> <h2>Features</h2> <ul> <li>Implement backjumping to significantly speed up the resolution process by skipping over irrelevant parts of the resolution search space. <code>[#113](sarugaku/resolvelib#113) <https://github.com/sarugaku/resolvelib/issues/113></code>_</li> </ul> <h1>0.9.0 (2022-11-17)</h1> <h2>Features</h2> <ul> <li>A new reporter hook <code>rejecting_candidate</code> is added, replacing <code>backtracking</code>. The hook is called every time the resolver rejects a conflicting candidate before trying out the next one in line. <code>[#101](sarugaku/resolvelib#101) <https://github.com/sarugaku/resolvelib/issues/101></code>_</li> </ul> <h2>Bug Fixes</h2> <ul> <li>Some valid states that were previously rejected are now accepted. This affects states where multiple candidates for the same dependency conflict with each other. The <code>information</code> argument passed to <code>AbstractProvider.get_preference</code> may now contain empty iterators. This has always been allowed by the method definition but it was previously not possible in practice. <code>[#91](sarugaku/resolvelib#91) <https://github.com/sarugaku/resolvelib/issues/91></code>_</li> </ul> </blockquote> </details> <details> <summary>Commits</summary> <ul> <li><a href="https://github.com/sarugaku/resolvelib/commit/c9ef371ad96e698bf3e0bb09acc682bd43e39bd7"><code>c9ef371</code></a> Release 1.0.1</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/fb97e4c71fe520ae6d1704b7be8bd742430cd6e6"><code>fb97e4c</code></a> Add missing news fragment for patch release</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/34bb1a7474e6a45103eeb08d9bbfd1a48e1b1cd3"><code>34bb1a7</code></a> Merge pull request <a href="https://redirect.github.com/sarugaku/resolvelib/issues/127">#127</a> from sarugaku/avoid-intermediate-set</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/409bcf753074ba5b03ffd259511bf12b5d181fde"><code>409bcf7</code></a> Use itertools.chain to avoid intermediate set</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/e8fecf776aafab9104eb0d101c4de08ce3c37eaf"><code>e8fecf7</code></a> Merge pull request <a href="https://redirect.github.com/sarugaku/resolvelib/issues/126">#126</a> from sarugaku/fix-</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/5ede4c4bd205e5c61d339ba957deb44c4f5400f9"><code>5ede4c4</code></a> use set comprehension</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/7e8adca961b96c159d3391049e6a6a37e25ed525"><code>7e8adca</code></a> fix: use the protocol method instead of .name attribute</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/02fb73619d536b14b621ecddb98ad24ccd6093d2"><code>02fb736</code></a> Merge pull request <a href="https://redirect.github.com/sarugaku/resolvelib/issues/125">#125</a> from sarugaku/release/1.0</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/69ae3253545a1da31a0096686693eed5c2dee08c"><code>69ae325</code></a> Update release process</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/40c867a2b7d12e3736ccf6c621a44a1b0dbefbc7"><code>40c867a</code></a> Prebump to 1.0.1.dev0</li> <li>Additional commits viewable in <a href="https://github.com/sarugaku/resolvelib/compare/0.8.1...1.0.1">compare view</a></li> </ul> </details> <br /> [](https://docs.github.com/en/github/managing-security-vulnerabilities/about-dependabot-security-updates#about-compatibility-scores) You can trigger a rebase of this PR by commenting `@dependabot rebase`. [//]: # (dependabot-automerge-start) [//]: # (dependabot-automerge-end) --- <details> <summary>Dependabot commands and options</summary> <br /> You can trigger Dependabot actions by commenting on this PR: - `@dependabot rebase` will rebase this PR - `@dependabot recreate` will recreate this PR, overwriting any edits that have been made to it - `@dependabot merge` will merge this PR after your CI passes on it - `@dependabot squash and merge` will squash and merge this PR after your CI passes on it - `@dependabot cancel merge` will cancel a previously requested merge and block automerging - `@dependabot reopen` will reopen this PR if it is closed - `@dependabot close` will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually - `@dependabot ignore this major version` will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this minor version` will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this dependency` will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself) </details>> **Note** > Automatic rebases have been disabled on this pull request as it has been open for over 30 days. --------- Signed-off-by: dependabot[bot] <support@github.com> Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Bumps [resolvelib](https://github.com/sarugaku/resolvelib) from 0.8.1 to 0.9.0. <details> <summary>Changelog</summary> <p><em>Sourced from <a href="https://github.com/sarugaku/resolvelib/blob/main/CHANGELOG.rst">resolvelib's changelog</a>.</em></p> <blockquote> <h1>0.9.0 (2022-11-17)</h1> <h2>Features</h2> <ul> <li>A new reporter hook <code>rejecting_candidate</code> is added, replacing <code>backtracking</code>. The hook is called every time the resolver rejects a conflicting candidate before trying out the next one in line. <code>[#101](sarugaku/resolvelib#101) <https://github.com/sarugaku/resolvelib/issues/101></code>_</li> </ul> <h2>Bug Fixes</h2> <ul> <li>Some valid states that were previously rejected are now accepted. This affects states where multiple candidates for the same dependency conflict with each other. The <code>information</code> argument passed to <code>AbstractProvider.get_preference</code> may now contain empty iterators. This has always been allowed by the method definition but it was previously not possible in practice. <code>[#91](sarugaku/resolvelib#91) <https://github.com/sarugaku/resolvelib/issues/91></code>_</li> </ul> </blockquote> </details> <details> <summary>Commits</summary> <ul> <li><a href="https://github.com/sarugaku/resolvelib/commit/a65e197764a357b64466fd9f0c05dff1d8380747"><code>a65e197</code></a> Release 0.9.0</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/262f110f67ae7791864e200bb9d03f3da3865f04"><code>262f110</code></a> Fix towncrier arg</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/ed26eb833e14083b679aa1cb30fac8ee83375087"><code>ed26eb8</code></a> Merge pull request <a href="https://redirect.github.com/sarugaku/resolvelib/issues/111">#111</a> from sanderr/issue/91-criteria-compatibility-check-fix</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/546a11f6f8d00e3b0ea71a1862bae7e8816ebdbe"><code>546a11f</code></a> added Resolution to type stub</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/6e9cf49c3d373fde265dddcc3a51dbda43d8912d"><code>6e9cf49</code></a> pep8</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/20df2c8ba8a6905b5166c931a0ae820969698894"><code>20df2c8</code></a> use packaging instead of setuptools</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/84205835e0865f078dce86990aef99e9bf583272"><code>8420583</code></a> Merge pull request <a href="https://redirect.github.com/sarugaku/resolvelib/issues/112">#112</a> from sanderr/issue/103-test-deprecation-warnings</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/3d71c81052577852df532d556f470c851d2ee885"><code>3d71c81</code></a> fixed invalid version specifiers in a test index</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/ad9eaca8a0c2f9ccff8c04186be6cff1e1d547dd"><code>ad9eaca</code></a> removed TODO</li> <li><a href="https://github.com/sarugaku/resolvelib/commit/cc1c220d0c15980fef81adaa6de336c40d6820a3"><code>cc1c220</code></a> added news fragment</li> <li>Additional commits viewable in <a href="https://github.com/sarugaku/resolvelib/compare/0.8.1...0.9.0">compare view</a></li> </ul> </details> <br /> [](https://docs.github.com/en/github/managing-security-vulnerabilities/about-dependabot-security-updates#about-compatibility-scores) Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting `@dependabot rebase`. [//]: # (dependabot-automerge-start) [//]: # (dependabot-automerge-end) --- <details> <summary>Dependabot commands and options</summary> <br /> You can trigger Dependabot actions by commenting on this PR: - `@dependabot rebase` will rebase this PR - `@dependabot recreate` will recreate this PR, overwriting any edits that have been made to it - `@dependabot merge` will merge this PR after your CI passes on it - `@dependabot squash and merge` will squash and merge this PR after your CI passes on it - `@dependabot cancel merge` will cancel a previously requested merge and block automerging - `@dependabot reopen` will reopen this PR if it is closed - `@dependabot close` will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually - `@dependabot ignore this major version` will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this minor version` will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself) - `@dependabot ignore this dependency` will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself) </details> --------- Signed-off-by: dependabot[bot] <support@github.com> Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com> Co-authored-by: Maxwell Cash <gignsky@gmail.com>
Context
While using pip, which makes use of this library, I noticed that
pip install flake8 flake8-isortresulted in backtracking over all flake8's versions, not finding a suitable candidate, followed by backtracking over flake8-isort's versions until a suitable (but very old) candidate was found there. When I looked at these projects I didn't see any reason why none of the flake8 versions would be compatible with the latest flake8-isort. Indeed, reversing the order (pip install flake8-isort) installs the latest flake8-isort and a compatible flake8 as expected, only having to backtrack once on flake8.When I noticed this seemingly inconsistent behavior I added some breakpoints to this library's code and tried to get a grasp of what was going on. I should note as a disclaimer that I haven't worked with this code before, so I might just be missing something.
Concrete
Here's a timeline of what I believe happens for
pip install flake8 flake8-isort:4.0.1at the time of writing) gets selected.flake8<4, which isn't compatible with the flake8 candidate, so we backtrack on flake8.resolvelib/src/resolvelib/resolvers.py
Lines 203 to 204 in 62c56b5
This seems to indicate that the dependency compatibility check includes the dependencies of the version we're backtracking on. Since the currently selected flake8 has a dependency constraint which is incompatible with the constraints for all older versions, backtracking fails. In practice, the latest
flake8<4is compatible with the rest of the current criteria.The text was updated successfully, but these errors were encountered: