Debian Codegraph @

vendor/nikic/php-parser/lib/PhpParser/Internal/Differ.php

raw
1 <?php declare(strict_types=1);
2
3 namespace PhpParser\Internal;
4
5 /**
6 * Implements the Myers diff algorithm.
7 *
8 * Myers, Eugene W. "An O (ND) difference algorithm and its variations."
9 * Algorithmica 1.1 (1986): 251-266.
10 *
11 * @template T
12 * @internal
13 */
14 class Differ {
15 /** @var callable(T, T): bool */
16 private $isEqual;
17
18 /**
19 * Create differ over the given equality relation.
20 *
21 * @param callable(T, T): bool $isEqual Equality relation
22 */
23 public function __construct(callable $isEqual) {
24 $this->isEqual = $isEqual;
25 }
26
27 /**
28 * Calculate diff (edit script) from $old to $new.
29 *
30 * @param T[] $old Original array
31 * @param T[] $new New array
32 *
33 * @return DiffElem[] Diff (edit script)
34 */
35 public function diff(array $old, array $new): array {
36 $old = \array_values($old);
37 $new = \array_values($new);
38 list($trace, $x, $y) = $this->calculateTrace($old, $new);
39 return $this->extractDiff($trace, $x, $y, $old, $new);
40 }
41
42 /**
43 * Calculate diff, including "replace" operations.
44 *
45 * If a sequence of remove operations is followed by the same number of add operations, these
46 * will be coalesced into replace operations.
47 *
48 * @param T[] $old Original array
49 * @param T[] $new New array
50 *
51 * @return DiffElem[] Diff (edit script), including replace operations
52 */
53 public function diffWithReplacements(array $old, array $new): array {
54 return $this->coalesceReplacements($this->diff($old, $new));
55 }
56
57 /**
58 * @param T[] $old
59 * @param T[] $new
60 * @return array{array<int, array<int, int>>, int, int}
61 */
62 private function calculateTrace(array $old, array $new): array {
63 $n = \count($old);
64 $m = \count($new);
65 $max = $n + $m;
66 $v = [1 => 0];
67 $trace = [];
68 for ($d = 0; $d <= $max; $d++) {
69 $trace[] = $v;
70 for ($k = -$d; $k <= $d; $k += 2) {
71 if ($k === -$d || ($k !== $d && $v[$k - 1] < $v[$k + 1])) {
72 $x = $v[$k + 1];
73 } else {
74 $x = $v[$k - 1] + 1;
75 }
76
77 $y = $x - $k;
78 while ($x < $n && $y < $m && ($this->isEqual)($old[$x], $new[$y])) {
79 $x++;
80 $y++;
81 }
82
83 $v[$k] = $x;
84 if ($x >= $n && $y >= $m) {
85 return [$trace, $x, $y];
86 }
87 }
88 }
89 throw new \Exception('Should not happen');
90 }
91
92 /**
93 * @param array<int, array<int, int>> $trace
94 * @param T[] $old
95 * @param T[] $new
96 * @return DiffElem[]
97 */
98 private function extractDiff(array $trace, int $x, int $y, array $old, array $new): array {
99 $result = [];
100 for ($d = \count($trace) - 1; $d >= 0; $d--) {
101 $v = $trace[$d];
102 $k = $x - $y;
103
104 if ($k === -$d || ($k !== $d && $v[$k - 1] < $v[$k + 1])) {
105 $prevK = $k + 1;
106 } else {
107 $prevK = $k - 1;
108 }
109
110 $prevX = $v[$prevK];
111 $prevY = $prevX - $prevK;
112
113 while ($x > $prevX && $y > $prevY) {
114 $result[] = new DiffElem(DiffElem::TYPE_KEEP, $old[$x - 1], $new[$y - 1]);
115 $x--;
116 $y--;
117 }
118
119 if ($d === 0) {
120 break;
121 }
122
123 while ($x > $prevX) {
124 $result[] = new DiffElem(DiffElem::TYPE_REMOVE, $old[$x - 1], null);
125 $x--;
126 }
127
128 while ($y > $prevY) {
129 $result[] = new DiffElem(DiffElem::TYPE_ADD, null, $new[$y - 1]);
130 $y--;
131 }
132 }
133 return array_reverse($result);
134 }
135
136 /**
137 * Coalesce equal-length sequences of remove+add into a replace operation.
138 *
139 * @param DiffElem[] $diff
140 * @return DiffElem[]
141 */
142 private function coalesceReplacements(array $diff): array {
143 $newDiff = [];
144 $c = \count($diff);
145 for ($i = 0; $i < $c; $i++) {
146 $diffType = $diff[$i]->type;
147 if ($diffType !== DiffElem::TYPE_REMOVE) {
148 $newDiff[] = $diff[$i];
149 continue;
150 }
151
152 $j = $i;
153 while ($j < $c && $diff[$j]->type === DiffElem::TYPE_REMOVE) {
154 $j++;
155 }
156
157 $k = $j;
158 while ($k < $c && $diff[$k]->type === DiffElem::TYPE_ADD) {
159 $k++;
160 }
161
162 if ($j - $i === $k - $j) {
163 $len = $j - $i;
164 for ($n = 0; $n < $len; $n++) {
165 $newDiff[] = new DiffElem(
166 DiffElem::TYPE_REPLACE, $diff[$i + $n]->old, $diff[$j + $n]->new
167 );
168 }
169 } else {
170 for (; $i < $k; $i++) {
171 $newDiff[] = $diff[$i];
172 }
173 }
174 $i = $k - 1;
175 }
176 return $newDiff;
177 }
178 }