npm / node-semver / 310

100%

master: 100%

push

travis-ci

Reduce unnecessary Comparators in Range set

There are a few cases that lead to Range's Comparator sets being longer
than strictly necessary.  This reduces performance of methods that
iterate over ranges repeatedly (for example, `intersects` and `subset`),
and leads to some confusing toString output like turning `x || * || X`
into `||||` instead of `*`.

- If any simple range in the set contains the null set <0.0.0-0, then
  the entire simple range is the null set. `2.x <0.0.0-0` is the same as
  just `<0.0.0-0`.  (This is used for `>*` and `<*`, which cannot match
  anything.)
- Ensure that a given Comparator will only occur once within each simple
  range set.  `2.3.x ^2.3` doesn't need to include `>=2.3.0` more than
  once.
- If a simple range set contains more than one comparator, remove any `*`
  comparators.  `* >=2.3.4` is the same as just `>=2.3.4`.  This was
  already being done in the cast to a string, but some `ANY` Comparators
  would be left behind in the set used for matching.
- If a Range set contains the simple range `*`, then drop any other
  simple ranges in the set. `* || 2.x` is the same as `*`.

There's still some unnecessary comparators in there.  For example, the
range `2.3 ^2.3.4` parses to `>=2.3.0 <2.4.0-0 >=2.3.4 <3.0.0-0`.  Of
course, anything that is `<2.4.0-0` is also `<3.0.0-0`, and anything
that is `>=2.3.4` is also `>=2.3.0`, so the `<3.0.0-0` and `>=2.3.0`
Comparators are not necessary.  But simplifying those out would be a bit
more work.

To do that, we could walk the set of Comparators checking to see if they
are a subset of any other Comparators in the list, and if so, removing
them.  The subset check would not have to be a full Range.subset(); we
could just see if the gtlt points in the same direction, and if one
semver is greater than the other.  It's an O(n^2) operation, but one on
typically very small n.

714 of 714 branches covered (100.0%)

1014 of 1014 relevant lines covered (100.0%)

348.12 hits per line