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.

---

<img src="https://avatars.githubusercontent.com/u/4833191?v=3" align="left" width="96" height="96"hspace="10"> Issue by tomaskulich
Originally opened as dart-lang/sdk#17429

---

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

[DartBot]

<img src="https://avatars.githubusercontent.com/u/4833191?v=3" align="left" width="48" height="48"hspace="10"> Comment by tomaskulich

---

Attachment:
pubtrace.zip (179.34 KB)

[DartBot]

<img src="https://avatars.githubusercontent.com/u/4833191?v=3" align="left" width="48" height="48"hspace="10"> 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]

<img src="https://avatars.githubusercontent.com/u/46275?v=3" align="left" width="48" height="48"hspace="10"> 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]

<img src="https://avatars.githubusercontent.com/u/4833191?v=3" align="left" width="48" height="48"hspace="10"> Comment by tomaskulich

---

Attachment:
pubspec.yaml (578 Bytes)

[DartBot]

<img src="https://avatars.githubusercontent.com/u/4833191?v=3" align="left" width="48" height="48"hspace="10"> 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]

<img src="https://avatars.githubusercontent.com/u/4865287?v=3" align="left" width="48" height="48"hspace="10"> Comment by lrhn

---

Added Area-Pub label.

[DartBot]

<img src="https://avatars.githubusercontent.com/u/188?v=3" align="left" width="48" height="48"hspace="10"> 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]

<img src="https://avatars.githubusercontent.com/u/188?v=3" align="left" width="48" height="48"hspace="10"> Comment by nex3

---

Issue #971 has been merged into this issue.

---

cc @keertip.

[DartBot]

<img src="https://avatars.githubusercontent.com/u/46275?v=3" align="left" width="48" height="48"hspace="10"> Comment by munificent

---

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

[DartBot]

<img src="https://avatars.githubusercontent.com/u/188?v=3" align="left" width="48" height="48"hspace="10"> Comment by nex3

---

Issue #1159 has been merged into this issue.

[DartBot]

<img src="https://avatars.githubusercontent.com/u/188?v=3" align="left" width="48" height="48"hspace="10"> Comment by nex3

---

Issue #1170 has been merged into this issue.

---

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

[DartBot]

<img src="https://avatars.githubusercontent.com/u/3476088?v=3" align="left" width="48" height="48"hspace="10"> 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....