Use backtracking when solving dependency constraints.

utils/pub/version_solver.dart

Index: utils/pub/version_solver.dart
diff --git a/utils/pub/version_solver.dart b/utils/pub/version_solver.dart
index 5b055d87e86b92871a42ebfbe91de1249bec52c1..6534d6c4a589072eee92d28b32c05be2470a84e7 100644
--- a/utils/pub/version_solver.dart
+++ b/utils/pub/version_solver.dart
@@ -2,37 +2,6 @@
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
-/// Attempts to resolve a set of version constraints for a package dependency
-/// graph and select an appropriate set of best specific versions for all
-/// dependent packages. It works iteratively and tries to reach a stable
-/// solution where the constraints of all dependencies are met. If it fails to
-/// reach a solution after a certain number of iterations, it assumes the
-/// dependency graph is unstable and reports and error.
-///
-/// There are two fundamental operations in the process of iterating over the
-/// graph:
-///
-/// 1.  Changing the selected concrete version of some package. (This includes
-///     adding and removing a package too, which is considering changing the
-///     version to or from "none".) In other words, a node has changed.
-/// 2.  Changing the version constraint that one package places on another. In
-///     other words, and edge has changed.
-///
-/// Both of these events have a corresponding (potentional) async operation and
-/// roughly cycle back and forth between each other. When we change the version
-/// of package changes, we asynchronously load the pubspec for the new version.
-/// When that's done, we compare the dependencies of the new version versus the
-/// old one. For everything that differs, we change those constraints between
-/// this package and that dependency.
-///
-/// When a constraint on a package changes, we re-calculate the overall
-/// constraint on that package. I.e. with a shared dependency, we intersect all
-/// of the constraints that its depending packages place on it. If that overall
-/// constraint changes (say from "<3.0.0" to "<2.5.0"), then the currently
-/// picked version for that package may fall outside of the new constraint. If
-/// that happens, we find the new best version that meets the updated constraint
-/// and then the change the package to use that version. That cycles back up to
-/// the beginning again.
 library version_solver;
 
 import 'dart:async';
@@ -47,6 +16,8 @@ import 'source.dart';
 import 'source_registry.dart';
 import 'utils.dart';
 import 'version.dart';
+import 'version_solver1.dart' as v1;
+import 'version_solver2.dart' as v2;

[nweiz, 2013/03/29 01:58:25]

Name these after the type of version solver they contain. Also probably make a
subdirectory for all the version_solver-related files.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

 
 /// Attempts to select the best concrete versions for all of the transitive
 /// dependencies of [root] taking into account all of the [VersionConstraint]s
@@ -56,415 +27,105 @@ import 'version.dart';
 /// with a [NoVersionException], [DisjointConstraintException], or
 /// [CouldNotSolveException].

[nweiz, 2013/03/29 01:58:25]

