Chris@0
|
1 <?php
|
Chris@0
|
2
|
Chris@0
|
3 namespace Drupal\Component\Diff\Engine;
|
Chris@0
|
4
|
Chris@0
|
5 /**
|
Chris@0
|
6 * Class used internally by Diff to actually compute the diffs.
|
Chris@0
|
7 *
|
Chris@0
|
8 * The algorithm used here is mostly lifted from the perl module
|
Chris@0
|
9 * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
|
Chris@0
|
10 * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
|
Chris@0
|
11 *
|
Chris@0
|
12 * More ideas are taken from:
|
Chris@0
|
13 * http://www.ics.uci.edu/~eppstein/161/960229.html
|
Chris@0
|
14 *
|
Chris@0
|
15 * Some ideas (and a bit of code) are from analyze.c, from GNU
|
Chris@0
|
16 * diffutils-2.7, which can be found at:
|
Chris@0
|
17 * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
|
Chris@0
|
18 *
|
Chris@0
|
19 * closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
|
Chris@0
|
20 * are my own.
|
Chris@0
|
21 *
|
Chris@0
|
22 * Line length limits for robustness added by Tim Starling, 2005-08-31
|
Chris@0
|
23 *
|
Chris@0
|
24 * @author Geoffrey T. Dairiki, Tim Starling
|
Chris@0
|
25 * @private
|
Chris@0
|
26 * @subpackage DifferenceEngine
|
Chris@0
|
27 */
|
Chris@0
|
28 class DiffEngine {
|
Chris@0
|
29
|
Chris@0
|
30 const USE_ASSERTS = FALSE;
|
Chris@0
|
31
|
Chris@0
|
32 const MAX_XREF_LENGTH = 10000;
|
Chris@0
|
33
|
Chris@0
|
34 public function diff($from_lines, $to_lines) {
|
Chris@0
|
35
|
Chris@0
|
36 $n_from = sizeof($from_lines);
|
Chris@0
|
37 $n_to = sizeof($to_lines);
|
Chris@0
|
38
|
Chris@0
|
39 $this->xchanged = $this->ychanged = [];
|
Chris@0
|
40 $this->xv = $this->yv = [];
|
Chris@0
|
41 $this->xind = $this->yind = [];
|
Chris@0
|
42 unset($this->seq);
|
Chris@0
|
43 unset($this->in_seq);
|
Chris@0
|
44 unset($this->lcs);
|
Chris@0
|
45
|
Chris@0
|
46 // Skip leading common lines.
|
Chris@0
|
47 for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
|
Chris@0
|
48 if ($from_lines[$skip] !== $to_lines[$skip]) {
|
Chris@0
|
49 break;
|
Chris@0
|
50 }
|
Chris@0
|
51 $this->xchanged[$skip] = $this->ychanged[$skip] = FALSE;
|
Chris@0
|
52 }
|
Chris@0
|
53 // Skip trailing common lines.
|
Chris@0
|
54 $xi = $n_from;
|
Chris@0
|
55 $yi = $n_to;
|
Chris@0
|
56 for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
|
Chris@0
|
57 if ($from_lines[$xi] !== $to_lines[$yi]) {
|
Chris@0
|
58 break;
|
Chris@0
|
59 }
|
Chris@0
|
60 $this->xchanged[$xi] = $this->ychanged[$yi] = FALSE;
|
Chris@0
|
61 }
|
Chris@0
|
62
|
Chris@0
|
63 // Ignore lines which do not exist in both files.
|
Chris@0
|
64 for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
|
Chris@0
|
65 $xhash[$this->_line_hash($from_lines[$xi])] = 1;
|
Chris@0
|
66 }
|
Chris@0
|
67
|
Chris@0
|
68 for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
|
Chris@0
|
69 $line = $to_lines[$yi];
|
Chris@0
|
70 if ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) {
|
Chris@0
|
71 continue;
|
Chris@0
|
72 }
|
Chris@0
|
73 $yhash[$this->_line_hash($line)] = 1;
|
Chris@0
|
74 $this->yv[] = $line;
|
Chris@0
|
75 $this->yind[] = $yi;
|
Chris@0
|
76 }
|
Chris@0
|
77 for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
|
Chris@0
|
78 $line = $from_lines[$xi];
|
Chris@0
|
79 if ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) {
|
Chris@0
|
80 continue;
|
Chris@0
|
81 }
|
Chris@0
|
82 $this->xv[] = $line;
|
Chris@0
|
83 $this->xind[] = $xi;
|
Chris@0
|
84 }
|
Chris@0
|
85
|
Chris@0
|
86 // Find the LCS.
|
Chris@0
|
87 $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
|
Chris@0
|
88
|
Chris@0
|
89 // Merge edits when possible
|
Chris@0
|
90 $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
|
Chris@0
|
91 $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
|
Chris@0
|
92
|
Chris@0
|
93 // Compute the edit operations.
|
Chris@0
|
94 $edits = [];
|
Chris@0
|
95 $xi = $yi = 0;
|
Chris@0
|
96 while ($xi < $n_from || $yi < $n_to) {
|
Chris@0
|
97 $this::USE_ASSERTS && assert($yi < $n_to || $this->xchanged[$xi]);
|
Chris@0
|
98 $this::USE_ASSERTS && assert($xi < $n_from || $this->ychanged[$yi]);
|
Chris@0
|
99
|
Chris@0
|
100 // Skip matching "snake".
|
Chris@0
|
101 $copy = [];
|
Chris@0
|
102 while ( $xi < $n_from && $yi < $n_to && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
|
Chris@0
|
103 $copy[] = $from_lines[$xi++];
|
Chris@0
|
104 ++$yi;
|
Chris@0
|
105 }
|
Chris@0
|
106 if ($copy) {
|
Chris@0
|
107 $edits[] = new DiffOpCopy($copy);
|
Chris@0
|
108 }
|
Chris@0
|
109 // Find deletes & adds.
|
Chris@0
|
110 $delete = [];
|
Chris@0
|
111 while ($xi < $n_from && $this->xchanged[$xi]) {
|
Chris@0
|
112 $delete[] = $from_lines[$xi++];
|
Chris@0
|
113 }
|
Chris@0
|
114 $add = [];
|
Chris@0
|
115 while ($yi < $n_to && $this->ychanged[$yi]) {
|
Chris@0
|
116 $add[] = $to_lines[$yi++];
|
Chris@0
|
117 }
|
Chris@0
|
118 if ($delete && $add) {
|
Chris@0
|
119 $edits[] = new DiffOpChange($delete, $add);
|
Chris@0
|
120 }
|
Chris@0
|
121 elseif ($delete) {
|
Chris@0
|
122 $edits[] = new DiffOpDelete($delete);
|
Chris@0
|
123 }
|
Chris@0
|
124 elseif ($add) {
|
Chris@0
|
125 $edits[] = new DiffOpAdd($add);
|
Chris@0
|
126 }
|
Chris@0
|
127 }
|
Chris@0
|
128 return $edits;
|
Chris@0
|
129 }
|
Chris@0
|
130
|
Chris@0
|
131 /**
|
Chris@0
|
132 * Returns the whole line if it's small enough, or the MD5 hash otherwise.
|
Chris@0
|
133 */
|
Chris@0
|
134 protected function _line_hash($line) {
|
Chris@17
|
135 if (mb_strlen($line) > $this::MAX_XREF_LENGTH) {
|
Chris@0
|
136 return md5($line);
|
Chris@0
|
137 }
|
Chris@0
|
138 else {
|
Chris@0
|
139 return $line;
|
Chris@0
|
140 }
|
Chris@0
|
141 }
|
Chris@0
|
142
|
Chris@0
|
143
|
Chris@0
|
144 /**
|
Chris@0
|
145 * Divide the Largest Common Subsequence (LCS) of the sequences
|
Chris@0
|
146 * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
|
Chris@0
|
147 * sized segments.
|
Chris@0
|
148 *
|
Chris@0
|
149 * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an
|
Chris@0
|
150 * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
|
Chris@0
|
151 * sub sequences. The first sub-sequence is contained in [X0, X1),
|
Chris@0
|
152 * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on. Note
|
Chris@0
|
153 * that (X0, Y0) == (XOFF, YOFF) and
|
Chris@0
|
154 * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
|
Chris@0
|
155 *
|
Chris@0
|
156 * This function assumes that the first lines of the specified portions
|
Chris@0
|
157 * of the two files do not match, and likewise that the last lines do not
|
Chris@0
|
158 * match. The caller must trim matching lines from the beginning and end
|
Chris@0
|
159 * of the portions it is going to specify.
|
Chris@0
|
160 */
|
Chris@0
|
161 protected function _diag($xoff, $xlim, $yoff, $ylim, $nchunks) {
|
Chris@0
|
162 $flip = FALSE;
|
Chris@0
|
163
|
Chris@0
|
164 if ($xlim - $xoff > $ylim - $yoff) {
|
Chris@0
|
165 // Things seems faster (I'm not sure I understand why)
|
Chris@0
|
166 // when the shortest sequence in X.
|
Chris@0
|
167 $flip = TRUE;
|
Chris@0
|
168 list($xoff, $xlim, $yoff, $ylim) = [$yoff, $ylim, $xoff, $xlim];
|
Chris@0
|
169 }
|
Chris@0
|
170
|
Chris@0
|
171 if ($flip) {
|
Chris@0
|
172 for ($i = $ylim - 1; $i >= $yoff; $i--) {
|
Chris@0
|
173 $ymatches[$this->xv[$i]][] = $i;
|
Chris@0
|
174 }
|
Chris@0
|
175 }
|
Chris@0
|
176 else {
|
Chris@0
|
177 for ($i = $ylim - 1; $i >= $yoff; $i--) {
|
Chris@0
|
178 $ymatches[$this->yv[$i]][] = $i;
|
Chris@0
|
179 }
|
Chris@0
|
180 }
|
Chris@0
|
181 $this->lcs = 0;
|
Chris@0
|
182 $this->seq[0] = $yoff - 1;
|
Chris@0
|
183 $this->in_seq = [];
|
Chris@0
|
184 $ymids[0] = [];
|
Chris@0
|
185
|
Chris@0
|
186 $numer = $xlim - $xoff + $nchunks - 1;
|
Chris@0
|
187 $x = $xoff;
|
Chris@0
|
188 for ($chunk = 0; $chunk < $nchunks; $chunk++) {
|
Chris@0
|
189 if ($chunk > 0) {
|
Chris@0
|
190 for ($i = 0; $i <= $this->lcs; $i++) {
|
Chris@0
|
191 $ymids[$i][$chunk - 1] = $this->seq[$i];
|
Chris@0
|
192 }
|
Chris@0
|
193 }
|
Chris@0
|
194
|
Chris@0
|
195 $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $chunk) / $nchunks);
|
Chris@0
|
196 for (; $x < $x1; $x++) {
|
Chris@0
|
197 $line = $flip ? $this->yv[$x] : $this->xv[$x];
|
Chris@0
|
198 if (empty($ymatches[$line])) {
|
Chris@0
|
199 continue;
|
Chris@0
|
200 }
|
Chris@0
|
201 $matches = $ymatches[$line];
|
Chris@14
|
202 $found_empty = FALSE;
|
Chris@14
|
203 foreach ($matches as $y) {
|
Chris@14
|
204 if (!$found_empty) {
|
Chris@14
|
205 if (empty($this->in_seq[$y])) {
|
Chris@14
|
206 $k = $this->_lcs_pos($y);
|
Chris@14
|
207 $this::USE_ASSERTS && assert($k > 0);
|
Chris@14
|
208 $ymids[$k] = $ymids[$k - 1];
|
Chris@14
|
209 $found_empty = TRUE;
|
Chris@14
|
210 }
|
Chris@0
|
211 }
|
Chris@14
|
212 else {
|
Chris@14
|
213 if ($y > $this->seq[$k - 1]) {
|
Chris@14
|
214 $this::USE_ASSERTS && assert($y < $this->seq[$k]);
|
Chris@14
|
215 // Optimization: this is a common case:
|
Chris@14
|
216 // next match is just replacing previous match.
|
Chris@14
|
217 $this->in_seq[$this->seq[$k]] = FALSE;
|
Chris@14
|
218 $this->seq[$k] = $y;
|
Chris@14
|
219 $this->in_seq[$y] = 1;
|
Chris@14
|
220 }
|
Chris@14
|
221 elseif (empty($this->in_seq[$y])) {
|
Chris@14
|
222 $k = $this->_lcs_pos($y);
|
Chris@14
|
223 $this::USE_ASSERTS && assert($k > 0);
|
Chris@14
|
224 $ymids[$k] = $ymids[$k - 1];
|
Chris@14
|
225 }
|
Chris@0
|
226 }
|
Chris@0
|
227 }
|
Chris@0
|
228 }
|
Chris@0
|
229 }
|
Chris@0
|
230
|
Chris@0
|
231 $seps[] = $flip ? [$yoff, $xoff] : [$xoff, $yoff];
|
Chris@0
|
232 $ymid = $ymids[$this->lcs];
|
Chris@0
|
233 for ($n = 0; $n < $nchunks - 1; $n++) {
|
Chris@0
|
234 $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
|
Chris@0
|
235 $y1 = $ymid[$n] + 1;
|
Chris@0
|
236 $seps[] = $flip ? [$y1, $x1] : [$x1, $y1];
|
Chris@0
|
237 }
|
Chris@0
|
238 $seps[] = $flip ? [$ylim, $xlim] : [$xlim, $ylim];
|
Chris@0
|
239
|
Chris@0
|
240 return [$this->lcs, $seps];
|
Chris@0
|
241 }
|
Chris@0
|
242
|
Chris@0
|
243 protected function _lcs_pos($ypos) {
|
Chris@0
|
244
|
Chris@0
|
245 $end = $this->lcs;
|
Chris@0
|
246 if ($end == 0 || $ypos > $this->seq[$end]) {
|
Chris@0
|
247 $this->seq[++$this->lcs] = $ypos;
|
Chris@0
|
248 $this->in_seq[$ypos] = 1;
|
Chris@0
|
249 return $this->lcs;
|
Chris@0
|
250 }
|
Chris@0
|
251
|
Chris@0
|
252 $beg = 1;
|
Chris@0
|
253 while ($beg < $end) {
|
Chris@0
|
254 $mid = (int)(($beg + $end) / 2);
|
Chris@0
|
255 if ($ypos > $this->seq[$mid]) {
|
Chris@0
|
256 $beg = $mid + 1;
|
Chris@0
|
257 }
|
Chris@0
|
258 else {
|
Chris@0
|
259 $end = $mid;
|
Chris@0
|
260 }
|
Chris@0
|
261 }
|
Chris@0
|
262
|
Chris@0
|
263 $this::USE_ASSERTS && assert($ypos != $this->seq[$end]);
|
Chris@0
|
264
|
Chris@0
|
265 $this->in_seq[$this->seq[$end]] = FALSE;
|
Chris@0
|
266 $this->seq[$end] = $ypos;
|
Chris@0
|
267 $this->in_seq[$ypos] = 1;
|
Chris@0
|
268 return $end;
|
Chris@0
|
269 }
|
Chris@0
|
270
|
Chris@0
|
271 /**
|
Chris@0
|
272 * Find LCS of two sequences.
|
Chris@0
|
273 *
|
Chris@0
|
274 * The results are recorded in the vectors $this->{x,y}changed[], by
|
Chris@0
|
275 * storing a 1 in the element for each line that is an insertion
|
Chris@0
|
276 * or deletion (ie. is not in the LCS).
|
Chris@0
|
277 *
|
Chris@0
|
278 * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
|
Chris@0
|
279 *
|
Chris@0
|
280 * Note that XLIM, YLIM are exclusive bounds.
|
Chris@0
|
281 * All line numbers are origin-0 and discarded lines are not counted.
|
Chris@0
|
282 */
|
Chris@0
|
283 protected function _compareseq($xoff, $xlim, $yoff, $ylim) {
|
Chris@0
|
284
|
Chris@0
|
285 // Slide down the bottom initial diagonal.
|
Chris@0
|
286 while ($xoff < $xlim && $yoff < $ylim && $this->xv[$xoff] == $this->yv[$yoff]) {
|
Chris@0
|
287 ++$xoff;
|
Chris@0
|
288 ++$yoff;
|
Chris@0
|
289 }
|
Chris@0
|
290
|
Chris@0
|
291 // Slide up the top initial diagonal.
|
Chris@0
|
292 while ($xlim > $xoff && $ylim > $yoff && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
|
Chris@0
|
293 --$xlim;
|
Chris@0
|
294 --$ylim;
|
Chris@0
|
295 }
|
Chris@0
|
296
|
Chris@0
|
297 if ($xoff == $xlim || $yoff == $ylim) {
|
Chris@0
|
298 $lcs = 0;
|
Chris@0
|
299 }
|
Chris@0
|
300 else {
|
Chris@0
|
301 // This is ad hoc but seems to work well.
|
Chris@0
|
302 //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
|
Chris@0
|
303 //$nchunks = max(2, min(8, (int)$nchunks));
|
Chris@0
|
304 $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
|
Chris@0
|
305 list($lcs, $seps) = $this->_diag($xoff, $xlim, $yoff, $ylim, $nchunks);
|
Chris@0
|
306 }
|
Chris@0
|
307
|
Chris@0
|
308 if ($lcs == 0) {
|
Chris@0
|
309 // X and Y sequences have no common subsequence:
|
Chris@0
|
310 // mark all changed.
|
Chris@0
|
311 while ($yoff < $ylim) {
|
Chris@0
|
312 $this->ychanged[$this->yind[$yoff++]] = 1;
|
Chris@0
|
313 }
|
Chris@0
|
314 while ($xoff < $xlim) {
|
Chris@0
|
315 $this->xchanged[$this->xind[$xoff++]] = 1;
|
Chris@0
|
316 }
|
Chris@0
|
317 }
|
Chris@0
|
318 else {
|
Chris@0
|
319 // Use the partitions to split this problem into subproblems.
|
Chris@0
|
320 reset($seps);
|
Chris@0
|
321 $pt1 = $seps[0];
|
Chris@0
|
322 while ($pt2 = next($seps)) {
|
Chris@0
|
323 $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
|
Chris@0
|
324 $pt1 = $pt2;
|
Chris@0
|
325 }
|
Chris@0
|
326 }
|
Chris@0
|
327 }
|
Chris@0
|
328
|
Chris@0
|
329 /**
|
Chris@0
|
330 * Adjust inserts/deletes of identical lines to join changes
|
Chris@0
|
331 * as much as possible.
|
Chris@0
|
332 *
|
Chris@0
|
333 * We do something when a run of changed lines include a
|
Chris@0
|
334 * line at one end and has an excluded, identical line at the other.
|
Chris@0
|
335 * We are free to choose which identical line is included.
|
Chris@0
|
336 * `compareseq' usually chooses the one at the beginning,
|
Chris@0
|
337 * but usually it is cleaner to consider the following identical line
|
Chris@0
|
338 * to be the "change".
|
Chris@0
|
339 *
|
Chris@0
|
340 * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
|
Chris@0
|
341 */
|
Chris@0
|
342 protected function _shift_boundaries($lines, &$changed, $other_changed) {
|
Chris@0
|
343 $i = 0;
|
Chris@0
|
344 $j = 0;
|
Chris@0
|
345
|
Chris@14
|
346 $this::USE_ASSERTS && assert(sizeof($lines) == sizeof($changed));
|
Chris@0
|
347 $len = sizeof($lines);
|
Chris@0
|
348 $other_len = sizeof($other_changed);
|
Chris@0
|
349
|
Chris@0
|
350 while (1) {
|
Chris@0
|
351 /*
|
Chris@0
|
352 * Scan forwards to find beginning of another run of changes.
|
Chris@0
|
353 * Also keep track of the corresponding point in the other file.
|
Chris@0
|
354 *
|
Chris@0
|
355 * Throughout this code, $i and $j are adjusted together so that
|
Chris@0
|
356 * the first $i elements of $changed and the first $j elements
|
Chris@0
|
357 * of $other_changed both contain the same number of zeros
|
Chris@0
|
358 * (unchanged lines).
|
Chris@0
|
359 * Furthermore, $j is always kept so that $j == $other_len or
|
Chris@0
|
360 * $other_changed[$j] == FALSE.
|
Chris@0
|
361 */
|
Chris@0
|
362 while ($j < $other_len && $other_changed[$j]) {
|
Chris@0
|
363 $j++;
|
Chris@0
|
364 }
|
Chris@0
|
365 while ($i < $len && !$changed[$i]) {
|
Chris@14
|
366 $this::USE_ASSERTS && assert($j < $other_len && ! $other_changed[$j]);
|
Chris@0
|
367 $i++;
|
Chris@0
|
368 $j++;
|
Chris@0
|
369 while ($j < $other_len && $other_changed[$j]) {
|
Chris@0
|
370 $j++;
|
Chris@0
|
371 }
|
Chris@0
|
372 }
|
Chris@0
|
373
|
Chris@0
|
374 if ($i == $len) {
|
Chris@0
|
375 break;
|
Chris@0
|
376 }
|
Chris@0
|
377 $start = $i;
|
Chris@0
|
378
|
Chris@0
|
379 // Find the end of this run of changes.
|
Chris@0
|
380 while (++$i < $len && $changed[$i]) {
|
Chris@0
|
381 continue;
|
Chris@0
|
382 }
|
Chris@0
|
383
|
Chris@0
|
384 do {
|
Chris@0
|
385 /*
|
Chris@0
|
386 * Record the length of this run of changes, so that
|
Chris@0
|
387 * we can later determine whether the run has grown.
|
Chris@0
|
388 */
|
Chris@0
|
389 $runlength = $i - $start;
|
Chris@0
|
390
|
Chris@0
|
391 /*
|
Chris@0
|
392 * Move the changed region back, so long as the
|
Chris@0
|
393 * previous unchanged line matches the last changed one.
|
Chris@0
|
394 * This merges with previous changed regions.
|
Chris@0
|
395 */
|
Chris@0
|
396 while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
|
Chris@0
|
397 $changed[--$start] = 1;
|
Chris@0
|
398 $changed[--$i] = FALSE;
|
Chris@0
|
399 while ($start > 0 && $changed[$start - 1]) {
|
Chris@0
|
400 $start--;
|
Chris@0
|
401 }
|
Chris@14
|
402 $this::USE_ASSERTS && assert($j > 0);
|
Chris@0
|
403 while ($other_changed[--$j]) {
|
Chris@0
|
404 continue;
|
Chris@0
|
405 }
|
Chris@14
|
406 $this::USE_ASSERTS && assert($j >= 0 && !$other_changed[$j]);
|
Chris@0
|
407 }
|
Chris@0
|
408
|
Chris@0
|
409 /*
|
Chris@0
|
410 * Set CORRESPONDING to the end of the changed run, at the last
|
Chris@0
|
411 * point where it corresponds to a changed run in the other file.
|
Chris@0
|
412 * CORRESPONDING == LEN means no such point has been found.
|
Chris@0
|
413 */
|
Chris@0
|
414 $corresponding = $j < $other_len ? $i : $len;
|
Chris@0
|
415
|
Chris@0
|
416 /*
|
Chris@0
|
417 * Move the changed region forward, so long as the
|
Chris@0
|
418 * first changed line matches the following unchanged one.
|
Chris@0
|
419 * This merges with following changed regions.
|
Chris@0
|
420 * Do this second, so that if there are no merges,
|
Chris@0
|
421 * the changed region is moved forward as far as possible.
|
Chris@0
|
422 */
|
Chris@0
|
423 while ($i < $len && $lines[$start] == $lines[$i]) {
|
Chris@0
|
424 $changed[$start++] = FALSE;
|
Chris@0
|
425 $changed[$i++] = 1;
|
Chris@0
|
426 while ($i < $len && $changed[$i]) {
|
Chris@0
|
427 $i++;
|
Chris@0
|
428 }
|
Chris@14
|
429 $this::USE_ASSERTS && assert($j < $other_len && ! $other_changed[$j]);
|
Chris@0
|
430 $j++;
|
Chris@0
|
431 if ($j < $other_len && $other_changed[$j]) {
|
Chris@0
|
432 $corresponding = $i;
|
Chris@0
|
433 while ($j < $other_len && $other_changed[$j]) {
|
Chris@0
|
434 $j++;
|
Chris@0
|
435 }
|
Chris@0
|
436 }
|
Chris@0
|
437 }
|
Chris@0
|
438 } while ($runlength != $i - $start);
|
Chris@0
|
439
|
Chris@0
|
440 /*
|
Chris@0
|
441 * If possible, move the fully-merged run of changes
|
Chris@0
|
442 * back to a corresponding run in the other file.
|
Chris@0
|
443 */
|
Chris@0
|
444 while ($corresponding < $i) {
|
Chris@0
|
445 $changed[--$start] = 1;
|
Chris@0
|
446 $changed[--$i] = 0;
|
Chris@14
|
447 $this::USE_ASSERTS && assert($j > 0);
|
Chris@0
|
448 while ($other_changed[--$j]) {
|
Chris@0
|
449 continue;
|
Chris@0
|
450 }
|
Chris@14
|
451 $this::USE_ASSERTS && assert($j >= 0 && !$other_changed[$j]);
|
Chris@0
|
452 }
|
Chris@0
|
453 }
|
Chris@0
|
454 }
|
Chris@0
|
455
|
Chris@0
|
456 }
|