First pass at version constraint solver.

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
new file mode 100644
index 0000000000000000000000000000000000000000..3aec1e5c36e40709405e9ba86972afbeb86b209f
--- /dev/null
+++ b/utils/pub/version_solver.dart
@@ -0,0 +1,412 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// 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('package.dart');
+#import('pubspec.dart');
+#import('source.dart');
+#import('source_registry.dart');
+#import('utils.dart');
+#import('version.dart');
+
+Future<Map<String, Version>> resolveVersions(

[nweiz, 2012/06/18 18:29:19]

This could use some docs.

+    SourceRegistry sources, Package root) {
+  return new VersionSolver(sources).solve(root);
+}
+
+class VersionSolver {
+  final SourceRegistry _sources;
+  final PubspecCache _pubspecs;
+  final Map<String, Dependency> _packages;
+  final Queue<WorkItem> _work;
+  int _numIterations = 0;
+
+  VersionSolver(SourceRegistry sources)
+      : _sources = sources,
+        _pubspecs = new PubspecCache(sources),
+        _packages = <Dependency>{},
+        _work = new Queue<WorkItem>();
+
+  Future<Map<String, Version>> solve(Package root) {
+    // Kick off the work by adding the root package at its concrete version to
+    // the dependency graph.
+    _pubspecs.cache(root);
+    enqueue(new ChangeConstraint('(entrypoint)', root.name, root.version));

[nweiz, 2012/06/18 18:29:19]

What happens if some other package depends on the root package?

[Bob Nystrom, 2012/06/20 01:40:04]

There TODOs to add tests for that. Added tests. They pass!

If the constraint of the other dependency still allows the root's concrete
version, then it should pass, otherwise it's an overconstraint error.

+
+    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.

[nweiz, 2012/06/18 18:29:19]

Are we planning to try to manually catch infinite loops, with this as a backup?
Or will this be our sole method of loop-detection?

[Bob Nystrom, 2012/06/20 01:40:04]

Right now, it's the sole method. Catching loops will, I think, require keeping
track of previous states that the resolver has been in and that adds some
complexity. If you think it's worth doing, I'm open to the idea. For the first
pass, I just went with something simple.

[nweiz, 2012/06/20 21:08:48]

It seems like a nice thing to do once we run out of actual features to add.

+        _numIterations++;
+        if (_numIterations > Math.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.

[nweiz, 2012/06/18 18:29:19]

Wouldn't it be possible to process other work items while the asynchronous ones
are pending?

[Bob Nystrom, 2012/06/20 01:40:04]

In theory yes, but that adds a lot of complexity I wanted to try to avoid. You
can get in nasty situations like:

1. We get a constraint on foo >=1.0.0, so we ask the server for what versions of
foo it has.
2. Meanwhile, some other server response completes whose result is to remove the
dependency on foo (or just change its constraint).
3. The response from 1 comes in and we pick a version from a constraint that no
longer applies.

It is possible to make this work, but I'm not sure it's worth the extra
complexity. Do you think it is?

[nweiz, 2012/06/20 21:08:48]

Probably not... that could also (potentially) make the version resolution
process non-deterministic, which we don't want.

+        if (future != null) {
+          return future.chain(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());
+    return _packages[package];
+  }
+
+  /**
+   * Sets the best selected version of [package] to [version].
+   */
+  void setVersion(String package, Version version) {
+    _packages[package].version = version;
+  }
+
+  Map<String, Version> buildResults() {
+    var results = <Version>{};
+    _packages.forEach((name, dependency) {
+      if (dependency.isDependedOn) {
+        results[name] = dependency.version;
+      }
+    });
+
+    return results;
+  }
+}
+
+/**
+ * The constraint solver works by iteratively processing a queue work items.

[nweiz, 2012/06/18 18:29:19]

"a queue of work items"

[Bob Nystrom, 2012/06/20 01:40:04]

Done.

+ * 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 avoiding deeply nest recursion.

[nweiz, 2012/06/18 18:29:19]

"avoid deeply nested recursion"

[Bob Nystrom, 2012/06/20 01:40:04]

Done.

+*/
+interface 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);
+}
+
+/**
+ * The best selected version for [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 package whose version is changing.
+   */
+  final String package;
+
+  /**
+   * The new selected version.
+   */
+  final Version version;
+
+  ChangeVersion(this.package, this.version);
+
+  Future process(VersionSolver solver) {
+    var oldVersion = solver.getDependency(package).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 getDependencies(solver, oldVersion).chain((oldDependencies) {
+      return getDependencies(solver, version).transform((newDependencies) {

[nweiz, 2012/06/18 18:29:19]

You could increase parallelism and reduce nesting here by using
Futures.wait([getDependencies(solver, oldVersion), getDependencies(solver,
version)]).

[Bob Nystrom, 2012/06/20 01:40:04]

I think I had that at one point but it felt like overkill for a list of two
items. If you prefer that, I could change it.

[nweiz, 2012/06/20 21:08:48]

I think it would be cleaner.

[Bob Nystrom, 2012/06/20 22:29:54]

Done.

+        for (var dependency in oldDependencies.getValues()) {
+          var constraint;
+          if (newDependencies.containsKey(dependency.name)) {
+            // The dependency is in both versions of this package, but its
+            // constraint may have changed.
+            constraint = newDependencies[dependency.name].version;

[nweiz, 2012/06/18 18:29:19]

constraint = newDependencies.remove(dependency.name).version;

[Bob Nystrom, 2012/06/20 01:40:04]

Done.

+            newDependencies.remove(dependency.name);
+          } else {
+            // The dependency is not in the new version of the package, so just
+            // remove its constraint.
+            constraint = null;
+          }
+
+          solver.enqueue(new ChangeConstraint(
+              package, dependency.name, constraint));
+        }
+
+        // Everything that's left is a depdendency that's only in the new
+        // version of the package.
+        for (var dependency in newDependencies.getValues()) {
+          solver.enqueue(new ChangeConstraint(
+              package, dependency.name, dependency.version));
+        }
+      });
+    });
+  }
+
+  /**
+   * Get the dependencies that [package] has at [version].
+   */
+  Future<Map<String, PackageRef>> getDependencies(VersionSolver solver,

[nweiz, 2012/06/18 18:29:19]

This name is confusing, since the method doesn't have anything to do with
Dependency objects. Maybe getDependencyRefs?

[Bob Nystrom, 2012/06/20 01:40:04]

Done. What I wouldn't give for a shorter synonym for "dependency".

[nweiz, 2012/06/20 21:08:48]

You could always use "dep".

[Bob Nystrom, 2012/06/20 22:29:54]

For some reason, that bugs me. Maybe I just don't like abbreviations.

[nweiz, 2012/06/20 23:47:45]

You used "ref" ;).

