Debian Codegraph @

vendor/jfcherng/php-diff/src/Differ.php

raw
1 <?php
2
3 declare(strict_types=1);
4
5 namespace Jfcherng\Diff;
6
7 use Jfcherng\Diff\Utility\Arr;
8
9 /**
10 * A comprehensive library for generating differences between two strings
11 * in multiple formats (unified, side by side HTML etc).
12 *
13 * @author Jack Cherng <[email protected]>
14 * @author Chris Boulton <[email protected]>
15 *
16 * @see http://github.com/chrisboulton/php-diff
17 */
18 final class Differ
19 {
20 /**
21 * @var int a safe number for indicating showing all contexts
22 */
23 public const CONTEXT_ALL = \PHP_INT_MAX >> 3;
24
25 /**
26 * @var string used to indicate a line has no EOL
27 *
28 * Arbitrary chars from the 15-16th Unicode reserved areas
29 * and hopefully, they won't appear in source texts
30 */
31 public const LINE_NO_EOL = "\u{fcf28}\u{fc231}";
32
33 /**
34 * @var array cached properties and their default values
35 */
36 private const CACHED_PROPERTIES = [
37 'groupedOpcodes' => [],
38 'groupedOpcodesGnu' => [],
39 'oldNoEolAtEofIdx' => -1,
40 'newNoEolAtEofIdx' => -1,
41 'oldNewComparison' => 0,
42 ];
43
44 /**
45 * @var array array of the options that have been applied for generating the diff
46 */
47 public array $options = [];
48
49 /**
50 * @var string[] the old sequence
51 */
52 private array $old = [];
53
54 /**
55 * @var string[] the new sequence
56 */
57 private array $new = [];
58
59 /**
60 * @var bool is any of cached properties dirty?
61 */
62 private bool $isCacheDirty = true;
63
64 /**
65 * @var SequenceMatcher the sequence matcher
66 */
67 private SequenceMatcher $sequenceMatcher;
68
69 private int $oldSrcLength = 0;
70
71 private int $newSrcLength = 0;
72
73 /**
74 * @var int the end index for the old if the old has no EOL at EOF
75 * `-1` means the old has an EOL at EOF
76 */
77 private int $oldNoEolAtEofIdx = -1;
78
79 /**
80 * @var int the end index for the new if the new has no EOL at EOF
81 * `-1` means the new has an EOL at EOF
82 */
83 private int $newNoEolAtEofIdx = -1;
84
85 /**
86 * @var int the result of comparing the old and the new with the spaceship operator
87 * `-1` means `old < new`, `0` means `old == new`, `1` means `old > new`
88 */
89 private int $oldNewComparison = 0;
90
91 /**
92 * @var int[][][] array containing the generated opcodes for the differences between the two items
93 */
94 private array $groupedOpcodes = [];
95
96 /**
97 * @var int[][][] array containing the generated opcodes for the differences between the two items (GNU version)
98 */
99 private array $groupedOpcodesGnu = [];
100
101 /**
102 * @var array associative array of the default options available for the Differ class and their default value
103 */
104 private static array $defaultOptions = [
105 // show how many neighbor lines
106 // Differ::CONTEXT_ALL can be used to show the whole file
107 'context' => 3,
108 // ignore case difference
109 'ignoreCase' => false,
110 // ignore line ending difference
111 'ignoreLineEnding' => false,
112 // ignore whitespace difference
113 'ignoreWhitespace' => false,
114 // if the input sequence is too long, it will just gives up (especially for char-level diff)
115 'lengthLimit' => 2000,
116 // if truthy, when inputs are identical, the whole inputs will be rendered in the output
117 'fullContextIfIdentical' => false,
118 ];
119
120 /**
121 * The constructor.
122 *
123 * @param string[] $old array containing the lines of the old string to compare
124 * @param string[] $new array containing the lines of the new string to compare
125 * @param array $options the options
126 */
127 public function __construct(array $old, array $new, array $options = [])
128 {
129 $this->sequenceMatcher = new SequenceMatcher([], []);
130
131 $this->setOldNew($old, $new)->setOptions($options);
132 }
133
134 /**
135 * Set old and new.
136 *
137 * @param string[] $old the old
138 * @param string[] $new the new
139 */
140 public function setOldNew(array $old, array $new): self
141 {
142 return $this->setOld($old)->setNew($new);
143 }
144
145 /**
146 * Set old.
147 *
148 * @param string[] $old the old
149 */
150 public function setOld(array $old): self
151 {
152 if ($this->old !== $old) {
153 $this->old = $old;
154 $this->isCacheDirty = true;
155 }
156
157 return $this;
158 }
159
160 /**
161 * Set new.
162 *
163 * @param string[] $new the new
164 */
165 public function setNew(array $new): self
166 {
167 if ($this->new !== $new) {
168 $this->new = $new;
169 $this->isCacheDirty = true;
170 }
171
172 return $this;
173 }
174
175 /**
176 * Set the options.
177 *
178 * @param array $options the options
179 */
180 public function setOptions(array $options): self
181 {
182 $mergedOptions = $options + self::$defaultOptions;
183
184 if ($this->options !== $mergedOptions) {
185 $this->options = $mergedOptions;
186 $this->isCacheDirty = true;
187 }
188
189 return $this;
190 }
191
192 /**
193 * Get a range of lines from $start to $end from the old.
194 *
195 * @param int $start the starting index (negative = count from backward)
196 * @param null|int $end the ending index (negative = count from backward)
197 * if is null, it returns a slice from $start to the end
198 *
199 * @return string[] array of all of the lines between the specified range
200 */
201 public function getOld(int $start = 0, ?int $end = null): array
202 {
203 return Arr::getPartialByIndex($this->old, $start, $end);
204 }
205
206 /**
207 * Get a range of lines from $start to $end from the new.
208 *
209 * @param int $start the starting index (negative = count from backward)
210 * @param null|int $end the ending index (negative = count from backward)
211 * if is null, it returns a slice from $start to the end
212 *
213 * @return string[] array of all of the lines between the specified range
214 */
215 public function getNew(int $start = 0, ?int $end = null): array
216 {
217 return Arr::getPartialByIndex($this->new, $start, $end);
218 }
219
220 /**
221 * Get the options.
222 *
223 * @return array the options
224 */
225 public function getOptions(): array
226 {
227 return $this->options;
228 }
229
230 /**
231 * Get the old no EOL at EOF index.
232 *
233 * @return int the old no EOL at EOF index
234 */
235 public function getOldNoEolAtEofIdx(): int
236 {
237 return $this->finalize()->oldNoEolAtEofIdx;
238 }
239
240 /**
241 * Get the new no EOL at EOF index.
242 *
243 * @return int the new no EOL at EOF index
244 */
245 public function getNewNoEolAtEofIdx(): int
246 {
247 return $this->finalize()->newNoEolAtEofIdx;
248 }
249
250 /**
251 * Compare the old and the new with the spaceship operator.
252 */
253 public function getOldNewComparison(): int
254 {
255 return $this->finalize()->oldNewComparison;
256 }
257
258 /**
259 * Get the singleton.
260 */
261 public static function getInstance(): self
262 {
263 static $singleton;
264
265 return $singleton ??= new self([], []);
266 }
267
268 /**
269 * Gets the diff statistics such as inserted and deleted etc...
270 *
271 * @return array<string,float> the statistics
272 */
273 public function getStatistics(): array
274 {
275 $ret = [
276 'inserted' => 0,
277 'deleted' => 0,
278 'unmodified' => 0,
279 'changedRatio' => 0.0,
280 ];
281
282 foreach ($this->getGroupedOpcodes() as $hunk) {
283 foreach ($hunk as [$op, $i1, $i2, $j1, $j2]) {
284 if ($op & (SequenceMatcher::OP_INS | SequenceMatcher::OP_REP)) {
285 $ret['inserted'] += $j2 - $j1;
286 }
287 if ($op & (SequenceMatcher::OP_DEL | SequenceMatcher::OP_REP)) {
288 $ret['deleted'] += $i2 - $i1;
289 }
290 }
291 }
292
293 $ret['unmodified'] = $this->oldSrcLength - $ret['deleted'];
294 $ret['changedRatio'] = 1 - ($ret['unmodified'] / $this->oldSrcLength);
295
296 return $ret;
297 }
298
299 /**
300 * Generate a list of the compiled and grouped opcodes for the differences between the
301 * two strings. Generally called by the renderer, this class instantiates the sequence
302 * matcher and performs the actual diff generation and return an array of the opcodes
303 * for it. Once generated, the results are cached in the Differ class instance.
304 *
305 * @return int[][][] array of the grouped opcodes for the generated diff
306 */
307 public function getGroupedOpcodes(): array
308 {
309 $this->finalize();
310
311 if (!empty($this->groupedOpcodes)) {
312 return $this->groupedOpcodes;
313 }
314
315 $old = $this->old;
316 $new = $this->new;
317
318 $this->getGroupedOpcodesPre($old, $new);
319
320 if ($this->oldNewComparison === 0 && $this->options['fullContextIfIdentical']) {
321 $opcodes = [
322 [
323 [SequenceMatcher::OP_EQ, 0, \count($old), 0, \count($new)],
324 ],
325 ];
326 } else {
327 $opcodes = $this->sequenceMatcher
328 ->setSequences($old, $new)
329 ->getGroupedOpcodes($this->options['context'])
330 ;
331 }
332
333 $this->getGroupedOpcodesPost($opcodes);
334
335 return $this->groupedOpcodes = $opcodes;
336 }
337
338 /**
339 * A EOL-at-EOF-sensitive version of getGroupedOpcodes().
340 *
341 * @return int[][][] array of the grouped opcodes for the generated diff (GNU version)
342 */
343 public function getGroupedOpcodesGnu(): array
344 {
345 $this->finalize();
346
347 if (!empty($this->groupedOpcodesGnu)) {
348 return $this->groupedOpcodesGnu;
349 }
350
351 $old = $this->old;
352 $new = $this->new;
353
354 $this->getGroupedOpcodesGnuPre($old, $new);
355
356 if ($this->oldNewComparison === 0 && $this->options['fullContextIfIdentical']) {
357 $opcodes = [
358 [
359 [SequenceMatcher::OP_EQ, 0, \count($old), 0, \count($new)],
360 ],
361 ];
362 } else {
363 $opcodes = $this->sequenceMatcher
364 ->setSequences($old, $new)
365 ->getGroupedOpcodes($this->options['context'])
366 ;
367 }
368
369 $this->getGroupedOpcodesGnuPost($opcodes);
370
371 return $this->groupedOpcodesGnu = $opcodes;
372 }
373
374 /**
375 * Triggered before getGroupedOpcodes(). May modify the $old and $new.
376 *
377 * @param string[] $old the old
378 * @param string[] $new the new
379 */
380 private function getGroupedOpcodesPre(array &$old, array &$new): void
381 {
382 // append these lines to make sure the last block of the diff result is OP_EQ
383 static $eolAtEofHelperLines = [
384 SequenceMatcher::APPENDED_HELPER_LINE,
385 SequenceMatcher::APPENDED_HELPER_LINE,
386 SequenceMatcher::APPENDED_HELPER_LINE,
387 SequenceMatcher::APPENDED_HELPER_LINE,
388 ];
389
390 $this->oldSrcLength = \count($old);
391 array_push($old, ...$eolAtEofHelperLines);
392
393 $this->newSrcLength = \count($new);
394 array_push($new, ...$eolAtEofHelperLines);
395 }
396
397 /**
398 * Triggered after getGroupedOpcodes(). May modify the $opcodes.
399 *
400 * @param int[][][] $opcodes the opcodes
401 */
402 private function getGroupedOpcodesPost(array &$opcodes): void
403 {
404 // remove those extra lines cause by adding extra SequenceMatcher::APPENDED_HELPER_LINE lines
405 foreach ($opcodes as $hunkIdx => &$hunk) {
406 foreach ($hunk as $blockIdx => &$block) {
407 // range overflow
408 if ($block[1] > $this->oldSrcLength) {
409 $block[1] = $this->oldSrcLength;
410 }
411 if ($block[2] > $this->oldSrcLength) {
412 $block[2] = $this->oldSrcLength;
413 }
414 if ($block[3] > $this->newSrcLength) {
415 $block[3] = $this->newSrcLength;
416 }
417 if ($block[4] > $this->newSrcLength) {
418 $block[4] = $this->newSrcLength;
419 }
420
421 // useless extra block?
422 /** @phan-suppress-next-line PhanTypePossiblyInvalidDimOffset */
423 if ($block[1] === $block[2] && $block[3] === $block[4]) {
424 unset($hunk[$blockIdx]);
425 }
426 }
427
428 if (empty($hunk)) {
429 unset($opcodes[$hunkIdx]);
430 }
431 }
432 }
433
434 /**
435 * Triggered before getGroupedOpcodesGnu(). May modify the $old and $new.
436 *
437 * @param string[] $old the old
438 * @param string[] $new the new
439 */
440 private function getGroupedOpcodesGnuPre(array &$old, array &$new): void
441 {
442 /**
443 * Make the lines to be prepared for GNU-style diff.
444 *
445 * This method checks whether $lines has no EOL at EOF and append a special
446 * indicator to the last line.
447 *
448 * @param string[] $lines the lines created by simply explode("\n", $string)
449 */
450 $createGnuCompatibleLines = static function (array $lines): array {
451 // note that the $lines should not be empty at this point
452 // they have at least one element "" in the array because explode("\n", "") === [""]
453 $lastLineIdx = \count($lines) - 1;
454 $lastLine = &$lines[$lastLineIdx];
455
456 if ($lastLine === '') {
457 // remove the last plain "" line since we don't need it anymore
458 // use array_slice() to also reset the array index
459 $lines = \array_slice($lines, 0, -1);
460 } else {
461 // this means the original source has no EOL at EOF
462 // we append a special indicator to that line so it no longer matches
463 $lastLine .= self::LINE_NO_EOL;
464 }
465
466 return $lines;
467 };
468
469 $old = $createGnuCompatibleLines($old);
470 $new = $createGnuCompatibleLines($new);
471
472 $this->getGroupedOpcodesPre($old, $new);
473 }
474
475 /**
476 * Triggered after getGroupedOpcodesGnu(). May modify the $opcodes.
477 *
478 * @param int[][][] $opcodes the opcodes
479 */
480 private function getGroupedOpcodesGnuPost(array &$opcodes): void
481 {
482 $this->getGroupedOpcodesPost($opcodes);
483 }
484
485 /**
486 * Claim this class has settled down and we could calculate cached
487 * properties by current properties.
488 *
489 * This method must be called before accessing cached properties to
490 * make suer that you will not get a outdated cached value.
491 *
492 * @internal
493 */
494 private function finalize(): self
495 {
496 if ($this->isCacheDirty) {
497 $this->resetCachedResults();
498
499 $this->oldNoEolAtEofIdx = $this->getOld(-1) === [''] ? -1 : \count($this->old);
500 $this->newNoEolAtEofIdx = $this->getNew(-1) === [''] ? -1 : \count($this->new);
501 $this->oldNewComparison = $this->old <=> $this->new;
502
503 $this->sequenceMatcher->setOptions($this->options);
504 }
505
506 return $this;
507 }
508
509 /**
510 * Reset cached results.
511 */
512 private function resetCachedResults(): self
513 {
514 foreach (self::CACHED_PROPERTIES as $property => $value) {
515 $this->{$property} = $value;
516 }
517
518 $this->isCacheDirty = false;
519
520 return $this;
521 }
522 }