[Summary view] [Print] [Text view]

   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 <[email protected]>
   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      function _WikiDiffOp_Copy ($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      function _WikiDiffOp_Delete ($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      function _WikiDiffOp_Add ($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      function _WikiDiffOp_Change ($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          while (list ($junk, $y) = each($matches))
 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          while (list ($junk, $y) = each($matches)) {
 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      function WikiDiff($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       * Compute reversed WikiDiff.
 511       *
 512       * SYNOPSIS:
 513       *
 514       *    $diff = new WikiDiff($lines1, $lines2);
 515       *    $rev = $diff->reverse();
 516       * @return object A WikiDiff object representing the inverse of the
 517       *                  original diff.
 518       */
 519      function reverse () {
 520      $rev = $this;
 521          $rev->edits = array();
 522          foreach ($this->edits as $edit) {
 523              $rev->edits[] = $edit->reverse();
 524          }
 525      return $rev;
 526      }
 527  
 528      /**
 529       * Check for empty diff.
 530       *
 531       * @return bool True iff two sequences were identical.
 532       */
 533      function isEmpty () {
 534          foreach ($this->edits as $edit) {
 535              if ($edit->type != 'copy')
 536                  return false;
 537          }
 538          return true;
 539      }
 540  
 541      /**
 542       * Compute the length of the Longest Common Subsequence (LCS).
 543       *
 544       * This is mostly for diagnostic purposed.
 545       *
 546       * @return int The length of the LCS.
 547       */
 548      function lcs () {
 549      $lcs = 0;
 550          foreach ($this->edits as $edit) {
 551              if ($edit->type == 'copy')
 552                  $lcs += sizeof($edit->orig);
 553          }
 554      return $lcs;
 555      }
 556  
 557      /**
 558       * Get the original set of lines.
 559       *
 560       * This reconstructs the $from_lines parameter passed to the
 561       * constructor.
 562       *
 563       * @return array The original sequence of strings.
 564       */
 565      function orig() {
 566          $lines = array();
 567  
 568          foreach ($this->edits as $edit) {
 569              if ($edit->orig)
 570                  array_splice($lines, sizeof($lines), 0, $edit->orig);
 571          }
 572          return $lines;
 573      }
 574  
 575      /**
 576       * Get the closing set of lines.
 577       *
 578       * This reconstructs the $to_lines parameter passed to the
 579       * constructor.
 580       *
 581       * @return array The sequence of strings.
 582       */
 583      function closing() {
 584          $lines = array();
 585  
 586          foreach ($this->edits as $edit) {
 587              if ($edit->closing)
 588                  array_splice($lines, sizeof($lines), 0, $edit->closing);
 589          }
 590          return $lines;
 591      }
 592  
 593      /**
 594       * Check a WikiDiff for validity.
 595       *
 596       * This is here only for debugging purposes.
 597       */
 598      function _check ($from_lines, $to_lines) {
 599          if (serialize($from_lines) != serialize($this->orig()))
 600              trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
 601          if (serialize($to_lines) != serialize($this->closing()))
 602              trigger_error("Reconstructed closing doesn't match", E_USER_ERROR);
 603  
 604          $rev = $this->reverse();
 605          if (serialize($to_lines) != serialize($rev->orig()))
 606              trigger_error("Reversed original doesn't match", E_USER_ERROR);
 607          if (serialize($from_lines) != serialize($rev->closing()))
 608              trigger_error("Reversed closing doesn't match", E_USER_ERROR);
 609  
 610  
 611          $prevtype = 'none';
 612          foreach ($this->edits as $edit) {
 613              if ( $prevtype == $edit->type )
 614                  trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
 615              $prevtype = $edit->type;
 616          }
 617  
 618          $lcs = $this->lcs();
 619          trigger_error("WikiDiff okay: LCS = $lcs", E_USER_NOTICE);
 620      }
 621  }
 622  
 623  /**
 624   * FIXME: bad name.
 625   */
 626   
 627  class MappedWikiDiff
 628  extends WikiDiff
 629  {
 630      /**
 631       * Constructor.
 632       *
 633       * Computes diff between sequences of strings.
 634       *
 635       * This can be used to compute things like
 636       * case-insensitve diffs, or diffs which ignore
 637       * changes in white-space.
 638       *
 639       * @param $from_lines array An array of strings.
 640       *    (Typically these are lines from a file.)
 641       *
 642       * @param $to_lines array An array of strings.
 643       *
 644       * @param $mapped_from_lines array This array should
 645       *    have the same size number of elements as $from_lines.
 646       *    The elements in $mapped_from_lines and
 647       *    $mapped_to_lines are what is actually compared
 648       *    when computing the diff.
 649       *
 650       * @param $mapped_to_lines array This array should
 651       *    have the same number of elements as $to_lines.
 652       */
 653      function MappedWikiDiff($from_lines, $to_lines,
 654                          $mapped_from_lines, $mapped_to_lines) {
 655  
 656          assert(sizeof($from_lines) == sizeof($mapped_from_lines));
 657          assert(sizeof($to_lines) == sizeof($mapped_to_lines));
 658  
 659          $this->WikiDiff($mapped_from_lines, $mapped_to_lines);
 660  
 661          $xi = $yi = 0;
 662          for ($i = 0; $i < sizeof($this->edits); $i++) {
 663              $orig = &$this->edits[$i]->orig;
 664              if (is_array($orig)) {
 665                  $orig = array_slice($from_lines, $xi, sizeof($orig));
 666                  $xi += sizeof($orig);
 667              }
 668  
 669              $closing = &$this->edits[$i]->closing;
 670              if (is_array($closing)) {
 671                  $closing = array_slice($to_lines, $yi, sizeof($closing));
 672                  $yi += sizeof($closing);
 673              }
 674          }
 675      }
 676  }
 677  
 678  /**
 679   * A class to format WikiDiffs
 680   *
 681   * This class formats the diff in classic diff format.
 682   * It is intended that this class be customized via inheritance,
 683   * to obtain fancier outputs.
 684   */
 685  class WikiDiffFormatter
 686  {
 687      /**
 688       * Number of leading context "lines" to preserve.
 689       *
 690       * This should be left at zero for this class, but subclasses
 691       * may want to set this to other values.
 692       */
 693      var $leading_context_lines = 0;
 694  
 695      /**
 696       * Number of trailing context "lines" to preserve.
 697       *
 698       * This should be left at zero for this class, but subclasses
 699       * may want to set this to other values.
 700       */
 701      var $trailing_context_lines = 0;
 702  
 703      /**
 704       * Format a diff.
 705       *
 706       * @param $diff object A WikiDiff object.
 707       * @return string The formatted output.
 708       */
 709      function format($diff) {
 710  
 711          $xi = $yi = 1;
 712          $block = false;
 713          $context = array();
 714  
 715          $nlead = $this->leading_context_lines;
 716          $ntrail = $this->trailing_context_lines;
 717  
 718          $this->_start_diff();
 719  
 720          foreach ($diff->edits as $edit) {
 721              if ($edit->type == 'copy') {
 722                  if (is_array($block)) {
 723                      if (sizeof($edit->orig) <= $nlead + $ntrail) {
 724                          $block[] = $edit;
 725                      }
 726                      else{
 727                          if ($ntrail) {
 728                              $context = array_slice($edit->orig, 0, $ntrail);
 729                              $block[] = new _WikiWikiDiffOp_Copy($context);
 730                          }
 731                          $this->_block($x0, $ntrail + $xi - $x0,
 732                                        $y0, $ntrail + $yi - $y0,
 733                                        $block);
 734                          $block = false;
 735                      }
 736                  }
 737                  $context = $edit->orig;
 738              }
 739              else {
 740                  if (! is_array($block)) {
 741                      $context = array_slice($context, sizeof($context) - $nlead);
 742                      $x0 = $xi - sizeof($context);
 743                      $y0 = $yi - sizeof($context);
 744                      $block = array();
 745                      if ($context)
 746                          $block[] = new _WikiWikiDiffOp_Copy($context);
 747                  }
 748                  $block[] = $edit;
 749              }
 750  
 751              if ($edit->orig)
 752                  $xi += sizeof($edit->orig);
 753              if ($edit->closing)
 754                  $yi += sizeof($edit->closing);
 755          }
 756  
 757          if (is_array($block))
 758              $this->_block($x0, $xi - $x0,
 759                            $y0, $yi - $y0,
 760                            $block);
 761  
 762          return $this->_end_diff();
 763      }
 764  
 765      function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) {
 766          $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen));
 767          foreach ($edits as $edit) {
 768              if ($edit->type == 'copy')
 769                  $this->_context($edit->orig);
 770              elseif ($edit->type == 'add')
 771                  $this->_added($edit->closing);
 772              elseif ($edit->type == 'delete')
 773                  $this->_deleted($edit->orig);
 774              elseif ($edit->type == 'change')
 775                  $this->_changed($edit->orig, $edit->closing);
 776              else
 777                  trigger_error("Unknown edit type", E_USER_ERROR);
 778          }
 779          $this->_end_block();
 780      }
 781  
 782      function _start_diff() {
 783          ob_start();
 784      }
 785  
 786      function _end_diff() {
 787          $val = ob_get_contents();
 788          ob_end_clean();
 789          return $val;
 790      }
 791  
 792      function _block_header($xbeg, $xlen, $ybeg, $ylen) {
 793          if ($xlen > 1)
 794              $xbeg .= "," . ($xbeg + $xlen - 1);
 795          if ($ylen > 1)
 796              $ybeg .= "," . ($ybeg + $ylen - 1);
 797  
 798          return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg;
 799      }
 800  
 801      function _start_block($header) {
 802          echo $header;
 803      }
 804  
 805      function _end_block() {
 806      }
 807  
 808      function _lines($lines, $prefix = ' ') {
 809          foreach ($lines as $line)
 810              echo "$prefix $line\n";
 811      }
 812  
 813      function _context($lines) {
 814          $this->_lines($lines);
 815      }
 816  
 817      function _added($lines) {
 818          $this->_lines($lines, ">");
 819      }
 820      function _deleted($lines) {
 821          $this->_lines($lines, "<");
 822      }
 823  
 824      function _changed($orig, $closing) {
 825          $this->_deleted($orig);
 826          echo "---\n";
 827          $this->_added($closing);
 828      }
 829  }
 830  
 831  
 832  /**
 833   *    Additions by Axel Boldt follow, partly taken from diff.php, phpwiki-1.3.3
 834   *
 835   */
 836  
 837  define('NBSP', '&#160;');            // iso-8859-x non-breaking space.
 838  
 839  class _WikiHWLDF_WordAccumulator {
 840      function _WikiHWLDF_WordAccumulator () {
 841          $this->_lines = array();
 842          $this->_line = '';
 843          $this->_group = '';
 844          $this->_tag = '';
 845      }
 846  
 847      function _flushGroup ($new_tag) {
 848          if ($this->_group !== '') {
 849        if ($this->_tag == 'mark')
 850              $this->_line .= '<span class="diffchange">'.$this->_group.'</span>';
 851        else
 852          $this->_line .= $this->_group;
 853      }
 854          $this->_group = '';
 855          $this->_tag = $new_tag;
 856      }
 857  
 858      function _flushLine ($new_tag) {
 859          $this->_flushGroup($new_tag);
 860          if ($this->_line != '')
 861              $this->_lines[] = $this->_line;
 862          $this->_line = '';
 863      }
 864  
 865      function addWords ($words, $tag = '') {
 866          if ($tag != $this->_tag)
 867              $this->_flushGroup($tag);
 868  
 869          foreach ($words as $word) {
 870              // new-line should only come as first char of word.
 871              if ($word == '')
 872                  continue;
 873              if ($word[0] == "\n") {
 874                  $this->_group .= NBSP;
 875                  $this->_flushLine($tag);
 876                  $word = substr($word, 1);
 877              }
 878              assert(!strstr($word, "\n"));
 879              $this->_group .= $word;
 880          }
 881      }
 882  
 883      function getLines() {
 884          $this->_flushLine('~done');
 885          return $this->_lines;
 886      }
 887  }
 888  
 889  class WordLevelWikiDiff extends MappedWikiDiff
 890  {
 891      function WordLevelWikiDiff ($orig_lines, $closing_lines) {
 892          list ($orig_words, $orig_stripped) = $this->_split($orig_lines);
 893          list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
 894  
 895  
 896          $this->MappedWikiDiff($orig_words, $closing_words,
 897                            $orig_stripped, $closing_stripped);
 898      }
 899  
 900      function _split($lines) {
 901          // FIXME: fix POSIX char class.
 902  #         if (!preg_match_all('/ ( [^\S\n]+ | [[:alnum:]]+ | . ) (?: (?!< \n) [^\S\n])? /xs',
 903          if (!preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xs',
 904                              implode("\n", $lines),
 905                              $m)) {
 906              return array(array(''), array(''));
 907          }
 908          return array($m[0], $m[1]);
 909      }
 910  
 911      function orig () {
 912          $orig = new _WikiHWLDF_WordAccumulator;
 913  
 914          foreach ($this->edits as $edit) {
 915              if ($edit->type == 'copy')
 916                  $orig->addWords($edit->orig);
 917              elseif ($edit->orig)
 918                  $orig->addWords($edit->orig, 'mark');
 919          }
 920          return $orig->getLines();
 921      }
 922  
 923      function closing () {
 924          $closing = new _WikiHWLDF_WordAccumulator;
 925  
 926          foreach ($this->edits as $edit) {
 927              if ($edit->type == 'copy')
 928                  $closing->addWords($edit->closing);
 929              elseif ($edit->closing)
 930                  $closing->addWords($edit->closing, 'mark');
 931          }
 932          return $closing->getLines();
 933      }
 934  }
 935  
 936  /**
 937   * @TODO: Doc this class
 938   */
 939  class TableWikiDiffFormatter extends WikiDiffFormatter
 940  {
 941      var $htmltable = array();
 942      
 943      function TableWikiDiffFormatter() {
 944          $this->leading_context_lines = 2;
 945          $this->trailing_context_lines = 2;
 946      }
 947      
 948      function _block_header( $xbeg, $xlen, $ybeg, $ylen) {
 949        
 950      }
 951      
 952      function _start_block ($header) {
 953  
 954      }
 955      
 956      function _end_block() {
 957  
 958      }
 959      
 960      function _lines($lines, $prefix=' ', $color="white") {
 961          
 962      }
 963      
 964      function _added($lines) {
 965          global $htmltable;
 966          foreach ($lines as $line) {
 967              $htmltable[] = array('','+','<div class="wiki_diffadd">'.$line.'</div>');
 968          }
 969      }
 970  
 971      function _deleted($lines) {
 972          global $htmltable;
 973          foreach ($lines as $line) {
 974              $htmltable[] = array('<div class="wiki_diffdel">'.$line.'</div>','-','');
 975          }
 976      }
 977      
 978      function _context($lines) {
 979          global $htmltable;
 980          foreach ($lines as $line) {
 981              $htmltable[] = array($line,'',$line);
 982          }
 983      }
 984      
 985      function _changed( $orig, $closing ) {
 986          global $htmltable;
 987          $diff = new WordLevelWikiDiff( $orig, $closing );
 988          $del = $diff->orig();
 989          $add = $diff->closing();
 990  
 991          while ( $line = array_shift( $del ) ) {
 992              $aline = array_shift( $add );
 993              $htmltable[] = array('<div class="wiki_diffdel">'.$line.'</div>','-','<div class="wiki_diffadd">'.$aline.'</div>');
 994          }
 995          $this->_added( $add ); # If any leftovers
 996      }
 997      
 998      function get_result() {
 999          global $htmltable;
1000          return $htmltable;
1001      }
1002  
1003  }
1004  
1005  
1006  /**
1007   *    Wikipedia Table style diff formatter.
1008   *
1009   */
1010  class TableWikiDiffFormatterOld extends WikiDiffFormatter
1011  {
1012      function TableWikiDiffFormatter() {
1013          $this->leading_context_lines = 2;
1014          $this->trailing_context_lines = 2;
1015      }
1016  
1017      function _block_header( $xbeg, $xlen, $ybeg, $ylen ) {
1018          $l1 = wfMsg( "lineno", $xbeg );
1019          $l2 = wfMsg( "lineno", $ybeg );
1020  
1021          $r = '<tr><td colspan="2" align="left"><strong>'.$l1."</strong></td>\n" .
1022            '<td colspan="2" align="left"><strong>'.$l2."</strong></td></tr>\n";
1023          return $r;
1024      }
1025  
1026      function _start_block( $header ) {
1027          global $wgOut;
1028          $wgOut->addHTML( $header );
1029      }
1030  
1031      function _end_block() {
1032      }
1033  
1034      function _lines( $lines, $prefix=' ', $color="white" ) {
1035      }
1036  
1037      function addedLine( $line ) {
1038          return '<td>+</td><td class="diff-addedline">' .
1039            $line.'</td>';
1040      }
1041  
1042      function deletedLine( $line ) {
1043          return '<td>-</td><td class="diff-deletedline">' .
1044            $line.'</td>';
1045      }
1046  
1047      function emptyLine() {
1048          return '<td colspan="2">&nbsp;</td>';
1049      }
1050  
1051      function contextLine( $line ) {
1052          return '<td> </td><td class="diff-context">'.$line.'</td>';
1053      }
1054  
1055      function _added($lines) {
1056          global $wgOut;
1057          foreach ($lines as $line) {
1058              $wgOut->addHTML( '<tr>' . $this->emptyLine() .
1059                $this->addedLine( $line ) . "</tr>\n" );
1060          }
1061      }
1062  
1063      function _deleted($lines) {
1064          global $wgOut;
1065          foreach ($lines as $line) {
1066              $wgOut->addHTML( '<tr>' . $this->deletedLine( $line ) .
1067                $this->emptyLine() . "</tr>\n" );
1068          }
1069      }
1070  
1071      function _context( $lines ) {
1072          global $wgOut;
1073          foreach ($lines as $line) {
1074              $wgOut->addHTML( '<tr>' . $this->contextLine( $line ) .
1075                $this->contextLine( $line ) . "</tr>\n" );
1076          }
1077      }
1078  
1079      function _changed( $orig, $closing ) {
1080          global $wgOut;
1081          $diff = new WordLevelWikiDiff( $orig, $closing );
1082          $del = $diff->orig();
1083          $add = $diff->closing();
1084  
1085          while ( $line = array_shift( $del ) ) {
1086              $aline = array_shift( $add );
1087              $wgOut->addHTML( '<tr>' . $this->deletedLine( $line ) .
1088                $this->addedLine( $aline ) . "</tr>\n" );
1089          }
1090          $this->_added( $add ); # If any leftovers
1091      }
1092  }
1093