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
50  private $from;
51  private $to;
52  private $m;
53  private $n;
54 
55  private $tooLong;
56  private $powLimit;
57 
58  protected $bailoutComplexity = 0;
59 
60  // State variables
61  private $maxDifferences;
63 
64  // Output variables
65  public $length;
66  public $removed;
67  public $added;
69 
70  function __construct( $tooLong = 2000000, $powLimit = 1.45 ) {
71  $this->tooLong = $tooLong;
72  $this->powLimit = $powLimit;
73  }
74 
84  public function diff( $from_lines, $to_lines ) {
85  // Diff and store locally
86  $this->diffInternal( $from_lines, $to_lines );
87 
88  // Merge edits when possible
89  $this->shiftBoundaries( $from_lines, $this->removed, $this->added );
90  $this->shiftBoundaries( $to_lines, $this->added, $this->removed );
91 
92  // Compute the edit operations.
93  $n_from = count( $from_lines );
94  $n_to = count( $to_lines );
95 
96  $edits = [];
97  $xi = $yi = 0;
98  while ( $xi < $n_from || $yi < $n_to ) {
99  assert( $yi < $n_to || $this->removed[$xi] );
100  assert( $xi < $n_from || $this->added[$yi] );
101 
102  // Skip matching "snake".
103  $copy = [];
104  while ( $xi < $n_from && $yi < $n_to
105  && !$this->removed[$xi] && !$this->added[$yi]
106  ) {
107  $copy[] = $from_lines[$xi++];
108  ++$yi;
109  }
110  if ( $copy ) {
111  $edits[] = new DiffOpCopy( $copy );
112  }
113 
114  // Find deletes & adds.
115  $delete = [];
116  while ( $xi < $n_from && $this->removed[$xi] ) {
117  $delete[] = $from_lines[$xi++];
118  }
119 
120  $add = [];
121  while ( $yi < $n_to && $this->added[$yi] ) {
122  $add[] = $to_lines[$yi++];
123  }
124 
125  if ( $delete && $add ) {
126  $edits[] = new DiffOpChange( $delete, $add );
127  } elseif ( $delete ) {
128  $edits[] = new DiffOpDelete( $delete );
129  } elseif ( $add ) {
130  $edits[] = new DiffOpAdd( $add );
131  }
132  }
133 
134  return $edits;
135  }
136 
141  public function setBailoutComplexity( $value ) {
142  $this->bailoutComplexity = $value;
143  }
144 
162  private function shiftBoundaries( array $lines, array &$changed, array $other_changed ) {
163  $i = 0;
164  $j = 0;
165 
166  assert( count( $lines ) == count( $changed ) );
167  $len = count( $lines );
168  $other_len = count( $other_changed );
169 
170  while ( 1 ) {
171  /*
172  * Scan forwards to find beginning of another run of changes.
173  * Also keep track of the corresponding point in the other file.
174  *
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
178  * (unchanged lines).
179  * Furthermore, $j is always kept so that $j == $other_len or
180  * $other_changed[$j] == false.
181  */
182  while ( $j < $other_len && $other_changed[$j] ) {
183  $j++;
184  }
185 
186  while ( $i < $len && !$changed[$i] ) {
187  assert( $j < $other_len && !$other_changed[$j] );
188  $i++;
189  $j++;
190  while ( $j < $other_len && $other_changed[$j] ) {
191  $j++;
192  }
193  }
194 
195  if ( $i == $len ) {
196  break;
197  }
198 
199  $start = $i;
200 
201  // Find the end of this run of changes.
202  while ( ++$i < $len && $changed[$i] ) {
203  continue;
204  }
205 
206  do {
207  /*
208  * Record the length of this run of changes, so that
209  * we can later determine whether the run has grown.
210  */
211  $runlength = $i - $start;
212 
213  /*
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.
217  */
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] ) {
222  $start--;
223  }
224  assert( $j > 0 );
225  while ( $other_changed[--$j] ) {
226  continue;
227  }
228  assert( $j >= 0 && !$other_changed[$j] );
229  }
230 
231  /*
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.
235  */
236  $corresponding = $j < $other_len ? $i : $len;
237 
238  /*
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.
244  */
245  while ( $i < $len && $lines[$start] == $lines[$i] ) {
246  $changed[$start++] = false;
247  $changed[$i++] = 1;
248  while ( $i < $len && $changed[$i] ) {
249  $i++;
250  }
251 
252  assert( $j < $other_len && !$other_changed[$j] );
253  $j++;
254  if ( $j < $other_len && $other_changed[$j] ) {
255  $corresponding = $i;
256  while ( $j < $other_len && $other_changed[$j] ) {
257  $j++;
258  }
259  }
260  }
261  } while ( $runlength != $i - $start );
262 
263  /*
264  * If possible, move the fully-merged run of changes
265  * back to a corresponding run in the other file.
266  */
267  while ( $corresponding < $i ) {
268  $changed[--$start] = 1;
269  $changed[--$i] = 0;
270  assert( $j > 0 );
271  while ( $other_changed[--$j] ) {
272  continue;
273  }
274  assert( $j >= 0 && !$other_changed[$j] );
275  }
276  }
277  }
278 
284  protected function diffInternal( array $from, array $to ) {
285  // remember initial lengths
286  $m = count( $from );
287  $n = count( $to );
288 
289  $this->heuristicUsed = false;
290 
291  // output
292  $removed = $m > 0 ? array_fill( 0, $m, true ) : [];
293  $added = $n > 0 ? array_fill( 0, $n, true ) : [];
294 
295  // reduce the complexity for the next step (intentionally done twice)
296  // remove common tokens at the start
297  $i = 0;
298  while ( $i < $m && $i < $n && $from[$i] === $to[$i] ) {
299  $removed[$i] = $added[$i] = false;
300  unset( $from[$i], $to[$i] );
301  ++$i;
302  }
303 
304  // remove common tokens at the end
305  $j = 1;
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] );
309  ++$j;
310  }
311 
312  $this->from = $newFromIndex = $this->to = $newToIndex = [];
313 
314  // remove tokens not in both sequences
315  $shared = [];
316  foreach ( $from as $key ) {
317  $shared[$key] = false;
318  }
319 
320  foreach ( $to as $index => &$el ) {
321  if ( array_key_exists( $el, $shared ) ) {
322  // keep it
323  $this->to[] = $el;
324  $shared[$el] = true;
325  $newToIndex[] = $index;
326  }
327  }
328  foreach ( $from as $index => &$el ) {
329  if ( $shared[$el] ) {
330  // keep it
331  $this->from[] = $el;
332  $newFromIndex[] = $index;
333  }
334  }
335 
336  unset( $shared, $from, $to );
337 
338  $this->m = count( $this->from );
339  $this->n = count( $this->to );
340 
341  if ( $this->bailoutComplexity > 0 && $this->m * $this->n > $this->bailoutComplexity ) {
342  throw new ComplexityException();
343  }
344 
345  $this->removed = $this->m > 0 ? array_fill( 0, $this->m, true ) : [];
346  $this->added = $this->n > 0 ? array_fill( 0, $this->n, true ) : [];
347 
348  if ( $this->m == 0 || $this->n == 0 ) {
349  $this->length = 0;
350  } else {
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" );
356  }
357 
358  /*
359  * The common prefixes and suffixes are always part of some LCS, include
360  * them now to reduce our search space
361  */
362  $max = min( $this->m, $this->n );
363  for ( $forwardBound = 0; $forwardBound < $max
364  && $this->from[$forwardBound] === $this->to[$forwardBound];
365  ++$forwardBound
366  ) {
367  $this->removed[$forwardBound] = $this->added[$forwardBound] = false;
368  }
369 
370  $backBoundL1 = $this->m - 1;
371  $backBoundL2 = $this->n - 1;
372 
373  while ( $backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
374  && $this->from[$backBoundL1] === $this->to[$backBoundL2]
375  ) {
376  $this->removed[$backBoundL1--] = $this->added[$backBoundL2--] = false;
377  }
378 
379  $temp = array_fill( 0, $this->m + $this->n + 1, 0 );
380  $V = [ $temp, $temp ];
381  $snake = [ 0, 0, 0 ];
382 
383  $this->length = $forwardBound + $this->m - $backBoundL1 - 1
384  + $this->lcs_rec(
385  $forwardBound,
386  $backBoundL1,
387  $forwardBound,
388  $backBoundL2,
389  $V,
390  $snake
391  );
392  }
393 
394  $this->m = $m;
395  $this->n = $n;
396 
397  $this->length += $i + $j - 1;
398 
399  foreach ( $this->removed as $key => &$removed_elem ) {
400  if ( !$removed_elem ) {
401  $removed[$newFromIndex[$key]] = false;
402  }
403  }
404  foreach ( $this->added as $key => &$added_elem ) {
405  if ( !$added_elem ) {
406  $added[$newToIndex[$key]] = false;
407  }
408  }
409  $this->removed = $removed;
410  $this->added = $added;
411  }
412 
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 );
417 
418  $ranges = [];
419  $xi = $yi = 0;
420  while ( $xi < $this->m || $yi < $this->n ) {
421  // Matching "snake".
422  while ( $xi < $this->m && $yi < $this->n
423  && !$this->removed[$xi]
424  && !$this->added[$yi]
425  ) {
426  ++$xi;
427  ++$yi;
428  }
429  // Find deletes & adds.
430  $xstart = $xi;
431  while ( $xi < $this->m && $this->removed[$xi] ) {
432  ++$xi;
433  }
434 
435  $ystart = $yi;
436  while ( $yi < $this->n && $this->added[$yi] ) {
437  ++$yi;
438  }
439 
440  if ( $xi > $xstart || $yi > $ystart ) {
441  $ranges[] = new RangeDifference( $xstart, $xi, $ystart, $yi );
442  }
443  }
444 
445  return $ranges;
446  }
447 
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 ) {
451  return 0;
452  }
453 
454  $d = $this->find_middle_snake( $bottoml1, $topl1, $bottoml2,
455  $topl2, $V, $snake );
456 
457  // need to store these so we don't lose them when they're
458  // overwritten by the recursion
459  list( $startx, $starty, $len ) = $snake;
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 ) {
510  $value_to_add_forward = 1;
511  } else {
512  $value_to_add_forward = 0;
513  }
514 
515  if ( $N & 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 ) {
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 }
deferred txt A few of the database updates required by various functions here can be deferred until after the result page is displayed to the user For updating the view updating the linked to tables after a etc PHP does not yet have any way to tell the server to actually return and disconnect while still running these but it might have such a feature in the future We handle these by creating a deferred update object and putting those objects on a global list
Definition: deferred.txt:11
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:62
Apache License January AND DISTRIBUTION Definitions License shall mean the terms and conditions for use
diff_range( $from_lines, $to_lines)
Definition: DiffEngine.php:413
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
find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
Definition: DiffEngine.php:490
$value
static findMostProgress( $M, $N, $limit, $V)
Definition: DiffEngine.php:714
Extends DiffOp.
Definition: DiffOpAdd.php:35
__construct( $tooLong=2000000, $powLimit=1.45)
Definition: DiffEngine.php:70
lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
Definition: DiffEngine.php:448
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:284
diff( $from_lines, $to_lines)
Performs diff.
Definition: DiffEngine.php:84
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
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:141
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
$lines
Definition: router.php:61
shiftBoundaries(array $lines, array &$changed, array $other_changed)
Adjust inserts/deletes of identical lines to join changes as much as possible.
Definition: DiffEngine.php:162
while(( $__line=Maintenance::readconsole()) !==false) print n
Definition: eval.php:64
Extends DiffOp.