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
25 use MediaWiki\Diff\ComplexityException
;
27 // FIXME: Don't use assert() in this file
28 // phpcs:disable MediaWiki.Usage.ForbiddenFunctions.assert
31 * This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which
32 * in turn is based on Myers' "An O(ND) difference algorithm and its variations"
33 * (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al.'s
34 * "An O(NP) Sequence Comparison Algorithm").
36 * This implementation supports an upper bound on the execution time.
38 * Some ideas (and a bit of code) are from analyze.c, from GNU
39 * diffutils-2.7, which can be found at:
40 * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
42 * Complexity: O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space
44 * @author Guy Van den Broeck, Geoffrey T. Dairiki, Tim Starling
45 * @ingroup DifferenceEngine
58 protected $bailoutComplexity = 0;
61 private $maxDifferences;
62 private $lcsLengthCorrectedForHeuristic = false;
68 public $heuristicUsed;
70 function __construct( $tooLong = 2000000, $powLimit = 1.45 ) {
71 $this->tooLong
= $tooLong;
72 $this->powLimit
= $powLimit;
78 * @param string[] $from_lines
79 * @param string[] $to_lines
80 * @throws ComplexityException
84 public function diff( $from_lines, $to_lines ) {
85 // Diff and store locally
86 $this->diffInternal( $from_lines, $to_lines );
88 // Merge edits when possible
89 $this->shiftBoundaries( $from_lines, $this->removed
, $this->added
);
90 $this->shiftBoundaries( $to_lines, $this->added
, $this->removed
);
92 // Compute the edit operations.
93 $n_from = count( $from_lines );
94 $n_to = count( $to_lines );
98 while ( $xi < $n_from ||
$yi < $n_to ) {
99 assert( $yi < $n_to ||
$this->removed
[$xi] );
100 assert( $xi < $n_from ||
$this->added
[$yi] );
102 // Skip matching "snake".
104 while ( $xi < $n_from && $yi < $n_to
105 && !$this->removed
[$xi] && !$this->added
[$yi]
107 $copy[] = $from_lines[$xi++
];
111 $edits[] = new DiffOpCopy( $copy );
114 // Find deletes & adds.
116 while ( $xi < $n_from && $this->removed
[$xi] ) {
117 $delete[] = $from_lines[$xi++
];
121 while ( $yi < $n_to && $this->added
[$yi] ) {
122 $add[] = $to_lines[$yi++
];
125 if ( $delete && $add ) {
126 $edits[] = new DiffOpChange( $delete, $add );
127 } elseif ( $delete ) {
128 $edits[] = new DiffOpDelete( $delete );
130 $edits[] = new DiffOpAdd( $add );
138 * Sets the complexity (in comparison operations) that can't be exceeded
141 public function setBailoutComplexity( $value ) {
142 $this->bailoutComplexity
= $value;
146 * Adjust inserts/deletes of identical lines to join changes
147 * as much as possible.
149 * We do something when a run of changed lines include a
150 * line at one end and has an excluded, identical line at the other.
151 * We are free to choose which identical line is included.
152 * `compareseq' usually chooses the one at the beginning,
153 * but usually it is cleaner to consider the following identical line
154 * to be the "change".
156 * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
158 * @param string[] $lines
159 * @param string[] $changed
160 * @param string[] $other_changed
162 private function shiftBoundaries( array $lines, array &$changed, array $other_changed ) {
166 assert( count( $lines ) == count( $changed ) );
167 $len = count( $lines );
168 $other_len = count( $other_changed );
172 * Scan forwards to find beginning of another run of changes.
173 * Also keep track of the corresponding point in the other file.
175 * Throughout this code, $i and $j are adjusted together so that
176 * the first $i elements of $changed and the first $j elements
177 * of $other_changed both contain the same number of zeros
179 * Furthermore, $j is always kept so that $j == $other_len or
180 * $other_changed[$j] == false.
182 while ( $j < $other_len && $other_changed[$j] ) {
186 while ( $i < $len && !$changed[$i] ) {
187 assert( $j < $other_len && !$other_changed[$j] );
190 while ( $j < $other_len && $other_changed[$j] ) {
201 // Find the end of this run of changes.
202 while ( ++
$i < $len && $changed[$i] ) {
208 * Record the length of this run of changes, so that
209 * we can later determine whether the run has grown.
211 $runlength = $i - $start;
214 * Move the changed region back, so long as the
215 * previous unchanged line matches the last changed one.
216 * This merges with previous changed regions.
218 while ( $start > 0 && $lines[$start - 1] == $lines[$i - 1] ) {
219 $changed[--$start] = 1;
220 $changed[--$i] = false;
221 while ( $start > 0 && $changed[$start - 1] ) {
225 while ( $other_changed[--$j] ) {
228 assert( $j >= 0 && !$other_changed[$j] );
232 * Set CORRESPONDING to the end of the changed run, at the last
233 * point where it corresponds to a changed run in the other file.
234 * CORRESPONDING == LEN means no such point has been found.
236 $corresponding = $j < $other_len ?
$i : $len;
239 * Move the changed region forward, so long as the
240 * first changed line matches the following unchanged one.
241 * This merges with following changed regions.
242 * Do this second, so that if there are no merges,
243 * the changed region is moved forward as far as possible.
245 while ( $i < $len && $lines[$start] == $lines[$i] ) {
246 $changed[$start++
] = false;
248 while ( $i < $len && $changed[$i] ) {
252 assert( $j < $other_len && !$other_changed[$j] );
254 if ( $j < $other_len && $other_changed[$j] ) {
256 while ( $j < $other_len && $other_changed[$j] ) {
261 } while ( $runlength != $i - $start );
264 * If possible, move the fully-merged run of changes
265 * back to a corresponding run in the other file.
267 while ( $corresponding < $i ) {
268 $changed[--$start] = 1;
271 while ( $other_changed[--$j] ) {
274 assert( $j >= 0 && !$other_changed[$j] );
280 * @param string[] $from
281 * @param string[] $to
282 * @throws ComplexityException
284 protected function diffInternal( array $from, array $to ) {
285 // remember initial lengths
289 $this->heuristicUsed
= false;
292 $removed = $m > 0 ?
array_fill( 0, $m, true ) : [];
293 $added = $n > 0 ?
array_fill( 0, $n, true ) : [];
295 // reduce the complexity for the next step (intentionally done twice)
296 // remove common tokens at the start
298 while ( $i < $m && $i < $n && $from[$i] === $to[$i] ) {
299 $removed[$i] = $added[$i] = false;
300 unset( $from[$i], $to[$i] );
304 // remove common tokens at the end
306 while ( $i +
$j <= $m && $i +
$j <= $n && $from[$m - $j] === $to[$n - $j] ) {
307 $removed[$m - $j] = $added[$n - $j] = false;
308 unset( $from[$m - $j], $to[$n - $j] );
312 $this->from
= $newFromIndex = $this->to
= $newToIndex = [];
314 // remove tokens not in both sequences
316 foreach ( $from as $key ) {
317 $shared[$key] = false;
320 foreach ( $to as $index => &$el ) {
321 if ( array_key_exists( $el, $shared ) ) {
325 $newToIndex[] = $index;
328 foreach ( $from as $index => &$el ) {
329 if ( $shared[$el] ) {
332 $newFromIndex[] = $index;
336 unset( $shared, $from, $to );
338 $this->m
= count( $this->from
);
339 $this->n
= count( $this->to
);
341 if ( $this->bailoutComplexity
> 0 && $this->m
* $this->n
> $this->bailoutComplexity
) {
342 throw new ComplexityException();
345 $this->removed
= $this->m
> 0 ?
array_fill( 0, $this->m
, true ) : [];
346 $this->added
= $this->n
> 0 ?
array_fill( 0, $this->n
, true ) : [];
348 if ( $this->m
== 0 ||
$this->n
== 0 ) {
351 $this->maxDifferences
= ceil( ( $this->m +
$this->n
) / 2.0 );
352 if ( $this->m
* $this->n
> $this->tooLong
) {
353 // limit complexity to D^POW_LIMIT for long sequences
354 $this->maxDifferences
= floor( $this->maxDifferences
** ( $this->powLimit
- 1.0 ) );
355 wfDebug( "Limiting max number of differences to $this->maxDifferences\n" );
359 * The common prefixes and suffixes are always part of some LCS, include
360 * them now to reduce our search space
362 $max = min( $this->m
, $this->n
);
363 for ( $forwardBound = 0; $forwardBound < $max
364 && $this->from
[$forwardBound] === $this->to
[$forwardBound];
367 $this->removed
[$forwardBound] = $this->added
[$forwardBound] = false;
370 $backBoundL1 = $this->m
- 1;
371 $backBoundL2 = $this->n
- 1;
373 while ( $backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
374 && $this->from
[$backBoundL1] === $this->to
[$backBoundL2]
376 $this->removed
[$backBoundL1--] = $this->added
[$backBoundL2--] = false;
379 $temp = array_fill( 0, $this->m +
$this->n +
1, 0 );
380 $V = [ $temp, $temp ];
381 $snake = [ 0, 0, 0 ];
383 $this->length
= $forwardBound +
$this->m
- $backBoundL1 - 1
397 $this->length +
= $i +
$j - 1;
399 foreach ( $this->removed
as $key => &$removed_elem ) {
400 if ( !$removed_elem ) {
401 $removed[$newFromIndex[$key]] = false;
404 foreach ( $this->added
as $key => &$added_elem ) {
405 if ( !$added_elem ) {
406 $added[$newToIndex[$key]] = false;
409 $this->removed
= $removed;
410 $this->added
= $added;
413 function diff_range( $from_lines, $to_lines ) {
414 // Diff and store locally
415 $this->diff( $from_lines, $to_lines );
416 unset( $from_lines, $to_lines );
420 while ( $xi < $this->m ||
$yi < $this->n
) {
422 while ( $xi < $this->m
&& $yi < $this->n
423 && !$this->removed
[$xi]
424 && !$this->added
[$yi]
429 // Find deletes & adds.
431 while ( $xi < $this->m
&& $this->removed
[$xi] ) {
436 while ( $yi < $this->n
&& $this->added
[$yi] ) {
440 if ( $xi > $xstart ||
$yi > $ystart ) {
441 $ranges[] = new RangeDifference( $xstart, $xi, $ystart, $yi );
448 private function lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
449 // check that both sequences are non-empty
450 if ( $bottoml1 > $topl1 ||
$bottoml2 > $topl2 ) {
454 $d = $this->find_middle_snake( $bottoml1, $topl1, $bottoml2,
455 $topl2, $V, $snake );
457 // need to store these so we don't lose them when they're
458 // overwritten by the recursion
463 // the middle snake is part of the LCS, store it
464 for ( $i = 0; $i < $len; ++
$i ) {
465 $this->removed
[$startx +
$i] = $this->added
[$starty +
$i] = false;
470 +
$this->lcs_rec( $bottoml1, $startx - 1, $bottoml2,
471 $starty - 1, $V, $snake )
472 +
$this->lcs_rec( $startx +
$len, $topl1, $starty +
$len,
473 $topl2, $V, $snake );
474 } elseif ( $d == 1 ) {
476 * In this case the sequences differ by exactly 1 line. We have
477 * already saved all the lines after the difference in the for loop
478 * above, now we need to save all the lines before the difference.
480 $max = min( $startx - $bottoml1, $starty - $bottoml2 );
481 for ( $i = 0; $i < $max; ++
$i ) {
482 $this->removed
[$bottoml1 +
$i] =
483 $this->added
[$bottoml2 +
$i] = false;
492 private function find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
493 $from = &$this->from
;
497 $snake0 = &$snake[0];
498 $snake1 = &$snake[1];
499 $snake2 = &$snake[2];
500 $bottoml1_min_1 = $bottoml1 - 1;
501 $bottoml2_min_1 = $bottoml2 - 1;
502 $N = $topl1 - $bottoml1_min_1;
503 $M = $topl2 - $bottoml2_min_1;
505 $maxabsx = $N +
$bottoml1;
506 $maxabsy = $M +
$bottoml2;
507 $limit = min( $this->maxDifferences
, ceil( ( $N +
$M ) / 2 ) );
509 // value_to_add_forward: a 0 or 1 that we add to the start
510 // offset to make it odd/even
511 if ( ( $M & 1 ) == 1 ) {
512 $value_to_add_forward = 1;
514 $value_to_add_forward = 0;
517 if ( ( $N & 1 ) == 1 ) {
518 $value_to_add_backward = 1;
520 $value_to_add_backward = 0;
523 $start_forward = -$M;
525 $start_backward = -$N;
528 $limit_min_1 = $limit - 1;
529 $limit_plus_1 = $limit +
1;
531 $V0[$limit_plus_1] = 0;
532 $V1[$limit_min_1] = $N;
533 $limit = min( $this->maxDifferences
, ceil( ( $N +
$M ) / 2 ) );
535 if ( ( $delta & 1 ) == 1 ) {
536 for ( $d = 0; $d <= $limit; ++
$d ) {
537 $start_diag = max( $value_to_add_forward +
$start_forward, -$d );
538 $end_diag = min( $end_forward, $d );
539 $value_to_add_forward = 1 - $value_to_add_forward;
541 // compute forward furthest reaching paths
542 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
543 if ( $k == -$d ||
( $k < $d
544 && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k] )
546 $x = $V0[$limit_plus_1 +
$k];
548 $x = $V0[$limit_min_1 +
$k] +
1;
551 $absx = $snake0 = $x +
$bottoml1;
552 $absy = $snake1 = $x - $k +
$bottoml2;
554 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
558 $x = $absx - $bottoml1;
560 $snake2 = $absx - $snake0;
561 $V0[$limit +
$k] = $x;
562 if ( $k >= $delta - $d +
1 && $k <= $delta +
$d - 1
563 && $x >= $V1[$limit +
$k - $delta]
568 // check to see if we can cut down the diagonal range
569 if ( $x >= $N && $end_forward > $k - 1 ) {
570 $end_forward = $k - 1;
571 } elseif ( $absy - $bottoml2 >= $M ) {
572 $start_forward = $k +
1;
573 $value_to_add_forward = 0;
577 $start_diag = max( $value_to_add_backward +
$start_backward, -$d );
578 $end_diag = min( $end_backward, $d );
579 $value_to_add_backward = 1 - $value_to_add_backward;
581 // compute backward furthest reaching paths
582 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
584 ||
( $k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k] )
586 $x = $V1[$limit_min_1 +
$k];
588 $x = $V1[$limit_plus_1 +
$k] - 1;
591 $y = $x - $k - $delta;
594 while ( $x > 0 && $y > 0
595 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1]
601 $V1[$limit +
$k] = $x;
603 // check to see if we can cut down our diagonal range
605 $start_backward = $k +
1;
606 $value_to_add_backward = 0;
607 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
608 $end_backward = $k - 1;
613 for ( $d = 0; $d <= $limit; ++
$d ) {
614 $start_diag = max( $value_to_add_forward +
$start_forward, -$d );
615 $end_diag = min( $end_forward, $d );
616 $value_to_add_forward = 1 - $value_to_add_forward;
618 // compute forward furthest reaching paths
619 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
621 ||
( $k < $d && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k] )
623 $x = $V0[$limit_plus_1 +
$k];
625 $x = $V0[$limit_min_1 +
$k] +
1;
628 $absx = $snake0 = $x +
$bottoml1;
629 $absy = $snake1 = $x - $k +
$bottoml2;
631 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
635 $x = $absx - $bottoml1;
636 $snake2 = $absx - $snake0;
637 $V0[$limit +
$k] = $x;
639 // check to see if we can cut down the diagonal range
640 if ( $x >= $N && $end_forward > $k - 1 ) {
641 $end_forward = $k - 1;
642 } elseif ( $absy - $bottoml2 >= $M ) {
643 $start_forward = $k +
1;
644 $value_to_add_forward = 0;
648 $start_diag = max( $value_to_add_backward +
$start_backward, -$d );
649 $end_diag = min( $end_backward, $d );
650 $value_to_add_backward = 1 - $value_to_add_backward;
652 // compute backward furthest reaching paths
653 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
655 ||
( $k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k] )
657 $x = $V1[$limit_min_1 +
$k];
659 $x = $V1[$limit_plus_1 +
$k] - 1;
662 $y = $x - $k - $delta;
665 while ( $x > 0 && $y > 0
666 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1]
672 $V1[$limit +
$k] = $x;
674 if ( $k >= -$delta - $d && $k <= $d - $delta
675 && $x <= $V0[$limit +
$k +
$delta]
677 $snake0 = $bottoml1 +
$x;
678 $snake1 = $bottoml2 +
$y;
683 // check to see if we can cut down our diagonal range
685 $start_backward = $k +
1;
686 $value_to_add_backward = 0;
687 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
688 $end_backward = $k - 1;
694 * computing the true LCS is too expensive, instead find the diagonal
695 * with the most progress and pretend a midle snake of length 0 occurs
699 $most_progress = self
::findMostProgress( $M, $N, $limit, $V );
701 $snake0 = $bottoml1 +
$most_progress[0];
702 $snake1 = $bottoml2 +
$most_progress[1];
704 wfDebug( "Computing the LCS is too expensive. Using a heuristic.\n" );
705 $this->heuristicUsed
= true;
708 * HACK: since we didn't really finish the LCS computation
709 * we don't really know the length of the SES. We don't do
710 * anything with the result anyway, unless it's <=1. We know
711 * for a fact SES > 1 so 5 is as good a number as any to
716 private static function findMostProgress( $M, $N, $limit, $V ) {
719 if ( ( $M & 1 ) == ( $limit & 1 ) ) {
720 $forward_start_diag = max( -$M, -$limit );
722 $forward_start_diag = max( 1 - $M, -$limit );
725 $forward_end_diag = min( $N, $limit );
727 if ( ( $N & 1 ) == ( $limit & 1 ) ) {
728 $backward_start_diag = max( -$N, -$limit );
730 $backward_start_diag = max( 1 - $N, -$limit );
733 $backward_end_diag = -min( $M, $limit );
737 $max_progress = array_fill( 0, ceil( max( $forward_end_diag - $forward_start_diag,
738 $backward_end_diag - $backward_start_diag ) / 2 ), $temp );
739 $num_progress = 0; // the 1st entry is current, it is initialized
742 // first search the forward diagonals
743 for ( $k = $forward_start_diag; $k <= $forward_end_diag; $k +
= 2 ) {
744 $x = $V[0][$limit +
$k];
746 if ( $x > $N ||
$y > $M ) {
751 if ( $progress > $max_progress[0][2] ) {
753 $max_progress[0][0] = $x;
754 $max_progress[0][1] = $y;
755 $max_progress[0][2] = $progress;
756 } elseif ( $progress == $max_progress[0][2] ) {
758 $max_progress[$num_progress][0] = $x;
759 $max_progress[$num_progress][1] = $y;
760 $max_progress[$num_progress][2] = $progress;
764 $max_progress_forward = true; // initially the maximum
765 // progress is in the forward
768 // now search the backward diagonals
769 for ( $k = $backward_start_diag; $k <= $backward_end_diag; $k +
= 2 ) {
770 $x = $V[1][$limit +
$k];
771 $y = $x - $k - $delta;
772 if ( $x < 0 ||
$y < 0 ) {
776 $progress = $N - $x +
$M - $y;
777 if ( $progress > $max_progress[0][2] ) {
779 $max_progress_forward = false;
780 $max_progress[0][0] = $x;
781 $max_progress[0][1] = $y;
782 $max_progress[0][2] = $progress;
783 } elseif ( $progress == $max_progress[0][2] && !$max_progress_forward ) {
785 $max_progress[$num_progress][0] = $x;
786 $max_progress[$num_progress][1] = $y;
787 $max_progress[$num_progress][2] = $progress;
791 // return the middle diagonal with maximal progress.
792 return $max_progress[(int)floor( $num_progress / 2 )];
798 public function getLcsLength() {
799 if ( $this->heuristicUsed
&& !$this->lcsLengthCorrectedForHeuristic
) {
800 $this->lcsLengthCorrectedForHeuristic
= true;
801 $this->length
= $this->m
- array_sum( $this->added
);
804 return $this->length
;