[dart-misc] Pub's new version solver is live!

['Natalie Weizenbaum' via Dart Misc]

Hey folks,

I've got some exciting news: as of Dart 2.0.0-dev.44.0, pub's old version
solver has been replaced by an entirely new implementation that uses
cutting-edge techniques for solving NP-hard search problems to be faster,
less likely to go exponential, and way better at reporting errors.

What does this look like for you? For starters, you'll be vastly less
likely to run into situations where the solver churns for ages on a package
graph without either finding a solution or producing an error. The old
solver never actually entered an infinite loop, but it could loop
for enough time that it might as well have been infinite. These situations
may still happen—version solving is a problem so difficult it's a major
open question <https://en.wikipedia.org/wiki/P_versus_NP_problem> whether
it's even *possible* to solve efficiently in all cases—but package graphs
have to be *much much* more gnarly to trip up the new solver.

It also means that when pub does determine that there's no solution
possible for your pubspec, it will produce a way better error message. The
old solver tried to explain everything with a single error message, which
just didn't match the reality of why solving fails a lot of the time.
Sometimes the output wasn't even accurate. The new solver remembers all the
reasons that it couldn't find a solution, and explains those reasons in
plain English.

Here's an example
<https://gist.github.com/nex3/030c7738eb0d228cce62afdc55def822>, loosely
based on a real-world solver failure
<https://github.com/dart-lang/sdk/issues/18300>, for which the old version
solver produces this error:

Package analyzer has no versions that match >=0.13.0 <0.14.0 derived from:
- di 0.0.32 depends on version >=0.13.0 <0.14.0

This output is super unhelpful. Where did di come from? Why does my package
depend on it? Why does pub claim analyzer 0.13.0 doesn't exist when it
clearly does? How do I solve this issue? Let's compare that to the output
from the new solver:

Because every version of angular depends on di ^0.0.32 which depends
on analyzer ^0.13.0, *every version of angular requires analyzer*
* ^0.13.0*.
And because analyzer >=0.13.0 depends on args ^1.0.0, *every version of*
* angular requires args ^1.0.0*.
So, because myapp depends on both args ^0.13.0 and angular any,
*version solving failed*.

This output explains exactly what's going on: angular depends on di, di
depends on analyzer, and analyzer's version of args conflicts with my
package's. And now it's clear to me that the solution is to upgrade the
version of args that my app is using.

The new solver's output also provides a glimpse behind the curtains at what
makes the new solver so fast: it's able to figure out new facts—things like
"every version of angular requires args ^1.0.0"—that are likely to be
relevant and use those facts to avoid re-treading its steps.

This output scales with the complexity of the reasons behind the solve
failure. No matter how tangled the package graph is, pub will explain every
step of its reasoning about why a failure can't be found, allowing you to
understand what went wrong and how to fix it.

Give the new solver a try, and be sure to report any issues you find
<http://github.com/dart-lang/pub/issues/new>! If you're interested in the
details of how it works, you can also check out my blog post
<https://medium.com/@nex3/pubgrub-2fb6470504f> about it, or if you're very
brave the in-depth algorithm documentation
<https://github.com/dart-lang/pub/blob/master/doc/solver.md>.

- Natalie

[Günter Zöchbauer]

That was one of the main pain points when working with Dart, especially for
beginners and especially for Flutter devs where pub_mediator couldn't be
used.

This is a huge leap forward for Dart!
Great work

Post by 'Natalie Weizenbaum' via Dart Misc
Hey folks,
I've got some exciting news: as of Dart 2.0.0-dev.44.0, pub's old version
solver has been replaced by an entirely new implementation that uses
cutting-edge techniques for solving NP-hard search problems to be faster,
less likely to go exponential, and way better at reporting errors.
What does this look like for you? For starters, you'll be vastly less
likely to run into situations where the solver churns for ages on a package
graph without either finding a solution or producing an error. The old
solver never actually entered an infinite loop, but it could loop
for enough time that it might as well have been infinite. These situations
may still happen—version solving is a problem so difficult it's a major
open question <https://en.wikipedia.org/wiki/P_versus_NP_problem> whether
it's even *possible* to solve efficiently in all cases—but package graphs
have to be *much much* more gnarly to trip up the new solver.
It also means that when pub does determine that there's no solution
possible for your pubspec, it will produce a way better error message. The
old solver tried to explain everything with a single error message, which
just didn't match the reality of why solving fails a lot of the time.
Sometimes the output wasn't even accurate. The new solver remembers all the
reasons that it couldn't find a solution, and explains those reasons in
plain English.
Here's an example
<https://gist.github.com/nex3/030c7738eb0d228cce62afdc55def822>, loosely
based on a real-world solver failure
<https://github.com/dart-lang/sdk/issues/18300>, for which the old
- di 0.0.32 depends on version >=0.13.0 <0.14.0
This output is super unhelpful. Where did di come from? Why does my
package depend on it? Why does pub claim analyzer 0.13.0 doesn't exist
when it clearly does? How do I solve this issue? Let's compare that to the
Because every version of angular depends on di ^0.0.32 which depends
on analyzer ^0.13.0, *every version of angular requires analyzer*
* ^0.13.0*.
And because analyzer >=0.13.0 depends on args ^1.0.0, *every version of*
* angular requires args ^1.0.0*.
So, because myapp depends on both args ^0.13.0 and angular any,
*version solving failed*.
This output explains exactly what's going on: angular depends on di, di
depends on analyzer, and analyzer's version of args conflicts with my
package's. And now it's clear to me that the solution is to upgrade the
version of args that my app is using.
The new solver's output also provides a glimpse behind the curtains at
what makes the new solver so fast: it's able to figure out new facts—things
like "every version of angular requires args ^1.0.0"—that are likely to
be relevant and use those facts to avoid re-treading its steps.
This output scales with the complexity of the reasons behind the solve
failure. No matter how tangled the package graph is, pub will explain every
step of its reasoning about why a failure can't be found, allowing you to
understand what went wrong and how to fix it.
Give the new solver a try, and be sure to report any issues you find
<http://github.com/dart-lang/pub/issues/new>! If you're interested in the
details of how it works, you can also check out my blog post
very brave the in-depth algorithm documentation
<https://github.com/dart-lang/pub/blob/master/doc/solver.md>.
- Natalie