Improve the version solver

[DartBot]

Edit by @nex3: I've retargeted this issue to track a major version solver refactor that should allow us to fix the solver's invalid error messages, further limit the cases in which it goes exponential, and semantically determine when a package graph is too complex to solve.

---

Issue by tomaskulich Originally opened as dart-lang/sdk#17429

---

Attachments: pubspec.yaml (625 Bytes) pubtrace.zip (0 Bytes)

[DartBot]

Comment by tomaskulich

---

Attachment: pubtrace.zip (179.34 KB)

[DartBot]

Comment by tomaskulich

---

Update: I just read http://news.dartlang.org/2013/04/pubs-new-constraint-solver.html and I'm afraid I understand, what is going on.

Some naive coder produced a (in all other terms, fine quality) package on which I depend, however, he put too restricting version-constraint on some of his dependencies. Now it's hard to find a fit for all these dependencies, and pub instead of shouting this problem all over the place starts to

wait for it

BACKTRACKING THROUGH A WHOLE UNIVERSE OF ALL POSSIBLE COMBINATIONS OF PACKAGE VERSIONS in a desperate attempt to heroically fulfill THE constrains.

Dear Dart creators, most of you probably have CS degrees, so you should understand HOW VAST THIS UNIVERSE IS!

If you really want to help the users, try something like this: Do some random-dependency-picking (or maybe even some sort of simulated annealing) for FIXED amount of time and FIXED memory usage (does pub memory leak?); collect heuristic information about possible problems (too restrictive dependencies between packages;) and then, eventually, REPORT A PROBLEM!

It's for no use, if pub keeps heroically eating crazy amounts of my time and my RAM.

[DartBot]

Comment by munificent

---

• error 'Connection closed before full header was received, uri = https://pub.dartlang.org/api/packages/http/versions/0.9.2%2B1' is printed, no packages are downloaded

This is an unrelated issue. Can you repro this reliably? If so, can you give me some details on your configuration?

• or, the memory is exhausted. (see zipped output from pub --verbose get)

This probably happens in verbose mode, but not in non-verbose.

However, since my pubspec.yaml is not so bug, I would expect pub behaving more correctly.

The size of your pubspec means very little in the grand scheme of things. It may have only one dependency, but if that dependency in turn has a ton, then you're going to slurp in the world. What matters is the size of your transitive dependency graph.

BACKTRACKING THROUGH A WHOLE UNIVERSE OF ALL POSSIBLE COMBINATIONS OF PACKAGE VERSIONS in a desperate attempt to heroically fulfill THE constrains.

On my machine, it does that successfully and finds a solution in 1m30s. Still slower than I'd like, but some pathological package graphs are bound to be slow.

most of you probably have CS degrees, so you should understand HOW VAST THIS UNIVERSE IS!

I actually don't have a CS degree, but I am aware that constraint solving is NP-complete. In fact, you can generate a set of pub packages that model any 3SAT problem.

Do some random-dependency-picking (or maybe even some sort of simulated annealing)

We can't do that because it would then lead to non-deterministic results. Running pub upgrade shouldn't be like pulling the lever on a slot machine!

for FIXED amount of time

If a user wants to limit the time pub spends, they can always just Ctrl-C if it takes too long. If we add an artificial limit, all that means is that we'll fail for some users who would otherwise be patient enough to wait.

We discussed this, but adding a limit seems to be strictly worse than not having one.

FIXED memory usage (does pub memory leak?);

It doesn't have any leaks that we're aware of. But note that if you run it in verbose mode, it ends up using quite a bit of memory for the log transcript. There are some optimizations we could do there.

collect heuristic information about possible problems (too restrictive dependencies between packages;) and then, eventually, REPORT A PROBLEM!

This is a great idea. I'll leave this bug open for that (and update the description).

In your case, the problem is that clean_backend depends on an old version of path. Path is a widely shared dependency, so constraining that pulls down the entire package graph.

In general, to have a healthier package ecosystem where constraint solving works well, the low level packages that everyone uses need to be pretty stable. This is part of the reason we pushed path to 1.0.0: when it churns, it causes everyone pain.

In this case, I can see that most common disjoint constraint that the solver had to backtrack on was from path, so a simple heuristic to it keep a count of how often we hit a disjoint constraint for each package. We could then either report that to the user or possibly take that into account when backtracking and try to route around it.

---

Added Triaged label. Changed the title to: "Use heuristics to show why solving is taking a long time".

[DartBot]

Comment by tomaskulich

---

Attachment: pubspec.yaml (578 Bytes)

[DartBot]

Comment by tomaskulich

---

