Search moodle.org's
Developer Documentation

See Release Notes

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