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..bf638bc5e464f6cf47594e45d83f6eb9b7def32f 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 : const _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,176 @@ 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 : const _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.
+      if (intersectMin == intersectMax) {
+        // If both ends are inclusive, allow that version.
+        if (intersectIncludeMin && intersectIncludeMax) return intersectMin;
+
+        // Otherwise, no versions.
+        return const _EmptyVersion();
+      }
+
+      if (intersectMin != null && intersectMax != null &&
+          intersectMin > intersectMax) {
+        // Non-overlapping ranges, so empty.
+        return const _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');
+    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>';
+}
+
+class _VersionConstraintFactory {
+  factory VersionConstraint.empty() => const _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) {
+    var constraint = new VersionRange();
+    for (var other in constraints) {
+      constraint = constraint.intersect(other);
+    }
+    return constraint;
+  }
+
+  static VersionConstraint parseSingleConstraint(String text) {
+    if (text == 'any') {
+      return new VersionRange();
+    }
+
+    // TODO(rnystrom): Consider other syntaxes for version constraints. This
+    // one is whitespace sensitive (you can't do "< 1.2.3") and "<" is
+    // unfortunately meaningful in YAML, requiring it to be quoted in a
+    // pubspec.
+    // See if it's a comparison operator followed by a version, like ">1.2.3".
+    var match = const RegExp(@"^([<>]=?)?(.*)$").firstMatch(text);
+    if (match != null) {
+      var comparison = match[1];
+      var version = new Version.parse(match[2]);
+      switch (match[1]) {
+        case '<=': return new VersionRange(max: version, includeMax: true);
+        case '<': return new VersionRange(max: version, includeMax: false);
+        case '>=': return new VersionRange(min: version, includeMin: true);
+        case '>': return new VersionRange(min: version, includeMin: false);
+      }
+    }
+
+    // Otherwise, it must be an explicit version.
+    return new Version.parse(text);
+  }
 }