Document the new arguments.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

 Future<List<PackageId>> resolveVersions(SourceRegistry sources, Package root,
-    LockFile lockFile) {
+    {int solver, LockFile lockFile, List<PackageRef> useLatest}) {

[nweiz, 2013/03/29 01:58:25]

Make solver an enum.

[Bob Nystrom, 2013/03/30 00:15:55]

Changed to a bool.

   log.message('Resolving dependencies...');
-  return new VersionSolver(sources, root, lockFile).solve();
-}
-
-class VersionSolver {
-  final SourceRegistry _sources;
-  final Package _root;
-  final LockFile lockFile;
-  final PubspecCache _pubspecs;
-  final Map<String, Dependency> _packages;
-  final Queue<WorkItem> _work;
-  int _numIterations = 0;
-
-  VersionSolver(SourceRegistry sources, this._root, this.lockFile)
-      : _sources = sources,
-        _pubspecs = new PubspecCache(sources),
-        _packages = <String, Dependency>{},
-        _work = new Queue<WorkItem>();
-
-  /// Tell the version solver to use the most recent version of [package] that
-  /// exists in whatever source it's installed from. If that version violates
-  /// constraints imposed by other dependencies, an error will be raised when
-  /// solving the versions, even if an earlier compatible version exists.
-  void useLatestVersion(String package) {
-    // TODO(nweiz): How do we want to detect and handle unknown dependencies
-    // here?
-    getDependency(package).useLatestVersion = true;
-    lockFile.packages.remove(package);
-  }
-
-  Future<List<PackageId>> solve() {
-    // Kick off the work by adding the root package at its concrete version to
-    // the dependency graph.
-    var ref = new PackageRef.root(_root);
-    enqueue(new AddConstraint('(entrypoint)', ref));
-    _pubspecs.cache(ref.atVersion(_root.version), _root.pubspec);
-
-    Future processNextWorkItem(_) {
-      while (true) {
-        // Stop if we are done.
-        if (_work.isEmpty) return new Future.immediate(buildResults());
-
-        // If we appear to be stuck in a loop, then we probably have an unstable
-        // graph, bail. We guess this based on a rough heuristic that it should
-        // only take a certain number of steps to solve a graph with a given
-        // number of connections.
-        // TODO(rnystrom): These numbers here are magic and arbitrary. Tune
-        // when we have a better picture of real-world package topologies.
-        _numIterations++;
-        if (_numIterations > max(50, _packages.length * 5)) {
-          throw new CouldNotSolveException();
-        }
-
-        // Run the first work item.
-        var future = _work.removeFirst().process(this);
-
-        // If we have an async operation to perform, chain the loop to resume
-        // when it's done. Otherwise, just loop synchronously.
-        if (future != null) {
-          return future.then(processNextWorkItem);
-        }
-      }
-    }
-
-    return processNextWorkItem(null);
-  }
-
-  void enqueue(WorkItem work) {
-    _work.add(work);
-  }
-
-  Dependency getDependency(String package) {
-    // There can be unused dependencies in the graph, so just create an empty
-    // one if needed.
-    _packages.putIfAbsent(package, () => new Dependency(package));
-    return _packages[package];
-  }
-
-  /// Sets the best selected version of [package] to [version].
-  void setVersion(String package, Version version) {
-    _packages[package].version = version;
-  }
-
-  /// Returns the most recent version of [dependency] that satisfies all of its
-  /// version constraints.
-  Future<Version> getBestVersion(Dependency dependency) {
-    return dependency.getVersions().then((versions) {
-      var best = null;
-      for (var version in versions) {
-        if (dependency.useLatestVersion ||
-            dependency.constraint.allows(version)) {
-          if (best == null || version > best) best = version;
-        }
-      }
-
-      // TODO(rnystrom): Better exception.
-      if (best == null) {
-        if (tryUnlockDepender(dependency)) return null;
-        throw new NoVersionException(dependency.name, dependency.constraint,
-            dependency._refs);
-      } else if (!dependency.constraint.allows(best)) {
-        if (tryUnlockDepender(dependency)) return null;
-        throw new CouldNotUpdateException(
-            dependency.name, dependency.constraint, best);
-      }
-
-      return best;
-    });
-  }
-
-  /// Looks for a package that depends (transitively) on [dependency] and has
-  /// its version locked in the lockfile. If one is found, enqueues an
-  /// [UnlockPackage] work item for it and returns true. Otherwise, returns
-  /// false.
-  ///
-  /// This does a breadth-first search; immediate dependers will be unlocked
-  /// first, followed by transitive dependers.
-  bool tryUnlockDepender(Dependency dependency, [Set<String> seen]) {
-    if (seen == null) seen = new Set();
-    // Avoid an infinite loop if there are circular dependencies.
-    if (seen.contains(dependency.name)) return false;
-    seen.add(dependency.name);
-
-    for (var dependerName in dependency.dependers) {
-      var depender = getDependency(dependerName);
-      var locked = lockFile.packages[dependerName];
-      if (locked != null && depender.version == locked.version &&
-          depender.source.name == locked.source.name) {
-        enqueue(new UnlockPackage(depender));
-        return true;
-      }
-    }
 
-    return dependency.dependers.map(getDependency).any((subdependency) =>
-        tryUnlockDepender(subdependency, seen));
+  if (solver == null) solver = 2;

[nweiz, 2013/03/29 01:58:25]

Let's make the existing solver the default for now.

[Bob Nystrom, 2013/03/30 00:15:55]

I'll do that if you'll let me submit this patch before implementing backjumping
and whatever other hoops you want me to jump through to convince you this won't
end the world. :)

[nweiz, 2013/04/03 00:28:43]

I'm willing to LGTM without the backjumper, on the understanding that I'm not
LGTMing the user-visible use of the backtracking solver.

[Bob Nystrom, 2013/04/08 22:12:59]

OK, I'll default to the old solver for now. We'll need to switch to the new one
to land SDK constraint solving, though, so I'll work on backjumping and some
tests that use it in a patch soon.

+  if (lockFile == null) lockFile = new LockFile.empty();
+  if (useLatest == null) useLatest = [];

[nweiz, 2013/03/29 01:58:25]

Is our style to just avoid using default values other than null?

[Bob Nystrom, 2013/03/30 00:15:55]

Yeah, I prefer to avoid them.

+
+  var versionSolver;
+  if (solver == 1) {
+    versionSolver = new v1.GreedyVersionSolver(
+        sources, root, lockFile, useLatest);
+  } else if (solver == 2) {
+    versionSolver = new v2.BacktrackingVersionSolver(
+        sources, root, lockFile, useLatest);
+  } else {
+    throw new ArgumentError("Argument 'solver' must be 1 or 2.");
   }
 
-  List<PackageId> buildResults() {
-    return _packages.values.where((dep) => dep.isDependedOn).map((dep) {
-      var description = dep.description;
-
-      // If the lockfile contains a fully-resolved description for the package,
-      // use that. This allows e.g. Git to ensure that the same commit is used.
-      var lockedPackage = lockFile.packages[dep.name];
-      if (lockedPackage != null && lockedPackage.version == dep.version &&
-          lockedPackage.source.name == dep.source.name &&
-          dep.source.descriptionsEqual(
-              description, lockedPackage.description)) {
-        description = lockedPackage.description;
-      }
-
-      return new PackageId(dep.name, dep.source, dep.version, description);
-    })
-    .toList();
-  }
+  return versionSolver.solve();
 }
 