Did you succeeded in reproducing the bug? If this is problem for you, I can grant you access to one of my Amazon AWS machines, it fails very consistently there.

[DartBot]

Comment by lrhn

---

Added Area-Pub label.

[DartBot]

Comment by nex3

---

This is an unrelated issue. Can you repro this reliably? If so, can you give me some details on your configuration?

This is actually probably not unrelated; we've seen connection errors before on pathological graphs. It's often caused by making too many requests to the server too quickly.

WHAT SHOULD DEFAULT BEHAVIOR OF PUB BE

I like Bob's suggestion of printing this information automatically if version solving is taking a long time. That said, even if we're pretty confident something pathological is going on, it's non-trivial to figure out the specifics. If it were easy, we'd use that to just do version resolution quickly.

It's probably possible to come up with some way of saying "it's likely that this resolution is taking a long time due to constraints on package X", but doing that well will take a considerable amount of work that we're unlikely to be able to spare at the moment. If you want to take a stab at it, please feel free.

WHY THIS BOTHERS ME SO MUCH

I think you may be overstating the severity of the issue here. As far as we've seen, these pathological problems only come up when there are substantial version clashes in a dependency graph. It should be fixable without too much trouble by submitting a few patches to upgrade third-party packages, or even forking them yourself.

MY IDEA FOR IMPROVEMENT, RANDOMNESS AND EVERYTHING

Seeding the randomness from the pubspec doesn't help much. It still trains users that if their version resolution is failing, they can re-order their dependencies (or whatever) and try again. This is not something we want to encourage our users to do.

[DartBot]

Comment by nex3

---

Issue #971 has been merged into this issue.

---

cc @keertip.

[DartBot]

Comment by munificent

---

Removed Type-Defect, Priority-Unassigned labels. Added Type-Enhancement, Priority-Medium labels.

[DartBot]

Comment by nex3

---

Issue #1159 has been merged into this issue.

[DartBot]

Comment by nex3

---

Issue #1170 has been merged into this issue.

---

cc @munificent. cc @alan-knight. cc @ricowind. cc @whesse. cc @kasperl.

[DartBot]

Comment by alan-knight

---

I have a theory that the connection issue is that the solver goes away into exponential land without doing any network activity long enough for the network connection to time out. I do see that the progress indicator display stutters when solving a complicated problem like this, so if it stutters long enough....

[DartBot]

Comment by kasperl

---

In my book, this is a pretty serious usability issue reported by multiple people. Issue #1159 and issue #1170 contain reproductions.

---

Added this to the 1.8 milestone. Removed Type-Enhancement, Priority-Medium labels. Added Type-Defect, Priority-High labels.

[DartBot]

Comment by nex3

---

Issue #1171 has been merged into this issue.

[DartBot]

Comment by nex3

---

Issue #1171 has been merged into this issue.

[DartBot]

Comment by nex3

---

Issue #1187 has been merged into this issue.

[DartBot]

Comment by ricowind

---

This is marked priority high and milestone 1.8, could we get an owner?

[DartBot]

Comment by munificent

---

I know this is an annoyance to users when it occurs, but we don't have immediate plans to try to solve it in pub itself. The simplest fix is and has been to address this at the ecosystem level: make sure packages have correct version ranges and try not to rev breaking changes in popular packages too frequently.

---

Set owner to @munificent. Removed this from the 1.8 milestone. Removed Priority-High label. Added Priority-Medium label.

[DartBot]

Comment by nex3

---

Issue #1237 has been merged into this issue.

[cedx]

+1 It can be very very hard to track down those dependency errors. I had the deadly Package xxx has no versions that match [...] message and no clue on how to fix it.

[nex3]

Note to future Natalie: #1371 has an example of a pair of simple pubspecs that (as of pub 1.14.0-edge.db643f5ae217e6af3f97d5738e2f0fb0cf327ece) goes seriously exponential.

[MikeMitterer]

This bug is sooooo annoying - I have it almost every day. In larger projects you can only guess which lib causes the problem.

Even more annoying is the stupid error message:

Package reflectable has no versions that match >=0.5.0 <0.6.0 derived from:
- beanvalidator 0.1.0 depends on version ^0.5.0
- validate_sample depends on version ^0.5.0

:rage:

[juliemr]

Also running into this, making a little more noise on this issue :)

[nex3]

I'm going to try to budget some serious time to work on this next quarter.

[aghassemi]

This error message is really misleading when the reason for not resolving is version mismatch in sub dependencies of two different direct dependencies. The error should indicate these reasons and also provide suggestions on version combinations that can actually be resolved. Whenever I run into this, it becomes a fishing trip to find versions of my dependencies that can work with each other. Very time consuming effort.

