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

utils/pub/version_solver.dart

 // 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
@@ skipping 58 matching lines @@
   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 = <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.
     var ref = new PackageRef(new RootSource(_root), _root.version, _root.name);
     enqueue(new AddConstraint('(entrypoint)', ref));
     _pubspecs.cache(ref.atVersion(_root.version), _root.pubspec);
 
     Future processNextWorkItem(_) {
       while (true) {
         // Stop if we are done.
@@ skipping 35 matching lines @@
     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.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;
 
       // 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(
@@ skipping 110 matching lines @@
  * 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.
  */
 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);
     }
 
     // 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(source, description, null));
@@ skipping 14 matching lines @@
     if (lockedPackage != null) {
       var lockedVersion = lockedPackage.version;
       if (newConstraint.allows(lockedVersion)) {
         solver.enqueue(new ChangeVersion(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 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.

       }
     });
   }
 }
 
 /**
  * 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) {
     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);
   }
 }
 
 /**
  * [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) {
     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));
+    });
+  }
+}
+
 // 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;
@@ skipping 55 matching lines @@
    * according to [source].
    */
   var description;
 
   /**
    * The currently-selected best version for this 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
    * package is in the process of being added to the graph), returns `null`.
    */
   VersionConstraint get constraint() {
     if (_refs.isEmpty()) return null;
     return new VersionConstraint.intersect(
         _refs.getValues().map((ref) => ref.constraint));
   }
@@ skipping 16 matching lines @@
       throw new DescriptionMismatchException(
           name, description, ref.description);
     }
 
     _refs[package] = ref;
   }
 
   /**
    * 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;
   }
 }
 
 // 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 constraint;
 
   NoVersionException(this.package, this.constraint);
 
   String toString() =>
       "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
  * 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);
@@ skipping 39 matching lines @@
   final description1;
   final description2;
 
   DescriptionMismatchException(this.package, this.description1,
       this.description2);
 
   // TODO(nweiz): Dump to YAML when that's supported
   String toString() => "Package '$package' has conflicting descriptions "
     "'${JSON.stringify(description1)}' and '${JSON.stringify(description2)}'";
 }