I am implementing a resolver for Python packages, which needs to support extras. Unfortunately, verifying if a candidate archive provides a specified extra is expensive, as I need to download the archive and possible build a wheel, and that is required to make sure the candidate is valid.

The thing is, the resolver will only choose one version and try to work with that, only passing the next one if there are incompatibilities.

Would it make sense to add a is_valid_candidate method, or something similar, that the resolver would call before trying to work with a candidate?
For backwards compatibility, we should provide a default implementation would always validate.

This issue in particular should be somewhat mitigated by https://www.python.org/dev/peps/pep-0658/, but that is still a draft, but there would still be cases where the metadata could be dynamic, where I would have to download the sdist and build the wheels.
I expect some users with other use-cases to be in a similar situation.

See #17 (comment)

The ResolutionImpossible was thrown here, during when we go through the candidates to find one that satisfies all existing constraints. Currently we give up when all candidates fail. We should instead backtrack (pop the state stack and remove the last pinned candidate) and keep trying.

gel is a in-development new package manager for Ruby (mentioned in pypa/pip#7406).

https://github.com/gel-rb/gel

The frozen index is in test/fixtures, but the actual test cases (inputs/outputs) are implemented in Ruby (I think). Let’s keep this noted.

I got a bit confused while trying to understand how to correctly implement support for 'extras'.
There is an ExtrasProvider base class provided.
ExtrasProvider has 2 normal and 2 abstract methods.
In the example PyPIProvider which implements ExtrasProvider, both normal methods are overridden and one of the abstract methods is never called.
So either the abstraction ExtrasProvider is a bit off or the only existing example is a very special case in which case it would be nice to also provide an example that is not a special case.

Resolvelib has multiple test failures when the tests are run using packaging 22.0 or 23.0. All tests pass with 21.3. It appears that packaging has implemented a more strict definition of what an appropriate version number is. Here's the test summary:

======================================================== short test summary info ========================================================
FAILED tests/functional/cocoapods/test_resolvers_cocoapods.py::test_resolver[shared_parent_dependency] - packaging.version.InvalidVersion: Invalid version: '0.10.0-qs.0'
FAILED tests/functional/cocoapods/test_resolvers_cocoapods.py::test_resolver[deep_complex_conflict] - packaging.version.InvalidVersion: Invalid version: '4.0.0-preview2.1'
FAILED tests/functional/cocoapods/test_resolvers_cocoapods.py::test_resolver[shared_parent_dependency_with_swapping] - packaging.version.InvalidVersion: Invalid version: '0.3.6-pre.f7e3358'
FAILED tests/functional/cocoapods/test_resolvers_cocoapods.py::test_resolver[spapping_and_rewinding] - packaging.version.InvalidVersion: Invalid version: '2.0.0.pre.develop.2'
FAILED tests/functional/cocoapods/test_resolvers_cocoapods.py::test_resolver[pruned_unresolved_orphan] - packaging.version.InvalidVersion: Invalid version: '0.18.0-gh.de28323'
FAILED tests/functional/cocoapods/test_resolvers_cocoapods.py::test_resolver[conflict_common_parent] - packaging.version.InvalidVersion: Invalid version: '5.0.0-beta1.1'
================================================ 6 failed, 40 passed, 3 xfailed in 6.87s

See the attached for the details.

Scott K
test_results_packaging_22_0.txt

Look for ready-made declarative tests to run against the resolver. Some potential sources:

• Swift Package Manager. Especially the performance test inputs. #17
• CocoaPods. See resolver integration spec. #21
• Cargo. I don’t see any serious tests though :(
• vgo. I don’t know how it works. Someone help please.
• Bundler (Ruby). Tests and indexes in DSL.
• Dart. Fixtures seem to be integrated in tests.
• Poetry. Fixtures in code. Mixology too.

Molinilo (CocoaPods) detects dependency cycles and rejects them. ResolveLib does not do this (neither does pip currently), but maybe it would be possible to implement a provider hook to let the user decide whether or not to?

Currently the resolver only allow one way for the provider to trigger backtracking, by supplying requirements (dependencies) that would empty a criterion’s candidate list. This prevents some oppertunities for applications to reject candidates in later stages. pip, for example, wants to reject a candidate with invalid/inconsistent metadata, but there’s currently no way for it to do this.

Except there is already a hook for that: is_satisfied_by(). This hook is already checked during pinning:

The first block catches RequirementsConflicted, which would be used to trigger backtracking. The second calls is_satisfied_by(), but expects it to always return True (otherwise raises InconsistentCandidate). If we modify the block to instead continue (i.e. give up on the candidate) when is_satisfied() returns false, the provider can then use it to validate the candidate and signal any latent issues that cannot be found previously.

This would help issues such as pypa/pip#9203, and provide the companion fix needed for pypa/pip#9199.

Hi! I'm currently looking into updating this package for Arch Linux.
I noticed that the pypi.org sdist tarballs do not contain files required for testing. From a downstream perspective it is always good to be able to rely on sdist tarballs for running tests as well.

It would be awesome if they could be added! Thank you! :)

Not sure where best to post this. There are mainly three things I want to do:

• Address the “extras cannot see URL specified in non-extra-ed requirement” issue by passing additional requirements to find_matches() (#56)
• Add a provider hook for tree pruning (#67)
• Provide more useful information to get_preferences() to implement more intelligent requirement ordering (pypa/pip#9187 (comment))

All of these requirement changes to the provider interface, and I would like to do them in one bump from 0.5.x to 0.6. But I also want to introduce each of them to pip separately to keep the PRs clean and real users more easily to test. How would be best to approach this? Should I vendor resolvelib from Git commits, or create some versions (e.g. 0.6.0a1) for each breaking change?

Resolver should clean up the graph to purge dead subtrees, and maping to remove unneeded pins after resolution (or maybe after each round?).

I'm trying to package your module as an rpm package. So I'm using the typical PEP517 based build, install and test cycle used on building packages from non-root account.

• python3 -sBm build -w --no-isolation
• because I'm calling build with --no-isolation I'm using during all processes only locally installed modules
• install .whl file in </install/prefix>
• run pytest with PYTHONPATH pointing to sitearch and sitelib inside </install/prefix>

Here is pytest output:

+ PYTHONPATH=/home/tkloczko/rpmbuild/BUILDROOT/python-resolvelib-0.8.1-2.fc35.x86_64/usr/lib64/python3.8/site-packages:/home/tkloczko/rpmbuild/BUILDROOT/python-resolvelib-0.8.1-2.fc35.x86_64/usr/lib/python3.8/site-packages
+ /usr/bin/pytest -ra
=========================================================================== test session starts ============================================================================
platform linux -- Python 3.8.13, pytest-7.1.2, pluggy-1.0.0
rootdir: /home/tkloczko/rpmbuild/BUILD/resolvelib-0.8.1
collected 48 items

tests/test_resolvers.py ....                                                                                                                                         [  8%]
tests/test_structs.py .......                                                                                                                                        [ 22%]
tests/functional/cocoapods/test_resolvers_cocoapods.py x........x...............                                                                                     [ 75%]
tests/functional/python/test_resolvers_python.py ....xx..                                                                                                            [ 91%]
tests/functional/swift-package-manager/test_resolvers_swift.py ....                                                                                                  [100%]

============================================================================= warnings summary =============================================================================
tests/functional/cocoapods/test_resolvers_cocoapods.py: 188 warnings
tests/functional/python/test_resolvers_python.py: 20 warnings
  /usr/lib/python3.8/site-packages/packaging/version.py:111: DeprecationWarning: Creating a LegacyVersion has been deprecated and will be removed in the next major release
    warnings.warn(

tests/functional/python/test_resolvers_python.py: 27 warnings
  /usr/lib/python3.8/site-packages/packaging/specifiers.py:255: DeprecationWarning: Creating a LegacyVersion has been deprecated and will be removed in the next major release
    warnings.warn(

-- Docs: https://docs.pytest.org/en/stable/how-to/capture-warnings.html
========================================================================= short test summary info ==========================================================================
XFAIL tests/functional/cocoapods/test_resolvers_cocoapods.py::test_resolver[circular]
  circular dependencies works for us, no conflicts
XFAIL tests/functional/cocoapods/test_resolvers_cocoapods.py::test_resolver[fixed_circular]
  circular dependencies works for us, no backtracks
XFAIL tests/functional/python/test_resolvers_python.py::test_resolver[pyrex-1.9.8]
  Too many rounds (>500)
XFAIL tests/functional/python/test_resolvers_python.py::test_resolver[same-package-extras]
  State not cleaned up correctly
=============================================================== 44 passed, 4 xfailed, 235 warnings in 14.99s ===============================================================

Cargo directly merges extras (features in Rust terminology) into existing, already resolved candidates.

https://github.com/rust-lang/cargo/blob/4fbd644bc76e25815a8e3a2189b6430fe69fd0d6/src/cargo/core/resolver/mod.rs#L646-L657

This means the provider needs a way to “talk back” to the resolver “I want to add edges to another node,” which is a departure to the current design, in which all communication is one-sided (the resolver asks, and provider responds). But it would make handling extras more natural, and could help with marker merging (which might require a similar talk-back mechanism).

Another thing to consider is that merging extras could make it harder to answer where exactly does that dependency came from? because all extra dependencies got connected to a common parent, losing context. Cargo handles this by maintaining a separate record of requested features. I guess this eventually is a choice of poison; you gotta introduce the complexity somewhere.

One benefit of not merging extras in the resolver is that the graph becomes strictly insert-only. Once a node is inserted you know how many (out-going) edges it has; it won’t change. Sounds like a nice property, but is it even useful at all in practice?

We have a tool using resolvelib which implements the AbstractProvider interface. 0.5.5 broke the API with 915363f changing the signature of identify.

Following semver, technically such changes are to be expected, but I also saw #74 warning about upcoming API breakage in 0.6.0, so I'm wondering what the policy around API changes is in resolvelib.

Slightly related to #11.

Currently our resolver picks one package to resolve for each iteration by looking all known requirements. In contrast, Rust uses a DFS, i.e. it picks one initial requirement to resolve, and pick one of its dependency to resolve, and so on, completing the whole branch before looking at the next initial requirement. My instinct was that looking at all known requirements (so more of a BFS) makes it easier to detect conflicts early, but that might not be the case.

Again, real-world cases would help greatly to determine which choice is better.

The specification of the provider's find_matches method doesn't include any information about whether candidates need to be "unique". To give an example, consider two requirements, pip >= 19.0 and pip >= 20.0. The candidate pip-20.0-py3-none-any.whl satisfies both of these.

When a client implements find_matches on a provider, is it necessary that the same candidate is returned in both calls, or is it enough that "equivalent" candidates are returned? (To be honest, I'm not even clear what it means to be the "same" candidate here - is object identity enough?)

Reasons this matters:

1. If methods on the candidate object are expensive to calculate (for pip, identify could involve building the project to get the project name), we want to avoid doing this multiple times if it's not needed.
2. If different candidate objects are returned, will resolvelib (potentially) consider both of them, which would duplicate work (again, particularly expensive if we need to build projects as part of calling methods on the candidate). Or will "equivalent" candidates get merged?

I can look at the existing code to determine how things work, but this should be documented so that the implementation isn't constrained to keep internal details the same because clients rely on them.

One of the things that can be found in zazo's issue tracker, is a bunch of Python-specific failure cases for the current pip resolver.

It might be useful to add test cases for those situations. Another case that would be really handy would be to have test cases for some successful situations, like installing https://libraries.io/github/aws/chalice -- which depends on 35+ packages directly, including botocore, which has 900+ releases.

Cargo sorts the resolution order by number of available candidates (resolve package with fewer candidates first). This matches my (instinctive) choice in Passa, and could actually be the answer?

https://github.com/rust-lang/cargo/blob/4fbd644bc76e25815a8e3a2189b6430fe69fd0d6/src/cargo/core/resolver/types.rs#L205-L219

https://github.com/sarugaku/passa/blob/2ac00f16cd5a8f07d679a3ab02b7cc13c6f42bee/src/passa/models/providers.py#L44-L47

But I still think more real-world cases need to be tested before we can settle on a good default. (Note that the default implementation should be somewhat cheap, since this is called on every resolution round.)

pip install "apache-airflow[devel_ci]==1.10.14rc1" --constraint "https://raw.githubusercontent.com/apache/airflow/constraints-1-10/constraints-3.6.txt"

This (run against pypa/pip@fd8ddb6) would result in the resolver backtracking on setuptools, but these backtracks are obviously useless since setuptools does not have dependencies.

The resolver should be able to “look ahead” and see that trying other versions of setuptools would not change the conflicting graph, and skip working on them altogether. This applies not only to packages without dependencies (although they are the easiest target), but also versions that have the same dependencies. The idea of “the same dependencies” however require provider support (a new hook are_dependencies_equal or something) so those are more difficult to implement.

A stub issue to remind myself. Will first need to collect what exactly Cargo does first. A sensible default implementation using logging might be a good idea here as well.

In some preliminary testing and prior experience, copying results in both memory and run-time overhead.

I think it could be useful to add some property-based tests to resolvelib, to stress test some of the basic properties of the resolver. Some ideas I had for useful tests:

• If the resolver succeeds, the resolver result will satisfy the supplied requirements.
• Given a set of requirements, adding an extra one that contradicts one in the set will cause a resolver failure.

The key will be setting up "strategies" that generate sets of candidates and requirements.

I'm mainly adding this here as a reminder, so that I don't forget to look at this at some point in the future.

This is likely a sane thing to do.

On current master (rev. 243acc5).
Executing pypi_wheel_provider.py django fails with:
resolvelib.resolvers.ResolutionTooDeep: 100

Context: pypa/pip#7966 (comment)

I think it is theoratically possible for the resolver to not process the candidate list immediately, but to simply add a “filter” thing on it, and check is_satisfied_by on a candidate only if it ever needs it (because all candidates with higher preferences don’t work). This would probably make the things a lot of complex than they are right now, but it sounds like a good thing for performance as well.

Especially same-package-extras.json, which is failing with a plain exception.

Context

While using pip, which makes use of this library, I noticed that pip install flake8 flake8-isort resulted 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:

1. The latest flake8 (4.0.1 at the time of writing) gets selected.
2. The latest flake8-isort gets selected
3. The flake8-isort candidate requires flake8<4, which isn't compatible with the flake8 candidate, so we backtrack on flake8.
4. For each flake8 version, we check if its dependencies are compatible with the current criteria:

   resolvelib/src/resolvelib/resolvers.py

   Lines 203 to 204 in 62c56b5

   	for requirement in self._p.get_dependencies(candidate=candidate):
   	self._add_to_criteria(criteria, requirement, parent=candidate)

5. This fails with

> /home/sander/.virtualenvs/temp/lib/python3.9/site-packages/pip/_vendor/resolvelib/resolvers.py(218)_attempt_to_pin_criterion()
-> continue
(Pdb) l
213  	            try:
214  	                criteria = self._get_updated_criteria(candidate)
215  	            except RequirementsConflicted as e:
216  	                causes.append(e.criterion)
217  	                breakpoint()
218  ->	                continue
219  	
220  	            # Check the newly-pinned candidate actually works. This should
221  	            # always pass under normal circumstances, but in the case of a
222  	            # faulty provider, we will raise an error to notify the implementer
223  	            # to fix find_matches() and/or is_satisfied_by().
(Pdb) e.criterion
Criterion((SpecifierRequirement('pyflakes<2.5.0,>=2.4.0'), via=LinkCandidate('https://files.pythonhosted.org/packages/34/39/cde2c8a227abb4f9ce62fe55586b920f438f1d2903a1a22514d0b982c333/flake8-4.0.1-py2.py3-none-any.whl#sha256=479b1304f72536a55948cb40a32dce8bb0ffe3501e26eaf292c7e60eb5e0428d (from https://pypi.org/simple/flake8/) (requires-python:>=3.6)')), (SpecifierRequirement('pyflakes<2.4.0,>=2.3.0'), via=LinkCandidate('https://files.pythonhosted.org/packages/fc/80/35a0716e5d5101e643404dabd20f07f5528a21f3ef4032d31a49c913237b/flake8-3.9.2-py2.py3-none-any.whl#sha256=bf8fd333346d844f616e8d47905ef3a3384edae6b4e9beb0c5101e25e3110907 (from https://pypi.org/simple/flake8/) (requires-python:!=3.0.*,!=3.1.*,!=3.2.*,!=3.3.*,!=3.4.*,>=2.7)')))

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<4 is compatible with the rest of the current criteria.

Carried over from pradyunsg/zazo#9:

• https://medium.com/@nex3/pubgrub-2fb6470504f
• https://github.com/dart-lang/pub/blob/master/doc/solver.md

The following test fails.

def test_requirements_different_candidate_sets():
    requirements = {
        "r1": ["c1"],
        "r2": ["c2"],
    }

    class Provider(AbstractProvider):
        def identify(self, d):
            return "r" if d.startswith("r") else d

        def get_preference(self, *_):
            return 0

        def get_dependencies(self, _):
            return []

        def find_matches(self, r):
            return requirements.get(r, [])

        def is_satisfied_by(self, r, c):
            if r == "r1":
                return c in requirements[r]
            elif r == "r2":
                # r2 accepts anything, even stuff it doesn't
                # return in find_matches
                return True
            return False

    resolver = Resolver(Provider(), BaseReporter())
    result = resolver.resolve(["r1", "r2"])
    assert result.mapping["r"] == "c1"

    resolver = Resolver(Provider(), BaseReporter())
    result = resolver.resolve(["r2", "r1"])
    assert result.mapping["r"] == "c1"

Note that the two tests at the end are the same request, just with the order of the requirements reversed.

The requirements have been constructed so that:

1. They are both for the same "project".
2. r1 is a normal sort of requirement.
3. r2 accepts the candidate r1 returns as well as its own one, but doesn't return that candidate in find_matches.

This specific configuration came up in pypa/pip#8136.

I don't think the result of a resolve() call should be order-dependent like this, even if we argue that the provider is pathological. If we don't want to support providers like this, we need to document precisely what rules the provider has to follow - and we should validate them and produce a proper error, not just return an incorrect result.

(Personally, I'd like to get this case to work, as it's far easier to implement pip's constraints if we can).

When upgrading a package (plcoud) I am starting to get these errors, doesn't matter what pkg it is or if I am root or not. It looks like a TypeError. I did upgrade resolvelib a few months ago using pacman but I made the mistake of doing a pip install --upgrade resolvelib and I am currently running version 0.7.1 from pip.

Should I remove the pip 0.7.1 version and reinstall the pacman 0.5.5-1 version?

$ pip install --upgrade pcloud
Defaulting to user installation because normal site-packages is not writeable
ERROR: Exception:
Traceback (most recent call last):
  File "/usr/lib/python3.9/site-packages/pip/_internal/cli/base_command.py", line 223, in _main
    status = self.run(options, args)
  File "/usr/lib/python3.9/site-packages/pip/_internal/cli/req_command.py", line 180, in wrapper
    return func(self, options, args)
  File "/usr/lib/python3.9/site-packages/pip/_internal/commands/install.py", line 320, in run
    requirement_set = resolver.resolve(
  File "/usr/lib/python3.9/site-packages/pip/_internal/resolution/resolvelib/resolver.py", line 121, in resolve
    self._result = resolver.resolve(
  File "/usr/lib/python3.9/site-packages/resolvelib/resolvers.py", line 472, in resolve
    state = resolution.resolve(requirements, max_rounds=max_rounds)
  File "/usr/lib/python3.9/site-packages/resolvelib/resolvers.py", line 341, in resolve
    self._add_to_criteria(self.state.criteria, r, parent=None)
  File "/usr/lib/python3.9/site-packages/resolvelib/resolvers.py", line 147, in _add_to_criteria
    matches = self._p.find_matches(
TypeError: find_matches() got an unexpected keyword argument 'identifier'
$ sudo pip install --upgrade pcloud
[sudo] password for alarm: 
ERROR: Exception:
Traceback (most recent call last):
  File "/usr/lib/python3.9/site-packages/pip/_internal/cli/base_command.py", line 223, in _main
    status = self.run(options, args)
  File "/usr/lib/python3.9/site-packages/pip/_internal/cli/req_command.py", line 180, in wrapper
    return func(self, options, args)
  File "/usr/lib/python3.9/site-packages/pip/_internal/commands/install.py", line 320, in run
    requirement_set = resolver.resolve(
  File "/usr/lib/python3.9/site-packages/pip/_internal/resolution/resolvelib/resolver.py", line 121, in resolve
    self._result = resolver.resolve(
  File "/usr/lib/python3.9/site-packages/resolvelib/resolvers.py", line 472, in resolve
    state = resolution.resolve(requirements, max_rounds=max_rounds)
  File "/usr/lib/python3.9/site-packages/resolvelib/resolvers.py", line 341, in resolve
    self._add_to_criteria(self.state.criteria, r, parent=None)
  File "/usr/lib/python3.9/site-packages/resolvelib/resolvers.py", line 147, in _add_to_criteria
    matches = self._p.find_matches(
TypeError: find_matches() got an unexpected keyword argument 'identifier'

It would be nice to keep PyPI releases and git tags in sync :)

This sort here gets a list of (name, criterion) pairs.

The criterions, however, may change during the later loop. Since we made a copy here, criteria updated in the loop won’t be picked up until the next round, resulting in missed edges.

Example: A and B needs to be pinned in a round. B depends on A (we don’t know that yet until we pin B), and B is pinned before A.

• We make a copy of the current criteria. Those of A and B are both (say) empty.
• B is pinned. It has a child A, but since A is not yet pinned, it skips connecting to A, and leave A to connect.
• B contributes to A’s criterion. This updates self._criteria['A'], but not the copy made previously.
• A is pinned (in the same round). It uses the copied criterion, and does not know it should connect to B.

The solution is simple knowing what the problem is. Instead of cpoying .items(), only copy the key, and get the values lazily when we actually need it.

Hi, could anyone post a public statement explaining if this project follows any specific versioning scheme? It'd be useful for the consumers to know how to set up the dependency boundaries.

I've asked this in a comment #69 (comment) but it seems to have been missed. Plus it even confuses our contributors who attempt submitting not-very-well-thought bumps apparently: ansible/ansible#76257.

Or introduce some real documentation. It might help to use pip’s implementation as “examples” to how various things can be implemented within the resolver’s model. (e.g. Requires-Python, extras)

I think it makes sense to do this, given that this is used by pip.

I've been thinking about the unsat exception to be raised and, basically, I think it might be a good idea to expose 2 optional methods to:

• get the equivalent of learned clauses, that we could feed back into the system.
• get a human readable explanation of the situation.

Both are optional, but I imagine that resolution algorithms are capable of these outputs and surfacing them via a standard mechanism might make sense. YAGNI possibly applied here, but I'm fairly certain that the human-readable messaging makes sense on its own anyway. A clear standard / documentation on how/what it could be would be nice to have.

OK with moving to https://www.python.org/psf/conduct/ ?

The first thing I look for in a README is how to install and run the test suite.

I think it's time to drop support for Python versions prior to 3.7.

/cc @uranusjr @pradyunsg

This would be useful for reporters, to determine why a certain requirement is added.

I'm imagining a evaluating hook, that's called at the start of the loop on _attempt_to_pin_criterion, prior to pinning but unconditionally (so that it doesn't actually have to match the criterion).

As an example, I want to be able to visualize false-starts / not-compatible-version checks, before they're pinned and currently, there's no way for the reporter to get this information.

Follow up of #21.

• complex_conflict.json
• shared_parent_dependency_with_swapping.json
• spapping_and_rewinding.json
• circular.json
• complex_conflict_unwinding.json
• conflict_on_child.json
• deep_complex_conflict.json
• fixed_circular.json
• previous_conflict.json
• pruned_unresolved_orphan.json
• swapping_children_with_successors.json

Adding some documentation would go a very long way to help adopters of this library beyond pip.
For a start I suggest adding some generated API ReST doc using sphinx and published on RTD.
Would you need help for this?

Here's how AbstractProvider.get_preferences is defined:

    def get_preference(
        self,
        identifier,
        resolutions,
        candidates,
        information,
        backtrack_causes,
    ):

and here's the .pyi definition:

    def get_preference(
        self,
        identifier: KT,
        resolutions: Mapping[KT, CT],
        candidates: Mapping[KT, Iterator[CT]],
        information: Mapping[KT, Iterator[RequirementInformation[RT, CT]]],
    ) -> Preference: ...

Note that the latter is missing backtrack_causes, so any downstream consumers of resolvelib's type hints won't be able to use the signature.

I'm happy to make a small PR fixing this!

It should not. This currently works in pip because pip’s implementation caches candidates so equality works via object identity, and in tests because all tests currently use tuples (or namedtuples) to represent candidates.

Some potential solutions:

• Explicitly require the implementer to supply Candidate.__eq__ (and __ne__ on Python 2). I don’t like this.
• Add Provider.is_equal_to(candidate_a, candidate_b).
• Add Provider.excluding(candidate_iterable, excluding_candidates).

The resolver should be able to accept an already resolved graph, and start resolving from there (instead of a new graph). Upgrade semantic can probably be done on the callee side: Remove a vertex from an existing graph [*], and send it to the resolver with the requirements (including the package to be upgraded) to upgrade. I don’t have a proof, but this should work.

[*]: The vertex’s children should not be removed (although edges to it obviously need to be severed). The resolver will probably need to gain a cleanup phase to remove orphan vertices (vertices without any parents) from the graph after resolution is done.

This will help improve the performance by not requesting the network with certain provider implementations. For example, a provider will first find matches from local files and then from the remote server, all candidates are combined into a generator returned by find_matches(). So if the local candidates meet the requirement, we don't need to read the whole iterable.

File this issue just as an improvement idea. I will do some experiment to find out a solution for it.

This is like pypa/pip#9071, but in a more generic sense. I suppose that this may ties to the algorithm, but I don't think the current algo requires this to be done. In short, before doing any resolution work, the resolver tries to find all the matches for each of the initial requirements:

Now suppose I have [A, B>6], where the first match for A is version 42 and A 42 depends on B<9, and that Provider.find_matches([B>6]) and Provider.find_matches([B>6,B<9]) do totally different things (or that the result of the underlying expensive operations can't be shared), then Provider.find_matches([B>6]) is wasteful.

In pip's case, of course the majority of the time it's reaching to simple repositories, which has an index shared for all B, so with caching/memoization it's not a problem though.

I’m going to work toward 0.6.0, which is going to contain several breaking changes. This post serves both as a heads-up and summary to myself so I don’t forget something or have to add new things at the last minute.

Keyword arguments

All Provider and Reporter methods will be called with keyword arguments from now on. This means you can start adding **kwargs for future compatibility now.

find_matches argument changes

def find_matches(
    identifier: Identifier,
    requirements: Mapping[Identifier, List[Requirement]],
    incompatibilities: Mapping[Identifier, List[Candidate]],
) -> Matches: ...

The current requirements: List[Requirement] can be replaced by requirements[identifier]. The new incompatibilities argument provides incompatible candidates already known to the resolver. The provider must exclude them from the result.

get_preference argument changes

def get_preference(
    identifier: Identifier,
    resolutions: Mapping[Identifier, Candidate],
    candidates: Mapping[Identifier, Collection[Candidate]],
    information: Mapping[Identifier, Sequence[Information]],
) -> Preference: ...

Identifier is the return type of identify. Criterion is the same as in Result.

Old get_preference() arguments can be replaced by:

• resolution: resolutions.get(identifier).
• candidates: candidates[identifier].candidates is an abstraction around the return value of find_matches(). It implements the equence protocol if you returned a list from find_matches(). Otherwise, it is an iterable container.
• information: criteria[identifier].information.

Would be beneficial to the development workflow. :)

Quoting @pradyunsg from https://python.zulipchat.com/#narrow/stream/218659-pip-development/topic/Resolvelib.20question/near/195392774

spec = """\
A 1.0.0
    B == 1.0.0
A 2.0.0
    B == 2.0.0
    C == 1.0.0
A 3.0.0
    B == 3.0.0
    C == 2.0.0
B 1.0.0
    C == 1.0.0
B 2.0.0
    C == 2.0.0
B 3.0.0
    C == 3.0.0
# C 1.0.0
C 2.0.0
C 3.0.0
"""

I'm seeing an exception in _backtrack, and I'm not sure if the issue is with the resolver logic or with the provider at hand:

 Traceback (most recent call last):
  File "examples/reporter_demo.py", line 101, in <module>
    result = resolver.resolve([("A", SpecifierSet(">=1.0"))])
  File "resolvelib/resolvers.py", line 414, in resolve
    state = resolution.resolve(requirements, max_rounds=max_rounds)
  File "resolvelib/resolvers.py", line 315, in resolve
    result = self._backtrack()
  File "resolvelib/resolvers.py", line 257, in _backtrack
    name, candidate = self._states.pop().mapping.popitem()
KeyError: 'dictionary is empty'