Add more set-like version constraint operations.

lib/src/version_union.dart

Index: lib/src/version_union.dart
diff --git a/lib/src/version_union.dart b/lib/src/version_union.dart
new file mode 100644
index 0000000000000000000000000000000000000000..8ced188fc97831cb50bff6f5d7ece1081d467932
--- /dev/null
+++ b/lib/src/version_union.dart
@@ -0,0 +1,186 @@
+// Copyright (c) 2015, 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_semver.src.version_union;
+
+import 'dart:collection';
+
+import 'package:collection/collection.dart';
+
+import 'utils.dart';
+import 'version.dart';
+import 'version_constraint.dart';
+import 'version_range.dart';
+
+/// A (package-private) version constraint representing a union of multiple
+/// disjoint version constraints.
+///
+/// An instance of this will only be created if the version can't be represented
+/// as a non-compound value.
+class VersionUnion implements VersionConstraint {
+  /// The constraints that compose this union.
+  ///
+  /// This list has several invariants:
+  ///
+  /// * It contains only [Version]s and [VersionRange]s.
+  /// * Its contents are sorted from lowest to highest matched versions.
+  /// * Its contents are disjoint and non-adjacent. In other words, for any two
+  ///   constraints next to each other in the list, there's some version between
+  ///   those constraints that they don't match.
+  final List<VersionConstraint> constraints;
+
+  bool get isEmpty => false;
+
+  bool get isAny => false;
+
+  /// Returns the union of [constraints].
+  ///
+  /// This ensures that an actual [VersionUnion] is only returned if necessary.
+  /// It also takes care of sorting and merging the constraints to ensure that
+  /// they're disjoint.
+  static VersionConstraint create(Iterable<VersionConstraint> constraints) {
+    constraints = constraints.expand((constraint) {

[Bob Nystrom, 2015/05/05 20:49:09]

Instead of reassigning, how about:

var flattened = ...

[nweiz, 2015/05/05 22:52:34]

Done.

+      if (constraint.isEmpty) return [];
+      if (constraint is VersionUnion) return constraint.constraints;
+      return [constraint];
+    }).toList();
+
+    if (constraints.isEmpty) return VersionConstraint.empty;
+
+    if (constraints.any((constraint) => constraint.isAny)) {
+      return VersionConstraint.any;
+    }
+
+    // Only allow Versions and VersionRanges here so we can more easily reason
+    // about everything in [constraints]. _EmptyVersions and VersionUnions are
+    // filtered out above.
+    for (var constraint in constraints) {
+      if (constraint is Version || constraint is VersionRange) continue;
+      throw new ArgumentError('Unknown VersionConstraint type $constraint.');
+    }
+
+    (constraints as List).sort(compareMax);
+
+    var merged = [];
+    for (var constraint in constraints) {

[Bob Nystrom, 2015/05/05 20:49:09]

// If this constraint doesn't touch the previous one.

[nweiz, 2015/05/05 22:52:34]

Done.

+      if (merged.isEmpty ||
+          (!merged.last.allowsAny(constraint) &&
+              !areAdjacent(merged.last, constraint))) {
+        merged.add(constraint);
+      } else {
+        merged[merged.length - 1] = merged.last.union(constraint);
+      }
+    }
+
+    if (merged.length == 1) return merged.single;
+    return new VersionUnion._(merged);
+  }
+
+  VersionUnion._(List<VersionConstraint> constraints)
+      : constraints = new UnmodifiableListView(constraints);

[Bob Nystrom, 2015/05/05 20:49:09]

If this is a package private class, is this worth doing?

[nweiz, 2015/05/05 22:52:34]

Probably not. Removed.

+
+  bool allows(Version version) =>
+      constraints.any((constraint) => constraint.allows(version));
+
+  bool allowsAll(VersionConstraint other) {
+    var ourConstraints = constraints.iterator;
+    var theirConstraints = _constraintsFor(other).iterator;
+
+    // Because both lists of constraints are ordered by minimum version, we can
+    // safely move through them linearly here.
+    ourConstraints.moveNext();
+    theirConstraints.moveNext();
+    while (ourConstraints.current != null && theirConstraints.current != null) {

[Bob Nystrom, 2015/05/05 20:49:09]

Checking for .current == null feels sketchy to me. I know null should never be a
value in the list, but it still feels like the return value of .moveNext() is a
clearer indication of end-of-sequence to me.

Either way, this is a pretty neat algorithm. :)

[nweiz, 2015/05/05 22:52:34]

I don't think there's a clean way to do that. Even if we do "while (true)" and
break in the body, it handles the original calls to moveNext() much less
gracefully.

+      if (ourConstraints.current.allowsAll(theirConstraints.current)) {
+        theirConstraints.moveNext();
+      } else {
+        ourConstraints.moveNext();
+      }
+    }
+
+    // If our constraints have allowed all of their constraints, we'll have
+    // consumed all of them.
+    return theirConstraints.current == null;
+  }
+
+  bool allowsAny(VersionConstraint other) {
+    var ourConstraints = constraints.iterator;
+    var theirConstraints = _constraintsFor(other).iterator;
+
+    // Because both lists of constraints are ordered by minimum version, we can
+    // safely move through them linearly here.
+    ourConstraints.moveNext();
+    theirConstraints.moveNext();
+    while (ourConstraints.current != null && theirConstraints.current != null) {
+      if (ourConstraints.current.allowsAny(theirConstraints.current)) {
+        return true;
+      }
+
+      // Move the constraint with the higher max value forward. This ensures
+      // that we keep both lists in sync as much as possible.
+      if (compareMax(ourConstraints.current, theirConstraints.current) < 0) {
+        ourConstraints.moveNext();
+      } else {
+        theirConstraints.moveNext();
+      }
+    }
+
+    return false;
+  }
+
+  VersionConstraint intersect(VersionConstraint other) {
+    var ourConstraints = constraints.iterator;
+    var theirConstraints = _constraintsFor(other).iterator;
+
+    // Because both lists of constraints are ordered by minimum version, we can
+    // safely move through them linearly here.
+    var newConstraints = [];
+    ourConstraints.moveNext();
+    theirConstraints.moveNext();
+    while (ourConstraints.current != null && theirConstraints.current != null) {
+      var intersection = ourConstraints.current
+          .intersect(theirConstraints.current);
+
+      if (!intersection.isEmpty) newConstraints.add(intersection);
+
+      // Move the constraint with the higher max value forward. This ensures
+      // that we keep both lists in sync as much as possible, and that large
+      // constraints have a change to match multiple small constraints that they

[Bob Nystrom, 2015/05/05 20:49:09]

"change" -> "chance".

[nweiz, 2015/05/05 22:52:34]

Done.

+      // contain.
+      if (compareMax(ourConstraints.current, theirConstraints.current) < 0) {
+        ourConstraints.moveNext();
+      } else {
+        theirConstraints.moveNext();
+      }
+    }
+
+    if (newConstraints.isEmpty) return VersionConstraint.empty;
+    if (newConstraints.length == 1) return newConstraints.single;
+
+    return new VersionUnion._(newConstraints);
+  }
+
+  /// Returns [constraint] as a list of constraints.
+  ///
+  /// This is used to normalize constraints of various types.
+  List<VersionConstraint> _constraintsFor(VersionConstraint constraint) {

[Bob Nystrom, 2015/05/05 20:49:09]

Make this a function?

[nweiz, 2015/05/05 22:52:34]

What do you mean?

[Bob Nystrom, 2015/05/06 17:30:58]

It's an instance method here, but it doesn't access any fields. You could just
hoist it out to a top level function to make that clear.

[nweiz, 2015/05/06 18:18:58]

We don't typically do this for private methods in classes, even those that don't
access state.

My feeling is that it's more valuable to be able to easily change a method to
make it use state than it is to clearly signal that it currently doesn't.

+    if (constraint.isEmpty) return [];
+    if (constraint is VersionUnion) return constraint.constraints;
+    if (constraint is Version) return [constraint];
+    if (constraint is VersionRange) return [constraint];
+    throw new ArgumentError('Unknown VersionConstraint type $constraint.');
+  }
+
+  VersionConstraint union(VersionConstraint other) =>
+      new VersionConstraint.unionOf([this, other]);
+
+  bool operator ==(other) {
+    if (other is! VersionUnion) return false;
+    return const ListEquality().equals(constraints, other.constraints);
+  }
+
+  int get hashCode => const ListEquality().hash(constraints);
+
+  String toString() => constraints.join(" or ");
+}