Pub's new version solver is live!

[Natalie Weizenbaum]

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 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, loosely based on a real-world solver failure, 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! If you're interested in the details of how it works, you can also check out my blog post about it, or if you're very brave the in-depth algorithm documentation.

- Natalie