lib/diff.php

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