70 $this->heuristicUsed =
false;
74 $added =
$n > 0 ? array_fill( 0,
$n,
true ) : [];
87 while ( $i + $j <=
$m && $i + $j <=
$n &&
$from[
$m - $j] ===
$to[
$n - $j] ) {
93 $this->
from = $newFromIndex = $this->to = $newToIndex = [];
98 $shared[
$key] =
false;
101 foreach (
$to as $index => &$el ) {
102 if ( array_key_exists( $el, $shared ) ) {
106 $newToIndex[] = $index;
109 foreach (
$from as $index => &$el ) {
110 if ( $shared[$el] ) {
113 $newFromIndex[] = $index;
119 $this->m = count( $this->
from );
120 $this->
n = count( $this->to );
122 $this->removed = $this->m > 0 ? array_fill( 0, $this->m,
true ) : [];
123 $this->added = $this->
n > 0 ? array_fill( 0, $this->
n,
true ) : [];
125 if ( $this->m == 0 || $this->
n == 0 ) {
128 $this->maxDifferences = ceil( ( $this->m + $this->
n ) / 2.0 );
129 if ( $this->m * $this->
n > $this->tooLong ) {
131 $this->maxDifferences = floor( pow( $this->maxDifferences, $this->powLimit - 1.0 ) );
132 wfDebug(
"Limiting max number of differences to $this->maxDifferences\n" );
139 $max = min( $this->m, $this->
n );
140 for ( $forwardBound = 0; $forwardBound < $max
141 && $this->
from[$forwardBound] === $this->to[$forwardBound];
144 $this->removed[$forwardBound] = $this->added[$forwardBound] =
false;
147 $backBoundL1 = $this->m - 1;
148 $backBoundL2 = $this->
n - 1;
150 while ( $backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
151 && $this->from[$backBoundL1] === $this->to[$backBoundL2]
153 $this->removed[$backBoundL1--] = $this->added[$backBoundL2--] =
false;
156 $temp = array_fill( 0, $this->m + $this->
n + 1, 0 );
157 $V = [ $temp, $temp ];
158 $snake = [ 0, 0, 0 ];
160 $this->length = $forwardBound + $this->m - $backBoundL1 - 1
174 $this->length += $i + $j - 1;
176 foreach ( $this->removed
as $key => &$removed_elem ) {
177 if ( !$removed_elem ) {
181 foreach ( $this->added
as $key => &$added_elem ) {
182 if ( !$added_elem ) {
192 $this->
diff( $from_lines, $to_lines );
193 unset( $from_lines, $to_lines );
197 while ( $xi < $this->m || $yi < $this->
n ) {
199 while ( $xi < $this->m && $yi < $this->n
200 && !$this->removed[$xi]
201 && !$this->added[$yi]
208 while ( $xi < $this->m && $this->removed[$xi] ) {
213 while ( $yi < $this->n && $this->added[$yi] ) {
217 if ( $xi > $xstart || $yi > $ystart ) {
225 private function lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
227 if ( $bottoml1 > $topl1 || $bottoml2 > $topl2 ) {
232 $topl2, $V, $snake );
241 for ( $i = 0; $i < $len; ++$i ) {
242 $this->removed[$startx + $i] = $this->added[$starty + $i] =
false;
247 + $this->
lcs_rec( $bottoml1, $startx - 1, $bottoml2,
248 $starty - 1, $V, $snake )
249 + $this->
lcs_rec( $startx + $len, $topl1, $starty + $len,
250 $topl2, $V, $snake );
251 } elseif ( $d == 1 ) {
257 $max = min( $startx - $bottoml1, $starty - $bottoml2 );
258 for ( $i = 0; $i < $max; ++$i ) {
259 $this->removed[$bottoml1 + $i] =
260 $this->added[$bottoml2 + $i] =
false;
274 $snake0 = &$snake[0];
275 $snake1 = &$snake[1];
276 $snake2 = &$snake[2];
277 $bottoml1_min_1 = $bottoml1 - 1;
278 $bottoml2_min_1 = $bottoml2 - 1;
279 $N = $topl1 - $bottoml1_min_1;
280 $M = $topl2 - $bottoml2_min_1;
282 $maxabsx = $N + $bottoml1;
283 $maxabsy = $M + $bottoml2;
284 $limit = min( $this->maxDifferences, ceil( ( $N + $M ) / 2 ) );
288 if ( ( $M & 1 ) == 1 ) {
289 $value_to_add_forward = 1;
291 $value_to_add_forward = 0;
294 if ( ( $N & 1 ) == 1 ) {
295 $value_to_add_backward = 1;
297 $value_to_add_backward = 0;
300 $start_forward = -$M;
302 $start_backward = -$N;
305 $limit_min_1 =
$limit - 1;
306 $limit_plus_1 =
$limit + 1;
308 $V0[$limit_plus_1] = 0;
309 $V1[$limit_min_1] = $N;
310 $limit = min( $this->maxDifferences, ceil( ( $N + $M ) / 2 ) );
312 if ( ( $delta & 1 ) == 1 ) {
313 for ( $d = 0; $d <=
$limit; ++$d ) {
314 $start_diag = max( $value_to_add_forward + $start_forward, -$d );
315 $end_diag = min( $end_forward, $d );
316 $value_to_add_forward = 1 - $value_to_add_forward;
319 for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
320 if ( $k == -$d || ( $k < $d
321 && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k] )
323 $x = $V0[$limit_plus_1 + $k];
325 $x = $V0[$limit_min_1 + $k] + 1;
328 $absx = $snake0 = $x + $bottoml1;
329 $absy = $snake1 = $x - $k + $bottoml2;
331 while ( $absx < $maxabsx && $absy < $maxabsy &&
$from[$absx] ===
$to[$absy] ) {
335 $x = $absx - $bottoml1;
337 $snake2 = $absx - $snake0;
339 if ( $k >= $delta - $d + 1 && $k <= $delta + $d - 1
340 && $x >= $V1[
$limit + $k - $delta]
346 if ( $x >= $N && $end_forward > $k - 1 ) {
347 $end_forward = $k - 1;
348 } elseif ( $absy - $bottoml2 >= $M ) {
349 $start_forward = $k + 1;
350 $value_to_add_forward = 0;
354 $start_diag = max( $value_to_add_backward + $start_backward, -$d );
355 $end_diag = min( $end_backward, $d );
356 $value_to_add_backward = 1 - $value_to_add_backward;
359 for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
361 || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] )
363 $x = $V1[$limit_min_1 + $k];
365 $x = $V1[$limit_plus_1 + $k] - 1;
368 $y = $x - $k - $delta;
371 while ( $x > 0 && $y > 0
372 &&
$from[$x + $bottoml1_min_1] ===
$to[$y + $bottoml2_min_1]
382 $start_backward = $k + 1;
383 $value_to_add_backward = 0;
384 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
385 $end_backward = $k - 1;
390 for ( $d = 0; $d <=
$limit; ++$d ) {
391 $start_diag = max( $value_to_add_forward + $start_forward, -$d );
392 $end_diag = min( $end_forward, $d );
393 $value_to_add_forward = 1 - $value_to_add_forward;
396 for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
398 || ( $k < $d && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k] )
400 $x = $V0[$limit_plus_1 + $k];
402 $x = $V0[$limit_min_1 + $k] + 1;
405 $absx = $snake0 = $x + $bottoml1;
406 $absy = $snake1 = $x - $k + $bottoml2;
408 while ( $absx < $maxabsx && $absy < $maxabsy &&
$from[$absx] ===
$to[$absy] ) {
412 $x = $absx - $bottoml1;
413 $snake2 = $absx - $snake0;
417 if ( $x >= $N && $end_forward > $k - 1 ) {
418 $end_forward = $k - 1;
419 } elseif ( $absy - $bottoml2 >= $M ) {
420 $start_forward = $k + 1;
421 $value_to_add_forward = 0;
425 $start_diag = max( $value_to_add_backward + $start_backward, -$d );
426 $end_diag = min( $end_backward, $d );
427 $value_to_add_backward = 1 - $value_to_add_backward;
430 for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
432 || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] )
434 $x = $V1[$limit_min_1 + $k];
436 $x = $V1[$limit_plus_1 + $k] - 1;
439 $y = $x - $k - $delta;
442 while ( $x > 0 && $y > 0
443 &&
$from[$x + $bottoml1_min_1] ===
$to[$y + $bottoml2_min_1]
451 if ( $k >= -$delta - $d && $k <= $d - $delta
452 && $x <= $V0[
$limit + $k + $delta]
454 $snake0 = $bottoml1 + $x;
455 $snake1 = $bottoml2 + $y;
462 $start_backward = $k + 1;
463 $value_to_add_backward = 0;
464 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
465 $end_backward = $k - 1;
476 $most_progress = self::findMostProgress( $M, $N,
$limit, $V );
478 $snake0 = $bottoml1 + $most_progress[0];
479 $snake1 = $bottoml2 + $most_progress[1];
481 wfDebug(
"Computing the LCS is too expensive. Using a heuristic.\n" );
482 $this->heuristicUsed =
true;
496 if ( ( $M & 1 ) == (
$limit & 1 ) ) {
497 $forward_start_diag = max( -$M, -
$limit );
499 $forward_start_diag = max( 1 - $M, -
$limit );
502 $forward_end_diag = min( $N,
$limit );
504 if ( ( $N & 1 ) == (
$limit & 1 ) ) {
505 $backward_start_diag = max( -$N, -
$limit );
507 $backward_start_diag = max( 1 - $N, -
$limit );
510 $backward_end_diag = -min( $M,
$limit );
514 $max_progress = array_fill( 0, ceil( max( $forward_end_diag - $forward_start_diag,
515 $backward_end_diag - $backward_start_diag ) / 2 ), $temp );
520 for ( $k = $forward_start_diag; $k <= $forward_end_diag; $k += 2 ) {
523 if ( $x > $N || $y > $M ) {
528 if ( $progress > $max_progress[0][2] ) {
530 $max_progress[0][0] = $x;
531 $max_progress[0][1] = $y;
532 $max_progress[0][2] = $progress;
533 } elseif ( $progress == $max_progress[0][2] ) {
535 $max_progress[$num_progress][0] = $x;
536 $max_progress[$num_progress][1] = $y;
537 $max_progress[$num_progress][2] = $progress;
541 $max_progress_forward =
true;
546 for ( $k = $backward_start_diag; $k <= $backward_end_diag; $k += 2 ) {
548 $y = $x - $k - $delta;
549 if ( $x < 0 || $y < 0 ) {
553 $progress = $N - $x + $M - $y;
554 if ( $progress > $max_progress[0][2] ) {
556 $max_progress_forward =
false;
557 $max_progress[0][0] = $x;
558 $max_progress[0][1] = $y;
559 $max_progress[0][2] = $progress;
560 } elseif ( $progress == $max_progress[0][2] && !$max_progress_forward ) {
562 $max_progress[$num_progress][0] = $x;
563 $max_progress[$num_progress][1] = $y;
564 $max_progress[$num_progress][2] = $progress;
569 return $max_progress[(int)floor( $num_progress / 2 )];
576 if ( $this->heuristicUsed && !$this->lcsLengthCorrectedForHeuristic ) {
577 $this->lcsLengthCorrectedForHeuristic =
true;
578 $this->length = $this->m - array_sum( $this->added );
__construct($leftstart, $leftend, $rightstart, $rightend)
magic word the default is to use $key to get the and $key value or $key value text $key value html to format the value $key
diff_range($from_lines, $to_lines)
Alternative representation of a set of changes, by the index ranges that are changed.
This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which in turn...
find_middle_snake($bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
__construct($tooLong=2000000, $powLimit=1.45)
wfDebug($text, $dest= 'all', array $context=[])
Sends a line to the debug log if enabled or, optionally, to a comment in output.
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
static findMostProgress($M, $N, $limit, $V)
lcs_rec($bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake)
while(($__line=Maintenance::readconsole())!==false) print n
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
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
this hook is for auditing only RecentChangesLinked and Watchlist RecentChangesLinked and Watchlist e g Watchlist 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 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
$lcsLengthCorrectedForHeuristic