MediaWiki REL1_34
DiffEngine.php
Go to the documentation of this file.
1<?php
26
27// FIXME: Don't use assert() in this file
28// phpcs:disable MediaWiki.Usage.ForbiddenFunctions.assert
29
48
49 // Input variables
51 private $from;
53 private $to;
54 private $m;
55 private $n;
56
57 private $tooLong;
58 private $powLimit;
59
60 protected $bailoutComplexity = 0;
61
62 // State variables
65
66 // Output variables
67 public $length;
68 public $removed;
69 public $added;
71
72 function __construct( $tooLong = 2000000, $powLimit = 1.45 ) {
73 $this->tooLong = $tooLong;
74 $this->powLimit = $powLimit;
75 }
76
86 public function diff( $from_lines, $to_lines ) {
87 // Diff and store locally
88 $this->diffInternal( $from_lines, $to_lines );
89
90 // Merge edits when possible
91 $this->shiftBoundaries( $from_lines, $this->removed, $this->added );
92 $this->shiftBoundaries( $to_lines, $this->added, $this->removed );
93
94 // Compute the edit operations.
95 $n_from = count( $from_lines );
96 $n_to = count( $to_lines );
97
98 $edits = [];
99 $xi = $yi = 0;
100 while ( $xi < $n_from || $yi < $n_to ) {
101 assert( $yi < $n_to || $this->removed[$xi] );
102 assert( $xi < $n_from || $this->added[$yi] );
103
104 // Skip matching "snake".
105 $copy = [];
106 while ( $xi < $n_from && $yi < $n_to
107 && !$this->removed[$xi] && !$this->added[$yi]
108 ) {
109 $copy[] = $from_lines[$xi++];
110 ++$yi;
111 }
112 if ( $copy ) {
113 $edits[] = new DiffOpCopy( $copy );
114 }
115
116 // Find deletes & adds.
117 $delete = [];
118 while ( $xi < $n_from && $this->removed[$xi] ) {
119 $delete[] = $from_lines[$xi++];
120 }
121
122 $add = [];
123 while ( $yi < $n_to && $this->added[$yi] ) {
124 $add[] = $to_lines[$yi++];
125 }
126
127 if ( $delete && $add ) {
128 $edits[] = new DiffOpChange( $delete, $add );
129 } elseif ( $delete ) {
130 $edits[] = new DiffOpDelete( $delete );
131 } elseif ( $add ) {
132 $edits[] = new DiffOpAdd( $add );
133 }
134 }
135
136 return $edits;
137 }
138
143 public function setBailoutComplexity( $value ) {
144 $this->bailoutComplexity = $value;
145 }
146
164 private function shiftBoundaries( array $lines, array &$changed, array $other_changed ) {
165 $i = 0;
166 $j = 0;
167
168 assert( count( $lines ) == count( $changed ) );
169 $len = count( $lines );
170 $other_len = count( $other_changed );
171
172 while ( 1 ) {
173 /*
174 * Scan forwards to find beginning of another run of changes.
175 * Also keep track of the corresponding point in the other file.
176 *
177 * Throughout this code, $i and $j are adjusted together so that
178 * the first $i elements of $changed and the first $j elements
179 * of $other_changed both contain the same number of zeros
180 * (unchanged lines).
181 * Furthermore, $j is always kept so that $j == $other_len or
182 * $other_changed[$j] == false.
183 */
184 while ( $j < $other_len && $other_changed[$j] ) {
185 $j++;
186 }
187
188 while ( $i < $len && !$changed[$i] ) {
189 assert( $j < $other_len && !$other_changed[$j] );
190 $i++;
191 $j++;
192 while ( $j < $other_len && $other_changed[$j] ) {
193 $j++;
194 }
195 }
196
197 if ( $i == $len ) {
198 break;
199 }
200
201 $start = $i;
202
203 // Find the end of this run of changes.
204 while ( ++$i < $len && $changed[$i] ) {
205 continue;
206 }
207
208 do {
209 /*
210 * Record the length of this run of changes, so that
211 * we can later determine whether the run has grown.
212 */
213 $runlength = $i - $start;
214
215 /*
216 * Move the changed region back, so long as the
217 * previous unchanged line matches the last changed one.
218 * This merges with previous changed regions.
219 */
220 while ( $start > 0 && $lines[$start - 1] == $lines[$i - 1] ) {
221 $changed[--$start] = 1;
222 $changed[--$i] = false;
223 while ( $start > 0 && $changed[$start - 1] ) {
224 $start--;
225 }
226 assert( $j > 0 );
227 while ( $other_changed[--$j] ) {
228 continue;
229 }
230 assert( $j >= 0 && !$other_changed[$j] );
231 }
232
233 /*
234 * Set CORRESPONDING to the end of the changed run, at the last
235 * point where it corresponds to a changed run in the other file.
236 * CORRESPONDING == LEN means no such point has been found.
237 */
238 $corresponding = $j < $other_len ? $i : $len;
239
240 /*
241 * Move the changed region forward, so long as the
242 * first changed line matches the following unchanged one.
243 * This merges with following changed regions.
244 * Do this second, so that if there are no merges,
245 * the changed region is moved forward as far as possible.
246 */
247 while ( $i < $len && $lines[$start] == $lines[$i] ) {
248 $changed[$start++] = false;
249 $changed[$i++] = 1;
250 while ( $i < $len && $changed[$i] ) {
251 $i++;
252 }
253
254 assert( $j < $other_len && !$other_changed[$j] );
255 $j++;
256 if ( $j < $other_len && $other_changed[$j] ) {
257 $corresponding = $i;
258 while ( $j < $other_len && $other_changed[$j] ) {
259 $j++;
260 }
261 }
262 }
263 } while ( $runlength != $i - $start );
264
265 /*
266 * If possible, move the fully-merged run of changes
267 * back to a corresponding run in the other file.
268 */
269 while ( $corresponding < $i ) {
270 $changed[--$start] = 1;
271 $changed[--$i] = 0;
272 assert( $j > 0 );
273 while ( $other_changed[--$j] ) {
274 continue;
275 }
276 assert( $j >= 0 && !$other_changed[$j] );
277 }
278 }
279 }
280
286 protected function diffInternal( array $from, array $to ) {
287 // remember initial lengths
288 $m = count( $from );
289 $n = count( $to );
290
291 $this->heuristicUsed = false;
292
293 // output
294 $removed = $m > 0 ? array_fill( 0, $m, true ) : [];
295 $added = $n > 0 ? array_fill( 0, $n, true ) : [];
296
297 // reduce the complexity for the next step (intentionally done twice)
298 // remove common tokens at the start
299 $i = 0;
300 while ( $i < $m && $i < $n && $from[$i] === $to[$i] ) {
301 $removed[$i] = $added[$i] = false;
302 unset( $from[$i], $to[$i] );
303 ++$i;
304 }
305
306 // remove common tokens at the end
307 $j = 1;
308 while ( $i + $j <= $m && $i + $j <= $n && $from[$m - $j] === $to[$n - $j] ) {
309 $removed[$m - $j] = $added[$n - $j] = false;
310 unset( $from[$m - $j], $to[$n - $j] );
311 ++$j;
312 }
313
314 $this->from = $newFromIndex = $this->to = $newToIndex = [];
315
316 // remove tokens not in both sequences
317 $shared = [];
318 foreach ( $from as $key ) {
319 $shared[$key] = false;
320 }
321
322 foreach ( $to as $index => &$el ) {
323 if ( array_key_exists( $el, $shared ) ) {
324 // keep it
325 $this->to[] = $el;
326 $shared[$el] = true;
327 $newToIndex[] = $index;
328 }
329 }
330 foreach ( $from as $index => &$el ) {
331 if ( $shared[$el] ) {
332 // keep it
333 $this->from[] = $el;
334 $newFromIndex[] = $index;
335 }
336 }
337
338 unset( $shared, $from, $to );
339
340 $this->m = count( $this->from );
341 $this->n = count( $this->to );
342
343 if ( $this->bailoutComplexity > 0 && $this->m * $this->n > $this->bailoutComplexity ) {
344 throw new ComplexityException();
345 }
346
347 $this->removed = $this->m > 0 ? array_fill( 0, $this->m, true ) : [];
348 $this->added = $this->n > 0 ? array_fill( 0, $this->n, true ) : [];
349
350 if ( $this->m == 0 || $this->n == 0 ) {
351 $this->length = 0;
352 } else {
353 $this->maxDifferences = ceil( ( $this->m + $this->n ) / 2.0 );
354 if ( $this->m * $this->n > $this->tooLong ) {
355 // limit complexity to D^POW_LIMIT for long sequences
356 $this->maxDifferences = floor( $this->maxDifferences ** ( $this->powLimit - 1.0 ) );
357 wfDebug( "Limiting max number of differences to $this->maxDifferences\n" );
358 }
359
360 /*
361 * The common prefixes and suffixes are always part of some LCS, include
362 * them now to reduce our search space
363 */
364 $max = min( $this->m, $this->n );
365 for ( $forwardBound = 0; $forwardBound < $max
366 && $this->from[$forwardBound] === $this->to[$forwardBound];
367 ++$forwardBound
368 ) {
369 $this->removed[$forwardBound] = $this->added[$forwardBound] = false;
370 }
371
372 $backBoundL1 = $this->m - 1;
373 $backBoundL2 = $this->n - 1;
374
375 while ( $backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
376 && $this->from[$backBoundL1] === $this->to[$backBoundL2]
377 ) {
378 $this->removed[$backBoundL1--] = $this->added[$backBoundL2--] = false;
379 }
380
381 $temp = array_fill( 0, $this->m + $this->n + 1, 0 );
382 $V = [ $temp, $temp ];
383 $snake = [ 0, 0, 0 ];
384
385 $this->length = $forwardBound + $this->m - $backBoundL1 - 1
386 + $this->lcs_rec(
387 $forwardBound,
388 $backBoundL1,
389 $forwardBound,
390 $backBoundL2,
391 $V,
392 $snake
393 );
394 }
395
396 $this->m = $m;
397 $this->n = $n;
398
399 $this->length += $i + $j - 1;
400
401 foreach ( $this->removed as $key => &$removed_elem ) {
402 if ( !$removed_elem ) {
403 $removed[$newFromIndex[$key]] = false;
404 }
405 }
406 foreach ( $this->added as $key => &$added_elem ) {
407 if ( !$added_elem ) {
408 $added[$newToIndex[$key]] = false;
409 }
410 }
411 $this->removed = $removed;
412 $this->added = $added;
413 }
414
415 function diff_range( $from_lines, $to_lines ) {
416 // Diff and store locally
417 $this->diff( $from_lines, $to_lines );
418 unset( $from_lines, $to_lines );
419
420 $ranges = [];
421 $xi = $yi = 0;
422 while ( $xi < $this->m || $yi < $this->n ) {
423 // Matching "snake".
424 while ( $xi < $this->m && $yi < $this->n
425 && !$this->removed[$xi]
426 && !$this->added[$yi]
427 ) {
428 ++$xi;
429 ++$yi;
430 }
431 // Find deletes & adds.
432 $xstart = $xi;
433 while ( $xi < $this->m && $this->removed[$xi] ) {
434 ++$xi;
435 }
436
437 $ystart = $yi;
438 while ( $yi < $this->n && $this->added[$yi] ) {
439 ++$yi;
440 }
441
442 if ( $xi > $xstart || $yi > $ystart ) {
443 $ranges[] = new RangeDifference( $xstart, $xi, $ystart, $yi );
444 }
445 }
446
447 return $ranges;
448 }
449
450 private function lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
451 // check that both sequences are non-empty
452 if ( $bottoml1 > $topl1 || $bottoml2 > $topl2 ) {
453 return 0;
454 }
455
456 $d = $this->find_middle_snake( $bottoml1, $topl1, $bottoml2,
457 $topl2, $V, $snake );
458
459 // need to store these so we don't lose them when they're
460 // overwritten by the recursion
461 list( $startx, $starty, $len ) = $snake;
462
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;
466 }
467
468 if ( $d > 1 ) {
469 return $len
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 ) {
475 /*
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.
479 */
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;
484 }
485
486 return $max + $len;
487 }
488
489 return $len;
490 }
491
492 private function find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
494 $to = &$this->to;
495 $V0 = &$V[0];
496 $V1 = &$V[1];
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;
504 $delta = $N - $M;
505 $maxabsx = $N + $bottoml1;
506 $maxabsy = $M + $bottoml2;
507 $limit = min( $this->maxDifferences, ceil( ( $N + $M ) / 2 ) );
508
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 ) {
512 $value_to_add_forward = 1;
513 } else {
514 $value_to_add_forward = 0;
515 }
516
517 if ( $N & 1 ) {
518 $value_to_add_backward = 1;
519 } else {
520 $value_to_add_backward = 0;
521 }
522
523 $start_forward = -$M;
524 $end_forward = $N;
525 $start_backward = -$N;
526 $end_backward = $M;
527
528 $limit_min_1 = $limit - 1;
529 $limit_plus_1 = $limit + 1;
530
531 $V0[$limit_plus_1] = 0;
532 $V1[$limit_min_1] = $N;
533 $limit = min( $this->maxDifferences, ceil( ( $N + $M ) / 2 ) );
534
535 if ( $delta & 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;
540
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] )
545 ) {
546 $x = $V0[$limit_plus_1 + $k];
547 } else {
548 $x = $V0[$limit_min_1 + $k] + 1;
549 }
550
551 $absx = $snake0 = $x + $bottoml1;
552 $absy = $snake1 = $x - $k + $bottoml2;
553
554 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
555 ++$absx;
556 ++$absy;
557 }
558 $x = $absx - $bottoml1;
559
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]
564 ) {
565 return 2 * $d - 1;
566 }
567
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;
574 }
575 }
576
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;
580
581 // compute backward furthest reaching paths
582 for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
583 if ( $k == $d
584 || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] )
585 ) {
586 $x = $V1[$limit_min_1 + $k];
587 } else {
588 $x = $V1[$limit_plus_1 + $k] - 1;
589 }
590
591 $y = $x - $k - $delta;
592
593 $snake2 = 0;
594 while ( $x > 0 && $y > 0
595 && $from[$x + $bottoml1_min_1] === $to[$y + $bottoml2_min_1]
596 ) {
597 --$x;
598 --$y;
599 ++$snake2;
600 }
601 $V1[$limit + $k] = $x;
602
603 // check to see if we can cut down our diagonal range
604 if ( $x <= 0 ) {
605 $start_backward = $k + 1;
606 $value_to_add_backward = 0;
607 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
608 $end_backward = $k - 1;
609 }
610 }
611 }
612 } else {
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;
617
618 // compute forward furthest reaching paths
619 for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
620 if ( $k == -$d
621 || ( $k < $d && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k] )
622 ) {
623 $x = $V0[$limit_plus_1 + $k];
624 } else {
625 $x = $V0[$limit_min_1 + $k] + 1;
626 }
627
628 $absx = $snake0 = $x + $bottoml1;
629 $absy = $snake1 = $x - $k + $bottoml2;
630
631 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
632 ++$absx;
633 ++$absy;
634 }
635 $x = $absx - $bottoml1;
636 $snake2 = $absx - $snake0;
637 $V0[$limit + $k] = $x;
638
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;
645 }
646 }
647
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;
651
652 // compute backward furthest reaching paths
653 for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
654 if ( $k == $d
655 || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] )
656 ) {
657 $x = $V1[$limit_min_1 + $k];
658 } else {
659 $x = $V1[$limit_plus_1 + $k] - 1;
660 }
661
662 $y = $x - $k - $delta;
663
664 $snake2 = 0;
665 while ( $x > 0 && $y > 0
666 && $from[$x + $bottoml1_min_1] === $to[$y + $bottoml2_min_1]
667 ) {
668 --$x;
669 --$y;
670 ++$snake2;
671 }
672 $V1[$limit + $k] = $x;
673
674 if ( $k >= -$delta - $d && $k <= $d - $delta
675 && $x <= $V0[$limit + $k + $delta]
676 ) {
677 $snake0 = $bottoml1 + $x;
678 $snake1 = $bottoml2 + $y;
679
680 return 2 * $d;
681 }
682
683 // check to see if we can cut down our diagonal range
684 if ( $x <= 0 ) {
685 $start_backward = $k + 1;
686 $value_to_add_backward = 0;
687 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
688 $end_backward = $k - 1;
689 }
690 }
691 }
692 }
693 /*
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
696 * there.
697 */
698
699 $most_progress = self::findMostProgress( $M, $N, $limit, $V );
700
701 $snake0 = $bottoml1 + $most_progress[0];
702 $snake1 = $bottoml2 + $most_progress[1];
703 $snake2 = 0;
704 wfDebug( "Computing the LCS is too expensive. Using a heuristic.\n" );
705 $this->heuristicUsed = true;
706
707 return 5; /*
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
712 * return here
713 */
714 }
715
716 private static function findMostProgress( $M, $N, $limit, $V ) {
717 $delta = $N - $M;
718
719 if ( ( $M & 1 ) == ( $limit & 1 ) ) {
720 $forward_start_diag = max( -$M, -$limit );
721 } else {
722 $forward_start_diag = max( 1 - $M, -$limit );
723 }
724
725 $forward_end_diag = min( $N, $limit );
726
727 if ( ( $N & 1 ) == ( $limit & 1 ) ) {
728 $backward_start_diag = max( -$N, -$limit );
729 } else {
730 $backward_start_diag = max( 1 - $N, -$limit );
731 }
732
733 $backward_end_diag = -min( $M, $limit );
734
735 $temp = [ 0, 0, 0 ];
736
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
740 // with 0s
741
742 // first search the forward diagonals
743 for ( $k = $forward_start_diag; $k <= $forward_end_diag; $k += 2 ) {
744 $x = $V[0][$limit + $k];
745 $y = $x - $k;
746 if ( $x > $N || $y > $M ) {
747 continue;
748 }
749
750 $progress = $x + $y;
751 if ( $progress > $max_progress[0][2] ) {
752 $num_progress = 0;
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] ) {
757 ++$num_progress;
758 $max_progress[$num_progress][0] = $x;
759 $max_progress[$num_progress][1] = $y;
760 $max_progress[$num_progress][2] = $progress;
761 }
762 }
763
764 $max_progress_forward = true; // initially the maximum
765 // progress is in the forward
766 // direction
767
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 ) {
773 continue;
774 }
775
776 $progress = $N - $x + $M - $y;
777 if ( $progress > $max_progress[0][2] ) {
778 $num_progress = 0;
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 ) {
784 ++$num_progress;
785 $max_progress[$num_progress][0] = $x;
786 $max_progress[$num_progress][1] = $y;
787 $max_progress[$num_progress][2] = $progress;
788 }
789 }
790
791 // return the middle diagonal with maximal progress.
792 return $max_progress[(int)floor( $num_progress / 2 )];
793 }
794
798 public function getLcsLength() {
799 if ( $this->heuristicUsed && !$this->lcsLengthCorrectedForHeuristic ) {
800 $this->lcsLengthCorrectedForHeuristic = true;
801 $this->length = $this->m - array_sum( $this->added );
802 }
803
804 return $this->length;
805 }
806
807}
wfDebug( $text, $dest='all', array $context=[])
Sends a line to the debug log if enabled or, optionally, to a comment in output.
This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which in turn...
setBailoutComplexity( $value)
Sets the complexity (in comparison operations) that can't be exceeded.
diff_range( $from_lines, $to_lines)
string[] $from
string[] $to
__construct( $tooLong=2000000, $powLimit=1.45)
lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
shiftBoundaries(array $lines, array &$changed, array $other_changed)
Adjust inserts/deletes of identical lines to join changes as much as possible.
diff( $from_lines, $to_lines)
Performs diff.
diffInternal(array $from, array $to)
$lcsLengthCorrectedForHeuristic
find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
static findMostProgress( $M, $N, $limit, $V)
Extends DiffOp.
Definition DiffOpAdd.php:35
Extends DiffOp.
Extends DiffOp.
Extends DiffOp.
Alternative representation of a set of changes, by the index ranges that are changed.
$lines
Definition router.php:61