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

Differ.php in WPIDE – File Manager & Code Editor 3.5.9, at vendor/nikic/php-parser/lib/PhpParser/Internal/Differ.php

165 lines 4.6 KB

Raw Download Zip

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