Debian Codegraph @

vendor/jfcherng/php-sequence-matcher/src/SequenceMatcher.php

raw
1 <?php
2
3 declare(strict_types=1);
4
5 namespace Jfcherng\Diff;
6
7 /**
8 * A longest sequence matcher.
9 *
10 * The logic is primarily based on the Python difflib package.
11 *
12 * @see https://docs.python.org/3/library/difflib.html
13 */
14 final class SequenceMatcher
15 {
16 /** @var int 0, opcode: no operation */
17 public const OP_NOP = 0;
18
19 /** @var int 1, opcode: equal */
20 public const OP_EQ = 1 << 0;
21
22 /** @var int 2, opcode: delete */
23 public const OP_DEL = 1 << 1;
24
25 /** @var int 4, opcode: insert */
26 public const OP_INS = 1 << 2;
27
28 /** @var int 8, opcode: replace */
29 public const OP_REP = 1 << 3;
30
31 public const OP_INT_TO_STR_MAP = [
32 self::OP_NOP => 'nop',
33 self::OP_EQ => 'eq',
34 self::OP_DEL => 'del',
35 self::OP_INS => 'ins',
36 self::OP_REP => 'rep',
37 ];
38
39 public const OP_STR_TO_INT_MAP = [
40 'nop' => self::OP_NOP,
41 'eq' => self::OP_EQ,
42 'del' => self::OP_DEL,
43 'ins' => self::OP_INS,
44 'rep' => self::OP_REP,
45 ];
46
47 /**
48 * The helper line which may be used to append to the source inputs to help
49 * it easier to handle EOL at EOF problem. This line shouldn't be counted into diff.
50 *
51 * @var string
52 */
53 public const APPENDED_HELPER_LINE = "\u{fcf28}\u{fc232}";
54
55 /**
56 * @var null|\Closure either a string or an array containing a callback function to determine if a line is "junk" or not
57 */
58 private ?\Closure $junkCallback;
59
60 /**
61 * @var array the first sequence to compare against
62 */
63 private array $a = [];
64
65 /**
66 * @var array the second sequence
67 */
68 private array $b = [];
69
70 /**
71 * @var array the first sequence to compare against (transformed)
72 */
73 private array $at = [];
74
75 /**
76 * @var array the second sequence (transformed)
77 */
78 private array $bt = [];
79
80 /**
81 * @var array array of characters that are considered junk from the second sequence. Characters are the array key.
82 */
83 private array $junkDict = [];
84
85 /**
86 * @var array array of indices that do not contain junk elements
87 */
88 private array $b2j = [];
89
90 private array $options = [];
91
92 private static array $defaultOptions = [
93 'ignoreCase' => false,
94 'ignoreLineEnding' => false,
95 'ignoreWhitespace' => false,
96 'lengthLimit' => 2000,
97 ];
98
99 private array $matchingBlocks = [];
100
101 /**
102 * @var array generated opcodes which manipulates seq1 to seq2
103 */
104 private array $opcodes = [];
105
106 /**
107 * The constructor. With the sequences being passed, they'll be set
108 * for the sequence matcher and it will perform a basic cleanup &
109 * calculate junk elements.
110 *
111 * @param string[] $a an array containing the lines to compare against
112 * @param string[] $b an array containing the lines to compare
113 * @param null|\Closure $junkCallback either an array or string that references a callback function (if there is one) to determine 'junk' characters
114 * @param array $options the options
115 */
116 public function __construct(array $a, array $b, ?\Closure $junkCallback = null, array $options = [])
117 {
118 $this->junkCallback = $junkCallback;
119 $this->setOptions($options);
120 $this->setSequences($a, $b);
121 }
122
123 /**
124 * Set the options.
125 *
126 * @param array $options The options
127 */
128 public function setOptions(array $options): static
129 {
130 $needRerunChainB = $this->isAnyOptionChanged(
131 $this->options,
132 $options,
133 ['ignoreCase', 'ignoreLineEnding', 'ignoreWhitespace', 'lengthLimit'],
134 );
135
136 $this->options = $options + self::$defaultOptions;
137
138 if ($needRerunChainB) {
139 $this->chainB();
140 }
141
142 $this->resetCachedResults();
143
144 return $this;
145 }
146
147 /**
148 * Get the options.
149 */
150 public function getOptions(): array
151 {
152 return $this->options;
153 }
154
155 /**
156 * Reset cached results.
157 */
158 public function resetCachedResults(): static
159 {
160 $this->matchingBlocks = [];
161 $this->opcodes = [];
162
163 return $this;
164 }
165
166 /**
167 * Set the first and second sequences to use with the sequence matcher.
168 *
169 * This method is more effecient than "->setSeq1($old)->setSeq2($new)"
170 * because it only run the routine once.
171 *
172 * @param string[] $a an array containing the lines to compare against
173 * @param string[] $b an array containing the lines to compare
174 */
175 public function setSequences(array $a, array $b): static
176 {
177 $need_routine = false;
178
179 if ($this->a !== $a) {
180 $need_routine = true;
181 $this->a = $a;
182 }
183
184 if ($this->b !== $b) {
185 $need_routine = true;
186 $this->b = $b;
187 }
188
189 if ($need_routine) {
190 $this->chainB();
191 $this->resetCachedResults();
192 }
193
194 return $this;
195 }
196
197 /**
198 * Set the first sequence ($a) and reset any internal caches to indicate that
199 * when calling the calculation methods, we need to recalculate them.
200 *
201 * @param string[] $a the sequence to set as the first sequence
202 */
203 public function setSeq1(array $a): static
204 {
205 if ($this->a !== $a) {
206 $this->a = $a;
207 $this->chainB();
208 $this->resetCachedResults();
209 }
210
211 return $this;
212 }
213
214 /**
215 * Set the second sequence ($b) and reset any internal caches to indicate that
216 * when calling the calculation methods, we need to recalculate them.
217 *
218 * @param string[] $b the sequence to set as the second sequence
219 */
220 public function setSeq2(array $b): static
221 {
222 if ($this->b !== $b) {
223 $this->b = $b;
224 $this->chainB();
225 $this->resetCachedResults();
226 }
227
228 return $this;
229 }
230
231 /**
232 * Find the longest matching block in the two sequences, as defined by the
233 * lower and upper constraints for each sequence. (for the first sequence,
234 * $alo - $ahi and for the second sequence, $blo - $bhi).
235 *
236 * Essentially, of all of the maximal matching blocks, return the one that
237 * startest earliest in $a, and all of those maximal matching blocks that
238 * start earliest in $a, return the one that starts earliest in $b.
239 *
240 * If the junk callback is defined, do the above but with the restriction
241 * that the junk element appears in the block. Extend it as far as possible
242 * by matching only junk elements in both $a and $b.
243 *
244 * @param int $alo the lower constraint for the first sequence
245 * @param int $ahi the upper constraint for the first sequence
246 * @param int $blo the lower constraint for the second sequence
247 * @param int $bhi the upper constraint for the second sequence
248 *
249 * @return int[] an array containing the longest match that includes the starting position in $a, start in $b and the length/size
250 */
251 public function findLongestMatch(int $alo, int $ahi, int $blo, int $bhi): array
252 {
253 $bestI = $alo;
254 $bestJ = $blo;
255 $bestSize = 0;
256
257 $j2Len = [];
258
259 for ($i = $alo; $i < $ahi; ++$i) {
260 if (null === ($element = $this->at[$i] ?? null)) {
261 continue;
262 }
263
264 $newJ2Len = [];
265 $jDict = $this->b2j[$element] ?? [];
266
267 foreach ($jDict as $j) {
268 if ($j < $blo) {
269 continue;
270 }
271
272 if ($j >= $bhi) {
273 break;
274 }
275
276 $k = ($j2Len[$j - 1] ?? 0) + 1;
277 $newJ2Len[$j] = $k;
278
279 if ($k > $bestSize) {
280 $bestI = $i - $k + 1;
281 $bestJ = $j - $k + 1;
282 $bestSize = $k;
283 }
284 }
285
286 $j2Len = $newJ2Len;
287 }
288
289 while (
290 $bestI > $alo
291 && $bestJ > $blo
292 && $this->at[$bestI - 1] === $this->bt[$bestJ - 1]
293 && !$this->isBJunk($this->bt[$bestJ - 1])
294 ) {
295 --$bestI;
296 --$bestJ;
297 ++$bestSize;
298 }
299
300 while (
301 $bestI + $bestSize < $ahi
302 && $bestJ + $bestSize < $bhi
303 && $this->at[$bestI + $bestSize] === $this->bt[$bestJ + $bestSize]
304 && !$this->isBJunk($this->bt[$bestJ + $bestSize])
305 ) {
306 ++$bestSize;
307 }
308
309 while (
310 $bestI > $alo
311 && $bestJ > $blo
312 && $this->at[$bestI - 1] === $this->bt[$bestJ - 1]
313 && $this->isBJunk($this->bt[$bestJ - 1])
314 ) {
315 --$bestI;
316 --$bestJ;
317 ++$bestSize;
318 }
319
320 while (
321 $bestI + $bestSize < $ahi
322 && $bestJ + $bestSize < $bhi
323 && $this->at[$bestI + $bestSize] === $this->bt[$bestJ + $bestSize]
324 && $this->isBJunk($this->bt[$bestJ + $bestSize])
325 ) {
326 ++$bestSize;
327 }
328
329 return [$bestI, $bestJ, $bestSize];
330 }
331
332 /**
333 * Return a nested set of arrays for all of the matching sub-sequences
334 * in the strings $a and $b.
335 *
336 * Each block contains the lower constraint of the block in $a, the lower
337 * constraint of the block in $b and finally the number of lines that the
338 * block continues for.
339 *
340 * @return int[][] a nested array of the matching blocks, as described by the function
341 */
342 public function getMatchingBlocks(): array
343 {
344 if (!empty($this->matchingBlocks)) {
345 return $this->matchingBlocks;
346 }
347
348 $aCount = \count($this->a);
349 $bCount = \count($this->b);
350
351 $queue = [
352 [0, $aCount, 0, $bCount],
353 ];
354
355 $matchingBlocks = [];
356 while (!empty($queue)) {
357 [$alo, $ahi, $blo, $bhi] = array_pop($queue);
358 [$i, $j, $k] = $x = $this->findLongestMatch($alo, $ahi, $blo, $bhi);
359
360 if ($k) {
361 $matchingBlocks[] = $x;
362
363 if ($alo < $i && $blo < $j) {
364 $queue[] = [$alo, $i, $blo, $j];
365 }
366
367 if ($i + $k < $ahi && $j + $k < $bhi) {
368 $queue[] = [$i + $k, $ahi, $j + $k, $bhi];
369 }
370 }
371 }
372
373 usort($matchingBlocks, function (array $a, array $b): int {
374 $aCount = \count($a);
375 $bCount = \count($b);
376 $min = min($aCount, $bCount);
377
378 for ($i = 0; $i < $min; ++$i) {
379 if ($a[$i] !== $b[$i]) {
380 return $a[$i] <=> $b[$i];
381 }
382 }
383
384 return $aCount <=> $bCount;
385 });
386
387 $i1 = $j1 = $k1 = 0;
388 $nonAdjacent = [];
389 foreach ($matchingBlocks as [$i2, $j2, $k2]) {
390 if ($i1 + $k1 === $i2 && $j1 + $k1 === $j2) {
391 $k1 += $k2;
392
393 continue;
394 }
395
396 if ($k1) {
397 $nonAdjacent[] = [$i1, $j1, $k1];
398 }
399
400 $i1 = $i2;
401 $j1 = $j2;
402 $k1 = $k2;
403 }
404
405 if ($k1) {
406 $nonAdjacent[] = [$i1, $j1, $k1];
407 }
408
409 $nonAdjacent[] = [$aCount, $bCount, 0];
410
411 $this->matchingBlocks = $nonAdjacent;
412
413 return $this->matchingBlocks;
414 }
415
416 /**
417 * Return a list of all of the opcodes for the differences between the
418 * two strings.
419 *
420 * The nested array returned contains an array describing the opcode
421 * which includes:
422 * 0 - The type of op (as described below) for the opcode.
423 * 1 - The beginning line in the first sequence.
424 * 2 - The end line in the first sequence.
425 * 3 - The beginning line in the second sequence.
426 * 4 - The end line in the second sequence.
427 *
428 * The different types of ops include:
429 * replace - The string from $i1 to $i2 in $a should be replaced by
430 * the string in $b from $j1 to $j2.
431 * delete - The string in $a from $i1 to $j2 should be deleted.
432 * insert - The string in $b from $j1 to $j2 should be inserted at
433 * $i1 in $a.
434 * equal - The two strings with the specified ranges are equal.
435 *
436 * @return int[][] array of the opcodes describing the differences between the strings
437 */
438 public function getOpcodes(): array
439 {
440 if (!empty($this->opcodes)) {
441 return $this->opcodes;
442 }
443
444 $i = $j = 0;
445 $this->opcodes = [];
446
447 foreach ($this->getMatchingBlocks() as [$ai, $bj, $size]) {
448 if ($i < $ai && $j < $bj) {
449 $op = self::OP_REP;
450 } elseif ($i < $ai) {
451 $op = self::OP_DEL;
452 } elseif ($j < $bj) {
453 $op = self::OP_INS;
454 } else {
455 $op = self::OP_NOP;
456 }
457
458 if ($op) {
459 $this->opcodes[] = [$op, $i, $ai, $j, $bj];
460 }
461
462 $i = $ai + $size;
463 $j = $bj + $size;
464
465 if ($size) {
466 $this->opcodes[] = [self::OP_EQ, $ai, $i, $bj, $j];
467 }
468 }
469
470 return $this->opcodes;
471 }
472
473 /**
474 * Return a series of nested arrays containing different groups of generated
475 * opcodes for the differences between the strings with up to $context lines
476 * of surrounding content.
477 *
478 * Essentially what happens here is any big equal blocks of strings are stripped
479 * out, the smaller subsets of changes are then arranged in to their groups.
480 * This means that the sequence matcher and diffs do not need to include the full
481 * content of the different files but can still provide context as to where the
482 * changes are.
483 *
484 * @param int $context the number of lines of context to provide around the groups
485 *
486 * @return int[][][] nested array of all of the grouped opcodes
487 */
488 public function getGroupedOpcodes(int $context = 3): array
489 {
490 $opcodes = $this->getOpcodes();
491
492 if (empty($opcodes)) {
493 $opcodes = [
494 [self::OP_EQ, 0, 1, 0, 1],
495 ];
496 }
497
498 if ($opcodes[0][0] === self::OP_EQ) {
499 // fix the leading sequence which is out of context.
500 $opcodes[0] = [
501 $opcodes[0][0],
502 max($opcodes[0][1], $opcodes[0][2] - $context),
503 $opcodes[0][2],
504 max($opcodes[0][3], $opcodes[0][4] - $context),
505 $opcodes[0][4],
506 ];
507 }
508
509 $lastItem = \count($opcodes) - 1;
510 if ($opcodes[$lastItem][0] === self::OP_EQ) {
511 [$op, $i1, $i2, $j1, $j2] = $opcodes[$lastItem];
512 // fix the trailing sequence which is out of context.
513 $opcodes[$lastItem] = [
514 $op,
515 $i1,
516 min($i2, $i1 + $context),
517 $j1,
518 min($j2, $j1 + $context),
519 ];
520 }
521
522 $maxRange = $context << 1;
523 $groups = $group = [];
524 foreach ($opcodes as [$op, $i1, $i2, $j1, $j2]) {
525 if ($op === self::OP_EQ && $i2 - $i1 > $maxRange) {
526 $group[] = [
527 $op,
528 $i1,
529 min($i2, $i1 + $context),
530 $j1,
531 min($j2, $j1 + $context),
532 ];
533 $groups[] = $group;
534 $group = [];
535 $i1 = max($i1, $i2 - $context);
536 $j1 = max($j1, $j2 - $context);
537 }
538
539 $group[] = [$op, $i1, $i2, $j1, $j2];
540 }
541
542 if (
543 !empty($group)
544 && (
545 \count($group) !== 1
546 || $group[0][0] !== self::OP_EQ
547 )
548 ) {
549 $groups[] = $group;
550 }
551
552 // there will be at least leading/trailing OP_EQ blocks
553 // if we want really zero-context, we keep only non-equal blocks
554 if ($context <= 0) {
555 $groupsNew = [];
556
557 foreach ($groups as $group) {
558 $groupNew = [];
559
560 foreach ($group as $block) {
561 if ($block[0] !== self::OP_EQ) {
562 $groupNew[] = $block;
563 }
564 }
565
566 if (!empty($groupNew)) {
567 $groupsNew[] = $groupNew;
568 }
569 }
570
571 return $groupsNew;
572 }
573
574 return $groups;
575 }
576
577 /**
578 * Convert an operation code from int into its string form.
579 *
580 * @param int $op the operation code
581 *
582 * @throws \InvalidArgumentException
583 *
584 * @return string the string representation of the operation code
585 */
586 public static function opIntToStr(int $op): string
587 {
588 if (!isset(self::OP_INT_TO_STR_MAP[$op])) {
589 throw new \InvalidArgumentException("Invalid OP: {$op}");
590 }
591
592 return self::OP_INT_TO_STR_MAP[$op];
593 }
594
595 /**
596 * Convert an operation code from string into its int form.
597 *
598 * @param string $op the operation code
599 *
600 * @throws \InvalidArgumentException
601 *
602 * @return int the int representation of the operation code
603 */
604 public static function opStrToInt(string $op): int
605 {
606 if (!isset(self::OP_STR_TO_INT_MAP[$op])) {
607 throw new \InvalidArgumentException("Invalid OP: {$op}");
608 }
609
610 return self::OP_STR_TO_INT_MAP[$op];
611 }
612
613 /**
614 * Determine if any option under test changed.
615 *
616 * @param array $old the old options
617 * @param array $new the new options
618 * @param array $keys the option keys under test
619 */
620 private function isAnyOptionChanged(array $old, array $new, array $keys): bool
621 {
622 foreach ($keys as $key) {
623 if (isset($new[$key]) && $new[$key] !== $old[$key]) {
624 return true;
625 }
626 }
627
628 return false;
629 }
630
631 /**
632 * Get the processed line with the initialized options.
633 *
634 * @param string $line the line
635 *
636 * @return string the line after being processed
637 */
638 private function processLineWithOptions(string $line): string
639 {
640 if ($this->options['ignoreWhitespace']) {
641 static $whitespaces = [' ', "\t", "\r", "\n"];
642
643 $line = str_replace($whitespaces, '', $line);
644 }
645
646 if ($this->options['ignoreCase']) {
647 $line = strtolower($line);
648 }
649
650 if ($this->options['ignoreLineEnding']) {
651 $line = rtrim($line, "\r\n");
652 }
653
654 return $line;
655 }
656
657 /**
658 * Generate the internal arrays containing the list of junk and non-junk
659 * characters for the second ($b) sequence.
660 */
661 private function chainB(): static
662 {
663 $this->at = array_map([$this, 'processLineWithOptions'], $this->a);
664 $this->bt = array_map([$this, 'processLineWithOptions'], $this->b);
665
666 $length = \count($this->bt);
667 $this->b2j = [];
668 $popularDict = [];
669
670 for ($i = 0; $i < $length; ++$i) {
671 $char = $this->bt[$i];
672 $this->b2j[$char] = $this->b2j[$char] ?? [];
673
674 if (
675 $length >= $this->options['lengthLimit']
676 && \count($this->b2j[$char]) * 100 > $length
677 && $char !== self::APPENDED_HELPER_LINE
678 ) {
679 $popularDict[$char] = 1;
680
681 unset($this->b2j[$char]);
682 } else {
683 $this->b2j[$char][] = $i;
684 }
685 }
686
687 // remove leftovers
688 foreach (array_keys($popularDict) as $char) {
689 unset($this->b2j[$char]);
690 }
691
692 $this->junkDict = [];
693 if (\is_callable($this->junkCallback)) {
694 foreach (array_keys($popularDict) as $char) {
695 if (($this->junkCallback)($char)) {
696 $this->junkDict[$char] = 1;
697 unset($popularDict[$char]);
698 }
699 }
700
701 foreach (array_keys($this->b2j) as $char) {
702 if (($this->junkCallback)($char)) {
703 $this->junkDict[$char] = 1;
704 unset($this->b2j[$char]);
705 }
706 }
707 }
708
709 return $this;
710 }
711
712 /**
713 * Checks if a particular character is in the junk dictionary
714 * for the list of junk characters.
715 *
716 * @return bool $b True if the character is considered junk. False if not.
717 */
718 private function isBJunk(string $b): bool
719 {
720 return isset($this->junkDict[$b]);
721 }
722 }