[munificent]

also provide suggestions on version combinations that can actually be resolved

If it could do that, it would just pick those versions and resolve successfully. :) Unfortunately, version constraint solving is NP-complete and sometimes it can't find a solution. When it can't, you get this error.

The error message is completely misleading—the thing it tells you is wrong often has little to do with the change that you would make to fix the issue. But, unfortunately, it's hard for it to give you a better message. I do wish, until we have a better error, we would at least have a more vague one instead of leading you on a wild goose chase, but I haven't had any time to work on pub lately.

[johnpryan]

FWIW I've been running into this issue. Here's a simple way to reproduce using dart 1.16:

name: noversionsthatmatch
dependencies:
  angular: ^1.0.0
  source_gen: ^0.5.0

outputs the no versions that match message:

$ pub get
Resolving dependencies... (1.7s) 
Package angular has no versions that match >=1.0.0 <2.0.0 derived from:
- noversionsthatmatch depends on version ^1.0.0

[zoechi]

@johnpryan Sure, it's easy to reproduce. You just need two dependencies that aren't compatible. The "bug" is only the unhelpful message.

[johnpryan]

@zoechi Yes a more helpful message would help. I'm curious if it makes sense to stop searching for dependencies after a while. Watching a pub get run indefinitely is also not a great user experience.

[zoechi]

@johnpryan it times out eventually AFAIK. The timeout might be a bit long but with a slow connection and short timeouts it probably stops too early.

[mkustermann]

Attached a pubspec which causes backtracking even though there should be a feasible solution to the constraints. pubspec.yaml.txt

[travissanderson-wf]

quite a few of us have hit https://github.com/dart-lang/sdk/issues/26763 which was closed as a dupe of this issue, it is very tough issue to debug and/or discover a workaround for

[whesse]

I just looked at the backtracking solver and found that it doesn't use boosting, which is a major strategy that SAT solvers and other CSP solvers use to improve performance. The current backtracking solver adds dependencies as they are found, in the depth-first search of the dependency tree. With boosting, the clause (or package in this case) which is infeasible has its priority boosted, so that a solution to it is chosen earlier in the search, after backtracking. In this way, the kernel of packages that are infeasible gets boosted, so we only try choices of them, ignoring the other packages. Of course, if we boost too high, we haven't seen it as a dependency yet. Boosting would mainly help by choosing the order in which to queue the new dependencies added by a single package.

An alternative, which would help a log in giving a useful error message, would be to see if there are 1 or 2 packages which are "causing" the failure, in that, if they were removed, the solver can find a solution. You could start by picking the package that is either the source of an unsatisfiable constraint, or the package that has no satisfiable version. Try running the solver in a mode in which it ignores any constraints on that package, and and constraints from it. If it succeeds, then you have tracked down a package that is key to the problem. But you want to find the package furthest down the dependency graph, probably, not an important one near the root, to "drop" in this way, because you lose part of the dependency graph when you ignore a package. But here is a suggestion for how to find a package lower in the dependency graph to drop instead, if it exists:

If you find a package that you can "drop" this way, then solve the dependency graph, postponing choosing a version for this package, and then see if you have no feasible version of this package. If so, report this package as the problem. Otherwise, continue solving, and you will have pushed the problem down to one of its dependencies. You can then find out if there is a solution when you ignore that (lower) dependency, and then you have found a conflict lower in the dependency graph, and hopefully a dependency that, if you ignore it, lets you solve the problem, and is low in the graph. You can report this dependency, and the constraints on it, and the packages that cause those constraints.

If you want me to help on this, let me know.

[munificent]

Fascinating! I confess that when I wrote the backtracker, my knowledge of constraint solving was (and is) pretty limited, so I'm not surprised there's some advanced stuff it could be doing. I was also hesitant to apply too many heuristics that affected the order that the solver tried things because I wanted to ensure that it deterministically picked a solution that wasn't too sensitive to details of the package graph.

I know @nex3 put a lot of love into the solver recently to help around this issue, but I don't know the status of it. When she's around, hopefully she'll chime in.

[nex3]

I'm actively working on this—as you can see from all the related commits I've made over the past month :wink:. It's a tough problem, but I have some very solid progress on a plan for improving the error output and reducing the cases where backtracking goes exponential, including boosting problem packages.

[robbecker-wf]

What's the latest on this? No updates in a while. I'd like to see better error messages for incompatible versions. Is it blocked up in this refactor?

[nex3]

I haven't had time allocated towards this for the last few quarters. I'm hoping to come back to it in Q2 this year, but I can't make any promises.

[ryanhanks-wf]

Any updates on this? We'd love to see this realized.

