1
|
|
|
<?php |
2
|
|
|
/** |
3
|
|
|
* (c) Steve Nebes <[email protected]> |
4
|
|
|
* |
5
|
|
|
* For the full copyright and license information, please view the LICENSE |
6
|
|
|
* file that was distributed with this source code. |
7
|
|
|
*/ |
8
|
|
|
|
9
|
|
|
declare(strict_types=1); |
10
|
|
|
|
11
|
|
|
namespace SN\DaisyDiff\RangeDifferencer; |
12
|
|
|
|
13
|
|
|
use SN\DaisyDiff\RangeDifferencer\Core\LCSSettings; |
14
|
|
|
|
15
|
|
|
/** |
16
|
|
|
* A RangeDifferencer finds the differences between two or three RangeComparatorInterfaces. |
17
|
|
|
* |
18
|
|
|
* To use the differencer, clients provide an RangeComparatorInterface that breaks their input data into a sequence of |
19
|
|
|
* comparable entities. The differencer returns the differences among these sequences as an array of RangeDifference |
20
|
|
|
* objects (findDifferences methods). Every RangeDifference represents a single kind of difference and the corresponding |
21
|
|
|
* ranges of the underlying comparable entities in the left, right, and optionally ancestor sides. |
22
|
|
|
* |
23
|
|
|
* Alternatively, the findRanges methods not only return objects for the differing ranges but for non-differing ranges |
24
|
|
|
* too. |
25
|
|
|
* |
26
|
|
|
* The algorithm used is an objectified version of one described in: A File Comparison Program, by Webb Miller and |
27
|
|
|
* Eugene W. Myers, Software Practice and Experience, Vol. 15, Nov. 1985. |
28
|
|
|
*/ |
29
|
|
|
final class RangeDifferencer |
30
|
|
|
{ |
31
|
|
|
/** |
32
|
|
|
* Prevent class instantiation. |
33
|
|
|
* |
34
|
|
|
* @codeCoverageIgnore |
35
|
|
|
*/ |
36
|
|
|
private function __construct() |
37
|
|
|
{ |
38
|
|
|
} |
39
|
|
|
|
40
|
|
|
/** |
41
|
|
|
* Finds the differences between two RangeComparatorInterfaces. The differences are returned as an array of |
42
|
|
|
* RangeDifferences. If no differences are detected an empty array is returned. |
43
|
|
|
* |
44
|
|
|
* @param RangeComparatorInterface $left |
45
|
|
|
* @param RangeComparatorInterface $right |
46
|
|
|
* @param LCSSettings $settings |
47
|
|
|
* @return RangeDifference[] |
48
|
|
|
*/ |
49
|
39 |
|
public static function findDifferences( |
50
|
|
|
RangeComparatorInterface $left, |
51
|
|
|
RangeComparatorInterface $right, |
52
|
|
|
?LCSSettings $settings = null |
53
|
|
|
): array { |
54
|
39 |
|
if (null === $settings) { |
55
|
23 |
|
$settings = new LCSSettings(); |
56
|
|
|
} |
57
|
|
|
|
58
|
39 |
|
if (!$settings->isUseGreedyMethod()) { |
59
|
30 |
|
return OldDifferencer::findDifferences($left, $right); |
60
|
|
|
} |
61
|
|
|
|
62
|
9 |
|
return RangeComparatorLCS::findDifferences($left, $right, $settings); |
63
|
|
|
} |
64
|
|
|
|
65
|
|
|
/** |
66
|
|
|
* Finds the differences among three RangeComparatorInterfaces. The differences are returned as a list of |
67
|
|
|
* RangeDifferences. If no differences are detected an empty list is returned. If the ancestor range comparator is |
68
|
|
|
* null, a two-way comparison is performed. |
69
|
|
|
* |
70
|
|
|
* @param RangeComparatorInterface $ancestor |
71
|
|
|
* @param RangeComparatorInterface $left |
72
|
|
|
* @param RangeComparatorInterface $right |
73
|
|
|
* @param LCSSettings $settings |
74
|
|
|
* @return RangeDifference[] |
75
|
|
|
*/ |
76
|
2 |
|
public static function findDifferences3( |
77
|
|
|
RangeComparatorInterface $ancestor, |
78
|
|
|
RangeComparatorInterface $left, |
79
|
|
|
RangeComparatorInterface $right, |
80
|
|
|
?LCSSettings $settings = null |
81
|
|
|
): array { |
82
|
2 |
|
$leftAncestorScript = null; |
83
|
2 |
|
$rightAncestorScript = self::findDifferences($ancestor, $right, $settings); |
84
|
|
|
|
85
|
2 |
|
if (!empty($rightAncestorScript)) { |
86
|
2 |
|
$leftAncestorScript = self::findDifferences($ancestor, $left, $settings); |
87
|
|
|
} |
88
|
|
|
|
89
|
2 |
|
if (empty($leftAncestorScript) || empty($rightAncestorScript)) { |
90
|
|
|
return []; |
91
|
|
|
} |
92
|
|
|
|
93
|
2 |
|
$myIter = new DifferencesIterator($rightAncestorScript); |
94
|
2 |
|
$yourIter = new DifferencesIterator($leftAncestorScript); |
95
|
|
|
|
96
|
|
|
// Prime array with a sentinel. |
97
|
2 |
|
$diff3 = []; |
98
|
2 |
|
$diff3[] = new RangeDifference(RangeDifference::ERROR); |
99
|
|
|
|
100
|
|
|
// Combine the two-way edit scripts into one. |
101
|
2 |
|
while (null !== $myIter->getDifference() || null !== $yourIter->getDifference()) { |
102
|
2 |
|
$myIter->removeAll(); |
103
|
2 |
|
$yourIter->removeAll(); |
104
|
|
|
|
105
|
|
|
// Take the next diff that is closer to the start. |
106
|
2 |
|
if (null === $myIter->getDifference()) { |
107
|
|
|
$startThread = $yourIter; |
108
|
2 |
|
} elseif (null === $yourIter->getDifference()) { |
109
|
|
|
$startThread = $myIter; |
110
|
|
|
} else { |
111
|
|
|
// Not at end of both scripts take the lowest range. |
112
|
2 |
|
if ($myIter->getDifference()->getLeftStart() <= $yourIter->getDifference()->getLeftStart()) { |
113
|
2 |
|
$startThread = $myIter; |
114
|
|
|
} else { |
115
|
|
|
$startThread = $yourIter; |
116
|
|
|
} |
117
|
|
|
} |
118
|
|
|
|
119
|
2 |
|
$changeRangeStart = $startThread->getDifference()->getLeftStart(); |
120
|
2 |
|
$changeRangeEnd = $startThread->getDifference()->getLeftEnd(); |
121
|
2 |
|
$startThread->next(); |
122
|
|
|
|
123
|
|
|
// Check for overlapping changes with other thread merge overlapping changes with this range. |
124
|
2 |
|
$other = $startThread->other($myIter, $yourIter); |
125
|
|
|
|
126
|
2 |
|
while (null !== $other->getDifference() && $other->getDifference()->getLeftStart() <= $changeRangeEnd) { |
127
|
2 |
|
$newMax = $other->getDifference()->getLeftEnd(); |
128
|
2 |
|
$other->next(); |
129
|
|
|
|
130
|
2 |
|
if ($newMax >= $changeRangeEnd) { |
131
|
2 |
|
$changeRangeEnd = $newMax; |
132
|
2 |
|
$other = $other->other($myIter, $yourIter); |
133
|
|
|
} |
134
|
|
|
} |
135
|
|
|
|
136
|
2 |
|
$diff3[] = self::createRangeDifference3( |
137
|
2 |
|
$myIter, $yourIter, $diff3, |
138
|
2 |
|
$right, $left, |
139
|
2 |
|
$changeRangeStart, $changeRangeEnd); |
140
|
|
|
} |
141
|
|
|
|
142
|
|
|
// Remove sentinel, the first item in the array. |
143
|
2 |
|
\array_shift($diff3); |
144
|
|
|
|
145
|
2 |
|
return $diff3; |
146
|
|
|
} |
147
|
|
|
|
148
|
|
|
/** |
149
|
|
|
* @param RangeComparatorInterface $left |
150
|
|
|
* @param RangeComparatorInterface $right |
151
|
|
|
* @param LCSSettings|null $settings |
152
|
|
|
* @return RangeDifference[] |
153
|
|
|
*/ |
154
|
3 |
|
public static function findRanges( |
155
|
|
|
RangeComparatorInterface $left, |
156
|
|
|
RangeComparatorInterface $right, |
157
|
|
|
?LCSSettings $settings = null |
158
|
|
|
): array { |
159
|
3 |
|
$in = self::findDifferences($left, $right, $settings); |
160
|
3 |
|
$out = []; |
161
|
|
|
|
162
|
3 |
|
$mStart = 0; |
163
|
3 |
|
$yStart = 0; |
164
|
|
|
|
165
|
3 |
|
for ($i = 0, $iMax = \count($in); $i < $iMax; $i++) { |
166
|
3 |
|
$es = $in[$i]; |
167
|
3 |
|
$rd = new RangeDifference(RangeDifference::NOCHANGE, |
168
|
3 |
|
$mStart, $es->getRightStart() - $mStart, |
169
|
3 |
|
$yStart, $es->getLeftStart() - $yStart); |
170
|
|
|
|
171
|
3 |
|
if ($rd->getMaxLength() !== 0) { |
172
|
3 |
|
$out[] = $rd; |
173
|
|
|
} |
174
|
|
|
|
175
|
3 |
|
$out[] = $es; |
176
|
|
|
|
177
|
3 |
|
$mStart = $es->getRightEnd(); |
178
|
3 |
|
$yStart = $es->getLeftEnd(); |
179
|
|
|
} |
180
|
|
|
|
181
|
3 |
|
$rd = new RangeDifference(RangeDifference::NOCHANGE, |
182
|
3 |
|
$mStart, $right->getRangeCount() - $mStart, |
183
|
3 |
|
$yStart, $left->getRangeCount() - $yStart); |
184
|
|
|
|
185
|
3 |
|
if ($rd->getMaxLength() > 0) { |
186
|
3 |
|
$out[] = $rd; |
187
|
|
|
} |
188
|
|
|
|
189
|
3 |
|
return $out; |
190
|
|
|
} |
191
|
|
|
|
192
|
|
|
/** |
193
|
|
|
* @param RangeComparatorInterface $ancestor |
194
|
|
|
* @param RangeComparatorInterface $left |
195
|
|
|
* @param RangeComparatorInterface $right |
196
|
|
|
* @param LCSSettings|null $settings |
197
|
|
|
* @return RangeDifference[] |
198
|
|
|
*/ |
199
|
1 |
|
public static function findRanges3( |
200
|
|
|
RangeComparatorInterface $ancestor, |
201
|
|
|
RangeComparatorInterface $left, |
202
|
|
|
RangeComparatorInterface $right, |
203
|
|
|
?LCSSettings $settings = null |
204
|
|
|
): array { |
205
|
1 |
|
$in = self::findDifferences3($ancestor, $left, $right, $settings); |
206
|
1 |
|
$out = []; |
207
|
|
|
|
208
|
1 |
|
$mStart = 0; |
209
|
1 |
|
$yStart = 0; |
210
|
1 |
|
$aStart = 0; |
211
|
|
|
|
212
|
1 |
|
for ($i = 0, $iMax = \count($in); $i < $iMax; $i++) { |
213
|
1 |
|
$es = $in[$i]; |
214
|
1 |
|
$rd = new RangeDifference(RangeDifference::NOCHANGE, |
215
|
1 |
|
$mStart, $es->getRightStart() - $mStart, |
216
|
1 |
|
$yStart, $es->getLeftStart() - $yStart, |
217
|
1 |
|
$aStart, $es->getAncestorStart() - $aStart); |
218
|
|
|
|
219
|
1 |
|
if ($rd->getMaxLength() > 0) { |
220
|
1 |
|
$out[] = $rd; |
221
|
|
|
} |
222
|
|
|
|
223
|
1 |
|
$out[] = $es; |
224
|
|
|
|
225
|
1 |
|
$mStart = $es->getRightEnd(); |
226
|
1 |
|
$yStart = $es->getLeftEnd(); |
227
|
1 |
|
$aStart = $es->getAncestorEnd(); |
228
|
|
|
} |
229
|
|
|
|
230
|
1 |
|
$rd = new RangeDifference(RangeDifference::NOCHANGE, |
231
|
1 |
|
$mStart, $right->getRangeCount() - $mStart, |
232
|
1 |
|
$yStart, $left->getRangeCount() - $yStart, |
233
|
1 |
|
$aStart, $ancestor->getRangeCount() - $aStart); |
234
|
|
|
|
235
|
1 |
|
if ($rd->getMaxLength() > 0) { |
236
|
1 |
|
$out[] = $rd; |
237
|
|
|
} |
238
|
|
|
|
239
|
1 |
|
return $out; |
240
|
|
|
} |
241
|
|
|
|
242
|
|
|
/** |
243
|
|
|
* @param DifferencesIterator $myIter |
244
|
|
|
* @param DifferencesIterator $yourIter |
245
|
|
|
* @param array $diff3 |
246
|
|
|
* @param RangeComparatorInterface $right |
247
|
|
|
* @param RangeComparatorInterface $left |
248
|
|
|
* @param int $changeRangeStart |
249
|
|
|
* @param int $changeRangeEnd |
250
|
|
|
* @return RangeDifference |
251
|
|
|
*/ |
252
|
2 |
|
private static function createRangeDifference3( |
253
|
|
|
DifferencesIterator $myIter, |
254
|
|
|
DifferencesIterator $yourIter, |
255
|
|
|
array &$diff3, |
256
|
|
|
RangeComparatorInterface $right, |
257
|
|
|
RangeComparatorInterface $left, |
258
|
|
|
int $changeRangeStart = 0, |
259
|
|
|
int $changeRangeEnd = 0 |
260
|
|
|
): RangeDifference { |
261
|
2 |
|
$kind = RangeDifference::ERROR; |
262
|
|
|
|
263
|
|
|
/** @var RangeDifference $last */ |
264
|
2 |
|
$last = $diff3[\count($diff3) - 1]; |
265
|
|
|
|
266
|
|
|
// At least one range array must be non-empty. |
267
|
2 |
|
\assert($myIter->getCount() > 0 || $yourIter->getCount() > 0); |
268
|
|
|
|
269
|
|
|
// Find corresponding lines to fChangeRangeStart/End in right and left. |
270
|
2 |
|
if (0 === $myIter->getCount()) { |
271
|
|
|
// Only left changed. |
272
|
|
|
$rightStart = $changeRangeStart - $last->getAncestorEnd() + $last->getRightEnd(); |
273
|
|
|
$rightEnd = $changeRangeEnd - $last->getAncestorEnd() + $last->getRightEnd(); |
274
|
|
|
$kind = RangeDifference::LEFT; |
275
|
|
|
} else { |
276
|
|
|
/** @var RangeDifference[] $range */ |
277
|
2 |
|
$range = $myIter->getRange(); |
278
|
2 |
|
$f = $range[0]; |
279
|
2 |
|
$l = $range[\count($range) - 1]; |
280
|
2 |
|
$rightStart = $changeRangeStart - $f->getLeftStart() + $f->getRightStart(); |
281
|
2 |
|
$rightEnd = $changeRangeEnd - $l->getLeftEnd() + $l->getRightEnd(); |
282
|
|
|
} |
283
|
|
|
|
284
|
2 |
|
if (0 === $yourIter->getCount()) { |
285
|
|
|
// Only right changed. |
286
|
|
|
$leftStart = $changeRangeStart - $last->getAncestorEnd() + $last->getLeftEnd(); |
287
|
|
|
$leftEnd = $changeRangeEnd - $last->getAncestorEnd() + $last->getLeftEnd(); |
288
|
|
|
$kind = RangeDifference::RIGHT; |
289
|
|
|
} else { |
290
|
|
|
/** @var RangeDifference[] $range */ |
291
|
2 |
|
$range = $yourIter->getRange(); |
292
|
2 |
|
$f = $range[0]; |
293
|
2 |
|
$l = $range[\count($range) - 1]; |
294
|
2 |
|
$leftStart = $changeRangeStart - $f->getLeftStart() + $f->getRightStart(); |
295
|
2 |
|
$leftEnd = $changeRangeEnd - $l->getLeftEnd() + $l->getRightEnd(); |
296
|
|
|
} |
297
|
|
|
|
298
|
2 |
|
if (RangeDifference::ERROR === $kind) { |
299
|
|
|
// Overlapping change (conflict). |
300
|
2 |
|
if (self::rangeSpansEqual( |
301
|
2 |
|
$right, $rightStart, $rightEnd - $rightStart, $left, $leftStart, $leftEnd - $leftStart)) { |
302
|
|
|
$kind = RangeDifference::ANCESTOR; |
303
|
|
|
} else { |
304
|
2 |
|
$kind = RangeDifference::CONFLICT; |
305
|
|
|
} |
306
|
|
|
} |
307
|
|
|
|
308
|
2 |
|
return new RangeDifference( |
309
|
2 |
|
$kind, |
310
|
2 |
|
$rightStart, $rightEnd - $rightStart, |
311
|
2 |
|
$leftStart, $leftEnd - $leftStart, |
312
|
2 |
|
$changeRangeStart, $changeRangeEnd - $changeRangeStart); |
313
|
|
|
} |
314
|
|
|
|
315
|
|
|
/** |
316
|
|
|
* @param RangeComparatorInterface $right |
317
|
|
|
* @param int $rightStart |
318
|
|
|
* @param int $rightLen |
319
|
|
|
* @param RangeComparatorInterface $left |
320
|
|
|
* @param int $leftStart |
321
|
|
|
* @param int $leftLen |
322
|
|
|
* @return bool |
323
|
|
|
*/ |
324
|
2 |
|
private static function rangeSpansEqual( |
325
|
|
|
RangeComparatorInterface $right, |
326
|
|
|
int $rightStart, |
327
|
|
|
int $rightLen, |
328
|
|
|
RangeComparatorInterface $left, |
329
|
|
|
int $leftStart, |
330
|
|
|
int $leftLen |
331
|
|
|
): bool { |
332
|
2 |
|
if ($rightLen === $leftLen) { |
333
|
|
|
for ($i = 0; $i < $rightLen; $i++) { |
334
|
|
|
if (!self::rangesEqual($right, $rightStart + $i, $left, $leftStart + $i)) { |
335
|
|
|
break; |
336
|
|
|
} |
337
|
|
|
} |
338
|
|
|
|
339
|
|
|
if ($i === $rightLen) { |
340
|
|
|
return true; |
341
|
|
|
} |
342
|
|
|
} |
343
|
|
|
|
344
|
2 |
|
return false; |
345
|
|
|
} |
346
|
|
|
|
347
|
|
|
/** |
348
|
|
|
* @param RangeComparatorInterface $a |
349
|
|
|
* @param int $ai |
350
|
|
|
* @param RangeComparatorInterface $b |
351
|
|
|
* @param int $bi |
352
|
|
|
* @return bool |
353
|
|
|
*/ |
354
|
|
|
private static function rangesEqual( |
355
|
|
|
RangeComparatorInterface $a, |
356
|
|
|
int $ai, |
357
|
|
|
RangeComparatorInterface $b, |
358
|
|
|
int $bi |
359
|
|
|
): bool { |
360
|
|
|
return $a->rangesEqual($ai, $b, $bi); |
361
|
|
|
} |
362
|
|
|
} |
363
|
|
|
|