| 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 |
} |