inc/DifferenceEngine.php

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