Add VersionConstraint.difference().
See dart-lang/pub#912
R=rnystrom@google.com
Review URL: https://codereview.chromium.org//2045803002 .
diff --git a/CHANGELOG.md b/CHANGELOG.md
index cf95427..db3d320 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -4,6 +4,9 @@
implement `new VersionConstraint.unionOf()` and `VersionConstraint.union()`.
Now it's public so you can use it too.
+* Added `VersionConstraint.difference()`. This returns a constraint matching all
+ versions matched by one constraint but not another.
+
* Make `VersionRange` implement `Comparable<VersionRange>`. Ranges are ordered
first by lower bound, then by upper bound.
diff --git a/lib/src/utils.dart b/lib/src/utils.dart
index 6493dda..efe105a 100644
--- a/lib/src/utils.dart
+++ b/lib/src/utils.dart
@@ -13,17 +13,46 @@
(!range1.includeMax && range2.includeMin);
}
-/// A [Comparator] that compares the maximum versions of [range1] and [range2].
-int compareMax(VersionRange range1, VersionRange range2) {
- if (range1.max == null) {
- if (range2.max == null) return 0;
- return 1;
- } else if (range2.max == null) {
- return -1;
- }
+/// Returns whether [range1] allows lower versions than [range2].
+bool allowsLower(VersionRange range1, VersionRange range2) {
+ if (range1.min == null) return range2.min != null;
+ if (range2.min == null) return false;
- var result = range1.max.compareTo(range2.max);
- if (result != 0) return result;
- if (range1.includeMax != range2.includeMax) return range1.includeMax ? 1 : -1;
- return 0;
+ var comparison = range1.min.compareTo(range2.min);
+ if (comparison == -1) return true;
+ if (comparison == 1) return false;
+ return range1.includeMin && !range2.includeMin;
+}
+
+/// Returns whether [range1] allows higher versions than [range2].
+bool allowsHigher(VersionRange range1, VersionRange range2) {
+ if (range1.max == null) return range2.max != null;
+ if (range2.max == null) return false;
+
+ var comparison = range1.max.compareTo(range2.max);
+ if (comparison == 1) return true;
+ if (comparison == -1) return false;
+ return range1.includeMax && !range2.includeMax;
+}
+
+/// Returns whether [range1] allows only versions lower than those allowed by
+/// [range2].
+bool strictlyLower(VersionRange range1, VersionRange range2) {
+ if (range1.max == null || range2.min == null) return false;
+
+ var comparison = range1.max.compareTo(range2.min);
+ if (comparison == -1) return true;
+ if (comparison == 1) return false;
+ return !range1.includeMax || !range2.includeMin;
+}
+
+/// Returns whether [range1] allows only versions higher than those allowed by
+/// [range2].
+bool strictlyHigher(VersionRange range1, VersionRange range2) {
+ if (range1.min == null || range2.max == null) return false;
+
+ var comparison = range1.min.compareTo(range2.max);
+ if (comparison == 1) return true;
+ if (comparison == -1) return false;
+ return !range1.includeMin || !range2.includeMax;
}
diff --git a/lib/src/version.dart b/lib/src/version.dart
index f2662b9..2d43a1a 100644
--- a/lib/src/version.dart
+++ b/lib/src/version.dart
@@ -267,6 +267,9 @@
return new VersionConstraint.unionOf([this, other]);
}
+ VersionConstraint difference(VersionConstraint other) =>
+ other.allows(this) ? VersionConstraint.empty : this;
+
int compareTo(VersionRange other) {
if (other is Version) {
if (major != other.major) return major.compareTo(other.major);
diff --git a/lib/src/version_constraint.dart b/lib/src/version_constraint.dart
index 68827a4..edd8abd 100644
--- a/lib/src/version_constraint.dart
+++ b/lib/src/version_constraint.dart
@@ -229,13 +229,17 @@
/// allows.
bool allowsAny(VersionConstraint other);
- /// Creates a new [VersionConstraint] that only allows [Version]s allowed by
- /// both this and [other].
+ /// Returns a [VersionConstraint] that only allows [Version]s allowed by both
+ /// this and [other].
VersionConstraint intersect(VersionConstraint other);
- /// Creates a new [VersionConstraint] that allows [Versions]s allowed by
- /// either this or [other].
+ /// Returns a [VersionConstraint] that allows [Versions]s allowed by either
+ /// this or [other].
VersionConstraint union(VersionConstraint other);
+
+ /// Returns a [VersionConstraint] that allows [Version]s allowed by this but
+ /// not [other].
+ VersionConstraint difference(VersionConstraint other);
}
class _EmptyVersion implements VersionConstraint {
@@ -248,6 +252,7 @@
bool allowsAny(VersionConstraint other) => false;
VersionConstraint intersect(VersionConstraint other) => this;
VersionConstraint union(VersionConstraint other) => other;
+ VersionConstraint difference(VersionConstraint other) => this;
String toString() => '<empty>';
}
diff --git a/lib/src/version_range.dart b/lib/src/version_range.dart
index a8d6069..ffa50ab 100644
--- a/lib/src/version_range.dart
+++ b/lib/src/version_range.dart
@@ -160,37 +160,7 @@
}
if (other is VersionRange) {
- // If neither range has a minimum, they'll overlap at some point.
- //
- // ... this ]
- // ... other ]
- if (min == null && other.min == null) return true;
-
- // If this range has a lower minimum than the other range, it overlaps as
- // long as its maximum is higher than or the same as the other range's
- // minimum.
- //
- // [ this ] [ this ]
- // [ other ] [ other ]
- if (min == null || (other.min != null && min < other.min)) {
- if (max == null) return true;
- if (max > other.min) return true;
- if (max < other.min) return false;
- assert(max == other.min);
- return includeMax && other.includeMin;
- }
-
- // If this range has a higher minimum than the other range, it overlaps as
- // long as its minimum is lower than or the same as the other range's
- // maximum.
- //
- // [ this ] [ this ]
- // [ other ] [ other ]
- if (other.max == null) return true;
- if (min < other.max) return true;
- if (min > other.max) return false;
- assert(min == other.max);
- return includeMin && other.includeMax;
+ return !strictlyLower(other, this) && !strictlyHigher(other, this);
}
throw new ArgumentError('Unknown VersionConstraint type $other.');
@@ -320,9 +290,100 @@
return new VersionConstraint.unionOf([this, other]);
}
+ VersionConstraint difference(VersionConstraint other) {
+ if (other.isEmpty) return this;
+
+ if (other is Version) {
+ if (!allows(other)) return this;
+
+ if (other == min) {
+ if (!includeMin) return this;
+ return new VersionRange(
+ min: min, max: max,
+ includeMin: false, includeMax: includeMax);
+ }
+
+ if (other == max) {
+ if (!includeMax) return this;
+ return new VersionRange(
+ min: min, max: max,
+ includeMin: includeMin, includeMax: false);
+ }
+
+ return new VersionUnion.fromRanges([
+ new VersionRange(
+ min: min, max: other,
+ includeMin: includeMin, includeMax: false),
+ new VersionRange(
+ min: other, max: max,
+ includeMin: false, includeMax: includeMax)
+ ]);
+ } else if (other is VersionRange) {
+ if (!allowsAny(other)) return this;
+
+ VersionConstraint before;
+ if (!allowsLower(this, other)) {
+ before = VersionConstraint.empty;
+ } else if (min == other.min) {
+ assert(includeMin && !other.includeMin);
+ assert(min != null);
+ before = min;
+ } else {
+ before = new VersionRange(
+ min: min, max: other.min,
+ includeMin: includeMin, includeMax: !other.includeMin);
+ }
+
+ VersionConstraint after;
+ if (!allowsHigher(this, other)) {
+ after = VersionConstraint.empty;
+ } else if (max == other.max) {
+ assert(includeMax && !other.includeMax);
+ assert(max != null);
+ after = max;
+ } else {
+ after = new VersionRange(
+ min: other.max, max: max,
+ includeMin: !other.includeMax, includeMax: includeMax);
+ }
+
+ if (before == VersionConstraint.empty) return after;
+ if (after == VersionConstraint.empty) return before;
+ return new VersionUnion.fromRanges([before, after]);
+ } else if (other is VersionUnion) {
+ var ranges = <VersionRange>[];
+ var current = this;
+
+ for (var range in other.ranges) {
+ // Skip any ranges that are strictly lower than [current].
+ if (strictlyLower(range, current)) continue;
+
+ // If we reach a range strictly higher than [current], no more ranges
+ // will be relevant so we can bail early.
+ if (strictlyHigher(range, current)) break;
+
+ var difference = current.difference(range);
+ if (difference is VersionUnion) {
+ // If [range] split [current] in half, we only need to continue
+ // checking future ranges against the latter half.
+ assert(difference.ranges.length == 2);
+ ranges.add(difference.ranges.first);
+ current = difference.ranges.last;
+ } else {
+ current = difference as VersionRange;
+ }
+ }
+
+ if (ranges.isEmpty) return current;
+ return new VersionUnion.fromRanges(ranges..add(current));
+ }
+
+ throw new ArgumentError('Unknown VersionConstraint type $other.');
+ }
+
int compareTo(VersionRange other) {
if (min == null) {
- if (other.min == null) return compareMax(this, other);
+ if (other.min == null) return _compareMax(other);
return -1;
} else if (other.min == null) {
return 1;
@@ -332,7 +393,22 @@
if (result != 0) return result;
if (includeMin != other.includeMin) return includeMin ? -1 : 1;
- return compareMax(this, other);
+ return _compareMax(other);
+ }
+
+ /// Compares the maximum values of [this] and [other].
+ int _compareMax(VersionRange other) {
+ if (max == null) {
+ if (other.max == null) return 0;
+ return 1;
+ } else if (other.max == null) {
+ return -1;
+ }
+
+ var result = max.compareTo(other.max);
+ if (result != 0) return result;
+ if (includeMax != other.includeMax) return includeMax ? 1 : -1;
+ return 0;
}
String toString() {
diff --git a/lib/src/version_union.dart b/lib/src/version_union.dart
index d0e1e2b..a26cb52 100644
--- a/lib/src/version_union.dart
+++ b/lib/src/version_union.dart
@@ -76,7 +76,7 @@
// Move the constraint with the lower max value forward. This ensures that
// we keep both lists in sync as much as possible.
- if (compareMax(ourRanges.current, theirRanges.current) < 0) {
+ if (allowsHigher(theirRanges.current, ourRanges.current)) {
ourRanges.moveNext();
} else {
theirRanges.moveNext();
@@ -104,7 +104,7 @@
// Move the constraint with the lower max value forward. This ensures that
// we keep both lists in sync as much as possible, and that large ranges
// have a chance to match multiple small ranges that they contain.
- if (compareMax(ourRanges.current, theirRanges.current) < 0) {
+ if (allowsHigher(theirRanges.current, ourRanges.current)) {
ourRanges.moveNext();
} else {
theirRanges.moveNext();
@@ -117,6 +117,80 @@
return new VersionUnion.fromRanges(newRanges);
}
+ VersionConstraint difference(VersionConstraint other) {
+ var ourRanges = ranges.iterator;
+ var theirRanges = _rangesFor(other).iterator;
+
+ var newRanges = <VersionRange>[];
+ ourRanges.moveNext();
+ theirRanges.moveNext();
+ var current = ourRanges.current;
+
+ theirNextRange() {
+ if (theirRanges.moveNext()) return true;
+
+ // If there are no more of their ranges, none of the rest of our ranges
+ // need to be subtracted so we can add them as-is.
+ newRanges.add(current);
+ while (ourRanges.moveNext()) {
+ newRanges.add(ourRanges.current);
+ }
+ return false;
+ }
+
+ ourNextRange({bool includeCurrent: true}) {
+ if (includeCurrent) newRanges.add(current);
+ if (!ourRanges.moveNext()) return false;
+ current = ourRanges.current;
+ return true;
+ }
+
+ while (true) {
+ // If the current ranges are disjoint, move the lowest one forward.
+ if (strictlyLower(theirRanges.current, current)) {
+ if (!theirNextRange()) break;
+ continue;
+ }
+
+ if (strictlyHigher(theirRanges.current, current)) {
+ if (!ourNextRange()) break;
+ continue;
+ }
+
+ // If we're here, we know [theirRanges.current] overlaps [current].
+ var difference = current.difference(theirRanges.current);
+ if (difference is VersionUnion) {
+ // If their range split [current] in half, we only need to continue
+ // checking future ranges against the latter half.
+ assert(difference.ranges.length == 2);
+ newRanges.add(difference.ranges.first);
+ current = difference.ranges.last;
+
+ // Since their range split [current], it definitely doesn't allow higher
+ // versions, so we should move their ranges forward.
+ if (!theirNextRange()) break;
+ } else if (difference.isEmpty) {
+ if (!ourNextRange(includeCurrent: false)) break;
+ } else {
+ current = difference as VersionRange;
+
+ // Move the constraint with the lower max value forward. This ensures
+ // that we keep both lists in sync as much as possible, and that large
+ // ranges have a chance to subtract or be subtracted by multiple small
+ // ranges that they contain.
+ if (allowsHigher(current, theirRanges.current)) {
+ if (!theirNextRange()) break;
+ } else {
+ if (!ourNextRange()) break;
+ }
+ }
+ }
+
+ if (newRanges.isEmpty) return VersionConstraint.empty;
+ if (newRanges.length == 1) return newRanges.single;
+ return new VersionUnion.fromRanges(newRanges);
+ }
+
/// Returns [constraint] as a list of ranges.
///
/// This is used to normalize ranges of various types.
diff --git a/pubspec.yaml b/pubspec.yaml
index 53ef4d3..531ace6 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: pub_semver
-version: 1.3.0-dev
+version: 1.3.0
author: Dart Team <misc@dartlang.org>
description: >
Versions and version constraints implementing pub's versioning policy. This
diff --git a/test/version_range_test.dart b/test/version_range_test.dart
index eaa473f..a2dbf98 100644
--- a/test/version_range_test.dart
+++ b/test/version_range_test.dart
@@ -340,8 +340,8 @@
});
test('adjacent ranges allow no versions if exclusive', () {
- var a = new VersionRange(min: v114, max: v124, includeMax: false);
- var b = new VersionRange(min: v124, max: v200, includeMin: true);
+ var a = new VersionRange(min: v114, max: v124);
+ var b = new VersionRange(min: v124, max: v200);
expect(a.intersect(b).isEmpty, isTrue);
});
@@ -441,6 +441,164 @@
});
});
+ group('difference()', () {
+ test("with an empty range returns the original range", () {
+ expect(
+ new VersionRange(min: v003, max: v114)
+ .difference(VersionConstraint.empty),
+ equals(new VersionRange(min: v003, max: v114)));
+ });
+
+ test("with a version outside the range returns the original range", () {
+ expect(
+ new VersionRange(min: v003, max: v114).difference(v200),
+ equals(new VersionRange(min: v003, max: v114)));
+ });
+
+ test("with a version in the range splits the range", () {
+ expect(
+ new VersionRange(min: v003, max: v114).difference(v072),
+ equals(new VersionConstraint.unionOf([
+ new VersionRange(min: v003, max: v072),
+ new VersionRange(min: v072, max: v114)
+ ])));
+ });
+
+ test("with the max version makes the max exclusive", () {
+ expect(
+ new VersionRange(min: v003, max: v114, includeMax: true)
+ .difference(v114),
+ equals(new VersionRange(min: v003, max: v114)));
+ });
+
+ test("with the min version makes the min exclusive", () {
+ expect(
+ new VersionRange(min: v003, max: v114, includeMin: true)
+ .difference(v003),
+ equals(new VersionRange(min: v003, max: v114)));
+ });
+
+ test("with a disjoint range returns the original", () {
+ expect(
+ new VersionRange(min: v003, max: v114)
+ .difference(new VersionRange(min: v123, max: v140)),
+ equals(new VersionRange(min: v003, max: v114)));
+ });
+
+ test("with an adjacent range returns the original", () {
+ expect(
+ new VersionRange(min: v003, max: v114, includeMax: true)
+ .difference(new VersionRange(min: v114, max: v140)),
+ equals(new VersionRange(min: v003, max: v114, includeMax: true)));
+ });
+
+ test("with a range at the beginning cuts off the beginning of the range",
+ () {
+ expect(
+ new VersionRange(min: v080, max: v130)
+ .difference(new VersionRange(min: v010, max: v114)),
+ equals(new VersionRange(min: v114, max: v130, includeMin: true)));
+ expect(
+ new VersionRange(min: v080, max: v130)
+ .difference(new VersionRange(max: v114)),
+ equals(new VersionRange(min: v114, max: v130, includeMin: true)));
+ expect(
+ new VersionRange(min: v080, max: v130).difference(
+ new VersionRange(min: v010, max: v114, includeMax: true)),
+ equals(new VersionRange(min: v114, max: v130)));
+ expect(
+ new VersionRange(min: v080, max: v130, includeMin: true).difference(
+ new VersionRange(min: v010, max: v080, includeMax: true)),
+ equals(new VersionRange(min: v080, max: v130)));
+ expect(
+ new VersionRange(min: v080, max: v130, includeMax: true)
+ .difference(new VersionRange(min: v080, max: v130)),
+ equals(v130));
+ });
+
+ test("with a range at the end cuts off the end of the range",
+ () {
+ expect(
+ new VersionRange(min: v080, max: v130)
+ .difference(new VersionRange(min: v114, max: v140)),
+ equals(new VersionRange(min: v080, max: v114, includeMax: true)));
+ expect(
+ new VersionRange(min: v080, max: v130)
+ .difference(new VersionRange(min: v114)),
+ equals(new VersionRange(min: v080, max: v114, includeMax: true)));
+ expect(
+ new VersionRange(min: v080, max: v130).difference(
+ new VersionRange(min: v114, max: v140, includeMin: true)),
+ equals(new VersionRange(min: v080, max: v114)));
+ expect(
+ new VersionRange(min: v080, max: v130, includeMax: true).difference(
+ new VersionRange(min: v130, max: v140, includeMin: true)),
+ equals(new VersionRange(min: v080, max: v130)));
+ expect(
+ new VersionRange(min: v080, max: v130, includeMin: true)
+ .difference(new VersionRange(min: v080, max: v130)),
+ equals(v080));
+ });
+
+ test("with a range in the middle cuts the range in half", () {
+ expect(
+ new VersionRange(min: v003, max: v130)
+ .difference(new VersionRange(min: v072, max: v114)),
+ equals(new VersionConstraint.unionOf([
+ new VersionRange(min: v003, max: v072, includeMax: true),
+ new VersionRange(min: v114, max: v130, includeMin: true)
+ ])));
+ });
+
+ test("with a totally covering range returns empty", () {
+ expect(
+ new VersionRange(min: v114, max: v200)
+ .difference(new VersionRange(min: v072, max: v300)),
+ isEmpty);
+ expect(
+ new VersionRange(min: v003, max: v114)
+ .difference(new VersionRange(min: v003, max: v114)),
+ isEmpty);
+ expect(
+ new VersionRange(
+ min: v003, max: v114, includeMin: true, includeMax: true)
+ .difference(new VersionRange(
+ min: v003, max: v114, includeMin: true, includeMax: true)),
+ isEmpty);
+ });
+
+ test("with a version union that doesn't cover the range, returns the "
+ "original", () {
+ expect(
+ new VersionRange(min: v114, max: v140)
+ .difference(new VersionConstraint.unionOf([v010, v200])),
+ equals(new VersionRange(min: v114, max: v140)));
+ });
+
+ test("with a version union that intersects the ends, chops them off", () {
+ expect(
+ new VersionRange(min: v114, max: v140)
+ .difference(new VersionConstraint.unionOf([
+ new VersionRange(min: v080, max: v123),
+ new VersionRange(min: v130, max: v200)
+ ])),
+ equals(new VersionRange(
+ min: v123, max: v130, includeMin: true, includeMax: true)));
+ });
+
+ test("with a version union that intersects the middle, chops it up", () {
+ expect(
+ new VersionRange(min: v114, max: v140)
+ .difference(new VersionConstraint.unionOf([v123, v124, v130])),
+ equals(new VersionConstraint.unionOf([
+ new VersionRange(min: v114, max: v123),
+ new VersionRange(min: v123, max: v124),
+ new VersionRange(min: v124, max: v130),
+ new VersionRange(min: v130, max: v140)
+ ])));
+ });
+ });
+
test('isEmpty', () {
expect(new VersionRange().isEmpty, isFalse);
expect(new VersionRange(min: v123, max: v124).isEmpty, isFalse);
diff --git a/test/version_test.dart b/test/version_test.dart
index ddc6c94..b278d4c 100644
--- a/test/version_test.dart
+++ b/test/version_test.dart
@@ -202,6 +202,27 @@
});
});
+ group('difference()', () {
+ test("with the same version returns an empty constraint", () {
+ expect(v123.difference(v123), isEmpty);
+ });
+
+ test("with a different version returns the original version", () {
+ expect(v123.difference(v080), equals(v123));
+ });
+
+ test("returns an empty constraint with a range that contains the version",
+ () {
+ expect(v123.difference(new VersionRange(min: v114, max: v124)), isEmpty);
+ });
+
+ test("returns the version constraint with a range that doesn't contain it",
+ () {
+ expect(v123.difference(new VersionRange(min: v140, max: v300)),
+ equals(v123));
+ });
+ });
+
test('isEmpty', () {
expect(v123.isEmpty, isFalse);
});
diff --git a/test/version_union_test.dart b/test/version_union_test.dart
index f3518a0..06a427d 100644
--- a/test/version_union_test.dart
+++ b/test/version_union_test.dart
@@ -349,4 +349,62 @@
});
});
});
+
+ group("difference()", () {
+ test("ignores ranges that don't intersect", () {
+ expect(new VersionConstraint.unionOf([
+ new VersionRange(min: v072, max: v080),
+ new VersionRange(min: v123, max: v130)
+ ]).difference(new VersionConstraint.unionOf([
+ new VersionRange(min: v003, max: v010),
+ new VersionRange(min: v080, max: v123),
+ new VersionRange(min: v140)
+ ])), equals(new VersionConstraint.unionOf([
+ new VersionRange(min: v072, max: v080),
+ new VersionRange(min: v123, max: v130)
+ ])));
+ });
+
+ test("removes overlapping portions", () {
+ expect(new VersionConstraint.unionOf([
+ new VersionRange(min: v010, max: v080),
+ new VersionRange(min: v123, max: v130)
+ ]).difference(new VersionConstraint.unionOf([
+ new VersionRange(min: v003, max: v072),
+ new VersionRange(min: v124)
+ ])), equals(new VersionConstraint.unionOf([
+ new VersionRange(min: v072, max: v080, includeMin: true),
+ new VersionRange(min: v123, max: v124, includeMax: true)
+ ])));
+ });
+
+ test("removes multiple portions from the same range", () {
+ expect(new VersionConstraint.unionOf([
+ new VersionRange(min: v010, max: v114),
+ new VersionRange(min: v130, max: v200)
+ ]).difference(new VersionConstraint.unionOf([v072, v080])),
+ equals(new VersionConstraint.unionOf([
+ new VersionRange(min: v010, max: v072),
+ new VersionRange(min: v072, max: v080),
+ new VersionRange(min: v080, max: v114),
+ new VersionRange(min: v130, max: v200)
+ ])));
+ });
+
+ test("removes the same range from multiple ranges", () {
+ expect(new VersionConstraint.unionOf([
+ new VersionRange(min: v010, max: v072),
+ new VersionRange(min: v080, max: v123),
+ new VersionRange(min: v124, max: v130),
+ new VersionRange(min: v200, max: v234),
+ new VersionRange(min: v250, max: v300)
+ ]).difference(new VersionRange(min: v114, max: v201)),
+ equals(new VersionConstraint.unionOf([
+ new VersionRange(min: v010, max: v072),
+ new VersionRange(min: v080, max: v114, includeMax: true),
+ new VersionRange(min: v201, max: v234, includeMin: true),
+ new VersionRange(min: v250, max: v300)
+ ])));
+ });
+ });
}
\ No newline at end of file