I don't actually care either way; I like "dependency" just fine.

+      Version version) {
+    // If there is no version, it means no package, so no dependencies.
+    if (version == null) {
+      return new Future<Map<String, PackageRef>>.immediate(<PackageRef>{});
+    }
+
+    return solver._pubspecs.load(package, version).transform((pubspec) {
+      var dependencies = <PackageRef>{};
+      for (var dependency in pubspec.dependencies) {
+        dependencies[dependency.name] = dependency;
+      }
+      return dependencies;
+    });
+  }
+}
+
+/**
+ * The [VersionConstraint] that [package] places on depdendency [dependent] has
+ * changed from [from] to [to]. The [from] constraint may be `null` which means
+ * this is the first time [package] has depended on [dependent]. The [to]
+ * constraint may be `null` which means [package] no longer depends on
+ * [dependent].

[nweiz, 2012/06/18 18:29:19]

This is inaccurate. "[package]" and "[dependent]" don't refer to anything, and
"[from]" and "[to]" are package names rather than constraints.

[Bob Nystrom, 2012/06/20 01:40:04]

Stale comment is stale. This went through a few iterations. Fixed.

+ */
+class ChangeConstraint implements WorkItem {
+  /**
+   * The package that has the dependency.
+   */
+  final String from;
+
+  /**
+   * The package being depended on.
+   */
+  final String to;

[nweiz, 2012/06/18 18:29:19]

I'm finding "from" and "to" confusing when reading the code in #process. Maybe
"depender" and "dependee"?

[Bob Nystrom, 2012/06/20 01:40:04]

Changed to "depender" (which kind of sounds like suspenders for old people
diapers to me) and "dependent".

+
+  /**
+   * The constraint that [from] places on [to]'s version.
+   */
+  final VersionConstraint version;

[nweiz, 2012/06/18 18:29:19]

I'd call this "constraint", since it's a VersionConstraint and not always a
Version. I might also change the "version" field in PackageRef to "constraint"
as well. Trying to figure out what was a Version and what was a
VersionConstraint tripped me up while reading this code.

[Bob Nystrom, 2012/06/20 01:40:04]

Done.

+
+  ChangeConstraint(this.from, this.to, this.version);
+
+  Future process(VersionSolver solver) {
+    var dependency = solver.getDependency(to);
+    var oldConstraint = dependency.constraint;
+    dependency.setConstraint(from, version);
+    var newConstraint = dependency.constraint;
+
+    // If we the package is over-constrained, i.e. the packages depending

[nweiz, 2012/06/18 18:29:19]

"If the package is"

[Bob Nystrom, 2012/06/20 01:40:04]

Done.

+    // have disjoint constraints, then stop.
+    if (newConstraint != null && newConstraint.isEmpty) {
+      throw new DisjointConstraintException(to);
+    }
+
+    // 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;
+
+    // If the dependency has been cut free from the graph, just remove it.
+    if (!dependency.isDependedOn) {
+      solver.enqueue(new ChangeVersion(to, null));
+      return null;
+    }
+
+    // The constraint has changed, so see what the best version of the package
+    // that meets the new constraint is.
+    // TODO(rnystrom): Should this always be the default source?
+    var source = solver._sources.defaultSource;
+    return source.findVersion(to, newConstraint).transform((best) {
+      // TODO(rnystrom): Better exception.
+      if (best == null) throw new NoVersionException(to, newConstraint);
+
+      if (dependency.version != best) {
+        solver.enqueue(new ChangeVersion(to, best));
+      }
+    });
+  }
+}
+
+// TODO(rnystrom): Instead of always pulling from the source (which will mean
+// hitting a server, we should cache pubspecs of installed packages in the
+// system cache.

