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