-
Notifications
You must be signed in to change notification settings - Fork 30
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
An example of resolution failure while it does have a valid resolution. #134
Comments
I can reproduce both steps on Pip 23.2.1 Python 3.9 on Linux. The resolution impossible gives the error:
Which is certainly weird, here is the debug output: https://gist.github.com/notatallshaw/f39c7986aa81fb05ee3a710787484551 I took a quick look now to see if the issue is related to specifiers rather than resolvelib, but I didn't get very far. I can investigate more in a couple of days if someone hasn't figured it out by then. |
Actually it falls into this branch: resolvelib/src/resolvelib/resolvers.py Lines 317 to 318 in 77b256c
Where the causes are related to To fix this, we should considered a less hard fail for this case, for example, when no state is found, just pop the last pin. |
I tested this on Pip directly by creating a copy the States ahead of time and if backjumping fails falling back to the old backtracking by restoring the state and doing the backtrack. It appears to fix this situation, it can correctly resolve:
But I do not have the knowledge of how backjumping is working to be confident to raise a PR or know what tests to add, there is also probably a far more elegant approach to this. So here is the patch if anyone wants to adapt this specific approach this code is free to use: diff --git a/src/pip/_vendor/resolvelib/resolvers.py b/src/pip/_vendor/resolvelib/resolvers.py
index 2c3d0e306..e63377c8e 100644
--- a/src/pip/_vendor/resolvelib/resolvers.py
+++ b/src/pip/_vendor/resolvelib/resolvers.py
@@ -307,22 +307,31 @@ class Resolution(object):
# Remove the state that triggered backtracking.
del self._states[-1]
- # Ensure to backtrack to a state that caused the incompatibility
- incompatible_state = False
- while not incompatible_state:
- # Retrieve the last candidate pin and known incompatibilities.
- try:
+ _states_backup = [
+ State(s.mapping.copy(), s.criteria.copy(), s.backtrack_causes[:])
+ for s in self._states
+ ]
+ try:
+ # Ensure to backtrack to a state that caused the incompatibility
+ incompatible_state = False
+ while not incompatible_state:
+ # Retrieve the last candidate pin and known incompatibilities.
broken_state = self._states.pop()
name, candidate = broken_state.mapping.popitem()
- except (IndexError, KeyError):
- raise ResolutionImpossible(causes)
- current_dependencies = {
- self._p.identify(d)
- for d in self._p.get_dependencies(candidate)
- }
- incompatible_state = not current_dependencies.isdisjoint(
- incompatible_deps
- )
+ current_dependencies = {
+ self._p.identify(d)
+ for d in self._p.get_dependencies(candidate)
+ }
+ incompatible_state = not current_dependencies.isdisjoint(
+ incompatible_deps
+ )
+ except (IndexError, KeyError):
+ # Backjumping failed, so fall back to backtrack where
+ # we just pop the previous state
+ self._states = _states_backup
+ broken_state = self._states.pop()
+ name, candidate = broken_state.mapping.popitem()
+ del _states_backup
incompatibilities_from_broken = [
(k, list(v.incompatibilities))
|
I created this much more tighly bounded set of requirements that fails when it shouldn't, it should be relatively resistent to any changes on PyPi and hopefully easier to debug as
Notice that these requirements succeeds:
And:
I also notice in the original PR @pradyunsg made a comment about this exception: https://github.com/sarugaku/resolvelib/pull/113/files#r1097012024 but closed it without any interaction from the PR author @bennati |
An even tighter set of requirements, this resolves:
This does not:
Not sure any of this is helpful but at the begining of the method [
RequirementInformation(requirement=SpecifierRequirement('pystac<=1.8.3,>=1.8.2'), parent=None),
RequirementInformation(requirement=SpecifierRequirement('pystac~=1.2.0'), parent=LinkCandidate('https://files.pythonhosted.org/packages/ff/a3/f0e871f97d77ac638b58f634dfa545aca5f866d2310a299b1eb1a51e84f2/pystac_client-0.3.2-py3-none-any.whl (from https://pypi.org/simple/pystac-client/) (requires-python:>=3.7)'))
] And this is what self.states looks like: [
State(mapping=OrderedDict(), criteria={'pandas': Criterion((SpecifierRequirement('pandas<=1.4.0,>=1.3.5'), via=None)), 'pystac': Criterion((SpecifierRequirement('pystac<=1.8.3,>=1.8.2'), via=None)), 'pystac-client': Criterion((SpecifierRequirement('pystac-client<=0.3.3,>=0.3.2'), via=None)), 'sat-stac': Criterion((SpecifierRequirement('sat-stac<=0.1.1'), via=None))}, backtrack_causes=[]),
State(mapping=OrderedDict([('pandas', LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))]), criteria={'pandas': Criterion((SpecifierRequirement('pandas<=1.4.0,>=1.3.5'), via=None)), 'pystac': Criterion((SpecifierRequirement('pystac<=1.8.3,>=1.8.2'), via=None)), 'pystac-client': Criterion((SpecifierRequirement('pystac-client<=0.3.3,>=0.3.2'), via=None)), 'sat-stac': Criterion((SpecifierRequirement('sat-stac<=0.1.1'), via=None)), 'python-dateutil': Criterion((SpecifierRequirement('python-dateutil>=2.8.1'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), 'pytz': Criterion((SpecifierRequirement('pytz>=2020.1'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), 'numpy': Criterion((SpecifierRequirement('numpy>=1.18.5; platform_machine != "aarch64" and platform_machine != "arm64" and python_version < "3.10"'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), '<Python from Requires-Python>': Criterion((RequiresPythonRequirement('>=3.8'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')))}, backtrack_causes=[]),
State(mapping=OrderedDict([('pandas', LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')), ('<Python from Requires-Python>', <pip._internal.resolution.resolvelib.candidates.RequiresPythonCandidate object at 0x7fd6585e33a0>)]), criteria={'pandas': Criterion((SpecifierRequirement('pandas<=1.4.0,>=1.3.5'), via=None)), 'pystac': Criterion((SpecifierRequirement('pystac<=1.8.3,>=1.8.2'), via=None)), 'pystac-client': Criterion((SpecifierRequirement('pystac-client<=0.3.3,>=0.3.2'), via=None)), 'sat-stac': Criterion((SpecifierRequirement('sat-stac<=0.1.1'), via=None)), 'python-dateutil': Criterion((SpecifierRequirement('python-dateutil>=2.8.1'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), 'pytz': Criterion((SpecifierRequirement('pytz>=2020.1'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), 'numpy': Criterion((SpecifierRequirement('numpy>=1.18.5; platform_machine != "aarch64" and platform_machine != "arm64" and python_version < "3.10"'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), '<Python from Requires-Python>': Criterion((RequiresPythonRequirement('>=3.8'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')))}, backtrack_causes=[]),
State(mapping=OrderedDict([('pandas', LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')), ('<Python from Requires-Python>', <pip._internal.resolution.resolvelib.candidates.RequiresPythonCandidate object at 0x7fd6585e33a0>), ('pystac', LinkCandidate('https://files.pythonhosted.org/packages/d2/35/efb3ada4f8db776144d786338a41d38e5128f2c1e4a86b681c658fe1151e/pystac-1.8.3-py3-none-any.whl (from https://pypi.org/simple/pystac/) (requires-python:>=3.8)'))]), criteria={'pandas': Criterion((SpecifierRequirement('pandas<=1.4.0,>=1.3.5'), via=None)), 'pystac': Criterion((SpecifierRequirement('pystac<=1.8.3,>=1.8.2'), via=None)), 'pystac-client': Criterion((SpecifierRequirement('pystac-client<=0.3.3,>=0.3.2'), via=None)), 'sat-stac': Criterion((SpecifierRequirement('sat-stac<=0.1.1'), via=None)), 'python-dateutil': Criterion((SpecifierRequirement('python-dateutil>=2.8.1'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')), (SpecifierRequirement('python-dateutil>=2.7.0'), via=LinkCandidate('https://files.pythonhosted.org/packages/d2/35/efb3ada4f8db776144d786338a41d38e5128f2c1e4a86b681c658fe1151e/pystac-1.8.3-py3-none-any.whl (from https://pypi.org/simple/pystac/) (requires-python:>=3.8)'))), 'pytz': Criterion((SpecifierRequirement('pytz>=2020.1'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), 'numpy': Criterion((SpecifierRequirement('numpy>=1.18.5; platform_machine != "aarch64" and platform_machine != "arm64" and python_version < "3.10"'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), '<Python from Requires-Python>': Criterion((RequiresPythonRequirement('>=3.8'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')), (RequiresPythonRequirement('>=3.8'), via=LinkCandidate('https://files.pythonhosted.org/packages/d2/35/efb3ada4f8db776144d786338a41d38e5128f2c1e4a86b681c658fe1151e/pystac-1.8.3-py3-none-any.whl (from https://pypi.org/simple/pystac/) (requires-python:>=3.8)')))}, backtrack_causes=[]),
State(mapping=OrderedDict([('pandas', LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')), ('<Python from Requires-Python>', <pip._internal.resolution.resolvelib.candidates.RequiresPythonCandidate object at 0x7fd6585e33a0>), ('pystac', LinkCandidate('https://files.pythonhosted.org/packages/d2/35/efb3ada4f8db776144d786338a41d38e5128f2c1e4a86b681c658fe1151e/pystac-1.8.3-py3-none-any.whl (from https://pypi.org/simple/pystac/) (requires-python:>=3.8)'))]), criteria={'pandas': Criterion((SpecifierRequirement('pandas<=1.4.0,>=1.3.5'), via=None)), 'pystac': Criterion((SpecifierRequirement('pystac<=1.8.3,>=1.8.2'), via=None)), 'pystac-client': Criterion((SpecifierRequirement('pystac-client<=0.3.3,>=0.3.2'), via=None)), 'sat-stac': Criterion((SpecifierRequirement('sat-stac<=0.1.1'), via=None)), 'python-dateutil': Criterion((SpecifierRequirement('python-dateutil>=2.8.1'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')), (SpecifierRequirement('python-dateutil>=2.7.0'), via=LinkCandidate('https://files.pythonhosted.org/packages/d2/35/efb3ada4f8db776144d786338a41d38e5128f2c1e4a86b681c658fe1151e/pystac-1.8.3-py3-none-any.whl (from https://pypi.org/simple/pystac/) (requires-python:>=3.8)'))), 'pytz': Criterion((SpecifierRequirement('pytz>=2020.1'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), 'numpy': Criterion((SpecifierRequirement('numpy>=1.18.5; platform_machine != "aarch64" and platform_machine != "arm64" and python_version < "3.10"'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)'))), '<Python from Requires-Python>': Criterion((RequiresPythonRequirement('>=3.8'), via=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')), (RequiresPythonRequirement('>=3.8'), via=LinkCandidate('https://files.pythonhosted.org/packages/d2/35/efb3ada4f8db776144d786338a41d38e5128f2c1e4a86b681c658fe1151e/pystac-1.8.3-py3-none-any.whl (from https://pypi.org/simple/pystac/) (requires-python:>=3.8)')))}, backtrack_causes=[RequirementInformation(requirement=SpecifierRequirement('python-dateutil>=2.8.1'), parent=LinkCandidate('https://files.pythonhosted.org/packages/eb/fa/6cbc442e86f625dc403fbceb79e869893fc09486cfba79bd4ba33e366293/pandas-1.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (from https://pypi.org/simple/pandas/) (requires-python:>=3.8)')), RequirementInformation(requirement=SpecifierRequirement('python-dateutil>=2.7.0'), parent=LinkCandidate('https://files.pythonhosted.org/packages/d2/35/efb3ada4f8db776144d786338a41d38e5128f2c1e4a86b681c658fe1151e/pystac-1.8.3-py3-none-any.whl (from https://pypi.org/simple/pystac/) (requires-python:>=3.8)')), RequirementInformation(requirement=SpecifierRequirement('python-dateutil~=2.7.5'), parent=LinkCandidate('https://files.pythonhosted.org/packages/4a/2b/558c882901d6c6d2593673d434141b915c80f11819290be2fe564d891296/sat-stac-0.1.1.tar.gz (from https://pypi.org/simple/sat-stac/)')), RequirementInformation(requirement=SpecifierRequirement('requests>=2.25'), parent=LinkCandidate('https://files.pythonhosted.org/packages/97/6b/8d156f9d1fefbf56cecaa5e4907910758fe9e4496c1868befbbf56bdb778/pystac_client-0.3.3-py3-none-any.whl (from https://pypi.org/simple/pystac-client/) (requires-python:>=3.7)')), RequirementInformation(requirement=SpecifierRequirement('requests~=2.19.1'), parent=LinkCandidate('https://files.pythonhosted.org/packages/93/70/0e9b2768c16b9de617946e0f89c31f90dfba9752fe65b5c8068a83d5c144/sat-stac-0.1.0.tar.gz (from https://pypi.org/simple/sat-stac/)'))])
] |
So, this issue appears to be that backjumping as implemented by #113 is incorrectly discarding state. I beleive this also causes Pip 23.3 to fail to install Although in that case not the same exception triggers. |
Experimenting tonight with the examples a bit I beleive the assumptions in #113 that you can safely discard state until there are no intersection between the causes and the now current dependencies is fault for two possible reasons:
This is all currently speculation and I'm just sharing in the hopes the issue is more obvious to someone else, I'll try and investigate further when I have time. |
Another triggering requirement, at least in Pip 23.2.1: It no longer occurs in Pip 23.3 but that is because of optimizations applied on Pip side that seems to side step this issue for this specific set of requirements, details of testing here: pypa/pip#12376 (comment) |
The requirements I hit this bug with were Narrowing the packages to either I've spent a fair chunk of the weekend trying to setup a test case, I think my first stop might be to make some adjustments to py2index. |
@notatallshaw 's solution seems a viable way to fix it, can you make a PR please? |
I don't think it is actually, it only works in the case that the incorrect backjumping is the one that causes states or state.mapping to be exhausted. However other than the initial example it seems the incorrect backjumping skips over a valid state earlier in the resolution process, meaning that this specific error doesn't raise but you still get a resolution impossible incorrectly. My plan currently is to take another look at it this week and if I can't figure out a patch that works for all found cases I was going create a PR to revert backjumping out of resolvelib. |
Can you please provide more context on your set-up, I was able to reproduce the
And it does look like backjumping is the issue, it seems to jump over the valid requirement |
@notatallshaw Oh weird, I've never hit the too deep problem. The only other context I have is:
I'm using
|
Here's a zip that contains an index file that can be used for the test (it took a few days of crawling to generate). With this I was able to recreate the This changes to |
I am looking for some feedback from resolvelib maintainers, @frostming @pradyunsg @uranusjr, I have multiple solutions and don't have a strong opinion on which one should be implemented, I am happy to answer questions and gather data but there are basically 4 different options and I don't want to waste time on options never going to happen. Here is the current state: There are two PRs that directly address the issue on resolvelib side, #142 reverts backjumping, #144 adds a fallback of backjumping to backtracking in a relatively simple way without having to start the whole process over from the begining. There are two coupled PRs that indirectly address the issue but for Pip only, pypa/pip#12459 (with the accompining resolvelib PR #145), this seems to cause Pip to choose the causes in a way that satisfies the backjumping assumptions about conflicts (or at least I can no longer reproduce this issue with that PR) and it also improves the performance of Pip that removing backjumping is not a significant performance degradation. This leads me to think of a third PR I could raise for resolvelib, one that gives the calling library a switch of whether to choose backtracking or backjumping, and leave it up to the calling library to decide whether they can trust the implict assumptions of backjumping and how they provide their dependency graph and prefer causes not to cause an incorrect ResolutionImpossibles. |
@notatallshaw Thanks for all the efforts you have put into addressing this problem. I personally like the fallback approach. I also would like to review your PRs and leave some comments, but it needs inputs from the pip maintainers for the final decision since resolvelib is a significant component of it. However, they haven't shown up for unknown reasons but let's be patient. |
Sounds good, no worries. I think everyone has just got busy outside of OSS work. Pip is seemingly precariously resource constrained, I wouldn't be able to add much time either if I was an OSS maintainer. If I have some time I will turn my attention back to the fallback solution to see if there's any simplifications or other improvements I can make. |
@frostming can you clarify what you need from the pip maintainers? I don’t have an in-depth understanding of the resolver algorithms, so I can’t give a view on the technicalities. What I can say is:
Beyond that, I have no view unless you have specific questions. In particular, I’d leave it you you to decide between the two “resolvelib only” options. |
Run resolution on this requirement will result in a failure:
While it does have a valid resolution if you remove the second dep but it is in the final resolution:
Which resolves to:
It seems an issue with the backtracking process.
Original report: pdm-project/pdm#2193
The text was updated successfully, but these errors were encountered: