Use backtracking when solving dependency constraints.

utils/pub/package.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.
 
 library package;
 
 import 'dart:async';
 
 import 'package:pathos/path.dart' as path;
 
@@ skipping 85 matching lines @@
   final Version version;
 
   /// The metadata used by the package's [source] to identify and locate it. It
   /// contains whatever [Source]-specific data it needs to be able to install
   /// the package. For example, the description of a git sourced package might
   /// by the URL "git://github.com/dart/uilib.git".
   final description;
 
   PackageId(this.name, this.source, this.version, this.description);
 
+  /// Creates an ID for the given root package.
+  PackageId.root(Package package)
+      : name = package.name,
+        source = null,
+        version = package.version,
+        description = package.name;
+
   /// Whether this ID identifies the root package.
   bool get isRoot => source == null;
 
   int get hashCode => name.hashCode ^ source.hashCode ^ version.hashCode;
 
   /// Gets the directory where this package is or would be found in the
   /// [SystemCache].
   Future<String> get systemCacheDirectory => source.systemCacheDirectory(this);
 
   bool operator ==(other) {
@@ skipping 20 matching lines @@
     if (nameComp != 0) return nameComp;
 
     return version.compareTo(other.version);
   }
 
   /// Returns the pubspec for this package.
   Future<Pubspec> describe() => source.describe(this);
 
   /// Returns a future that completes to the resovled [PackageId] for this id.
   Future<PackageId> get resolved => source.resolveId(this);
+
+  /// Returns a [PackageRef] that references this package and constrains its
+  /// version to exactly match [version].
+  PackageRef toRef() {
+    return new PackageRef(name, source, version, description);
+  }
+
+  /// Returns `true` if this id's description matches [other]'s.
+  bool descriptionEquals(PackageRef other) {
+    return source.descriptionsEqual(description, other.description);
+  }
 }
 
 /// A reference to a package. Unlike a [PackageId], a PackageRef may not
 /// unambiguously refer to a single package. It may describe a range of allowed
 /// packages.
 class PackageRef {
   /// The name of the package being identified.
   final String name;
 
   /// The [Source] used to look up the package. If this refers to a root
   /// package, this will be `null`.
   final Source source;
 
   /// The allowed package versions.
   final VersionConstraint constraint;
 
   /// The metadata used to identify the package being referenced. The
   /// interpretation of this will vary based on the [source].
   final description;
 
   PackageRef(this.name, this.source, this.constraint, this.description);
 
+  // TODO(rnystrom): Remove this if the old version solver is removed.
   /// Creates a reference to the given root package.
   PackageRef.root(Package package)
       : name = package.name,
         source = null,
         constraint = package.version,
         description = package.name;
 
   /// Whether this refers to the root package.
   bool get isRoot => source == null;
 
   String toString() {
     if (isRoot) return "$name $constraint (root)";
     return "$name $constraint from $source ($description)";
   }
 
   /// Returns a [PackageId] generated from this [PackageRef] with the given
   /// concrete version.
   PackageId atVersion(Version version) =>
     new PackageId(name, source, version, description);
+
+  /// Returns `true` if this reference's description matches [other]'s.
+  bool descriptionEquals(PackageRef other) {
+    return source.descriptionsEqual(description, other.description);
+  }
 }
 
 class PubspecNotFoundException implements Exception {
   final String name;
 
   PubspecNotFoundException(this.name);
 
   String toString() => 'Package "$name" doesn\'t have a pubspec.yaml file.';
 }
 
 class PubspecHasNoNameException implements Exception {
   final String name;
 
   PubspecHasNoNameException(this.name);
 
   String toString() => 'Package "$name"\'s pubspec.yaml file is missing the '
     'required "name" field (e.g. "name: $name").';
 }
 
 class PubspecNameMismatchException implements Exception {
   final String expectedName;
   final String actualName;
 
   PubspecNameMismatchException(this.expectedName, this.actualName);
 
   String toString() => 'The name you specified for your dependency, '
     '"$expectedName", doesn\'t match the name "$actualName" in its pubspec.';
 }