Add VersionConstraint.difference(). See dart-lang/pubdart-lang/pub_semver#912 R=rnystrom@google.com Review URL: https://codereview.chromium.org//2045803002 .
diff --git a/pkgs/pub_semver/CHANGELOG.md b/pkgs/pub_semver/CHANGELOG.md index cf95427..db3d320 100644 --- a/pkgs/pub_semver/CHANGELOG.md +++ b/pkgs/pub_semver/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/pkgs/pub_semver/lib/src/utils.dart b/pkgs/pub_semver/lib/src/utils.dart index 6493dda..efe105a 100644 --- a/pkgs/pub_semver/lib/src/utils.dart +++ b/pkgs/pub_semver/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/pkgs/pub_semver/lib/src/version.dart b/pkgs/pub_semver/lib/src/version.dart index f2662b9..2d43a1a 100644 --- a/pkgs/pub_semver/lib/src/version.dart +++ b/pkgs/pub_semver/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/pkgs/pub_semver/lib/src/version_constraint.dart b/pkgs/pub_semver/lib/src/version_constraint.dart index 68827a4..edd8abd 100644 --- a/pkgs/pub_semver/lib/src/version_constraint.dart +++ b/pkgs/pub_semver/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/pkgs/pub_semver/lib/src/version_range.dart b/pkgs/pub_semver/lib/src/version_range.dart index a8d6069..ffa50ab 100644 --- a/pkgs/pub_semver/lib/src/version_range.dart +++ b/pkgs/pub_semver/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/pkgs/pub_semver/lib/src/version_union.dart b/pkgs/pub_semver/lib/src/version_union.dart index d0e1e2b..a26cb52 100644 --- a/pkgs/pub_semver/lib/src/version_union.dart +++ b/pkgs/pub_semver/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/pkgs/pub_semver/pubspec.yaml b/pkgs/pub_semver/pubspec.yaml index 53ef4d3..531ace6 100644 --- a/pkgs/pub_semver/pubspec.yaml +++ b/pkgs/pub_semver/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/pkgs/pub_semver/test/version_range_test.dart b/pkgs/pub_semver/test/version_range_test.dart index eaa473f..a2dbf98 100644 --- a/pkgs/pub_semver/test/version_range_test.dart +++ b/pkgs/pub_semver/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/pkgs/pub_semver/test/version_test.dart b/pkgs/pub_semver/test/version_test.dart index ddc6c94..b278d4c 100644 --- a/pkgs/pub_semver/test/version_test.dart +++ b/pkgs/pub_semver/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/pkgs/pub_semver/test/version_union_test.dart b/pkgs/pub_semver/test/version_union_test.dart index f3518a0..06a427d 100644 --- a/pkgs/pub_semver/test/version_union_test.dart +++ b/pkgs/pub_semver/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