-
-
Notifications
You must be signed in to change notification settings - Fork 76
/
Intervals.php
478 lines (417 loc) · 19.9 KB
/
Intervals.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
<?php
/*
* This file is part of composer/semver.
*
* (c) Composer <https://github.com/composer>
*
* For the full copyright and license information, please view
* the LICENSE file that was distributed with this source code.
*/
namespace Composer\Semver;
use Composer\Semver\Constraint\Constraint;
use Composer\Semver\Constraint\ConstraintInterface;
use Composer\Semver\Constraint\MatchAllConstraint;
use Composer\Semver\Constraint\MatchNoneConstraint;
use Composer\Semver\Constraint\MultiConstraint;
/**
* Helper class generating intervals from constraints
*
* This contains utilities for:
*
* - compacting an existing constraint which can be used to combine several into one
* by creating a MultiConstraint out of the many constraints you have.
*
* - checking whether one subset is a subset of another.
*
* Note: You should call clear to free memoization memory usage when you are done using this class
*/
class Intervals
{
/**
* @phpstan-var array<string, array{'numeric': Interval[], 'branches': array{'names': string[], 'exclude': bool}}>
*/
private static $intervalsCache = array();
/**
* @phpstan-var array<string, int>
*/
private static $opSortOrder = array(
'>=' => -3,
'<' => -2,
'>' => 2,
'<=' => 3,
);
/**
* Clears the memoization cache once you are done
*
* @return void
*/
public static function clear()
{
self::$intervalsCache = array();
}
/**
* Checks whether $candidate is a subset of $constraint
*
* @return bool
*/
public static function isSubsetOf(ConstraintInterface $candidate, ConstraintInterface $constraint)
{
if ($constraint instanceof MatchAllConstraint) {
return true;
}
if ($candidate instanceof MatchNoneConstraint || $constraint instanceof MatchNoneConstraint) {
return false;
}
$intersectionIntervals = self::get(new MultiConstraint(array($candidate, $constraint), true));
$candidateIntervals = self::get($candidate);
if (\count($intersectionIntervals['numeric']) !== \count($candidateIntervals['numeric'])) {
return false;
}
foreach ($intersectionIntervals['numeric'] as $index => $interval) {
if (!isset($candidateIntervals['numeric'][$index])) {
return false;
}
if ((string) $candidateIntervals['numeric'][$index]->getStart() !== (string) $interval->getStart()) {
return false;
}
if ((string) $candidateIntervals['numeric'][$index]->getEnd() !== (string) $interval->getEnd()) {
return false;
}
}
if ($intersectionIntervals['branches']['exclude'] !== $candidateIntervals['branches']['exclude']) {
return false;
}
if (\count($intersectionIntervals['branches']['names']) !== \count($candidateIntervals['branches']['names'])) {
return false;
}
foreach ($intersectionIntervals['branches']['names'] as $index => $name) {
if ($name !== $candidateIntervals['branches']['names'][$index]) {
return false;
}
}
return true;
}
/**
* Checks whether $a and $b have any intersection, equivalent to $a->matches($b)
*
* @return bool
*/
public static function haveIntersections(ConstraintInterface $a, ConstraintInterface $b)
{
if ($a instanceof MatchAllConstraint || $b instanceof MatchAllConstraint) {
return true;
}
if ($a instanceof MatchNoneConstraint || $b instanceof MatchNoneConstraint) {
return false;
}
$intersectionIntervals = self::generateIntervals(new MultiConstraint(array($a, $b), true), true);
return \count($intersectionIntervals['numeric']) > 0 || $intersectionIntervals['branches']['exclude'] || \count($intersectionIntervals['branches']['names']) > 0;
}
/**
* Attempts to optimize a MultiConstraint
*
* When merging MultiConstraints together they can get very large, this will
* compact it by looking at the real intervals covered by all the constraints
* and then creates a new constraint containing only the smallest amount of rules
* to match the same intervals.
*
* @return ConstraintInterface
*/
public static function compactConstraint(ConstraintInterface $constraint)
{
if (!$constraint instanceof MultiConstraint) {
return $constraint;
}
$intervals = self::generateIntervals($constraint);
$constraints = array();
$hasNumericMatchAll = false;
if (\count($intervals['numeric']) === 1 && (string) $intervals['numeric'][0]->getStart() === (string) Interval::fromZero() && (string) $intervals['numeric'][0]->getEnd() === (string) Interval::untilPositiveInfinity()) {
$constraints[] = $intervals['numeric'][0]->getStart();
$hasNumericMatchAll = true;
} else {
$unEqualConstraints = array();
for ($i = 0, $count = \count($intervals['numeric']); $i < $count; $i++) {
$interval = $intervals['numeric'][$i];
// if current interval ends with < N and next interval begins with > N we can swap this out for != N
// but this needs to happen as a conjunctive expression together with the start of the current interval
// and end of next interval, so [>=M, <N] || [>N, <P] => [>=M, !=N, <P] but M/P can be skipped if
// they are zero/+inf
if ($interval->getEnd()->getOperator() === '<' && $i+1 < $count) {
$nextInterval = $intervals['numeric'][$i+1];
if ($interval->getEnd()->getVersion() === $nextInterval->getStart()->getVersion() && $nextInterval->getStart()->getOperator() === '>') {
// only add a start if we didn't already do so, can be skipped if we're looking at second
// interval in [>=M, <N] || [>N, <P] || [>P, <Q] where unEqualConstraints currently contains
// [>=M, !=N] already and we only want to add !=P right now
if (\count($unEqualConstraints) === 0 && (string) $interval->getStart() !== (string) Interval::fromZero()) {
$unEqualConstraints[] = $interval->getStart();
}
$unEqualConstraints[] = new Constraint('!=', $interval->getEnd()->getVersion());
continue;
}
}
if (\count($unEqualConstraints) > 0) {
// this is where the end of the following interval of a != constraint is added as explained above
if ((string) $interval->getEnd() !== (string) Interval::untilPositiveInfinity()) {
$unEqualConstraints[] = $interval->getEnd();
}
// count is 1 if entire constraint is just one != expression
if (\count($unEqualConstraints) > 1) {
$constraints[] = new MultiConstraint($unEqualConstraints, true);
} else {
$constraints[] = $unEqualConstraints[0];
}
$unEqualConstraints = array();
continue;
}
// convert back >= x - <= x intervals to == x
if ($interval->getStart()->getVersion() === $interval->getEnd()->getVersion() && $interval->getStart()->getOperator() === '>=' && $interval->getEnd()->getOperator() === '<=') {
$constraints[] = new Constraint('==', $interval->getStart()->getVersion());
continue;
}
if ((string) $interval->getStart() === (string) Interval::fromZero()) {
$constraints[] = $interval->getEnd();
} elseif ((string) $interval->getEnd() === (string) Interval::untilPositiveInfinity()) {
$constraints[] = $interval->getStart();
} else {
$constraints[] = new MultiConstraint(array($interval->getStart(), $interval->getEnd()), true);
}
}
}
$devConstraints = array();
if (0 === \count($intervals['branches']['names'])) {
if ($intervals['branches']['exclude']) {
if ($hasNumericMatchAll) {
return new MatchAllConstraint;
}
// otherwise constraint should contain a != operator and already cover this
}
} else {
foreach ($intervals['branches']['names'] as $branchName) {
if ($intervals['branches']['exclude']) {
$devConstraints[] = new Constraint('!=', $branchName);
} else {
$devConstraints[] = new Constraint('==', $branchName);
}
}
// excluded branches, e.g. != dev-foo are conjunctive with the interval, so
// > 2.0 != dev-foo must return a conjunctive constraint
if ($intervals['branches']['exclude']) {
if (\count($constraints) > 1) {
return new MultiConstraint(array_merge(
array(new MultiConstraint($constraints, false)),
$devConstraints
), true);
}
if (\count($constraints) === 1 && (string)$constraints[0] === (string)Interval::fromZero()) {
if (\count($devConstraints) > 1) {
return new MultiConstraint($devConstraints, true);
}
return $devConstraints[0];
}
return new MultiConstraint(array_merge($constraints, $devConstraints), true);
}
// otherwise devConstraints contains a list of == operators for branches which are disjunctive with the
// rest of the constraint
$constraints = array_merge($constraints, $devConstraints);
}
if (\count($constraints) > 1) {
return new MultiConstraint($constraints, false);
}
if (\count($constraints) === 1) {
return $constraints[0];
}
return new MatchNoneConstraint;
}
/**
* Creates an array of numeric intervals and branch constraints representing a given constraint
*
* if the returned numeric array is empty it means the constraint matches nothing in the numeric range (0 - +inf)
* if the returned branches array is empty it means no dev-* versions are matched
* if a constraint matches all possible dev-* versions, branches will contain Interval::anyDev()
*
* @return array
* @phpstan-return array{'numeric': Interval[], 'branches': array{'names': string[], 'exclude': bool}}
*/
public static function get(ConstraintInterface $constraint)
{
$key = (string) $constraint;
if (!isset(self::$intervalsCache[$key])) {
self::$intervalsCache[$key] = self::generateIntervals($constraint);
}
return self::$intervalsCache[$key];
}
/**
* @param bool $stopOnFirstValidInterval
*
* @phpstan-return array{'numeric': Interval[], 'branches': array{'names': string[], 'exclude': bool}}
*/
private static function generateIntervals(ConstraintInterface $constraint, $stopOnFirstValidInterval = false)
{
if ($constraint instanceof MatchAllConstraint) {
return array('numeric' => array(new Interval(Interval::fromZero(), Interval::untilPositiveInfinity())), 'branches' => Interval::anyDev());
}
if ($constraint instanceof MatchNoneConstraint) {
return array('numeric' => array(), 'branches' => array('names' => array(), 'exclude' => false));
}
if ($constraint instanceof Constraint) {
return self::generateSingleConstraintIntervals($constraint);
}
if (!$constraint instanceof MultiConstraint) {
throw new \UnexpectedValueException('The constraint passed in should be an MatchAllConstraint, Constraint or MultiConstraint instance, got '.\get_class($constraint).'.');
}
$constraints = $constraint->getConstraints();
$numericGroups = array();
$constraintBranches = array();
foreach ($constraints as $c) {
$res = self::get($c);
$numericGroups[] = $res['numeric'];
$constraintBranches[] = $res['branches'];
}
if ($constraint->isDisjunctive()) {
$branches = Interval::noDev();
foreach ($constraintBranches as $b) {
if ($b['exclude']) {
if ($branches['exclude']) {
// disjunctive constraint, so only exclude what's excluded in all constraints
// !=a,!=b || !=b,!=c => !=b
$branches['names'] = array_intersect($branches['names'], $b['names']);
} else {
// disjunctive constraint so exclude all names which are not explicitly included in the alternative
// (==b || ==c) || !=a,!=b => !=a
$branches['exclude'] = true;
$branches['names'] = array_diff($b['names'], $branches['names']);
}
} else {
if ($branches['exclude']) {
// disjunctive constraint so exclude all names which are not explicitly included in the alternative
// !=a,!=b || (==b || ==c) => !=a
$branches['names'] = array_diff($branches['names'], $b['names']);
} else {
// disjunctive constraint, so just add all the other branches
// (==a || ==b) || ==c => ==a || ==b || ==c
$branches['names'] = array_merge($branches['names'], $b['names']);
}
}
}
} else {
$branches = Interval::anyDev();
foreach ($constraintBranches as $b) {
if ($b['exclude']) {
if ($branches['exclude']) {
// conjunctive, so just add all branch names to be excluded
// !=a && !=b => !=a,!=b
$branches['names'] = array_merge($branches['names'], $b['names']);
} else {
// conjunctive, so only keep included names which are not excluded
// (==a||==c) && !=a,!=b => ==c
$branches['names'] = array_diff($branches['names'], $b['names']);
}
} else {
if ($branches['exclude']) {
// conjunctive, so only keep included names which are not excluded
// !=a,!=b && (==a||==c) => ==c
$branches['names'] = array_diff($b['names'], $branches['names']);
$branches['exclude'] = false;
} else {
// conjunctive, so only keep names that are included in both
// (==a||==b) && (==a||==c) => ==a
$branches['names'] = array_intersect($branches['names'], $b['names']);
}
}
}
}
$branches['names'] = array_unique($branches['names']);
if (\count($numericGroups) === 1) {
return array('numeric' => $numericGroups[0], 'branches' => $branches);
}
$borders = array();
foreach ($numericGroups as $group) {
foreach ($group as $interval) {
$borders[] = array('version' => $interval->getStart()->getVersion(), 'operator' => $interval->getStart()->getOperator(), 'side' => 'start');
$borders[] = array('version' => $interval->getEnd()->getVersion(), 'operator' => $interval->getEnd()->getOperator(), 'side' => 'end');
}
}
$opSortOrder = self::$opSortOrder;
usort($borders, function ($a, $b) use ($opSortOrder) {
$order = version_compare($a['version'], $b['version']);
if ($order === 0) {
return $opSortOrder[$a['operator']] - $opSortOrder[$b['operator']];
}
return $order;
});
$activeIntervals = 0;
$intervals = array();
$index = 0;
$activationThreshold = $constraint->isConjunctive() ? \count($numericGroups) : 1;
$start = null;
foreach ($borders as $border) {
if ($border['side'] === 'start') {
$activeIntervals++;
} else {
$activeIntervals--;
}
if (!$start && $activeIntervals >= $activationThreshold) {
$start = new Constraint($border['operator'], $border['version']);
} elseif ($start && $activeIntervals < $activationThreshold) {
// filter out invalid intervals like > x - <= x, or >= x - < x
if (
version_compare($start->getVersion(), $border['version'], '=')
&& (
($start->getOperator() === '>' && $border['operator'] === '<=')
|| ($start->getOperator() === '>=' && $border['operator'] === '<')
)
) {
unset($intervals[$index]);
} else {
$intervals[$index] = new Interval($start, new Constraint($border['operator'], $border['version']));
$index++;
if ($stopOnFirstValidInterval) {
break;
}
}
$start = null;
}
}
return array('numeric' => $intervals, 'branches' => $branches);
}
/**
* @phpstan-return array{'numeric': Interval[], 'branches': array{'names': string[], 'exclude': bool}}
*/
private static function generateSingleConstraintIntervals(Constraint $constraint)
{
$op = $constraint->getOperator();
// handle branch constraints first
if (strpos($constraint->getVersion(), 'dev-') === 0) {
$intervals = array();
$branches = array('names' => array(), 'exclude' => false);
// != dev-foo means any numeric version may match, we treat >/< like != they are not really defined for branches
if ($op === '!=') {
$intervals[] = new Interval(Interval::fromZero(), Interval::untilPositiveInfinity());
$branches = array('names' => array($constraint->getVersion()), 'exclude' => true);
} elseif ($op === '==') {
$branches['names'][] = $constraint->getVersion();
}
return array(
'numeric' => $intervals,
'branches' => $branches,
);
}
if ($op[0] === '>') { // > & >=
return array('numeric' => array(new Interval($constraint, Interval::untilPositiveInfinity())), 'branches' => Interval::noDev());
}
if ($op[0] === '<') { // < & <=
return array('numeric' => array(new Interval(Interval::fromZero(), $constraint)), 'branches' => Interval::noDev());
}
if ($op === '!=') {
// convert !=x to intervals of 0 - <x && >x - +inf + dev*
return array('numeric' => array(
new Interval(Interval::fromZero(), new Constraint('<', $constraint->getVersion())),
new Interval(new Constraint('>', $constraint->getVersion()), Interval::untilPositiveInfinity()),
), 'branches' => Interval::anyDev());
}
// convert ==x to an interval of >=x - <=x
return array('numeric' => array(
new Interval(new Constraint('>=', $constraint->getVersion()), new Constraint('<=', $constraint->getVersion())),
), 'branches' => Interval::noDev());
}
}