Use backtracking when solving dependency constraints.

utils/tests/pub/version_solver_test.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 pub_update_test;
 
 import 'dart:async';
 import 'dart:io';
 
 import 'package:unittest/unittest.dart';
 
 import '../../pub/lock_file.dart';
 import '../../pub/package.dart';
 import '../../pub/pubspec.dart';
 import '../../pub/source.dart';
 import '../../pub/source_registry.dart';
 import '../../pub/system_cache.dart';
 import '../../pub/utils.dart';
 import '../../pub/version.dart';
-import '../../pub/version_solver.dart';
+import '../../pub/solver/version_solver.dart';
 import 'test_pub.dart';
 
-Matcher noVersion(List<String> packages) {
-  return predicate((x) {
-    if (x is! NoVersionException) return false;
-
-    // Make sure the error string mentions the conflicting dependers.
-    var message = x.toString();
-    return packages.every((package) => message.contains(package));
-  }, "is a NoVersionException");
-}
-
-Matcher disjointConstraint(List<String> packages) {
-  return predicate((x) {
-    if (x is! DisjointConstraintException) return false;
-
-    // Make sure the error string mentions the conflicting dependers.
-    var message = x.toString();
-    return packages.every((package) => message.contains(package));
-  }, "is a DisjointConstraintException");
-}
-
-Matcher descriptionMismatch(String package1, String package2) {
-  return predicate((x) {
-    if (x is! DescriptionMismatchException) return false;
-
-    // Make sure the error string mentions the conflicting dependers.
-    if (!x.toString().contains(package1)) return false;
-    if (!x.toString().contains(package2)) return false;
-
-    return true;
-  }, "is a DescriptionMismatchException");
-}
-
-final couldNotSolve = predicate((x) => x is CouldNotSolveException,
-    "is a CouldNotSolveException");
-
-Matcher sourceMismatch(String package1, String package2) {
-  return predicate((x) {
-    if (x is! SourceMismatchException) return false;
-
-    // Make sure the error string mentions the conflicting dependers.
-    if (!x.toString().contains(package1)) return false;
-    if (!x.toString().contains(package2)) return false;
-
-    return true;
-  }, "is a SourceMismatchException");
-}
-
 MockSource source1;
 MockSource source2;
 
