wiki_diff.php3

   1 <!-- $Id: wiki_diff.php3,v 1.6 2000-07-15 21:00:38 ahollosi Exp $ -->
   2 <?
   3 // wiki_diff.php3
   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 ($edit > 0)
 475               {
 476                 // Was a copy --- just pass it through.       }
 477                 $x += $edit;
 478               }
 479             else if ($edit < 0)
 480               { // Was a delete, turn it into an add.
 481                 $ndelete = -$edit;
 482                 $edit = array();
 483                 while ($ndelete-- > 0)
 484                     $edit[] = "" . $from_lines[$x++];
 485               }
 486             else if (is_array($edit))
 487               { // Was an add, turn it into a delete.
 488                 $nadd = sizeof($edit);
 489                 if ($nadd == 0) die("assertion error");
 490                 $edit = -$nadd;
 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 ($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 ($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 ($edit > 0)
 663                 while ($edit--)
 664                     $output[] = $from_lines[$x++];
 665             else if ($edit < 0)
 666                 $x += -$edit;
 667             else
 668               {
 669                 reset($edit);
 670                 while (list ($junk, $line) = each($edit))
 671                     $output[] = $line;
 672               }
 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    * Compute the length of the Longest Common Subsequence (LCS).
 697    *
 698    * This is mostly for diagnostic purposed.
 699    */
 700   function lcs ()
 701       {
 702         $lcs = 0;
 703         for (reset($this->edits);
 704              $edit = current($this->edits);
 705              next($this->edits))
 706           {
 707             if ($edit > 0)
 708                 $lcs += $edit;
 709           }
 710         return $lcs;
 711       }
 712
 713   /**
 714    * Check a WikiDiff for validity.
 715    *
 716    * This is here only for debugging purposes.
 717    */
 718   function _check ($from_lines, $to_lines)
 719       {
 720         $test = $this->apply($from_lines);
 721         if (serialize($test) != serialize($to_lines))
 722             die("WikiDiff::_check: failed");
 723
 724         reset($this->edits);
 725         $prev = current($this->edits);
 726         $prevtype = $prev > 0 ? 'c' : ($prev < 0 ? 'd' : 'a');
 727
 728         while ($edit = next($this->edits))
 729           {
 730             $type = $edit > 0 ? 'c' : ($edit < 0 ? 'd' : 'a');
 731             if ( $prevtype == $type )
 732                 die("WikiDiff::_check: edit sequence is non-optimal");
 733             $prevtype = $type;
 734           }
 735         $lcs = $this->lcs();
 736         echo "<strong>WikiDiff Okay: LCS = $lcs</strong>\n";
 737       }
 738 }
 739
 740
 741 /**
 742  * A class to format a WikiDiff as HTML.
 743  *
 744  * Usage:
 745  *
 746  *   $diff = new WikiDiff($lines1, $lines2); // compute diff.
 747  *
 748  *   $fmt = new WikiDiffFormatter;
 749  *   echo $fmt->format($diff, $lines1); // Output HTMLified standard diff.
 750  *
 751  * or to output reverse diff (diff's that would take $lines2 to $lines1):
 752  *
 753  *   $fmt = new WikiDiffFormatter('reversed');
 754  *   echo $fmt->format($diff, $lines1);
 755  */
 756 class WikiDiffFormatter
 757 {
 758   var $context_lines;
 759   var $do_reverse_diff;
 760   var $context_prefix, $deletes_prefix, $adds_prefix;
 761
 762   function WikiDiffFormatter ($reverse = false)
 763       {
 764         $this->do_reverse_diff = $reverse;
 765         $this->context_lines = 0;
 766         $this->context_prefix = '&nbsp;&nbsp;';
 767         $this->deletes_prefix = '&lt;&nbsp;';
 768         $this->adds_prefix = '&gt;&nbsp;';
 769       }
 770
 771   function format ($diff, $from_lines)
 772       {
 773         $html = '<table width="100%" bgcolor="black"' .
 774                 "cellspacing=2 cellpadding=2 border=0\n";
 775         $html .= $this->_format($diff->edits, $from_lines);
 776         $html .= "</table>\n";
 777
 778         return $html;
 779       }
 780
 781   function _format ($edits, $from_lines)
 782       {
 783         $x = 0; $y = 0;
 784         $xlim = sizeof($from_lines);
 785
 786         reset($edits);
 787         while ($edit = current($edits))
 788           {
 789             if ($edit > 0)
 790               { // Edit op is a copy.
 791                 $ncopy = $edit;
 792               }
 793             else
 794               {
 795                 $ncopy = 0;
 796                 if (!$hunk)
 797                   {
 798                     // Start of an output hunk.
 799                     $xoff = max(0, $x - $this->context_lines);
 800                     $yoff = $xoff + $y - $x;
 801                     if ($xoff < $x)
 802                       {
 803                         // Get leading context.
 804                         $context = array();
 805                         for ($i = $xoff; $i < $x; $i++)
 806                             $context[] = $from_lines[$i];
 807                         $hunk['c'] = $context;
 808                       }
 809                   }
 810                 if ($edit < 0)
 811                   { // Edit op is a delete
 812                     $deletes = array();
 813                     while ($edit++ < 0)
 814                         $deletes[] = $from_lines[$x++];
 815                     $hunk[$this->do_reverse_diff ? 'a' : 'd'] = $deletes;
 816                   }
 817                 else
 818                   { // Edit op is an add.
 819                     if (!is_array($edit)) die("assertion error");
 820                     $y += sizeof($edit);
 821                     $hunk[$this->do_reverse_diff ? 'd' : 'a'] = $edit;
 822                   }
 823               }
 824
 825             $next = next($edits);
 826             if ($hunk)
 827               {
 828                 if ( !$next || $ncopy > 2 * $this->context_lines)
 829                   {
 830                     // End of an output hunk.
 831                     $hunks[] = $hunk;
 832                     unset($hunk);
 833
 834                     $xend = min($x + $this->context_lines, $xlim);
 835                     if ($x < $xend)
 836                       {
 837                         // Get trailing context.
 838                         $context = array();
 839                         for ($i = $x; $i < $xend; $i++)
 840                             $context[] = $from_lines[$i];
 841                         $hunks[] = array('c' => $context);
 842                       }
 843
 844                     $xlen = $xend - $xoff;
 845                     $ylen = $xend + $y - $x - $yoff;
 846                     $xbeg = $xlen ? $xoff + 1 : $xoff;
 847                     $ybeg = $ylen ? $yoff + 1 : $yoff;
 848
 849                     if ($this->do_reverse_diff)
 850                         list ($xbeg, $xlen, $ybeg, $ylen)
 851                             = array($ybeg, $ylen, $xbeg, $xlen);
 852
 853                     $html .= $this->_emit_diff($xbeg,$xlen,$ybeg,$ylen,
 854                                                $hunks);
 855                     unset($hunks);
 856                   }
 857                 else if ($ncopy)
 858                   {
 859                     $hunks[] = $hunk;
 860
 861                     // Copy context.
 862                     $context = array();
 863                     for ($i = $x; $i < $x + $ncopy; $i++)
 864                         $context[] = $from_lines[$i];
 865                     $hunk = array('c' => $context);
 866                   }
 867               }
 868
 869             $x += $ncopy;
 870             $y += $ncopy;
 871           }
 872         return $html;
 873       }
 874
 875   function _emit_lines($lines,  $prefix, $color)
 876       {
 877         reset($lines);
 878         while (list ($junk, $line) = each($lines))
 879           {
 880             $html .= "<tr bgcolor=\"$color\"><td><tt>$prefix</tt>";
 881             $html .= "<tt>" . htmlspecialchars($line) . "</tt></td></tr>\n";
 882           }
 883         return $html;
 884       }
 885
 886   function _emit_diff ($xbeg,$xlen,$ybeg,$ylen,$hunks)
 887       {
 888         $html = '<tr><td><table width="100%" bgcolor="white"'
 889               . " cellspacing=0 border=0 cellpadding=4>\n"
 890               . '<tr bgcolor="#cccccc"><td><tt>'
 891               . $this->_diff_header($xbeg, $xlen, $ybeg, $ylen)
 892               . "</tt></td></tr>\n<tr><td>\n"
 893               . "<table width=\"100%\" cellspacing=0 border=0 cellpadding=2>\n";
 894
 895         $prefix = array('c' => $this->context_prefix,
 896                         'a' => $this->adds_prefix,
 897                         'd' => $this->deletes_prefix);
 898         $color = array('c' => '#ffffff',
 899                        'a' => '#ffcccc',
 900                        'd' => '#ccffcc');
 901
 902         for (reset($hunks); $hunk = current($hunks); next($hunks))
 903           {
 904             if ($lines = $hunk['c'])
 905                 $html .= $this->_emit_lines($lines,
 906                                             $this->context_prefix, '#ffffff');
 907             if ($lines = $hunk['d'])
 908                 $html .= $this->_emit_lines($lines,
 909                                             $this->deletes_prefix, '#ccffcc');
 910             if ($lines = $hunk['a'])
 911                 $html .= $this->_emit_lines($lines,
 912                                             $this->adds_prefix, '#ffcccc');
 913           }
 914
 915         $html .= "</table></td></tr></table></td></tr>\n";
 916         return $html;
 917       }
 918
 919   function _diff_header ($xbeg,$xlen,$ybeg,$ylen)
 920       {
 921         $what = $xlen ? ($ylen ? 'c' : 'd') : 'a';
 922         $xlen = $xlen > 1 ? "," . ($xbeg + $xlen - 1) : '';
 923         $ylen = $ylen > 1 ? "," . ($ybeg + $ylen - 1) : '';
 924
 925         return "$xbeg$xlen$what$ybeg$ylen";
 926       }
 927 }
 928
 929 /**
 930  * A class to format a WikiDiff as a pretty HTML unified diff.
 931  *
 932  * Usage:
 933  *
 934  *   $diff = new WikiDiff($lines1, $lines2); // compute diff.
 935  *
 936  *   $fmt = new WikiUnifiedDiffFormatter;
 937  *   echo $fmt->format($diff, $lines1); // Output HTMLified unified diff.
 938  */
 939 class WikiUnifiedDiffFormatter extends WikiDiffFormatter
 940 {
 941   function WikiUnifiedDiffFormatter ($reverse = false, $context_lines = 3)
 942       {
 943         $this->do_reverse_diff = $reverse;
 944         $this->context_lines = $context_lines;
 945         $this->context_prefix = '&nbsp;';
 946         $this->deletes_prefix = '-';
 947         $this->adds_prefix = '+';
 948       }
 949
 950   function _diff_header ($xbeg,$xlen,$ybeg,$ylen)
 951       {
 952         $xlen = $xlen == 1 ? '' : ",$xlen";
 953         $ylen = $ylen == 1 ? '' : ",$ylen";
 954
 955         return "@@ -$xbeg$xlen +$ybeg$ylen @@";
 956       }
 957 }
 958
 959
 960
 961 /////////////////////////////////////////////////////////////////
 962
 963 if ($diff)
 964 {
 965   if (get_magic_quotes_gpc()) {
 966      $diff = stripslashes($diff);
 967   }
 968
 969   $pagename = $diff;
 970
 971   $wiki = RetrievePage($dbi, $pagename);
 972   $dba = OpenDataBase($ArchiveDataBase);
 973   $archive= RetrievePage($dba, $pagename);
 974
 975   $html = '<table><tr><td align="right">Current page:</td>';
 976   if (is_array($wiki))
 977       $html .= "<td>version $wiki[version],</td><td>last modified on "
 978           . date($datetimeformat, $wiki['lastmodified'])
 979           . "</td><td>by $wiki[author]</td>";
 980   else
 981       $html .= "<td colspan=3><em>None</em></td>";
 982   $html .= '</tr><tr><td align="right">Archived page:</td>';
 983   if (is_array($archive))
 984       $html .= "<td>version $archive[version],</td><td>last modified on "
 985           . date($datetimeformat, $archive['lastmodified'])
 986           . "</td><td>by $archive[author]</td>";
 987   else
 988       $html .= "<td colspan=3><em>None</em></td>";
 989   $html .= "</tr></table><p>\n";
 990
 991
 992   if (is_array($wiki) && is_array($archive))
 993     {
 994       $diff = new WikiDiff($archive['content'], $wiki['content']);
 995       //$fmt = new WikiDiffFormatter;
 996       $fmt = new WikiUnifiedDiffFormatter;
 997       $html .= $fmt->format($diff, $archive['content']);
 998     }
 999
1000   GeneratePage('MESSAGE', $html, 'Diff of '.htmlspecialchars($pagename), 0);
1001 }
1002 ?>