1<?php declare(strict_types=1);
2
3namespace 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 */
14class 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}
179