lib/diff.php

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