Allow `pub install` and `pub update` to update dependers.

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 a71a04f8ff79d3cc62a633304ca0d0d6233419ef..9c7d84cddcdffdd0e78d3f4df4f9759254ff74d2 100644
--- a/utils/pub/version_solver.dart
+++ b/utils/pub/version_solver.dart
@@ -76,6 +76,19 @@ class VersionSolver {
         _packages = <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.

[Bob Nystrom, 2012/08/15 17:48:16]

Nice comment. :)

+   */
+  void useBestVersion(String package) {

[Bob Nystrom, 2012/08/15 17:48:16]

"useLatestVersion"

Up to this point, "best" always meant "the latest version that matches the
constraints", and I'd like to preserve that meaning.

[nweiz, 2012/08/15 21:25:42]

Done.

+    // TODO(nweiz): How do we want to detect and handle unknown dependencies
+    // here?
+    getDependency(package).useBestVersion = 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.
@@ -131,6 +144,56 @@ class VersionSolver {
     _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.source.getVersions(dependency.description)
+        .transform((versions) {
+      var best = null;
+      for (var version in versions) {
+        if (dependency.useBestVersion ||
+            dependency.constraint.allows(version)) {
+          if (best == null || version > best) best = version;
+        }
+      }
+
+      // TODO(rnystrom): Better exception.
+      if (best == null) {
+        if (unlockDepender(dependency)) return null;
+        throw new NoVersionException(dependency.name, dependency.constraint);
+      } else if (!dependency.constraint.allows(best)) {
+        if (unlockDepender(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 unlockDepender(Dependency dependency) {

[Bob Nystrom, 2012/08/15 17:48:16]

"unlockDepender" -> "tryUnlockDepender"

[nweiz, 2012/08/15 21:25:42]

Done.

+    for (var dependerName in dependency.dependers) {
+      var depender = getDependency(dependerName);
+      var locked = lockFile.packages[dependerName];
+      if (locked != null && depender.version == locked.version) {
+        enqueue(new UnlockPackage(depender));
+        return true;
+      }
+    }
+    return dependency.dependers.map(getDependency).some(unlockDepender);
+  }
+
   List<PackageId> buildResults() {
     return _packages.getValues().filter((dep) => dep.isDependedOn).map((dep) {
       var description = dep.description;
@@ -261,14 +324,24 @@ class ChangeVersion implements WorkItem {
 class ChangeConstraint implements WorkItem {
   abstract Future process(VersionSolver solver);
 
-  Future _processChange(VersionSolver solver, Source source, description,
-      Dependency dependency, VersionConstraint oldConstraint,
-      VersionConstraint newConstraint) {
+  abstract void undo(VersionSolver solver);
+
+  Future _processChange(VersionSolver solver, Dependency dependency,
+      VersionConstraint oldConstraint) {
     var name = dependency.name;
+    var description = dependency.description;
+    var source = dependency.source;
+    var newConstraint = dependency.constraint;
 
     // If the package is over-constrained, i.e. the packages depending have
-    // disjoint constraints, then stop.
+    // 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.unlockDepender(dependency)) {
+        undo(solver);
+        return null;
+      }
+
       throw new DisjointConstraintException(name);
     }
 
@@ -303,18 +376,10 @@ class ChangeConstraint implements WorkItem {
 
     // The constraint has changed, so see what the best version of the package
     // that meets the new constraint is.
-    return source.getVersions(description).transform((versions) {
-      var best = null;
-      for (var version in versions) {
-        if (newConstraint.allows(version)) {
-          if (best == null || version > best) best = version;
-        }
-      }
-
-      // TODO(rnystrom): Better exception.
-      if (best == null) throw new NoVersionException(name, newConstraint);
-
-      if (dependency.version != best) {
+    return solver.getBestVersion(dependency).transform((best) {
+      if (best == null) {
+        undo(solver);
+      } else if (dependency.version != best) {
         solver.enqueue(new ChangeVersion(source, description, best));

[Bob Nystrom, 2012/08/15 17:48:16]

Here, we check that the version has actually changed before we enqueue the
ChangeVersion, which is good. But it looks like other places above this aren't
doing that.

If I remember right, I had originally intended that you only enqueue work items
when you know there's work to be done (i.e. you check for a delta first). Do you
think we should add these checks above?

[nweiz, 2012/08/15 21:25:42]

I didn't go that direction for code complexity issues. In order to determine
whether UnlockPackage would cause an actual change, we need to figure out what
new version it would be pinned at, which requires an asynchronous call to
getBestVersion. This would mean that tryUnlockDepender would need to be async,
which would add a fair amount of complexity.

       }
     });
@@ -343,9 +408,11 @@ class AddConstraint extends ChangeConstraint {
     var dependency = solver.getDependency(ref.name);
     var oldConstraint = dependency.constraint;
     dependency.placeConstraint(depender, ref);
-    var newConstraint = dependency.constraint;
-    return _processChange(solver, ref.source, ref.description, dependency,
-        oldConstraint, newConstraint);
+    return _processChange(solver, dependency, oldConstraint);
+  }
+
+  void undo(VersionSolver solver) {
+    solver.getDependency(ref.name).removeConstraint(depender);
   }
 }
 
@@ -363,17 +430,38 @@ class RemoveConstraint extends ChangeConstraint {
    */
   String dependent;
 
+  /** The constraint that was removed. */
+  PackageRef _removed;
+
   RemoveConstraint(this.depender, this.dependent);
 
   Future process(VersionSolver solver) {
     var dependency = solver.getDependency(dependent);
     var oldConstraint = dependency.constraint;
     var source = dependency.source;
-    var description = dependency.description;
-    dependency.removeConstraint(depender);
-    var newConstraint = dependency.constraint;
-    return _processChange(solver, source, description, dependency,
-        oldConstraint, newConstraint);
+    _removed = dependency.removeConstraint(depender);
+    return _processChange(solver, dependency, oldConstraint);
+  }
+
+  void undo() {
+    solver.getDependency(dependent).placeConstraint(depender, _removed);
+  }
+}
+
+/** [package]'s version is no longer constrained by the lockfile. */
+class UnlockPackage implements WorkItem {
+  /** The package being unlocked. */
+  Dependency package;
+
+  UnlockPackage(this.package);
+
+  Future process(VersionSolver solver) {
+    solver.lockFile.packages.remove(package.name);
+    return solver.getBestVersion(package).transform((best) {
+      if (best == null) return null;
+      solver.enqueue(new ChangeVersion(
+          package.source, package.description, best));
+    });
   }
 }
 
@@ -452,12 +540,20 @@ class Dependency {
   Version version;
 
   /**
+   * Whether this dependency should always select the best version available.

[Bob Nystrom, 2012/08/15 17:48:16]

"best" -> "latest"

[nweiz, 2012/08/15 21:25:42]

Done.

+   */
+  bool useBestVersion = false;

[Bob Nystrom, 2012/08/15 17:48:16]

"useLatestVersion"

[nweiz, 2012/08/15 21:25:42]

Done.

+
+  /**
    * 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();
 
+  /** A list of all the packages that depend on this dependency. */

[Bob Nystrom, 2012/08/15 17:48:16]

"A list" -> "The names"

[nweiz, 2012/08/15 21:25:42]

Done.

+  Collection<String> get dependers() => _refs.getKeys();
+
   /**
    * 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
@@ -494,13 +590,15 @@ class Dependency {
   /**
    * Removes the constraint from [package] onto this.
    */
-  void removeConstraint(String package) {
-    _refs.remove(package);
+  PackageRef removeConstraint(String package) {
+    var removed = _refs.remove(package);
 
     if (_refs.isEmpty()) {
       source = null;
       description = null;
     }
+
+    return removed;
   }
 }
 
@@ -520,6 +618,22 @@ class NoVersionException implements Exception {
       "Package '$package' has no versions that match $constraint.";
 }
 
+// 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 {
+  final String package;
+  final VersionConstraint constraint;
+  final Version best;
+
+  CouldNotUpdateException(this.package, this.constraint, this.best);
+
+  String toString() =>
+      "The last version of '$package', $best, does not match $constraint.";

[Bob Nystrom, 2012/08/15 17:48:16]

"last" -> "latest"

[nweiz, 2012/08/15 21:25:42]

Done.

+}
+
 // TODO(rnystrom): Report the last of depending packages and their constraints.
 /**
  * Exception thrown when the [VersionConstraint] used to match a package is