Merge branch 'release-0.9.0' into devel
Revert "bad merge diffs"

This reverts commit 7946be9f9b75fa43e700f519cb0caa07a352aac9.
Revert "one weird hack to maybe have better messages for nonexistent packages"

This reverts commit 75df1097e06dc7faed95e3f83d357ff3de63872f.
track ancestry as chain, not just root

switch constraintAncestor to be a nested mori.hash_map/mori.list
Also use mori for choices

Now there's no _.clone in resolver.js!
A more specific error for nonexistent package

This helps with #2410 though that particular case doesn't work since
paths are explored in a bad order.
Prefer to explore local packages first

(Or other packages where there is literally one version in existence.)
Merge branch 'constraint-solver-errors-ancestor' into release-0.9.0

Improves the #2410 fix to (at least for the particular case) be a little
less hacky: it's now OK if bad packages exist somewhere in the graph as
long as there's a way to avoid them.
Refactor ConstraintSolver.Resolver

Factor out the "state" into its own class, ResolverState.  The big
difference from the previous state object: it actually explicitly tracks
the set of potential UnitVersions for every active dependency.  This
essentially replaces the DependencyList class.

Because we always know exactly how many options there are for a given
dependency, we can both generalize and simplify the "propagate
transitive exact deps" optimization.  That optimization only worked on
"foo@=1.2.3" dependencies, which meant it didn't apply in any other
situation where there was only one possible package to choose. But there
are a whole lot of other situations like that: local packages, packages
that just don't have many versions, packages that already have a lot of
constraints applied to them, etc.  By tracking the set of potential
alternatives, we can just make sure to always expand 1-alternative units
first. We also maintain the aspect of the optimization where we don't
need to call the cost function until we've actually gotten to a state
with multiple neighbors.

This keeps #2410 fixed as well.

I've removed the constraintAncestor support as part of this refactoring,
so some error messages may be worse than they were before. But this
should set me up pretty well to improve error messages tomorrow.
Merge branch 'release-0.9.0' into devel
Simplify "make trivial easy choices immediately"

Instead of having two different spots where we do special checks to see
if a piece of the state might have only one alternative, we just ensure
that the ResolverState itself always eagerly converts one-alternative
dependencies into choices.
Keep alternatives sorted

Instead of recalculating the "edge versions", just keep the list of
alternatives for each dep sorted and look at the first and last.

Provides another 25% speedup to the benchmark, deletes a lot of
code, *AND* removes the one part of the constraint solver that tries to
have a deep understanding of the different constraint types other than
the "is this constraint satisfied" function (ie, makes it easier to add
more constraint types later).
show stack if error is unexpected
delete unused methods
delete unused field
Simplify ConstraintsList data structure

It now no longer has N nested 2-element hashmaps; the 2-element split
happens at the top level in the JS object.  And a nested hash_map is now
just a set (it's great that we can rely on the interned-ness of
constraints!)

8% benchmark speedup and less code.
Cache minimal constraint versions
Avoid passing empty options, and defend against it if we do
Avoid passing empty options, and defend against it if we do
Merge branch 'release-0.9.0' into devel