First pass at version constraint solver.

utils/pub/source.dart

Index: utils/pub/source.dart
diff --git a/utils/pub/source.dart b/utils/pub/source.dart
index 974f677f31dd626a90a69ca326e70a27ed583cf7..9647d3907137797b435fbddf62c7e640cf0bdcf7 100644
--- a/utils/pub/source.dart
+++ b/utils/pub/source.dart
@@ -30,6 +30,29 @@ class Source {
   abstract bool get shouldCache();
 
   /**
+   * Finds the best known version of package [name] that meets [constraint].
+   *
+   * Note that this does *not* require the packages to be installed, which is
+   * the point. This is used during version resolution to determine which
+   * package versions are available to be installed (or already installed).
+   */
+  Future<Version> findVersion(String name,

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

Shouldn't "name" be "description" instead?

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

Yeah. Right now, this giant patch punts on how different sources should be
handled and just does the dumb default of treating packages as name/version
pairs.

It should do this better, and there are some TODOs to that effect. If it's OK
with you, I'd like to handle that in a separate patch.

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

Sure, it's reasonable to put this off.

+      VersionConstraint constraint) {

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

This puts a lot of burden onto the sources for understanding every type of
VersionConstraint that exists. This seems dangerous, since additional
VersionConstraints could potentially break third-party sources.

Maybe a better API would be a listVersions method that just returns a list of
all versions available for a given package?

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

Maybe I'm being premature, but I worry that that could be slow/redundant if a
package has a ton of released versions, many of which you already know of
locally.

Right now, a VersionConstraint is always a contiguous range (which may be
inclusive, exclusive, or open on either end) even though the API doesn't make
that clear. If we want, we can make that implicit fact explicitly declared and
then a Source can rely on always being asked for the set of versions within a
range.

Or, if we don't want to worry about that, keep in mind that the simplest
implementation of this for a source is just:

1. Get all versions.
2. Walk the list and see which ones the constraint allows.

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

If we do pass VersionConstraints to sources, we should definitely be explicit
about what the sources can assume about them. I still don't think that's a good
idea, though.

Right now, in order for the source to avoid massive numbers of HTTP fetches, it
also needs to have caching logic for the list of all sources, and it has to have
its own logic for choosing the "best" version (which means it needs to decide
for itself how to handle e.g. prerelease versions). It's not as simple as the
two-step process you outline.

I think for now, worrying about this optimization isn't worth it.

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

My intent is that that caching would live outside of source. So pub itself would
keep a cache of the known version numbers for a given package. When the solver
requests all of the versions in a given range, pub can intersect that with the
ranges that it already knows it has and pass that remaining constraint to the
source.

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

My point is that if the source receives findVersion("foo", >= 5.6.0 < 6.0.0),
the algorithm you outlined would have it request all versions and find the most
recent that matches the constraint. In order to make this efficient, it would
need to cache the result of the "all versions" request. This isn't something
that can be cached externally, since the external code has no knowledge of the
full set of versions downloaded.

[Bob Nystrom, 2012/06/21 00:12:18]

Ah, sorry. I see what you're getting at. I forgot I'd changed findVersion() to
just return one version.

Fixed.

+    // TODO(rnystrom): Do something better here.
+    throw "Source $name doesn't support versioning.";
+  }
+
+  /**
+   * Loads the (possibly remote) pubspec for the desired [version] of the named
+   * [package]. This will be called for packages that have not yet been
+   * installed during the version resolution process.
+   */
+  Future<Pubspec> describe(String package, Version version) {
+    // TODO(rnystrom): Figure out how non-default sources should handle this.
+    throw "Source $name doesn't support versioning.";
+  }
+
+  /**
    * Installs the package identified by [id] to [path]. Returns a [Future] that
    * completes when the installation was finished. The [Future] should resolve
    * to true if the package was found in the source and false if it wasn't. For