“Learn” to avoid trying routes that do not affect the dependency graph

[uranusjr]

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.

[pfmoore]

I'm not sure I understand. You say "setuptools does not have dependencies", but surely we can only say that "this specific version of setuptools does not have dependencies"? If we backtrack and try a different version of setuptools, we might get one that does have dependencies.

Am I missing something? (It's early and I haven't had a cup of tea yet, so it's quite likely 🙂)

[uranusjr]

Yes, sorry for the lax language, I was in a hurry writing the message. What I have in mind is the resolver should be able to look at (say) setuptools 40, and realise the rest of the dependency graph after pinning it would be exactly the same as setuptools 40.1. So if 40.1 failed, 40.0 is also destined to fail, and should be skipped entirely. But if setuptools x does have dependencies (or more generally, have a different set of dependencies from other versions we’ve tried), then we should try it.

[pfmoore]

Ah, OK. So if we fail on 40.1, then the resolver can ask the provider "does 40.0 have the same dependencies?" and ignore 40.0 if the answer is "no".

I can see how that would help, but would it not be almost as good (and not require an additional mechanism) if the provider cached dependency data in memory, so that checking 40.0 would be fast enough that skipping it is not worth it? That would mean breaking pathological cases like projects that calculate dependencies randomly, but IMO it's fine for a provider to make that choice (and I'd be fine with pip doing so, as we already cache wheels which in effect does that).

Of course, it's not an either/or choice - we can do both.

[pradyunsg]

IIUC, This is essentially the CDCL style behaviour - I'm not a 100% sure I understand how we'd phrase that in terms of criterion-based model we have here, but I'm a strong +1 on this.

[uranusjr]

The main things this is trying to avoid is not setuptools itself, but the states derived after setuptools 40.04 is pinned. If the resolution process is thought as a maze, setuptools 41.0 and 40.0 are two doors that lead to the same room. With naive backtracking, we’ll need to check all the doors that room has every time we enter it, but if we can somehow identify that the two doors (versions) bring us to the same room (state of criteria), we can avoid exploring the room the second time altogether. This can be done after we enter the room (i.e. pinning setuptools 40.0), but since each resolution round in resolvelib is a process of pinning + adding dependencies, doing it after entering the room (pinning) means we somehow need to abort a round half way; it is probably easier to “peek” before we walk through the setuptools 40.0 door (I think). The main challenge here would be to implement an efficient way to identify whether we indeed are entering the same room (i.e. implement equality on the criteria-held requirements in a state).

And yes, this is basically Conflict Driven Clause Learning (CDCL). We can express each resolvelib as an unsatisfied boolean formula,^{[citation needed]} and everything beside setuptools!=40.0 is already known to evaluate to false, so we can perform unit propagation and derive setuptools!=40.0 must be true. But this can be explained in a human-friendly way, so I would prefer to not bring in martian language 🙂

[pfmoore]

Cool. I checked the Wikipedia entry on CDCL, and I definitely prefer your explanation 🙂

[pradyunsg]

Whoops! I should've used more words, and communicated more clearly. Here's my attempt at describing CDCL in simpler terms:

remembering about "things that conflict", so that it knows when it's gonna see the same conflict later, because it changed a component that doesn't affect the conflict.

"it" is the resolver.

As @uranusjr put it, the trick is figuring out "things that conflict" and efficiently detecting when that re-occurs.

[pradyunsg]

Do you reckon #84 handles this?

[notatallshaw]

Do you reckon #84 handles this?

I'm reading through Wikipedia's example of CDCL and it has a step analogous to what I wanted to implemented as part of #84: "Step 14 - Non-chronological back jump to appropriate decision level"

I believe this could make an even bigger difference on reducing the amount of backtracking, but the complexity looked to be too much to implement as a first PR. And I found that implementing just the part of preferring failure causes was good enough for almost all real world examples I could find.

[notatallshaw]

I've been thinking about this further today and I would say the optimization I've implemented as part of #84 is only effective for what I would call "shallow conflicts", i.e. conflicts where by focusing on the requirements of the known failures at the current position in the dependency tree you are able to resolve those conflicts and find a solution for all the requirements without significant backtracking up the dependency tree.

