Debian Codegraph @

vendor/phpstan/phpdoc-parser/src/Printer/Differ.php

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