lib/diff.php

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