However I would call a "deep conflict" where you have found failures but to find a solution it requires significantly backtracking up the dependency tree because those failures were pinned many rounds ago. An example of this is "airflow[all]==1.10.13".

My gut feeling is there are strong techniques that can tackle these problems. But let's see if they are reported first?

[notatallshaw]

I've been mulling on this idea and I think I have devised a simple(ish) approach to implementing an analogous step to the "Non-chronological back jump" in CDCL and how that might be used to speed up resolution. Once #84 and pypa/pip#10481 land I'm going to start experimenting and see if I can actually implement it and if there are really use cases it can improve.

By definition it will actually change the behavior of the resolver itself, not just give the downstream library the opportunity to choose a different path, so if I can implement it and show it helps in some cases it's still probably going to take even more agreement that it's a good approach.

[notatallshaw]

I've started work on this "Non-chronological back jump" and even though I've only implemented a naive solution I've already had very good success with it, I have 2 primary tests (both happen to be Python 3.7 only):

Test 1 (runs dozens of times faster with back jumps):

poetry2setup
wheel
twine

Test 2 (actually able to achieve ResolutionImpossible after ~5-10 mins [using cache] with back jumps):

apache-airflow[all]==1.10.13

For those curious here is the output of the apache airflow resolution impossible (click to expand)

ERROR: Cannot install apache-airflow and boto3 because these package versions have conflicting dependencies.

