First pass at version constraint solver.

utils/tests/pub/version_solver_test.dart

Index: utils/tests/pub/version_solver_test.dart
diff --git a/utils/tests/pub/version_solver_test.dart b/utils/tests/pub/version_solver_test.dart
new file mode 100644
index 0000000000000000000000000000000000000000..286c366a345fd90d6ac7ae78a23247d316249cac
--- /dev/null
+++ b/utils/tests/pub/version_solver_test.dart
@@ -0,0 +1,275 @@
+// 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:io');
+
+#import('../../pub/package.dart');
+#import('../../pub/pubspec.dart');
+#import('../../pub/source.dart');
+#import('../../pub/source_registry.dart');
+#import('../../pub/version.dart');
+#import('../../pub/version_solver.dart');
+#import('../../../lib/unittest/unittest.dart');
+
+final noVersion = 'no version';
+final disjointConstraint = 'disjoint';
+final couldNotSolve = 'unsolved';
+
+main() {
+  testResolve('no dependencies', {
+    'myapp 0.0.0': {}
+  }, result: {
+    'myapp': '0.0.0'
+  });
+
+  testResolve('simple dependency tree', {
+    'myapp 0.0.0': {
+      'a': '1.0.0',
+      'b': '1.0.0'
+    },
+    'a 1.0.0': {
+      'aa': '1.0.0',
+      'ab': '1.0.0'
+    },
+    'aa 1.0.0': {},
+    'ab 1.0.0': {},
+    'b 1.0.0': {
+      'ba': '1.0.0',
+      'bb': '1.0.0'
+    },
+    'ba 1.0.0': {},
+    'bb 1.0.0': {}
+  }, result: {
+    'myapp': '0.0.0',
+    'a': '1.0.0',
+    'aa': '1.0.0',
+    'ab': '1.0.0',
+    'b': '1.0.0',
+    'ba': '1.0.0',
+    'bb': '1.0.0'
+  });
+
+  testResolve('shared dependency with overlapping constraints', {
+    'myapp 0.0.0': {
+      'a': '1.0.0',
+      'b': '1.0.0'
+    },
+    'a 1.0.0': {
+      'shared': '>=2.0.0 <4.0.0'
+    },
+    'b 1.0.0': {
+      'shared': '>=3.0.0 <5.0.0'
+    },
+    'shared 2.0.0': {},
+    'shared 3.0.0': {},
+    'shared 3.6.9': {},
+    'shared 4.0.0': {},
+    'shared 5.0.0': {},
+  }, result: {
+    'myapp': '0.0.0',
+    'a': '1.0.0',
+    'b': '1.0.0',
+    'shared': '3.6.9'
+  });
+
+  testResolve('shared dependency where dependent version in turn affects '
+              'other dependencies', {
+    'myapp 0.0.0': {
+      'foo': '<=1.0.2',
+      'bar': '1.0.0'
+    },
+    'foo 1.0.0': {},
+    'foo 1.0.1': { 'bang': '1.0.0' },
+    'foo 1.0.2': { 'whoop': '1.0.0' },
+    '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': '0.0.0',
+    'foo': '1.0.1',
+    'bar': '1.0.0',
+    'bang': '1.0.0'
+  });
+
+  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);
+
+  testResolve('no version that matches combined constraint', {
+    'myapp 0.0.0': {
+      'foo': '1.0.0',
+      'bar': '1.0.0'
+    },
+    'foo 1.0.0': {
+      'shared': '>=2.0.0 <3.0.0'
+    },
+    'bar 1.0.0': {
+      'shared': '>=2.9.0 <4.0.0'
+    },
+    'shared 2.5.0': {},
+    'shared 3.5.0': {}
+  }, error: noVersion);
+
+  testResolve('disjoint constraints', {
+    'myapp 0.0.0': {
+      'foo': '1.0.0',
+      'bar': '1.0.0'
+    },
+    'foo 1.0.0': {
+      'shared': '<2.0.0'
+    },
+    'bar 1.0.0': {
+      'shared': '>3.0.0'
+    },
+    'shared 2.0.0': {},
+    'shared 4.0.0': {}
+  }, error: disjointConstraint);
+
+  // TODO(rnystrom): Uncomment this when the resolver doesn't get stuck in an
+  // infinite loop on unstable graphs.

[nweiz, 2012/06/18 18:29:19]

Remove TODO

[Bob Nystrom, 2012/06/20 01:40:04]

Done.

