First pass at version constraint solver.

utils/pub/version.dart

Index: utils/pub/version.dart
diff --git a/utils/pub/version.dart b/utils/pub/version.dart
index ee5aca0cc461c22d4feddf28a8214299bf8bf124..114fa0c3c04a314bdb8374fc72e07f4e2519e244 100644
--- a/utils/pub/version.dart
+++ b/utils/pub/version.dart
@@ -13,7 +13,8 @@
 
 /** A parsed semantic version number. */
 class Version implements Comparable, Hashable, VersionConstraint {
-  static get none() => new Version(0, 0, 0);
+  /** No released version: i.e. "0.0.0". */
+  static Version get none() => new Version(0, 0, 0);
 
   static final _PARSE_REGEX = const RegExp(
       @'^'                                        // Start at beginning.
@@ -71,7 +72,7 @@ class Version implements Comparable, Hashable, VersionConstraint {
     }
   }
 
-  bool operator ==(Version other) {
+  bool operator ==(other) {
     if (other is! Version) return false;
     return compareTo(other) == 0;
   }
@@ -81,9 +82,24 @@ class Version implements Comparable, Hashable, VersionConstraint {
   bool operator <=(Version other) => compareTo(other) <= 0;
   bool operator >=(Version other) => compareTo(other) >= 0;
 
+  bool get isEmpty() => false;
+
   /** Tests if [other] matches this version exactly. */
   bool allows(Version other) => this == other;
 
+  VersionConstraint intersect(VersionConstraint other) {
+    if (other.isEmpty) return other;
+
+    // Intersect a version and a range.
+    if (other is VersionRange) return other.intersect(this);
+
+    // Intersecting two versions only works if they are the same.
+    if (other is Version) return this == other ? this : _emptyVersion;
+
+    throw new IllegalArgumentException(
+        'Unknown VersionConstraint type $other.');
+  }
+
   int compareTo(Version other) {
     if (major != other.major) return major.compareTo(other.major);
     if (minor != other.minor) return minor.compareTo(other.minor);
@@ -179,8 +195,52 @@ class Version implements Comparable, Hashable, VersionConstraint {
  * version that is "2.0.0" or greater. Version objects themselves implement
  * this to match a specific version.
  */
-interface VersionConstraint {
+interface VersionConstraint default _VersionConstraintFactory {
+  /**
+   * A [VersionConstraint] that allows no versions: i.e. the empty set.
+   */
+  VersionConstraint.empty();
+
+  /**
+   * Parses a version constraint. This string is a space-separated series of
+   * version parts. Each part can be one of:
+   *
+   *   * A version string like `1.2.3`. In other words, anything that can be
+   *     parsed by [Version.parse()].
+   *   * A comparison operator (`<`, `>`, `<=`, or `>=`) followed by a version
+   *     string. There cannot be a space between the operator and the version.
+   *
+   * Examples:
+   *
+   *     1.2.3-alpha
+   *     <=5.1.4
+   *     >2.0.4 <=2.4.6
+   */
+  VersionConstraint.parse(String text);
+
+  /**
+   * Creates a new version constraint that is the intersection of [constraints].
+   * It will only allow versions that all of those constraints allow. If
+   * constraints is empty, then it returns a VersionConstraint that allows all
+   * versions.
+   */
+  VersionConstraint.intersect(Collection<VersionConstraint> constraints);
+
+  /**
+   * Returns `true` if this constraint allows no versions.
+   */
+  bool get isEmpty();
+
+  /**
+   * Returns `true` if this constraint allows [version].
+   */
   bool allows(Version version);
+
+  /**
+   * Creates a new [VersionConstraint] that only allows [Version]s allowed by
+   * both this and [other].
+   */
+  VersionConstraint intersect(VersionConstraint other);
 }
 
 /**
@@ -192,18 +252,184 @@ interface VersionConstraint {
 class VersionRange implements VersionConstraint {
   final Version min;
   final Version max;
+  final bool includeMin;
+  final bool includeMax;
 
-  VersionRange([this.min, this.max]) {
+  VersionRange([this.min, this.max,
+      this.includeMin = false, this.includeMax = false]) {
     if (min != null && max != null && min > max) {
       throw new IllegalArgumentException(
-          'Maximum version ("$max") must be less than minimum ("$min").');
+          'Minimum version ("$min") must be less than maximum ("$max").');
     }
   }
 
+  bool operator ==(other) {
+    if (other is! VersionRange) return false;
+
+    return min == other.min &&
+           max == other.max &&
+           includeMin == other.includeMin &&
+           includeMax == other.includeMax;
+  }
+
+  bool get isEmpty() => false;
+
   /** Tests if [other] matches falls within this version range. */
   bool allows(Version other) {
     if (min != null && other < min) return false;
-    if (max != null && other >= max) return false;
+    if (min != null && !includeMin && other == min) return false;
+    if (max != null && other > max) return false;
+    if (max != null && !includeMax && other == max) return false;
     return true;
   }
+
+  VersionConstraint intersect(VersionConstraint other) {
+    if (other.isEmpty) return other;
+
+    // A range and a Version just yields the version if it's in the range.
+    if (other is Version) return allows(other) ? other : _emptyVersion;
+
+    if (other is VersionRange) {
+      // Intersect the two ranges.
+      var intersectMin = min;
+      var intersectIncludeMin = includeMin;
+      var intersectMax = max;
+      var intersectIncludeMax = includeMax;
+
+      if (other.min == null) {
+        // Do nothing.
+      } else if (intersectMin == null || intersectMin < other.min) {
+        intersectMin = other.min;
+        intersectIncludeMin = other.includeMin;
+      } else if (intersectMin == other.min && !other.includeMin) {
+        // The edges are the same, but one is exclusive, make it exclusive.
+        intersectIncludeMin = false;
+      }
+
+      if (other.max == null) {
+        // Do nothing.
+      } else if (intersectMax == null || intersectMax > other.max) {
+        intersectMax = other.max;
+        intersectIncludeMax = other.includeMax;
+      } else if (intersectMax == other.max && !other.includeMax) {
+        // The edges are the same, but one is exclusive, make it exclusive.
+        intersectIncludeMax = false;
+      }
+
+      if (intersectMin == null && intersectMax == null) {
+        // Open range.
+        return new VersionRange();
+      }
+
+      // If the range is just a single version.

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

There are other cases where it could just be a single version. For example:

intersectMin = 0.0.1
intersectMax = 0.0.2
intersectIncludeMin = true
intersectIncludeMax = false

intersectMin = 0.0.1
intersectMax = 0.0.3
intersectIncludeMin = false
intersectIncludeMax = false

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

That can still have other versions, like: 0.0.1+hotfix1
Ditto: 0.0.2-alpha, 0.0.2-beta, 0.0.2+patch1, etc. Given prerelease and build
suffixes, version numbers are essentially points on the real number line, I
believe.

You can think of it as a three digit floating point number where the digits to
the left of the decimal point are base infinity, and the digits (of which there
are can be arbitrarily many) to the right are base 256 ASCII. :)

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

Good point.

+      if (intersectMin == intersectMax) {
+        // If both ends are inclusive, allow that version.
+        if (intersectIncludeMin && intersectIncludeMax) return intersectMin;
+
+        // Otherwise, no versions.
+        return _emptyVersion;
+      }
+
+      if (intersectMin != null && intersectMax != null &&
+          intersectMin > intersectMax) {
+        // Non-overlapping ranges, so empty.
+        return _emptyVersion;
+      }
+
+      // If we got here, there is an actual range.
+      return new VersionRange(intersectMin, intersectMax,
+          intersectIncludeMin, intersectIncludeMax);
+    }
+
+    throw new IllegalArgumentException(
+        'Unknown VersionConstraint type $other.');
+  }
+
+  String toString() {
+    var buffer = new StringBuffer();
+
+    if (min != null) {
+      buffer.add(includeMin ? '>=' : '>');
+      buffer.add(min);
+    }
+
+    if (max != null) {
+      if (min != null) buffer.add(' ');
+      buffer.add(includeMax ? '<=' : '<');
+      buffer.add(max);
+    }
+
+    if (min == null && max == null) buffer.add('any');

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

We should only print this if we parse "any" as allowing any version.

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

Done. Added parse support for it. That should make pubspecs a bit nicer too:

dependencies:
  foo: any

+    return buffer.toString();
+  }
+}
+
+class _EmptyVersion implements VersionConstraint {
+  const _EmptyVersion();
+
+  bool get isEmpty() => true;
+  bool allows(Version other) => false;
+  VersionConstraint intersect(VersionConstraint other) => this;
+  String toString() => '<empty>';
+}
+
+final _emptyVersion = const _EmptyVersion();

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

Why is this necessary? Can't const automatically canonicalize values?

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

Done.

+
+class _VersionConstraintFactory {
+  factory VersionConstraint.empty() => _emptyVersion;
+
+  factory VersionConstraint.parse(String text) {
+    if (text.trim() == '') {
+      throw new FormatException('Cannot parse an empty string.');
+    }
+
+    // Split it into space-separated parts.
+    var constraints = <VersionConstraint>[];
+    for (var part in text.split(' ')) {
+      constraints.add(parseSingleConstraint(part));
+    }
+
+    return new VersionConstraint.intersect(constraints);
+  }
+
+  factory VersionConstraint.intersect(Collection<VersionConstraint> constraints) {

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

Line length.

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

Done.

+    var constraint = new VersionRange();
+    for (var other in constraints) {
+      constraint = constraint.intersect(other);
+    }
+    return constraint;
+  }
+
+  static VersionConstraint parseSingleConstraint(String text) {
+    // TODO(rnystrom): Consider other syntaxes for version constraints. This
+    // one is whitespace sensitive (you can't do "< 1.2.3") and "<" is

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

I'm coming around on quoting constraints in general, but I definitely don't
think we should disallow "< 1.2.3". It wouldn't be too hard to have it be
space-separated and still allow that.

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

Agreed, this is too finicky, but is it OK to be simple for this patch?

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

Yes, definitely.

+    // unfortunately meaningful in YAML, requiring it to be quoted in a
+    // pubspec.
+    if (text.startsWith('<=')) {

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

I think you could save some repetition here by parsing this with a regular
expression. E.g.:

var match = const RegExp(r"^([<>]=?)?(.*)$").firstMatch(text);
var operator = match[1];
var version = match[2];

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

Done. Good call.

+      // A maximum version (inclusive).
+      var version = new Version.parse(text.substring('<='.length));
+      return new VersionRange(max: version, includeMax: true);
+    }
+
+    if (text.startsWith('<')) {
+      // A maximum version (exclusive).
+      var version = new Version.parse(text.substring('<'.length));
+      return new VersionRange(max: version, includeMax: false);
+    }
+
+    if (text.startsWith('>=')) {
+      // A minimum version (inclusive).
+      var version = new Version.parse(text.substring('>='.length));
+      return new VersionRange(min: version, includeMin: true);
+    }
+
+    if (text.startsWith('>')) {
+      // A minimum version (exclusive).
+      var version = new Version.parse(text.substring('>'.length));
+      return new VersionRange(min: version, includeMin: false);
+    }
+
+    // Otherwise, it must be an explicit version.
+    return new Version.parse(text);
+  }
 }