lib/diff.php

   1 <?php
   2 rcs_id('$Id: diff.php,v 1.13 2001-09-18 19:16:23 dairiki Exp $');
   3 // diff.php
   4 //
   5 // A PHP diff engine for phpwiki.
   6 //
   7 // Copyright (C) 2000 Geoffrey T. Dairiki <dairiki@dairiki.org>
   8 // You may copy this code freely under the conditions of the GPL.
   9 //
  10
  11 // FIXME: possibly remove assert()'s for production version?
  12
  13 // PHP3 does not have assert()
  14 define('USE_ASSERTS', function_exists('assert'));
  15
  16
  17 /**
  18  * Class used internally by WikiDiff to actually compute the diffs.
  19  *
  20  * The algorithm used here is mostly lifted from the perl module
  21  * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
  22  *   http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
  23  *
  24  * More ideas are taken from:
  25  *   http://www.ics.uci.edu/~eppstein/161/960229.html
  26  *
  27  * Some ideas are (and a bit of code) are from from analyze.c, from GNU
  28  * diffutils-2.7, which can be found at:
  29  *   ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
  30  *
  31  * Finally, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
  32  * are my own.
  33  */
  34 class _WikiDiffEngine
  35 {
  36   var $edits;   // List of editing operation to convert XV to YV.
  37   var $xv = array(), $yv = array();
  38
  39   function _WikiDiffEngine ($from_lines, $to_lines)
  40       {
  41         $n_from = sizeof($from_lines);
  42         $n_to = sizeof($to_lines);
  43         $endskip = 0;
  44
  45         // Ignore trailing and leading matching lines.
  46         while ($n_from > 0 && $n_to > 0)
  47           {
  48             if ($from_lines[$n_from - 1] != $to_lines[$n_to - 1])
  49                 break;
  50             $n_from--;
  51             $n_to--;
  52             $endskip++;
  53           }
  54         for ( $skip = 0; $skip < min($n_from, $n_to); $skip++)
  55             if ($from_lines[$skip] != $to_lines[$skip])
  56                 break;
  57         $n_from -= $skip;
  58         $n_to -= $skip;
  59
  60         $xlines = array();
  61         $ylines = array();
  62         $this->xchanged = array();
  63         $this->ychanged = array();
  64
  65         // Ignore lines which do not exist in both files.
  66         for ($x = 0; $x < $n_from; $x++)
  67             $xhash[$from_lines[$x + $skip]] = 1;
  68         for ($y = 0; $y < $n_to; $y++)
  69           {
  70             $line = $to_lines[$y + $skip];
  71             $ylines[] = $line;
  72             if ( ($this->ychanged[$y] = empty($xhash[$line])) )
  73                 continue;
  74             $yhash[$line] = 1;
  75             $this->yv[] = $line;
  76             $this->yind[] = $y;
  77           }
  78         for ($x = 0; $x < $n_from; $x++)
  79           {
  80             $line = $from_lines[$x + $skip];
  81             $xlines[] = $line;
  82             if ( ($this->xchanged[$x] = empty($yhash[$line])) )
  83                 continue;
  84             $this->xv[] = $line;
  85             $this->xind[] = $x;
  86           }
  87
  88         // Find the LCS.
  89         $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
  90
  91         // Merge edits when possible
  92         $this->_shift_boundaries($xlines, $this->xchanged, $this->ychanged);
  93         $this->_shift_boundaries($ylines, $this->ychanged, $this->xchanged);
  94
  95         // Compute the edit operations.
  96         $this->edits = array();
  97         if ($skip)
  98             $this->edits[] = $skip;
  99
 100         $x = 0;
 101         $y = 0;
 102         while ($x < $n_from || $y < $n_to)
 103           {
 104             USE_ASSERTS && assert($y < $n_to || $this->xchanged[$x]);
 105             USE_ASSERTS && assert($x < $n_from || $this->ychanged[$y]);
 106
 107             // Skip matching "snake".
 108             $x0 = $x;
 109             $ncopy = 0;
 110
 111             while ( $x < $n_from && $y < $n_to
 112                     && !$this->xchanged[$x] && !$this->ychanged[$y])
 113               {
 114                 ++$x;
 115                 ++$y;
 116                 ++$ncopy;
 117               }
 118             if ($x > $x0)
 119                 $this->edits[] = $x - $x0;
 120
 121             // Find deletes.
 122             $x0 = $x;
 123             $ndelete = 0;
 124             while ($x < $n_from && $this->xchanged[$x])
 125               {
 126                 ++$x;
 127                 ++$ndelete;
 128               }
 129             if ($x > $x0)
 130                 $this->edits[] = -($x - $x0);
 131
 132             // Find adds.
 133             if (!empty($this->ychanged[$y]))
 134               {
 135                 $adds = array();
 136                 while ($y < $n_to && $this->ychanged[$y])
 137                     $adds[] = "" . $ylines[$y++];
 138                 $this->edits[] = $adds;
 139               }
 140           }
 141         if ($endskip != 0)
 142             $this->edits[] = $endskip;
 143       }
 144
 145   /* Divide the Largest Common Subsequence (LCS) of the sequences
 146    * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
 147    * sized segments.
 148    *
 149    * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an
 150    * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
 151    * sub sequences.  The first sub-sequence is contained in [X0, X1),
 152    * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on.  Note
 153    * that (X0, Y0) == (XOFF, YOFF) and
 154    * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
 155    *
 156    * This function assumes that the first lines of the specified portions
 157    * of the two files do not match, and likewise that the last lines do not
 158    * match.  The caller must trim matching lines from the beginning and end
 159    * of the portions it is going to specify.
 160    */
 161   function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks)
 162       {
 163         $flip = false;
 164
 165         if ($xlim - $xoff > $ylim - $yoff)
 166           {
 167             // Things seems faster (I'm not sure I understand why)
 168             // when the shortest sequence in X.
 169             $flip = true;
 170             list ($xoff, $xlim, $yoff, $ylim)
 171                 = array( $yoff, $ylim, $xoff, $xlim);
 172           }
 173
 174         if ($flip)
 175             for ($i = $ylim - 1; $i >= $yoff; $i--)
 176                 $ymatches[$this->xv[$i]][] = $i;
 177         else
 178             for ($i = $ylim - 1; $i >= $yoff; $i--)
 179                 $ymatches[$this->yv[$i]][] = $i;
 180
 181         $this->lcs = 0;
 182         $this->seq[0]= $yoff - 1;
 183         $this->in_seq = array();
 184         $ymids[0] = array();
 185
 186         $numer = $xlim - $xoff + $nchunks - 1;
 187         $x = $xoff;
 188         for ($chunk = 0; $chunk < $nchunks; $chunk++)
 189           {
 190             if ($chunk > 0)
 191                 for ($i = 0; $i <= $this->lcs; $i++)
 192                     $ymids[$i][$chunk-1] = $this->seq[$i];
 193
 194             $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
 195             for ( ; $x < $x1; $x++)
 196               {
 197                 $matches = $ymatches[$flip ? $this->yv[$x] : $this->xv[$x]];
 198                 if (!$matches)
 199                     continue;
 200                 reset($matches);
 201                 while (list ($junk, $y) = each($matches))
 202                     if (empty($this->in_seq[$y]))
 203                       {
 204                         $k = $this->_lcs_pos($y);
 205                         USE_ASSERTS && assert($k > 0);
 206                         $ymids[$k] = $ymids[$k-1];
 207                         break;
 208                       }
 209                 while (list ($junk, $y) = each($matches))
 210                   {
 211                     if ($y > $this->seq[$k-1])
 212                       {
 213                         USE_ASSERTS && assert($y < $this->seq[$k]);
 214                         // Optimization: this is a common case:
 215                         //  next match is just replacing previous match.
 216                         $this->in_seq[$this->seq[$k]] = false;
 217                         $this->seq[$k] = $y;
 218                         $this->in_seq[$y] = 1;
 219                       }
 220                     else if (empty($this->in_seq[$y]))
 221                       {
 222                         $k = $this->_lcs_pos($y);
 223                         USE_ASSERTS && assert($k > 0);
 224                         $ymids[$k] = $ymids[$k-1];
 225                       }
 226                   }
 227               }
 228           }
 229
 230         $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
 231         $ymid = $ymids[$this->lcs];
 232         for ($n = 0; $n < $nchunks - 1; $n++)
 233           {
 234             $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
 235             $y1 = $ymid[$n] + 1;
 236             $seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
 237           }
 238         $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
 239
 240         return array($this->lcs, $seps);
 241       }
 242
 243   function _lcs_pos ($ypos)
 244       {
 245         $end = $this->lcs;
 246         if ($end == 0 || $ypos > $this->seq[$end])
 247           {
 248             $this->seq[++$this->lcs] = $ypos;
 249             $this->in_seq[$ypos] = 1;
 250             return $this->lcs;
 251           }
 252
 253         $beg = 1;
 254         while ($beg < $end)
 255           {
 256             $mid = (int)(($beg + $end) / 2);
 257             if ( $ypos > $this->seq[$mid] )
 258                 $beg = $mid + 1;
 259             else
 260                 $end = $mid;
 261           }
 262
 263         USE_ASSERTS && assert($ypos != $this->seq[$end]);
 264
 265         $this->in_seq[$this->seq[$end]] = false;
 266         $this->seq[$end] = $ypos;
 267         $this->in_seq[$ypos] = 1;
 268         return $end;
 269       }
 270
 271   /* Find LCS of two sequences.
 272    *
 273    * The results are recorded in the vectors $this->{x,y}changed[], by
 274    * storing a 1 in the element for each line that is an insertion
 275    * or deletion (ie. is not in the LCS).
 276    *
 277    * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
 278    *
 279    * Note that XLIM, YLIM are exclusive bounds.
 280    * All line numbers are origin-0 and discarded lines are not counted.
 281    */
 282   function _compareseq ($xoff, $xlim, $yoff, $ylim)
 283       {
 284         // Slide down the bottom initial diagonal.
 285         while ($xoff < $xlim && $yoff < $ylim
 286         && $this->xv[$xoff] == $this->yv[$yoff])
 287           {
 288             ++$xoff;
 289             ++$yoff;
 290           }
 291
 292         // Slide up the top initial diagonal.
 293         while ($xlim > $xoff && $ylim > $yoff
 294         && $this->xv[$xlim - 1] == $this->yv[$ylim - 1])
 295           {
 296             --$xlim;
 297             --$ylim;
 298           }
 299
 300         if ($xoff == $xlim || $yoff == $ylim)
 301             $lcs = 0;
 302         else
 303           {
 304             // This is ad hoc but seems to work well.
 305             //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
 306             //$nchunks = max(2,min(8,(int)$nchunks));
 307             $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
 308             list ($lcs, $seps)
 309                 = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks);
 310           }
 311
 312         if ($lcs == 0)
 313           {
 314             // X and Y sequences have no common subsequence:
 315             // mark all changed.
 316             while ($yoff < $ylim)
 317                 $this->ychanged[$this->yind[$yoff++]] = 1;
 318             while ($xoff < $xlim)
 319                 $this->xchanged[$this->xind[$xoff++]] = 1;
 320           }
 321         else
 322           {
 323             // Use the partitions to split this problem into subproblems.
 324             reset($seps);
 325             $pt1 = $seps[0];
 326             while ($pt2 = next($seps))
 327               {
 328                 $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
 329                 $pt1 = $pt2;
 330               }
 331           }
 332       }
 333
 334   /* Adjust inserts/deletes of identical lines to join changes
 335    * as much as possible.
 336    *
 337    * We do something when a run of changed lines include a
 338    * line at one end and has an excluded, identical line at the other.
 339    * We are free to choose which identical line is included.
 340    * `compareseq' usually chooses the one at the beginning,
 341    * but usually it is cleaner to consider the following identical line
 342    * to be the "change".
 343    *
 344    * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
 345    */
 346   function _shift_boundaries ($lines, &$changed, $other_changed)
 347       {
 348         $i = 0;
 349         $j = 0;
 350
 351         USE_ASSERTS && assert('sizeof($lines) == sizeof($changed)');
 352         $len = sizeof($lines);
 353         $other_len = sizeof($other_changed);
 354
 355         while (1)
 356           {
 357             /*
 358              * Scan forwards to find beginning of another run of changes.
 359              * Also keep track of the corresponding point in the other file.
 360              *
 361              * Throughout this code, $i and $j are adjusted together so that
 362              * the first $i elements of $changed and the first $j elements
 363              * of $other_changed both contain the same number of zeros
 364              * (unchanged lines).
 365              * Furthermore, $j is always kept so that $j == $other_len or
 366              * $other_changed[$j] == false.
 367              */
 368             while ($j < $other_len && $other_changed[$j])
 369                 $j++;
 370
 371             while ($i < $len && ! $changed[$i])
 372               {
 373                 USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
 374                 $i++; $j++;
 375                 while ($j < $other_len && $other_changed[$j])
 376                     $j++;
 377               }
 378
 379             if ($i == $len)
 380                 break;
 381
 382             $start = $i;
 383
 384             // Find the end of this run of changes.
 385             while (++$i < $len && $changed[$i])
 386                 continue;
 387
 388             do
 389               {
 390                 /*
 391                  * Record the length of this run of changes, so that
 392                  * we can later determine whether the run has grown.
 393                  */
 394                 $runlength = $i - $start;
 395
 396                 /*
 397                  * Move the changed region back, so long as the
 398                  * previous unchanged line matches the last changed one.
 399                  * This merges with previous changed regions.
 400                  */
 401                 while ($start > 0 && $lines[$start - 1] == $lines[$i - 1])
 402                   {
 403                     $changed[--$start] = 1;
 404                     $changed[--$i] = false;
 405                     while ($start > 0 && $changed[$start - 1])
 406                         $start--;
 407                     USE_ASSERTS && assert('$j > 0');
 408                     while ($other_changed[--$j])
 409                         continue;
 410                     USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
 411                   }
 412
 413                 /*
 414                  * Set CORRESPONDING to the end of the changed run, at the last
 415                  * point where it corresponds to a changed run in the other file.
 416                  * CORRESPONDING == LEN means no such point has been found.
 417                  */
 418                 $corresponding = $j < $other_len ? $i : $len;
 419
 420                 /*
 421                  * Move the changed region forward, so long as the
 422                  * first changed line matches the following unchanged one.
 423                  * This merges with following changed regions.
 424                  * Do this second, so that if there are no merges,
 425                  * the changed region is moved forward as far as possible.
 426                  */
 427                 while ($i < $len && $lines[$start] == $lines[$i])
 428                   {
 429                     $changed[$start++] = false;
 430                     $changed[$i++] = 1;
 431                     while ($i < $len && $changed[$i])
 432                         $i++;
 433
 434                     USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
 435                     $j++;
 436                     if ($j < $other_len && $other_changed[$j])
 437                       {
 438                         $corresponding = $i;
 439                         while ($j < $other_len && $other_changed[$j])
 440                             $j++;
 441                       }
 442                   }
 443               }
 444             while ($runlength != $i - $start);
 445
 446             /*
 447              * If possible, move the fully-merged run of changes
 448              * back to a corresponding run in the other file.
 449              */
 450             while ($corresponding < $i)
 451               {
 452                 $changed[--$start] = 1;
 453                 $changed[--$i] = 0;
 454                 USE_ASSERTS && assert('$j > 0');
 455                 while ($other_changed[--$j])
 456                     continue;
 457                 USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
 458               }
 459           }
 460       }
 461 }
 462
 463 /**
 464  * Class representing a diff between two files.
 465  */
 466 class WikiDiff
 467 {
 468   var $edits;
 469
 470   /**
 471    * Compute diff between files (or deserialize serialized WikiDiff.)
 472    */
 473   function WikiDiff($from_lines = false, $to_lines = false)
 474       {
 475         if ($from_lines && $to_lines)
 476           {
 477             $compute = new _WikiDiffEngine($from_lines, $to_lines);
 478             $this->edits = $compute->edits;
 479           }
 480         else if ($from_lines)
 481           {
 482             // $from_lines is not really from_lines, but rather
 483             // a serialized WikiDiff.
 484             $this->edits = unserialize($from_lines);
 485           }
 486         else
 487           {
 488             $this->edits = array();
 489           }
 490       }
 491
 492   /**
 493    * Compute reversed WikiDiff.
 494    *
 495    * SYNOPSIS:
 496    *
 497    *  $diff = new WikiDiff($lines1, $lines2);
 498    *  $rev = $diff->reverse($lines1);
 499    *
 500    *  // reconstruct $lines1 from $lines2:
 501    *  $out = $rev->apply($lines2);
 502    */
 503   function reverse ($from_lines)
 504       {
 505         $x = 0;
 506         $rev = new WikiDiff;
 507
 508         for ( reset($this->edits);
 509               $edit = current($this->edits);
 510               next($this->edits) )
 511           {
 512             if (is_array($edit))
 513               { // Was an add, turn it into a delete.
 514                 $nadd = sizeof($edit);
 515                 USE_ASSERTS && assert ($nadd > 0);
 516                 $edit = -$nadd;
 517               }
 518             else if ($edit > 0)
 519               {
 520                 // Was a copy --- just pass it through.       }
 521                 $x += $edit;
 522               }
 523             else if ($edit < 0)
 524               { // Was a delete, turn it into an add.
 525                 $ndelete = -$edit;
 526                 $edit = array();
 527                 while ($ndelete-- > 0)
 528                     $edit[] = "" . $from_lines[$x++];
 529               }
 530             else
 531                 trigger_error("assertion error", E_USER_ERROR);
 532
 533             $rev->edits[] = $edit;
 534           }
 535
 536         return $rev;
 537       }
 538
 539   /**
 540    * Compose (concatenate) WikiDiffs.
 541    *
 542    * SYNOPSIS:
 543    *
 544    *  $diff1 = new WikiDiff($lines1, $lines2);
 545    *  $diff2 = new WikiDiff($lines2, $lines3);
 546    *  $comp = $diff1->compose($diff2);
 547    *
 548    *  // reconstruct $lines3 from $lines1:
 549    *  $out = $comp->apply($lines1);
 550    */
 551   function compose ($that)
 552       {
 553         reset($this->edits);
 554         reset($that->edits);
 555
 556         $comp = new WikiDiff;
 557         $left = current($this->edits);
 558         $right = current($that->edits);
 559
 560         while ($left || $right)
 561           {
 562             if (!is_array($left) && $left < 0)
 563               { // Left op is a delete.
 564                 $newop = $left;
 565                 $left = next($this->edits);
 566               }
 567             else if (is_array($right))
 568               { // Right op is an add.
 569                 $newop = $right;
 570                 $right = next($that->edits);
 571               }
 572             else if (!$left || !$right)
 573                 trigger_error("assertion error", E_USER_ERROR);
 574             else if (!is_array($left) && $left > 0)
 575               { // Left op is a copy.
 576                 if ($left <= abs($right))
 577                   {
 578                     $newop = $right > 0 ? $left : -$left;
 579                     $right -= $newop;
 580                     if ($right == 0)
 581                         $right = next($that->edits);
 582                     $left = next($this->edits);
 583                   }
 584                 else
 585                   {
 586                     $newop = $right;
 587                     $left -= abs($right);
 588                     $right = next($that->edits);
 589                   }
 590               }
 591             else
 592               { // Left op is an add.
 593                 assert('is_array($left)');
 594                 $nleft = sizeof($left);
 595                 if ($nleft <= abs($right))
 596                   {
 597                     if ($right > 0)
 598                       { // Right op is copy
 599                         $newop = $left;
 600                         $right -= $nleft;
 601                       }
 602                     else // Right op is delete
 603                       {
 604                         $newop = false;
 605                         $right += $nleft;
 606                       }
 607                     if ($right == 0)
 608                         $right = next($that->edits);
 609                     $left = next($this->edits);
 610                   }
 611                 else
 612                   {
 613                     unset($newop);
 614                     if ($right > 0)
 615                         for ($i = 0; $i < $right; $i++)
 616                             $newop[] = $left[$i];
 617
 618                     $tmp = array();
 619                     for ($i = abs($right); $i < $nleft; $i++)
 620                         $tmp[] = $left[$i];
 621                     $left = $tmp;
 622                     $right = next($that->edits);
 623                   }
 624               }
 625             if (!$op)
 626               {
 627                 $op = $newop;
 628                 continue;
 629               }
 630             if (! $newop)
 631                 continue;
 632
 633             if (is_array($op) && is_array($newop))
 634               {
 635                 // Both $op and $newop are adds.
 636                 for ($i = 0; $i < sizeof($newop); $i++)
 637                     $op[] = $newop[$i];
 638               }
 639             else if (($op > 0 && $newop > 0) || ($op < 0 && $newop < 0))
 640               { // $op and $newop are both either deletes or copies.
 641                 $op += $newop;
 642               }
 643             else
 644               {
 645                 $comp->edits[] = $op;
 646                 $op = $newop;
 647               }
 648           }
 649         if ($op)
 650             $comp->edits[] = $op;
 651
 652         return $comp;
 653       }
 654
 655   /* Debugging only:
 656   function _dump ()
 657       {
 658         echo "<ol>";
 659         for (reset($this->edits);
 660              $edit = current($this->edits);
 661              next($this->edits))
 662           {
 663             echo "<li>";
 664             if ($edit > 0)
 665                 echo "Copy $edit";
 666             else if ($edit < 0)
 667                 echo "Delete " . -$edit;
 668             else if (is_array($edit))
 669               {
 670                 echo "Add " . sizeof($edit) . "<ul>";
 671                 for ($i = 0; $i < sizeof($edit); $i++)
 672                     echo "<li>" . htmlspecialchars($edit[$i]);
 673                 echo "</ul>";
 674               }
 675             else
 676                 trigger_error("assertion error", E_USER_ERROR);
 677           }
 678         echo "</ol>";
 679       }
 680   */
 681
 682   /**
 683    * Apply a WikiDiff to a set of lines.
 684    *
 685    * SYNOPSIS:
 686    *
 687    *  $diff = new WikiDiff($lines1, $lines2);
 688    *
 689    *  // reconstruct $lines2 from $lines1:
 690    *  $out = $diff->apply($lines1);
 691    */
 692   function apply ($from_lines)
 693       {
 694         $x = 0;
 695         $xlim = sizeof($from_lines);
 696
 697         for ( reset($this->edits);
 698               $edit = current($this->edits);
 699               next($this->edits) )
 700           {
 701             if (is_array($edit))
 702               {
 703                 reset($edit);
 704                 while (list ($junk, $line) = each($edit))
 705                     $output[] = $line;
 706               }
 707             else if ($edit > 0)
 708                 while ($edit--)
 709                     $output[] = $from_lines[$x++];
 710             else
 711                 $x += -$edit;
 712           }
 713         if ($x != $xlim)
 714             ExitWiki(sprintf(gettext ("WikiDiff::apply: line count mismatch: %s != %s"), $x, $xlim));
 715         return $output;
 716       }
 717
 718   /**
 719    * Serialize a WikiDiff.
 720    *
 721    * SYNOPSIS:
 722    *
 723    *  $diff = new WikiDiff($lines1, $lines2);
 724    *  $string = $diff->serialize;
 725    *
 726    *  // recover WikiDiff from serialized version:
 727    *  $diff2 = new WikiDiff($string);
 728    */
 729   function serialize ()
 730       {
 731         return serialize($this->edits);
 732       }
 733
 734   /**
 735    * Return true if two files were equal.
 736    */
 737   function isEmpty ()
 738       {
 739         if (sizeof($this->edits) > 1)
 740             return false;
 741         if (sizeof($this->edits) == 0)
 742             return true;
 743         // Test for: only edit is a copy.
 744         return !is_array($this->edits[0]) && $this->edits[0] > 0;
 745       }
 746
 747   /**
 748    * Compute the length of the Longest Common Subsequence (LCS).
 749    *
 750    * This is mostly for diagnostic purposed.
 751    */
 752   function lcs ()
 753       {
 754         $lcs = 0;
 755         for (reset($this->edits);
 756              $edit = current($this->edits);
 757              next($this->edits))
 758           {
 759             if (!is_array($edit) && $edit > 0)
 760                 $lcs += $edit;
 761           }
 762         return $lcs;
 763       }
 764
 765   /**
 766    * Check a WikiDiff for validity.
 767    *
 768    * This is here only for debugging purposes.
 769    */
 770   function _check ($from_lines, $to_lines)
 771       {
 772         $test = $this->apply($from_lines);
 773         if (serialize($test) != serialize($to_lines))
 774             ExitWiki(gettext ("WikiDiff::_check: failed"));
 775
 776         reset($this->edits);
 777         $prev = current($this->edits);
 778         $prevtype = is_array($prev) ? 'a' : ($prev > 0 ? 'c' : 'd');
 779
 780         while ($edit = next($this->edits))
 781           {
 782             $type = is_array($edit) ? 'a' : ($edit > 0 ? 'c' : 'd');
 783             if ( $prevtype == $type )
 784                 ExitWiki(gettext ("WikiDiff::_check: edit sequence is non-optimal"));
 785             $prevtype = $type;
 786           }
 787         $lcs = $this->lcs();
 788         printf ("<strong>" . gettext ("WikiDiff Okay: LCS = %s") . "</strong>\n", $lcs);
 789       }
 790 }
 791
 792
 793 /**
 794  * A class to format a WikiDiff as HTML.
 795  *
 796  * Usage:
 797  *
 798  *   $diff = new WikiDiff($lines1, $lines2); // compute diff.
 799  *
 800  *   $fmt = new WikiDiffFormatter;
 801  *   echo $fmt->format($diff, $lines1); // Output HTMLified standard diff.
 802  *
 803  * or to output reverse diff (diff's that would take $lines2 to $lines1):
 804  *
 805  *   $fmt = new WikiDiffFormatter('reversed');
 806  *   echo $fmt->format($diff, $lines1);
 807  */
 808 class WikiDiffFormatter
 809 {
 810   var $context_lines;
 811   var $do_reverse_diff;
 812   var $context_prefix, $deletes_prefix, $adds_prefix;
 813
 814   function WikiDiffFormatter ($reverse = false)
 815       {
 816         $this->do_reverse_diff = $reverse;
 817         $this->context_lines = 0;
 818         $this->context_prefix = '&nbsp;&nbsp;';
 819         $this->deletes_prefix = '&lt;&nbsp;';
 820         $this->adds_prefix = '&gt;&nbsp;';
 821       }
 822
 823   function format ($diff, $from_lines)
 824       {
 825         return Element('table',
 826                        array('width' => '100%',
 827                              'bgcolor' => 'black',
 828                              'cellspacing' => 2,
 829                              'cellpadding' => 2,
 830                              'border' => 0),
 831                        $this->_format($diff->edits, $from_lines));
 832       }
 833
 834   function _format ($edits, $from_lines)
 835       {
 836         $rows = '';
 837         $x = 0; $y = 0;
 838         $xlim = sizeof($from_lines);
 839
 840         reset($edits);
 841         while ($edit = current($edits))
 842           {
 843             if (!is_array($edit) && $edit >= 0)
 844               { // Edit op is a copy.
 845                 $ncopy = $edit;
 846               }
 847             else
 848               {
 849                 $ncopy = 0;
 850                 if (empty($hunk))
 851                   {
 852                     // Start of an output hunk.
 853                     $xoff = max(0, $x - $this->context_lines);
 854                     $yoff = $xoff + $y - $x;
 855                     if ($xoff < $x)
 856                       {
 857                         // Get leading context.
 858                         $context = array();
 859                         for ($i = $xoff; $i < $x; $i++)
 860                             $context[] = $from_lines[$i];
 861                         $hunk['c'] = $context;
 862                       }
 863                   }
 864                 if (is_array($edit))
 865                   { // Edit op is an add.
 866                     $y += sizeof($edit);
 867                     $hunk[$this->do_reverse_diff ? 'd' : 'a'] = $edit;
 868                   }
 869                 else
 870                   { // Edit op is a delete
 871                     $deletes = array();
 872                     while ($edit++ < 0)
 873                         $deletes[] = $from_lines[$x++];
 874                     $hunk[$this->do_reverse_diff ? 'a' : 'd'] = $deletes;
 875                   }
 876               }
 877
 878             $next = next($edits);
 879             if (!empty($hunk))
 880               {
 881                 if ( !$next || $ncopy > 2 * $this->context_lines)
 882                   {
 883                     // End of an output hunk.
 884                     $hunks[] = $hunk;
 885                     unset($hunk);
 886
 887                     $xend = min($x + $this->context_lines, $xlim);
 888                     if ($x < $xend)
 889                       {
 890                         // Get trailing context.
 891                         $context = array();
 892                         for ($i = $x; $i < $xend; $i++)
 893                             $context[] = $from_lines[$i];
 894                         $hunks[] = array('c' => $context);
 895                       }
 896
 897                     $xlen = $xend - $xoff;
 898                     $ylen = $xend + $y - $x - $yoff;
 899                     $xbeg = $xlen ? $xoff + 1 : $xoff;
 900                     $ybeg = $ylen ? $yoff + 1 : $yoff;
 901
 902                     if ($this->do_reverse_diff)
 903                         list ($xbeg, $xlen, $ybeg, $ylen)
 904                             = array($ybeg, $ylen, $xbeg, $xlen);
 905
 906                     $rows .= $this->_emit_diff($xbeg,$xlen,$ybeg,$ylen, $hunks);
 907                     unset($hunks);
 908                   }
 909                 else if ($ncopy)
 910                   {
 911                     $hunks[] = $hunk;
 912
 913                     // Copy context.
 914                     $context = array();
 915                     for ($i = $x; $i < $x + $ncopy; $i++)
 916                         $context[] = $from_lines[$i];
 917                     $hunk = array('c' => $context);
 918                   }
 919               }
 920
 921             $x += $ncopy;
 922             $y += $ncopy;
 923           }
 924         return $rows;
 925       }
 926
 927   function _emit_lines($lines,  $prefix, $color)
 928       {
 929         $html = '';
 930         $prefix = Element('td', array('bgcolor' => '#cccccc', 'width' => "1%"), $prefix);
 931         reset($lines);
 932         while (list ($junk, $line) = each($lines))
 933           {
 934             $line = rtrim($line);
 935             $line = empty($line) ? '&nbsp;' : htmlspecialchars($line);
 936             $html .= Element('tr', array('valign' => 'top'),
 937                              $prefix . Element('td', array('bgcolor' => $color),
 938                                                Element('tt', $line)));
 939           }
 940         return $html;
 941       }
 942
 943   function _emit_diff ($xbeg,$xlen,$ybeg,$ylen,$hunks)
 944       {
 945         $header = Element('tr', array('bgcolor' => '#cccccc'),
 946                           Element('td', array('colspan' => 2),
 947                                   QElement('tt',
 948                                            $this->_diff_header($xbeg, $xlen, $ybeg, $ylen))));
 949
 950         $prefix = array('c' => $this->context_prefix,
 951                         'a' => $this->adds_prefix,
 952                         'd' => $this->deletes_prefix);
 953         $color = array('c' => '#ffffff',
 954                        'a' => '#ffcccc',
 955                        'd' => '#ccffcc');
 956
 957         $diff = '';
 958         for (reset($hunks); $hunk = current($hunks); next($hunks))
 959           {
 960             if (!empty($hunk['c']))
 961                 $diff .= $this->_emit_lines($hunk['c'],
 962                                             $this->context_prefix, '#ffffff');
 963             if (!empty($hunk['d']))
 964                 $diff .= $this->_emit_lines($hunk['d'],
 965                                             $this->deletes_prefix, '#ccffcc');
 966             if (!empty($hunk['a']))
 967                 $diff .= $this->_emit_lines($hunk['a'],
 968                                             $this->adds_prefix, '#ffcccc');
 969           }
 970
 971
 972         return Element('tr', Element('td',
 973                                      Element('table',
 974                                              array('width' => '100%',
 975                                                    'bgcolor' => 'white',
 976                                                    'cellspacing' => 0,
 977                                                    'cellpadding' => 1,
 978                                                    'border' => 0),
 979                                              $header. $diff)));
 980
 981       }
 982
 983   function _diff_header ($xbeg,$xlen,$ybeg,$ylen)
 984       {
 985         $what = $xlen ? ($ylen ? 'c' : 'd') : 'a';
 986         $xlen = $xlen > 1 ? "," . ($xbeg + $xlen - 1) : '';
 987         $ylen = $ylen > 1 ? "," . ($ybeg + $ylen - 1) : '';
 988
 989         return "$xbeg$xlen$what$ybeg$ylen";
 990       }
 991 }
 992
 993 /**
 994  * A class to format a WikiDiff as a pretty HTML unified diff.
 995  *
 996  * Usage:
 997  *
 998  *   $diff = new WikiDiff($lines1, $lines2); // compute diff.
 999  *
1000  *   $fmt = new WikiUnifiedDiffFormatter;
1001  *   echo $fmt->format($diff, $lines1); // Output HTMLified unified diff.
1002  */
1003 class WikiUnifiedDiffFormatter extends WikiDiffFormatter
1004 {
1005   function WikiUnifiedDiffFormatter ($reverse = false, $context_lines = 3)
1006       {
1007         $this->do_reverse_diff = $reverse;
1008         $this->context_lines = $context_lines;
1009         $this->context_prefix = '&nbsp;';
1010         $this->deletes_prefix = '-';
1011         $this->adds_prefix = '+';
1012       }
1013
1014   function _diff_header ($xbeg,$xlen,$ybeg,$ylen)
1015       {
1016         $xlen = $xlen == 1 ? '' : ",$xlen";
1017         $ylen = $ylen == 1 ? '' : ",$ylen";
1018
1019         return "@@ -$xbeg$xlen +$ybeg$ylen @@";
1020       }
1021 }
1022
1023
1024
1025 /////////////////////////////////////////////////////////////////
1026
1027 function PageInfoRow ($pagename, $label, $rev)
1028 {
1029    global $datetimeformat;
1030
1031    $cols = QElement('td', array('align' => 'right'), $label);
1032
1033    if ($rev) {
1034        $url = WikiURL($pagename, array('version' => $rev->getVersion()));
1035        $linked_version = QElement('a', array('href' => $url), $rev->getVersion());
1036        $cols .= Element('td',
1037                         gettext("version") . " " . $linked_version);
1038
1039        $cols .= QElement('td',
1040                          sprintf(gettext ("last modified on %s"),
1041                                  strftime($datetimeformat, $rev->get('mtime'))));
1042        $cols .= QElement('td',
1043                          sprintf(gettext ("by %s"), $rev->get('author')));
1044    } else {
1045        $cols .= QElement('td', array('colspan' => '3'),
1046                          gettext ("None"));
1047    }
1048    return Element('tr', $cols);
1049 }
1050
1051 function showDiff ($dbi, $request) {
1052     $pagename = $request->getArg('pagename');
1053     $version = $request->getArg('version');
1054     $previous = $request->getArg('previous');
1055
1056     $page = $dbi->getPage($pagename);
1057
1058     if ($version) {
1059         if (!($new = $page->getRevision($version)))
1060             NoSuchRevision($page, $version);
1061         $new_version = sprintf(gettext("version %d"), $version);
1062     }
1063     else {
1064         $new = $page->getCurrentRevision();
1065         $new_version = gettext('current version');
1066     }
1067
1068     if (preg_match('/^\d+$/', $previous)) {
1069         if ( !($old = $page->getRevision($previous)) )
1070             NoSuchRevision($page, $previous);
1071         $old_version = sprintf(gettext("version %d"), $previous);
1072         $others = array('major', 'minor', 'author');
1073     }
1074     else {
1075         switch ($previous) {
1076         case 'major':
1077             $old = $new;
1078             while ($old = $page->getRevisionBefore($old)) {
1079                 if (! $old->get('is_minor_edit'))
1080                     break;
1081             }
1082             $old_version = gettext("previous major revision");
1083             $others = array('minor', 'author');
1084             break;
1085         case 'author':
1086             $old = $new;
1087             while ($old = $page->getRevisionBefore($old)) {
1088                 if ($old->get('author') != $new->get('author'))
1089                     break;
1090             }
1091             $old_version = gettext("revision by previous author");
1092             $others = array('major', 'minor');
1093             break;
1094         case 'minor':
1095         default:
1096             $previous='minor';
1097             $old = $page->getRevisionBefore($new);
1098             $old_version = gettext("previous revision");
1099             $others = array('major', 'author');
1100             break;
1101         }
1102     }
1103
1104     $new_url = WikiURL($pagename, array('version' => $new->getVersion()));
1105     $new_link = QElement('a', array('href' => $new_url), $new_version);
1106     $old_url = WikiURL($pagename, array('version' => $old ? $old->getVersion() : 0));
1107     $old_link = QElement('a', array('href' => $old_url), $old_version);
1108     $page_link = LinkExistingWikiWord($pagename);
1109
1110     $html = Element('p',
1111                     sprintf(htmlspecialchars(gettext("Differences between %s and %s of %s.")),
1112                             $new_link, $old_link, $page_link));
1113
1114     $otherdiffs='';
1115     $label = array('major' => gettext("Previous Major Revision"),
1116                    'minor' => gettext("Previous Revision"),
1117                    'author'=> gettext("Previous Author"));
1118     foreach ($others as $other) {
1119         $args = array('action' => 'diff', 'previous' => $other);
1120         if ($version)
1121             $args['version'] = $version;
1122         $otherdiffs .= ' ' . QElement('a', array('href' => WikiURL($pagename, $args),
1123                                                  'class' => 'wikiaction'),
1124                                       $label[$other]);
1125     }
1126     $html .= Element('p',
1127                      htmlspecialchars(gettext("Other diffs:"))
1128                      . $otherdiffs);
1129
1130
1131     if ($old and $old->getVersion() == 0)
1132         $old = false;
1133
1134     $html .= Element('table',
1135                     PageInfoRow($pagename, gettext ("Newer page:"), $new)
1136                     . PageInfoRow($pagename, gettext ("Older page:"), $old));
1137
1138     $html .= "<p>\n";
1139
1140     if ($new && $old) {
1141         $diff = new WikiDiff($old->getContent(), $new->getContent());
1142         if ($diff->isEmpty()) {
1143             $html .= '<hr>[' . gettext ("Versions are identical") . ']';
1144         }
1145         else {
1146             //$fmt = new WikiDiffFormatter;
1147             $fmt = new WikiUnifiedDiffFormatter;
1148             $html .= $fmt->format($diff, $old->getContent());
1149         }
1150     }
1151
1152     include_once('lib/Template.php');
1153     echo GeneratePage('MESSAGE', $html,
1154                       sprintf(gettext ("Diff: %s"), $pagename));
1155 }
1156
1157 // Local Variables:
1158 // mode: php
1159 // tab-width: 8
1160 // c-basic-offset: 4
1161 // c-hanging-comment-ender-p: nil
1162 // indent-tabs-mode: nil
1163 // End:
1164 ?>