+  testResolve('unstable dependency graph', {

[nweiz, 2012/06/18 18:29:19]

Shouldn't this stabilize at a=1.0.0?

[Bob Nystrom, 2012/06/20 01:40:04]

That would be a valid solution, but the solver is greedy. It won't pick a
non-best version for a constraint just to avoid other dependencies that would
lead to a non-solution.

In other words, if it gives you a solution, the versions it picks should be the
best versions for the constraints in the dependency graph of that solution.

[nweiz, 2012/06/20 21:08:48]

But shouldn't it resolve this like so:

* Set a=2.0.0
* Add constraint to b: =1.0.0
* Set b=1.0.0
* Add constraint to a: =1.0.0
* Set a=1.0.0
But if chose a=1.0.0 and b=1.0.0, then that's the case since there is no better
version of b and a=1.0.0 is the best that satisfies all the constraints.

[Bob Nystrom, 2012/06/20 22:29:54]

When it sets a=1.0.0, that removes the dependency that a=2.0.0 has on b=1.0.0.
That removes b from the graph. That in turn removes b's constraint on a=1.0.0.
Since a's constraint changed, we look for the new best version that meets that
constraint and now it becomes a 2.0.0.
a=1.0.0 is the best version that satisfied the set of all possible constraints
that could exist in when considering all versions of those dependencies. But
it's not the best version that matches the actual constraints present in the
resulting graph.

We can't settle on a=1.0.0 and b=1.0.0 because that doesn't make sense: we would
be including b even though nothing actually depends on it and it isn't being
used.

If we settle on a=1.0.0 and no b that graph's constraint on a is just >=1.0.0,
and 1.0.0 isn't the best version that meets that constraint: 2.0.0 is. It would
be a valid graph, but it's confusing. The graph itself doesn't tell you why that
version of a was selected. You would have to know that selecting a different
version of a would have other implications that aren't solvable.

[nweiz, 2012/06/20 23:47:45]

Ah, I see now.

+    '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);
+
+// TODO(rnystrom): More stuff to test:
+// - Root depends on A, A depends back on root, but doesn't allow current
+//   version. Should fail.
+// - Root depends on A, A depends back on root, and does allow current version.
+// - Two packages depend on the same package, but from different sources. Should
+//   fail.
+// - 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, [result, error]) {
+  test(description, () {
+    var sources = new SourceRegistry();
+    var source = new MockSource(sources);
+    sources.register(source);
+    sources.setDefault(source.name);
+
+    // Build the test package graph.
+    var root;
+    packages.forEach((nameVersion, dependencies) {
+      var parts = nameVersion.split(' ');
+      var name = parts[0];
+      var version = parts[1];
+      var package = source.mockPackage(name, version, dependencies);
+      if (name == 'myapp') root = package;
+    });
+
+    // Clean up the expectation.
+    if (result != null) {
+      result.forEach((name, version) {
+        result[name] = new Version.parse(version);
+      });
+    }
+
+    // Resolve the versions.
+    var future = resolveVersions(sources, root);
+
+    if (result != null) {
+      expect(future, completion(recursivelyMatches(result)));
+    } else if (error == noVersion) {
+      expect(future, throwsA(new isInstanceOf<NoVersionException>()));
+    } else if (error == disjointConstraint) {
+      expect(future, throwsA(new isInstanceOf<DisjointConstraintException>()));
+    } else if (error == couldNotSolve) {
+      expect(future, throwsA(new isInstanceOf<CouldNotSolveException>()));
+    } else {
+      expect(future, throwsA(error));
+    }
+
+    // Uncomment this if you want to debug why a resolve is throwing an
+    // exception.

[nweiz, 2012/06/18 18:29:19]

It seems like sufficient information for debugging should be printed by default.

[Bob Nystrom, 2012/06/20 01:40:04]

Done.

+    /*
+    future.handleException((ex) {
+      print(ex);
+      print(future.stackTrace);
+      return true;
+    });
+    */
+  });
+}
+
+class MockSource extends Source {

[nweiz, 2012/06/18 18:29:19]

Maybe it's time to make MockSource its own library in utils/tests/pub? It's
defined three separate times now.

[Bob Nystrom, 2012/06/20 01:40:04]

Maybe. I think each one does different things, and I kind of like mocks that are
minimal and tailored to each use.

[nweiz, 2012/06/20 21:08:48]

I prefer libraries that are re-usable, personally.

+  final SourceRegistry _sources;
+  final Map<String, Map<Version, Package>> _packages;
+
+  String get name() => 'mock';
+  bool get shouldCache() => true;
+
+  MockSource(this._sources)
+      : _packages = <Map<Version, Package>>{};
+
+  Future<Version> findVersion(String name,
+      VersionConstraint constraint) {
+    return fakeAsync(() {
+      var best = null;
+      for (var version in _packages[name].getKeys()) {
+        if (constraint.allows(version)) {
+          if (best == null || version > best) best = version;
+        }
+      }
+
+      return best;
+    });
+  }
+
+  Future<Pubspec> describe(String package, Version version) {
+    return fakeAsync(() {
+      return _packages[package][version].pubspec;
+    });
+  }
+
+  Future<bool> install(PackageId id, String path) {
+    throw 'no';
+  }
+
+  Package mockPackage(String name, String version, Map dependencies) {

[nweiz, 2012/06/18 18:29:19]

It seems like you could simplify this method and avoid taking a SourceRegistry
in the constructor if you just use the Package._ constructor.

[Bob Nystrom, 2012/06/20 01:40:04]

Done.

+    // Build the pubspec string.
+    var pubspec = new StringBuffer();
+    pubspec.add('version: $version\n');
+    if (!dependencies.isEmpty()) {
+      pubspec.add('dependencies:\n');
+      dependencies.forEach((name, version) {
+        pubspec.add('  $name: "$version"\n');
+      });
+    }
+
+    var package = new Package.inMemory(name,
+        new Pubspec.parse(pubspec.toString(), _sources));
+
+    _packages.putIfAbsent(name, () => new Map<Version, Package>());
+    _packages[name][package.version] = package;
+    return package;
+  }
+}
+
+Future fakeAsync(callback()) {
+  var completer = new Completer();
+  new Timer(0, (_) {
+    completer.complete(callback());
+  });
+
+  return completer.future;
+}