MediaWiki  master
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 
47 class DiffEngine {
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
63  private $maxDifferences;
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 ) {
493  $from = &$this->from;
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 }
Extends DiffOp.
Alternative representation of a set of changes, by the index ranges that are changed.
Extends DiffOp.
Definition: DiffOpCopy.php:35
$lcsLengthCorrectedForHeuristic
Definition: DiffEngine.php:64
diff_range( $from_lines, $to_lines)
Definition: DiffEngine.php:415
find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
Definition: DiffEngine.php:492
static findMostProgress( $M, $N, $limit, $V)
Definition: DiffEngine.php:716
Extends DiffOp.
Definition: DiffOpAdd.php:35
__construct( $tooLong=2000000, $powLimit=1.45)
Definition: DiffEngine.php:72
lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
Definition: DiffEngine.php:450
wfDebug( $text, $dest='all', array $context=[])
Sends a line to the debug log if enabled or, optionally, to a comment in output.
diffInternal(array $from, array $to)
Definition: DiffEngine.php:286
diff( $from_lines, $to_lines)
Performs diff.
Definition: DiffEngine.php:86
This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which in turn...
Definition: DiffEngine.php:47
setBailoutComplexity( $value)
Sets the complexity (in comparison operations) that can&#39;t be exceeded.
Definition: DiffEngine.php:143
string [] $from
Definition: DiffEngine.php:51
$lines
Definition: router.php:61
string [] $to
Definition: DiffEngine.php:53
shiftBoundaries(array $lines, array &$changed, array $other_changed)
Adjust inserts/deletes of identical lines to join changes as much as possible.
Definition: DiffEngine.php:164
while(( $__line=Maintenance::readconsole()) !==false) print n
Definition: eval.php:64
Extends DiffOp.