These results are based on our legacy PHP analysis, consider migrating to our new PHP analysis engine instead. Learn more
1 | <?php |
||
2 | /** |
||
3 | * Text_Diff |
||
4 | * |
||
5 | * General API for generating and formatting diffs - the differences between |
||
6 | * two sequences of strings. |
||
7 | * |
||
8 | * The PHP diff code used in this package was originally written by Geoffrey |
||
9 | * T. Dairiki and is used with his permission. |
||
10 | * |
||
11 | * $Horde: framework/Text_Diff/Diff.php,v 1.13 2005/05/26 20:26:06 selsky Exp $ |
||
12 | * |
||
13 | * @package Text_Diff |
||
14 | * @author Geoffrey T. Dairiki <[email protected]> |
||
15 | */ |
||
16 | class Text_Diff { |
||
17 | |||
18 | /** |
||
19 | * Array of changes. |
||
20 | * |
||
21 | * @var array |
||
22 | */ |
||
23 | var $_edits; |
||
24 | |||
25 | /** |
||
26 | * Computes diffs between sequences of strings. |
||
27 | * |
||
28 | * @param array $from_lines An array of strings. Typically these are |
||
29 | * lines from a file. |
||
30 | * @param array $to_lines An array of strings. |
||
31 | */ |
||
32 | function __construct($from_lines, $to_lines) |
||
33 | { |
||
34 | array_walk($from_lines, array($this, '_trimNewlines')); |
||
35 | array_walk($to_lines, array($this, '_trimNewlines')); |
||
36 | |||
37 | if (extension_loaded('xdiff')) { |
||
38 | $engine = new Text_Diff_Engine_xdiff(); |
||
39 | } else { |
||
40 | $engine = new Text_Diff_Engine_native(); |
||
41 | } |
||
42 | |||
43 | $this->_edits = $engine->diff($from_lines, $to_lines); |
||
44 | } |
||
45 | |||
46 | /** |
||
47 | * Returns the array of differences. |
||
48 | */ |
||
49 | function getDiff() |
||
50 | { |
||
51 | return $this->_edits; |
||
52 | } |
||
53 | |||
54 | /** |
||
55 | * Computes a reversed diff. |
||
56 | * |
||
57 | * Example: |
||
58 | * <code> |
||
59 | * $diff = &new Text_Diff($lines1, $lines2); |
||
60 | * $rev = $diff->reverse(); |
||
61 | * </code> |
||
62 | * |
||
63 | * @return Text_Diff A Diff object representing the inverse of the |
||
64 | * original diff. Note that we purposely don't return a |
||
65 | * reference here, since this essentially is a clone() |
||
66 | * method. |
||
67 | */ |
||
68 | function reverse() |
||
69 | { |
||
70 | if (version_compare(zend_version(), '2', '>')) { |
||
71 | $rev = clone$obj; |
||
72 | } else { |
||
73 | $rev = $this; |
||
74 | } |
||
75 | $rev->_edits = array(); |
||
76 | foreach ($this->_edits as $edit) { |
||
77 | $rev->_edits[] = $edit->reverse(); |
||
78 | } |
||
79 | |||
80 | return $rev; |
||
81 | } |
||
82 | |||
83 | /** |
||
84 | * Checks for an empty diff. |
||
85 | * |
||
86 | * @return boolean True if two sequences were identical. |
||
87 | */ |
||
88 | function isEmpty() |
||
89 | { |
||
90 | foreach ($this->_edits as $edit) { |
||
91 | if (!is_a($edit, 'Text_Diff_Op_copy')) { |
||
92 | return false; |
||
93 | } |
||
94 | } |
||
95 | |||
96 | return true; |
||
97 | } |
||
98 | |||
99 | /** |
||
100 | * Computes the length of the Longest Common Subsequence (LCS). |
||
101 | * |
||
102 | * This is mostly for diagnostic purposes. |
||
103 | * |
||
104 | * @return integer The length of the LCS. |
||
105 | */ |
||
106 | function lcs() |
||
107 | { |
||
108 | $lcs = 0; |
||
109 | foreach ($this->_edits as $edit) { |
||
110 | if (is_a($edit, 'Text_Diff_Op_copy')) { |
||
111 | $lcs += count($edit->orig); |
||
112 | } |
||
113 | } |
||
114 | |||
115 | return $lcs; |
||
116 | } |
||
117 | |||
118 | /** |
||
119 | * Gets the original set of lines. |
||
120 | * |
||
121 | * This reconstructs the $from_lines parameter passed to the constructor. |
||
122 | * |
||
123 | * @return array The original sequence of strings. |
||
124 | */ |
||
125 | View Code Duplication | function getOriginal() |
|
126 | { |
||
127 | $lines = array(); |
||
128 | foreach ($this->_edits as $edit) { |
||
129 | if ($edit->orig) { |
||
130 | array_splice($lines, count($lines), 0, $edit->orig); |
||
131 | } |
||
132 | } |
||
133 | |||
134 | return $lines; |
||
135 | } |
||
136 | |||
137 | /** |
||
138 | * Gets the final set of lines. |
||
139 | * |
||
140 | * This reconstructs the $to_lines parameter passed to the constructor. |
||
141 | * |
||
142 | * @return array The sequence of strings. |
||
143 | */ |
||
144 | View Code Duplication | function getFinal() |
|
145 | { |
||
146 | $lines = array(); |
||
147 | foreach ($this->_edits as $edit) { |
||
148 | if ($edit->final) { |
||
149 | array_splice($lines, count($lines), 0, $edit->final); |
||
150 | } |
||
151 | } |
||
152 | |||
153 | return $lines; |
||
154 | } |
||
155 | |||
156 | /** |
||
157 | * Removes trailing newlines from a line of text. This is meant to be used |
||
158 | * with array_walk(). |
||
159 | * |
||
160 | * @param string $line The line to trim. |
||
161 | * @param integer $key The index of the line in the array. Not used. |
||
162 | */ |
||
163 | function _trimNewlines(&$line, $key) |
||
164 | { |
||
165 | $line = str_replace(array("\n", "\r"), '', $line); |
||
166 | } |
||
167 | |||
168 | /** |
||
169 | * Checks a diff for validity. |
||
170 | * |
||
171 | * This is here only for debugging purposes. |
||
172 | */ |
||
173 | function _check($from_lines, $to_lines) |
||
174 | { |
||
175 | if (serialize($from_lines) != serialize($this->getOriginal())) { |
||
176 | trigger_error("Reconstructed original doesn't match", E_USER_ERROR); |
||
177 | } |
||
178 | if (serialize($to_lines) != serialize($this->getFinal())) { |
||
179 | trigger_error("Reconstructed final doesn't match", E_USER_ERROR); |
||
180 | } |
||
181 | |||
182 | $rev = $this->reverse(); |
||
183 | if (serialize($to_lines) != serialize($rev->getOriginal())) { |
||
184 | trigger_error("Reversed original doesn't match", E_USER_ERROR); |
||
185 | } |
||
186 | if (serialize($from_lines) != serialize($rev->getFinal())) { |
||
187 | trigger_error("Reversed final doesn't match", E_USER_ERROR); |
||
188 | } |
||
189 | |||
190 | $prevtype = null; |
||
191 | foreach ($this->_edits as $edit) { |
||
192 | if ($prevtype == get_class($edit)) { |
||
193 | trigger_error('Edit sequence is non-optimal', E_USER_ERROR); |
||
194 | } |
||
195 | $prevtype = get_class($edit); |
||
196 | } |
||
197 | |||
198 | return true; |
||
199 | } |
||
200 | |||
201 | } |
||
202 | |||
203 | /** |
||
204 | * $Horde: framework/Text_Diff/Diff.php,v 1.13 2005/05/26 20:26:06 selsky Exp $ |
||
205 | * |
||
206 | * @package Text_Diff |
||
207 | * @author Geoffrey T. Dairiki <[email protected]> |
||
208 | */ |
||
209 | class Text_MappedDiff extends Text_Diff { |
||
210 | |||
211 | /** |
||
212 | * Computes a diff between sequences of strings. |
||
213 | * |
||
214 | * This can be used to compute things like case-insensitve diffs, or diffs |
||
215 | * which ignore changes in white-space. |
||
216 | * |
||
217 | * @param array $from_lines An array of strings. |
||
218 | * @param array $to_lines An array of strings. |
||
219 | * @param array $mapped_from_lines This array should have the same size |
||
220 | * number of elements as $from_lines. The |
||
221 | * elements in $mapped_from_lines and |
||
222 | * $mapped_to_lines are what is actually |
||
223 | * compared when computing the diff. |
||
224 | * @param array $mapped_to_lines This array should have the same number |
||
225 | * of elements as $to_lines. |
||
226 | */ |
||
227 | function __construct($from_lines, $to_lines, |
||
228 | $mapped_from_lines, $mapped_to_lines) |
||
229 | { |
||
230 | assert(count($from_lines) == count($mapped_from_lines)); |
||
231 | assert(count($to_lines) == count($mapped_to_lines)); |
||
232 | |||
233 | parent::Text_Diff($mapped_from_lines, $mapped_to_lines); |
||
234 | |||
235 | $xi = $yi = 0; |
||
236 | for ($i = 0; $i < count($this->_edits); $i++) { |
||
237 | $orig = &$this->_edits[$i]->orig; |
||
238 | if (is_array($orig)) { |
||
239 | $orig = array_slice($from_lines, $xi, count($orig)); |
||
240 | $xi += count($orig); |
||
241 | } |
||
242 | |||
243 | $final = &$this->_edits[$i]->final; |
||
244 | if (is_array($final)) { |
||
245 | $final = array_slice($to_lines, $yi, count($final)); |
||
246 | $yi += count($final); |
||
247 | } |
||
248 | } |
||
249 | } |
||
250 | |||
251 | } |
||
252 | |||
253 | /** |
||
254 | * Class used internally by Diff to actually compute the diffs. This class |
||
255 | * uses the xdiff PECL package (http://pecl.php.net/package/xdiff) to compute |
||
256 | * the differences between the two input arrays. |
||
257 | * |
||
258 | * @author Jon Parise <[email protected]> |
||
259 | * @package Text_Diff |
||
260 | * |
||
261 | * @access private |
||
262 | */ |
||
263 | class Text_Diff_Engine_xdiff { |
||
264 | |||
265 | function diff($from_lines, $to_lines) |
||
266 | { |
||
267 | /* Convert the two input arrays into strings for xdiff processing. */ |
||
268 | $from_string = implode("\n", $from_lines); |
||
269 | $to_string = implode("\n", $to_lines); |
||
270 | |||
271 | /* Diff the two strings and convert the result to an array. */ |
||
272 | $diff = xdiff_string_diff($from_string, $to_string, count($to_lines)); |
||
273 | $diff = explode("\n", $diff); |
||
274 | |||
275 | /* Walk through the diff one line at a time. We build the $edits |
||
276 | * array of diff operations by reading the first character of the |
||
277 | * xdiff output (which is in the "unified diff" format). |
||
278 | * |
||
279 | * Note that we don't have enough information to detect "changed" |
||
280 | * lines using this approach, so we can't add Text_Diff_Op_changed |
||
281 | * instances to the $edits array. The result is still perfectly |
||
282 | * valid, albeit a little less descriptive and efficient. */ |
||
283 | $edits = array(); |
||
284 | foreach ($diff as $line) { |
||
285 | switch ($line[0]) { |
||
286 | case ' ': |
||
287 | $edits[] = new Text_Diff_Op_copy(array(substr($line, 1))); |
||
288 | break; |
||
289 | |||
290 | case '+': |
||
291 | $edits[] = new Text_Diff_Op_add(array(substr($line, 1))); |
||
292 | break; |
||
293 | |||
294 | case '-': |
||
295 | $edits[] = new Text_Diff_Op_delete(array(substr($line, 1))); |
||
296 | break; |
||
297 | } |
||
298 | } |
||
299 | |||
300 | return $edits; |
||
301 | } |
||
302 | |||
303 | } |
||
304 | |||
305 | /** |
||
306 | * Class used internally by Diff to actually compute the diffs. This class is |
||
307 | * implemented using native PHP code. |
||
308 | * |
||
309 | * The algorithm used here is mostly lifted from the perl module |
||
310 | * Algorithm::Diff (version 1.06) by Ned Konz, which is available at: |
||
311 | * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip |
||
312 | * |
||
313 | * More ideas are taken from: |
||
314 | * http://www.ics.uci.edu/~eppstein/161/960229.html |
||
315 | * |
||
316 | * Some ideas (and a bit of code) are taken from analyze.c, of GNU |
||
317 | * diffutils-2.7, which can be found at: |
||
318 | * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz |
||
319 | * |
||
320 | * Some ideas (subdivision by NCHUNKS > 2, and some optimizations) are from |
||
321 | * Geoffrey T. Dairiki <[email protected]>. The original PHP version of this |
||
322 | * code was written by him, and is used/adapted with his permission. |
||
323 | * |
||
324 | * @author Geoffrey T. Dairiki <[email protected]> |
||
325 | * @package Text_Diff |
||
326 | * |
||
327 | * @access private |
||
328 | */ |
||
329 | class Text_Diff_Engine_native { |
||
330 | |||
331 | function diff($from_lines, $to_lines) |
||
332 | { |
||
333 | $n_from = count($from_lines); |
||
334 | $n_to = count($to_lines); |
||
335 | |||
336 | $this->xchanged = $this->ychanged = array(); |
||
337 | $this->xv = $this->yv = array(); |
||
338 | $this->xind = $this->yind = array(); |
||
339 | unset($this->seq); |
||
340 | unset($this->in_seq); |
||
341 | unset($this->lcs); |
||
342 | |||
343 | // Skip leading common lines. |
||
344 | for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) { |
||
345 | if ($from_lines[$skip] != $to_lines[$skip]) { |
||
346 | break; |
||
347 | } |
||
348 | $this->xchanged[$skip] = $this->ychanged[$skip] = false; |
||
349 | } |
||
350 | |||
351 | // Skip trailing common lines. |
||
352 | $xi = $n_from; $yi = $n_to; |
||
353 | for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) { |
||
354 | if ($from_lines[$xi] != $to_lines[$yi]) { |
||
355 | break; |
||
356 | } |
||
357 | $this->xchanged[$xi] = $this->ychanged[$yi] = false; |
||
358 | } |
||
359 | |||
360 | // Ignore lines which do not exist in both files. |
||
361 | for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { |
||
362 | $xhash[$from_lines[$xi]] = 1; |
||
363 | } |
||
364 | for ($yi = $skip; $yi < $n_to - $endskip; $yi++) { |
||
365 | $line = $to_lines[$yi]; |
||
366 | if ($this->ychanged[$yi] = empty($xhash[$line])) { |
||
367 | continue; |
||
368 | } |
||
369 | $yhash[$line] = 1; |
||
370 | $this->yv[] = $line; |
||
371 | $this->yind[] = $yi; |
||
372 | } |
||
373 | for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { |
||
374 | $line = $from_lines[$xi]; |
||
375 | if ($this->xchanged[$xi] = empty($yhash[$line])) { |
||
376 | continue; |
||
377 | } |
||
378 | $this->xv[] = $line; |
||
379 | $this->xind[] = $xi; |
||
380 | } |
||
381 | |||
382 | // Find the LCS. |
||
383 | $this->_compareseq(0, count($this->xv), 0, count($this->yv)); |
||
384 | |||
385 | // Merge edits when possible. |
||
386 | $this->_shiftBoundaries($from_lines, $this->xchanged, $this->ychanged); |
||
387 | $this->_shiftBoundaries($to_lines, $this->ychanged, $this->xchanged); |
||
388 | |||
389 | // Compute the edit operations. |
||
390 | $edits = array(); |
||
391 | $xi = $yi = 0; |
||
392 | while ($xi < $n_from || $yi < $n_to) { |
||
393 | assert($yi < $n_to || $this->xchanged[$xi]); |
||
394 | assert($xi < $n_from || $this->ychanged[$yi]); |
||
395 | |||
396 | // Skip matching "snake". |
||
397 | $copy = array(); |
||
398 | while ($xi < $n_from && $yi < $n_to |
||
399 | && !$this->xchanged[$xi] && !$this->ychanged[$yi]) { |
||
400 | $copy[] = $from_lines[$xi++]; |
||
401 | ++$yi; |
||
402 | } |
||
403 | if ($copy) { |
||
404 | $edits[] = new Text_Diff_Op_copy($copy); |
||
405 | } |
||
406 | |||
407 | // Find deletes & adds. |
||
408 | $delete = array(); |
||
409 | while ($xi < $n_from && $this->xchanged[$xi]) { |
||
410 | $delete[] = $from_lines[$xi++]; |
||
411 | } |
||
412 | |||
413 | $add = array(); |
||
414 | while ($yi < $n_to && $this->ychanged[$yi]) { |
||
415 | $add[] = $to_lines[$yi++]; |
||
416 | } |
||
417 | |||
418 | if ($delete && $add) { |
||
419 | $edits[] = new Text_Diff_Op_change($delete, $add); |
||
420 | } elseif ($delete) { |
||
421 | $edits[] = new Text_Diff_Op_delete($delete); |
||
422 | } elseif ($add) { |
||
423 | $edits[] = new Text_Diff_Op_add($add); |
||
424 | } |
||
425 | } |
||
426 | |||
427 | return $edits; |
||
428 | } |
||
429 | |||
430 | /** |
||
431 | * Divides the Largest Common Subsequence (LCS) of the sequences (XOFF, |
||
432 | * XLIM) and (YOFF, YLIM) into NCHUNKS approximately equally sized |
||
433 | * segments. |
||
434 | * |
||
435 | * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an array of |
||
436 | * NCHUNKS+1 (X, Y) indexes giving the diving points between sub |
||
437 | * sequences. The first sub-sequence is contained in (X0, X1), (Y0, Y1), |
||
438 | * the second in (X1, X2), (Y1, Y2) and so on. Note that (X0, Y0) == |
||
439 | * (XOFF, YOFF) and (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM). |
||
440 | * |
||
441 | * This function assumes that the first lines of the specified portions of |
||
442 | * the two files do not match, and likewise that the last lines do not |
||
443 | * match. The caller must trim matching lines from the beginning and end |
||
444 | * of the portions it is going to specify. |
||
445 | */ |
||
446 | function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) |
||
447 | { |
||
448 | $flip = false; |
||
449 | |||
450 | if ($xlim - $xoff > $ylim - $yoff) { |
||
451 | /* Things seems faster (I'm not sure I understand why) when the |
||
452 | * shortest sequence is in X. */ |
||
453 | $flip = true; |
||
454 | list ($xoff, $xlim, $yoff, $ylim) |
||
455 | = array($yoff, $ylim, $xoff, $xlim); |
||
456 | } |
||
457 | |||
458 | if ($flip) { |
||
459 | for ($i = $ylim - 1; $i >= $yoff; $i--) { |
||
460 | $ymatches[$this->xv[$i]][] = $i; |
||
461 | } |
||
462 | } else { |
||
463 | for ($i = $ylim - 1; $i >= $yoff; $i--) { |
||
464 | $ymatches[$this->yv[$i]][] = $i; |
||
465 | } |
||
466 | } |
||
467 | |||
468 | $this->lcs = 0; |
||
469 | $this->seq[0]= $yoff - 1; |
||
470 | $this->in_seq = array(); |
||
471 | $ymids[0] = array(); |
||
472 | |||
473 | $numer = $xlim - $xoff + $nchunks - 1; |
||
474 | $x = $xoff; |
||
475 | for ($chunk = 0; $chunk < $nchunks; $chunk++) { |
||
476 | if ($chunk > 0) { |
||
477 | for ($i = 0; $i <= $this->lcs; $i++) { |
||
478 | $ymids[$i][$chunk - 1] = $this->seq[$i]; |
||
479 | } |
||
480 | } |
||
481 | |||
482 | $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks); |
||
483 | for (; $x < $x1; $x++) { |
||
484 | $line = $flip ? $this->yv[$x] : $this->xv[$x]; |
||
485 | if (empty($ymatches[$line])) { |
||
486 | continue; |
||
487 | } |
||
488 | $matches = $ymatches[$line]; |
||
489 | foreach ($matches as $y) { |
||
490 | View Code Duplication | if (empty($this->in_seq[$y])) { |
|
491 | $k = $this->_lcsPos($y); |
||
492 | assert($k > 0); |
||
493 | $ymids[$k] = $ymids[$k - 1]; |
||
494 | break; |
||
495 | } |
||
496 | } |
||
497 | |||
498 | while (list($junk, $y) = each($matches)) { |
||
499 | if ($y > $this->seq[$k - 1]) { |
||
500 | assert($y < $this->seq[$k]); |
||
501 | /* Optimization: this is a common case: next match is |
||
502 | * just replacing previous match. */ |
||
503 | $this->in_seq[$this->seq[$k]] = false; |
||
504 | $this->seq[$k] = $y; |
||
505 | $this->in_seq[$y] = 1; |
||
506 | View Code Duplication | } elseif (empty($this->in_seq[$y])) { |
|
507 | $k = $this->_lcsPos($y); |
||
508 | assert($k > 0); |
||
509 | $ymids[$k] = $ymids[$k - 1]; |
||
510 | } |
||
511 | } |
||
512 | } |
||
513 | } |
||
514 | |||
515 | $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff); |
||
516 | $ymid = $ymids[$this->lcs]; |
||
517 | for ($n = 0; $n < $nchunks - 1; $n++) { |
||
518 | $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks); |
||
519 | $y1 = $ymid[$n] + 1; |
||
520 | $seps[] = $flip ? array($y1, $x1) : array($x1, $y1); |
||
521 | } |
||
522 | $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim); |
||
523 | |||
524 | return array($this->lcs, $seps); |
||
525 | } |
||
526 | |||
527 | function _lcsPos($ypos) |
||
528 | { |
||
529 | $end = $this->lcs; |
||
530 | if ($end == 0 || $ypos > $this->seq[$end]) { |
||
531 | $this->seq[++$this->lcs] = $ypos; |
||
532 | $this->in_seq[$ypos] = 1; |
||
533 | |||
534 | return $this->lcs; |
||
535 | } |
||
536 | |||
537 | $beg = 1; |
||
538 | while ($beg < $end) { |
||
539 | $mid = (int)(($beg + $end) / 2); |
||
540 | if ($ypos > $this->seq[$mid]) { |
||
541 | $beg = $mid + 1; |
||
542 | } else { |
||
543 | $end = $mid; |
||
544 | } |
||
545 | } |
||
546 | |||
547 | assert($ypos != $this->seq[$end]); |
||
548 | |||
549 | $this->in_seq[$this->seq[$end]] = false; |
||
550 | $this->seq[$end] = $ypos; |
||
551 | $this->in_seq[$ypos] = 1; |
||
552 | |||
553 | return $end; |
||
554 | } |
||
555 | |||
556 | /** |
||
557 | * Finds LCS of two sequences. |
||
558 | * |
||
559 | * The results are recorded in the vectors $this->{x,y}changed[], by |
||
560 | * storing a 1 in the element for each line that is an insertion or |
||
561 | * deletion (ie. is not in the LCS). |
||
562 | * |
||
563 | * The subsequence of file 0 is (XOFF, XLIM) and likewise for file 1. |
||
564 | * |
||
565 | * Note that XLIM, YLIM are exclusive bounds. All line numbers are |
||
566 | * origin-0 and discarded lines are not counted. |
||
567 | */ |
||
568 | function _compareseq ($xoff, $xlim, $yoff, $ylim) |
||
569 | { |
||
570 | /* Slide down the bottom initial diagonal. */ |
||
571 | while ($xoff < $xlim && $yoff < $ylim |
||
572 | && $this->xv[$xoff] == $this->yv[$yoff]) { |
||
573 | ++$xoff; |
||
574 | ++$yoff; |
||
575 | } |
||
576 | |||
577 | /* Slide up the top initial diagonal. */ |
||
578 | while ($xlim > $xoff && $ylim > $yoff |
||
579 | && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) { |
||
580 | --$xlim; |
||
581 | --$ylim; |
||
582 | } |
||
583 | |||
584 | if ($xoff == $xlim || $yoff == $ylim) { |
||
585 | $lcs = 0; |
||
586 | } else { |
||
587 | /* This is ad hoc but seems to work well. $nchunks = |
||
588 | * sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); $nchunks = |
||
589 | * max(2,min(8,(int)$nchunks)); */ |
||
590 | $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1; |
||
591 | list($lcs, $seps) |
||
592 | = $this->_diag($xoff, $xlim, $yoff, $ylim, $nchunks); |
||
593 | } |
||
594 | |||
595 | if ($lcs == 0) { |
||
596 | /* X and Y sequences have no common subsequence: mark all |
||
597 | * changed. */ |
||
598 | while ($yoff < $ylim) { |
||
599 | $this->ychanged[$this->yind[$yoff++]] = 1; |
||
600 | } |
||
601 | while ($xoff < $xlim) { |
||
602 | $this->xchanged[$this->xind[$xoff++]] = 1; |
||
603 | } |
||
604 | } else { |
||
605 | /* Use the partitions to split this problem into subproblems. */ |
||
606 | reset($seps); |
||
607 | $pt1 = $seps[0]; |
||
608 | while ($pt2 = next($seps)) { |
||
609 | $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]); |
||
610 | $pt1 = $pt2; |
||
611 | } |
||
612 | } |
||
613 | } |
||
614 | |||
615 | /** |
||
616 | * Adjusts inserts/deletes of identical lines to join changes as much as |
||
617 | * possible. |
||
618 | * |
||
619 | * We do something when a run of changed lines include a line at one end |
||
620 | * and has an excluded, identical line at the other. We are free to |
||
621 | * choose which identical line is included. `compareseq' usually chooses |
||
622 | * the one at the beginning, but usually it is cleaner to consider the |
||
623 | * following identical line to be the "change". |
||
624 | * |
||
625 | * This is extracted verbatim from analyze.c (GNU diffutils-2.7). |
||
626 | */ |
||
627 | function _shiftBoundaries($lines, &$changed, $other_changed) |
||
628 | { |
||
629 | $i = 0; |
||
630 | $j = 0; |
||
631 | |||
632 | assert('count($lines) == count($changed)'); |
||
633 | $len = count($lines); |
||
634 | $other_len = count($other_changed); |
||
635 | |||
636 | while (1) { |
||
637 | /* Scan forward to find the beginning of another run of |
||
638 | * changes. Also keep track of the corresponding point in the |
||
639 | * other file. |
||
640 | * |
||
641 | * Throughout this code, $i and $j are adjusted together so that |
||
642 | * the first $i elements of $changed and the first $j elements of |
||
643 | * $other_changed both contain the same number of zeros (unchanged |
||
644 | * lines). |
||
645 | * |
||
646 | * Furthermore, $j is always kept so that $j == $other_len or |
||
647 | * $other_changed[$j] == false. */ |
||
648 | while ($j < $other_len && $other_changed[$j]) { |
||
649 | $j++; |
||
650 | } |
||
651 | |||
652 | while ($i < $len && ! $changed[$i]) { |
||
653 | assert('$j < $other_len && ! $other_changed[$j]'); |
||
654 | $i++; $j++; |
||
655 | while ($j < $other_len && $other_changed[$j]) { |
||
656 | $j++; |
||
657 | } |
||
658 | } |
||
659 | |||
660 | if ($i == $len) { |
||
661 | break; |
||
662 | } |
||
663 | |||
664 | $start = $i; |
||
665 | |||
666 | /* Find the end of this run of changes. */ |
||
667 | while (++$i < $len && $changed[$i]) { |
||
668 | continue; |
||
669 | } |
||
670 | |||
671 | do { |
||
672 | /* Record the length of this run of changes, so that we can |
||
673 | * later determine whether the run has grown. */ |
||
674 | $runlength = $i - $start; |
||
675 | |||
676 | /* Move the changed region back, so long as the previous |
||
677 | * unchanged line matches the last changed one. This merges |
||
678 | * with previous changed regions. */ |
||
679 | while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) { |
||
680 | $changed[--$start] = 1; |
||
681 | $changed[--$i] = false; |
||
682 | while ($start > 0 && $changed[$start - 1]) { |
||
683 | $start--; |
||
684 | } |
||
685 | assert('$j > 0'); |
||
686 | while ($other_changed[--$j]) { |
||
687 | continue; |
||
688 | } |
||
689 | assert('$j >= 0 && !$other_changed[$j]'); |
||
690 | } |
||
691 | |||
692 | /* Set CORRESPONDING to the end of the changed run, at the |
||
693 | * last point where it corresponds to a changed run in the |
||
694 | * other file. CORRESPONDING == LEN means no such point has |
||
695 | * been found. */ |
||
696 | $corresponding = $j < $other_len ? $i : $len; |
||
697 | |||
698 | /* Move the changed region forward, so long as the first |
||
699 | * changed line matches the following unchanged one. This |
||
700 | * merges with following changed regions. Do this second, so |
||
701 | * that if there are no merges, the changed region is moved |
||
702 | * forward as far as possible. */ |
||
703 | while ($i < $len && $lines[$start] == $lines[$i]) { |
||
704 | $changed[$start++] = false; |
||
705 | $changed[$i++] = 1; |
||
706 | while ($i < $len && $changed[$i]) { |
||
707 | $i++; |
||
708 | } |
||
709 | |||
710 | assert('$j < $other_len && ! $other_changed[$j]'); |
||
711 | $j++; |
||
712 | if ($j < $other_len && $other_changed[$j]) { |
||
713 | $corresponding = $i; |
||
714 | while ($j < $other_len && $other_changed[$j]) { |
||
715 | $j++; |
||
716 | } |
||
717 | } |
||
718 | } |
||
719 | } while ($runlength != $i - $start); |
||
720 | |||
721 | /* If possible, move the fully-merged run of changes back to a |
||
722 | * corresponding run in the other file. */ |
||
723 | while ($corresponding < $i) { |
||
724 | $changed[--$start] = 1; |
||
725 | $changed[--$i] = 0; |
||
726 | assert('$j > 0'); |
||
727 | while ($other_changed[--$j]) { |
||
728 | continue; |
||
729 | } |
||
730 | assert('$j >= 0 && !$other_changed[$j]'); |
||
731 | } |
||
732 | } |
||
733 | } |
||
734 | |||
735 | } |
||
736 | |||
737 | /** |
||
738 | * @package Text_Diff |
||
739 | * @author Geoffrey T. Dairiki <[email protected]> |
||
740 | * |
||
741 | * @access private |
||
742 | */ |
||
743 | class Text_Diff_Op { |
||
744 | |||
745 | var $orig; |
||
746 | var $final; |
||
747 | |||
748 | function reverse() |
||
749 | { |
||
750 | trigger_error('Abstract method', E_USER_ERROR); |
||
751 | } |
||
752 | |||
753 | function norig() |
||
754 | { |
||
755 | return $this->orig ? count($this->orig) : 0; |
||
756 | } |
||
757 | |||
758 | function nfinal() |
||
759 | { |
||
760 | return $this->final ? count($this->final) : 0; |
||
761 | } |
||
762 | |||
763 | } |
||
764 | |||
765 | /** |
||
766 | * @package Text_Diff |
||
767 | * @author Geoffrey T. Dairiki <[email protected]> |
||
768 | * |
||
769 | * @access private |
||
770 | */ |
||
771 | class Text_Diff_Op_copy extends Text_Diff_Op { |
||
772 | |||
773 | function __construct($orig, $final = false) |
||
774 | { |
||
775 | if (!is_array($final)) { |
||
776 | $final = $orig; |
||
777 | } |
||
778 | $this->orig = $orig; |
||
779 | $this->final = $final; |
||
780 | } |
||
781 | |||
782 | function &reverse() |
||
783 | { |
||
784 | return $reverse = new Text_Diff_Op_copy($this->final, $this->orig); |
||
0 ignored issues
–
show
|
|||
785 | } |
||
786 | |||
787 | } |
||
788 | |||
789 | /** |
||
790 | * @package Text_Diff |
||
791 | * @author Geoffrey T. Dairiki <[email protected]> |
||
792 | * |
||
793 | * @access private |
||
794 | */ |
||
795 | View Code Duplication | class Text_Diff_Op_delete extends Text_Diff_Op { |
|
796 | |||
797 | function Text_Diff_Op_delete($lines) |
||
798 | { |
||
799 | $this->orig = $lines; |
||
800 | $this->final = false; |
||
801 | } |
||
802 | |||
803 | function &reverse() |
||
804 | { |
||
805 | return $reverse = &new Text_Diff_Op_add($this->orig); |
||
806 | } |
||
807 | |||
808 | } |
||
809 | |||
810 | /** |
||
811 | * @package Text_Diff |
||
812 | * @author Geoffrey T. Dairiki <[email protected]> |
||
813 | * |
||
814 | * @access private |
||
815 | */ |
||
816 | View Code Duplication | class Text_Diff_Op_add extends Text_Diff_Op { |
|
817 | |||
818 | function __construct($lines) |
||
819 | { |
||
820 | $this->final = $lines; |
||
821 | $this->orig = false; |
||
822 | } |
||
823 | |||
824 | function &reverse() |
||
825 | { |
||
826 | return $reverse = new Text_Diff_Op_delete($this->final); |
||
0 ignored issues
–
show
$reverse is not used, you could remove the assignment.
This check looks for variable assignements that are either overwritten by other assignments or where the variable is not used subsequently. $myVar = 'Value';
$higher = false;
if (rand(1, 6) > 3) {
$higher = true;
} else {
$higher = false;
}
Both the ![]() |
|||
827 | } |
||
828 | |||
829 | } |
||
830 | |||
831 | /** |
||
832 | * @package Text_Diff |
||
833 | * @author Geoffrey T. Dairiki <[email protected]> |
||
834 | * |
||
835 | * @access private |
||
836 | */ |
||
837 | class Text_Diff_Op_change extends Text_Diff_Op { |
||
838 | |||
839 | function __construct($orig, $final) |
||
840 | { |
||
841 | $this->orig = $orig; |
||
842 | $this->final = $final; |
||
843 | } |
||
844 | |||
845 | function &reverse() |
||
846 | { |
||
847 | return $reverse = new Text_Diff_Op_change($this->final, $this->orig); |
||
0 ignored issues
–
show
$reverse is not used, you could remove the assignment.
This check looks for variable assignements that are either overwritten by other assignments or where the variable is not used subsequently. $myVar = 'Value';
$higher = false;
if (rand(1, 6) > 3) {
$higher = true;
} else {
$higher = false;
}
Both the ![]() |
|||
848 | } |
||
849 | |||
850 | } |
||
851 |
This check looks for variable assignements that are either overwritten by other assignments or where the variable is not used subsequently.
Both the
$myVar
assignment in line 1 and the$higher
assignment in line 2 are dead. The first because$myVar
is never used and the second because$higher
is always overwritten for every possible time line.