The conflict is caused by:
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.26 depends on botocore<1.17.0 and >=1.16.26
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.25 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.24 depends on botocore<1.17.0 and >=1.16.24
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.23 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.22 depends on botocore<1.17.0 and >=1.16.22
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.21 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.20 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.19 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.18 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.17 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.16 depends on botocore<1.17.0 and >=1.16.16
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.15 depends on botocore<1.17.0 and >=1.16.15
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.14 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.13 depends on botocore<1.17.0 and >=1.16.13
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.12 depends on botocore<1.17.0 and >=1.16.12
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.11 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.10 depends on botocore<1.17.0 and >=1.16.10
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.9 depends on botocore<1.17.0 and >=1.16.9
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.8 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.7 depends on botocore<1.17.0 and >=1.16.7
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.6 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.5 depends on botocore<1.17.0 and >=1.16.5
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.4 depends on botocore<1.17.0 and >=1.16.4
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.13.3 depends on botocore<1.17.0 and >=1.16.3
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.2 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.1 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.13.0 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.49 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.48 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.47 depends on botocore<1.16.0 and >=1.15.47
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.46 depends on botocore<1.16.0 and >=1.15.46
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.45 depends on botocore<1.16.0 and >=1.15.45
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.44 depends on botocore<1.16.0 and >=1.15.44
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.43 depends on botocore<1.16.0 and >=1.15.43
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.42 depends on botocore<1.16.0 and >=1.15.42
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.41 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.40 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.39 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.38 depends on botocore<1.16.0 and >=1.15.38
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.37 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.36 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.35 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.34 depends on botocore<1.16.0 and >=1.15.34
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.33 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.32 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.31 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.30 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.29 depends on botocore<1.16.0 and >=1.15.29
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.28 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.27 depends on botocore<1.16.0 and >=1.15.27
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.26 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.25 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.24 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.23 depends on botocore<1.16.0 and >=1.15.23
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.22 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.21 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.20 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.19 depends on botocore<1.16.0 and >=1.15.19
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.18 depends on botocore<1.16.0 and >=1.15.18
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.17 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.16 depends on botocore<1.16.0 and >=1.15.16
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.15 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.14 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.13 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.12 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.11 depends on botocore<1.16.0 and >=1.15.11
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.10 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.9 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.8 depends on botocore<1.16.0 and >=1.15.8
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.7 depends on botocore<1.16.0 and >=1.15.7
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.6 depends on botocore<1.16.0 and >=1.15.6
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.5 depends on botocore<1.16.0 and >=1.15.5
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.4 depends on botocore<1.16.0 and >=1.15.4
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.12.3 depends on botocore<1.16.0 and >=1.15.3
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.2 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.1 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.12.0 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.17 depends on botocore<1.15.0 and >=1.14.17
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.16 depends on botocore<1.15.0 and >=1.14.16
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.15 depends on botocore<1.15.0 and >=1.14.15
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.14 depends on botocore<1.15.0 and >=1.14.14
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.13 depends on botocore<1.15.0 and >=1.14.13
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.12 depends on botocore<1.15.0 and >=1.14.12
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.11.11 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.11.10 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.11.9 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.8 depends on botocore<1.15.0 and >=1.14.8
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.11.7 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.6 depends on botocore<1.15.0 and >=1.14.6
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.11.5 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.11.4 depends on s3transfer<0.4.0 and >=0.3.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.11.3 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.2 depends on botocore<1.15.0 and >=1.14.2
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.11.1 depends on s3transfer<0.4.0 and >=0.3.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.11.0 depends on botocore<1.15.0 and >=1.14.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.50 depends on botocore<1.14.0 and >=1.13.50
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.49 depends on botocore<1.14.0 and >=1.13.49
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.48 depends on s3transfer<0.3.0 and >=0.2.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.47 depends on botocore<1.14.0 and >=1.13.47
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.46 depends on s3transfer<0.3.0 and >=0.2.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.45 depends on botocore<1.14.0 and >=1.13.45
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.44 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.43 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.42 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.41 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.40 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.39 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.38 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.37 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.36 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.35 depends on s3transfer<0.3.0 and >=0.2.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.34 depends on botocore<1.14.0 and >=1.13.34
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.33 depends on botocore<1.14.0 and >=1.13.33
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.32 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.31 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.30 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.29 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.28 depends on s3transfer<0.3.0 and >=0.2.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.27 depends on botocore<1.14.0 and >=1.13.27
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.26 depends on s3transfer<0.3.0 and >=0.2.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.25 depends on botocore<1.14.0 and >=1.13.25
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.24 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.23 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.22 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.21 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.20 depends on s3transfer<0.3.0 and >=0.2.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.19 depends on botocore<1.14.0 and >=1.13.19
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.18 depends on botocore<1.14.0 and >=1.13.18
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.17 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.16 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.15 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.14 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.13 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.12 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.11 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.10 depends on s3transfer<0.3.0 and >=0.2.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.9 depends on botocore<1.14.0 and >=1.13.9
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.8 depends on botocore<1.14.0 and >=1.13.8
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.7 depends on botocore<1.14.0 and >=1.13.7
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.6 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.5 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.4 depends on s3transfer<0.3.0 and >=0.2.0
    moto 1.3.14 depends on botocore>=1.12.201
    boto3 1.18.60 depends on botocore<1.22.0 and >=1.21.60
    s3transfer 0.5.0 depends on botocore<2.0a.0 and >=1.12.36
    boto3 1.10.3 depends on botocore<1.14.0 and >=1.13.3
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.2 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.1 depends on s3transfer<0.3.0 and >=0.2.0
    boto3 1.18.60 depends on s3transfer<0.6.0 and >=0.5.0
    boto3 1.10.0 depends on s3transfer<0.3.0 and >=0.2.0

To fix this you could try to:
1. loosen the range of package versions you've specified
2. remove package versions to allow pip attempt to solve the dependency conflict

ERROR: ResolutionImpossible: for help visit https://pip.pypa.io/en/latest/user_guide/#fixing-conflicting-dependencies

The idea of this approach is that if the failure causes have been previously pinned beyond the most recent pinning then to "back jump" to the state where they were last pinned and attach the new backtrack causes to that state.

This allows the failure causes to all be focused on together and means the resolution doesn't get stuck backtracking on some intermediate pinned requirement. It may also require an extra step of deciding if not all the backtrack causes are currently available to pin then pin the non-backtrack causes until they are, but I have not experimented with this yet.

In general this approach is a lot more tricky and potentially prone to infinite loops if not careful, but I think worth further exploration and I will continue to do so.

[pradyunsg]

apache-airflow[all]==1.10.13

This failing doesn't make sense -- there is a solution for this in the space that the resolver is exploring?

Doesn't pip install "apache-airflow[all]==1.10.13" --constraint "https://raw.githubusercontent.com/apache/airflow/constraints-1.10.13/constraints-3.7.txt" work, in those cases?