An example of resolution failure while it does have a valid resolution.

[frostming]

Run resolution on this requirement will result in a failure:

pandas
pystac   # removing this line will resolve successfully
pystac-client
sat-stac

While it does have a valid resolution if you remove the second dep but it is in the final resolution:

pandas
pystac-client
sat-stac

Which resolves to:

pandas==1.3.5
pystac==1.8.3
pystac-client==0.6.1
sat-stac==0.4.1

It seems an issue with the backtracking process.

Original report: https://github.com/pdm-project/pdm/issues/2193

[notatallshaw]

I can reproduce both steps on Pip 23.2.1 Python 3.9 on Linux.

The resolution impossible gives the error:

ERROR: Cannot install -r requirements.txt (line 3) and pystac because these package versions have conflicting dependencies.

The conflict is caused by:
    The user requested pystac
    pystac-client 0.6.1 depends on pystac>=1.7.0

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.

[frostming]

Actually it falls into this branch: https://github.com/sarugaku/resolvelib/blob/77b256cdfb747e86112025d75cd698861ce355a5/src/resolvelib/resolvers.py#L317-L318

Where the causes are related to pystac, specifically, all versions of pystac have been marked as incompatible.

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.

[notatallshaw]

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:

pandas
pystac
pystac-client
sat-stac

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))

[notatallshaw]

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 self.states doesn't grow nearly as large:

pandas>=1.3.5,<=1.4.0
pystac>=1.8.2,<=1.8.3
pystac-client>=0.3.2,<=0.6.1
sat-stac<=0.4.1

Notice that these requirements succeeds:

pandas>=1.3.5,<=1.4.0
pystac>=1.8.2,<=1.8.3
pystac-client>=0.3.2,<=0.6.1
sat-stac>=0.1.1,<=0.4.1

And:

pandas>=1.3.5,<=1.4.0
pystac>=1.8.2,<=1.8.3
pystac-client>=0.3.3,<=0.6.1
sat-stac<=0.4.1

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

[notatallshaw]

An even tighter set of requirements, this resolves:

pandas==1.3.5
pystac==1.8.3
pystac-client==0.3.3
sat-stac==0.1.1

This does not:

pandas>=1.3.5,<=1.4.0
pystac>=1.8.2,<=1.8.3
pystac-client>=0.3.2,<=0.3.3
sat-stac<=0.1.1

Not sure any of this is helpful but at the begining of the method _backjump the this is what the causes object looks like:

[
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/)'))])
]

[notatallshaw]

So, this issue appears to be that backjumping as implemented by https://github.com/sarugaku/resolvelib/pull/113 is incorrectly discarding state.

I beleive this also causes Pip 23.3 to fail to install kedro[test]==0.18.13, I have tested reverting the backjumping optimization in Pip and it correctly installs: https://github.com/pypa/pip/issues/12376#issuecomment-1786140131

Although in that case not the same exception triggers.

[notatallshaw]

Experimenting tonight with the examples a bit I beleive the assumptions in https://github.com/sarugaku/resolvelib/pull/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:

1. The provides causes are too wide and cover things which might not currently be an issue
2. Or, because resolverlib eagerly adds criteria to each state the backjumps in state are too far

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.

[notatallshaw]

Another triggering requirement, at least in Pip 23.2.1: "aicsimageio==4.9.1" "napari-aicsimageio==0.7.2" "napari"

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: https://github.com/pypa/pip/issues/12376#issuecomment-1788232379

[jspri]

The requirements I hit this bug with were "boto3>=1.28.64,<1.28.66" "dagster==1.5.5" "pandas[aws]==2.1.2" "dagster-aws>=0.21.5" .

Narrowing the packages to either boto3==1.28.64 or dagster-aws==0.21.5 causes it to resolve.

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.

[frostming]

@notatallshaw 's solution seems a viable way to fix it, can you make a PR please?

[notatallshaw]

@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.

[notatallshaw]

The requirements I hit this bug with were "boto3>=1.28.64,<1.28.66" "dagster==1.5.5" "pandas[aws]==2.1.2" "dagster-aws>=0.21.5" .

Can you please provide more context on your set-up, I was able to reproduce the ResolutionImpossible on Python 3.10 by updating the requirements to "boto3>=1.28.64,<1.28.66" "dagster==1.5.5" "pandas[aws]==2.1.2" "dagster-aws>=0.21.5" "PyYAML>=6.0.1" and getting this error:

ERROR: Cannot install dagster-aws==0.21.6, dagster-aws==0.21.7 and dagster==1.5.5 because these package versions have conflicting dependencies.

The conflict is caused by:
    The user requested dagster==1.5.5
    dagster-aws 0.21.7 depends on dagster==1.5.7
    The user requested dagster==1.5.5
    dagster-aws 0.21.6 depends on dagster==1.5.6

