[ Index ]

PHP Cross Reference of DokuWiki

title

Body

[close]

/inc/ -> DifferenceEngine.php (source)

   1  <?php
   2  /**
   3   * A PHP diff engine for phpwiki. (Taken from phpwiki-1.3.3)
   4   *
   5   * Additions by Axel Boldt for MediaWiki
   6   *
   7   * @copyright (C) 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
   8   * @license  You may copy this code freely under the conditions of the GPL.
   9   */
  10  define('USE_ASSERTS', function_exists('assert'));
  11  
  12  class _DiffOp {
  13      var $type;
  14      var $orig;
  15      var $closing;
  16  
  17      /**
  18       * @return _DiffOp
  19       */
  20      function reverse() {
  21          trigger_error("pure virtual", E_USER_ERROR);
  22      }
  23  
  24      function norig() {
  25          return $this->orig ? count($this->orig) : 0;
  26      }
  27  
  28      function nclosing() {
  29          return $this->closing ? count($this->closing) : 0;
  30      }
  31  }
  32  
  33  class _DiffOp_Copy extends _DiffOp {
  34      var $type = 'copy';
  35  
  36      function __construct($orig, $closing = false) {
  37          if (!is_array($closing))
  38              $closing = $orig;
  39          $this->orig = $orig;
  40          $this->closing = $closing;
  41      }
  42  
  43      function reverse() {
  44          return new _DiffOp_Copy($this->closing, $this->orig);
  45      }
  46  }
  47  
  48  class _DiffOp_Delete extends _DiffOp {
  49      var $type = 'delete';
  50  
  51      function __construct($lines) {
  52          $this->orig = $lines;
  53          $this->closing = false;
  54      }
  55  
  56      function reverse() {
  57          return new _DiffOp_Add($this->orig);
  58      }
  59  }
  60  
  61  class _DiffOp_Add extends _DiffOp {
  62      var $type = 'add';
  63  
  64      function __construct($lines) {
  65          $this->closing = $lines;
  66          $this->orig = false;
  67      }
  68  
  69      function reverse() {
  70          return new _DiffOp_Delete($this->closing);
  71      }
  72  }
  73  
  74  class _DiffOp_Change extends _DiffOp {
  75      var $type = 'change';
  76  
  77      function __construct($orig, $closing) {
  78          $this->orig = $orig;
  79          $this->closing = $closing;
  80      }
  81  
  82      function reverse() {
  83          return new _DiffOp_Change($this->closing, $this->orig);
  84      }
  85  }
  86  
  87  
  88  /**
  89   * Class used internally by Diff to actually compute the diffs.
  90   *
  91   * The algorithm used here is mostly lifted from the perl module
  92   * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
  93   *   http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
  94   *
  95   * More ideas are taken from:
  96   *   http://www.ics.uci.edu/~eppstein/161/960229.html
  97   *
  98   * Some ideas are (and a bit of code) are from from analyze.c, from GNU
  99   * diffutils-2.7, which can be found at:
 100   *   ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
 101   *
 102   * closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
 103   * are my own.
 104   *
 105   * @author Geoffrey T. Dairiki
 106   * @access private
 107   */
 108  class _DiffEngine {
 109  
 110      var $xchanged = array();
 111      var $ychanged = array();
 112      var $xv = array();
 113      var $yv = array();
 114      var $xind = array();
 115      var $yind = array();
 116      var $seq;
 117      var $in_seq;
 118      var $lcs;
 119  
 120      /**
 121       * @param array $from_lines
 122       * @param array $to_lines
 123       * @return _DiffOp[]
 124       */
 125      function diff($from_lines, $to_lines) {
 126          $n_from = count($from_lines);
 127          $n_to = count($to_lines);
 128  
 129          $this->xchanged = $this->ychanged = array();
 130          $this->xv = $this->yv = array();
 131          $this->xind = $this->yind = array();
 132          unset($this->seq);
 133          unset($this->in_seq);
 134          unset($this->lcs);
 135  
 136          // Skip leading common lines.
 137          for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
 138              if ($from_lines[$skip] != $to_lines[$skip])
 139                  break;
 140              $this->xchanged[$skip] = $this->ychanged[$skip] = false;
 141          }
 142          // Skip trailing common lines.
 143          $xi = $n_from;
 144          $yi = $n_to;
 145          for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
 146              if ($from_lines[$xi] != $to_lines[$yi])
 147                  break;
 148              $this->xchanged[$xi] = $this->ychanged[$yi] = false;
 149          }
 150  
 151          // Ignore lines which do not exist in both files.
 152          for ($xi = $skip; $xi < $n_from - $endskip; $xi++)
 153              $xhash[$from_lines[$xi]] = 1;
 154          for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
 155              $line = $to_lines[$yi];
 156              if (($this->ychanged[$yi] = empty($xhash[$line])))
 157                  continue;
 158              $yhash[$line] = 1;
 159              $this->yv[] = $line;
 160              $this->yind[] = $yi;
 161          }
 162          for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
 163              $line = $from_lines[$xi];
 164              if (($this->xchanged[$xi] = empty($yhash[$line])))
 165                  continue;
 166              $this->xv[] = $line;
 167              $this->xind[] = $xi;
 168          }
 169  
 170          // Find the LCS.
 171          $this->_compareseq(0, count($this->xv), 0, count($this->yv));
 172  
 173          // Merge edits when possible
 174          $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
 175          $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
 176  
 177          // Compute the edit operations.
 178          $edits = array();
 179          $xi = $yi = 0;
 180          while ($xi < $n_from || $yi < $n_to) {
 181              USE_ASSERTS && assert($yi < $n_to || $this->xchanged[$xi]);
 182              USE_ASSERTS && assert($xi < $n_from || $this->ychanged[$yi]);
 183  
 184              // Skip matching "snake".
 185              $copy = array();
 186              while ($xi < $n_from && $yi < $n_to && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
 187                  $copy[] = $from_lines[$xi++];
 188                  ++$yi;
 189              }
 190              if ($copy)
 191                  $edits[] = new _DiffOp_Copy($copy);
 192  
 193              // Find deletes & adds.
 194              $delete = array();
 195              while ($xi < $n_from && $this->xchanged[$xi])
 196                  $delete[] = $from_lines[$xi++];
 197  
 198              $add = array();
 199              while ($yi < $n_to && $this->ychanged[$yi])
 200                  $add[] = $to_lines[$yi++];
 201  
 202              if ($delete && $add)
 203                  $edits[] = new _DiffOp_Change($delete, $add);
 204              elseif ($delete)
 205                  $edits[] = new _DiffOp_Delete($delete);
 206              elseif ($add)
 207                  $edits[] = new _DiffOp_Add($add);
 208          }
 209          return $edits;
 210      }
 211  
 212  
 213      /**
 214       * Divide the Largest Common Subsequence (LCS) of the sequences
 215       * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
 216       * sized segments.
 217       *
 218       * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an
 219       * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
 220       * sub sequences.  The first sub-sequence is contained in [X0, X1),
 221       * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on.  Note
 222       * that (X0, Y0) == (XOFF, YOFF) and
 223       * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
 224       *
 225       * This function assumes that the first lines of the specified portions
 226       * of the two files do not match, and likewise that the last lines do not
 227       * match.  The caller must trim matching lines from the beginning and end
 228       * of the portions it is going to specify.
 229       *
 230       * @param integer $xoff
 231       * @param integer $xlim
 232       * @param integer $yoff
 233       * @param integer $ylim
 234       * @param integer $nchunks
 235       *
 236       * @return array
 237       */
 238      function _diag($xoff, $xlim, $yoff, $ylim, $nchunks) {
 239          $flip = false;
 240  
 241          if ($xlim - $xoff > $ylim - $yoff) {
 242              // Things seems faster (I'm not sure I understand why)
 243              // when the shortest sequence in X.
 244              $flip = true;
 245              list ($xoff, $xlim, $yoff, $ylim) = array($yoff, $ylim, $xoff, $xlim);
 246          }
 247  
 248          if ($flip)
 249              for ($i = $ylim - 1; $i >= $yoff; $i--)
 250                  $ymatches[$this->xv[$i]][] = $i;
 251          else
 252              for ($i = $ylim - 1; $i >= $yoff; $i--)
 253                  $ymatches[$this->yv[$i]][] = $i;
 254  
 255          $this->lcs = 0;
 256          $this->seq[0]= $yoff - 1;
 257          $this->in_seq = array();
 258          $ymids[0] = array();
 259  
 260          $numer = $xlim - $xoff + $nchunks - 1;
 261          $x = $xoff;
 262          for ($chunk = 0; $chunk < $nchunks; $chunk++) {
 263              if ($chunk > 0)
 264                  for ($i = 0; $i <= $this->lcs; $i++)
 265                      $ymids[$i][$chunk-1] = $this->seq[$i];
 266  
 267              $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
 268              for ( ; $x < $x1; $x++) {
 269                  $line = $flip ? $this->yv[$x] : $this->xv[$x];
 270                  if (empty($ymatches[$line]))
 271                      continue;
 272                  $matches = $ymatches[$line];
 273                  $switch = false;
 274                  foreach ($matches as $y) {
 275                      if ($switch && $y > $this->seq[$k-1]) {
 276                          USE_ASSERTS && assert($y < $this->seq[$k]);
 277                          // Optimization: this is a common case:
 278                          //  next match is just replacing previous match.
 279                          $this->in_seq[$this->seq[$k]] = false;
 280                          $this->seq[$k] = $y;
 281                          $this->in_seq[$y] = 1;
 282                      }
 283                      else if (empty($this->in_seq[$y])) {
 284                          $k = $this->_lcs_pos($y);
 285                          USE_ASSERTS && assert($k > 0);
 286                          $ymids[$k] = $ymids[$k-1];
 287                          $switch = true;
 288                      }
 289                  }
 290              }
 291          }
 292  
 293          $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
 294          $ymid = $ymids[$this->lcs];
 295          for ($n = 0; $n < $nchunks - 1; $n++) {
 296              $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
 297              $y1 = $ymid[$n] + 1;
 298              $seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
 299          }
 300          $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
 301  
 302          return array($this->lcs, $seps);
 303      }
 304  
 305      function _lcs_pos($ypos) {
 306          $end = $this->lcs;
 307          if ($end == 0 || $ypos > $this->seq[$end]) {
 308              $this->seq[++$this->lcs] = $ypos;
 309              $this->in_seq[$ypos] = 1;
 310              return $this->lcs;
 311          }
 312  
 313          $beg = 1;
 314          while ($beg < $end) {
 315              $mid = (int)(($beg + $end) / 2);
 316              if ($ypos > $this->seq[$mid])
 317                  $beg = $mid + 1;
 318              else
 319                  $end = $mid;
 320          }
 321  
 322          USE_ASSERTS && assert($ypos != $this->seq[$end]);
 323  
 324          $this->in_seq[$this->seq[$end]] = false;
 325          $this->seq[$end] = $ypos;
 326          $this->in_seq[$ypos] = 1;
 327          return $end;
 328      }
 329  
 330      /**
 331       * Find LCS of two sequences.
 332       *
 333       * The results are recorded in the vectors $this->{x,y}changed[], by
 334       * storing a 1 in the element for each line that is an insertion
 335       * or deletion (ie. is not in the LCS).
 336       *
 337       * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
 338       *
 339       * Note that XLIM, YLIM are exclusive bounds.
 340       * All line numbers are origin-0 and discarded lines are not counted.
 341       *
 342       * @param integer $xoff
 343       * @param integer $xlim
 344       * @param integer $yoff
 345       * @param integer $ylim
 346       */
 347      function _compareseq($xoff, $xlim, $yoff, $ylim) {
 348          // Slide down the bottom initial diagonal.
 349          while ($xoff < $xlim && $yoff < $ylim && $this->xv[$xoff] == $this->yv[$yoff]) {
 350              ++$xoff;
 351              ++$yoff;
 352          }
 353  
 354          // Slide up the top initial diagonal.
 355          while ($xlim > $xoff && $ylim > $yoff && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
 356              --$xlim;
 357              --$ylim;
 358          }
 359  
 360          if ($xoff == $xlim || $yoff == $ylim)
 361              $lcs = 0;
 362          else {
 363              // This is ad hoc but seems to work well.
 364              //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
 365              //$nchunks = max(2,min(8,(int)$nchunks));
 366              $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
 367              list ($lcs, $seps)
 368                  = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks);
 369          }
 370  
 371          if ($lcs == 0) {
 372              // X and Y sequences have no common subsequence:
 373              // mark all changed.
 374              while ($yoff < $ylim)
 375                  $this->ychanged[$this->yind[$yoff++]] = 1;
 376              while ($xoff < $xlim)
 377                  $this->xchanged[$this->xind[$xoff++]] = 1;
 378          }
 379          else {
 380              // Use the partitions to split this problem into subproblems.
 381              reset($seps);
 382              $pt1 = $seps[0];
 383              while ($pt2 = next($seps)) {
 384                  $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
 385                  $pt1 = $pt2;
 386              }
 387          }
 388      }
 389  
 390      /**
 391       * Adjust inserts/deletes of identical lines to join changes
 392       * as much as possible.
 393       *
 394       * We do something when a run of changed lines include a
 395       * line at one end and has an excluded, identical line at the other.
 396       * We are free to choose which identical line is included.
 397       * `compareseq' usually chooses the one at the beginning,
 398       * but usually it is cleaner to consider the following identical line
 399       * to be the "change".
 400       *
 401       * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
 402       *
 403       * @param array $lines
 404       * @param array $changed
 405       * @param array $other_changed
 406       */
 407      function _shift_boundaries($lines, &$changed, $other_changed) {
 408          $i = 0;
 409          $j = 0;
 410  
 411          USE_ASSERTS && assert(count($lines) == count($changed));
 412          $len = count($lines);
 413          $other_len = count($other_changed);
 414  
 415          while (1) {
 416              /*
 417               * Scan forwards to find beginning of another run of changes.
 418               * Also keep track of the corresponding point in the other file.
 419               *
 420               * Throughout this code, $i and $j are adjusted together so that
 421               * the first $i elements of $changed and the first $j elements
 422               * of $other_changed both contain the same number of zeros
 423               * (unchanged lines).
 424               * Furthermore, $j is always kept so that $j == $other_len or
 425               * $other_changed[$j] == false.
 426               */
 427              while ($j < $other_len && $other_changed[$j])
 428                  $j++;
 429  
 430              while ($i < $len && ! $changed[$i]) {
 431                  USE_ASSERTS && assert($j < $other_len && ! $other_changed[$j]);
 432                  $i++;
 433                  $j++;
 434                  while ($j < $other_len && $other_changed[$j])
 435                      $j++;
 436              }
 437  
 438              if ($i == $len)
 439                  break;
 440  
 441              $start = $i;
 442  
 443              // Find the end of this run of changes.
 444              while (++$i < $len && $changed[$i])
 445                  continue;
 446  
 447              do {
 448                  /*
 449                   * Record the length of this run of changes, so that
 450                   * we can later determine whether the run has grown.
 451                   */
 452                  $runlength = $i - $start;
 453  
 454                  /*
 455                   * Move the changed region back, so long as the
 456                   * previous unchanged line matches the last changed one.
 457                   * This merges with previous changed regions.
 458                   */
 459                  while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
 460                      $changed[--$start] = 1;
 461                      $changed[--$i] = false;
 462                      while ($start > 0 && $changed[$start - 1])
 463                          $start--;
 464                      USE_ASSERTS && assert($j > 0);
 465                      while ($other_changed[--$j])
 466                          continue;
 467                      USE_ASSERTS && assert($j >= 0 && !$other_changed[$j]);
 468                  }
 469  
 470                  /*
 471                   * Set CORRESPONDING to the end of the changed run, at the last
 472                   * point where it corresponds to a changed run in the other file.
 473                   * CORRESPONDING == LEN means no such point has been found.
 474                   */
 475                  $corresponding = $j < $other_len ? $i : $len;
 476  
 477                  /*
 478                   * Move the changed region forward, so long as the
 479                   * first changed line matches the following unchanged one.
 480                   * This merges with following changed regions.
 481                   * Do this second, so that if there are no merges,
 482                   * the changed region is moved forward as far as possible.
 483                   */
 484                  while ($i < $len && $lines[$start] == $lines[$i]) {
 485                      $changed[$start++] = false;
 486                      $changed[$i++] = 1;
 487                      while ($i < $len && $changed[$i])
 488                          $i++;
 489  
 490                      USE_ASSERTS && assert($j < $other_len && ! $other_changed[$j]);
 491                      $j++;
 492                      if ($j < $other_len && $other_changed[$j]) {
 493                          $corresponding = $i;
 494                          while ($j < $other_len && $other_changed[$j])
 495                              $j++;
 496                      }
 497                  }
 498              } while ($runlength != $i - $start);
 499  
 500              /*
 501               * If possible, move the fully-merged run of changes
 502               * back to a corresponding run in the other file.
 503               */
 504              while ($corresponding < $i) {
 505                  $changed[--$start] = 1;
 506                  $changed[--$i] = 0;
 507                  USE_ASSERTS && assert($j > 0);
 508                  while ($other_changed[--$j])
 509                      continue;
 510                  USE_ASSERTS && assert($j >= 0 && !$other_changed[$j]);
 511              }
 512          }
 513      }
 514  }
 515  
 516  /**
 517   * Class representing a 'diff' between two sequences of strings.
 518   */
 519  class Diff {
 520  
 521      var $edits;
 522  
 523      /**
 524       * Constructor.
 525       * Computes diff between sequences of strings.
 526       *
 527       * @param array $from_lines An array of strings.
 528       *                          (Typically these are lines from a file.)
 529       * @param array $to_lines   An array of strings.
 530       */
 531      function __construct($from_lines, $to_lines) {
 532          $eng = new _DiffEngine;
 533          $this->edits = $eng->diff($from_lines, $to_lines);
 534          //$this->_check($from_lines, $to_lines);
 535      }
 536  
 537      /**
 538       * Compute reversed Diff.
 539       *
 540       * SYNOPSIS:
 541       *
 542       *  $diff = new Diff($lines1, $lines2);
 543       *  $rev = $diff->reverse();
 544       *
 545       * @return Diff  A Diff object representing the inverse of the
 546       *               original diff.
 547       */
 548      function reverse() {
 549          $rev = $this;
 550          $rev->edits = array();
 551          foreach ($this->edits as $edit) {
 552              $rev->edits[] = $edit->reverse();
 553          }
 554          return $rev;
 555      }
 556  
 557      /**
 558       * Check for empty diff.
 559       *
 560       * @return bool True iff two sequences were identical.
 561       */
 562      function isEmpty() {
 563          foreach ($this->edits as $edit) {
 564              if ($edit->type != 'copy')
 565                  return false;
 566          }
 567          return true;
 568      }
 569  
 570      /**
 571       * Compute the length of the Longest Common Subsequence (LCS).
 572       *
 573       * This is mostly for diagnostic purposed.
 574       *
 575       * @return int The length of the LCS.
 576       */
 577      function lcs() {
 578          $lcs = 0;
 579          foreach ($this->edits as $edit) {
 580              if ($edit->type == 'copy')
 581                  $lcs += count($edit->orig);
 582          }
 583          return $lcs;
 584      }
 585  
 586      /**
 587       * Get the original set of lines.
 588       *
 589       * This reconstructs the $from_lines parameter passed to the
 590       * constructor.
 591       *
 592       * @return array The original sequence of strings.
 593       */
 594      function orig() {
 595          $lines = array();
 596  
 597          foreach ($this->edits as $edit) {
 598              if ($edit->orig)
 599                  array_splice($lines, count($lines), 0, $edit->orig);
 600          }
 601          return $lines;
 602      }
 603  
 604      /**
 605       * Get the closing set of lines.
 606       *
 607       * This reconstructs the $to_lines parameter passed to the
 608       * constructor.
 609       *
 610       * @return array The sequence of strings.
 611       */
 612      function closing() {
 613          $lines = array();
 614  
 615          foreach ($this->edits as $edit) {
 616              if ($edit->closing)
 617                  array_splice($lines, count($lines), 0, $edit->closing);
 618          }
 619          return $lines;
 620      }
 621  
 622      /**
 623       * Check a Diff for validity.
 624       *
 625       * This is here only for debugging purposes.
 626       *
 627       * @param mixed $from_lines
 628       * @param mixed $to_lines
 629       */
 630      function _check($from_lines, $to_lines) {
 631          if (serialize($from_lines) != serialize($this->orig()))
 632              trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
 633          if (serialize($to_lines) != serialize($this->closing()))
 634              trigger_error("Reconstructed closing doesn't match", E_USER_ERROR);
 635  
 636          $rev = $this->reverse();
 637          if (serialize($to_lines) != serialize($rev->orig()))
 638              trigger_error("Reversed original doesn't match", E_USER_ERROR);
 639          if (serialize($from_lines) != serialize($rev->closing()))
 640              trigger_error("Reversed closing doesn't match", E_USER_ERROR);
 641  
 642          $prevtype = 'none';
 643          foreach ($this->edits as $edit) {
 644              if ($prevtype == $edit->type)
 645                  trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
 646              $prevtype = $edit->type;
 647          }
 648  
 649          $lcs = $this->lcs();
 650          trigger_error("Diff okay: LCS = $lcs", E_USER_NOTICE);
 651      }
 652  }
 653  
 654  /**
 655   * FIXME: bad name.
 656   */
 657  class MappedDiff extends Diff {
 658      /**
 659       * Constructor.
 660       *
 661       * Computes diff between sequences of strings.
 662       *
 663       * This can be used to compute things like
 664       * case-insensitve diffs, or diffs which ignore
 665       * changes in white-space.
 666       *
 667       * @param string[] $from_lines         An array of strings.
 668       *                                     (Typically these are lines from a file.)
 669       *
 670       * @param string[] $to_lines           An array of strings.
 671       *
 672       * @param string[] $mapped_from_lines  This array should
 673       *                                     have the same size number of elements as $from_lines.
 674       *                                     The elements in $mapped_from_lines and
 675       *                                     $mapped_to_lines are what is actually compared
 676       *                                     when computing the diff.
 677       *
 678       * @param string[] $mapped_to_lines    This array should
 679       *                                     have the same number of elements as $to_lines.
 680       */
 681      function __construct($from_lines, $to_lines, $mapped_from_lines, $mapped_to_lines) {
 682  
 683          assert(count($from_lines) == count($mapped_from_lines));
 684          assert(count($to_lines) == count($mapped_to_lines));
 685  
 686          parent::__construct($mapped_from_lines, $mapped_to_lines);
 687  
 688          $xi = $yi = 0;
 689          $ecnt = count($this->edits);
 690          for ($i = 0; $i < $ecnt; $i++) {
 691              $orig = &$this->edits[$i]->orig;
 692              if (is_array($orig)) {
 693                  $orig = array_slice($from_lines, $xi, count($orig));
 694                  $xi += count($orig);
 695              }
 696  
 697              $closing = &$this->edits[$i]->closing;
 698              if (is_array($closing)) {
 699                  $closing = array_slice($to_lines, $yi, count($closing));
 700                  $yi += count($closing);
 701              }
 702          }
 703      }
 704  }
 705  
 706  /**
 707   * A class to format Diffs
 708   *
 709   * This class formats the diff in classic diff format.
 710   * It is intended that this class be customized via inheritance,
 711   * to obtain fancier outputs.
 712   */
 713  class DiffFormatter {
 714      /**
 715       * Number of leading context "lines" to preserve.
 716       *
 717       * This should be left at zero for this class, but subclasses
 718       * may want to set this to other values.
 719       */
 720      var $leading_context_lines = 0;
 721  
 722      /**
 723       * Number of trailing context "lines" to preserve.
 724       *
 725       * This should be left at zero for this class, but subclasses
 726       * may want to set this to other values.
 727       */
 728      var $trailing_context_lines = 0;
 729  
 730      /**
 731       * Format a diff.
 732       *
 733       * @param Diff $diff A Diff object.
 734       * @return string The formatted output.
 735       */
 736      function format($diff) {
 737  
 738          $xi = $yi = 1;
 739          $x0 = $y0 = 0;
 740          $block = false;
 741          $context = array();
 742  
 743          $nlead = $this->leading_context_lines;
 744          $ntrail = $this->trailing_context_lines;
 745  
 746          $this->_start_diff();
 747  
 748          foreach ($diff->edits as $edit) {
 749              if ($edit->type == 'copy') {
 750                  if (is_array($block)) {
 751                      if (count($edit->orig) <= $nlead + $ntrail) {
 752                          $block[] = $edit;
 753                      }
 754                      else{
 755                          if ($ntrail) {
 756                              $context = array_slice($edit->orig, 0, $ntrail);
 757                              $block[] = new _DiffOp_Copy($context);
 758                          }
 759                          $this->_block($x0, $ntrail + $xi - $x0, $y0, $ntrail + $yi - $y0, $block);
 760                          $block = false;
 761                      }
 762                  }
 763                  $context = $edit->orig;
 764              }
 765              else {
 766                  if (! is_array($block)) {
 767                      $context = array_slice($context, count($context) - $nlead);
 768                      $x0 = $xi - count($context);
 769                      $y0 = $yi - count($context);
 770                      $block = array();
 771                      if ($context)
 772                          $block[] = new _DiffOp_Copy($context);
 773                  }
 774                  $block[] = $edit;
 775              }
 776  
 777              if ($edit->orig)
 778                  $xi += count($edit->orig);
 779              if ($edit->closing)
 780                  $yi += count($edit->closing);
 781          }
 782  
 783          if (is_array($block))
 784              $this->_block($x0, $xi - $x0, $y0, $yi - $y0, $block);
 785  
 786          return $this->_end_diff();
 787      }
 788  
 789      /**
 790       * @param int $xbeg
 791       * @param int $xlen
 792       * @param int $ybeg
 793       * @param int $ylen
 794       * @param array $edits
 795       */
 796      function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) {
 797          $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen));
 798          foreach ($edits as $edit) {
 799              if ($edit->type == 'copy')
 800                  $this->_context($edit->orig);
 801              elseif ($edit->type == 'add')
 802                  $this->_added($edit->closing);
 803              elseif ($edit->type == 'delete')
 804                  $this->_deleted($edit->orig);
 805              elseif ($edit->type == 'change')
 806                  $this->_changed($edit->orig, $edit->closing);
 807              else
 808                  trigger_error("Unknown edit type", E_USER_ERROR);
 809          }
 810          $this->_end_block();
 811      }
 812  
 813      function _start_diff() {
 814          ob_start();
 815      }
 816  
 817      function _end_diff() {
 818          $val = ob_get_contents();
 819          ob_end_clean();
 820          return $val;
 821      }
 822  
 823      /**
 824       * @param int $xbeg
 825       * @param int $xlen
 826       * @param int $ybeg
 827       * @param int $ylen
 828       * @return string
 829       */
 830      function _block_header($xbeg, $xlen, $ybeg, $ylen) {
 831          if ($xlen > 1)
 832              $xbeg .= "," . ($xbeg + $xlen - 1);
 833          if ($ylen > 1)
 834              $ybeg .= "," . ($ybeg + $ylen - 1);
 835  
 836          return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg;
 837      }
 838  
 839      /**
 840       * @param string $header
 841       */
 842      function _start_block($header) {
 843          echo $header;
 844      }
 845  
 846      function _end_block() {
 847      }
 848  
 849      function _lines($lines, $prefix = ' ') {
 850          foreach ($lines as $line)
 851              echo "$prefix ".$this->_escape($line)."\n";
 852      }
 853  
 854      function _context($lines) {
 855          $this->_lines($lines);
 856      }
 857  
 858      function _added($lines) {
 859          $this->_lines($lines, ">");
 860      }
 861      function _deleted($lines) {
 862          $this->_lines($lines, "<");
 863      }
 864  
 865      function _changed($orig, $closing) {
 866          $this->_deleted($orig);
 867          echo "---\n";
 868          $this->_added($closing);
 869      }
 870  
 871      /**
 872       * Escape string
 873       *
 874       * Override this method within other formatters if escaping required.
 875       * Base class requires $str to be returned WITHOUT escaping.
 876       *
 877       * @param $str string Text string to escape
 878       * @return string The escaped string.
 879       */
 880      function _escape($str){
 881          return $str;
 882      }
 883  }
 884  
 885  /**
 886   * Utilityclass for styling HTML formatted diffs
 887   *
 888   * Depends on global var $DIFF_INLINESTYLES, if true some minimal predefined
 889   * inline styles are used. Useful for HTML mails and RSS feeds
 890   *
 891   * @author Andreas Gohr <andi@splitbrain.org>
 892   */
 893  class HTMLDiff {
 894      /**
 895       * Holds the style names and basic CSS
 896       */
 897      static public $styles = array(
 898              'diff-addedline'    => 'background-color: #ddffdd;',
 899              'diff-deletedline'  => 'background-color: #ffdddd;',
 900              'diff-context'      => 'background-color: #f5f5f5;',
 901              'diff-mark'         => 'color: #ff0000;',
 902          );
 903  
 904      /**
 905       * Return a class or style parameter
 906       *
 907       * @param string $classname
 908       *
 909       * @return string
 910       */
 911      static function css($classname){
 912          global $DIFF_INLINESTYLES;
 913  
 914          if($DIFF_INLINESTYLES){
 915              if(!isset(self::$styles[$classname])) return '';
 916              return 'style="'.self::$styles[$classname].'"';
 917          }else{
 918              return 'class="'.$classname.'"';
 919          }
 920      }
 921  }
 922  
 923  /**
 924   *  Additions by Axel Boldt follow, partly taken from diff.php, phpwiki-1.3.3
 925   *
 926   */
 927  
 928  define('NBSP', "\xC2\xA0");     // utf-8 non-breaking space.
 929  
 930  class _HWLDF_WordAccumulator {
 931  
 932      function __construct() {
 933          $this->_lines = array();
 934          $this->_line = '';
 935          $this->_group = '';
 936          $this->_tag = '';
 937      }
 938  
 939      function _flushGroup($new_tag) {
 940          if ($this->_group !== '') {
 941              if ($this->_tag == 'mark')
 942                  $this->_line .= '<strong '.HTMLDiff::css('diff-mark').'>'.$this->_escape($this->_group).'</strong>';
 943              elseif ($this->_tag == 'add')
 944                  $this->_line .= '<span '.HTMLDiff::css('diff-addedline').'>'.$this->_escape($this->_group).'</span>';
 945              elseif ($this->_tag == 'del')
 946                  $this->_line .= '<span '.HTMLDiff::css('diff-deletedline').'><del>'.$this->_escape($this->_group).'</del></span>';
 947              else
 948                  $this->_line .= $this->_escape($this->_group);
 949          }
 950          $this->_group = '';
 951          $this->_tag = $new_tag;
 952      }
 953  
 954      /**
 955       * @param string $new_tag
 956       */
 957      function _flushLine($new_tag) {
 958          $this->_flushGroup($new_tag);
 959          if ($this->_line != '')
 960              $this->_lines[] = $this->_line;
 961          $this->_line = '';
 962      }
 963  
 964      function addWords($words, $tag = '') {
 965          if ($tag != $this->_tag)
 966              $this->_flushGroup($tag);
 967  
 968          foreach ($words as $word) {
 969              // new-line should only come as first char of word.
 970              if ($word == '')
 971                  continue;
 972              if ($word[0] == "\n") {
 973                  $this->_group .= NBSP;
 974                  $this->_flushLine($tag);
 975                  $word = substr($word, 1);
 976              }
 977              assert(!strstr($word, "\n"));
 978              $this->_group .= $word;
 979          }
 980      }
 981  
 982      function getLines() {
 983          $this->_flushLine('~done');
 984          return $this->_lines;
 985      }
 986  
 987      function _escape($str){
 988          return hsc($str);
 989      }
 990  }
 991  
 992  class WordLevelDiff extends MappedDiff {
 993  
 994      function __construct($orig_lines, $closing_lines) {
 995          list ($orig_words, $orig_stripped) = $this->_split($orig_lines);
 996          list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
 997  
 998          parent::__construct($orig_words, $closing_words, $orig_stripped, $closing_stripped);
 999      }
1000  
1001      function _split($lines) {
1002          if (!preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xsu',
1003               implode("\n", $lines), $m)) {
1004              return array(array(''), array(''));
1005          }
1006          return array($m[0], $m[1]);
1007      }
1008  
1009      function orig() {
1010          $orig = new _HWLDF_WordAccumulator;
1011  
1012          foreach ($this->edits as $edit) {
1013              if ($edit->type == 'copy')
1014                  $orig->addWords($edit->orig);
1015              elseif ($edit->orig)
1016                  $orig->addWords($edit->orig, 'mark');
1017          }
1018          return $orig->getLines();
1019      }
1020  
1021      function closing() {
1022          $closing = new _HWLDF_WordAccumulator;
1023  
1024          foreach ($this->edits as $edit) {
1025              if ($edit->type == 'copy')
1026                  $closing->addWords($edit->closing);
1027              elseif ($edit->closing)
1028                  $closing->addWords($edit->closing, 'mark');
1029          }
1030          return $closing->getLines();
1031      }
1032  }
1033  
1034  class InlineWordLevelDiff extends MappedDiff {
1035  
1036      function __construct($orig_lines, $closing_lines) {
1037          list ($orig_words, $orig_stripped) = $this->_split($orig_lines);
1038          list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
1039  
1040          parent::__construct($orig_words, $closing_words, $orig_stripped, $closing_stripped);
1041      }
1042  
1043      function _split($lines) {
1044          if (!preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xsu',
1045               implode("\n", $lines), $m)) {
1046              return array(array(''), array(''));
1047          }
1048          return array($m[0], $m[1]);
1049      }
1050  
1051      function inline() {
1052          $orig = new _HWLDF_WordAccumulator;
1053          foreach ($this->edits as $edit) {
1054              if ($edit->type == 'copy')
1055                  $orig->addWords($edit->closing);
1056              elseif ($edit->type == 'change'){
1057                  $orig->addWords($edit->orig, 'del');
1058                  $orig->addWords($edit->closing, 'add');
1059              } elseif ($edit->type == 'delete')
1060                  $orig->addWords($edit->orig, 'del');
1061              elseif ($edit->type == 'add')
1062                  $orig->addWords($edit->closing, 'add');
1063              elseif ($edit->orig)
1064                  $orig->addWords($edit->orig, 'del');
1065          }
1066          return $orig->getLines();
1067      }
1068  }
1069  
1070  /**
1071   * "Unified" diff formatter.
1072   *
1073   * This class formats the diff in classic "unified diff" format.
1074   *
1075   * NOTE: output is plain text and unsafe for use in HTML without escaping.
1076   */
1077  class UnifiedDiffFormatter extends DiffFormatter {
1078  
1079      function __construct($context_lines = 4) {
1080          $this->leading_context_lines = $context_lines;
1081          $this->trailing_context_lines = $context_lines;
1082      }
1083  
1084      function _block_header($xbeg, $xlen, $ybeg, $ylen) {
1085          if ($xlen != 1)
1086              $xbeg .= "," . $xlen;
1087          if ($ylen != 1)
1088              $ybeg .= "," . $ylen;
1089          return "@@ -$xbeg +$ybeg @@\n";
1090      }
1091  
1092      function _added($lines) {
1093          $this->_lines($lines, "+");
1094      }
1095      function _deleted($lines) {
1096          $this->_lines($lines, "-");
1097      }
1098      function _changed($orig, $final) {
1099          $this->_deleted($orig);
1100          $this->_added($final);
1101      }
1102  }
1103  
1104  /**
1105   *  Wikipedia Table style diff formatter.
1106   *
1107   */
1108  class TableDiffFormatter extends DiffFormatter {
1109      var $colspan = 2;
1110  
1111      function __construct() {
1112          $this->leading_context_lines = 2;
1113          $this->trailing_context_lines = 2;
1114      }
1115  
1116      /**
1117       * @param Diff $diff
1118       * @return string
1119       */
1120      function format($diff) {
1121          // Preserve whitespaces by converting some to non-breaking spaces.
1122          // Do not convert all of them to allow word-wrap.
1123          $val = parent::format($diff);
1124          $val = str_replace('  ','&#160; ', $val);
1125          $val = preg_replace('/ (?=<)|(?<=[ >]) /', '&#160;', $val);
1126          return $val;
1127      }
1128  
1129      function _pre($text){
1130          $text = htmlspecialchars($text);
1131          return $text;
1132      }
1133  
1134      function _block_header($xbeg, $xlen, $ybeg, $ylen) {
1135          global $lang;
1136          $l1 = $lang['line'].' '.$xbeg;
1137          $l2 = $lang['line'].' '.$ybeg;
1138          $r = '<tr><td '.HTMLDiff::css('diff-blockheader').' colspan="'.$this->colspan.'">'.$l1.":</td>\n".
1139               '<td '.HTMLDiff::css('diff-blockheader').' colspan="'.$this->colspan.'">'.$l2.":</td>\n".
1140               "</tr>\n";
1141          return $r;
1142      }
1143  
1144      function _start_block($header) {
1145          print($header);
1146      }
1147  
1148      function _end_block() {
1149      }
1150  
1151      function _lines($lines, $prefix=' ', $color="white") {
1152      }
1153  
1154      function addedLine($line,$escaped=false) {
1155          if (!$escaped){
1156              $line = $this->_escape($line);
1157          }
1158          return '<td '.HTMLDiff::css('diff-lineheader').'>+</td>'.
1159                 '<td '.HTMLDiff::css('diff-addedline').'>' .  $line.'</td>';
1160      }
1161  
1162      function deletedLine($line,$escaped=false) {
1163          if (!$escaped){
1164              $line = $this->_escape($line);
1165          }
1166          return '<td '.HTMLDiff::css('diff-lineheader').'>-</td>'.
1167                 '<td '.HTMLDiff::css('diff-deletedline').'>' .  $line.'</td>';
1168      }
1169  
1170      function emptyLine() {
1171          return '<td colspan="'.$this->colspan.'">&#160;</td>';
1172      }
1173  
1174      function contextLine($line) {
1175          return '<td '.HTMLDiff::css('diff-lineheader').'>&#160;</td>'.
1176                 '<td '.HTMLDiff::css('diff-context').'>'.$this->_escape($line).'</td>';
1177      }
1178  
1179      function _added($lines) {
1180          $this->_addedLines($lines,false);
1181      }
1182  
1183      function _addedLines($lines,$escaped=false){
1184          foreach ($lines as $line) {
1185              print('<tr>' . $this->emptyLine() . $this->addedLine($line,$escaped) . "</tr>\n");
1186          }
1187      }
1188  
1189      function _deleted($lines) {
1190          foreach ($lines as $line) {
1191              print('<tr>' . $this->deletedLine($line) . $this->emptyLine() . "</tr>\n");
1192          }
1193      }
1194  
1195      function _context($lines) {
1196          foreach ($lines as $line) {
1197              print('<tr>' . $this->contextLine($line) .  $this->contextLine($line) . "</tr>\n");
1198          }
1199      }
1200  
1201      function _changed($orig, $closing) {
1202          $diff = new WordLevelDiff($orig, $closing);  // this escapes the diff data
1203          $del = $diff->orig();
1204          $add = $diff->closing();
1205  
1206          while ($line = array_shift($del)) {
1207              $aline = array_shift($add);
1208              print('<tr>' . $this->deletedLine($line,true) . $this->addedLine($aline,true) . "</tr>\n");
1209          }
1210          $this->_addedLines($add,true); # If any leftovers
1211      }
1212  
1213      function _escape($str) {
1214          return hsc($str);
1215      }
1216  }
1217  
1218  /**
1219   *  Inline style diff formatter.
1220   *
1221   */
1222  class InlineDiffFormatter extends DiffFormatter {
1223      var $colspan = 2;
1224  
1225      function __construct() {
1226          $this->leading_context_lines = 2;
1227          $this->trailing_context_lines = 2;
1228      }
1229  
1230      /**
1231       * @param Diff $diff
1232       * @return string
1233       */
1234      function format($diff) {
1235          // Preserve whitespaces by converting some to non-breaking spaces.
1236          // Do not convert all of them to allow word-wrap.
1237          $val = parent::format($diff);
1238          $val = str_replace('  ','&#160; ', $val);
1239          $val = preg_replace('/ (?=<)|(?<=[ >]) /', '&#160;', $val);
1240          return $val;
1241      }
1242  
1243      function _pre($text){
1244          $text = htmlspecialchars($text);
1245          return $text;
1246      }
1247  
1248      function _block_header($xbeg, $xlen, $ybeg, $ylen) {
1249          global $lang;
1250          if ($xlen != 1)
1251              $xbeg .= "," . $xlen;
1252          if ($ylen != 1)
1253              $ybeg .= "," . $ylen;
1254          $r = '<tr><td colspan="'.$this->colspan.'" '.HTMLDiff::css('diff-blockheader').'>@@ '.$lang['line']." -$xbeg +$ybeg @@";
1255          $r .= ' <span '.HTMLDiff::css('diff-deletedline').'><del>'.$lang['deleted'].'</del></span>';
1256          $r .= ' <span '.HTMLDiff::css('diff-addedline').'>'.$lang['created'].'</span>';
1257          $r .= "</td></tr>\n";
1258          return $r;
1259      }
1260  
1261      function _start_block($header) {
1262          print($header."\n");
1263      }
1264  
1265      function _end_block() {
1266      }
1267  
1268      function _lines($lines, $prefix=' ', $color="white") {
1269      }
1270  
1271      function _added($lines) {
1272          foreach ($lines as $line) {
1273              print('<tr><td '.HTMLDiff::css('diff-lineheader').'>&#160;</td><td '.HTMLDiff::css('diff-addedline').'>'. $this->_escape($line) . "</td></tr>\n");
1274          }
1275      }
1276  
1277      function _deleted($lines) {
1278          foreach ($lines as $line) {
1279              print('<tr><td '.HTMLDiff::css('diff-lineheader').'>&#160;</td><td '.HTMLDiff::css('diff-deletedline').'><del>' . $this->_escape($line) . "</del></td></tr>\n");
1280          }
1281      }
1282  
1283      function _context($lines) {
1284          foreach ($lines as $line) {
1285              print('<tr><td '.HTMLDiff::css('diff-lineheader').'>&#160;</td><td '.HTMLDiff::css('diff-context').'>'. $this->_escape($line) ."</td></tr>\n");
1286          }
1287      }
1288  
1289      function _changed($orig, $closing) {
1290          $diff = new InlineWordLevelDiff($orig, $closing);  // this escapes the diff data
1291          $add = $diff->inline();
1292  
1293          foreach ($add as $line)
1294              print('<tr><td '.HTMLDiff::css('diff-lineheader').'>&#160;</td><td>'.$line."</td></tr>\n");
1295      }
1296  
1297      function _escape($str) {
1298          return hsc($str);
1299      }
1300  }
1301  
1302  /**
1303   * A class for computing three way diffs.
1304   *
1305   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1306   */
1307  class Diff3 extends Diff {
1308  
1309      /**
1310       * Conflict counter.
1311       *
1312       * @var integer
1313       */
1314      var $_conflictingBlocks = 0;
1315  
1316      /**
1317       * Computes diff between 3 sequences of strings.
1318       *
1319       * @param array $orig    The original lines to use.
1320       * @param array $final1  The first version to compare to.
1321       * @param array $final2  The second version to compare to.
1322       */
1323      function __construct($orig, $final1, $final2) {
1324          $engine = new _DiffEngine();
1325  
1326          $this->_edits = $this->_diff3($engine->diff($orig, $final1),
1327                                        $engine->diff($orig, $final2));
1328      }
1329  
1330      /**
1331       * Returns the merged lines
1332       *
1333       * @param string $label1  label for first version
1334       * @param string $label2  label for second version
1335       * @param string $label3  separator between versions
1336       * @return array          lines of the merged text
1337       */
1338      function mergedOutput($label1='<<<<<<<',$label2='>>>>>>>',$label3='=======') {
1339          $lines = array();
1340          foreach ($this->_edits as $edit) {
1341              if ($edit->isConflict()) {
1342                  /* FIXME: this should probably be moved somewhere else. */
1343                  $lines = array_merge($lines,
1344                                       array($label1),
1345                                       $edit->final1,
1346                                       array($label3),
1347                                       $edit->final2,
1348                                       array($label2));
1349                  $this->_conflictingBlocks++;
1350              } else {
1351                  $lines = array_merge($lines, $edit->merged());
1352              }
1353          }
1354  
1355          return $lines;
1356      }
1357  
1358      /**
1359       * @access private
1360       *
1361       * @param array $edits1
1362       * @param array $edits2
1363       *
1364       * @return array
1365       */
1366      function _diff3($edits1, $edits2) {
1367          $edits = array();
1368          $bb = new _Diff3_BlockBuilder();
1369  
1370          $e1 = current($edits1);
1371          $e2 = current($edits2);
1372          while ($e1 || $e2) {
1373              if ($e1 && $e2 && is_a($e1, '_DiffOp_copy') && is_a($e2, '_DiffOp_copy')) {
1374                  /* We have copy blocks from both diffs. This is the (only)
1375                   * time we want to emit a diff3 copy block.  Flush current
1376                   * diff3 diff block, if any. */
1377                  if ($edit = $bb->finish()) {
1378                      $edits[] = $edit;
1379                  }
1380  
1381                  $ncopy = min($e1->norig(), $e2->norig());
1382                  assert($ncopy > 0);
1383                  $edits[] = new _Diff3_Op_copy(array_slice($e1->orig, 0, $ncopy));
1384  
1385                  if ($e1->norig() > $ncopy) {
1386                      array_splice($e1->orig, 0, $ncopy);
1387                      array_splice($e1->closing, 0, $ncopy);
1388                  } else {
1389                      $e1 = next($edits1);
1390                  }
1391  
1392                  if ($e2->norig() > $ncopy) {
1393                      array_splice($e2->orig, 0, $ncopy);
1394                      array_splice($e2->closing, 0, $ncopy);
1395                  } else {
1396                      $e2 = next($edits2);
1397                  }
1398              } else {
1399                  if ($e1 && $e2) {
1400                      if ($e1->orig && $e2->orig) {
1401                          $norig = min($e1->norig(), $e2->norig());
1402                          $orig = array_splice($e1->orig, 0, $norig);
1403                          array_splice($e2->orig, 0, $norig);
1404                          $bb->input($orig);
1405                      }
1406  
1407                      if (is_a($e1, '_DiffOp_copy')) {
1408                          $bb->out1(array_splice($e1->closing, 0, $norig));
1409                      }
1410  
1411                      if (is_a($e2, '_DiffOp_copy')) {
1412                          $bb->out2(array_splice($e2->closing, 0, $norig));
1413                      }
1414                  }
1415  
1416                  if ($e1 && ! $e1->orig) {
1417                      $bb->out1($e1->closing);
1418                      $e1 = next($edits1);
1419                  }
1420                  if ($e2 && ! $e2->orig) {
1421                      $bb->out2($e2->closing);
1422                      $e2 = next($edits2);
1423                  }
1424              }
1425          }
1426  
1427          if ($edit = $bb->finish()) {
1428              $edits[] = $edit;
1429          }
1430  
1431          return $edits;
1432      }
1433  }
1434  
1435  /**
1436   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1437   *
1438   * @access private
1439   */
1440  class _Diff3_Op {
1441  
1442      function __construct($orig = false, $final1 = false, $final2 = false) {
1443          $this->orig = $orig ? $orig : array();
1444          $this->final1 = $final1 ? $final1 : array();
1445          $this->final2 = $final2 ? $final2 : array();
1446      }
1447  
1448      function merged() {
1449          if (!isset($this->_merged)) {
1450              if ($this->final1 === $this->final2) {
1451                  $this->_merged = &$this->final1;
1452              } elseif ($this->final1 === $this->orig) {
1453                  $this->_merged = &$this->final2;
1454              } elseif ($this->final2 === $this->orig) {
1455                  $this->_merged = &$this->final1;
1456              } else {
1457                  $this->_merged = false;
1458              }
1459          }
1460  
1461          return $this->_merged;
1462      }
1463  
1464      function isConflict() {
1465          return $this->merged() === false;
1466      }
1467  
1468  }
1469  
1470  /**
1471   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1472   *
1473   * @access private
1474   */
1475  class _Diff3_Op_copy extends _Diff3_Op {
1476  
1477      function __construct($lines = false) {
1478          $this->orig = $lines ? $lines : array();
1479          $this->final1 = &$this->orig;
1480          $this->final2 = &$this->orig;
1481      }
1482  
1483      function merged() {
1484          return $this->orig;
1485      }
1486  
1487      function isConflict() {
1488          return false;
1489      }
1490  }
1491  
1492  /**
1493   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1494   *
1495   * @access private
1496   */
1497  class _Diff3_BlockBuilder {
1498  
1499      function __construct() {
1500          $this->_init();
1501      }
1502  
1503      function input($lines) {
1504          if ($lines) {
1505              $this->_append($this->orig, $lines);
1506          }
1507      }
1508  
1509      function out1($lines) {
1510          if ($lines) {
1511              $this->_append($this->final1, $lines);
1512          }
1513      }
1514  
1515      function out2($lines) {
1516          if ($lines) {
1517              $this->_append($this->final2, $lines);
1518          }
1519      }
1520  
1521      function isEmpty() {
1522          return !$this->orig && !$this->final1 && !$this->final2;
1523      }
1524  
1525      function finish() {
1526          if ($this->isEmpty()) {
1527              return false;
1528          } else {
1529              $edit = new _Diff3_Op($this->orig, $this->final1, $this->final2);
1530              $this->_init();
1531              return $edit;
1532          }
1533      }
1534  
1535      function _init() {
1536          $this->orig = $this->final1 = $this->final2 = array();
1537      }
1538  
1539      function _append(&$array, $lines) {
1540          array_splice($array, sizeof($array), 0, $lines);
1541      }
1542  }
1543  
1544  //Setup VIM: ex: et ts=4 :