+bool allowBacktracking;
+
 main() {
   initConfig();
 
+  for (allowBacktracking in [false, true]) {
+    group(allowBacktracking ? 'BackTrackingSolver' : 'GreedySolver', () {
+      group('basic graph', basicGraph);
+      group('with lockfile', withLockFile);
+      group('root dependency', rootDependency);
+      group('dev dependency', devDependency);
+      group('unsolvable', unsolvable);
+      group('backtracking', backtracking);
+    });
+  }
+}
+
+void basicGraph() {
   testResolve('no dependencies', {
     'myapp 0.0.0': {}
   }, result: {
     'myapp from root': '0.0.0'
   });
 
   testResolve('simple dependency tree', {
     'myapp 0.0.0': {
       'a': '1.0.0',
       'b': '1.0.0'
@@ skipping 55 matching lines @@
     'foo 1.0.3': { 'zoop': '1.0.0' },
     'bar 1.0.0': { 'foo': '<=1.0.1' },
     'bang 1.0.0': {},
     'whoop 1.0.0': {},
     'zoop 1.0.0': {}
   }, result: {
     'myapp from root': '0.0.0',
     'foo': '1.0.1',
     'bar': '1.0.0',
     'bang': '1.0.0'
+  }, maxTries: 2, hasGreedySolution: true);
+
+  testResolve('circular dependency', {
+    'myapp 1.0.0': {
+      'foo': '1.0.0'
+    },
+    'foo 1.0.0': {
+      'bar': '1.0.0'
+    },
+    'bar 1.0.0': {
+      'foo': '1.0.0'
+    }
+  }, result: {
+    'myapp from root': '1.0.0',
+    'foo': '1.0.0',
+    'bar': '1.0.0'
   });
+}
 
+withLockFile() {
   testResolve('with compatible locked dependency', {
     'myapp 0.0.0': {
       'foo': 'any'
     },
     'foo 1.0.0': { 'bar': '1.0.0' },
     'foo 1.0.1': { 'bar': '1.0.1' },
     'foo 1.0.2': { 'bar': '1.0.2' },
     'bar 1.0.0': {},
     'bar 1.0.1': {},
     'bar 1.0.2': {}
@@ skipping 35 matching lines @@
     'bar 1.0.2': {},
     'baz 1.0.0': {}
   }, lockfile: {
     'baz': '1.0.0'
   }, result: {
     'myapp from root': '0.0.0',
     'foo': '1.0.2',
     'bar': '1.0.2'
   });
 
-  testResolve('circular dependency', {
+  testResolve('unlocks dependencies if necessary to ensure that a new '
+      'dependency is satisfied', {
+    'myapp 0.0.0': {
+      'foo': 'any',
+      'newdep': 'any'
+    },
+    'foo 1.0.0': { 'bar': '<2.0.0' },
+    'bar 1.0.0': { 'baz': '<2.0.0' },
+    'baz 1.0.0': { 'qux': '<2.0.0' },
+    'qux 1.0.0': {},
+    'foo 2.0.0': { 'bar': '<3.0.0' },
+    'bar 2.0.0': { 'baz': '<3.0.0' },
+    'baz 2.0.0': { 'qux': '<3.0.0' },
+    'qux 2.0.0': {},
+    'newdep 2.0.0': { 'baz': '>=1.5.0' }
+  }, lockfile: {
+    'foo': '1.0.0',
+    'bar': '1.0.0',
+    'baz': '1.0.0',
+    'qux': '1.0.0'
+  }, result: {
+    'myapp from root': '0.0.0',
+    'foo': '2.0.0',
+    'bar': '2.0.0',
+    'baz': '2.0.0',
+    'qux': '1.0.0',
+    'newdep': '2.0.0'
+  }, maxTries: 3, hasGreedySolution: true);
+}
+
+rootDependency() {
+  testResolve('with root source', {
     'myapp 1.0.0': {
       'foo': '1.0.0'
     },
-    'foo 1.0.0': {
-      'bar': '1.0.0'
-    },
-    'bar 1.0.0': {
-      'foo': '1.0.0'
-    }
-  }, result: {
-    'myapp from root': '1.0.0',
-    'foo': '1.0.0',
-    'bar': '1.0.0'
-  });
-
-  testResolve('dependency back onto root package', {
-    'myapp 1.0.0': {
-      'foo': '1.0.0'
-    },
     'foo 1.0.0': {
       'myapp from root': '>=1.0.0'
     }
   }, result: {
     'myapp from root': '1.0.0',
     'foo': '1.0.0'
   });
 
-  testResolve('dependency back onto root package with different source', {
+  testResolve('with different source', {
     'myapp 1.0.0': {
       'foo': '1.0.0'
     },
     'foo 1.0.0': {
       'myapp': '>=1.0.0'
     }
   }, result: {
     'myapp from root': '1.0.0',
     'foo': '1.0.0'
   });
 
-  testResolve('mismatched dependencies back onto root package', {
+  testResolve('with mismatched sources', {
     'myapp 1.0.0': {
       'foo': '1.0.0',
       'bar': '1.0.0'
     },
     'foo 1.0.0': {
       'myapp': '>=1.0.0'
     },
     'bar 1.0.0': {
       'myapp from mock2': '>=1.0.0'
     }
   }, error: sourceMismatch('foo', 'bar'));
 
-  testResolve('dependency back onto root package with wrong version', {
+  testResolve('with wrong version', {
     'myapp 1.0.0': {
       'foo': '1.0.0'
     },
     'foo 1.0.0': {
       'myapp': '<1.0.0'
     }
-  }, error: disjointConstraint(['foo']));
+  }, error: couldNotSolve);
+}
 
+devDependency() {
+  testResolve("includes root package's dev dependencies", {
+    'myapp 1.0.0': {
+      '(dev) foo': '1.0.0',
+      '(dev) bar': '1.0.0'
+    },
+    'foo 1.0.0': {},
+    'bar 1.0.0': {}
+  }, result: {
+    'myapp from root': '1.0.0',
+    'foo': '1.0.0',
+    'bar': '1.0.0'
+  });
+
+  testResolve("includes dev dependency's transitive dependencies", {
+    'myapp 1.0.0': {
+      '(dev) foo': '1.0.0'
+    },
+    'foo 1.0.0': {
+      'bar': '1.0.0'
+    },
+    'bar 1.0.0': {}
+  }, result: {
+    'myapp from root': '1.0.0',
+    'foo': '1.0.0',
+    'bar': '1.0.0'
+  });
+
+  testResolve("ignores transitive dependency's dev dependencies", {
+    'myapp 1.0.0': {
+      'foo': '1.0.0'
+    },
+    'foo 1.0.0': {
+      '(dev) bar': '1.0.0'
+    },
+    'bar 1.0.0': {}
+  }, result: {
+    'myapp from root': '1.0.0',
+    'foo': '1.0.0'
+  });
+}
+
+unsolvable() {
   testResolve('no version that matches requirement', {
     'myapp 0.0.0': {
       'foo': '>=1.0.0 <2.0.0'
     },
     'foo 2.0.0': {},
     'foo 2.1.3': {}
   }, error: noVersion(['myapp']));
 
   testResolve('no version that matches combined constraint', {
     'myapp 0.0.0': {
@@ skipping 48 matching lines @@
     'foo 1.0.0': {
       'shared': '1.0.0'
     },
     'bar 1.0.0': {
       'shared from mock2': '1.0.0'
     },
     'shared 1.0.0': {},
     'shared 1.0.0 from mock2': {}
   }, error: sourceMismatch('foo', 'bar'));
 
-  testResolve('unstable dependency graph', {
+  testResolve('no valid solution', {
+    'myapp 0.0.0': {
+      'a': 'any',
+      'b': 'any'
+    },
+    'a 1.0.0': {
+      'b': '1.0.0'
+    },
+    'a 2.0.0': {
+      'b': '2.0.0'
+    },
+    'b 1.0.0': {
+      'a': '2.0.0'
+    },
+    'b 2.0.0': {
+      'a': '1.0.0'
+    }
+  }, error: couldNotSolve, maxTries: 4);
+}
+
+backtracking() {
+  testResolve('circular dependency on older version', {
     'myapp 0.0.0': {
       'a': '>=1.0.0'
     },
     'a 1.0.0': {},
     'a 2.0.0': {
       'b': '1.0.0'
     },
     'b 1.0.0': {
       'a': '1.0.0'
     }
-  }, error: couldNotSolve);
+  }, result: {
+    'myapp from root': '0.0.0',
+    'a': '1.0.0'
+  }, maxTries: 2);
 
-  group('dev dependencies', () {
-    testResolve("includes root package's dev dependencies", {
-      'myapp 1.0.0': {
-        '(dev) foo': '1.0.0',
-        '(dev) bar': '1.0.0'
-      },
-      'foo 1.0.0': {},
-      'bar 1.0.0': {}
-    }, result: {
-      'myapp from root': '1.0.0',
-      'foo': '1.0.0',
-      'bar': '1.0.0'
-    });
+  /// The latest versions of a and b disagree on c. An older version of either
+  /// will resolve the problem. This test validates that b, which is farther
+  /// in the dependency graph from myapp is downgraded first.
+  testResolve('rolls back leaf versions first', {
+    'myapp 0.0.0': {
+      'a': 'any'
+    },
+    'a 1.0.0': {
+      'b': 'any'
+    },
+    'a 2.0.0': {
+      'b': 'any',
+      'c': '2.0.0'
+    },
+    'b 1.0.0': {},
+    'b 2.0.0': {
+      'c': '1.0.0'
+    },
+    'c 1.0.0': {},
+    'c 2.0.0': {}
+  }, result: {
+    'myapp from root': '0.0.0',
+    'a': '2.0.0',
+    'b': '1.0.0',
+    'c': '2.0.0'
+  }, maxTries: 2);
 
-    testResolve("includes dev dependency's transitive dependencies", {
-      'myapp 1.0.0': {
-        '(dev) foo': '1.0.0'
-      },
-      'foo 1.0.0': {
-        'bar': '1.0.0'
-      },
-      'bar 1.0.0': {}
-    }, result: {
-      'myapp from root': '1.0.0',
-      'foo': '1.0.0',
-      'bar': '1.0.0'
-    });
+  // Only one version of baz, so foo and bar will have to downgrade until they
+  // reach it.
+  testResolve('simple transitive', {
+    'myapp 0.0.0': {'foo': 'any'},
+    'foo 1.0.0': {'bar': '1.0.0'},
+    'foo 2.0.0': {'bar': '2.0.0'},
+    'foo 3.0.0': {'bar': '3.0.0'},
+    'bar 1.0.0': {'baz': 'any'},
+    'bar 2.0.0': {'baz': '2.0.0'},
+    'bar 3.0.0': {'baz': '3.0.0'},
+    'baz 1.0.0': {}
+  }, result: {
+    'myapp from root': '0.0.0',
+    'foo': '1.0.0',
+    'bar': '1.0.0',
+    'baz': '1.0.0'
+  }, maxTries: 3);
 
-    testResolve("ignores transitive dependency's dev dependencies", {
-      'myapp 1.0.0': {
-        'foo': '1.0.0'
-      },
-      'foo 1.0.0': {
-        '(dev) bar': '1.0.0'
-      },
-      'bar 1.0.0': {}
-    }, result: {
-      'myapp from root': '1.0.0',
-      'foo': '1.0.0'
-    });
-  });
+  // This ensures it doesn't exhaustively search all versions of b and c when
+  // it's really a-2.0.0 which has an unsatisfied dependency.
+  testResolve('backjump to nearer unsatisfied package', {
+    'myapp 0.0.0': {'a': 'any'},
+    'a 1.0.0': {'b': 'any'},
+    'a 2.0.0': {
+      'b': 'any',
+      'd': '2.0.0-nonexistent'
+    },
+    'b 1.0.0': {'c': 'any'},
+    'b 2.0.0': {'c': 'any'},
+    'b 3.0.0': {'c': 'any'},
+    'c 1.0.0': {},
+    'c 2.0.0': {},
+    'c 3.0.0': {},
+    'd 1.0.0': {},
+  }, result: {
+    'myapp from root': '0.0.0',
+    'a': '1.0.0',
+    'b': '3.0.0',
+    'c': '3.0.0'
+  }, maxTries: 2);

[nweiz, 2013/04/10 22:56:35]

This would pass if you used bundler's sort heuristic without using backjumping
at all, since d would be checked before b. If you make a dependency on "c
4.0.0-nonexistent", that might avoid the issue, depending on how b and c were
sorted relative to one another. I think if you add another version of c that
would ensure that it gets sorted after b.

[Bob Nystrom, 2013/04/11 00:55:11]

Sorting by number of versions will require us to download the version lists for
all dependencies of a package before we can start traversing into any of them.

I can do that, but it will add complexity to the solver. In the absense of
empirical data that it will help users, I prefer to keep it simple.
Done, though that doesn't currently affect the sorting.

[nweiz, 2013/04/11 22:12:04]

For this test, I was pointing it out from a black-box perspective; with no
knowledge of the actual implementation, this test could pass either because of
backjumping or because of sort order. That's still the case, BTW, unless you
have "a" depend on "c" instead of "d".

In general, it's pretty clear that sorting by the number of available packages
will help avoid exponential cases. I don't think this requires empirical
evidence; it's not something that's dependent on any practical conditions other
than some packages having different numbers of available versions than others,
which is clearly going to be the case.

I don't think downloading version lists early is a problem. We're probably going
to download those version lists anyway at some point. We should be batching more
requests anyway, since bandwidth is cheap but requests are expensive.

[Bob Nystrom, 2013/04/16 18:34:17]

Added some more documentation and revised the test.
Agreed, done.

+
+  // This sets up a hundred versions of foo and bar, 0.0.0 through 9.9.0. Each
+  // version of foo depends on a baz with the same major version. Each version
+  // of bar depends on a baz with the same minor version. There is only one
+  // version of baz, 0.0.0, so only older versions of foo and bar will
+  // satisfy it.
+  var map = {
+    'myapp 0.0.0': {
+      'foo': 'any',
+      'bar': 'any'
+    },
+    'baz 0.0.0': {}
+  };
+
+  for (var i = 0; i < 10; i++) {
+    for (var j = 0; j < 10; j++) {
+      map['foo $i.$j.0'] = {'baz': '$i.0.0'};
+      map['bar $i.$j.0'] = {'baz': '0.$j.0'};
+    }
+  }
+
+  testResolve('complex backtrack', map, result: {
+    'myapp from root': '0.0.0',
+    'foo': '0.9.0',
+    'bar': '9.0.0',
+    'baz': '0.0.0'
+  }, maxTries: 100);

[nweiz, 2013/04/10 22:56:35]

woo

[Bob Nystrom, 2013/04/11 00:55:11]

Yes, much better.

+
+  // TODO(rnystrom): More tests. In particular:
+  // - Tests that demonstrate backtracking for every case that can cause a
+  //   solution to fail (no versions, disjoint, etc.)
+  // - Tests where there are multiple valid solutions and "best" is possibly
+  //   ambiguous to nail down which order the backtracker tries solutions.
 }
 
-// TODO(rnystrom): More stuff to test:
-// - Depending on a non-existent package.
-// - Test that only a certain number requests are sent to the mock source so we
-//   can keep track of server traffic.
+testResolve(description, packages,
+            {lockfile, result, FailMatcherBuilder error, int maxTries,
+             bool hasGreedySolution}) {
+  // Close over the top-level variable since it will be mutated.
+  var allowBacktracking_ = allowBacktracking;
 
-testResolve(description, packages, {lockfile, result, Matcher error}) {
+  if (maxTries == null) maxTries = 1;
+  if (hasGreedySolution == null) hasGreedySolution = maxTries == 1;
+
+  if (!allowBacktracking_) {
+    // The greedy solver should fail any graph that does expect multiple tries
+    // and isn't explicitly annotated to have a greedy solution.
+    if (!hasGreedySolution) {
+      result = null;
+      error = couldNotSolve;
+    }
+  }
+
   test(description, () {
     var cache = new SystemCache('.');
     source1 = new MockSource('mock1');
     source2 = new MockSource('mock2');
     cache.register(source1);
     cache.register(source2);
     cache.sources.setDefault(source1.name);
 
     // Build the test package graph.
     var root;
     packages.forEach((nameVersion, dependencies) {
       var parsed = parseSource(nameVersion, (isDev, nameVersion, source) {
         var parts = nameVersion.split(' ');
         var name = parts[0];
         var version = parts[1];
 
-        var package = source1.mockPackage(name, version, dependencies);
+        var package = mockPackage(name, version, dependencies);
         if (name == 'myapp') {
           // Don't add the root package to the server, so we can verify that Pub
           // doesn't try to look up information about the local package on the
           // remote server.
           root = package;
         } else {
-          source.addPackage(package);
+          source.addPackage(name, package);
         }
       });
     });
 
     // Clean up the expectation.
     if (result != null) {
       var newResult = {};
       result.forEach((name, version) {
         parseSource(name, (isDev, name, source) {
           version = new Version.parse(version);
           newResult[name] = new PackageId(name, source, version, name);
         });
       });
       result = newResult;
     }
 
     var realLockFile = new LockFile.empty();
     if (lockfile != null) {
       lockfile.forEach((name, version) {
         version = new Version.parse(version);
         realLockFile.packages[name] =
           new PackageId(name, source1, version, name);
       });
     }
 
     // Resolve the versions.
-    var future = resolveVersions(cache.sources, root, realLockFile);
+    var future = resolveVersions(cache.sources, root,
+        allowBacktracking: allowBacktracking_, lockFile: realLockFile);
 
+    var matcher;
     if (result != null) {
-      expect(future, completion(predicate((actualResult) {
-        for (var actualId in actualResult) {
-          if (!result.containsKey(actualId.name)) return false;
-          var expectedId = result.remove(actualId.name);
-          if (actualId != expectedId) return false;
-        }
-        return result.isEmpty;
-      }, 'packages to match $result')));
+      matcher = new SolveSuccessMatcher(result, maxTries);
     } else if (error != null) {
-      expect(future, throwsA(error));
+      matcher = error(maxTries);
     }
+
+    expect(future, completion(matcher));
   });
 }
 
+typedef SolveFailMatcher FailMatcherBuilder(int maxTries);
+
+FailMatcherBuilder noVersion(List<String> packages) {
+  return (maxTries) => new SolveFailMatcher(packages, maxTries,
+      NoVersionException);
+}
+
+FailMatcherBuilder disjointConstraint(List<String> packages) {
+  return (maxTries) => new SolveFailMatcher(packages, maxTries,
+      DisjointConstraintException);
+}
+
+FailMatcherBuilder descriptionMismatch(String package1, String package2) {
+  return (maxTries) => new SolveFailMatcher([package1, package2], maxTries,
+      DescriptionMismatchException);
+}
+
+// If no solution can be found, the solver just reports the last failure that
+// happened during propagation. Since we don't specify the order that solutions
+// are tried, this just validates that *some* failure occurred, but not which.
+SolveFailMatcher couldNotSolve(maxTries) =>
+    new SolveFailMatcher([], maxTries, null);
+
+FailMatcherBuilder sourceMismatch(String package1, String package2) {
+  return (maxTries) => new SolveFailMatcher([package1, package2], maxTries,
+      SourceMismatchException);
+}
+
+class SolveSuccessMatcher implements Matcher {
+  /// The expected concrete package selections.
+  final Map<String, PackageId> _expected;
+
+  /// The maximum number of attempts that should have been tried before finding
+  /// the solution.
+  final int _maxTries;
+
+  SolveSuccessMatcher(this._expected, this._maxTries);
+
+  Description describe(Description description) {
+    return description.add(
+        'Solver to use at most $_maxTries attempts to find:\n'
+        '${_listPackages(_expected.values)}');
+  }
+
+  Description describeMismatch(SolveResult result,
+                               Description description,
+                               MatchState state, bool verbose) {
+    if (!result.succeeded) {
+      description.add('Solver failed with:\n${result.error}');
+      return;
+    }
+
+    description.add('Resolved:\n${_listPackages(result.packages)}\n');
+    description.add(state.state);
+    return description;
+  }
+
+  bool matches(SolveResult result, MatchState state) {
+    if (!result.succeeded) return false;
+
+    var expected = new Map.from(_expected);
+    for (var id in result.packages) {
+      if (!expected.containsKey(id.name)) {
+        state.state = 'Should not have selected $id';
+        return false;
+      }
+
+      var expectedId = expected.remove(id.name);
+      if (id != expectedId) {
+        state.state = 'Expected $expectedId, not $id';
+        return false;
+      }
+    }
+
+    if (!expected.isEmpty) {
+      state.state = 'Missing:\n${_listPackages(expected.values)}';
+      return false;
+    }
+
+    // Allow 1 here because the greedy solver will only make one attempt.
+    if (result.attemptedSolutions != 1 &&
+        result.attemptedSolutions != _maxTries) {
+      state.state = 'Took ${result.attemptedSolutions} attempts';
+      return false;
+    }
+
+    return true;
+  }
+
+  String _listPackages(Iterable<PackageId> packages) {
+    return '- ${packages.join('\n- ')}';
+  }
+}
+
+class SolveFailMatcher implements Matcher {
+  /// The strings that should appear in the resulting error message.
+  final Iterable<String> _expected;
+
+  /// The maximum number of attempts that should be tried before failing.
+  final int _maxTries;
+
+  /// The concrete error type that should be found, or `null` if any
+  /// [SolveFailure] is allowed.
+  final Type _expectedType;
+
+  SolveFailMatcher(this._expected, this._maxTries, this._expectedType);
+
+  Description describe(Description description) {
+    description.add('Solver should fail after at most $_maxTries attempts.');
+    if (!_expected.isEmpty) {
+      var textList = _expected.map((s) => '"$s"').join(", ");
+      description.add(' The error should contain $textList.');
+    }
+    return description;
+  }
+
+  Description describeMismatch(SolveResult result,
+                               Description description,
+                               MatchState state, bool verbose) {
+    if (result.succeeded) {
+      description.add('Solver succeeded');
+      return;
+    }
+
+    description.add(state.state);
+    return description;
+  }
+
+  bool matches(SolveResult result, MatchState state) {
+    if (result.succeeded) return false;
+
+    if (_expectedType != null && result.error.runtimeType != _expectedType) {
+      state.state = 'Should have error type $_expectedType, got '
+                    '${result.error.runtimeType}';
+      return false;
+    }
+
+    var message = result.error.toString();
+    for (var expected in _expected) {
+      if (!message.contains(expected)) {
+        state = 'Expected error to contain "$expected", got:\n$message';
+        return false;
+      }
+    }
+
+    // Allow 1 here because the greedy solver will only make one attempt.
+    if (result.attemptedSolutions != 1 &&
+        result.attemptedSolutions != _maxTries) {
+      state.state = 'Took ${result.attemptedSolutions} attempts';
+      return false;
+    }
+
+    return true;
+  }
+}
+
 /// A source used for testing. This both creates mock package objects and acts
 /// as a source for them.
 ///
 /// In order to support testing packages that have the same name but different
 /// descriptions, a package's name is calculated by taking the description
 /// string and stripping off any trailing hyphen followed by non-hyphen
 /// characters.
 class MockSource extends Source {
-  final Map<String, Map<Version, Package>> _packages;
+  final _packages = <String, Map<Version, Package>>{};
+
+  /// Keeps track of which package version lists have been requested. Ensures
+  /// that a source is only hit once for a given package and that pub
+  /// internally caches the results.
+  final _requestedVersions = new Set<String>();
+
+  /// Keeps track of which package pubspecs have been requested. Ensures that a
+  /// source is only hit once for a given package and that pub internally
+  /// caches the results.
+  final _requestedPubspecs = new Map<String, Set<Version>>();
 
   final String name;
   bool get shouldCache => true;
 
-  MockSource(this.name)
-      : _packages = <String, Map<Version, Package>>{};
+  MockSource(this.name);
 
   Future<List<Version>> getVersions(String name, String description) {
-    return new Future.of(() => _packages[description].keys.toList());
+    return new Future.of(() {
+      // Make sure the solver doesn't request the same thing twice.
+      if (_requestedVersions.contains(description)) {
+        throw 'Version list for $description was already requested.';
+      }
+
+      _requestedVersions.add(description);
+
+      if (!_packages.containsKey(description)){
+        throw 'MockSource does not have a package matching "$description".';
+      }
+      return _packages[description].keys.toList();
+    });
   }
 
   Future<Pubspec> describe(PackageId id) {
-    return new Future.of(() => _packages[id.name][id.version].pubspec);
+    return new Future.of(() {
+      // Make sure the solver doesn't request the same thing twice.
+      if (_requestedPubspecs.containsKey(id.description) &&
+          _requestedPubspecs[id.description].contains(id.version)) {
+        throw 'Pubspec for $id was already requested.';
+      }
+
+      _requestedPubspecs.putIfAbsent(id.description, () => new Set<Version>());
+      _requestedPubspecs[id.description].add(id.version);
+
+      return _packages[id.description][id.version].pubspec;
+    });
   }
 
   Future<bool> install(PackageId id, String path) {
     throw 'no';
   }
 
-  Package mockPackage(String description, String version,
-      Map dependencyStrings) {
-    // Build the pubspec dependencies.
-    var dependencies = <PackageRef>[];
-    var devDependencies = <PackageRef>[];
-
-    dependencyStrings.forEach((name, constraint) {
-      parseSource(name, (isDev, name, source) {
-        var packageName = name.replaceFirst(new RegExp(r"-[^-]+$"), "");
-        var ref = new PackageRef(packageName, source,
-            new VersionConstraint.parse(constraint), name);
-
-        if (isDev) {
-          devDependencies.add(ref);
-        } else {
-          dependencies.add(ref);
-        }
-      });
-    });
-
-    var pubspec = new Pubspec(
-        description, new Version.parse(version), dependencies, devDependencies,
-        new PubspecEnvironment());
-    return new Package.inMemory(pubspec);
-  }
-
-  void addPackage(Package package) {
-    _packages.putIfAbsent(package.name, () => new Map<Version, Package>());
-    _packages[package.name][package.version] = package;
+  void addPackage(String description, Package package) {
+    _packages.putIfAbsent(description, () => new Map<Version, Package>());
+    _packages[description][package.version] = package;
   }
 }
 
+Package mockPackage(String description, String version,
+                    Map dependencyStrings) {
+  // Build the pubspec dependencies.
+  var dependencies = <PackageRef>[];
+  var devDependencies = <PackageRef>[];
+
+  dependencyStrings.forEach((name, constraint) {
+    parseSource(name, (isDev, name, source) {
+      var packageName = name.replaceFirst(new RegExp(r"-[^-]+$"), "");
+      var ref = new PackageRef(packageName, source,
+          new VersionConstraint.parse(constraint), name);
+
+      if (isDev) {
+        devDependencies.add(ref);
+      } else {
+        dependencies.add(ref);
+      }
+    });
+  });
+
+  var name = description.replaceFirst(new RegExp(r"-[^-]+$"), "");
+  var pubspec = new Pubspec(
+      name, new Version.parse(version), dependencies, devDependencies,
+      new PubspecEnvironment());
+  return new Package.inMemory(pubspec);
+}
+
 void parseSource(String description,
     callback(bool isDev, String name, Source source)) {
   var isDev = false;
 
   if (description.startsWith("(dev) ")) {
     description = description.substring("(dev) ".length);
     isDev = true;
   }
 
   var name = description;
   var source = source1;
 
   var sourceNames = {
     'mock1': source1,
     'mock2': source2,
     'root': null
   };
 
   var match = new RegExp(r"(.*) from (.*)").firstMatch(description);
   if (match != null) {
     name = match[1];
     source = sourceNames[match[2]];
   }
 
   callback(isDev, name, source);
 }