And it does look like backjumping is the issue, it seems to jump over the valid requirement dagster-aws==0.21.5, but I haven't been able to proove backjumping is the issue yet because removing backjumping from Pip caused this resolution to reach ResolutionTooDeep. If you have some more context it may be helpful on prooving it definitively.

[jspri]

@notatallshaw Oh weird, I've never hit the too deep problem.

The only other context I have is:

• "boto3" "dagster==1.5.5" "pandas[aws]==2.1.2" "dagster-aws>=0.21.5" fails, this uses a fully unspecified boto3 version, before I had the range for faster resolution
• Changing the order can cause it to pass e.g "dagster==1.5.5" "pandas[aws]==2.1.2" "dagster-aws>=0.21.5" "boto3"
• "dagster==1.5.5" "pandas[aws]==2.1.2" "dagster-aws>=0.21.5" passes (no boto3 specified but it's still part of the dependency tree)
• There are a few other combinations I've tried but in general ranges seem to break things and exact versions seem to work

I'm using pip 23.3.1 (python 3.11). An example full resolution is

Would install Jinja2-3.1.2 Mako-1.3.0 MarkupSafe-2.1.3 PyYAML-6.0.1 SQLAlchemy-2.0.23 aiobotocore-2.7.0 aiohttp-3.8.6 aioitertools-0.11.0 aiosignal-1.3.1 alembic-1.12.1 annotated-types-0.6.0 async-timeout-4.0.3 attrs-23.1.0 boto3-1.28.64 botocore-1.31.64 click-8.1.7 coloredlogs-14.0 croniter-2.0.1 dagster-1.5.5 dagster-aws-0.21.5 dagster-pipes-1.5.5 docstring-parser-0.15 frozenlist-1.4.0 fsspec-2023.10.0 greenlet-3.0.1 grpcio-1.59.2 grpcio-health-checking-1.59.2 humanfriendly-10.0 jmespath-1.0.1 multidict-6.0.4 numpy-1.26.2 pandas-2.1.2 pendulum-2.1.2 protobuf-4.25.0 psutil-5.9.6 pydantic-2.4.2 pydantic_core-2.10.1 pyreadline3-3.4.1 python-dateutil-2.8.2 python-dotenv-1.0.0 pytz-2023.3.post1 pytzdata-2020.1 pywin32-306 s3fs-2023.10.0 s3transfer-0.7.0 tabulate-0.9.0 tomli-2.0.1 toposort-1.10 tqdm-4.66.1 typing_extensions-4.8.0 tzdata-2023.3 universal-pathlib-0.1.4 watchdog-3.0.0 wrapt-1.16.0 yarl-1.9.2

[jspri]

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 ResolutionTooDeep that you mentioned and that I couldn't get with pip.

This changes to ResolutionImpossible if I specify max_rounds=200 in the test runner. This is all with backtracking still enabled.

[notatallshaw]

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, https://github.com/sarugaku/resolvelib/pull/142 reverts backjumping, https://github.com/sarugaku/resolvelib/pull/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, https://github.com/pypa/pip/pull/12459 (with the accompining resolvelib PR https://github.com/sarugaku/resolvelib/pull/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.

[frostming]

@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.

[notatallshaw]

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.

[pfmoore]

it needs inputs from the pip maintainers for the final decision

@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:

1. I’d prefer a general solution over one that only fixed the issue for pip (but I’d have expected the resolvelib maintainers to be arguing for that anyway).
2. I’d prefer a solution that didn’t ask the caller to choose between trade-offs. The resolution problem is hard enough that I prefer as much as possible to treat resolvelib as a “black box” and just say “go off and do it for me”.

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.

[notatallshaw]

I have been unhappy with either of the two PRs I created that workaround this bug, I have therefore been working on trying to make a significantly simpler reproducer that a test can be written against, and hopefully find the underlying cause.

Therefore I have worked on creating a minimal pip-resolver-benchmarks scenario that produces the same error for a resolvable scenario. And here it is:

{
  "input": {
    "requirements": [
      "pandas<=1.4.0,>=1.3.5",
      "pystac<=1.8.3,>=1.8.2",
      "pystac-client<=0.3.3,>=0.3.2",
      "sat-stac<=0.1.1"
    ],
    "timestamp": "2024-05-12T15:44:05.521946",
    "allow_sdists_for": [],
    "environment": {
      "markers": {
        "implementation_name": "cpython",
        "implementation_version": "3.9.19",
        "os_name": "posix",
        "platform_machine": "x86_64",
        "platform_release": "5.15.146.1-microsoft-standard-WSL2",
        "platform_system": "Linux",
        "platform_version": "#1 SMP Thu Jan 11 04:09:03 UTC 2024",
        "python_full_version": "3.9.19",
        "platform_python_implementation": "CPython",
        "python_version": "3.9",
        "sys_platform": "linux"
      },
      "tags": [
        "py39-none-any"
      ]
    }
  },
  "packages": {
    "pandas": {
      "1.4.0": {
        "depends_by_extra": {
          "": [
            "python-dateutil>=2.8.1"
          ]
        }
      },
      "1.3.5": {
        "depends_by_extra": {
          "": [
            "python-dateutil>=2.7.3"
          ]
        }
      }
    },
    "pystac": {
      "1.8.3": {
        "depends_by_extra": {
          "": [
            "python-dateutil>=2.7.0"
          ]
        }
      },
      "1.8.2": {
        "depends_by_extra": {
          "": [
            "python-dateutil>=2.7.0"
          ]
        }
      }
    },
    "pystac-client": {
      "0.3.3": {
        "depends_by_extra": {
          "": [
            "requests>=2.25",
            "pystac>=1.4.0"
          ]
        }
      },
      "0.3.2": {
        "depends_by_extra": {
          "": [
            "requests>=2.25",
            "pystac~=1.2.0"
          ]
        }
      }
    },
    "sat-stac": {
      "0.1.1": {
        "depends_by_extra": {
          "": [
            "python-dateutil~=2.7.5"
          ]
        }
      },
      "0.1.0": {
        "depends_by_extra": {
          "": [
            "requests~=2.19.1",
            "python-dateutil~=2.7.5"
          ]
        }
      }
    },
    "python-dateutil": {
      "2.9.0": {
        "depends_by_extra": {}
      },
      "2.7.5": {
        "depends_by_extra": {}
      }
    },
    "requests": {
      "2.31.0": {
        "depends_by_extra": {}
      }
    }
  }
}

I had planned to turn it into a packse scenario and then debug pip against the index packse provides, but so far I have not been able to reproduce the error with packse. I am going to work on breaking about pip-resolver-benchmarks so I can use it to provide the wheels and independently run pip against those wheels it provides.

[notatallshaw]

Okay, I am now able to reproduce this without running via nox. In the pip-resolver-benchmarks repo, where the above scenario is in the file scenarios/resolvelib-bug.json run:

$ python src/create-wheels.py resolvelib-bug--output-dir-base wheels

Then you can run the scenario with:

python -m pip install --index-url file://$PWD/wheels/pip-resolver-benchmarks --disable-pip-version-check --dry-run --ignore-installed  "pandas<=1.4.0,>=1.3.5" "pystac<=1.8.3,>=1.8.2" "pystac-client<=0.3.3,>=0.3.2" "sat-stac<=0.1.1"

Which produces the bug (and is independant of the Python version you use):

ERROR: Cannot install pystac-client==0.3.2 and pystac<=1.8.3 and >=1.8.2 because these package versions have conflicting dependencies.

I have a hunch what the issue is and applied that hunch and this and other scenarios are now correctly resolving, and it's not a hacky workaround or removing backjumping entirely.

But before I post a PR I want to carefully walk through each step, gain a strong intuitive understanding, recreate the scenario in packse, and have a good idea how to write a test for it. So I expect it to take at least a few days, if someone wants to beat me to the punch and post a PR first I'll happily test it.

[notatallshaw]

A PR is ready to review: https://github.com/sarugaku/resolvelib/pull/152

[notatallshaw]

So https://github.com/sarugaku/resolvelib/pull/152 fixes the original example, but not kedro[test]==0.18.13.

I have been able to reproduce kedro[test]==0.18.13 with pip-resolver-benchmarks and am working on creating a minal example so try and find the issue, but I have a hunch now what the problem is and I think it's going to be a more complicated to fix than https://github.com/sarugaku/resolvelib/pull/152, so perhaps it should be put in as a seperate PR.

[notatallshaw]

As I've looked deeper into kedro[test]==0.18.13 I've started to beleive that in general backjumping is unsound within resolvelib, I have added two test cases here that demonstrate that: https://github.com/sarugaku/resolvelib/pull/154

I've written more on that PR, but I beleive backjumping should either be reverted or made opt-in.

[uranusjr]

Is it worthwhile to try backjumping, and revert to backtracking if it yields no results?

[notatallshaw]

Is it worthwhile to try backjumping, and revert to backtracking if it yields no results?

I think it would generally work but there are a few issues:

1. Where do you revert to? The very beginning or somewhere else? I tried made an intelligent PR but it's non-trivial: https://github.com/sarugaku/resolvelib/pull/144. I would be happy to revive it with the now additional test cases if that was right to be the best way forward
2. Any genuine ResolutionImpossible is now potentially twice as long
3. The provider could have costly side effects for visiting candidates or only be able to visit them once, but now there would be situations where they are visited twice

[uranusjr]

I’m thinking reverting to where the first backjump happens (so all the way back I guess?)

The second point is the deciding point. Whether this is worthwhile probably depends on how much faster backjumping is than simple backtracking. Say it is 90% faster, the fall-back would cause a 10% slowdown in the worst case (than backtracking—I don’t think keeping the current implementation is viable at this point), which should be definitely worwhile. If it’s just 10% faster, the slowdown would be 90% and definitely not worthwhile. The real value is probably somewhere in between. We should probably investigate some examples, but I’m wondering if you have a ballpark idea we can use to make a quick decision from.

[notatallshaw]

I’m thinking reverting to where the first backjump happens (so all the way back I guess?)

Not quite sure that you mean, here are the possible points where it makes sense to me to revert to:

1. The very beginning (clear all state and start over)
2. After all direct dependencies have been collected (the end of the BFS but before DFS begins)
3. The state before the first time a "backtrack" happens
4. The state before the first time a "backjump" happens (i.e. more than one backtrack happens in the backjump loop)

My PR implemented the last one, as anything after this point is logically unsound.

The second point is the deciding point. Whether this is worthwhile probably depends on how much faster backjumping is than simple backtracking. Say it is 90% faster, the fall-back would cause a 10% slowdown in the worst case (than backtracking—I don’t think keeping the current implementation is viable at this point), which should be definitely worwhile. If it’s just 10% faster, the slowdown would be 90% and definitely not worthwhile

Thinking on this, there are two perspectives on the impact it has:

1. The ResolutionImpossible is assumed to be suspect and therefore backtracking must happen to confirm it (the perspective you've outlined here)
2. The provider is confident they are fulfilling the implicit contract backjumping has created and the ResolutionImpossible is valid and therefore backtracking is a waste of time

From perspective 1, the worst case scenario is the revert point is near the beginning of the resolution, but otherwise the resolution doesn't make much difference, and therefore reverting from backjumping to backtracking to confirm a resolution impossible doubles the amount of time, and the best case scenario is the revert point is near the end of the resolution and reverting to confirm resolution time is negligible.

From perspective 2 however, the worst case is this can turn confirmed impossible resolutions from completing quickly to taking effectively an infinite amount of time. If users like @bennati believe backjumping is not unsound for their provider then it makes sense to add an opt-out of reverting and falling back to backtracking.

We should probably investigate some examples, but I’m wondering if you have a ballpark idea we can use to make a quick decision from.

I can work on collecting some real world benchmarks of valid ResolutionImpossibles, but my concern is there is no simple relationship between a dependency graph and performance impact, very small changes can turn simple resolutions into pathological examples. So it will be hard to treat any sort of data collection as much more than anecdotal.

[uranusjr]

I was thinking 4 too so most of the reasoning you made above makes sense to me. Personally I feel we should lean toward correctness than speed so if we can’t reliably ensure backjumping is logically correct, and doing the resolution twice (BJ + BT) takes too much additional time than simply BT, I would prefer to remove BJ entirely.

If BJ is still mostly valuable for people, maybe we can treat BJ like compiler optimisations—optional, and if you turn it on we don’t promise it always does the right thing, but it should mostly do a good enough job to be worthwhile.

[notatallshaw]

Oh, in general terms of resolutions, there are definitely resolutions that will not complete if back jumping is removed because they will take too long.

At least, until pip prefers directly conflicting dependencies, which will have a similar performance improvement for pathological examples as back jumping has. And I believe that back jumping is actually sound once pip (the provider) prefers directly conflicting dependencies.

[notatallshaw]

And sorry if I wasn't clear on this before, but backjumping within itself is sound in the context of dependency resolution. I'm just saying it requires the provder to make the "correct" preferences while backtracking, and resolvelib has no way of enforcing, or even checking, it is doing that.

[pfmoore]

Could we not simply document that the provider must do this? I've only been following this discussion at a high level, but I'd rather have an efficient algorithm that places some requirements on providers over something that's less efficient but handles every possible case.

If this means requiring https://github.com/pypa/pip/pull/12459, then I'm fine with that - although as I said in that PR, I'd like resolvelib to document clearly what it expects from providers, so we don't end up with tight coupling between pip and resolvelib because no-one else can work out how to write a conforming provider 😉

[notatallshaw]

It's certainly an option, but currently none of resolvelib's test providers implement it, the pip test provider would need to be updated at least, which I can work on, so it can pass at least the tests in https://github.com/sarugaku/resolvelib/pull/154.

Also, in resolvelib's current API design, I don't beleive it's possible for the provider to always prefer directly conflicting conflicts without introducing a new O(n²) issue. And my proposed fix to avoid O(n²) is https://github.com/sarugaku/resolvelib/pull/145, which I had planned to work on after "fixing backjumping", but I guess it could all be part of the same thing.

[notatallshaw]

Okay, I think I found an actual logical fix: https://github.com/sarugaku/resolvelib/pull/155