Repository: jazzband/pip-tools
Pull request #1539 (2021-11-22 08:30:28)

Add support for pip's 2020 dependency resolver
### What's new?

Added new option `--resolver [backtracking|legacy]` to `pip-compile` (default is `legacy`). 

### How to use?

To enable [2020 dependency resolver](https://pip.pypa.io/en/latest/user_guide/#changes-to-the-pip-dependency-resolver-in-20-3-2020) run `pip-compile --resolver=backtracking`.

### Backtracking resolver example

```bash
$ echo "oslo.utils==1.4.0" | pip-compile - --resolver=backtracking --allow-unsafe --annotation-style=line -qo-
#
# This file is autogenerated by pip-compile with python 3.8
# To update, run:
#
#    pip-compile --allow-unsafe --annotation-style=line --output-file=- --resolver=backtracking -
#
babel==2.10.3             # via oslo-i18n, oslo-utils
iso8601==1.0.2            # via oslo-utils
netaddr==0.8.0            # via oslo-utils
netifaces==0.11.0         # via oslo-utils
oslo-i18n==2.1.0          # via oslo-utils
oslo-utils==1.4.0         # via -r -
pbr==0.11.1               # via oslo-i18n, oslo-utils
pytz==2022.1              # via babel
six==1.16.0               # via oslo-i18n, oslo-utils

# The following packages are considered to be unsafe in a requirements file:
pip==22.1.2               # via pbr
```

### Legacy resolver example

```bash
$ echo "oslo.utils==1.4.0" | pip-compile - --resolver=legacy --allow-unsafe -qo-
Could not find a version that matches pbr!=0.7,!=2.1.0,<1.0,>=0.6,>=2.0.0 (from oslo.utils==1.4.0->-r -)
Tried: 0.5.2.5.g5b3e942, 0.5.0, 0.5.1, 0.5.2, 0.5.4, 0.5.5, 0.5.6, 0.5.7, 0.5.8, 0.5.10, 0.5.11, 0.5.12, 0.5.13, 0.5.14, 0.5.15, 0.5.16, 0.5.17, 0.5.18, 0.5.19, 0.5.20, 0.5.21, 0.5.22, 0.5.23, 0.6, 0.7.0, 0.8.0, 0.8.1, 0.8.2, 0.9.0, 0.9.0, 0.10.0, 0.10.0, 0.10.1, 0.10.1, 0.10.2, 0.10.2, 0.10.3, 0.10.3, 0.10.4, 0.10.4, 0.10.5, 0.10.5, 0.10.6, 0.10.6, 0.10.7, 0.10.7, 0.10.8, 0.10.8, 0.11.0, 0.11.0, 0.11.1, 0.11.1, 1.0.0, 1.0.0, 1.0.1, 1.0.1, 1.1.0, 1.1.0, 1.1.1, 1.1.1, 1.2.0, 1.2.0, 1.3.0, 1.3.0, 1.4.0, 1.4.0, 1.5.0, 1.5.0, 1.6.0, 1.6.0, 1.7.0, 1.7.0, 1.8.0, 1.8.0, 1.8.1, 1.8.1, 1.9.0, 1.9.0, 1.9.1, 1.9.1, 1.10.0, 1.10.0, 2.0.0, 2.0.0, 2.1.0, 2.1.0, 3.0.0, 3.0.0, 3.0.1, 3.0.1, 3.1.0, 3.1.0, 3.1.1, 3.1.1, 4.0.0, 4.0.0, 4.0.1, 4.0.1, 4.0.2, 4.0.2, 4.0.3, 4.0.3, 4.0.4, 4.0.4, 4.1.0, 4.1.0, 4.1.1, 4.1.1, 4.2.0, 4.2.0, 4.3.0, 4.3.0, 5.0.0, 5.0.0, 5.1.0, 5.1.0, 5.1.1, 5.1.1, 5.1.2, 5.1.2, 5.1.3, 5.1.3, 5.2.0, 5.2.0, 5.2.1, 5.2.1, 5.3.0, 5.3.0, 5.3.1, 5.3.1, 5.4.0, 5.4.0, 5.4.1, 5.4.1, 5.4.2, 5.4.2, 5.4.3, 5.4.3, 5.4.4, 5.4.4, 5.4.5, 5.4.5, 5.5.0, 5.5.0, 5.5.1, 5.5.1, 5.6.0, 5.6.0, 5.7.0, 5.7.0, 5.8.0, 5.8.0
There are incompatible versions in the resolved dependencies:
  pbr!=0.7,<1.0,>=0.6 (from oslo.utils==1.4.0->-r -)
  pbr!=2.1.0,>=2.0.0 (from oslo.i18n==5.1.0->oslo.utils==1.4.0->-r -)
```
 
##### Contributor checklist

- [x] Provided the tests for the changes.
- [x] Assure PR title is short, clear, and good to be included in the user-oriented changelog

##### Maintainer checklist

- [x] Assure one of these labels is present: `backwards incompatible`, `feature`, `enhancement`, `deprecation`, `bug`, `dependency`, `docs` or `skip-changelog` as they determine changelog listing.
- [x] Assign the PR to an existing or new milestone for the target version (following [Semantic Versioning](https://blog.versioneye.com/2014/01/16/semantic-versioning/)).


astrojuanlu: I confirm that this fixes my original use case in #1277 🚀 

<details>

```
(.venv) juanlu at arion2 in /tmp/reqs
$ echo 'jupyterlab==3.0.0rc13' > requirements.in
(.venv) juanlu at arion2 in /tmp/reqs
$ pip-compile
Could not find a version that matches jupyter-server~=1.0.1,~=1.1,~=1.5 (from jupyterlab==3.0.0rc13->-r requirements.in (line 1))
Tried: 0.0.1, 0.0.1, 0.0.2, 0.0.2, 0.0.3, 0.0.3, 0.0.4, 0.0.4, 0.0.5, 0.0.5, 0.1.0, 0.1.0, 0.1.1, 0.1.1, 0.2.0, 0.2.0, 0.2.1, 0.2.1, 0.3.0, 0.3.0, 1.0.0, 1.0.0, 1.0.1, 1.0.1, 1.0.2, 1.0.2, 1.0.3, 1.0.3, 1.0.4, 1.0.4, 1.0.5, 1.0.5, 1.0.6, 1.0.6, 1.0.7, 1.0.7, 1.0.8, 1.0.8, 1.0.9, 1.0.9, 1.0.10, 1.0.10, 1.0.11, 1.0.11, 1.1.0, 1.1.0, 1.1.1, 1.1.1, 1.1.2, 1.1.2, 1.1.3, 1.1.3, 1.1.4, 1.1.4, 1.2.0, 1.2.0, 1.2.1, 1.2.1, 1.2.2, 1.2.2, 1.2.3, 1.2.3, 1.3.0, 1.3.0, 1.4.0, 1.4.0, 1.4.1, 1.4.1, 1.5.0, 1.5.0, 1.5.1, 1.5.1, 1.6.0, 1.6.0, 1.6.1, 1.6.1, 1.6.2, 1.6.2, 1.6.3, 1.6.3, 1.6.4, 1.6.4, 1.7.0, 1.7.0, 1.8.0, 1.8.0, 1.9.0, 1.9.0, 1.10.0, 1.10.0, 1.10.1, 1.10.1, 1.10.2, 1.10.2, 1.11.0, 1.11.0, 1.11.1, 1.11.1, 1.11.2, 1.11.2
Skipped pre-versions: 1.0.0rc0, 1.0.0rc0, 1.0.0rc1, 1.0.0rc1, 1.0.0rc2, 1.0.0rc2, 1.0.0rc3, 1.0.0rc3, 1.0.0rc4, 1.0.0rc4, 1.0.0rc5, 1.0.0rc5, 1.0.0rc6, 1.0.0rc6, 1.0.0rc7, 1.0.0rc7, 1.0.0rc8, 1.0.0rc8, 1.0.0rc9, 1.0.0rc9, 1.0.0rc10, 1.0.0rc10, 1.0.0rc11, 1.0.0rc11, 1.0.0rc12, 1.0.0rc12, 1.0.0rc13, 1.0.0rc13, 1.0.0rc14, 1.0.0rc14, 1.0.0rc15, 1.0.0rc15, 1.0.0rc16, 1.0.0rc16, 1.7.0a1, 1.7.0a1, 1.7.0a2, 1.7.0a2
There are incompatible versions in the resolved dependencies:
  jupyter-server~=1.0.1 (from jupyterlab==3.0.0rc13->-r requirements.in (line 1))
  jupyter-server~=1.1 (from jupyterlab-server==2.0.0->jupyterlab==3.0.0rc13->-r requirements.in (line 1))
  jupyter-server~=1.5 (from nbclassic==0.2.8->jupyterlab==3.0.0rc13->-r requirements.in (line 1))
(.venv) juanlu at arion2 in /tmp/reqs
$ pip-compile --resolver=2020
#
# This file is autogenerated by pip-compile with python 3.9
# To update, run:
#
#    pip-compile --resolver=2020
#
argon2-cffi==21.1.0
    # via notebook
attrs==21.2.0
    # via jsonschema
babel==2.9.1
    # via jupyterlab-server
backcall==0.2.0
    # via ipython
bleach==4.1.0
    # via nbconvert
certifi==2021.10.8
    # via requests
cffi==1.15.0
    # via argon2-cffi
charset-normalizer==2.0.7
    # via requests
debugpy==1.5.1
    # via ipykernel
decorator==5.1.0
    # via ipython
defusedxml==0.7.1
    # via nbconvert
entrypoints==0.3
    # via
    #   jupyter-client
    #   nbconvert
idna==3.3
    # via requests
ipykernel==6.5.1
    # via notebook
ipython==7.29.0
    # via
    #   ipykernel
    #   jupyterlab
ipython-genutils==0.2.0
    # via
    #   jupyter-server
    #   nbformat
    #   notebook
jedi==0.18.1
    # via ipython
jinja2==3.0.3
    # via
    #   jupyter-server
    #   jupyterlab
    #   jupyterlab-server
    #   nbconvert
    #   notebook
json5==0.9.6
    # via jupyterlab-server
jsonschema==4.2.1
    # via
    #   jupyterlab-server
    #   nbformat
jupyter-client==7.0.6
    # via
    #   ipykernel
    #   jupyter-server
    #   nbclient
    #   notebook
jupyter-core==4.9.1
    # via
    #   jupyter-client
    #   jupyter-server
    #   jupyterlab
    #   nbconvert
    #   nbformat
    #   notebook
jupyter-server==1.0.11
    # via
    #   jupyterlab
    #   jupyterlab-server
    #   nbclassic
jupyterlab==3.0.0rc13
    # via -r requirements.in
jupyterlab-pygments==0.1.2
    # via nbconvert
jupyterlab-server==2.0.0rc7
    # via jupyterlab
markupsafe==2.0.1
    # via jinja2
matplotlib-inline==0.1.3
    # via
    #   ipykernel
    #   ipython
mistune==0.8.4
    # via nbconvert
nbclassic==0.2.4
    # via jupyterlab
nbclient==0.5.9
    # via nbconvert
nbconvert==6.3.0
    # via
    #   jupyter-server
    #   notebook
nbformat==5.1.3
    # via
    #   jupyter-server
    #   nbclient
    #   nbconvert
    #   notebook
nest-asyncio==1.5.1
    # via
    #   jupyter-client
    #   nbclient
    #   notebook
notebook==6.4.6
    # via nbclassic
packaging==21.3
    # via
    #   bleach
    #   jupyterlab
    #   jupyterlab-server
pandocfilters==1.5.0
    # via nbconvert
parso==0.8.2
    # via jedi
pexpect==4.8.0
    # via ipython
pickleshare==0.7.5
    # via ipython
prometheus-client==0.12.0
    # via
    #   jupyter-server
    #   notebook
prompt-toolkit==3.0.22
    # via ipython
ptyprocess==0.7.0
    # via
    #   pexpect
    #   terminado
pycparser==2.21
    # via cffi
pygments==2.10.0
    # via
    #   ipython
    #   jupyterlab-pygments
    #   nbconvert
pyparsing==3.0.6
    # via packaging
pyrsistent==0.18.0
    # via jsonschema
python-dateutil==2.8.2
    # via jupyter-client
pytz==2021.3
    # via babel
pyzmq==22.3.0
    # via
    #   jupyter-client
    #   jupyter-server
    #   notebook
requests==2.26.0
    # via jupyterlab-server
send2trash==1.8.0
    # via
    #   jupyter-server
    #   notebook
six==1.16.0
    # via
    #   bleach
    #   python-dateutil
terminado==0.12.1
    # via
    #   jupyter-server
    #   notebook
testpath==0.5.0
    # via nbconvert
tornado==6.1
    # via
    #   ipykernel
    #   jupyter-client
    #   jupyter-server
    #   jupyterlab
    #   notebook
    #   terminado
traitlets==5.1.1
    # via
    #   ipykernel
    #   ipython
    #   jupyter-client
    #   jupyter-core
    #   jupyter-server
    #   matplotlib-inline
    #   nbclient
    #   nbconvert
    #   nbformat
    #   notebook
urllib3==1.26.7
    # via requests
wcwidth==0.2.5
    # via prompt-toolkit
webencodings==0.5.1
    # via bleach

# The following packages are considered to be unsafe in a requirements file:
# setuptools
```
</details>
FlorentJeannot: Hello @atugushev 

Thank you for pinging me to test your branch, and thank you for taking the time to work on this feature!

I tried it and I noted some remarks:

1. ℹ️ From now on, `-c requirements.txt` does not work if the `requirements.txt` contains for example a direct reference. It requires a package name with a constraint. This is not related to your PR, but to how `pip` works. I thought it was interesting to mention it.

2. ❓ The listing of dependencies in the generated `.txt` file is a bit weird, for example:
```
certifi==2021.10.8
    # via
    #   requests
    #   requests[socks]
```
I don't know if we want to output the same package name twice?

3. ⚠️ The generated `.txt` file does not output the same dependencies depending on the order in the `.in` file.

For example:
```
crochet==2.0.0
Scrapy==2.5.1
```

Will output:
```
[...]
twisted==21.7.0
    # via
    #   crochet
    #   twisted[http2]
[...]
```

While:
```
Scrapy==2.5.1
crochet==2.0.0
```

Will output:
```
[...]
 twisted[http2]==21.7.0
    # via
    #   crochet
    #   scrapy
    #   twisted[http2]
[...]
```
atugushev: @FlorentJeannot thanks for the feedback and good catch! Looks like we need more tests for packages with extras. I'll address the bugs shortly.
FlorentJeannot: Thank you @atugushev. I found another one, not sure if it's related to your changes though.

When I have a direct reference with a relative path which contains an egg, the output of the .txt is the absolute path of the file on my machine.

Let me know if you need an exemple and thank you.
Also let me know when you have made some fixes, so that I can test it again and let you know if I spot other things.
webknjaz: @FlorentJeannot if you could send a PR with a failing test, it'd be easier to come up with a fix separately, once it's committed in Git. Per https://pganssle-talks.github.io/xfail-lightning/.
AndydeCleyre: 
> When I declare a local file which contains an egg (for example `file:./vendored/package.zip[requests]`), the output of the `.txt` is the absolute path of the file on my machine.

@FlorentJeannot I don't know if @atugushev  wants to merge this before or after #1329
AndydeCleyre: I wonder if the varying extras behavior noted by @FlorentJeannot is resolved by @richafrank's sitting PRs.

@atugushev Do you think we'll be finalizing this one before any other PRs, or are there some you plan to review and merge first?
jdimatteo: I'd love for this PR to be merged soon! I was using this but this branch is missing fixes like https://github.com/jazzband/pip-tools/pull/1567
saulshanabrook: Would folks be open to someone else taking on this PR to address the pending comments and rebase off of master?
pradyunsg: > Would folks be open to someone else taking on this PR to address the pending comments and rebase off of master?

Yes, that would be welcome.
atugushev: Hey @FlorentJeannot! 

Could you please check the latest version where I've fixed the [bug with annotations](https://github.com/jazzband/pip-tools/pull/1539#issuecomment-975542600) (2 and 3 points)?
FlorentJeannot: Hello @atugushev !

Thank you for your update and pinging me about this. I tried your changes and it looks good!

However, I found some other issues. I am trying to reproduce them as I cannot share the files with you, but so far I could not.

Basically the bug is that for some dependencies, local files or from a VCS, instead of showing the correct path or URL in the output, it shows the absolute path of a wheel file from pip's cache. I'll continue investigating tomorrow. If I can't reproduce I'll share more information.
FlorentJeannot: @atugushev
TL;DR: Looks good to me 👍 

I had an issue which would show this kind of output:

```
file:///Users/fj/Library/Caches/pip/wheels/2d/87/4b/d4a9edf4de8fdfbebd07dad937ddd46e0cf9a73740fdd64706/package-version-py3-none-any.whl
```

I fixed it by deleting the cache of pip. If we have people opening issue tickets for this, we should ask them to try `pip cache purge`. Also note that I did `rm -rf /Users/florent/Library/Caches/pip/*` for myself, but I expect pip's command line to do the same.

Also there's a discrepancy between legacy and backtracking about the extras. If the extra comes from a package in the `.in` file, then it's displayed in the `.txt` file; otherwise it's omitted.
I think it's somewhat fine, since we're heading in the right direction (e.g. only specify extras in `.in` files and do not show them in compiled files to mimic `pip freeze` behavior).

Before
```
twisted[http2]==21.7.0
    # via
    #   crochet
    #   scrapy
```

After

```
twisted==21.7.0
    # via
    #   crochet
    #   scrapy
```
atugushev: I've just checked all [reported resolver bugs](https://github.com/jazzband/pip-tools/issues?q=is%3Aissue+is%3Aopen+label%3Aresolver+label%3Abug) (16 open) - new resolver fixes them all 🔥 It looks ready to go live.
AndydeCleyre: I'm not sure if this is specific for this branch, because the input (`https://github.com/vmware/vsphere-automation-sdk-python/archive/v7.0.3.0.tar.gz`) doesn't compile at all in master, but over at [1597 (comment)](https://github.com/jazzband/pip-tools/issues/1597#issuecomment-1062718003) we're seeing for example:

```
nsx-policy-python-sdk @ file://localhost//tmp/pip-resolve-ehumdwah/vsphere-automation-sdk_a3f4013e6ddf4bc2a7c6a2cb49639288/lib/nsx-policy-python-sdk/nsx_policy_python_sdk-3.1.2.1.1-py2.py3-none-any.whl
```

I tried working around it with `pip cache purge`, but the output is the same.
atugushev: > I'm not sure if this is specific for this branch, because the input (`https://github.com/vmware/vsphere-automation-sdk-python/archive/v7.0.3.0.tar.gz`) doesn't compile at all in master, but over at [1597 (comment)](https://github.com/jazzband/pip-tools/issues/1597#issuecomment-1062718003) we're seeing for example:

@AndydeCleyre this looks out of the scope of this PR.
AndydeCleyre: Agreed now that you've shown what that package is doing. Thanks for having a look! 
AndydeCleyre: This branch is failing some tests locally but I have to run and will check it out again in like 8 hours.
AndydeCleyre: A pretty straightforward merge from master fixes my local tests, just as you can see `CI / Ubuntu / 3.7 / main` can't use `pip._internal.req.req_tracker`.
atugushev: > I'm happy to do a rebase but I don't want to disrupt ongoing work and review.

@AndydeCleyre please, feel free to.
atugushev: @AndydeCleyre I'd avoid rebase though and prefer merge. Feel free to push commits to the branch to address the issue with req_tracker.
atugushev: The `pipmain` still doesn't pass CI. I've tracked down bad commit https://github.com/pypa/pip/commit/0c284520c6d068cb25ac89d9dbee0456c2eba23a using bisect.
q0w: @atugushev could you also update `repositories/pypi.py` because of this change https://github.com/pypa/pip/pull/11014
AndydeCleyre: Would it be worthwhile to cut a small release with the `pip` version capped (both in the readme, and in `setup.cfg`)?
atugushev: @q0w updated. Thanks for noticing!
atugushev: > Would it be worthwhile to cut a small release with the `pip` version capped (both in the readme, and in `setup.cfg`)?

@AndydeCleyre after `pip-22.1` is released we can upgrade minimal requirements to `pip>=22.0`.
AndydeCleyre: @thomas-riccardi 

Thanks! Reproduced here as well.
atugushev: @AndydeCleyre thanks for the attached tests 🙏🏻 
atugushev: Hey @thomas-riccardi,

Thanks for the good catch and simple reproducer! I've fixed the bug and tested it on docker - looks good. Could you confirm whether the last commit ([56d0ab3](https://github.com/jazzband/pip-tools/pull/1539/commits/56d0ab303b75f44e966bddf62f518135b2261e66)) fixes your upgrade workflow?


thomas-riccardi: Hello @atugushev , thanks for the fast reply!
I confirm that e2b2c911b15bdb72d3de5bd8f7b9cfbee8609e3a fixes the simple scenario I reported here; but it doesn't cover our most complex scenario: sub-dependencies conflicts. Indeed your fix handles direct conflicts with requirements.in, but not indirect ones.

Here is an updated repro (using the latest version of this PR, including your fix):
### Reproduction 2
<details>
  <summary>Click to expand</summary>

```Dockerfile
# Usage: docker build . --progress=plain --build-arg CACHE_BREAKER=$RANDOM --build-arg RESOLVER=backtracking

FROM python:3.7

RUN pip --version
RUN pip install pip==21.*  

#RUN pip install pip-tools@git+https://github.com/atugushev/pip-tools@new-resolver
RUN pip install pip-tools@git+https://github.com/atugushev/pip-tools@56d0ab303b75f44e966bddf62f518135b2261e66  # pin commit for stability

ARG CACHE_BREAKER

ARG RESOLVER=legacy
RUN echo "flake8==3.8.4" > requirements.in
RUN pip-compile --verbose requirements.in -o requirements.txt --resolver=$RESOLVER
RUN cat requirements.txt

# simulate minimal upgrade: update requirements.in, keep old requirements.txt
RUN echo "flake8==3.9.2" > requirements.in
RUN pip-compile --verbose requirements.in -o requirements.txt --resolver=$RESOLVER
RUN cat requirements.txt

# result:
# expected: both resolvers should work
# actual: backtracking resolover fails: it seems to newly take output requirements.txt as strict constraints
```

backtracking resolver output:
```
#12 0.991   The conflict is caused by:
#12 0.991       flake8 3.9.2 depends on pycodestyle<2.8.0 and >=2.7.0
#12 0.991       The user requested (constraint) pycodestyle==2.6.0
```

legacy resolver output:
```
#13 0.349 flake8==3.9.2                                                                       
#13 0.349     # via -r requirements.in                                                        
#13 0.349 importlib-metadata==4.11.3                                                          
#13 0.349     # via flake8                                                                    
#13 0.349 mccabe==0.6.1                                                                       
#13 0.349     # via flake8                                                                                                                                                                   
#13 0.349 pycodestyle==2.7.0                                                                                                                                                                 
#13 0.349     # via flake8                                                                                                                                                                   
#13 0.349 pyflakes==2.3.1                                                                     
#13 0.349     # via flake8                                                                    
#13 0.349 typing-extensions==4.2.0                                                            
#13 0.349     # via importlib-metadata                                                        
#13 0.349 zipp==3.8.0                                                                         
#13 0.349     # via importlib-metadata                                                        
#13 DONE 0.4s
```
</details>
LouisAumaitre: Hi!

I'm getting an issue with extras using this resolver.

When I attempt to compile a file containing `-c other_file.txt`, if that other file contains extras, I get `pip._internal.exceptions.InstallationError: Constraints cannot have extras`. (I don't get the error when I compile the other file)

Example:

`file_a.txt` contains `coverage[toml]==6.3.2`

`file_b.txt` contains `-c file_a.txt`

Compiling `file_a.txt` works, compiling `file_b.txt` throws an `InstallationError`.
AndydeCleyre: As long as we are offering `--strip-extras` and not offering its negative, I'd guess that the default output line format would include extras (where this PR currently strips them).

Now that the constraints syntax is stricter (with the backtracking resolver), I expect it will be *much* more common for folks to need files without the extras. So I would support a separate PR to do that by default, while offering a new option to include them, e.g. `--no-strip-extras`.

#1613
AndydeCleyre: > > Would it be worthwhile to cut a small release with the `pip` version capped (both in the readme, and in `setup.cfg`)?
> 
> @AndydeCleyre after `pip-22.1` is released we can upgrade minimal requirements to `pip>=22.0`.

Looks like we ran out of time here... 
ryanhiebert: @AndydeCleyre : It may be a myopia of limited viewpoint, but I don't know what benefit having the extras in the output gives, and I'd be perfectly fine with there being no option to have them at all. The biggest downside I currently know of is that it would change existing output files, but since they are auto-generated lock files, that doesn't seem like a very big deal to me.
AndydeCleyre: @ryanhiebert 

I'm not saying it's good or common practice, but my understanding is that extras can be used to enforce installation order, and the set of packages already installed can be used by `setup.py`'s `install` to follow different code paths accordingly.

A hypothetical example:

- we have a package, `mypackage`
- it defines an extra, `interactive`
- the same package author also provides a kind of dummy package, `mypackage-interactive-installation`, required by `mypackages`'s `interactive` extra
- during `mypackage`'s `install`, if and only if `mypackage-interactive-installation` is already installed, the user is prompted to make some choices which will affect the installation
AndydeCleyre: @atugushev 

I'm excited for this PR to get merged, but if the final 1% of the problem isn't an easy solve, can we hammer out some of the other PRs that have been piling up behind this one? I'd be happy to help merge/rebase this afterward.
atugushev: > I'm excited for this PR to get merged, but if the final 1% of the problem isn't an easy solve, can we hammer out some of the other PRs that have been piling up behind this one? I'd be happy to help merge/rebase this afterward.

@AndydeCleyre 

I agree, let's not block other PRs by this one. 👍🏻 Thanks for helping!
AndydeCleyre: I merged master back in, so now in addition to our need to get `test_ignore_incompatible_existing_pins` passing, the backtracking resolver breaks master's relatively new `test_combine_different_extras_of_the_same_package`:

```diff
- ay[default]==0.1
+ ay[default,tune]==0.1
```
AndydeCleyre: I don't know if we can easily discard incompatible existing pins during resolution, like I *think* we do with the legacy resolver.

What does look easy enough is discarding all the existing pins and trying again, in the case where including them results in a resolution error.

In other words, this change would get the `test_ignore_incompatible_existing_pins` test passing, and not break existing tests, but would change the behavior in some cases I think:

```diff
diff --git a/piptools/resolver.py b/piptools/resolver.py
index 1022306..2b8ef36 100644
--- a/piptools/resolver.py
+++ b/piptools/resolver.py
@@ -17,6 +17,7 @@ from typing import (
 
 import click
 from pip._internal.cache import WheelCache
+from pip._internal.exceptions import DistributionNotFound
 from pip._internal.req import InstallRequirement
 from pip._internal.req.constructors import install_req_from_line
 from pip._internal.resolution.resolvelib.base import Candidate
@@ -538,6 +539,7 @@ class Resolver(BaseResolver):
 
             # Pass compiled requirements from `requirements.txt`
             # as constraints to resolver
+            compatible_existing_constraints = []
             for ireq in self.existing_constraints.values():
                 # Skip if the compiled install requirement conflicts with
                 # the primary install requirement.
@@ -551,7 +553,7 @@ class Resolver(BaseResolver):
                 ireq.extras = set()  # pip does not support extras in constraints
                 ireq.constraint = True
                 ireq.user_supplied = False
-                self.constraints.append(ireq)
+                compatible_existing_constraints.append(ireq)
 
             wheel_cache = WheelCache(
                 self.options.cache_dir, self.options.format_control
@@ -593,10 +595,18 @@ class Resolver(BaseResolver):
 
             self.command.trace_basic_info(self.finder)
 
-            resolver.resolve(
-                root_reqs=self.constraints,
-                check_supported_wheels=not self.options.target_dir,
-            )
+            try:
+                resolver.resolve(
+                    root_reqs=self.constraints + compatible_existing_constraints,
+                    check_supported_wheels=not self.options.target_dir,
+                )
+            except DistributionNotFound as e:
+                log.info(str(e))
+                log.info("Discarding existing pins and trying again")
+                resolver.resolve(
+                    root_reqs=self.constraints,
+                    check_supported_wheels=not self.options.target_dir,
+                )
 
         return self._get_install_requirements(resolver._result)

```
atugushev: > What does look easy enough is discarding all the existing pins and trying again, in the case where including them results in a resolution error.

@AndydeCleyre excellent idea, this let me figure out how to fix the issue properly! Thanks a lot 🙏🏻 

Hey @thomas-riccardi! Could you review and confirm the fix?
atugushev: > I merged master back in, so now in addition to our need to get `test_ignore_incompatible_existing_pins` passing, the backtracking resolver breaks master's relatively new `test_combine_different_extras_of_the_same_package`:
> 
> ```diff
> - ay[default]==0.1
> + ay[default,tune]==0.1
> ```

@AndydeCleyre thanks for the test! Addressed in 868052d1a06b5fd6adc44209a778d1713d9954f0.
AndydeCleyre: This is looking great!

I think the CI failures for pip's unreleased main branch are only encountered by the backtracking resolver, so that might be one more issue worth tackling before a merge.
atugushev: > I think the CI failures for pip's unreleased main branch are only encountered by the backtracking resolver, so that might be one more issue worth tackling before a merge.

@AndydeCleyre yeah, this looks related to https://github.com/jazzband/pip-tools/pull/1632.
atugushev: All checks (except `codecov/project`, which is fine) are green. This is ready for final review.
atugushev: @jazzband/pip-tools 

Pip's legacy resolver is going to be removed in the nearest future according to https://github.com/pypa/pip/issues/10946, so I need some volunteers to push this through so that users would have enough time to test the backtracking resolver. 
ssbarnea: @atugushev You have my support but there is a problem. That code is so old that pip behavior changed few times. For example the new resolver is default and passing the 2020-resolver flag is a very bad idea, read the waring.
```
WARNING: --use-feature=2020-resolver no longer has any effect, since it is now the default dependency resolver in pip. This will become an error in pip 21.0.
```

It is bit hilarious because that error came from pip `22.1.2` even if they declared that they will remove the flag in `21.0`.

I would say the we need to drop support for pip versions that did not have the new resolved active by default and avoid passing arguments for it.

In fact I would go so far to say that I don't even bother about the legacy one.
atugushev: @ssbarnea I've removed  `--use-feature=2020-resolver` usage in 4fb4610a3ca23bc94fbf3076bae9e1ab367eb0e1

atugushev: @thomas-riccardi thanks for the catch! That looks easy to fix. I'll do it shortly.
atugushev: @thomas-riccardi fixed in 697ec256a331bbd1514a4aa63a1a9817e15779d0. Could you try it?
thomas-riccardi: @atugushev 
> @thomas-riccardi fixed in [697ec25](https://github.com/jazzband/pip-tools/commit/697ec256a331bbd1514a4aa63a1a9817e15779d0). Could you try it?

I confirm this fixes both my repro v3 *and* our real use-case (after 3 rounds), thank you!
atugushev: @thomas-riccardi Excellent! Thanks for your help - that was super helpful 🙏🏻 

--- 
I'm going to squash some commits and prepare PR for merging.
atugushev: Huh, squashing all but preserving a few commits is a nightmare. I think I'd go with "Create merge commit" if nobody minds.
ssbarnea: Squash it! I do not want to see 65 commits polluting our history.

Patch:
diff --git a/piptools/repositories/base.py b/piptools/repositories/base.py
index 3ffec38..7e6c354 100644
--- a/piptools/repositories/base.py
+++ b/piptools/repositories/base.py
@@ -3,6 +3,7 @@ from abc import ABCMeta, abstractmethod
 from contextlib import contextmanager
 from typing import Iterator, Optional, Set
 
+from pip._internal.commands.install import InstallCommand
 from pip._internal.index.package_finder import PackageFinder
 from pip._internal.models.index import PyPI
 from pip._internal.network.session import PipSession
@@ -61,3 +62,8 @@ class BaseRepository(metaclass=ABCMeta):
     @abstractmethod
     def finder(self) -> PackageFinder:
         """Returns a package finder to interact with simple repository API (PEP 503)"""
+
+    @property
+    @abstractmethod
+    def command(self) -> InstallCommand:
+        """Return an install command."""
diff --git a/piptools/repositories/local.py b/piptools/repositories/local.py
index 754b607..99d9902 100644
--- a/piptools/repositories/local.py
+++ b/piptools/repositories/local.py
@@ -2,6 +2,7 @@ import optparse
 from contextlib import contextmanager
 from typing import Iterator, Mapping, Optional, Set, cast
 
+from pip._internal.commands.install import InstallCommand
 from pip._internal.index.package_finder import PackageFinder
 from pip._internal.models.candidate import InstallationCandidate
 from pip._internal.req import InstallRequirement
@@ -61,6 +62,11 @@ class LocalRequirementsRepository(BaseRepository):
     def session(self) -> Session:
         return self.repository.session
 
+    @property
+    def command(self) -> InstallCommand:
+        """Return an install command instance."""
+        return self.repository.command
+
     def clear_caches(self) -> None:
         self.repository.clear_caches()
 
diff --git a/piptools/repositories/pypi.py b/piptools/repositories/pypi.py
index cc99c0c..533a16d 100644
--- a/piptools/repositories/pypi.py
+++ b/piptools/repositories/pypi.py
@@ -73,10 +73,9 @@ class PyPIRepository(BaseRepository):
         # Use pip's parser for pip.conf management and defaults.
         # General options (find_links, index_url, extra_index_url, trusted_host,
         # and pre) are deferred to pip.
-        self.command: InstallCommand = create_command("install")
-        extra_pip_args = ["--use-deprecated", "legacy-resolver"]
+        self._command: InstallCommand = create_command("install")
 
-        options, _ = self.command.parse_args(pip_args + extra_pip_args)
+        options, _ = self.command.parse_args(pip_args)
         if options.cache_dir:
             options.cache_dir = normalize_path(options.cache_dir)
         options.require_hashes = False
@@ -103,8 +102,7 @@ class PyPIRepository(BaseRepository):
         self._cache_dir = normalize_path(str(cache_dir))
         self._download_dir = os.path.join(self._cache_dir, "pkgs")
 
-        if PIP_VERSION[0] < 22:
-            self._setup_logging()
+        self._setup_logging()
 
     def clear_caches(self) -> None:
         rmtree(self._download_dir, ignore_errors=True)
@@ -121,6 +119,11 @@ class PyPIRepository(BaseRepository):
     def finder(self) -> PackageFinder:
         return self._finder
 
+    @property
+    def command(self) -> InstallCommand:
+        """Return an install command instance."""
+        return self._command
+
     def find_all_candidates(self, req_name: str) -> List[InstallationCandidate]:
         if req_name not in self._available_candidates_cache:
             candidates = self.finder.find_all_candidates(req_name)
@@ -464,6 +467,9 @@ class PyPIRepository(BaseRepository):
             user_log_file=self.options.log,
         )
 
+        if PIP_VERSION[0] >= 22:
+            return
+
         # Sync pip's console handler stream with LogContext.stream
         logger = logging.getLogger()
         for handler in logger.handlers:
diff --git a/piptools/resolver.py b/piptools/resolver.py
index 012e9f0..f9d3d12 100644
--- a/piptools/resolver.py
+++ b/piptools/resolver.py
@@ -1,24 +1,53 @@
+import collections
 import copy
+from abc import ABCMeta, abstractmethod
 from functools import partial
 from itertools import chain, count, groupby
-from typing import Dict, Iterable, Iterator, List, Optional, Set, Tuple
+from typing import (
+    Any,
+    DefaultDict,
+    Dict,
+    Iterable,
+    Iterator,
+    List,
+    Optional,
+    Set,
+    Tuple,
+)
 
 import click
+from pip._internal.cache import WheelCache
+from pip._internal.exceptions import DistributionNotFound
 from pip._internal.req import InstallRequirement
 from pip._internal.req.constructors import install_req_from_line
+from pip._internal.resolution.resolvelib.base import Candidate
+from pip._internal.resolution.resolvelib.candidates import ExtrasCandidate
+from pip._internal.resolution.resolvelib.resolver import Resolver
+from pip._internal.utils.logging import indent_log
+from pip._internal.utils.temp_dir import TempDirectory, global_tempdir_manager
+from pip._vendor.packaging.specifiers import SpecifierSet
+from pip._vendor.packaging.utils import canonicalize_name
+from pip._vendor.resolvelib.resolvers import ResolutionImpossible, Result
 
 from piptools.cache import DependencyCache
 from piptools.repositories.base import BaseRepository
 
-from ._compat.pip_compat import update_env_context_manager
+from ._compat import PIP_VERSION
+from ._compat.pip_compat import get_build_tracker, update_env_context_manager
+from .exceptions import PipToolsError
 from .logging import log
 from .utils import (
     UNSAFE_PACKAGES,
+    as_tuple,
+    copy_install_requirement,
     format_requirement,
     format_specifier,
     is_pinned_requirement,
     is_url_requirement,
     key_from_ireq,
+    key_from_req,
+    omit_list_value,
+    strip_extras,
 )
 
 green = partial(click.style, fg="green")
@@ -110,33 +139,68 @@ def combine_install_requirements(
             key=lambda x: (len(str(x)), str(x)),
         )
 
-    combined_ireq = InstallRequirement(
+    combined_ireq = copy_install_requirement(
+        template=source_ireqs[0],
         req=req,
         comes_from=comes_from,
-        editable=source_ireqs[0].editable,
-        link=link_attrs["link"],
-        markers=source_ireqs[0].markers,
-        use_pep517=source_ireqs[0].use_pep517,
-        isolated=source_ireqs[0].isolated,
-        install_options=source_ireqs[0].install_options,
-        global_options=source_ireqs[0].global_options,
-        hash_options=source_ireqs[0].hash_options,
         constraint=constraint,
         extras=extras,
-        user_supplied=source_ireqs[0].user_supplied,
+        **link_attrs,
     )
-    # e.g. If the original_link was None, keep it so. Passing `link` as an
-    # argument to `InstallRequirement` sets it as the original_link:
-    combined_ireq.original_link = link_attrs["original_link"]
     combined_ireq._source_ireqs = source_ireqs
 
     return combined_ireq
 
 
-class Resolver:
+class BaseResolver(metaclass=ABCMeta):
+    repository: BaseRepository
+    unsafe_constraints: Set[InstallRequirement]
+
+    @abstractmethod
+    def resolve(self, max_rounds: int) -> Set[InstallRequirement]:
+        """
+        Find concrete package versions for all the given InstallRequirements
+        and their recursive dependencies and return a set of pinned
+        ``InstallRequirement``'s.
+        """
+
+    def resolve_hashes(
+        self, ireqs: Set[InstallRequirement]
+    ) -> Dict[InstallRequirement, Set[str]]:
+        """Find acceptable hashes for all of the given ``InstallRequirement``s."""
+        log.debug("")
+        log.debug("Generating hashes:")
+        with self.repository.allow_all_wheels(), log.indentation():
+            return {ireq: self.repository.get_hashes(ireq) for ireq in ireqs}
+
+    def _filter_out_unsafe_constraints(
+        self,
+        ireqs: Set[InstallRequirement],
+        reverse_dependencies: Dict[str, Set[str]],
+    ) -> None:
+        """
+        Remove from a given set of ``InstallRequirement``'s unsafe constraints.
+
+        Reverse_dependencies is used to filter out packages that are only
+        required by unsafe packages. This logic is incomplete, as it would
+        fail to filter sub-sub-dependencies of unsafe packages. None of the
+        UNSAFE_PACKAGES currently have any dependencies at all (which makes
+        sense for installation tools) so this seems sufficient.
+        """
+        for req in ireqs.copy():
+            required_by = reverse_dependencies.get(req.name.lower(), set())
+            if req.name in UNSAFE_PACKAGES or (
+                required_by and all(name in UNSAFE_PACKAGES for name in required_by)
+            ):
+                self.unsafe_constraints.add(req)
+                ireqs.remove(req)
+
+
+class LegacyResolver(BaseResolver):
     def __init__(
         self,
         constraints: Iterable[InstallRequirement],
+        existing_constraints: Dict[str, InstallRequirement],
         repository: BaseRepository,
         cache: DependencyCache,
         prereleases: Optional[bool] = False,
@@ -157,28 +221,26 @@ class Resolver:
         self.allow_unsafe = allow_unsafe
         self.unsafe_constraints: Set[InstallRequirement] = set()
 
+        options = self.repository.options
+        if "legacy-resolver" not in options.deprecated_features_enabled:
+            raise PipToolsError("Legacy resolver deprecated feature must be enabled.")
+
+        # Make sure there is no enabled 2020-resolver
+        options.features_enabled = omit_list_value(
+            options.features_enabled, "2020-resolver"
+        )
+
     @property
     def constraints(self) -> Set[InstallRequirement]:
         return set(
             self._group_constraints(chain(self.our_constraints, self.their_constraints))
         )
 
-    def resolve_hashes(
-        self, ireqs: Set[InstallRequirement]
-    ) -> Dict[InstallRequirement, Set[str]]:
-        """
-        Finds acceptable hashes for all of the given InstallRequirements.
-        """
-        log.debug("")
-        log.debug("Generating hashes:")
-        with self.repository.allow_all_wheels(), log.indentation():
-            return {ireq: self.repository.get_hashes(ireq) for ireq in ireqs}
-
     def resolve(self, max_rounds: int = 10) -> Set[InstallRequirement]:
         """
-        Finds concrete package versions for all the given InstallRequirements
-        and their recursive dependencies.  The end result is a flat list of
-        (name, version) tuples.  (Or an editable package.)
+        Find concrete package versions for all the given InstallRequirements
+        and their recursive dependencies and return a set of pinned
+        ``InstallRequirement``'s.
 
         Resolves constraints one round at a time, until they don't change
         anymore.  Protects against infinite loops by breaking out after a max
@@ -216,21 +278,11 @@ class Resolver:
         results = {req for req in best_matches if not req.constraint}
 
         # Filter out unsafe requirements.
-        self.unsafe_constraints = set()
         if not self.allow_unsafe:
-            # reverse_dependencies is used to filter out packages that are only
-            # required by unsafe packages. This logic is incomplete, as it would
-            # fail to filter sub-sub-dependencies of unsafe packages. None of the
-            # UNSAFE_PACKAGES currently have any dependencies at all (which makes
-            # sense for installation tools) so this seems sufficient.
-            reverse_dependencies = self.reverse_dependencies(results)
-            for req in results.copy():
-                required_by = reverse_dependencies.get(req.name.lower(), set())
-                if req.name in UNSAFE_PACKAGES or (
-                    required_by and all(name in UNSAFE_PACKAGES for name in required_by)
-                ):
-                    self.unsafe_constraints.add(req)
-                    results.remove(req)
+            self._filter_out_unsafe_constraints(
+                ireqs=results,
+                reverse_dependencies=self.reverse_dependencies(results),
+            )
 
         return results
 
@@ -445,3 +497,290 @@ class Resolver:
             ireq for ireq in ireqs if not (ireq.editable or is_url_requirement(ireq))
         ]
         return self.dependency_cache.reverse_dependencies(non_editable)
+
+
+class BacktrackingResolver(BaseResolver):
+    """A wrapper for backtracking resolver."""
+
+    def __init__(
+        self,
+        constraints: Iterable[InstallRequirement],
+        existing_constraints: Dict[str, InstallRequirement],
+        repository: BaseRepository,
+        allow_unsafe: bool = False,
+        **kwargs: Any,
+    ) -> None:
+        self.constraints = list(constraints)
+        self.repository = repository
+        self.allow_unsafe = allow_unsafe
+
+        options = self.options = self.repository.options
+        self.session = self.repository.session
+        self.finder = self.repository.finder
+        self.command = self.repository.command
+        self.unsafe_constraints: Set[InstallRequirement] = set()
+
+        self.existing_constraints = existing_constraints
+        self._constraints_map = {key_from_ireq(ireq): ireq for ireq in constraints}
+
+        # Make sure there is no enabled legacy resolver
+        options.deprecated_features_enabled = omit_list_value(
+            options.deprecated_features_enabled, "legacy-resolver"
+        )
+
+    def resolve(self, max_rounds: int = 10) -> Set[InstallRequirement]:
+        """
+        Find concrete package versions for all the given InstallRequirements
+        and their recursive dependencies and return a set of pinned
+        ``InstallRequirement``'s.
+        """
+        with update_env_context_manager(
+            PIP_EXISTS_ACTION="i"
+        ), get_build_tracker() as build_tracker, global_tempdir_manager(), indent_log():
+            # Mark direct/primary/user_supplied packages
+            for ireq in self.constraints:
+                ireq.user_supplied = True
+
+            # Pass compiled requirements from `requirements.txt`
+            # as constraints to resolver
+            compatible_existing_constraints: Dict[str, InstallRequirement] = {}
+            for ireq in self.existing_constraints.values():
+                # Skip if the compiled install requirement conflicts with
+                # the primary install requirement.
+                primary_ireq = self._constraints_map.get(key_from_ireq(ireq))
+                if primary_ireq is not None:
+                    _, version, _ = as_tuple(ireq)
+                    prereleases = ireq.specifier.prereleases
+                    if not primary_ireq.specifier.contains(version, prereleases):
+                        continue
+
+                ireq.extras = set()  # pip does not support extras in constraints
+                ireq.constraint = True
+                ireq.user_supplied = False
+                compatible_existing_constraints[key_from_ireq(ireq)] = ireq
+
+            wheel_cache = WheelCache(
+                self.options.cache_dir, self.options.format_control
+            )
+
+            temp_dir = TempDirectory(
+                delete=not self.options.no_clean,
+                kind="resolve",
+                globally_managed=True,
+            )
+
+            preparer_kwargs = {
+                "temp_build_dir": temp_dir,
+                "options": self.options,
+                "session": self.session,
+                "finder": self.finder,
+                "use_user_site": False,
+            }
+
+            if PIP_VERSION[:2] <= (22, 0):
+                preparer_kwargs["req_tracker"] = build_tracker
+            else:
+                preparer_kwargs["build_tracker"] = build_tracker
+
+            preparer = self.command.make_requirement_preparer(**preparer_kwargs)
+
+            resolver = self.command.make_resolver(
+                preparer=preparer,
+                finder=self.finder,
+                options=self.options,
+                wheel_cache=wheel_cache,
+                use_user_site=False,
+                ignore_installed=True,
+                ignore_requires_python=False,
+                force_reinstall=False,
+                use_pep517=self.options.use_pep517,
+                upgrade_strategy="to-satisfy-only",
+            )
+
+            self.command.trace_basic_info(self.finder)
+
+            for current_round in count(start=1):  # pragma: no branch
+                if current_round > max_rounds:
+                    raise RuntimeError(
+                        "No stable configuration of concrete packages "
+                        "could be found for the given constraints after "
+                        f"{max_rounds} rounds of resolving.\n"
+                        "This is likely a bug."
+                    )
+
+                log.debug("")
+                log.debug(magenta(f"{f'ROUND {current_round}':^60}"))
+
+                is_resolved = self._do_resolve(
+                    resolver=resolver,
+                    compatible_existing_constraints=compatible_existing_constraints,
+                )
+                if is_resolved:
+                    break
+
+        resolver_result = resolver._result
+        assert isinstance(resolver_result, Result)
+
+        # Get reverse requirements from the resolver result graph.
+        reverse_dependencies = self._get_reverse_dependencies(resolver_result)
+
+        # Prepare set of install requirements from resolver result.
+        result_ireqs = self._get_install_requirements(
+            resolver_result=resolver_result,
+            reverse_dependencies=reverse_dependencies,
+        )
+
+        # Filter out unsafe requirements.
+        if not self.allow_unsafe:
+            self._filter_out_unsafe_constraints(
+                ireqs=result_ireqs,
+                reverse_dependencies=reverse_dependencies,
+            )
+
+        return result_ireqs
+
+    def _do_resolve(
+        self,
+        resolver: Resolver,
+        compatible_existing_constraints: Dict[str, InstallRequirement],
+    ) -> bool:
+        """
+        Return true on successful resolution, otherwise remove problematic
+        requirements from existing constraints and return false.
+        """
+        try:
+            resolver.resolve(
+                root_reqs=self.constraints
+                + list(compatible_existing_constraints.values()),
+                check_supported_wheels=not self.options.target_dir,
+            )
+        except DistributionNotFound as e:
+            cause_exc = e.__cause__
+            if cause_exc is None:
+                raise
+
+            if not isinstance(cause_exc, ResolutionImpossible):
+                raise
+
+            # Collect all incompatible install requirement names
+            cause_ireq_names = {
+                key_from_req(cause.requirement) for cause in cause_exc.causes
+            }
+
+            # Looks like resolution is impossible, try to fix
+            for cause_ireq_name in cause_ireq_names:
+                # Find the cause requirement in existing requirements,
+                # otherwise raise error
+                cause_existing_ireq = compatible_existing_constraints.get(
+                    cause_ireq_name
+                )
+                if cause_existing_ireq is None:
+                    raise
+
+                # Remove existing incompatible constraint that causes error
+                log.warning(
+                    f"Discarding {cause_existing_ireq} to proceed the resolution"
+                )
+                del compatible_existing_constraints[cause_ireq_name]
+
+            return False
+
+        return True
+
+    def _get_install_requirements(
+        self,
+        resolver_result: Result,
+        reverse_dependencies: Dict[str, Set[str]],
+    ) -> Set[InstallRequirement]:
+        """Return a set of install requirements from resolver results."""
+        result_ireqs: Dict[str, InstallRequirement] = {}
+
+        # Transform candidates to install requirements
+        resolved_candidates = tuple(resolver_result.mapping.values())
+        for candidate in resolved_candidates:
+            ireq = self._get_install_requirement_from_candidate(
+                candidate=candidate,
+                reverse_dependencies=reverse_dependencies,
+            )
+            if ireq is None:
+                continue
+
+            project_name = canonicalize_name(candidate.project_name)
+            result_ireqs[project_name] = ireq
+
+        # Merge extras to install requirements
+        extras_candidates = (
+            candidate
+            for candidate in resolved_candidates
+            if isinstance(candidate, ExtrasCandidate)
+        )
+        for extras_candidate in extras_candidates:
+            project_name = canonicalize_name(extras_candidate.project_name)
+            ireq = result_ireqs[project_name]
+            ireq.extras |= extras_candidate.extras
+            ireq.req.extras |= extras_candidate.extras
+
+        return set(result_ireqs.values())
+
+    @staticmethod
+    def _get_reverse_dependencies(
+        resolver_result: Result,
+    ) -> Dict[str, Set[str]]:
+        reverse_dependencies: DefaultDict[str, Set[str]] = collections.defaultdict(set)
+
+        for candidate in resolver_result.mapping.values():
+            stripped_name = strip_extras(canonicalize_name(candidate.name))
+
+            for parent_name in resolver_result.graph.iter_parents(candidate.name):
+                # Skip root dependency which is always None
+                if parent_name is None:
+                    continue
+
+                # Skip a dependency that equals to the candidate. This could be
+                # the dependency with extras.
+                stripped_parent_name = strip_extras(canonicalize_name(parent_name))
+                if stripped_name == stripped_parent_name:
+                    continue
+
+                reverse_dependencies[stripped_name].add(stripped_parent_name)
+
+        return dict(reverse_dependencies)
+
+    def _get_install_requirement_from_candidate(
+        self, candidate: Candidate, reverse_dependencies: Dict[str, Set[str]]
+    ) -> Optional[InstallRequirement]:
+        ireq = candidate.get_install_requirement()
+        if ireq is None:
+            return None
+
+        # Determine a pin operator
+        version_pin_operator = "=="
+        version_as_str = str(candidate.version)
+        for specifier in ireq.specifier:
+            if specifier.operator == "===" and specifier.version == version_as_str:
+                version_pin_operator = "==="
+                break
+
+        # Prepare pinned install requirement. Copy it from candidate's install
+        # requirement so that it could be mutated later.
+        pinned_ireq = copy_install_requirement(ireq)
+
+        # Canonicalize name
+        assert ireq.name is not None
+        pinned_ireq.req.name = canonicalize_name(ireq.name)
+
+        # Pin requirement to a resolved version
+        pinned_ireq.req.specifier = SpecifierSet(
+            f"{version_pin_operator}{candidate.version}"
+        )
+
+        # Save reverse dependencies for annotation
+        ireq_key = key_from_ireq(ireq)
+        pinned_ireq._required_by = reverse_dependencies.get(ireq_key, set())
+
+        # Save source for annotation
+        source_ireq = self._constraints_map.get(ireq_key)
+        if source_ireq is not None and ireq_key not in self.existing_constraints:
+            pinned_ireq._source_ireqs = [source_ireq]
+
+        return pinned_ireq
diff --git a/piptools/scripts/compile.py b/piptools/scripts/compile.py
index 32b7d56..0c98c6b 100755
--- a/piptools/scripts/compile.py
+++ b/piptools/scripts/compile.py
@@ -21,7 +21,7 @@ from ..locations import CACHE_DIR
 from ..logging import log
 from ..repositories import LocalRequirementsRepository, PyPIRepository
 from ..repositories.base import BaseRepository
-from ..resolver import Resolver
+from ..resolver import BacktrackingResolver, LegacyResolver
 from ..utils import (
     UNSAFE_PACKAGES,
     dedup,
@@ -225,6 +225,14 @@ def _get_default_option(option_name: str) -> Any:
 @click.option(
     "--pip-args", "pip_args_str", help="Arguments to pass directly to the pip command."
 )
+@click.option(
+    "--resolver",
+    "resolver_name",
+    type=click.Choice(("legacy", "backtracking")),
+    default="legacy",
+    envvar="PIP_TOOLS_RESOLVER",
+    help="Choose the dependency resolver.",
+)
 @click.option(
     "--emit-index-url/--no-emit-index-url",
     is_flag=True,
@@ -268,6 +276,7 @@ def cli(
     emit_find_links: bool,
     cache_dir: str,
     pip_args_str: Optional[str],
+    resolver_name: str,
     emit_index_url: bool,
     emit_options: bool,
 ) -> None:
@@ -334,9 +343,10 @@ def cli(
         pip_args.extend(["--pre"])
     for host in trusted_host:
         pip_args.extend(["--trusted-host", host])
-
     if not build_isolation:
         pip_args.append("--no-build-isolation")
+    if resolver_name == "legacy":
+        pip_args.extend(["--use-deprecated", "legacy-resolver"])
     pip_args.extend(right_args)
 
     repository: BaseRepository
@@ -350,6 +360,10 @@ def cli(
 
     existing_pins_to_upgrade = set()
 
+    # Exclude packages from --upgrade-package/-P from the existing
+    # constraints, and separately gather pins to be upgraded
+    existing_pins = {}
+
     # Proxy with a LocalRequirementsRepository if --upgrade is not specified
     # (= default invocation)
     if not upgrade and os.path.exists(output_file.name):
@@ -363,9 +377,6 @@ def cli(
             options=tmp_repository.options,
         )
 
-        # Exclude packages from --upgrade-package/-P from the existing
-        # constraints, and separately gather pins to be upgraded
-        existing_pins = {}
         for ireq in filter(is_pinned_requirement, ireqs):
             key = key_from_ireq(ireq)
             if key in upgrade_install_reqs:
@@ -462,10 +473,12 @@ def cli(
             for find_link in dedup(repository.finder.find_links):
                 log.debug(redact_auth_from_url(find_link))
 
+    resolver_cls = LegacyResolver if resolver_name == "legacy" else BacktrackingResolver
     try:
-        resolver = Resolver(
-            constraints,
-            repository,
+        resolver = resolver_cls(
+            constraints=constraints,
+            existing_constraints=existing_pins,
+            repository=repository,
             prereleases=repository.finder.allow_all_prereleases or pre,
             cache=DependencyCache(cache_dir),
             clear_caches=rebuild,
diff --git a/piptools/utils.py b/piptools/utils.py
index ccd9472..47f3637 100644
--- a/piptools/utils.py
+++ b/piptools/utils.py
@@ -3,9 +3,11 @@ import copy
 import itertools
 import json
 import os
+import re
 import shlex
 import typing
 from typing import (
+    Any,
     Callable,
     Dict,
     Iterable,
@@ -441,3 +443,56 @@ def get_sys_path_for_python_executable(python_executable: str) -> List[str]:
     assert isinstance(paths, list)
     assert all(isinstance(i, str) for i in paths)
     return [os.path.abspath(path) for path in paths]
+
+
+def omit_list_value(lst: List[_T], value: _T) -> List[_T]:
+    """Produce a new list with a given value skipped."""
+    return [item for item in lst if item != value]
+
+
+_strip_extras_re = re.compile(r"\[.+?\]")
+
+
+def strip_extras(name: str) -> str:
+    """Strip extras from package name, e.g. pytest[testing] -> pytest."""
+    return re.sub(_strip_extras_re, "", name)
+
+
+def copy_install_requirement(
+    template: InstallRequirement, **extra_kwargs: Any
+) -> InstallRequirement:
+    """Make a copy of a template ``InstallRequirement`` with extra kwargs."""
+    # Prepare install requirement kwargs.
+    kwargs = {
+        "comes_from": template.comes_from,
+        "editable": template.editable,
+        "link": template.link,
+        "markers": template.markers,
+        "use_pep517": template.use_pep517,
+        "isolated": template.isolated,
+        "install_options": template.install_options,
+        "global_options": template.global_options,
+        "hash_options": template.hash_options,
+        "constraint": template.constraint,
+        "extras": template.extras,
+        "user_supplied": template.user_supplied,
+    }
+    kwargs.update(extra_kwargs)
+
+    # Original link does not belong to install requirements constructor,
+    # pop it now to update later.
+    original_link = kwargs.pop("original_link", None)
+
+    # Copy template.req if not specified in extra kwargs.
+    if "req" not in kwargs:
+        kwargs["req"] = copy.deepcopy(template.req)
+
+    ireq = InstallRequirement(**kwargs)
+
+    # If the original_link was None, keep it so. Passing `link` as an
+    # argument to `InstallRequirement` sets it as the original_link.
+    ireq.original_link = (
+        template.original_link if original_link is None else original_link
+    )
+
+    return ireq
diff --git a/piptools/writer.py b/piptools/writer.py
index a838171..6ab95f8 100644
--- a/piptools/writer.py
+++ b/piptools/writer.py
@@ -2,13 +2,25 @@ import os
 import re
 import sys
 from itertools import chain
-from typing import BinaryIO, Dict, Iterable, Iterator, List, Optional, Set, Tuple
+from typing import (
+    BinaryIO,
+    Dict,
+    Iterable,
+    Iterator,
+    List,
+    Optional,
+    Set,
+    Tuple,
+    Union,
+    cast,
+)
 
 from click import unstyle
 from click.core import Context
 from pip._internal.models.format_control import FormatControl
 from pip._internal.req.req_install import InstallRequirement
 from pip._vendor.packaging.markers import Marker
+from pip._vendor.packaging.utils import canonicalize_name
 
 from .logging import log
 from .utils import (
@@ -18,6 +30,7 @@ from .utils import (
     format_requirement,
     get_compile_command,
     key_from_ireq,
+    strip_extras,
 )
 
 MESSAGE_UNHASHED_PACKAGE = comment(
@@ -45,10 +58,10 @@ MESSAGE_UNINSTALLABLE = (
 strip_comes_from_line_re = re.compile(r" \(line \d+\)$")
 
 
-def _comes_from_as_string(ireq: InstallRequirement) -> str:
-    if isinstance(ireq.comes_from, str):
-        return strip_comes_from_line_re.sub("", ireq.comes_from)
-    return key_from_ireq(ireq.comes_from)
+def _comes_from_as_string(comes_from: Union[str, InstallRequirement]) -> str:
+    if isinstance(comes_from, str):
+        return strip_comes_from_line_re.sub("", comes_from)
+    return cast(str, canonicalize_name(key_from_ireq(comes_from)))
 
 
 def annotation_style_split(required_by: Set[str]) -> str:
@@ -263,7 +276,7 @@ class OutputWriter:
 
         line = format_requirement(ireq, marker=marker, hashes=ireq_hashes)
         if self.strip_extras:
-            line = re.sub(r"\[.+?\]", "", line)
+            line = strip_extras(line)
 
         if not self.annotate:
             return line
@@ -272,12 +285,15 @@ class OutputWriter:
         required_by = set()
         if hasattr(ireq, "_source_ireqs"):
             required_by |= {
-                _comes_from_as_string(src_ireq)
+                _comes_from_as_string(src_ireq.comes_from)
                 for src_ireq in ireq._source_ireqs
                 if src_ireq.comes_from
             }
-        elif ireq.comes_from:
-            required_by.add(_comes_from_as_string(ireq))
+
+        if ireq.comes_from:
+            required_by.add(_comes_from_as_string(ireq.comes_from))
+
+        required_by |= set(getattr(ireq, "_required_by", set()))
 
         if required_by:
             if self.annotation_style == "split":
@@ -288,6 +304,8 @@ class OutputWriter:
                 sep = "\n    " if ireq_hashes else "  "
             else:  # pragma: no cover
                 raise ValueError("Invalid value for annotation style")
+            if self.strip_extras:
+                annotation = strip_extras(annotation)
             # 24 is one reasonable column size to use here, that we've used in the past
             lines = f"{line:24}{sep}{comment(annotation)}".splitlines()
             line = "\n".join(ln.rstrip() for ln in lines)


Test patch:
diff --git a/tests/conftest.py b/tests/conftest.py
index 8e868cc..bee5079 100644
--- a/tests/conftest.py
+++ b/tests/conftest.py
@@ -1,14 +1,16 @@
 import json
-import optparse
 import os
 import subprocess
 import sys
 from contextlib import contextmanager
+from dataclasses import dataclass, field
 from functools import partial
 from textwrap import dedent
+from typing import List, Optional
 
 import pytest
 from click.testing import CliRunner
+from pip._internal.commands.install import InstallCommand
 from pip._internal.index.package_finder import PackageFinder
 from pip._internal.models.candidate import InstallationCandidate
 from pip._internal.network.session import PipSession
@@ -24,7 +26,7 @@ from piptools.cache import DependencyCache
 from piptools.exceptions import NoCandidateFound
 from piptools.repositories import PyPIRepository
 from piptools.repositories.base import BaseRepository
-from piptools.resolver import Resolver
+from piptools.resolver import BacktrackingResolver, LegacyResolver
 from piptools.utils import (
     as_tuple,
     is_url_requirement,
@@ -37,8 +39,17 @@ from .constants import MINIMAL_WHEELS_PATH, TEST_DATA_PATH
 from .utils import looks_like_ci
 
 
+@dataclass
+class FakeOptions:
+    features_enabled: List[str] = field(default_factory=list)
+    deprecated_features_enabled: List[str] = field(default_factory=list)
+    target_dir: Optional[str] = None
+
+
 class FakeRepository(BaseRepository):
-    def __init__(self):
+    def __init__(self, options: FakeOptions):
+        self._options = options
+
         with open(os.path.join(TEST_DATA_PATH, "fake-index.json")) as f:
             self.index = json.load(f)
 
@@ -91,8 +102,8 @@ class FakeRepository(BaseRepository):
         yield
 
     @property
-    def options(self) -> optparse.Values:
-        """Not used"""
+    def options(self):
+        return self._options
 
     @property
     def session(self) -> PipSession:
@@ -102,6 +113,10 @@ class FakeRepository(BaseRepository):
     def finder(self) -> PackageFinder:
         """Not used"""
 
+    @property
+    def command(self) -> InstallCommand:
+        """Not used"""
+
 
 class FakeInstalledDistribution:
     def __init__(self, line, deps=None):
@@ -145,13 +160,20 @@ def fake_dist():
 
 @pytest.fixture
 def repository():
-    return FakeRepository()
+    return FakeRepository(
+        options=FakeOptions(deprecated_features_enabled=["legacy-resolver"])
+    )
 
 
 @pytest.fixture
 def pypi_repository(tmpdir):
     return PyPIRepository(
-        ["--index-url", PyPIRepository.DEFAULT_INDEX_URL],
+        [
+            "--index-url",
+            PyPIRepository.DEFAULT_INDEX_URL,
+            "--use-deprecated",
+            "legacy-resolver",
+        ],
         cache_dir=(tmpdir / "pypi-repo"),
     )
 
@@ -166,12 +188,27 @@ def resolver(depcache, repository):
     # TODO: It'd be nicer if Resolver instance could be set up and then
     #       use .resolve(...) on the specset, instead of passing it to
     #       the constructor like this (it's not reusable)
-    return partial(Resolver, repository=repository, cache=depcache)
+    return partial(
+        LegacyResolver, repository=repository, cache=depcache, existing_constraints={}
+    )
+
+
+@pytest.fixture
+def backtracking_resolver(depcache):
+    # TODO: It'd be nicer if Resolver instance could be set up and then
+    #       use .resolve(...) on the specset, instead of passing it to
+    #       the constructor like this (it's not reusable)
+    return partial(
+        BacktrackingResolver,
+        repository=FakeRepository(options=FakeOptions()),
+        cache=depcache,
+        existing_constraints={},
+    )
 
 
 @pytest.fixture
 def base_resolver(depcache):
-    return partial(Resolver, cache=depcache)
+    return partial(LegacyResolver, cache=depcache, existing_constraints={})
 
 
 @pytest.fixture
diff --git a/tests/test_cli_compile.py b/tests/test_cli_compile.py
index 4e95f61..359ce3f 100644
--- a/tests/test_cli_compile.py
+++ b/tests/test_cli_compile.py
@@ -9,9 +9,35 @@ import pytest
 from pip._internal.utils.urls import path_to_url
 
 from piptools.scripts.compile import cli
+from piptools.utils import COMPILE_EXCLUDE_OPTIONS
 
 from .constants import MINIMAL_WHEELS_PATH, PACKAGES_PATH
 
+legacy_resolver_only = pytest.mark.parametrize(
+    "current_resolver",
+    ("legacy",),
+    indirect=("current_resolver",),
+)
+
+
+@pytest.fixture(
+    autouse=True,
+    params=[
+        pytest.param("legacy", id="legacy resolver"),
+        pytest.param("backtracking", id="backtracking resolver"),
+    ],
+)
+def current_resolver(request, monkeypatch):
+    # Hide --resolver option from pip-compile header, so that we don't have to
+    # inject it every time to tests outputs.
+    exclude_options = COMPILE_EXCLUDE_OPTIONS | {"--resolver"}
+    monkeypatch.setattr("piptools.utils.COMPILE_EXCLUDE_OPTIONS", exclude_options)
+
+    # Setup given resolver name
+    resolver_name = request.param
+    monkeypatch.setenv("PIP_TOOLS_RESOLVER", resolver_name)
+    return resolver_name
+
 
 @pytest.fixture(autouse=True)
 def _temp_dep_cache(tmpdir, monkeypatch):
@@ -421,6 +447,7 @@ def test_editable_package_without_non_editable_duplicate(pip_conf, runner):
     assert "small-fake-a==" not in out.stderr
 
 
+@legacy_resolver_only
 def test_editable_package_constraint_without_non_editable_duplicate(pip_conf, runner):
     """
     piptools keeps editable constraint,
@@ -445,6 +472,7 @@ def test_editable_package_constraint_without_non_editable_duplicate(pip_conf, ru
     assert "small-fake-a==" not in out.stderr
 
 
+@legacy_resolver_only
 @pytest.mark.parametrize("req_editable", ((True,), (False,)))
 def test_editable_package_in_constraints(pip_conf, runner, req_editable):
     """
@@ -483,6 +511,7 @@ def test_editable_package_vcs(runner):
     assert "click" in out.stderr  # dependency of pip-tools
 
 
+@legacy_resolver_only
 def test_locally_available_editable_package_is_not_archived_in_cache_dir(
     pip_conf, tmpdir, runner
 ):
@@ -649,7 +678,7 @@ def test_relative_file_uri_package(pip_conf, runner):
 def test_direct_reference_with_extras(runner):
     with open("requirements.in", "w") as req_in:
         req_in.write(
-            "piptools[testing,coverage] @ git+https://github.com/jazzband/pip-tools@6.2.0"
+            "pip-tools[testing,coverage] @ git+https://github.com/jazzband/pip-tools@6.2.0"
         )
     out = runner.invoke(cli, ["-n", "--rebuild"])
     assert out.exit_code == 0
@@ -673,6 +702,20 @@ def test_input_file_without_extension(pip_conf, runner):
     assert os.path.exists("requirements.txt")
 
 
+def test_ignore_incompatible_existing_pins(pip_conf, runner):
+    """
+    Successfully compile when existing output pins conflict with input.
+    """
+    with open("requirements.txt", "w") as req_txt:
+        req_txt.write("small-fake-a==0.2\nsmall-fake-b==0.2")
+    with open("requirements.in", "w") as req_in:
+        req_in.write("small-fake-with-deps\nsmall-fake-b<0.2")
+
+    out = runner.invoke(cli, [])
+
+    assert out.exit_code == 0
+
+
 def test_upgrade_packages_option(pip_conf, runner):
     """
     piptools respects --upgrade-package/-P inline list.
@@ -1021,6 +1064,7 @@ def test_bad_setup_file(runner):
     assert f"Failed to parse {os.path.abspath('setup.py')}" in out.stderr
 
 
+@legacy_resolver_only
 def test_no_candidates(pip_conf, runner):
     with open("requirements", "w") as req_in:
         req_in.write("small-fake-a>0.3b1,<0.3b2")
@@ -1031,6 +1075,7 @@ def test_no_candidates(pip_conf, runner):
     assert "Skipped pre-versions:" in out.stderr
 
 
+@legacy_resolver_only
 def test_no_candidates_pre(pip_conf, runner):
     with open("requirements", "w") as req_in:
         req_in.write("small-fake-a>0.3b1,<0.3b1")
@@ -1207,30 +1252,73 @@ def test_annotate_option(pip_conf, runner, options, expected):
 
     out = runner.invoke(cli, [*options, "-n", "--no-emit-find-links"])
 
+    assert out.exit_code == 0, out
     assert out.stderr == dedent(expected)
-    assert out.exit_code == 0
 
 
 @pytest.mark.parametrize(
     ("option", "expected"),
     (
-        ("--allow-unsafe", "small-fake-a==0.1"),
-        ("--no-allow-unsafe", "# small-fake-a"),
-        (None, "# small-fake-a"),
+        pytest.param(
+            "--allow-unsafe",
+            dedent(
+                """\
+                small-fake-a==0.1
+                small-fake-b==0.3
+                small-fake-with-deps==0.1
+                """
+            ),
+            id="allow all packages",
+        ),
+        pytest.param(
+            "--no-allow-unsafe",
+            dedent(
+                """\
+                small-fake-b==0.3
+
+                # The following packages are considered to be unsafe in a requirements file:
+                # small-fake-a
+                # small-fake-with-deps
+                """
+            ),
+            id="comment out small-fake-with-deps and its dependencies",
+        ),
+        pytest.param(
+            None,
+            dedent(
+                """\
+                small-fake-b==0.3
+
+                # The following packages are considered to be unsafe in a requirements file:
+                # small-fake-a
+                # small-fake-with-deps
+                """
+            ),
+            id="allow unsafe is default option",
+        ),
     ),
 )
 def test_allow_unsafe_option(pip_conf, monkeypatch, runner, option, expected):
     """
     Unsafe packages are printed as expected with and without --allow-unsafe.
     """
-    monkeypatch.setattr("piptools.resolver.UNSAFE_PACKAGES", {"small-fake-a"})
+    monkeypatch.setattr("piptools.resolver.UNSAFE_PACKAGES", {"small-fake-with-deps"})
     with open("requirements.in", "w") as req_in:
-        req_in.write(path_to_url(os.path.join(PACKAGES_PATH, "small_fake_with_deps")))
+        req_in.write("small-fake-b\n")
+        req_in.write("small-fake-with-deps")
 
-    out = runner.invoke(cli, ["--no-annotate", option] if option else [])
+    out = runner.invoke(
+        cli,
+        [
+            "--no-header",
+            "--no-emit-options",
+            "--no-annotate",
+            *([option] if option else []),
+        ],
+    )
 
-    assert expected in out.stderr.splitlines()
-    assert out.exit_code == 0
+    assert out.exit_code == 0, out
+    assert out.stderr == expected
 
 
 @pytest.mark.parametrize(
@@ -1487,6 +1575,7 @@ def test_options_in_requirements_file(runner, options):
         ),
     ),
 )
+@legacy_resolver_only
 def test_unreachable_index_urls(runner, cli_options, expected_message):
     """
     Test pip-compile raises an error if index URLs are not reachable.
@@ -2138,3 +2227,23 @@ def test_cli_compile_strip_extras(runner, make_package, make_sdist, tmpdir):
     assert out.exit_code == 0, out
     assert "test-package-2==0.1" in out.stderr
     assert "[more]" not in out.stderr
+
+
+def test_resolution_failure(runner):
+    """Test resolution impossible for unknown package."""
+    with open("requirements.in", "w") as reqs_out:
+        reqs_out.write("unknown-package")
+
+    out = runner.invoke(cli)
+
+    assert out.exit_code != 0, out
+
+
+def test_resolver_reaches_max_rounds(runner):
+    """Test resolver reched max rounds and raises error."""
+    with open("requirements.in", "w") as reqs_out:
+        reqs_out.write("six")
+
+    out = runner.invoke(cli, ["--max-rounds", 0])
+
+    assert out.exit_code != 0, out
diff --git a/tests/test_resolver.py b/tests/test_resolver.py
index a9beca1..0e9b2fe 100644
--- a/tests/test_resolver.py
+++ b/tests/test_resolver.py
@@ -1,4 +1,5 @@
 import pytest
+from pip._internal.exceptions import DistributionNotFound
 from pip._internal.utils.urls import path_to_url
 
 from piptools.exceptions import NoCandidateFound
@@ -500,3 +501,28 @@ def test_requirement_summary_with_other_objects(from_line):
     requirement_summary = RequirementSummary(from_line("test_package==1.2.3"))
     other_object = object()
     assert requirement_summary != other_object
+
+
+@pytest.mark.parametrize(
+    ("exception", "cause"),
+    (
+        pytest.param(DistributionNotFound, None, id="without cause"),
+        pytest.param(DistributionNotFound, ZeroDivisionError, id="with cause"),
+    ),
+)
+def test_catch_distribution_not_found_error(backtracking_resolver, exception, cause):
+    """
+    Test internal edge-cases when backtracking resolver catches
+    and re-raises ``DistributionNotFound`` error with/without causes.
+    """
+    resolver = backtracking_resolver([])
+
+    class FakePipResolver:
+        def resolve(self, *args, **kwargs):
+            raise exception from cause
+
+    with pytest.raises(DistributionNotFound):
+        resolver._do_resolve(
+            resolver=FakePipResolver(),
+            compatible_existing_constraints={},
+        )