Pub's version resolution goes exponential

[mkustermann]

Similar to Issue 874, I ran into a case where pub upgrade takes forever -- most likely due to pub's constraint solver. The way to reproduce it is to:

# This happens at origin/master == e7ce2a3278cb6d0b631242ac38fab3e17e3c0b74
$ git clone https://github.com/dart-lang/pub-dartlang-dart
$ cd pub-dartlang-dart/app
$ pub upgrade
Resolving dependencies... (7:00s)

I gave up after 7 minutes.

Since fetching pub dependencies worked fine until now there is a solution to the package constraints and pub should be able to discover it.

I can only suspect this started happening after publishing a new version of package:googleapis_auth with changed dependencies on package:crypto.

The version of pub is:

$ pub --version
Pub 1.17.0-dev.3.0

@nex3 Since you made some improvements, which closed Issue 874, I was wondering if you could take a look?

/cc @sgjesse

[nex3]

I'm going to merge this into #912, which despite its name is currently tracking all improvements to the solver. @mkustermann, can you post the pubspec which is causing the exponential explosion in a comment on that issue?

[mkustermann]

@nex3 It might actually not be the same issue. #912 seems to be about showing a nice message when pub does too much backtracking, I filed this issue because there should be a feasible solution and pub should be able to find it (I understand that the worst-case time complexity of a general constraint solver is exponential, but normal pubspec dependencies have a lot of structure one can exploit during resolution, so maybe the current algorithm could be improved).

I'll leave it up to you to reopen this issue or not.

As you asked, I've attached the pubspec file to the other issue.

[zoechi]

@mkustermann It usually helps to narrow the version constraints (perhaps even to one single possibility). This way you might be able to show that a solution actually exists.

[nex3]

The title of #912 is misleading; it's actually tracking all work on improving the solver, not just making the output better (the two turn out to be very tightly linked).