includes/diff/DairikiDiff.php

   1 <?php
   2 /**
   3  * A PHP diff engine for phpwiki. (Taken from phpwiki-1.3.3)
   4  *
   5  * Copyright © 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
   6  * You may copy this code freely under the conditions of the GPL.
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License along
  19  * with this program; if not, write to the Free Software Foundation, Inc.,
  20  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  21  * http://www.gnu.org/copyleft/gpl.html
  22  *
  23  * @file
  24  * @ingroup DifferenceEngine
  25  * @defgroup DifferenceEngine DifferenceEngine
  26  */
  27
  28 /**
  29  * @todo document
  30  * @private
  31  * @ingroup DifferenceEngine
  32  */
  33 abstract class DiffOp {
  34
  35         public $type;
  36         public $orig;
  37         public $closing;
  38
  39         public function getType() {
  40                 return $this->type;
  41         }
  42
  43         public function getOrig() {
  44                 return $this->orig;
  45         }
  46
  47         public function getClosing( $i = null ) {
  48                 if( $i === null ) {
  49                         return $this->closing;
  50                 }
  51                 if( array_key_exists( $i, $this->closing ) ) {
  52                         return $this->closing[$i];
  53                 }
  54                 return null;
  55         }
  56
  57         abstract public function reverse();
  58
  59         /**
  60          * @return int
  61          */
  62         public function norig() {
  63                 return $this->orig ? count( $this->orig ) : 0;
  64         }
  65
  66         /**
  67          * @return int
  68          */
  69         public function nclosing() {
  70                 return $this->closing ? count( $this->closing ) : 0;
  71         }
  72 }
  73
  74 /**
  75  * @todo document
  76  * @private
  77  * @ingroup DifferenceEngine
  78  */
  79 class DiffOpCopy extends DiffOp {
  80         public $type = 'copy';
  81
  82         public function __construct( $orig, $closing = false ) {
  83                 if ( !is_array( $closing ) ) {
  84                         $closing = $orig;
  85                 }
  86                 $this->orig = $orig;
  87                 $this->closing = $closing;
  88         }
  89
  90         /**
  91          * @return DiffOpCopy
  92          */
  93         public function reverse() {
  94                 return new DiffOpCopy( $this->closing, $this->orig );
  95         }
  96 }
  97
  98 /**
  99  * @todo document
 100  * @private
 101  * @ingroup DifferenceEngine
 102  */
 103 class DiffOpDelete extends DiffOp {
 104         public $type = 'delete';
 105
 106         public function __construct( $lines ) {
 107                 $this->orig = $lines;
 108                 $this->closing = false;
 109         }
 110
 111         /**
 112          * @return DiffOpAdd
 113          */
 114         public function reverse() {
 115                 return new DiffOpAdd( $this->orig );
 116         }
 117 }
 118
 119 /**
 120  * @todo document
 121  * @private
 122  * @ingroup DifferenceEngine
 123  */
 124 class DiffOpAdd extends DiffOp {
 125         public $type = 'add';
 126
 127         public function __construct( $lines ) {
 128                 $this->closing = $lines;
 129                 $this->orig = false;
 130         }
 131
 132         /**
 133          * @return DiffOpDelete
 134          */
 135         public function reverse() {
 136                 return new DiffOpDelete( $this->closing );
 137         }
 138 }
 139
 140 /**
 141  * @todo document
 142  * @private
 143  * @ingroup DifferenceEngine
 144  */
 145 class DiffOpChange extends DiffOp {
 146         public $type = 'change';
 147
 148         public function __construct( $orig, $closing ) {
 149                 $this->orig = $orig;
 150                 $this->closing = $closing;
 151         }
 152
 153         /**
 154          * @return DiffOpChange
 155          */
 156         public function reverse() {
 157                 return new DiffOpChange( $this->closing, $this->orig );
 158         }
 159 }
 160
 161 /**
 162  * Class used internally by Diff to actually compute the diffs.
 163  *
 164  * The algorithm used here is mostly lifted from the perl module
 165  * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
 166  *     http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
 167  *
 168  * More ideas are taken from:
 169  *     http://www.ics.uci.edu/~eppstein/161/960229.html
 170  *
 171  * Some ideas are (and a bit of code) are from from analyze.c, from GNU
 172  * diffutils-2.7, which can be found at:
 173  *     ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
 174  *
 175  * closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
 176  * are my own.
 177  *
 178  * Line length limits for robustness added by Tim Starling, 2005-08-31
 179  * Alternative implementation added by Guy Van den Broeck, 2008-07-30
 180  *
 181  * @author Geoffrey T. Dairiki, Tim Starling, Guy Van den Broeck
 182  * @private
 183  * @ingroup DifferenceEngine
 184  */
 185 class DiffEngine {
 186         const MAX_XREF_LENGTH = 10000;
 187
 188         protected $xchanged, $ychanged;
 189
 190         protected $xv = array(), $yv = array();
 191         protected $xind = array(), $yind = array();
 192
 193         protected $seq = array(), $in_seq = array();
 194
 195         protected $lcs = 0;
 196
 197         /**
 198          * @param $from_lines
 199          * @param $to_lines
 200          * @return array
 201          */
 202         public function diff( $from_lines, $to_lines ) {
 203                 wfProfileIn( __METHOD__ );
 204
 205                 // Diff and store locally
 206                 $this->diffLocal( $from_lines, $to_lines );
 207
 208                 // Merge edits when possible
 209                 $this->shiftBoundaries( $from_lines, $this->xchanged, $this->ychanged );
 210                 $this->shiftBoundaries( $to_lines, $this->ychanged, $this->xchanged );
 211
 212                 // Compute the edit operations.
 213                 $n_from = count( $from_lines );
 214                 $n_to = count( $to_lines );
 215
 216                 $edits = array();
 217                 $xi = $yi = 0;
 218                 while ( $xi < $n_from || $yi < $n_to ) {
 219                         assert( '$yi < $n_to || $this->xchanged[$xi]' );
 220                         assert( '$xi < $n_from || $this->ychanged[$yi]' );
 221
 222                         // Skip matching "snake".
 223                         $copy = array();
 224                         while ( $xi < $n_from && $yi < $n_to
 225                                 && !$this->xchanged[$xi] && !$this->ychanged[$yi]
 226                         ) {
 227                                 $copy[] = $from_lines[$xi++];
 228                                 ++$yi;
 229                         }
 230                         if ( $copy ) {
 231                                 $edits[] = new DiffOpCopy( $copy );
 232                         }
 233
 234                         // Find deletes & adds.
 235                         $delete = array();
 236                         while ( $xi < $n_from && $this->xchanged[$xi] ) {
 237                                 $delete[] = $from_lines[$xi++];
 238                         }
 239
 240                         $add = array();
 241                         while ( $yi < $n_to && $this->ychanged[$yi] ) {
 242                                 $add[] = $to_lines[$yi++];
 243                         }
 244
 245                         if ( $delete && $add ) {
 246                                 $edits[] = new DiffOpChange( $delete, $add );
 247                         } elseif ( $delete ) {
 248                                 $edits[] = new DiffOpDelete( $delete );
 249                         } elseif ( $add ) {
 250                                 $edits[] = new DiffOpAdd( $add );
 251                         }
 252                 }
 253                 wfProfileOut( __METHOD__ );
 254
 255                 return $edits;
 256         }
 257
 258         /**
 259          * @param $from_lines
 260          * @param $to_lines
 261          */
 262         private function diffLocal( $from_lines, $to_lines ) {
 263                 global $wgExternalDiffEngine;
 264                 wfProfileIn( __METHOD__ );
 265
 266                 if ( $wgExternalDiffEngine == 'wikidiff3' ) {
 267                         // wikidiff3
 268                         $wikidiff3 = new WikiDiff3();
 269                         $wikidiff3->diff( $from_lines, $to_lines );
 270                         $this->xchanged = $wikidiff3->removed;
 271                         $this->ychanged = $wikidiff3->added;
 272                         unset( $wikidiff3 );
 273                 } else {
 274                         // old diff
 275                         $n_from = count( $from_lines );
 276                         $n_to = count( $to_lines );
 277                         $this->xchanged = $this->ychanged = array();
 278                         $this->xv = $this->yv = array();
 279                         $this->xind = $this->yind = array();
 280                         unset( $this->seq );
 281                         unset( $this->in_seq );
 282                         unset( $this->lcs );
 283
 284                         // Skip leading common lines.
 285                         for ( $skip = 0; $skip < $n_from && $skip < $n_to; $skip++ ) {
 286                                 if ( $from_lines[$skip] !== $to_lines[$skip] ) {
 287                                         break;
 288                                 }
 289                                 $this->xchanged[$skip] = $this->ychanged[$skip] = false;
 290                         }
 291                         // Skip trailing common lines.
 292                         $xi = $n_from;
 293                         $yi = $n_to;
 294                         for ( $endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++ ) {
 295                                 if ( $from_lines[$xi] !== $to_lines[$yi] ) {
 296                                         break;
 297                                 }
 298                                 $this->xchanged[$xi] = $this->ychanged[$yi] = false;
 299                         }
 300
 301                         // Ignore lines which do not exist in both files.
 302                         for ( $xi = $skip; $xi < $n_from - $endskip; $xi++ ) {
 303                                 $xhash[$this->lineHash( $from_lines[$xi] )] = 1;
 304                         }
 305
 306                         for ( $yi = $skip; $yi < $n_to - $endskip; $yi++ ) {
 307                                 $line = $to_lines[$yi];
 308                                 if ( ( $this->ychanged[$yi] = empty( $xhash[$this->lineHash( $line )] ) ) ) {
 309                                         continue;
 310                                 }
 311                                 $yhash[$this->lineHash( $line )] = 1;
 312                                 $this->yv[] = $line;
 313                                 $this->yind[] = $yi;
 314                         }
 315                         for ( $xi = $skip; $xi < $n_from - $endskip; $xi++ ) {
 316                                 $line = $from_lines[$xi];
 317                                 if ( ( $this->xchanged[$xi] = empty( $yhash[$this->lineHash( $line )] ) ) ) {
 318                                         continue;
 319                                 }
 320                                 $this->xv[] = $line;
 321                                 $this->xind[] = $xi;
 322                         }
 323
 324                         // Find the LCS.
 325                         $this->compareSeq( 0, count( $this->xv ), 0, count( $this->yv ) );
 326                 }
 327                 wfProfileOut( __METHOD__ );
 328         }
 329
 330         /**
 331          * Returns the whole line if it's small enough, or the MD5 hash otherwise
 332          * @param $line string
 333          * @return string
 334          */
 335         private function lineHash( $line ) {
 336                 if ( strlen( $line ) > self::MAX_XREF_LENGTH ) {
 337                         return md5( $line );
 338                 } else {
 339                         return $line;
 340                 }
 341         }
 342
 343         /**
 344          * Divide the Largest Common Subsequence (LCS) of the sequences
 345          * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
 346          * sized segments.
 347          *
 348          * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an
 349          * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
 350          * sub sequences.  The first sub-sequence is contained in [X0, X1),
 351          * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on.  Note
 352          * that (X0, Y0) == (XOFF, YOFF) and
 353          * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
 354          *
 355          * This function assumes that the first lines of the specified portions
 356          * of the two files do not match, and likewise that the last lines do not
 357          * match.  The caller must trim matching lines from the beginning and end
 358          * of the portions it is going to specify.
 359          * @param $xoff
 360          * @param $xlim
 361          * @param $yoff
 362          * @param $ylim
 363          * @param $nchunks
 364          * @return array
 365          */
 366         private function diag( $xoff, $xlim, $yoff, $ylim, $nchunks ) {
 367                 $flip = false;
 368
 369                 if ( $xlim - $xoff > $ylim - $yoff ) {
 370                         // Things seems faster (I'm not sure I understand why)
 371                         // when the shortest sequence in X.
 372                         $flip = true;
 373                         list( $xoff, $xlim, $yoff, $ylim ) = array( $yoff, $ylim, $xoff, $xlim );
 374                 }
 375
 376                 if ( $flip ) {
 377                         for ( $i = $ylim - 1; $i >= $yoff; $i-- ) {
 378                                 $ymatches[$this->xv[$i]][] = $i;
 379                         }
 380                 } else {
 381                         for ( $i = $ylim - 1; $i >= $yoff; $i-- ) {
 382                                 $ymatches[$this->yv[$i]][] = $i;
 383                         }
 384                 }
 385
 386                 $this->lcs = 0;
 387                 $this->seq[0] = $yoff - 1;
 388                 $this->in_seq = array();
 389                 $ymids[0] = array();
 390
 391                 $numer = $xlim - $xoff + $nchunks - 1;
 392                 $x = $xoff;
 393                 for ( $chunk = 0; $chunk < $nchunks; $chunk++ ) {
 394                         if ( $chunk > 0 ) {
 395                                 for ( $i = 0; $i <= $this->lcs; $i++ ) {
 396                                         $ymids[$i][$chunk - 1] = $this->seq[$i];
 397                                 }
 398                         }
 399
 400                         $x1 = $xoff + (int)( ( $numer + ( $xlim - $xoff ) * $chunk ) / $nchunks );
 401                         for ( ; $x < $x1; $x++ ) {
 402                                 $line = $flip ? $this->yv[$x] : $this->xv[$x];
 403                                 if ( empty( $ymatches[$line] ) ) {
 404                                         continue;
 405                                 }
 406
 407                                 $k = 0;
 408                                 $matches = $ymatches[$line];
 409                                 reset( $matches );
 410                                 while ( list( , $y ) = each( $matches ) ) {
 411                                         if ( empty( $this->in_seq[$y] ) ) {
 412                                                 $k = $this->lcsPos( $y );
 413                                                 assert( '$k > 0' );
 414                                                 $ymids[$k] = $ymids[$k - 1];
 415                                                 break;
 416                                         }
 417                                 }
 418
 419                                 while ( list( , $y ) = each( $matches ) ) {
 420                                         if ( $y > $this->seq[$k - 1] ) {
 421                                                 assert( '$y < $this->seq[$k]' );
 422                                                 // Optimization: this is a common case:
 423                                                 //      next match is just replacing previous match.
 424                                                 $this->in_seq[$this->seq[$k]] = false;
 425                                                 $this->seq[$k] = $y;
 426                                                 $this->in_seq[$y] = 1;
 427                                         } elseif ( empty( $this->in_seq[$y] ) ) {
 428                                                 $k = $this->lcsPos( $y );
 429                                                 assert( '$k > 0' );
 430                                                 $ymids[$k] = $ymids[$k - 1];
 431                                         }
 432                                 }
 433                         }
 434                 }
 435
 436                 $seps[] = $flip ? array( $yoff, $xoff ) : array( $xoff, $yoff );
 437                 $ymid = $ymids[$this->lcs];
 438                 for ( $n = 0; $n < $nchunks - 1; $n++ ) {
 439                         $x1 = $xoff + (int)( ( $numer + ( $xlim - $xoff ) * $n ) / $nchunks );
 440                         $y1 = $ymid[$n] + 1;
 441                         $seps[] = $flip ? array( $y1, $x1 ) : array( $x1, $y1 );
 442                 }
 443                 $seps[] = $flip ? array( $ylim, $xlim ) : array( $xlim, $ylim );
 444
 445                 return array( $this->lcs, $seps );
 446         }
 447
 448         /**
 449          * @param $ypos
 450          * @return int
 451          */
 452         private function lcsPos( $ypos ) {
 453                 $end = $this->lcs;
 454                 if ( $end == 0 || $ypos > $this->seq[$end] ) {
 455                         $this->seq[++$this->lcs] = $ypos;
 456                         $this->in_seq[$ypos] = 1;
 457
 458                         return $this->lcs;
 459                 }
 460
 461                 $beg = 1;
 462                 while ( $beg < $end ) {
 463                         $mid = (int)( ( $beg + $end ) / 2 );
 464                         if ( $ypos > $this->seq[$mid] ) {
 465                                 $beg = $mid + 1;
 466                         } else {
 467                                 $end = $mid;
 468                         }
 469                 }
 470
 471                 assert( '$ypos != $this->seq[$end]' );
 472
 473                 $this->in_seq[$this->seq[$end]] = false;
 474                 $this->seq[$end] = $ypos;
 475                 $this->in_seq[$ypos] = 1;
 476
 477                 return $end;
 478         }
 479
 480         /**
 481          * Find LCS of two sequences.
 482          *
 483          * The results are recorded in the vectors $this->{x,y}changed[], by
 484          * storing a 1 in the element for each line that is an insertion
 485          * or deletion (ie. is not in the LCS).
 486          *
 487          * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
 488          *
 489          * Note that XLIM, YLIM are exclusive bounds.
 490          * All line numbers are origin-0 and discarded lines are not counted.
 491          * @param $xoff
 492          * @param $xlim
 493          * @param $yoff
 494          * @param $ylim
 495          */
 496         private function compareSeq( $xoff, $xlim, $yoff, $ylim ) {
 497                 // Slide down the bottom initial diagonal.
 498                 while ( $xoff < $xlim && $yoff < $ylim && $this->xv[$xoff] == $this->yv[$yoff] ) {
 499                         ++$xoff;
 500                         ++$yoff;
 501                 }
 502
 503                 // Slide up the top initial diagonal.
 504                 while ( $xlim > $xoff && $ylim > $yoff
 505                         && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]
 506                 ) {
 507                         --$xlim;
 508                         --$ylim;
 509                 }
 510
 511                 if ( $xoff == $xlim || $yoff == $ylim ) {
 512                         $lcs = 0;
 513                 } else {
 514                         // This is ad hoc but seems to work well.
 515                         // $nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
 516                         // $nchunks = max(2,min(8,(int)$nchunks));
 517                         $nchunks = min( 7, $xlim - $xoff, $ylim - $yoff ) + 1;
 518                         list( $lcs, $seps ) = $this->diag( $xoff, $xlim, $yoff, $ylim, $nchunks );
 519                 }
 520
 521                 if ( $lcs == 0 ) {
 522                         // X and Y sequences have no common subsequence:
 523                         // mark all changed.
 524                         while ( $yoff < $ylim ) {
 525                                 $this->ychanged[$this->yind[$yoff++]] = 1;
 526                         }
 527                         while ( $xoff < $xlim ) {
 528                                 $this->xchanged[$this->xind[$xoff++]] = 1;
 529                         }
 530                 } else {
 531                         // Use the partitions to split this problem into subproblems.
 532                         reset( $seps );
 533                         $pt1 = $seps[0];
 534                         while ( $pt2 = next( $seps ) ) {
 535                                 $this->compareSeq( $pt1[0], $pt2[0], $pt1[1], $pt2[1] );
 536                                 $pt1 = $pt2;
 537                         }
 538                 }
 539         }
 540
 541         /**
 542          * Adjust inserts/deletes of identical lines to join changes
 543          * as much as possible.
 544          *
 545          * We do something when a run of changed lines include a
 546          * line at one end and has an excluded, identical line at the other.
 547          * We are free to choose which identical line is included.
 548          * `compareseq' usually chooses the one at the beginning,
 549          * but usually it is cleaner to consider the following identical line
 550          * to be the "change".
 551          *
 552          * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
 553          */
 554         private function shiftBoundaries( $lines, &$changed, $other_changed ) {
 555                 wfProfileIn( __METHOD__ );
 556                 $i = 0;
 557                 $j = 0;
 558
 559                 assert( 'count($lines) == count($changed)' );
 560                 $len = count( $lines );
 561                 $other_len = count( $other_changed );
 562
 563                 while ( 1 ) {
 564                         /*
 565                          * Scan forwards to find beginning of another run of changes.
 566                          * Also keep track of the corresponding point in the other file.
 567                          *
 568                          * Throughout this code, $i and $j are adjusted together so that
 569                          * the first $i elements of $changed and the first $j elements
 570                          * of $other_changed both contain the same number of zeros
 571                          * (unchanged lines).
 572                          * Furthermore, $j is always kept so that $j == $other_len or
 573                          * $other_changed[$j] == false.
 574                          */
 575                         while ( $j < $other_len && $other_changed[$j] ) {
 576                                 $j++;
 577                         }
 578
 579                         while ( $i < $len && !$changed[$i] ) {
 580                                 assert( '$j < $other_len && ! $other_changed[$j]' );
 581                                 $i++;
 582                                 $j++;
 583                                 while ( $j < $other_len && $other_changed[$j] ) {
 584                                         $j++;
 585                                 }
 586                         }
 587
 588                         if ( $i == $len ) {
 589                                 break;
 590                         }
 591
 592                         $start = $i;
 593
 594                         // Find the end of this run of changes.
 595                         while ( ++$i < $len && $changed[$i] ) {
 596                                 continue;
 597                         }
 598
 599                         do {
 600                                 /*
 601                                  * Record the length of this run of changes, so that
 602                                  * we can later determine whether the run has grown.
 603                                  */
 604                                 $runlength = $i - $start;
 605
 606                                 /*
 607                                  * Move the changed region back, so long as the
 608                                  * previous unchanged line matches the last changed one.
 609                                  * This merges with previous changed regions.
 610                                  */
 611                                 while ( $start > 0 && $lines[$start - 1] == $lines[$i - 1] ) {
 612                                         $changed[--$start] = 1;
 613                                         $changed[--$i] = false;
 614                                         while ( $start > 0 && $changed[$start - 1] ) {
 615                                                 $start--;
 616                                         }
 617                                         assert( '$j > 0' );
 618                                         while ( $other_changed[--$j] ) {
 619                                                 continue;
 620                                         }
 621                                         assert( '$j >= 0 && !$other_changed[$j]' );
 622                                 }
 623
 624                                 /*
 625                                  * Set CORRESPONDING to the end of the changed run, at the last
 626                                  * point where it corresponds to a changed run in the other file.
 627                                  * CORRESPONDING == LEN means no such point has been found.
 628                                  */
 629                                 $corresponding = $j < $other_len ? $i : $len;
 630
 631                                 /*
 632                                  * Move the changed region forward, so long as the
 633                                  * first changed line matches the following unchanged one.
 634                                  * This merges with following changed regions.
 635                                  * Do this second, so that if there are no merges,
 636                                  * the changed region is moved forward as far as possible.
 637                                  */
 638                                 while ( $i < $len && $lines[$start] == $lines[$i] ) {
 639                                         $changed[$start++] = false;
 640                                         $changed[$i++] = 1;
 641                                         while ( $i < $len && $changed[$i] ) {
 642                                                 $i++;
 643                                         }
 644
 645                                         assert( '$j < $other_len && ! $other_changed[$j]' );
 646                                         $j++;
 647                                         if ( $j < $other_len && $other_changed[$j] ) {
 648                                                 $corresponding = $i;
 649                                                 while ( $j < $other_len && $other_changed[$j] ) {
 650                                                         $j++;
 651                                                 }
 652                                         }
 653                                 }
 654                         } while ( $runlength != $i - $start );
 655
 656                         /*
 657                          * If possible, move the fully-merged run of changes
 658                          * back to a corresponding run in the other file.
 659                          */
 660                         while ( $corresponding < $i ) {
 661                                 $changed[--$start] = 1;
 662                                 $changed[--$i] = 0;
 663                                 assert( '$j > 0' );
 664                                 while ( $other_changed[--$j] ) {
 665                                         continue;
 666                                 }
 667                                 assert( '$j >= 0 && !$other_changed[$j]' );
 668                         }
 669                 }
 670                 wfProfileOut( __METHOD__ );
 671         }
 672 }
 673
 674 /**
 675  * Class representing a 'diff' between two sequences of strings.
 676  * @todo document
 677  * @private
 678  * @ingroup DifferenceEngine
 679  */
 680 class Diff {
 681
 682         /**
 683          * @var DiffOp[]
 684          */
 685         public $edits;
 686
 687         /**
 688          * Constructor.
 689          * Computes diff between sequences of strings.
 690          *
 691          * @param $from_lines array An array of strings.
 692          *   Typically these are lines from a file.
 693          * @param $to_lines array An array of strings.
 694          */
 695         public function __construct( $from_lines, $to_lines ) {
 696                 $eng = new DiffEngine;
 697                 $this->edits = $eng->diff( $from_lines, $to_lines );
 698         }
 699
 700         /**
 701          * @return array|DiffOp[]
 702          */
 703         public function getEdits() {
 704                 return $this->edits;
 705         }
 706
 707         /**
 708          * Compute reversed Diff.
 709          *
 710          * SYNOPSIS:
 711          *
 712          *    $diff = new Diff($lines1, $lines2);
 713          *    $rev = $diff->reverse();
 714          * @return Object A Diff object representing the inverse of the
 715          *   original diff.
 716          */
 717         public function reverse() {
 718                 $rev = $this;
 719                 $rev->edits = array();
 720                 /** @var DiffOp $edit */
 721                 foreach ( $this->edits as $edit ) {
 722                         $rev->edits[] = $edit->reverse();
 723                 }
 724
 725                 return $rev;
 726         }
 727
 728         /**
 729          * Check for empty diff.
 730          *
 731          * @return bool True if two sequences were identical.
 732          */
 733         public function isEmpty() {
 734                 foreach ( $this->edits as $edit ) {
 735                         if ( $edit->type != 'copy' ) {
 736                                 return false;
 737                         }
 738                 }
 739
 740                 return true;
 741         }
 742
 743         /**
 744          * Compute the length of the Longest Common Subsequence (LCS).
 745          *
 746          * This is mostly for diagnostic purposed.
 747          *
 748          * @return int The length of the LCS.
 749          */
 750         public function lcs() {
 751                 $lcs = 0;
 752                 foreach ( $this->edits as $edit ) {
 753                         if ( $edit->type == 'copy' ) {
 754                                 $lcs += count( $edit->orig );
 755                         }
 756                 }
 757
 758                 return $lcs;
 759         }
 760
 761         /**
 762          * Get the original set of lines.
 763          *
 764          * This reconstructs the $from_lines parameter passed to the
 765          * constructor.
 766          *
 767          * @return array The original sequence of strings.
 768          */
 769         public function orig() {
 770                 $lines = array();
 771
 772                 foreach ( $this->edits as $edit ) {
 773                         if ( $edit->orig ) {
 774                                 array_splice( $lines, count( $lines ), 0, $edit->orig );
 775                         }
 776                 }
 777
 778                 return $lines;
 779         }
 780
 781         /**
 782          * Get the closing set of lines.
 783          *
 784          * This reconstructs the $to_lines parameter passed to the
 785          * constructor.
 786          *
 787          * @return array The sequence of strings.
 788          */
 789         public function closing() {
 790                 $lines = array();
 791
 792                 foreach ( $this->edits as $edit ) {
 793                         if ( $edit->closing ) {
 794                                 array_splice( $lines, count( $lines ), 0, $edit->closing );
 795                         }
 796                 }
 797
 798                 return $lines;
 799         }
 800 }
 801
 802 /**
 803  * @todo document, bad name.
 804  * @private
 805  * @ingroup DifferenceEngine
 806  */
 807 class MappedDiff extends Diff {
 808         /**
 809          * Constructor.
 810          *
 811          * Computes diff between sequences of strings.
 812          *
 813          * This can be used to compute things like
 814          * case-insensitve diffs, or diffs which ignore
 815          * changes in white-space.
 816          *
 817          * @param $from_lines array An array of strings.
 818          *   Typically these are lines from a file.
 819          *
 820          * @param $to_lines array An array of strings.
 821          *
 822          * @param $mapped_from_lines array This array should
 823          *   have the same size number of elements as $from_lines.
 824          *   The elements in $mapped_from_lines and
 825          *   $mapped_to_lines are what is actually compared
 826          *   when computing the diff.
 827          *
 828          * @param $mapped_to_lines array This array should
 829          *   have the same number of elements as $to_lines.
 830          */
 831         public function __construct( $from_lines, $to_lines,
 832                 $mapped_from_lines, $mapped_to_lines ) {
 833                 wfProfileIn( __METHOD__ );
 834
 835                 assert( 'count( $from_lines ) == count( $mapped_from_lines )' );
 836                 assert( 'count( $to_lines ) == count( $mapped_to_lines )' );
 837
 838                 parent::__construct( $mapped_from_lines, $mapped_to_lines );
 839
 840                 $xi = $yi = 0;
 841                 $editCount = count( $this->edits );
 842                 for ( $i = 0; $i < $editCount; $i++ ) {
 843                         $orig = &$this->edits[$i]->orig;
 844                         if ( is_array( $orig ) ) {
 845                                 $orig = array_slice( $from_lines, $xi, count( $orig ) );
 846                                 $xi += count( $orig );
 847                         }
 848
 849                         $closing = &$this->edits[$i]->closing;
 850                         if ( is_array( $closing ) ) {
 851                                 $closing = array_slice( $to_lines, $yi, count( $closing ) );
 852                                 $yi += count( $closing );
 853                         }
 854                 }
 855                 wfProfileOut( __METHOD__ );
 856         }
 857 }
 858
 859 /**
 860  * Additions by Axel Boldt follow, partly taken from diff.php, phpwiki-1.3.3
 861  */
 862
 863 /**
 864  * @todo document
 865  * @private
 866  * @ingroup DifferenceEngine
 867  */
 868 class HWLDFWordAccumulator {
 869         public $insClass = ' class="diffchange diffchange-inline"';
 870         public $delClass = ' class="diffchange diffchange-inline"';
 871
 872         private $lines = array();
 873         private $line = '';
 874         private $group = '';
 875         private $tag = '';
 876
 877         /**
 878          * @param $new_tag
 879          */
 880         private function flushGroup( $new_tag ) {
 881                 if ( $this->group !== '' ) {
 882                         if ( $this->tag == 'ins' ) {
 883                                 $this->line .= "<ins{$this->insClass}>" .
 884                                         htmlspecialchars( $this->group ) . '</ins>';
 885                         } elseif ( $this->tag == 'del' ) {
 886                                 $this->line .= "<del{$this->delClass}>" .
 887                                         htmlspecialchars( $this->group ) . '</del>';
 888                         } else {
 889                                 $this->line .= htmlspecialchars( $this->group );
 890                         }
 891                 }
 892                 $this->group = '';
 893                 $this->tag = $new_tag;
 894         }
 895
 896         /**
 897          * @param $new_tag
 898          */
 899         private function flushLine( $new_tag ) {
 900                 $this->flushGroup( $new_tag );
 901                 if ( $this->line != '' ) {
 902                         array_push( $this->lines, $this->line );
 903                 } else {
 904                         # make empty lines visible by inserting an NBSP
 905                         array_push( $this->lines, '&#160;' );
 906                 }
 907                 $this->line = '';
 908         }
 909
 910         /**
 911          * @param $words
 912          * @param $tag string
 913          */
 914         public function addWords( $words, $tag = '' ) {
 915                 if ( $tag != $this->tag ) {
 916                         $this->flushGroup( $tag );
 917                 }
 918
 919                 foreach ( $words as $word ) {
 920                         // new-line should only come as first char of word.
 921                         if ( $word == '' ) {
 922                                 continue;
 923                         }
 924                         if ( $word[0] == "\n" ) {
 925                                 $this->flushLine( $tag );
 926                                 $word = substr( $word, 1 );
 927                         }
 928                         assert( '!strstr( $word, "\n" )' );
 929                         $this->group .= $word;
 930                 }
 931         }
 932
 933         /**
 934          * @return array
 935          */
 936         public function getLines() {
 937                 $this->flushLine( '~done' );
 938
 939                 return $this->lines;
 940         }
 941 }
 942
 943 /**
 944  * @todo document
 945  * @private
 946  * @ingroup DifferenceEngine
 947  */
 948 class WordLevelDiff extends MappedDiff {
 949         const MAX_LINE_LENGTH = 10000;
 950
 951         /**
 952          * @param $orig_lines
 953          * @param $closing_lines
 954          */
 955         public function __construct( $orig_lines, $closing_lines ) {
 956                 wfProfileIn( __METHOD__ );
 957
 958                 list( $orig_words, $orig_stripped ) = $this->split( $orig_lines );
 959                 list( $closing_words, $closing_stripped ) = $this->split( $closing_lines );
 960
 961                 parent::__construct( $orig_words, $closing_words,
 962                         $orig_stripped, $closing_stripped );
 963                 wfProfileOut( __METHOD__ );
 964         }
 965
 966         /**
 967          * @param $lines
 968          * @return array
 969          */
 970         private function split( $lines ) {
 971                 wfProfileIn( __METHOD__ );
 972
 973                 $words = array();
 974                 $stripped = array();
 975                 $first = true;
 976                 foreach ( $lines as $line ) {
 977                         # If the line is too long, just pretend the entire line is one big word
 978                         # This prevents resource exhaustion problems
 979                         if ( $first ) {
 980                                 $first = false;
 981                         } else {
 982                                 $words[] = "\n";
 983                                 $stripped[] = "\n";
 984                         }
 985                         if ( strlen( $line ) > self::MAX_LINE_LENGTH ) {
 986                                 $words[] = $line;
 987                                 $stripped[] = $line;
 988                         } else {
 989                                 $m = array();
 990                                 if ( preg_match_all( '/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xs',
 991                                         $line, $m )
 992                                 ) {
 993                                         foreach ( $m[0] as $word ) {
 994                                                 $words[] = $word;
 995                                         }
 996                                         foreach ( $m[1] as $stripped_word ) {
 997                                                 $stripped[] = $stripped_word;
 998                                         }
 999                                 }
1000                         }
1001                 }
1002                 wfProfileOut( __METHOD__ );
1003
1004                 return array( $words, $stripped );
1005         }
1006
1007         /**
1008          * @return array
1009          */
1010         public function orig() {
1011                 wfProfileIn( __METHOD__ );
1012                 $orig = new HWLDFWordAccumulator;
1013
1014                 foreach ( $this->edits as $edit ) {
1015                         if ( $edit->type == 'copy' ) {
1016                                 $orig->addWords( $edit->orig );
1017                         } elseif ( $edit->orig ) {
1018                                 $orig->addWords( $edit->orig, 'del' );
1019                         }
1020                 }
1021                 $lines = $orig->getLines();
1022                 wfProfileOut( __METHOD__ );
1023
1024                 return $lines;
1025         }
1026
1027         /**
1028          * @return array
1029          */
1030         public function closing() {
1031                 wfProfileIn( __METHOD__ );
1032                 $closing = new HWLDFWordAccumulator;
1033
1034                 foreach ( $this->edits as $edit ) {
1035                         if ( $edit->type == 'copy' ) {
1036                                 $closing->addWords( $edit->closing );
1037                         } elseif ( $edit->closing ) {
1038                                 $closing->addWords( $edit->closing, 'ins' );
1039                         }
1040                 }
1041                 $lines = $closing->getLines();
1042                 wfProfileOut( __METHOD__ );
1043
1044                 return $lines;
1045         }
1046 }