[nweiz, 2012/06/18 18:29:19]

Rather than making a separate cache of just pubspecs, I think we should make use
of the pubspecs for the packages installed in the cache if such packages exist
and just fetch from the source otherwise. Keeping our own, separate pubspec
cache may violate some assumptions the sources make about when the spec might
update.

[Bob Nystrom, 2012/06/20 01:40:04]

Agreed that we should do this.
Hmm good point. Right now, this is just an in-memory cache. That's important
because the solver may need a given pubspec multiple times during a single solve
and we don't want to hit the server each time for that. If we ever look into
making that more persistent, we'll do some design on it.

+/**
+ * Maintains a synchronous cache of previously-loaded pubspecs. Used to

[nweiz, 2012/06/18 18:29:19]

What do you mean by "synchronous"?

[Bob Nystrom, 2012/06/20 01:40:04]

Stale comment. This used to have a synchronous "get" method for pubspecs that
were known to be in the cache. ChangeVersion would try to use that to reduce the
nested async calls but it was more trouble than it was worth. Fixed the comment.

+ * avoid requesting the same pubspec from the server repeatedly.
+ */
+class PubspecCache {
+  final SourceRegistry _sources;
+  final Map<String, Map<Version, Pubspec>> _pubspecs;
+
+  PubspecCache(this._sources)
+      : _pubspecs = <Map<Version, Pubspec>>{};
+
+  /**
+   * Adds the already loaded [package] to the cache.
+   */
+  void cache(Package package) {
+    _pubspecs.putIfAbsent(package.name, () => new Map<Version, Pubspec>());
+    _pubspecs[package.name][package.version] = package.pubspec;
+  }
+
+  /**
+   * Loads the pubspec for [package] at [version].
+   */
+  Future<Pubspec> load(String package, Version version) {
+    // Complete immediately if it's already cached.
+    if (_pubspecs.containsKey(package) &&
+        _pubspecs[package].containsKey(version)) {
+      return new Future<Pubspec>.immediate(_pubspecs[package][version]);
+    }
+
+    // TODO(rnystrom): Should this always be the default source?
+    var source = _sources.defaultSource;
+    return source.describe(package, version).transform((pubspec) {
+      // Cache it.
+      _pubspecs.putIfAbsent(package, () => new Map<Version, Pubspec>());
+      _pubspecs[package][version] = pubspec;
+
+      return pubspec;
+    });
+  }
+}
+
+/**
+ * Describes one [Package] in the [DependencyGraph] and keeps track of which
+ * packages depend on it and what [VersionConstraint]s they place on it.
+ */
+class Dependency {
+  /**
+   * The currently selected best version for this dependency.
+   */
+  Version version;
+
+  /**
+   * The constraints that depending packages have placed on this one.
+   */
+  final Map<String, VersionConstraint> _constraints;
+
+  /**
+   * 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() => !_constraints.isEmpty();
+
+  /**
+   * 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 (_constraints.isEmpty()) return null;
+    return new VersionConstraint.intersect(_constraints.getValues());
+  }
+
+  Dependency()
+      : _constraints = <VersionConstraint>{};
+
+  /**
+   * Places [constraint] from [package] onto this.
+   */
+  void setConstraint(String package, VersionConstraint constraint) {

[nweiz, 2012/06/18 18:29:19]

"addConstraint" would be a clearer name. It's true that that name is a little
misleading when called twice with the same package, but the current name is
misleading when this method is called only once, since it implies that there's a
single constraint for the dependency being set. Since in practice this is called
only once at a time, I think "add" is clearer.

[Bob Nystrom, 2012/06/20 01:40:04]

Changed to "placeConstraint". :)

+    if (constraint == null) {
+      _constraints.remove(package);
+    } else {
+      _constraints[package] = constraint;
+    }
+  }
+}
+
+// TODO(rnystrom): Report the last of depending packages and their 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
+ * that fit that constraint.
+ */
+class NoVersionException implements Exception {
+  final String package;
+  final VersionConstraint version;

[nweiz, 2012/06/18 18:29:19]

s/version/constraint/.

[Bob Nystrom, 2012/06/20 01:40:04]

Done.

+
+  NoVersionException(this.package, this.version);
+
+  String toString() =>
+      "Package '$package' has no versions that match constraint $version.";
+}
+
+// TODO(rnystrom): Report the last of depending packages and their constraints.
+/**
+ * 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 {
+  final String package;
+
+  DisjointConstraintException(this.package);
+
+  String toString() =>
+      "Package '$package' has disjoint constraints.";
+}
+
+/**
+ * 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.";
+}