lib/diff.php

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