[travissanderson-wf]

+1 this is commonly grumbled about / apologized for when getting people up to speed on Dart

[lamvak]

Grumble! :) Can anyone share some current workaround best practices?

[zoechi]

You can use http://mediator.thosakwe.com/ (https://github.com/thosakwe/mediator_web) to track down conflicts

[travissanderson-wf]

We have a short script for finding the most relevant output from pub get, the "inconsistent constraint" lines. @thosakwe has also made a Dart library, usable in this web app http://mediator.thosakwe.com, that does the same.

[thosakwe]

Some updates are on their way to make mediator friendlier to use 👍

[nex3]

In #1745, @matanlurey points out that pub downgrade often goes exponential for real-world packages.

[MikeMitterer]

Resolving dependencies... (1.9s)
Package l10n has no versions that match 1.2.2 derived from:
- beanvalidator depends on version 1.2.2

As you can see l10n is on 1.2.2 - actually the problem was that BeanValidator had a dependency on console_log_handler ^0.3.0 and l10n had the same dependency on version ^0.4.0

pub's error message is far more confusing than helpful

[MikeMitterer]

I found my specific problem - and I think its a general problem with Darts dependencies...

@zoechi mentioned Mediator which I tried. Mediator (@thosakwe ) failed with my git-dependencies. Today I change all my git-dependencies to local path-dependencies. This brought me one step further.

Mediator output:

Found 2 mismatching dependencies on package:dart_style:
  * sass_builder->build_runner requires  ^1.0.0
  * mobiad_rest_ui_mdl->servicefile->restrequest->webapp_base_signer->cryptoutils->zengen->source_gen requires  >=0.1.7 <0.3.0

The problem is hidden behind the 4th dependency level - cryptoutils. Cryptoutils is not maintained anymore. It took me several hours to figure out the where the problem was...

Plus!!! + the problem is dart_style. dart_style has nothing to do with the package-functionality. It's code_builder who is responsible for the problem. It's dependency-list includes dart_style! ( https://github.com/dart-lang/code_builder/blob/master/pubspec.yaml / https://github.com/dart-lang/code_builder/issues/180 )

OMG - That's what I call Dependency hell

[matanlurey]

FWIW I'm removing that dependency for similar reasons :)

https://github.com/dart-lang/code_builder/pull/182

[munificent]

It makes sense for code_builder to depend on dart_style. Packages that generate code shouldn't have to worry about formatting it. That's exactly why dart_style exists.

It also makes sense for dart_style to depend on analyzer, which is where the actual version pain is coming from here. A formatter shouldn't need to write its own parser.

The problem is that the analyzer package is much more than just a parser. It's a full static analysis front end. Also, it's very heavily used by many of our tools, and has had a very quickly-changing public API for quite some time. That leads it to being depended on by a number of packages, and also with narrow version constraints. That's, unfortunately, a recipe for version lock. :(

@nex3's new version solver may help. With the transition to 2.0, we may also end up moving dart_style off analyzer and onto a new, more stable parsing package. That may also help.

Code reuse is hard. There's no silver bullet.

[jimmyff]

I'm getting the following error:

Package sass_builder has no versions that match >=1.0.1 <2.0.0 derived from:
- angular_components 0.8.0 depends on version ^1.0.1
- app_angular depends on version ^1.0.1

Both packages have the same dependancy version so not sure why I'm getting this error?

[bkonyi]

I think a user of DRAW ran into a similar issue (let me know if this isn't the right issue for this).

Here's the error output from flutter package get:

Package draw has no versions that match 0.0.3 derived from:
- draw_check depends on version 0.0.3

For reference, here's the sample pubspec:

name: draw_check                                                                                                                                                                                                                              
description: A new Flutter project.                                                                                                                                                                                                           

dependencies:                                                                                                                                                                                                                                 
  flutter:                                                                                                                                                                                                                                    
    sdk: flutter                                                                                                                                                                                                                              

  # The following adds the Cupertino Icons font to your application.                                                                                                                                                                          
  # Use with the CupertinoIcons class for iOS style icons.                                                                                                                                                                                    
  cupertino_icons: ^0.1.0                                                                                                                                                                                                                     
  draw: 0.0.3                                                                                                                                                                                                                                 

dev_dependencies:                                                                                                                                                                                                                             
  flutter_test:                                                                                                                                                                                                                               
    sdk: flutter       

draw 0.0.3 does exist but has conflicting constraints for quiver (flutter_test requires 0.28.0, draw 0.0.3 requires an earlier version). I talked to @cbracken and he mentioned that these conflicting constraints are probably what's causing this failure, but we should probably give a better error message in this case.