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 = <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(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.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);
+      } 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) {
+    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(tryUnlockDepender);
+  }
+
   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 111 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);
 
+  abstract void undo(VersionSolver solver);
+
   Future _processChange(VersionSolver solver, Source source, description,
-      Dependency dependency, VersionConstraint oldConstraint,
-      VersionConstraint newConstraint) {
+      Dependency dependency, VersionConstraint oldConstraint) {

[Bob Nystrom, 2012/08/21 18:29:57]

(source, dep, constraint) is a PackageRef. Can we just pass one of those around
instead? Seems like it would make this a lot cleaner.

[nweiz, 2012/08/21 19:57:23]

Calling these values a PackageRef isn't really an accurate description of what's
going on. [source] and [description] are just capturing the properties of
[dependency] in case removing a package ref from that caused them to be deleted.

A more semantic way to clean this up would be to pass in the old dependency as
well as the new dependency, so that's what I've done.

     var name = dependency.name;
+    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.tryUnlockDepender(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) {
+      if (source == null) print("dependency for null source: ${dependency.name}");

[Bob Nystrom, 2012/08/21 18:29:57]

Debug code. Nix.

[nweiz, 2012/08/21 19:57:23]

Done.

       solver.enqueue(new ChangeVersion(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(
           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) {
       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));
       }
     });
   }
 }
 
 /**
  * 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);
+        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;
+    _removed = dependency.removeConstraint(depender);
     return _processChange(solver, source, description, dependency,
-        oldConstraint, newConstraint);
+        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 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. */
+  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 latest version of '$package', $best, does not match $constraint.";
+}
+
 // 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)}'";
 }