Use backtracking when solving dependency constraints.

utils/pub/package.dart

Index: utils/pub/package.dart
diff --git a/utils/pub/package.dart b/utils/pub/package.dart
index b7c2f9943a38659cedcb9c6f461ff85afdb4e9be..36e7441d5c14e82e80cbf19754c093b82906cc49 100644
--- a/utils/pub/package.dart
+++ b/utils/pub/package.dart
@@ -105,6 +105,13 @@ class PackageId implements Comparable<PackageId> {
 
   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;
 
@@ -145,6 +152,17 @@ class PackageId implements Comparable<PackageId> {
 
   /// 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` of this references description matches [other]'s.

[nweiz, 2013/03/29 01:58:25]

"of" -> "if", "references" -> "id's"

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+  bool descriptionEquals(PackageRef other) {
+    return source.descriptionsEqual(description, other.description);
+  }
 }
 
 /// A reference to a package. Unlike a [PackageId], a PackageRef may not
@@ -167,6 +185,7 @@ class PackageRef {
 
   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,
@@ -186,6 +205,11 @@ class PackageRef {
   /// concrete version.
   PackageId atVersion(Version version) =>
     new PackageId(name, source, version, description);
+
+  /// Returns `true` of this references description matches [other]'s.

[nweiz, 2013/03/29 01:58:25]

"of" -> "if", "references" -> "reference's"

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+  bool descriptionEquals(PackageRef other) {
+    return source.descriptionsEqual(description, other.description);
+  }
 }
 
 class PubspecNotFoundException implements Exception {