3 * New version of the difference engine
5 * Copyright © 2008 Guy Van den Broeck <guy@guyvdb.eu>
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 * http://www.gnu.org/copyleft/gpl.html
23 * @ingroup DifferenceEngine
27 * This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which
28 * in turn is based on Myers' "An O(ND) difference algorithm and its variations"
29 * (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al.'s
30 * "An O(NP) Sequence Comparison Algorithm").
32 * This implementation supports an upper bound on the execution time.
34 * Some ideas (and a bit of code) are from analyze.c, from GNU
35 * diffutils-2.7, which can be found at:
36 * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
38 * Complexity: O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space
40 * @author Guy Van den Broeck, Geoffrey T. Dairiki, Tim Starling
41 * @ingroup DifferenceEngine
55 private $maxDifferences;
56 private $lcsLengthCorrectedForHeuristic = false;
62 public $heuristicUsed;
64 function __construct( $tooLong = 2000000, $powLimit = 1.45 ) {
65 $this->tooLong
= $tooLong;
66 $this->powLimit
= $powLimit;
70 * @param string[] $from_lines
71 * @param string[] $to_lines
75 public function diff( $from_lines, $to_lines ) {
77 // Diff and store locally
78 $this->diffInternal( $from_lines, $to_lines );
80 // Merge edits when possible
81 $this->shiftBoundaries( $from_lines, $this->removed
, $this->added
);
82 $this->shiftBoundaries( $to_lines, $this->added
, $this->removed
);
84 // Compute the edit operations.
85 $n_from = count( $from_lines );
86 $n_to = count( $to_lines );
90 while ( $xi < $n_from ||
$yi < $n_to ) {
91 assert( $yi < $n_to ||
$this->removed
[$xi] );
92 assert( $xi < $n_from ||
$this->added
[$yi] );
94 // Skip matching "snake".
96 while ( $xi < $n_from && $yi < $n_to
97 && !$this->removed
[$xi] && !$this->added
[$yi]
99 $copy[] = $from_lines[$xi++
];
103 $edits[] = new DiffOpCopy( $copy );
106 // Find deletes & adds.
108 while ( $xi < $n_from && $this->removed
[$xi] ) {
109 $delete[] = $from_lines[$xi++
];
113 while ( $yi < $n_to && $this->added
[$yi] ) {
114 $add[] = $to_lines[$yi++
];
117 if ( $delete && $add ) {
118 $edits[] = new DiffOpChange( $delete, $add );
119 } elseif ( $delete ) {
120 $edits[] = new DiffOpDelete( $delete );
122 $edits[] = new DiffOpAdd( $add );
130 * Adjust inserts/deletes of identical lines to join changes
131 * as much as possible.
133 * We do something when a run of changed lines include a
134 * line at one end and has an excluded, identical line at the other.
135 * We are free to choose which identical line is included.
136 * `compareseq' usually chooses the one at the beginning,
137 * but usually it is cleaner to consider the following identical line
138 * to be the "change".
140 * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
142 private function shiftBoundaries( $lines, &$changed, $other_changed ) {
146 assert( count( $lines ) == count( $changed ) );
147 $len = count( $lines );
148 $other_len = count( $other_changed );
152 * Scan forwards to find beginning of another run of changes.
153 * Also keep track of the corresponding point in the other file.
155 * Throughout this code, $i and $j are adjusted together so that
156 * the first $i elements of $changed and the first $j elements
157 * of $other_changed both contain the same number of zeros
159 * Furthermore, $j is always kept so that $j == $other_len or
160 * $other_changed[$j] == false.
162 while ( $j < $other_len && $other_changed[$j] ) {
166 while ( $i < $len && !$changed[$i] ) {
167 assert( $j < $other_len && ! $other_changed[$j] );
170 while ( $j < $other_len && $other_changed[$j] ) {
181 // Find the end of this run of changes.
182 while ( ++
$i < $len && $changed[$i] ) {
188 * Record the length of this run of changes, so that
189 * we can later determine whether the run has grown.
191 $runlength = $i - $start;
194 * Move the changed region back, so long as the
195 * previous unchanged line matches the last changed one.
196 * This merges with previous changed regions.
198 while ( $start > 0 && $lines[$start - 1] == $lines[$i - 1] ) {
199 $changed[--$start] = 1;
200 $changed[--$i] = false;
201 while ( $start > 0 && $changed[$start - 1] ) {
205 while ( $other_changed[--$j] ) {
208 assert( $j >= 0 && !$other_changed[$j] );
212 * Set CORRESPONDING to the end of the changed run, at the last
213 * point where it corresponds to a changed run in the other file.
214 * CORRESPONDING == LEN means no such point has been found.
216 $corresponding = $j < $other_len ?
$i : $len;
219 * Move the changed region forward, so long as the
220 * first changed line matches the following unchanged one.
221 * This merges with following changed regions.
222 * Do this second, so that if there are no merges,
223 * the changed region is moved forward as far as possible.
225 while ( $i < $len && $lines[$start] == $lines[$i] ) {
226 $changed[$start++
] = false;
228 while ( $i < $len && $changed[$i] ) {
232 assert( $j < $other_len && ! $other_changed[$j] );
234 if ( $j < $other_len && $other_changed[$j] ) {
236 while ( $j < $other_len && $other_changed[$j] ) {
241 } while ( $runlength != $i - $start );
244 * If possible, move the fully-merged run of changes
245 * back to a corresponding run in the other file.
247 while ( $corresponding < $i ) {
248 $changed[--$start] = 1;
251 while ( $other_changed[--$j] ) {
254 assert( $j >= 0 && !$other_changed[$j] );
259 protected function diffInternal( /*array*/ $from, /*array*/ $to ) {
260 // remember initial lengths
264 $this->heuristicUsed
= false;
267 $removed = $m > 0 ?
array_fill( 0, $m, true ) : [];
268 $added = $n > 0 ?
array_fill( 0, $n, true ) : [];
270 // reduce the complexity for the next step (intentionally done twice)
271 // remove common tokens at the start
273 while ( $i < $m && $i < $n && $from[$i] === $to[$i] ) {
274 $removed[$i] = $added[$i] = false;
275 unset( $from[$i], $to[$i] );
279 // remove common tokens at the end
281 while ( $i +
$j <= $m && $i +
$j <= $n && $from[$m - $j] === $to[$n - $j] ) {
282 $removed[$m - $j] = $added[$n - $j] = false;
283 unset( $from[$m - $j], $to[$n - $j] );
287 $this->from
= $newFromIndex = $this->to
= $newToIndex = [];
289 // remove tokens not in both sequences
291 foreach ( $from as $key ) {
292 $shared[$key] = false;
295 foreach ( $to as $index => &$el ) {
296 if ( array_key_exists( $el, $shared ) ) {
300 $newToIndex[] = $index;
303 foreach ( $from as $index => &$el ) {
304 if ( $shared[$el] ) {
307 $newFromIndex[] = $index;
311 unset( $shared, $from, $to );
313 $this->m
= count( $this->from
);
314 $this->n
= count( $this->to
);
316 $this->removed
= $this->m
> 0 ?
array_fill( 0, $this->m
, true ) : [];
317 $this->added
= $this->n
> 0 ?
array_fill( 0, $this->n
, true ) : [];
319 if ( $this->m
== 0 ||
$this->n
== 0 ) {
322 $this->maxDifferences
= ceil( ( $this->m +
$this->n
) / 2.0 );
323 if ( $this->m
* $this->n
> $this->tooLong
) {
324 // limit complexity to D^POW_LIMIT for long sequences
325 $this->maxDifferences
= floor( pow( $this->maxDifferences
, $this->powLimit
- 1.0 ) );
326 wfDebug( "Limiting max number of differences to $this->maxDifferences\n" );
330 * The common prefixes and suffixes are always part of some LCS, include
331 * them now to reduce our search space
333 $max = min( $this->m
, $this->n
);
334 for ( $forwardBound = 0; $forwardBound < $max
335 && $this->from
[$forwardBound] === $this->to
[$forwardBound];
338 $this->removed
[$forwardBound] = $this->added
[$forwardBound] = false;
341 $backBoundL1 = $this->m
- 1;
342 $backBoundL2 = $this->n
- 1;
344 while ( $backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
345 && $this->from
[$backBoundL1] === $this->to
[$backBoundL2]
347 $this->removed
[$backBoundL1--] = $this->added
[$backBoundL2--] = false;
350 $temp = array_fill( 0, $this->m +
$this->n +
1, 0 );
351 $V = [ $temp, $temp ];
352 $snake = [ 0, 0, 0 ];
354 $this->length
= $forwardBound +
$this->m
- $backBoundL1 - 1
368 $this->length +
= $i +
$j - 1;
370 foreach ( $this->removed
as $key => &$removed_elem ) {
371 if ( !$removed_elem ) {
372 $removed[$newFromIndex[$key]] = false;
375 foreach ( $this->added
as $key => &$added_elem ) {
376 if ( !$added_elem ) {
377 $added[$newToIndex[$key]] = false;
380 $this->removed
= $removed;
381 $this->added
= $added;
384 function diff_range( $from_lines, $to_lines ) {
385 // Diff and store locally
386 $this->diff( $from_lines, $to_lines );
387 unset( $from_lines, $to_lines );
391 while ( $xi < $this->m ||
$yi < $this->n
) {
393 while ( $xi < $this->m
&& $yi < $this->n
394 && !$this->removed
[$xi]
395 && !$this->added
[$yi]
400 // Find deletes & adds.
402 while ( $xi < $this->m
&& $this->removed
[$xi] ) {
407 while ( $yi < $this->n
&& $this->added
[$yi] ) {
411 if ( $xi > $xstart ||
$yi > $ystart ) {
412 $ranges[] = new RangeDifference( $xstart, $xi, $ystart, $yi );
419 private function lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
420 // check that both sequences are non-empty
421 if ( $bottoml1 > $topl1 ||
$bottoml2 > $topl2 ) {
425 $d = $this->find_middle_snake( $bottoml1, $topl1, $bottoml2,
426 $topl2, $V, $snake );
428 // need to store these so we don't lose them when they're
429 // overwritten by the recursion
434 // the middle snake is part of the LCS, store it
435 for ( $i = 0; $i < $len; ++
$i ) {
436 $this->removed
[$startx +
$i] = $this->added
[$starty +
$i] = false;
441 +
$this->lcs_rec( $bottoml1, $startx - 1, $bottoml2,
442 $starty - 1, $V, $snake )
443 +
$this->lcs_rec( $startx +
$len, $topl1, $starty +
$len,
444 $topl2, $V, $snake );
445 } elseif ( $d == 1 ) {
447 * In this case the sequences differ by exactly 1 line. We have
448 * already saved all the lines after the difference in the for loop
449 * above, now we need to save all the lines before the difference.
451 $max = min( $startx - $bottoml1, $starty - $bottoml2 );
452 for ( $i = 0; $i < $max; ++
$i ) {
453 $this->removed
[$bottoml1 +
$i] =
454 $this->added
[$bottoml2 +
$i] = false;
463 private function find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
464 $from = &$this->from
;
468 $snake0 = &$snake[0];
469 $snake1 = &$snake[1];
470 $snake2 = &$snake[2];
471 $bottoml1_min_1 = $bottoml1 - 1;
472 $bottoml2_min_1 = $bottoml2 - 1;
473 $N = $topl1 - $bottoml1_min_1;
474 $M = $topl2 - $bottoml2_min_1;
476 $maxabsx = $N +
$bottoml1;
477 $maxabsy = $M +
$bottoml2;
478 $limit = min( $this->maxDifferences
, ceil( ( $N +
$M ) / 2 ) );
480 // value_to_add_forward: a 0 or 1 that we add to the start
481 // offset to make it odd/even
482 if ( ( $M & 1 ) == 1 ) {
483 $value_to_add_forward = 1;
485 $value_to_add_forward = 0;
488 if ( ( $N & 1 ) == 1 ) {
489 $value_to_add_backward = 1;
491 $value_to_add_backward = 0;
494 $start_forward = -$M;
496 $start_backward = -$N;
499 $limit_min_1 = $limit - 1;
500 $limit_plus_1 = $limit +
1;
502 $V0[$limit_plus_1] = 0;
503 $V1[$limit_min_1] = $N;
504 $limit = min( $this->maxDifferences
, ceil( ( $N +
$M ) / 2 ) );
506 if ( ( $delta & 1 ) == 1 ) {
507 for ( $d = 0; $d <= $limit; ++
$d ) {
508 $start_diag = max( $value_to_add_forward +
$start_forward, -$d );
509 $end_diag = min( $end_forward, $d );
510 $value_to_add_forward = 1 - $value_to_add_forward;
512 // compute forward furthest reaching paths
513 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
514 if ( $k == -$d ||
( $k < $d
515 && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k] )
517 $x = $V0[$limit_plus_1 +
$k];
519 $x = $V0[$limit_min_1 +
$k] +
1;
522 $absx = $snake0 = $x +
$bottoml1;
523 $absy = $snake1 = $x - $k +
$bottoml2;
525 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
529 $x = $absx - $bottoml1;
531 $snake2 = $absx - $snake0;
532 $V0[$limit +
$k] = $x;
533 if ( $k >= $delta - $d +
1 && $k <= $delta +
$d - 1
534 && $x >= $V1[$limit +
$k - $delta]
539 // check to see if we can cut down the diagonal range
540 if ( $x >= $N && $end_forward > $k - 1 ) {
541 $end_forward = $k - 1;
542 } elseif ( $absy - $bottoml2 >= $M ) {
543 $start_forward = $k +
1;
544 $value_to_add_forward = 0;
548 $start_diag = max( $value_to_add_backward +
$start_backward, -$d );
549 $end_diag = min( $end_backward, $d );
550 $value_to_add_backward = 1 - $value_to_add_backward;
552 // compute backward furthest reaching paths
553 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
555 ||
( $k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k] )
557 $x = $V1[$limit_min_1 +
$k];
559 $x = $V1[$limit_plus_1 +
$k] - 1;
562 $y = $x - $k - $delta;
565 while ( $x > 0 && $y > 0
566 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1]
572 $V1[$limit +
$k] = $x;
574 // check to see if we can cut down our diagonal range
576 $start_backward = $k +
1;
577 $value_to_add_backward = 0;
578 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
579 $end_backward = $k - 1;
584 for ( $d = 0; $d <= $limit; ++
$d ) {
585 $start_diag = max( $value_to_add_forward +
$start_forward, -$d );
586 $end_diag = min( $end_forward, $d );
587 $value_to_add_forward = 1 - $value_to_add_forward;
589 // compute forward furthest reaching paths
590 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
592 ||
( $k < $d && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k] )
594 $x = $V0[$limit_plus_1 +
$k];
596 $x = $V0[$limit_min_1 +
$k] +
1;
599 $absx = $snake0 = $x +
$bottoml1;
600 $absy = $snake1 = $x - $k +
$bottoml2;
602 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
606 $x = $absx - $bottoml1;
607 $snake2 = $absx - $snake0;
608 $V0[$limit +
$k] = $x;
610 // check to see if we can cut down the diagonal range
611 if ( $x >= $N && $end_forward > $k - 1 ) {
612 $end_forward = $k - 1;
613 } elseif ( $absy - $bottoml2 >= $M ) {
614 $start_forward = $k +
1;
615 $value_to_add_forward = 0;
619 $start_diag = max( $value_to_add_backward +
$start_backward, -$d );
620 $end_diag = min( $end_backward, $d );
621 $value_to_add_backward = 1 - $value_to_add_backward;
623 // compute backward furthest reaching paths
624 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
626 ||
( $k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k] )
628 $x = $V1[$limit_min_1 +
$k];
630 $x = $V1[$limit_plus_1 +
$k] - 1;
633 $y = $x - $k - $delta;
636 while ( $x > 0 && $y > 0
637 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1]
643 $V1[$limit +
$k] = $x;
645 if ( $k >= -$delta - $d && $k <= $d - $delta
646 && $x <= $V0[$limit +
$k +
$delta]
648 $snake0 = $bottoml1 +
$x;
649 $snake1 = $bottoml2 +
$y;
654 // check to see if we can cut down our diagonal range
656 $start_backward = $k +
1;
657 $value_to_add_backward = 0;
658 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
659 $end_backward = $k - 1;
665 * computing the true LCS is too expensive, instead find the diagonal
666 * with the most progress and pretend a midle snake of length 0 occurs
670 $most_progress = self
::findMostProgress( $M, $N, $limit, $V );
672 $snake0 = $bottoml1 +
$most_progress[0];
673 $snake1 = $bottoml2 +
$most_progress[1];
675 wfDebug( "Computing the LCS is too expensive. Using a heuristic.\n" );
676 $this->heuristicUsed
= true;
679 * HACK: since we didn't really finish the LCS computation
680 * we don't really know the length of the SES. We don't do
681 * anything with the result anyway, unless it's <=1. We know
682 * for a fact SES > 1 so 5 is as good a number as any to
687 private static function findMostProgress( $M, $N, $limit, $V ) {
690 if ( ( $M & 1 ) == ( $limit & 1 ) ) {
691 $forward_start_diag = max( -$M, -$limit );
693 $forward_start_diag = max( 1 - $M, -$limit );
696 $forward_end_diag = min( $N, $limit );
698 if ( ( $N & 1 ) == ( $limit & 1 ) ) {
699 $backward_start_diag = max( -$N, -$limit );
701 $backward_start_diag = max( 1 - $N, -$limit );
704 $backward_end_diag = -min( $M, $limit );
708 $max_progress = array_fill( 0, ceil( max( $forward_end_diag - $forward_start_diag,
709 $backward_end_diag - $backward_start_diag ) / 2 ), $temp );
710 $num_progress = 0; // the 1st entry is current, it is initialized
713 // first search the forward diagonals
714 for ( $k = $forward_start_diag; $k <= $forward_end_diag; $k +
= 2 ) {
715 $x = $V[0][$limit +
$k];
717 if ( $x > $N ||
$y > $M ) {
722 if ( $progress > $max_progress[0][2] ) {
724 $max_progress[0][0] = $x;
725 $max_progress[0][1] = $y;
726 $max_progress[0][2] = $progress;
727 } elseif ( $progress == $max_progress[0][2] ) {
729 $max_progress[$num_progress][0] = $x;
730 $max_progress[$num_progress][1] = $y;
731 $max_progress[$num_progress][2] = $progress;
735 $max_progress_forward = true; // initially the maximum
736 // progress is in the forward
739 // now search the backward diagonals
740 for ( $k = $backward_start_diag; $k <= $backward_end_diag; $k +
= 2 ) {
741 $x = $V[1][$limit +
$k];
742 $y = $x - $k - $delta;
743 if ( $x < 0 ||
$y < 0 ) {
747 $progress = $N - $x +
$M - $y;
748 if ( $progress > $max_progress[0][2] ) {
750 $max_progress_forward = false;
751 $max_progress[0][0] = $x;
752 $max_progress[0][1] = $y;
753 $max_progress[0][2] = $progress;
754 } elseif ( $progress == $max_progress[0][2] && !$max_progress_forward ) {
756 $max_progress[$num_progress][0] = $x;
757 $max_progress[$num_progress][1] = $y;
758 $max_progress[$num_progress][2] = $progress;
762 // return the middle diagonal with maximal progress.
763 return $max_progress[(int)floor( $num_progress / 2 )];
769 public function getLcsLength() {
770 if ( $this->heuristicUsed
&& !$this->lcsLengthCorrectedForHeuristic
) {
771 $this->lcsLengthCorrectedForHeuristic
= true;
772 $this->length
= $this->m
- array_sum( $this->added
);
775 return $this->length
;
781 * Alternative representation of a set of changes, by the index
782 * ranges that are changed.
784 * @ingroup DifferenceEngine
786 class RangeDifference
{
806 function __construct( $leftstart, $leftend, $rightstart, $rightend ) {
807 $this->leftstart
= $leftstart;
808 $this->leftend
= $leftend;
809 $this->leftlength
= $leftend - $leftstart;
810 $this->rightstart
= $rightstart;
811 $this->rightend
= $rightend;
812 $this->rightlength
= $rightend - $rightstart;