-/// The constraint solver works by iteratively processing a queue of work items.
-/// Each item is a single atomic change to the dependency graph. Handling them
-/// in a queue lets us handle asynchrony (resolving versions requires
-/// information from servers) as well as avoid deeply nested recursion.
-abstract class WorkItem {
-  /// Processes this work item. Returns a future that completes when the work is
-  /// done. If `null` is returned, that means the work has completed
-  /// synchronously and the next item can be started immediately.
-  Future process(VersionSolver solver);
+time(String name, Future operation) {
+  var stopwatch = new Stopwatch()..start();
+  return operation.whenComplete(() {
+    log.message('$name took ${stopwatch.elapsed}');
+  });
 }

[nweiz, 2013/03/29 01:58:25]

Debugging function, remove it.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

 
-/// The best selected version for a package has changed to [version]. If the
-/// previous version of the package is `null`, that means the package is being
-/// added to the graph. If [version] is `null`, it is being removed.
-class ChangeVersion implements WorkItem {
-  /// The name of the package whose version is being changed.
-  final String package;
-
-  /// The source of the package whose version is changing.
-  final Source source;
-
-  /// The description identifying the package whose version is changing.
-  final description;
-
-  /// The new selected version.
-  final Version version;
-
-  ChangeVersion(this.package, this.source, this.description, this.version);
-
-  Future process(VersionSolver solver) {
-    log.fine("Changing $package to version $version.");
-
-    var dependency = solver.getDependency(package);
-    var oldVersion = dependency.version;
-    solver.setVersion(package, version);
-
-    // The dependencies between the old and new version may be different. Walk
-    // them both and update any constraints that differ between the two.
-    return Future.wait([
-        getDependencyRefs(solver, oldVersion),
-        getDependencyRefs(solver, version)]).then((list) {
-      var oldDependencyRefs = list[0];
-      var newDependencyRefs = list[1];
-
-      for (var oldRef in oldDependencyRefs.values) {
-        if (newDependencyRefs.containsKey(oldRef.name)) {
-          // The dependency is in both versions of this package, but its
-          // constraint may have changed.
-          var newRef = newDependencyRefs.remove(oldRef.name);
-          solver.enqueue(new AddConstraint(package, newRef));
-        } else {
-          // The dependency is not in the new version of the package, so just
-          // remove its constraint.
-          solver.enqueue(new RemoveConstraint(package, oldRef.name));
-        }
-      }
-
-      // Everything that's left is a depdendency that's only in the new
-      // version of the package.
-      for (var newRef in newDependencyRefs.values) {
-        solver.enqueue(new AddConstraint(package, newRef));
-      }
-    });
-  }
-
-  /// Get the dependencies at [version] of the package being changed.
-  Future<Map<String, PackageRef>> getDependencyRefs(VersionSolver solver,
-      Version version) {
-    // If there is no version, it means no package, so no dependencies.
-    if (version == null) {
-      return new Future<Map<String, PackageRef>>.immediate(
-          <String, PackageRef>{});
+/// Base class for an implementation of the version constraint solver.
+class VersionSolver {
+  final SourceRegistry sources;
+  final Package root;
+  final LockFile lockFile;
+  final PubspecCache cache;
+
+  VersionSolver(SourceRegistry sources, this.root, this.lockFile,
+                List<String> useLatest)
+      : sources = sources,
+        cache = new PubspecCache(sources) {
+    for (var package in useLatest) {
+      forceLatestVersion(package);
+      lockFile.packages.remove(package);
     }
-
-    var id = new PackageId(package, source, version, description);
-    return solver._pubspecs.load(id).then((pubspec) {
-      var dependencies = <String, PackageRef>{};
-      for (var dependency in pubspec.dependencies) {
-        dependencies[dependency.name] = dependency;
-      }
-
-      // Include dev dependencies only from the root package.
-      if (id.isRoot) {
-        for (var dependency in pubspec.devDependencies) {
-          dependencies[dependency.name] = dependency;
-        }
-      }
-
-      return dependencies;
-    });
   }
-}
-
-/// A constraint that a depending package places on a dependent package has
-/// changed.
-///
-/// This is an abstract class that contains logic for updating the dependency
-/// graph once a dependency has changed. Changing the dependency is the
-/// responsibility of subclasses.
-abstract class ChangeConstraint implements WorkItem {
-  Future process(VersionSolver solver);
-
-  void undo(VersionSolver solver);
-
-  Future _processChange(VersionSolver solver, Dependency oldDependency,
-      Dependency newDependency) {
-    var name = newDependency.name;
-    var source = oldDependency.source != null ?
-      oldDependency.source : newDependency.source;
-    var description = oldDependency.description != null ?
-      oldDependency.description : newDependency.description;
-    var oldConstraint = oldDependency.constraint;
-    var newConstraint = newDependency.constraint;
-
-    // If the package is over-constrained, i.e. the packages depending have
-    // disjoint constraints, then try unlocking a depender that's locked by the
-    // lockfile. If there are no remaining locked dependencies, throw an error.
-    if (newConstraint != null && newConstraint.isEmpty) {
-      if (solver.tryUnlockDepender(newDependency)) {
-        undo(solver);
-        return null;
-      }
-
-      throw new DisjointConstraintException(name, newDependency._refs);
-    }
 
-    // If this constraint change didn't cause the overall constraint on the
-    // package to change, then we don't need to do any further work.
-    if (oldConstraint == newConstraint) return null;
+  /// Force the solver to upgrade [package] to the latest available version.
+  void forceLatestVersion(String package);
 
-    // If the dependency has been cut free from the graph, just remove it.
-    if (!newDependency.isDependedOn) {
-      solver.enqueue(new ChangeVersion(name, source, description, null));
-      return null;
-    }
-
-    // If the dependency is on the root package, then we don't need to do
-    // anything since it's already at the best version.
-    if (name == solver._root.name) {
-      solver.enqueue(new ChangeVersion(
-          name, source, description, solver._root.version));
-      return null;
-    }
-
-    // If the dependency is on a package in the lockfile, use the lockfile's
-    // version for that package if it's valid given the other constraints.
-    var lockedPackage = solver.lockFile.packages[name];
-    if (lockedPackage != null && newDependency.source == lockedPackage.source) {
-      var lockedVersion = lockedPackage.version;
-      if (newConstraint.allows(lockedVersion)) {
-        solver.enqueue(
-            new ChangeVersion(name, source, description, lockedVersion));
-        return null;
-      }
-    }
-
-    // The constraint has changed, so see what the best version of the package
-    // that meets the new constraint is.
-    return solver.getBestVersion(newDependency).then((best) {
-      if (best == null) {
-        undo(solver);
-      } else if (newDependency.version != best) {
-        solver.enqueue(new ChangeVersion(name, source, description, best));
-      }
+  /// Run the solver. Completes with a list of specific package versions if
+  /// successful or an error if it failed to find a solution.
+  Future<List<PackageId>> solve() {
+    var stopwatch = new Stopwatch();
+    stopwatch.start();
+
+    // Gather some solving metrics.
+    return runSolver().whenComplete(() {
+      var buffer = new StringBuffer();
+      buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.');
+      buffer.writeln(
+          '- Requested ${cache.versionCacheMisses} version lists');
+      buffer.writeln(
+          '- Looked up ${cache.versionCacheHits} cached version lists');
+      buffer.writeln(
+          '- Requested ${cache.pubspecCacheMisses} pubspecs');
+      buffer.writeln(
+          '- Looked up ${cache.pubspecCacheHits} cached pubspecs');
+      log.solver(buffer);
     });
   }
-}
-
-/// The constraint given by [ref] is being placed by [depender].
-class AddConstraint extends ChangeConstraint {
-  /// The package that has the dependency.
-  final String depender;
-
-  /// The package being depended on and the constraints being placed on it. The
-  /// source, version, and description in this ref are all considered
-  /// constraints on the dependent package.
-  final PackageRef ref;
-
-  AddConstraint(this.depender, this.ref);
-
-  Future process(VersionSolver solver) {
-    log.fine("Adding $depender's constraint $ref.");
-
-    var dependency = solver.getDependency(ref.name);
-    var oldDependency = dependency.clone();
-    dependency.placeConstraint(depender, ref);
-    return _processChange(solver, oldDependency, dependency);
-  }
-
-  void undo(VersionSolver solver) {
-    solver.getDependency(ref.name).removeConstraint(depender);
-  }
-}
-
-/// [depender] is no longer placing a constraint on [dependent].
-class RemoveConstraint extends ChangeConstraint {
-  /// The package that was placing a constraint on [dependent].
-  String depender;
-
-  /// The package that was being depended on.
-  String dependent;
-
-  /// The constraint that was removed.
-  PackageRef _removed;
-
-  RemoveConstraint(this.depender, this.dependent);
-
-  Future process(VersionSolver solver) {
-    log.fine("Removing $depender's constraint ($_removed) on $dependent.");
-
-    var dependency = solver.getDependency(dependent);
-    var oldDependency = dependency.clone();
-    _removed = dependency.removeConstraint(depender);
-    return _processChange(solver, oldDependency, dependency);
-  }
 
-  void undo(VersionSolver solver) {
-    solver.getDependency(dependent).placeConstraint(depender, _removed);
-  }
+  /// Entrypoint for subclasses to actually begin solving. External code should
+  /// call [solve()].
+  Future<List<PackageId>> runSolver();
 }
 
-/// [package]'s version is no longer constrained by the lockfile.
-class UnlockPackage implements WorkItem {
-  /// The package being unlocked.
-  Dependency package;
+/// Maintains a cache of previously-requested data: pubspecs and version lists.
+/// Used to avoid requesting the same pubspec from the server repeatedly.
+class PubspecCache {
+  final SourceRegistry _sources;
+  final _versions = new Map<PackageId, List<Version>>();
+  final _pubspecs = new Map<PackageId, Pubspec>();
 
-  UnlockPackage(this.package);
+  /// The number of times a version list was requested and it wasn't cached and
+  /// had to be requested from the source.
+  int versionCacheMisses = 0;
 
-  Future process(VersionSolver solver) {
-    log.fine("Unlocking ${package.name}.");
+  /// The number of times a version list was requested and the cached version
+  /// was returned.
+  int versionCacheHits = 0;
 
-    solver.lockFile.packages.remove(package.name);
-    return solver.getBestVersion(package).then((best) {
-      if (best == null) return null;
-      solver.enqueue(new ChangeVersion(
-          package.name, package.source, package.description, best));
-    });
-  }
-}
+  /// The number of times a pubspec was requested and it wasn't cached and had
+  /// to be requested from the source.
+  int pubspecCacheMisses = 0;
 
-// TODO(rnystrom): Instead of always pulling from the source (which will mean
-// hitting a server), we should consider caching pubspecs of uninstalled
-// packages in the system cache.
-/// Maintains a cache of previously-loaded pubspecs. Used to avoid requesting
-/// the same pubspec from the server repeatedly.
-class PubspecCache {
-  final SourceRegistry _sources;
-  final Map<PackageId, Pubspec> _pubspecs;
+  /// The number of times a pubspec was requested and the cached version was
+  /// returned.
+  int pubspecCacheHits = 0;
 
-  PubspecCache(this._sources)
-      : _pubspecs = new Map<PackageId, Pubspec>();
+  PubspecCache(this._sources);
 
   /// Caches [pubspec] as the [Pubspec] for the package identified by [id].
   void cache(PackageId id, Pubspec pubspec) {
@@ -472,139 +133,96 @@ class PubspecCache {
   }
 
   /// Loads the pubspec for the package identified by [id].
-  Future<Pubspec> load(PackageId id) {
+  Future<Pubspec> getPubspec(PackageId id) {
     // Complete immediately if it's already cached.
     if (_pubspecs.containsKey(id)) {
+      pubspecCacheHits++;
       return new Future<Pubspec>.immediate(_pubspecs[id]);
     }
 
+    pubspecCacheMisses++;
     return id.describe().then((pubspec) {
+      log.solver('requested ${id} pubspec');

[nweiz, 2013/03/29 01:58:25]

"${id}" => "$id"

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+
       // Cache it.
       _pubspecs[id] = pubspec;
       return pubspec;
     });
   }
-}
 
-/// Describes one [Package] in the [DependencyGraph] and keeps track of which
-/// packages depend on it and what constraints they place on it.
-class Dependency {
-  /// The name of the this dependency's package.
-  final String name;
-
-  /// The [PackageRefs] that represent constraints that depending packages have
-  /// placed on this one.
-  final Map<String, PackageRef> _refs;
-
-  /// The currently-selected best version for this dependency.
-  Version version;
-
-  /// Whether this dependency should always select the latest version.
-  bool useLatestVersion = false;
-
-  /// Gets whether or not any other packages are currently depending on this
-  /// one. If `false`, then it means this package is not part of the dependency
-  /// graph and should be omitted.
-  bool get isDependedOn => !_refs.isEmpty;
-
-  /// The names of all the packages that depend on this dependency.
-  Iterable<String> get dependers => _refs.keys;
-
-  /// Gets the overall constraint that all packages are placing on this one.
-  /// If no packages have a constraint on this one (which can happen when this
-  /// package is in the process of being added to the graph), returns `null`.
-  VersionConstraint get constraint {
-    if (_refs.isEmpty) return null;
-    return new VersionConstraint.intersection(
-        _refs.values.map((ref) => ref.constraint));
-  }
+  /// Gets the list of versions for [package] in descending order.
+  Future<List<PackageId>> getVersions(String package, Source source, description) {
+    // Create a fake ID to use as a key.
+    var id = new PackageId(package, source, Version.none, description);
 
-  /// The source of this dependency's package.
-  Source get source {
-     var canonical = _canonicalRef();
-     if (canonical == null) return null;
-     return canonical.source;
-  }
+    // See if we have it cached.
+    var versions = _versions[id];
+    if (versions != null) {
+      versionCacheHits++;
+      return new Future.immediate(versions);
+    }
 
-  /// The description of this dependency's package.
-  get description {
-     var canonical = _canonicalRef();
-     if (canonical == null) return null;
-     return canonical.description;
-  }
+    versionCacheMisses++;
+    return source.getVersions(package, description).then((versions) {
+      var ids = versions
+          .map((version) => new PackageId(package, source, version, description))
+          .toList();
 
-  /// Return the PackageRef that has the canonical source and description for
-  /// this package. If any dependency is on the root package, that will be used;
-  /// otherwise, it will be the source and description that all dependencies
-  /// agree upon.
-  PackageRef _canonicalRef() {
-    if (_refs.isEmpty) return null;
-    var refs = _refs.values;
-    for (var ref in refs) {
-      if (ref.isRoot) return ref;
-    }
-    return refs.first;
+      // Sort by descending version so we try newer versions first.
+      ids.sort((a, b) => b.version.compareTo(a.version));
+
+      log.solver('requested $package version list');
+      _versions[id] = ids;
+      return ids;
+    });
   }
+}
 
-  Dependency(this.name)
-      : _refs = <String, PackageRef>{};
-
-  Dependency._clone(Dependency other)
-      : name = other.name,
-        version = other.version,
-        _refs = new Map<String, PackageRef>.from(other._refs);
-
-  /// Creates a copy of this dependency.
-  Dependency clone() => new Dependency._clone(this);
-
-  /// Return a list of available versions for this dependency.
-  Future<List<Version>> getVersions() => source.getVersions(name, description);
-
-  /// Places [ref] as a constraint from [package] onto this.
-  void placeConstraint(String package, PackageRef ref) {
-    var requiredDepender = _requiredDepender();
-    if (requiredDepender != null) {
-      var required = _refs[requiredDepender];
-      if (required.source.name != ref.source.name) {
-        throw new SourceMismatchException(name,
-            requiredDepender, required.source, package, ref.source);
-      } else if (!required.source.descriptionsEqual(
-                     required.description, ref.description)) {
-        throw new DescriptionMismatchException(name,
-            requiredDepender, required.description, package, ref.description);
-      }
-    }
+/// A reference from a depending package to a package that it depends on.
+class Dependency {
+  /// The name of the package that has this dependency.
+  final String depender;
 
-    _refs[package] = ref;
-  }
+  /// The referenced dependent package.
+  final PackageRef ref;
+
+  Dependency(this.depender, this.ref);
+}
 
-  /// Returns the name of a package whose constraint source and description
-  /// all other constraints must match. Returns null if there are no
-  /// requirements on new constraints.
-  String _requiredDepender() {
-    if (_refs.isEmpty) return null;
-
-    var dependers = _refs.keys.toList();
-    if (dependers.length == 1) {
-      var depender = dependers[0];
-      if (_refs[depender].isRoot) return null;
-      return depender;
+/// Base class for all failures that can occur while trying to resolve versions.
+class SolverFailure implements Exception {
+  /// Writes [deps] to [buffer] as a bullet list.
+  void _writeDependencies(StringBuffer buffer, List<Dependency> deps) {
+    var map = {};
+    for (var dep in deps) {
+      map[dep.depender] = dep.ref;
     }
 
-    return dependers[1];
+    var names = map.keys.toList();
+    names.sort();
+
+    for (var name in names) {
+      buffer.writeln("- '$name' depends on version ${map[name].constraint}");
+    }
   }
+}
+
+/// Exception thrown when the [VersionSolver] fails to find a solution after a
+/// certain number of iterations.
+class CouldNotSolveException extends SolverFailure {
+  CouldNotSolveException();
 
-  /// Removes the constraint from [package] onto this.
-  PackageRef removeConstraint(String package) => _refs.remove(package);
+  String toString() =>
+      "Could not find a solution that met all version constraints.";
 }
 
 /// Exception thrown when the [VersionConstraint] used to match a package is
-/// valid (i.e. non-empty), but there are no released versions of the package
+/// valid (i.e. non-empty), but there are no available versions of the package
 /// that fit that constraint.
-class NoVersionException implements Exception {
+class NoVersionException extends SolverFailure {
   final String package;
   final VersionConstraint constraint;
-  final Map<String, PackageRef> _dependencies;
+  final List<Dependency> _dependencies;
 
   NoVersionException(this.package, this.constraint, this._dependencies);
 
@@ -612,15 +230,7 @@ class NoVersionException implements Exception {
     var buffer = new StringBuffer();
     buffer.write("Package '$package' has no versions that match $constraint "
         "derived from:\n");
-
-    var keys = new List.from(_dependencies.keys);
-    keys.sort();
-
-    for (var key in keys) {
-      buffer.write("- '$key' depends on version "
-          "${_dependencies[key].constraint}\n");
-    }
-
+    _writeDependencies(buffer, _dependencies);
     return buffer.toString();
   }
 }
@@ -628,7 +238,7 @@ class NoVersionException implements Exception {
 // TODO(rnystrom): Report the list of depending packages and their constraints.
 /// Exception thrown when the most recent version of [package] must be selected,
 /// but doesn't match the [VersionConstraint] imposed on the package.
-class CouldNotUpdateException implements Exception {
+class CouldNotUpdateException extends SolverFailure {
   final String package;
   final VersionConstraint constraint;
   final Version best;
@@ -642,40 +252,23 @@ class CouldNotUpdateException implements Exception {
 /// Exception thrown when the [VersionConstraint] used to match a package is
 /// the empty set: in other words, multiple packages depend on it and have
 /// conflicting constraints that have no overlap.
-class DisjointConstraintException implements Exception {
+class DisjointConstraintException extends SolverFailure {
   final String package;
-  final Map<String, PackageRef> _dependencies;
+  final List<Dependency> _dependencies;
 
   DisjointConstraintException(this.package, this._dependencies);
 
   String toString() {
     var buffer = new StringBuffer();
     buffer.write("Incompatible version constraints on '$package':\n");
-
-    var keys = new List.from(_dependencies.keys);
-    keys.sort();
-
-    for (var key in keys) {
-      buffer.write("- '$key' depends on version "
-          "${_dependencies[key].constraint}\n");
-    }
-
+    _writeDependencies(buffer, _dependencies);
     return buffer.toString();
   }
 }
 
-/// Exception thrown when the [VersionSolver] fails to find a solution after a
-/// certain number of iterations.
-class CouldNotSolveException implements Exception {
-  CouldNotSolveException();
-
-  String toString() =>
-      "Could not find a solution that met all version constraints.";
-}
-
 /// Exception thrown when two packages with the same name but different sources
 /// are depended upon.
-class SourceMismatchException implements Exception {
+class SourceMismatchException extends SolverFailure {
   final String package;
   final String depender1;
   final Source source1;
@@ -694,7 +287,7 @@ class SourceMismatchException implements Exception {
 
 /// Exception thrown when two packages with the same name and source but
 /// different descriptions are depended upon.
-class DescriptionMismatchException implements Exception {
+class DescriptionMismatchException extends SolverFailure {
   final String package;
   final String depender1;
   final description1;