[ 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      /** @var array */
 933      protected $_lines;
 934  
 935      /** @var string */
 936      protected $_line;
 937  
 938      /** @var string */
 939      protected $_group;
 940  
 941      /** @var string */
 942      protected $_tag;
 943  
 944      function __construct() {
 945          $this->_lines = array();
 946          $this->_line = '';
 947          $this->_group = '';
 948          $this->_tag = '';
 949      }
 950  
 951      function _flushGroup($new_tag) {
 952          if ($this->_group !== '') {
 953              if ($this->_tag == 'mark')
 954                  $this->_line .= '<strong '.HTMLDiff::css('diff-mark').'>'.$this->_escape($this->_group).'</strong>';
 955              elseif ($this->_tag == 'add')
 956                  $this->_line .= '<span '.HTMLDiff::css('diff-addedline').'>'.$this->_escape($this->_group).'</span>';
 957              elseif ($this->_tag == 'del')
 958                  $this->_line .= '<span '.HTMLDiff::css('diff-deletedline').'><del>'.$this->_escape($this->_group).'</del></span>';
 959              else
 960                  $this->_line .= $this->_escape($this->_group);
 961          }
 962          $this->_group = '';
 963          $this->_tag = $new_tag;
 964      }
 965  
 966      /**
 967       * @param string $new_tag
 968       */
 969      function _flushLine($new_tag) {
 970          $this->_flushGroup($new_tag);
 971          if ($this->_line != '')
 972              $this->_lines[] = $this->_line;
 973          $this->_line = '';
 974      }
 975  
 976      function addWords($words, $tag = '') {
 977          if ($tag != $this->_tag)
 978              $this->_flushGroup($tag);
 979  
 980          foreach ($words as $word) {
 981              // new-line should only come as first char of word.
 982              if ($word == '')
 983                  continue;
 984              if ($word[0] == "\n") {
 985                  $this->_group .= NBSP;
 986                  $this->_flushLine($tag);
 987                  $word = substr($word, 1);
 988              }
 989              assert(!strstr($word, "\n"));
 990              $this->_group .= $word;
 991          }
 992      }
 993  
 994      function getLines() {
 995          $this->_flushLine('~done');
 996          return $this->_lines;
 997      }
 998  
 999      function _escape($str){
1000          return hsc($str);
1001      }
1002  }
1003  
1004  class WordLevelDiff extends MappedDiff {
1005  
1006      function __construct($orig_lines, $closing_lines) {
1007          list ($orig_words, $orig_stripped) = $this->_split($orig_lines);
1008          list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
1009  
1010          parent::__construct($orig_words, $closing_words, $orig_stripped, $closing_stripped);
1011      }
1012  
1013      function _split($lines) {
1014          if (!preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xsu',
1015               implode("\n", $lines), $m)) {
1016              return array(array(''), array(''));
1017          }
1018          return array($m[0], $m[1]);
1019      }
1020  
1021      function orig() {
1022          $orig = new _HWLDF_WordAccumulator;
1023  
1024          foreach ($this->edits as $edit) {
1025              if ($edit->type == 'copy')
1026                  $orig->addWords($edit->orig);
1027              elseif ($edit->orig)
1028                  $orig->addWords($edit->orig, 'mark');
1029          }
1030          return $orig->getLines();
1031      }
1032  
1033      function closing() {
1034          $closing = new _HWLDF_WordAccumulator;
1035  
1036          foreach ($this->edits as $edit) {
1037              if ($edit->type == 'copy')
1038                  $closing->addWords($edit->closing);
1039              elseif ($edit->closing)
1040                  $closing->addWords($edit->closing, 'mark');
1041          }
1042          return $closing->getLines();
1043      }
1044  }
1045  
1046  class InlineWordLevelDiff extends MappedDiff {
1047  
1048      function __construct($orig_lines, $closing_lines) {
1049          list ($orig_words, $orig_stripped) = $this->_split($orig_lines);
1050          list ($closing_words, $closing_stripped) = $this->_split($closing_lines);
1051  
1052          parent::__construct($orig_words, $closing_words, $orig_stripped, $closing_stripped);
1053      }
1054  
1055      function _split($lines) {
1056          if (!preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xsu',
1057               implode("\n", $lines), $m)) {
1058              return array(array(''), array(''));
1059          }
1060          return array($m[0], $m[1]);
1061      }
1062  
1063      function inline() {
1064          $orig = new _HWLDF_WordAccumulator;
1065          foreach ($this->edits as $edit) {
1066              if ($edit->type == 'copy')
1067                  $orig->addWords($edit->closing);
1068              elseif ($edit->type == 'change'){
1069                  $orig->addWords($edit->orig, 'del');
1070                  $orig->addWords($edit->closing, 'add');
1071              } elseif ($edit->type == 'delete')
1072                  $orig->addWords($edit->orig, 'del');
1073              elseif ($edit->type == 'add')
1074                  $orig->addWords($edit->closing, 'add');
1075              elseif ($edit->orig)
1076                  $orig->addWords($edit->orig, 'del');
1077          }
1078          return $orig->getLines();
1079      }
1080  }
1081  
1082  /**
1083   * "Unified" diff formatter.
1084   *
1085   * This class formats the diff in classic "unified diff" format.
1086   *
1087   * NOTE: output is plain text and unsafe for use in HTML without escaping.
1088   */
1089  class UnifiedDiffFormatter extends DiffFormatter {
1090  
1091      function __construct($context_lines = 4) {
1092          $this->leading_context_lines = $context_lines;
1093          $this->trailing_context_lines = $context_lines;
1094      }
1095  
1096      function _block_header($xbeg, $xlen, $ybeg, $ylen) {
1097          if ($xlen != 1)
1098              $xbeg .= "," . $xlen;
1099          if ($ylen != 1)
1100              $ybeg .= "," . $ylen;
1101          return "@@ -$xbeg +$ybeg @@\n";
1102      }
1103  
1104      function _added($lines) {
1105          $this->_lines($lines, "+");
1106      }
1107      function _deleted($lines) {
1108          $this->_lines($lines, "-");
1109      }
1110      function _changed($orig, $final) {
1111          $this->_deleted($orig);
1112          $this->_added($final);
1113      }
1114  }
1115  
1116  /**
1117   *  Wikipedia Table style diff formatter.
1118   *
1119   */
1120  class TableDiffFormatter extends DiffFormatter {
1121      var $colspan = 2;
1122  
1123      function __construct() {
1124          $this->leading_context_lines = 2;
1125          $this->trailing_context_lines = 2;
1126      }
1127  
1128      /**
1129       * @param Diff $diff
1130       * @return string
1131       */
1132      function format($diff) {
1133          // Preserve whitespaces by converting some to non-breaking spaces.
1134          // Do not convert all of them to allow word-wrap.
1135          $val = parent::format($diff);
1136          $val = str_replace('  ','&#160; ', $val);
1137          $val = preg_replace('/ (?=<)|(?<=[ >]) /', '&#160;', $val);
1138          return $val;
1139      }
1140  
1141      function _pre($text){
1142          $text = htmlspecialchars($text);
1143          return $text;
1144      }
1145  
1146      function _block_header($xbeg, $xlen, $ybeg, $ylen) {
1147          global $lang;
1148          $l1 = $lang['line'].' '.$xbeg;
1149          $l2 = $lang['line'].' '.$ybeg;
1150          $r = '<tr><td '.HTMLDiff::css('diff-blockheader').' colspan="'.$this->colspan.'">'.$l1.":</td>\n".
1151               '<td '.HTMLDiff::css('diff-blockheader').' colspan="'.$this->colspan.'">'.$l2.":</td>\n".
1152               "</tr>\n";
1153          return $r;
1154      }
1155  
1156      function _start_block($header) {
1157          print($header);
1158      }
1159  
1160      function _end_block() {
1161      }
1162  
1163      function _lines($lines, $prefix=' ', $color="white") {
1164      }
1165  
1166      function addedLine($line,$escaped=false) {
1167          if (!$escaped){
1168              $line = $this->_escape($line);
1169          }
1170          return '<td '.HTMLDiff::css('diff-lineheader').'>+</td>'.
1171                 '<td '.HTMLDiff::css('diff-addedline').'>' .  $line.'</td>';
1172      }
1173  
1174      function deletedLine($line,$escaped=false) {
1175          if (!$escaped){
1176              $line = $this->_escape($line);
1177          }
1178          return '<td '.HTMLDiff::css('diff-lineheader').'>-</td>'.
1179                 '<td '.HTMLDiff::css('diff-deletedline').'>' .  $line.'</td>';
1180      }
1181  
1182      function emptyLine() {
1183          return '<td colspan="'.$this->colspan.'">&#160;</td>';
1184      }
1185  
1186      function contextLine($line) {
1187          return '<td '.HTMLDiff::css('diff-lineheader').'>&#160;</td>'.
1188                 '<td '.HTMLDiff::css('diff-context').'>'.$this->_escape($line).'</td>';
1189      }
1190  
1191      function _added($lines) {
1192          $this->_addedLines($lines,false);
1193      }
1194  
1195      function _addedLines($lines,$escaped=false){
1196          foreach ($lines as $line) {
1197              print('<tr>' . $this->emptyLine() . $this->addedLine($line,$escaped) . "</tr>\n");
1198          }
1199      }
1200  
1201      function _deleted($lines) {
1202          foreach ($lines as $line) {
1203              print('<tr>' . $this->deletedLine($line) . $this->emptyLine() . "</tr>\n");
1204          }
1205      }
1206  
1207      function _context($lines) {
1208          foreach ($lines as $line) {
1209              print('<tr>' . $this->contextLine($line) .  $this->contextLine($line) . "</tr>\n");
1210          }
1211      }
1212  
1213      function _changed($orig, $closing) {
1214          $diff = new WordLevelDiff($orig, $closing);  // this escapes the diff data
1215          $del = $diff->orig();
1216          $add = $diff->closing();
1217  
1218          while ($line = array_shift($del)) {
1219              $aline = array_shift($add);
1220              print('<tr>' . $this->deletedLine($line,true) . $this->addedLine($aline,true) . "</tr>\n");
1221          }
1222          $this->_addedLines($add,true); # If any leftovers
1223      }
1224  
1225      function _escape($str) {
1226          return hsc($str);
1227      }
1228  }
1229  
1230  /**
1231   *  Inline style diff formatter.
1232   *
1233   */
1234  class InlineDiffFormatter extends DiffFormatter {
1235      var $colspan = 2;
1236  
1237      function __construct() {
1238          $this->leading_context_lines = 2;
1239          $this->trailing_context_lines = 2;
1240      }
1241  
1242      /**
1243       * @param Diff $diff
1244       * @return string
1245       */
1246      function format($diff) {
1247          // Preserve whitespaces by converting some to non-breaking spaces.
1248          // Do not convert all of them to allow word-wrap.
1249          $val = parent::format($diff);
1250          $val = str_replace('  ','&#160; ', $val);
1251          $val = preg_replace('/ (?=<)|(?<=[ >]) /', '&#160;', $val);
1252          return $val;
1253      }
1254  
1255      function _pre($text){
1256          $text = htmlspecialchars($text);
1257          return $text;
1258      }
1259  
1260      function _block_header($xbeg, $xlen, $ybeg, $ylen) {
1261          global $lang;
1262          if ($xlen != 1)
1263              $xbeg .= "," . $xlen;
1264          if ($ylen != 1)
1265              $ybeg .= "," . $ylen;
1266          $r = '<tr><td colspan="'.$this->colspan.'" '.HTMLDiff::css('diff-blockheader').'>@@ '.$lang['line']." -$xbeg +$ybeg @@";
1267          $r .= ' <span '.HTMLDiff::css('diff-deletedline').'><del>'.$lang['deleted'].'</del></span>';
1268          $r .= ' <span '.HTMLDiff::css('diff-addedline').'>'.$lang['created'].'</span>';
1269          $r .= "</td></tr>\n";
1270          return $r;
1271      }
1272  
1273      function _start_block($header) {
1274          print($header."\n");
1275      }
1276  
1277      function _end_block() {
1278      }
1279  
1280      function _lines($lines, $prefix=' ', $color="white") {
1281      }
1282  
1283      function _added($lines) {
1284          foreach ($lines as $line) {
1285              print('<tr><td '.HTMLDiff::css('diff-lineheader').'>&#160;</td><td '.HTMLDiff::css('diff-addedline').'>'. $this->_escape($line) . "</td></tr>\n");
1286          }
1287      }
1288  
1289      function _deleted($lines) {
1290          foreach ($lines as $line) {
1291              print('<tr><td '.HTMLDiff::css('diff-lineheader').'>&#160;</td><td '.HTMLDiff::css('diff-deletedline').'><del>' . $this->_escape($line) . "</del></td></tr>\n");
1292          }
1293      }
1294  
1295      function _context($lines) {
1296          foreach ($lines as $line) {
1297              print('<tr><td '.HTMLDiff::css('diff-lineheader').'>&#160;</td><td '.HTMLDiff::css('diff-context').'>'. $this->_escape($line) ."</td></tr>\n");
1298          }
1299      }
1300  
1301      function _changed($orig, $closing) {
1302          $diff = new InlineWordLevelDiff($orig, $closing);  // this escapes the diff data
1303          $add = $diff->inline();
1304  
1305          foreach ($add as $line)
1306              print('<tr><td '.HTMLDiff::css('diff-lineheader').'>&#160;</td><td>'.$line."</td></tr>\n");
1307      }
1308  
1309      function _escape($str) {
1310          return hsc($str);
1311      }
1312  }
1313  
1314  /**
1315   * A class for computing three way diffs.
1316   *
1317   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1318   */
1319  class Diff3 extends Diff {
1320  
1321      /**
1322       * Conflict counter.
1323       *
1324       * @var integer
1325       */
1326      var $_conflictingBlocks = 0;
1327  
1328      /**
1329       * Computes diff between 3 sequences of strings.
1330       *
1331       * @param array $orig    The original lines to use.
1332       * @param array $final1  The first version to compare to.
1333       * @param array $final2  The second version to compare to.
1334       */
1335      function __construct($orig, $final1, $final2) {
1336          $engine = new _DiffEngine();
1337  
1338          $this->_edits = $this->_diff3($engine->diff($orig, $final1),
1339                                        $engine->diff($orig, $final2));
1340      }
1341  
1342      /**
1343       * Returns the merged lines
1344       *
1345       * @param string $label1  label for first version
1346       * @param string $label2  label for second version
1347       * @param string $label3  separator between versions
1348       * @return array          lines of the merged text
1349       */
1350      function mergedOutput($label1='<<<<<<<',$label2='>>>>>>>',$label3='=======') {
1351          $lines = array();
1352          foreach ($this->_edits as $edit) {
1353              if ($edit->isConflict()) {
1354                  /* FIXME: this should probably be moved somewhere else. */
1355                  $lines = array_merge($lines,
1356                                       array($label1),
1357                                       $edit->final1,
1358                                       array($label3),
1359                                       $edit->final2,
1360                                       array($label2));
1361                  $this->_conflictingBlocks++;
1362              } else {
1363                  $lines = array_merge($lines, $edit->merged());
1364              }
1365          }
1366  
1367          return $lines;
1368      }
1369  
1370      /**
1371       * @access private
1372       *
1373       * @param array $edits1
1374       * @param array $edits2
1375       *
1376       * @return array
1377       */
1378      function _diff3($edits1, $edits2) {
1379          $edits = array();
1380          $bb = new _Diff3_BlockBuilder();
1381  
1382          $e1 = current($edits1);
1383          $e2 = current($edits2);
1384          while ($e1 || $e2) {
1385              if ($e1 && $e2 && is_a($e1, '_DiffOp_copy') && is_a($e2, '_DiffOp_copy')) {
1386                  /* We have copy blocks from both diffs. This is the (only)
1387                   * time we want to emit a diff3 copy block.  Flush current
1388                   * diff3 diff block, if any. */
1389                  if ($edit = $bb->finish()) {
1390                      $edits[] = $edit;
1391                  }
1392  
1393                  $ncopy = min($e1->norig(), $e2->norig());
1394                  assert($ncopy > 0);
1395                  $edits[] = new _Diff3_Op_copy(array_slice($e1->orig, 0, $ncopy));
1396  
1397                  if ($e1->norig() > $ncopy) {
1398                      array_splice($e1->orig, 0, $ncopy);
1399                      array_splice($e1->closing, 0, $ncopy);
1400                  } else {
1401                      $e1 = next($edits1);
1402                  }
1403  
1404                  if ($e2->norig() > $ncopy) {
1405                      array_splice($e2->orig, 0, $ncopy);
1406                      array_splice($e2->closing, 0, $ncopy);
1407                  } else {
1408                      $e2 = next($edits2);
1409                  }
1410              } else {
1411                  if ($e1 && $e2) {
1412                      if ($e1->orig && $e2->orig) {
1413                          $norig = min($e1->norig(), $e2->norig());
1414                          $orig = array_splice($e1->orig, 0, $norig);
1415                          array_splice($e2->orig, 0, $norig);
1416                          $bb->input($orig);
1417                      }
1418  
1419                      if (is_a($e1, '_DiffOp_copy')) {
1420                          $bb->out1(array_splice($e1->closing, 0, $norig));
1421                      }
1422  
1423                      if (is_a($e2, '_DiffOp_copy')) {
1424                          $bb->out2(array_splice($e2->closing, 0, $norig));
1425                      }
1426                  }
1427  
1428                  if ($e1 && ! $e1->orig) {
1429                      $bb->out1($e1->closing);
1430                      $e1 = next($edits1);
1431                  }
1432                  if ($e2 && ! $e2->orig) {
1433                      $bb->out2($e2->closing);
1434                      $e2 = next($edits2);
1435                  }
1436              }
1437          }
1438  
1439          if ($edit = $bb->finish()) {
1440              $edits[] = $edit;
1441          }
1442  
1443          return $edits;
1444      }
1445  }
1446  
1447  /**
1448   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1449   *
1450   * @access private
1451   */
1452  class _Diff3_Op {
1453  
1454      /** @var array|mixed */
1455      protected $orig;
1456  
1457      /** @var array|mixed */
1458      protected $final1;
1459  
1460      /** @var array|mixed */
1461      protected $final2;
1462  
1463      /** @var array|mixed|false */
1464      protected $_merged;
1465  
1466      function __construct($orig = false, $final1 = false, $final2 = false) {
1467          $this->orig = $orig ? $orig : array();
1468          $this->final1 = $final1 ? $final1 : array();
1469          $this->final2 = $final2 ? $final2 : array();
1470      }
1471  
1472      function merged() {
1473          if (!isset($this->_merged)) {
1474              if ($this->final1 === $this->final2) {
1475                  $this->_merged = &$this->final1;
1476              } elseif ($this->final1 === $this->orig) {
1477                  $this->_merged = &$this->final2;
1478              } elseif ($this->final2 === $this->orig) {
1479                  $this->_merged = &$this->final1;
1480              } else {
1481                  $this->_merged = false;
1482              }
1483          }
1484  
1485          return $this->_merged;
1486      }
1487  
1488      function isConflict() {
1489          return $this->merged() === false;
1490      }
1491  
1492  }
1493  
1494  /**
1495   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1496   *
1497   * @access private
1498   */
1499  class _Diff3_Op_copy extends _Diff3_Op {
1500  
1501      function __construct($lines = false) {
1502          $this->orig = $lines ? $lines : array();
1503          $this->final1 = &$this->orig;
1504          $this->final2 = &$this->orig;
1505      }
1506  
1507      function merged() {
1508          return $this->orig;
1509      }
1510  
1511      function isConflict() {
1512          return false;
1513      }
1514  }
1515  
1516  /**
1517   * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
1518   *
1519   * @access private
1520   */
1521  class _Diff3_BlockBuilder {
1522  
1523      function __construct() {
1524          $this->_init();
1525      }
1526  
1527      function input($lines) {
1528          if ($lines) {
1529              $this->_append($this->orig, $lines);
1530          }
1531      }
1532  
1533      function out1($lines) {
1534          if ($lines) {
1535              $this->_append($this->final1, $lines);
1536          }
1537      }
1538  
1539      function out2($lines) {
1540          if ($lines) {
1541              $this->_append($this->final2, $lines);
1542          }
1543      }
1544  
1545      function isEmpty() {
1546          return !$this->orig && !$this->final1 && !$this->final2;
1547      }
1548  
1549      function finish() {
1550          if ($this->isEmpty()) {
1551              return false;
1552          } else {
1553              $edit = new _Diff3_Op($this->orig, $this->final1, $this->final2);
1554              $this->_init();
1555              return $edit;
1556          }
1557      }
1558  
1559      function _init() {
1560          $this->orig = $this->final1 = $this->final2 = array();
1561      }
1562  
1563      function _append(&$array, $lines) {
1564          array_splice($array, sizeof($array), 0, $lines);
1565      }
1566  }
1567  
1568  //Setup VIM: ex: et ts=4 :