MediaWiki  1.29.1
DiffEngine.php
Go to the documentation of this file.
1 <?php
26 
44 class DiffEngine {
45 
46  // Input variables
47  private $from;
48  private $to;
49  private $m;
50  private $n;
51 
52  private $tooLong;
53  private $powLimit;
54 
55  protected $bailoutComplexity = 0;
56 
57  // State variables
58  private $maxDifferences;
60 
61  // Output variables
62  public $length;
63  public $removed;
64  public $added;
66 
67  function __construct( $tooLong = 2000000, $powLimit = 1.45 ) {
68  $this->tooLong = $tooLong;
69  $this->powLimit = $powLimit;
70  }
71 
81  public function diff( $from_lines, $to_lines ) {
82 
83  // Diff and store locally
84  $this->diffInternal( $from_lines, $to_lines );
85 
86  // Merge edits when possible
87  $this->shiftBoundaries( $from_lines, $this->removed, $this->added );
88  $this->shiftBoundaries( $to_lines, $this->added, $this->removed );
89 
90  // Compute the edit operations.
91  $n_from = count( $from_lines );
92  $n_to = count( $to_lines );
93 
94  $edits = [];
95  $xi = $yi = 0;
96  while ( $xi < $n_from || $yi < $n_to ) {
97  assert( $yi < $n_to || $this->removed[$xi] );
98  assert( $xi < $n_from || $this->added[$yi] );
99 
100  // Skip matching "snake".
101  $copy = [];
102  while ( $xi < $n_from && $yi < $n_to
103  && !$this->removed[$xi] && !$this->added[$yi]
104  ) {
105  $copy[] = $from_lines[$xi++];
106  ++$yi;
107  }
108  if ( $copy ) {
109  $edits[] = new DiffOpCopy( $copy );
110  }
111 
112  // Find deletes & adds.
113  $delete = [];
114  while ( $xi < $n_from && $this->removed[$xi] ) {
115  $delete[] = $from_lines[$xi++];
116  }
117 
118  $add = [];
119  while ( $yi < $n_to && $this->added[$yi] ) {
120  $add[] = $to_lines[$yi++];
121  }
122 
123  if ( $delete && $add ) {
124  $edits[] = new DiffOpChange( $delete, $add );
125  } elseif ( $delete ) {
126  $edits[] = new DiffOpDelete( $delete );
127  } elseif ( $add ) {
128  $edits[] = new DiffOpAdd( $add );
129  }
130  }
131 
132  return $edits;
133  }
134 
139  public function setBailoutComplexity( $value ) {
140  $this->bailoutComplexity = $value;
141  }
142 
160  private function shiftBoundaries( array $lines, array &$changed, array $other_changed ) {
161  $i = 0;
162  $j = 0;
163 
164  assert( count( $lines ) == count( $changed ) );
165  $len = count( $lines );
166  $other_len = count( $other_changed );
167 
168  while ( 1 ) {
169  /*
170  * Scan forwards to find beginning of another run of changes.
171  * Also keep track of the corresponding point in the other file.
172  *
173  * Throughout this code, $i and $j are adjusted together so that
174  * the first $i elements of $changed and the first $j elements
175  * of $other_changed both contain the same number of zeros
176  * (unchanged lines).
177  * Furthermore, $j is always kept so that $j == $other_len or
178  * $other_changed[$j] == false.
179  */
180  while ( $j < $other_len && $other_changed[$j] ) {
181  $j++;
182  }
183 
184  while ( $i < $len && !$changed[$i] ) {
185  assert( $j < $other_len && !$other_changed[$j] );
186  $i++;
187  $j++;
188  while ( $j < $other_len && $other_changed[$j] ) {
189  $j++;
190  }
191  }
192 
193  if ( $i == $len ) {
194  break;
195  }
196 
197  $start = $i;
198 
199  // Find the end of this run of changes.
200  while ( ++$i < $len && $changed[$i] ) {
201  continue;
202  }
203 
204  do {
205  /*
206  * Record the length of this run of changes, so that
207  * we can later determine whether the run has grown.
208  */
209  $runlength = $i - $start;
210 
211  /*
212  * Move the changed region back, so long as the
213  * previous unchanged line matches the last changed one.
214  * This merges with previous changed regions.
215  */
216  while ( $start > 0 && $lines[$start - 1] == $lines[$i - 1] ) {
217  $changed[--$start] = 1;
218  $changed[--$i] = false;
219  while ( $start > 0 && $changed[$start - 1] ) {
220  $start--;
221  }
222  assert( $j > 0 );
223  while ( $other_changed[--$j] ) {
224  continue;
225  }
226  assert( $j >= 0 && !$other_changed[$j] );
227  }
228 
229  /*
230  * Set CORRESPONDING to the end of the changed run, at the last
231  * point where it corresponds to a changed run in the other file.
232  * CORRESPONDING == LEN means no such point has been found.
233  */
234  $corresponding = $j < $other_len ? $i : $len;
235 
236  /*
237  * Move the changed region forward, so long as the
238  * first changed line matches the following unchanged one.
239  * This merges with following changed regions.
240  * Do this second, so that if there are no merges,
241  * the changed region is moved forward as far as possible.
242  */
243  while ( $i < $len && $lines[$start] == $lines[$i] ) {
244  $changed[$start++] = false;
245  $changed[$i++] = 1;
246  while ( $i < $len && $changed[$i] ) {
247  $i++;
248  }
249 
250  assert( $j < $other_len && !$other_changed[$j] );
251  $j++;
252  if ( $j < $other_len && $other_changed[$j] ) {
253  $corresponding = $i;
254  while ( $j < $other_len && $other_changed[$j] ) {
255  $j++;
256  }
257  }
258  }
259  } while ( $runlength != $i - $start );
260 
261  /*
262  * If possible, move the fully-merged run of changes
263  * back to a corresponding run in the other file.
264  */
265  while ( $corresponding < $i ) {
266  $changed[--$start] = 1;
267  $changed[--$i] = 0;
268  assert( $j > 0 );
269  while ( $other_changed[--$j] ) {
270  continue;
271  }
272  assert( $j >= 0 && !$other_changed[$j] );
273  }
274  }
275  }
276 
282  protected function diffInternal( array $from, array $to ) {
283  // remember initial lengths
284  $m = count( $from );
285  $n = count( $to );
286 
287  $this->heuristicUsed = false;
288 
289  // output
290  $removed = $m > 0 ? array_fill( 0, $m, true ) : [];
291  $added = $n > 0 ? array_fill( 0, $n, true ) : [];
292 
293  // reduce the complexity for the next step (intentionally done twice)
294  // remove common tokens at the start
295  $i = 0;
296  while ( $i < $m && $i < $n && $from[$i] === $to[$i] ) {
297  $removed[$i] = $added[$i] = false;
298  unset( $from[$i], $to[$i] );
299  ++$i;
300  }
301 
302  // remove common tokens at the end
303  $j = 1;
304  while ( $i + $j <= $m && $i + $j <= $n && $from[$m - $j] === $to[$n - $j] ) {
305  $removed[$m - $j] = $added[$n - $j] = false;
306  unset( $from[$m - $j], $to[$n - $j] );
307  ++$j;
308  }
309 
310  $this->from = $newFromIndex = $this->to = $newToIndex = [];
311 
312  // remove tokens not in both sequences
313  $shared = [];
314  foreach ( $from as $key ) {
315  $shared[$key] = false;
316  }
317 
318  foreach ( $to as $index => &$el ) {
319  if ( array_key_exists( $el, $shared ) ) {
320  // keep it
321  $this->to[] = $el;
322  $shared[$el] = true;
323  $newToIndex[] = $index;
324  }
325  }
326  foreach ( $from as $index => &$el ) {
327  if ( $shared[$el] ) {
328  // keep it
329  $this->from[] = $el;
330  $newFromIndex[] = $index;
331  }
332  }
333 
334  unset( $shared, $from, $to );
335 
336  $this->m = count( $this->from );
337  $this->n = count( $this->to );
338 
339  if ( $this->bailoutComplexity > 0 && $this->m * $this->n > $this->bailoutComplexity ) {
340  throw new ComplexityException();
341  }
342 
343  $this->removed = $this->m > 0 ? array_fill( 0, $this->m, true ) : [];
344  $this->added = $this->n > 0 ? array_fill( 0, $this->n, true ) : [];
345 
346  if ( $this->m == 0 || $this->n == 0 ) {
347  $this->length = 0;
348  } else {
349  $this->maxDifferences = ceil( ( $this->m + $this->n ) / 2.0 );
350  if ( $this->m * $this->n > $this->tooLong ) {
351  // limit complexity to D^POW_LIMIT for long sequences
352  $this->maxDifferences = floor( pow( $this->maxDifferences, $this->powLimit - 1.0 ) );
353  wfDebug( "Limiting max number of differences to $this->maxDifferences\n" );
354  }
355 
356  /*
357  * The common prefixes and suffixes are always part of some LCS, include
358  * them now to reduce our search space
359  */
360  $max = min( $this->m, $this->n );
361  for ( $forwardBound = 0; $forwardBound < $max
362  && $this->from[$forwardBound] === $this->to[$forwardBound];
363  ++$forwardBound
364  ) {
365  $this->removed[$forwardBound] = $this->added[$forwardBound] = false;
366  }
367 
368  $backBoundL1 = $this->m - 1;
369  $backBoundL2 = $this->n - 1;
370 
371  while ( $backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
372  && $this->from[$backBoundL1] === $this->to[$backBoundL2]
373  ) {
374  $this->removed[$backBoundL1--] = $this->added[$backBoundL2--] = false;
375  }
376 
377  $temp = array_fill( 0, $this->m + $this->n + 1, 0 );
378  $V = [ $temp, $temp ];
379  $snake = [ 0, 0, 0 ];
380 
381  $this->length = $forwardBound + $this->m - $backBoundL1 - 1
382  + $this->lcs_rec(
383  $forwardBound,
384  $backBoundL1,
385  $forwardBound,
386  $backBoundL2,
387  $V,
388  $snake
389  );
390  }
391 
392  $this->m = $m;
393  $this->n = $n;
394 
395  $this->length += $i + $j - 1;
396 
397  foreach ( $this->removed as $key => &$removed_elem ) {
398  if ( !$removed_elem ) {
399  $removed[$newFromIndex[$key]] = false;
400  }
401  }
402  foreach ( $this->added as $key => &$added_elem ) {
403  if ( !$added_elem ) {
404  $added[$newToIndex[$key]] = false;
405  }
406  }
407  $this->removed = $removed;
408  $this->added = $added;
409  }
410 
411  function diff_range( $from_lines, $to_lines ) {
412  // Diff and store locally
413  $this->diff( $from_lines, $to_lines );
414  unset( $from_lines, $to_lines );
415 
416  $ranges = [];
417  $xi = $yi = 0;
418  while ( $xi < $this->m || $yi < $this->n ) {
419  // Matching "snake".
420  while ( $xi < $this->m && $yi < $this->n
421  && !$this->removed[$xi]
422  && !$this->added[$yi]
423  ) {
424  ++$xi;
425  ++$yi;
426  }
427  // Find deletes & adds.
428  $xstart = $xi;
429  while ( $xi < $this->m && $this->removed[$xi] ) {
430  ++$xi;
431  }
432 
433  $ystart = $yi;
434  while ( $yi < $this->n && $this->added[$yi] ) {
435  ++$yi;
436  }
437 
438  if ( $xi > $xstart || $yi > $ystart ) {
439  $ranges[] = new RangeDifference( $xstart, $xi, $ystart, $yi );
440  }
441  }
442 
443  return $ranges;
444  }
445 
446  private function lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
447  // check that both sequences are non-empty
448  if ( $bottoml1 > $topl1 || $bottoml2 > $topl2 ) {
449  return 0;
450  }
451 
452  $d = $this->find_middle_snake( $bottoml1, $topl1, $bottoml2,
453  $topl2, $V, $snake );
454 
455  // need to store these so we don't lose them when they're
456  // overwritten by the recursion
457  $len = $snake[2];
458  $startx = $snake[0];
459  $starty = $snake[1];
460 
461  // the middle snake is part of the LCS, store it
462  for ( $i = 0; $i < $len; ++$i ) {
463  $this->removed[$startx + $i] = $this->added[$starty + $i] = false;
464  }
465 
466  if ( $d > 1 ) {
467  return $len
468  + $this->lcs_rec( $bottoml1, $startx - 1, $bottoml2,
469  $starty - 1, $V, $snake )
470  + $this->lcs_rec( $startx + $len, $topl1, $starty + $len,
471  $topl2, $V, $snake );
472  } elseif ( $d == 1 ) {
473  /*
474  * In this case the sequences differ by exactly 1 line. We have
475  * already saved all the lines after the difference in the for loop
476  * above, now we need to save all the lines before the difference.
477  */
478  $max = min( $startx - $bottoml1, $starty - $bottoml2 );
479  for ( $i = 0; $i < $max; ++$i ) {
480  $this->removed[$bottoml1 + $i] =
481  $this->added[$bottoml2 + $i] = false;
482  }
483 
484  return $max + $len;
485  }
486 
487  return $len;
488  }
489 
490  private function find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
491  $from = &$this->from;
492  $to = &$this->to;
493  $V0 = &$V[0];
494  $V1 = &$V[1];
495  $snake0 = &$snake[0];
496  $snake1 = &$snake[1];
497  $snake2 = &$snake[2];
498  $bottoml1_min_1 = $bottoml1 - 1;
499  $bottoml2_min_1 = $bottoml2 - 1;
500  $N = $topl1 - $bottoml1_min_1;
501  $M = $topl2 - $bottoml2_min_1;
502  $delta = $N - $M;
503  $maxabsx = $N + $bottoml1;
504  $maxabsy = $M + $bottoml2;
505  $limit = min( $this->maxDifferences, ceil( ( $N + $M ) / 2 ) );
506 
507  // value_to_add_forward: a 0 or 1 that we add to the start
508  // offset to make it odd/even
509  if ( ( $M & 1 ) == 1 ) {
510  $value_to_add_forward = 1;
511  } else {
512  $value_to_add_forward = 0;
513  }
514 
515  if ( ( $N & 1 ) == 1 ) {
516  $value_to_add_backward = 1;
517  } else {
518  $value_to_add_backward = 0;
519  }
520 
521  $start_forward = -$M;
522  $end_forward = $N;
523  $start_backward = -$N;
524  $end_backward = $M;
525 
526  $limit_min_1 = $limit - 1;
527  $limit_plus_1 = $limit + 1;
528 
529  $V0[$limit_plus_1] = 0;
530  $V1[$limit_min_1] = $N;
531  $limit = min( $this->maxDifferences, ceil( ( $N + $M ) / 2 ) );
532 
533  if ( ( $delta & 1 ) == 1 ) {
534  for ( $d = 0; $d <= $limit; ++$d ) {
535  $start_diag = max( $value_to_add_forward + $start_forward, -$d );
536  $end_diag = min( $end_forward, $d );
537  $value_to_add_forward = 1 - $value_to_add_forward;
538 
539  // compute forward furthest reaching paths
540  for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
541  if ( $k == -$d || ( $k < $d
542  && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k] )
543  ) {
544  $x = $V0[$limit_plus_1 + $k];
545  } else {
546  $x = $V0[$limit_min_1 + $k] + 1;
547  }
548 
549  $absx = $snake0 = $x + $bottoml1;
550  $absy = $snake1 = $x - $k + $bottoml2;
551 
552  while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
553  ++$absx;
554  ++$absy;
555  }
556  $x = $absx - $bottoml1;
557 
558  $snake2 = $absx - $snake0;
559  $V0[$limit + $k] = $x;
560  if ( $k >= $delta - $d + 1 && $k <= $delta + $d - 1
561  && $x >= $V1[$limit + $k - $delta]
562  ) {
563  return 2 * $d - 1;
564  }
565 
566  // check to see if we can cut down the diagonal range
567  if ( $x >= $N && $end_forward > $k - 1 ) {
568  $end_forward = $k - 1;
569  } elseif ( $absy - $bottoml2 >= $M ) {
570  $start_forward = $k + 1;
571  $value_to_add_forward = 0;
572  }
573  }
574 
575  $start_diag = max( $value_to_add_backward + $start_backward, -$d );
576  $end_diag = min( $end_backward, $d );
577  $value_to_add_backward = 1 - $value_to_add_backward;
578 
579  // compute backward furthest reaching paths
580  for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
581  if ( $k == $d
582  || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] )
583  ) {
584  $x = $V1[$limit_min_1 + $k];
585  } else {
586  $x = $V1[$limit_plus_1 + $k] - 1;
587  }
588 
589  $y = $x - $k - $delta;
590 
591  $snake2 = 0;
592  while ( $x > 0 && $y > 0
593  && $from[$x + $bottoml1_min_1] === $to[$y + $bottoml2_min_1]
594  ) {
595  --$x;
596  --$y;
597  ++$snake2;
598  }
599  $V1[$limit + $k] = $x;
600 
601  // check to see if we can cut down our diagonal range
602  if ( $x <= 0 ) {
603  $start_backward = $k + 1;
604  $value_to_add_backward = 0;
605  } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
606  $end_backward = $k - 1;
607  }
608  }
609  }
610  } else {
611  for ( $d = 0; $d <= $limit; ++$d ) {
612  $start_diag = max( $value_to_add_forward + $start_forward, -$d );
613  $end_diag = min( $end_forward, $d );
614  $value_to_add_forward = 1 - $value_to_add_forward;
615 
616  // compute forward furthest reaching paths
617  for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
618  if ( $k == -$d
619  || ( $k < $d && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k] )
620  ) {
621  $x = $V0[$limit_plus_1 + $k];
622  } else {
623  $x = $V0[$limit_min_1 + $k] + 1;
624  }
625 
626  $absx = $snake0 = $x + $bottoml1;
627  $absy = $snake1 = $x - $k + $bottoml2;
628 
629  while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
630  ++$absx;
631  ++$absy;
632  }
633  $x = $absx - $bottoml1;
634  $snake2 = $absx - $snake0;
635  $V0[$limit + $k] = $x;
636 
637  // check to see if we can cut down the diagonal range
638  if ( $x >= $N && $end_forward > $k - 1 ) {
639  $end_forward = $k - 1;
640  } elseif ( $absy - $bottoml2 >= $M ) {
641  $start_forward = $k + 1;
642  $value_to_add_forward = 0;
643  }
644  }
645 
646  $start_diag = max( $value_to_add_backward + $start_backward, -$d );
647  $end_diag = min( $end_backward, $d );
648  $value_to_add_backward = 1 - $value_to_add_backward;
649 
650  // compute backward furthest reaching paths
651  for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
652  if ( $k == $d
653  || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] )
654  ) {
655  $x = $V1[$limit_min_1 + $k];
656  } else {
657  $x = $V1[$limit_plus_1 + $k] - 1;
658  }
659 
660  $y = $x - $k - $delta;
661 
662  $snake2 = 0;
663  while ( $x > 0 && $y > 0
664  && $from[$x + $bottoml1_min_1] === $to[$y + $bottoml2_min_1]
665  ) {
666  --$x;
667  --$y;
668  ++$snake2;
669  }
670  $V1[$limit + $k] = $x;
671 
672  if ( $k >= -$delta - $d && $k <= $d - $delta
673  && $x <= $V0[$limit + $k + $delta]
674  ) {
675  $snake0 = $bottoml1 + $x;
676  $snake1 = $bottoml2 + $y;
677 
678  return 2 * $d;
679  }
680 
681  // check to see if we can cut down our diagonal range
682  if ( $x <= 0 ) {
683  $start_backward = $k + 1;
684  $value_to_add_backward = 0;
685  } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
686  $end_backward = $k - 1;
687  }
688  }
689  }
690  }
691  /*
692  * computing the true LCS is too expensive, instead find the diagonal
693  * with the most progress and pretend a midle snake of length 0 occurs
694  * there.
695  */
696 
697  $most_progress = self::findMostProgress( $M, $N, $limit, $V );
698 
699  $snake0 = $bottoml1 + $most_progress[0];
700  $snake1 = $bottoml2 + $most_progress[1];
701  $snake2 = 0;
702  wfDebug( "Computing the LCS is too expensive. Using a heuristic.\n" );
703  $this->heuristicUsed = true;
704 
705  return 5; /*
706  * HACK: since we didn't really finish the LCS computation
707  * we don't really know the length of the SES. We don't do
708  * anything with the result anyway, unless it's <=1. We know
709  * for a fact SES > 1 so 5 is as good a number as any to
710  * return here
711  */
712  }
713 
714  private static function findMostProgress( $M, $N, $limit, $V ) {
715  $delta = $N - $M;
716 
717  if ( ( $M & 1 ) == ( $limit & 1 ) ) {
718  $forward_start_diag = max( -$M, -$limit );
719  } else {
720  $forward_start_diag = max( 1 - $M, -$limit );
721  }
722 
723  $forward_end_diag = min( $N, $limit );
724 
725  if ( ( $N & 1 ) == ( $limit & 1 ) ) {
726  $backward_start_diag = max( -$N, -$limit );
727  } else {
728  $backward_start_diag = max( 1 - $N, -$limit );
729  }
730 
731  $backward_end_diag = -min( $M, $limit );
732 
733  $temp = [ 0, 0, 0 ];
734 
735  $max_progress = array_fill( 0, ceil( max( $forward_end_diag - $forward_start_diag,
736  $backward_end_diag - $backward_start_diag ) / 2 ), $temp );
737  $num_progress = 0; // the 1st entry is current, it is initialized
738  // with 0s
739 
740  // first search the forward diagonals
741  for ( $k = $forward_start_diag; $k <= $forward_end_diag; $k += 2 ) {
742  $x = $V[0][$limit + $k];
743  $y = $x - $k;
744  if ( $x > $N || $y > $M ) {
745  continue;
746  }
747 
748  $progress = $x + $y;
749  if ( $progress > $max_progress[0][2] ) {
750  $num_progress = 0;
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] ) {
755  ++$num_progress;
756  $max_progress[$num_progress][0] = $x;
757  $max_progress[$num_progress][1] = $y;
758  $max_progress[$num_progress][2] = $progress;
759  }
760  }
761 
762  $max_progress_forward = true; // initially the maximum
763  // progress is in the forward
764  // direction
765 
766  // now search the backward diagonals
767  for ( $k = $backward_start_diag; $k <= $backward_end_diag; $k += 2 ) {
768  $x = $V[1][$limit + $k];
769  $y = $x - $k - $delta;
770  if ( $x < 0 || $y < 0 ) {
771  continue;
772  }
773 
774  $progress = $N - $x + $M - $y;
775  if ( $progress > $max_progress[0][2] ) {
776  $num_progress = 0;
777  $max_progress_forward = false;
778  $max_progress[0][0] = $x;
779  $max_progress[0][1] = $y;
780  $max_progress[0][2] = $progress;
781  } elseif ( $progress == $max_progress[0][2] && !$max_progress_forward ) {
782  ++$num_progress;
783  $max_progress[$num_progress][0] = $x;
784  $max_progress[$num_progress][1] = $y;
785  $max_progress[$num_progress][2] = $progress;
786  }
787  }
788 
789  // return the middle diagonal with maximal progress.
790  return $max_progress[(int)floor( $num_progress / 2 )];
791  }
792 
796  public function getLcsLength() {
797  if ( $this->heuristicUsed && !$this->lcsLengthCorrectedForHeuristic ) {
798  $this->lcsLengthCorrectedForHeuristic = true;
799  $this->length = $this->m - array_sum( $this->added );
800  }
801 
802  return $this->length;
803  }
804 
805 }
806 
814 
816  public $leftstart;
817 
819  public $leftend;
820 
822  public $leftlength;
823 
825  public $rightstart;
826 
828  public $rightend;
829 
831  public $rightlength;
832 
834  $this->leftstart = $leftstart;
835  $this->leftend = $leftend;
836  $this->leftlength = $leftend - $leftstart;
837  $this->rightstart = $rightstart;
838  $this->rightend = $rightend;
839  $this->rightlength = $rightend - $rightstart;
840  }
841 
842 }
DiffEngine\$bailoutComplexity
$bailoutComplexity
Definition: DiffEngine.php:55
DiffEngine\$from
$from
Definition: DiffEngine.php:47
DiffEngine\shiftBoundaries
shiftBoundaries(array $lines, array &$changed, array $other_changed)
Adjust inserts/deletes of identical lines to join changes as much as possible.
Definition: DiffEngine.php:160
RangeDifference\$leftend
int $leftend
Definition: DiffEngine.php:819
RangeDifference\__construct
__construct( $leftstart, $leftend, $rightstart, $rightend)
Definition: DiffEngine.php:833
DiffEngine\$heuristicUsed
$heuristicUsed
Definition: DiffEngine.php:65
DiffEngine\$maxDifferences
$maxDifferences
Definition: DiffEngine.php:58
DiffOpDelete
Extends DiffOp.
Definition: DairikiDiff.php:132
captcha-old.count
count
Definition: captcha-old.py:225
RangeDifference\$rightstart
int $rightstart
Definition: DiffEngine.php:825
RangeDifference\$rightlength
int $rightlength
Definition: DiffEngine.php:831
use
as see the revision history and available at free of to any person obtaining a copy of this software and associated documentation to deal in the Software without including without limitation the rights to use
Definition: MIT-LICENSE.txt:10
php
injection txt This is an overview of how MediaWiki makes use of dependency injection The design described here grew from the discussion of RFC T384 The term dependency this means that anything an object needs to operate should be injected from the the object itself should only know narrow no concrete implementation of the logic it relies on The requirement to inject everything typically results in an architecture that based on two main types of and essentially stateless service objects that use other service objects to operate on the value objects As of the beginning MediaWiki is only starting to use the DI approach Much of the code still relies on global state or direct resulting in a highly cyclical dependency which acts as the top level factory for services in MediaWiki which can be used to gain access to default instances of various services MediaWikiServices however also allows new services to be defined and default services to be redefined Services are defined or redefined by providing a callback the instantiator that will return a new instance of the service When it will create an instance of MediaWikiServices and populate it with the services defined in the files listed by thereby bootstrapping the DI framework Per $wgServiceWiringFiles lists includes ServiceWiring php
Definition: injection.txt:35
DiffOpChange
Extends DiffOp.
Definition: DairikiDiff.php:178
DiffEngine\diff
diff( $from_lines, $to_lines)
Performs diff.
Definition: DiffEngine.php:81
DiffEngine\getLcsLength
getLcsLength()
Definition: DiffEngine.php:796
DiffOpCopy
Extends DiffOp.
Definition: DairikiDiff.php:106
DiffEngine\$to
$to
Definition: DiffEngine.php:48
DiffEngine\$length
$length
Definition: DiffEngine.php:62
DiffOpAdd
Extends DiffOp.
Definition: DairikiDiff.php:155
DiffEngine\setBailoutComplexity
setBailoutComplexity( $value)
Sets the complexity (in comparison operations) that can't be exceeded.
Definition: DiffEngine.php:139
$limit
this hook is for auditing only RecentChangesLinked and Watchlist RecentChangesLinked and Watchlist Do not use this to implement individual filters if they are compatible with the ChangesListFilter and ChangesListFilterGroup structure use sub classes of those in conjunction with the ChangesListSpecialPageStructuredFilters hook This hook can be used to implement filters that do not implement that or custom behavior that is not an individual filter e g Watchlist and Watchlist you will want to construct new ChangesListBooleanFilter or ChangesListStringOptionsFilter objects When constructing you specify which group they belong to You can reuse existing or create your you must register them with $special registerFilterGroup removed from all revisions and log entries to which it was applied This gives extensions a chance to take it off their books as the deletion has already been partly carried out by this point or something similar the user will be unable to create the tag set and then return false from the hook function Ensure you consume the ChangeTagAfterDelete hook to carry out custom deletion actions as context called by AbstractContent::getParserOutput May be used to override the normal model specific rendering of page content as context as context the output can only depend on parameters provided to this hook not on global state indicating whether full HTML should be generated If generation of HTML may be but other information should still be present in the ParserOutput object to manipulate or replace but no entry for that model exists in $wgContentHandlers please use GetContentModels hook to make them known to core if desired whether it is OK to use $contentModel on $title Handler functions that modify $ok should generally return false to prevent further hooks from further modifying $ok inclusive $limit
Definition: hooks.txt:1049
$lines
$lines
Definition: router.php:67
DiffEngine\findMostProgress
static findMostProgress( $M, $N, $limit, $V)
Definition: DiffEngine.php:714
wfDebug
wfDebug( $text, $dest='all', array $context=[])
Sends a line to the debug log if enabled or, optionally, to a comment in output.
Definition: GlobalFunctions.php:999
DiffEngine\$m
$m
Definition: DiffEngine.php:49
RangeDifference\$rightend
int $rightend
Definition: DiffEngine.php:828
DiffEngine\diff_range
diff_range( $from_lines, $to_lines)
Definition: DiffEngine.php:411
RangeDifference\$leftlength
int $leftlength
Definition: DiffEngine.php:822
$value
$value
Definition: styleTest.css.php:45
DiffEngine\$tooLong
$tooLong
Definition: DiffEngine.php:52
DiffEngine\__construct
__construct( $tooLong=2000000, $powLimit=1.45)
Definition: DiffEngine.php:67
DiffEngine\$lcsLengthCorrectedForHeuristic
$lcsLengthCorrectedForHeuristic
Definition: DiffEngine.php:59
DiffEngine
This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which in turn...
Definition: DiffEngine.php:44
DiffEngine\$added
$added
Definition: DiffEngine.php:64
as
This document is intended to provide useful advice for parties seeking to redistribute MediaWiki to end users It s targeted particularly at maintainers for Linux since it s been observed that distribution packages of MediaWiki often break We ve consistently had to recommend that users seeking support use official tarballs instead of their distribution s and this often solves whatever problem the user is having It would be nice if this could such as
Definition: distributors.txt:9
MediaWiki\Diff\ComplexityException
Definition: ComplexityException.php:26
from
Apache License January AND DISTRIBUTION Definitions License shall mean the terms and conditions for and distribution as defined by Sections through of this document Licensor shall mean the copyright owner or entity authorized by the copyright owner that is granting the License Legal Entity shall mean the union of the acting entity and all other entities that control are controlled by or are under common control with that entity For the purposes of this definition control direct or to cause the direction or management of such whether by contract or including but not limited to software source documentation and configuration files Object form shall mean any form resulting from mechanical transformation or translation of a Source including but not limited to compiled object generated and conversions to other media types Work shall mean the work of whether in Source or Object made available under the as indicated by a copyright notice that is included in or attached to the whether in Source or Object that is based or other modifications as a an original work of authorship For the purposes of this Derivative Works shall not include works that remain separable from
Definition: APACHE-LICENSE-2.0.txt:43
RangeDifference\$leftstart
int $leftstart
Definition: DiffEngine.php:816
DiffEngine\lcs_rec
lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
Definition: DiffEngine.php:446
DiffEngine\$n
$n
Definition: DiffEngine.php:50
DiffEngine\$powLimit
$powLimit
Definition: DiffEngine.php:53
RangeDifference
Alternative representation of a set of changes, by the index ranges that are changed.
Definition: DiffEngine.php:813
array
the array() calling protocol came about after MediaWiki 1.4rc1.
n
print Searching for spam in $maxID pages n
Definition: cleanup.php:99
DiffEngine\diffInternal
diffInternal(array $from, array $to)
Definition: DiffEngine.php:282
DiffEngine\find_middle_snake
find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
Definition: DiffEngine.php:490
DiffEngine\$removed
$removed
Definition: DiffEngine.php:63