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: pdm-project/pdm#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:

resolvelib/src/resolvelib/resolvers.py

Lines 317 to 318 in 77b256c

	except (IndexError, KeyError):
	raise ResolutionImpossible(causes) from None

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 #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: pypa/pip#12376 (comment)

Although in that case not the same exception triggers.

[notatallshaw]

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:

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: pypa/pip#12376 (comment)

[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, #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.

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