wiki_diff.php3

   1 <!-- $Id: wiki_diff.php3,v 1.4 2000-07-02 15:54:44 wainstead 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 /**
  13  * Class used internally by WikiDiff to actually compute the diffs.
  14  *
  15  * The algorithm and much of the code for this class is lifted straight
  16  * from analyze.c (from GNU diffutils-2.7).
  17  *
  18  * GNU diffutils can be found at:
  19  * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
  20  */
  21 class _WikiDiffEngine {
  22     var $xv, $yv;               // Vectors being compared.
  23     var $xchanged, $ychanged;   // Flags for changed lines in XV and YV.
  24     var $edits;                 // List of editing operation to convert XV to YV.
  25
  26     function _WikiDiffEngine ($from_lines, $to_lines)
  27         {
  28           $this->xv = $from_lines;
  29           $this->yv = $to_lines;
  30
  31           $x = 0;
  32           $y = 0;
  33
  34           $xlim = sizeof($this->xv);
  35           $ylim = sizeof($this->yv);
  36
  37           // Compute xchanged and ychanged.
  38           $this->_compareseq(0, $xlim, 0, $ylim);
  39
  40           $this->edits = array();
  41
  42           while ($x < $xlim || $y < $ylim)
  43             {
  44               unset($edit);
  45
  46               // Skip matching "snake".
  47               while ($x < $xlim && $y < $ylim
  48                      && !$this->xchanged[$x] && !$this->ychanged[$y])
  49                 {
  50                   ++$x;
  51                   ++$y;
  52                   ++$edit['cp'];
  53                 }
  54
  55               // Find deletes.
  56               while ($x < $xlim && $this->xchanged[$x])
  57                 {
  58                   ++$x;
  59                   ++$edit['del'];
  60                 }
  61
  62
  63               // Find adds.
  64               while ($y < $ylim && $this->ychanged[$y])
  65                   $edit['add'][] = $this->yv[$y++];
  66
  67               if ($edit['del'] || $edit['add'])
  68                   $this->edits[] = $edit;
  69             }
  70         }
  71
  72     /* Find the midpoint of the shortest edit script for a specified
  73        portion of the two files.
  74
  75        Scan from the beginnings of the files, and simultaneously from the ends,
  76        doing a breadth-first search through the space of edit-sequence.
  77        When the two searches meet, we have found the midpoint of the shortest
  78        edit sequence.
  79
  80        Returns (C, XMID, YMID).  C is the approximate edit cost; this is
  81        the total number of lines inserted or deleted (counting only lines
  82        before the midpoint).  (XMID, YMID) is the midpoint.
  83
  84        This function assumes that the first lines of the specified portions
  85        of the two files do not match, and likewise that the last lines do not
  86        match.  The caller must trim matching lines from the beginning and end
  87        of the portions it is going to specify. */
  88     function _diag ($xoff, $xlim, $yoff, $ylim)
  89         {
  90           $dmin = $xoff - $ylim; // Minimum valid diagonal.
  91           $doff = 1 - $dmin;    // Offset to assure index is always non-neg.
  92           $_dmin = 1;
  93           $_dmax = $xlim - $yoff + $doff; // Maximum valid diagonal
  94           $_fmid = $xoff - $yoff + $doff; // Center diagonal of top-down search
  95           $_bmid = $xlim - $ylim + $doff; // Center diagonal of bottom-up search
  96           $_fmin = $_fmid; $_fmax = $_fmid; // Limits of top-down search.
  97           $_bmin = $_bmid; $_bmax = $_bmid; // Limits of bottom-up search.
  98           $is_odd = ($_fmid - $_bmid) & 1; /* True if southeast corner is on
  99                                             * an odd diagonal with respect to
 100                                             * the northwest. */
 101
 102           $fd[$_fmid] = $xoff;
 103           $bd[$_bmid] = $xlim;
 104
 105           for ($c = 1;; ++$c)
 106             {
 107               //int d;                  /* Active diagonal. */
 108               //int big_snake = 0;
 109
 110               // Extend the top-down search by an edit step in each diagonal.
 111               if ($_fmin > $_dmin)
 112                   $fd[--$_fmin - 1] = -1;
 113               else
 114                   ++$_fmin;
 115               if ($_fmax < $_dmax)
 116                   $fd[++$_fmax + 1] = -1;
 117               else
 118                   --$_fmax;
 119
 120               for ($_d = $_fmax; $_d >= $_fmin; $_d -= 2)
 121                 {
 122                   $tlo = $fd[$_d - 1];
 123                   $thi = $fd[$_d + 1];
 124
 125                   if ($tlo >= $thi)
 126                     $x = $tlo + 1;
 127                   else
 128                     $x = $thi;
 129                   $oldx = $x;
 130                   $y = $x - ($_d - $doff);
 131                   while ($x < $xlim && $y < $ylim
 132                          && $this->xv[$x] == $this->yv[$y])
 133                     {
 134                       ++$x;
 135                       ++$y;
 136                     }
 137                   $fd[$_d] = $x;
 138                   if ($is_odd && $_bmin <= $_d && $_d <= $_bmax
 139                       && $bd[$_d] <= $x)
 140                     {
 141                       return array(2 * $c - 1, $x, $y);
 142                     }
 143                 }
 144
 145               /* Similarly extend the bottom-up search.  */
 146               if ($_bmin > $_dmin)
 147                   $bd[--$_bmin - 1] = $xlim + 1;
 148               else ++$_bmin;
 149               if ($_bmax < $_dmax)
 150                   $bd[++$_bmax + 1] = $xlim + 1;
 151               else
 152                   --$_bmax;
 153               for ($_d = $_bmax; $_d >= $_bmin; $_d -= 2)
 154                 {
 155                   $tlo = $bd[$_d - 1]; $thi = $bd[$_d + 1];
 156
 157                   if ($tlo < $thi)
 158                     $x = $tlo;
 159                   else
 160                     $x = $thi - 1;
 161                   $oldx = $x;
 162                   $y = $x - ($_d - $doff);
 163                   while ($x > $xoff && $y > $yoff
 164                          && $this->xv[$x - 1] == $this->yv[$y - 1])
 165                     {
 166                       --$x;
 167                       --$y;
 168                     }
 169                   $bd[$_d] = $x;
 170                   if (!$is_odd && $_fmin <= $_d && $_d <= $_fmax
 171                       && $x <= $fd[$_d])
 172                     {
 173                       return array(2 * $c, $x, $y);
 174                     }
 175                 }
 176               /* FIXME: add heuristics to avoid slowness?
 177                *
 178                * I've deleted from the diffutils algorithm two hairy
 179                * heuristics which are desingned to keep the algorithm
 180                * efficient even on large files.  (The algorithm as
 181                * implemented here on O(n^2).)
 182                *
 183                * I believe that As long as we're dealing with files
 184                * under a few hundred lines long this is not really
 185                * an issue.
 186                */
 187             }
 188         }
 189
 190     /* Compare in detail contiguous subsequences of the two files
 191        which are known, as a whole, to match each other.
 192
 193        The results are recorded in the vectors $this->{x,y}changed[], by
 194        storing a 1 in the element for each line that is an insertion
 195        or deletion.
 196
 197        The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
 198
 199        Note that XLIM, YLIM are exclusive bounds.
 200        All line numbers are origin-0 and discarded lines are not counted. */
 201     function _compareseq ($xoff, $xlim, $yoff, $ylim)
 202         {
 203           /* Slide down the bottom initial diagonal. */
 204           while ($xoff < $xlim && $yoff < $ylim
 205                  && $this->xv[$xoff] == $this->yv[$yoff])
 206             {
 207               ++$xoff;
 208               ++$yoff;
 209             }
 210
 211           /* Slide up the top initial diagonal. */
 212           while ($xlim > $xoff && $ylim > $yoff
 213                  && $this->xv[$xlim - 1] == $this->yv[$ylim - 1])
 214             {
 215               --$xlim;
 216               --$ylim;
 217             }
 218
 219           /* Handle simple cases. */
 220           if ($xoff == $xlim)
 221             {
 222               while ($yoff < $ylim)
 223                   $this->ychanged[$yoff++] = 1;
 224             }
 225           else if ($yoff == $ylim)
 226             {
 227               while ($xoff < $xlim)
 228                   $this->xchanged[$xoff++] = 1;
 229             }
 230           else
 231             {
 232               // Find a point of correspondence in the middle of the files.
 233               list ($c, $xmid, $ymid) = $this->_diag($xoff, $xlim,
 234                                                      $yoff, $ylim);
 235
 236               if ($c <= 1)
 237                 {
 238                   /* This should be impossible, because it implies that
 239                      one of the two subsequences is empty,
 240                      and that case was handled above without calling `diag'.
 241                      Let's verify that this is true.  */
 242                   die("This is impossible"); //FIXME
 243                 }
 244
 245               // Use the partitions to split this problem into subproblems.
 246               $this->_compareseq ($xoff, $xmid, $yoff, $ymid);
 247               $this->_compareseq ($xmid, $xlim, $ymid, $ylim);
 248             }
 249         }
 250 }
 251
 252
 253
 254 class WikiDiff
 255 {
 256     var $edits;
 257
 258     function WikiDiff($from_lines = false, $to_lines = false)
 259         {
 260           if ($from_lines && $to_lines)
 261             {
 262               $compute = new _WikiDiffEngine($from_lines, $to_lines);
 263               $this->edits = $compute->edits;
 264             }
 265           else if ($from_lines)
 266             {
 267               // $from_lines is not really from_lines, but rather
 268               // a serialized WikiDiff.
 269               $this->edits = unserialize($from_lines);
 270             }
 271         }
 272
 273     function apply ($from_lines)
 274         {
 275           $x = 0;
 276           $xlim = sizeof($from_lines);
 277
 278           for ( reset($this->edits);
 279                 $edit = current($this->edits);
 280                 next($this->edits) )
 281             {
 282
 283               for ($i = 0; $i < $edit['cp']; $i++)
 284                   $output[] = $from_lines[$x++];
 285               $x += $edit['del'];
 286               if ($adds = $edit['add'])
 287                   for ( reset($adds); $add = current($adds); next($adds) )
 288                       $output[] = $add;
 289             }
 290           while ($x < $xlim)
 291               $output[] = $from_lines[$x++];
 292           if ($x != $xlim)
 293               die("WikiDiff::apply: line count mismatch: $x != $xlim");
 294           return $output;
 295         }
 296
 297     function serialize ()
 298         {
 299           return serialize($this->edits);
 300         }
 301
 302     function unserialize ($serial)
 303         {
 304           $this->edits = unserialize($serial);
 305         }
 306 }
 307
 308 class WikiDiffFormatter {
 309
 310     var $context_lines;
 311     var $context_prefix, $deletes_prefix, $adds_prefix;
 312
 313     function WikiDiffFormatter ()
 314         {
 315           $this->context_lines = 0;
 316           $this->context_prefix = '&nbsp;&nbsp;';
 317           $this->deletes_prefix = '&lt;&nbsp;';
 318           $this->adds_prefix = '&gt;&nbsp;';
 319         }
 320
 321     function format ($diff, $from_lines)
 322         {
 323           $html = '<table width="100%" bgcolor="black"' .
 324                   "cellspacing=2 cellpadding=2 border=0\n";
 325           $html .= $this->_format($diff->edits, $from_lines);
 326           $html .= "</table>\n";
 327
 328           return $html;
 329         }
 330
 331     function _format ($edits, $from_lines)
 332         {
 333           $x = 0; $y = 0;
 334           $xlim = sizeof($from_lines);
 335
 336           reset($edits);
 337           while ($edit = current($edits))
 338             {
 339               $x += $edit['cp'];
 340               $y += $edit['cp'];
 341
 342               // Copy leading context.
 343               if (!isset($cc))
 344                   $cc = max(0, $x - $this->context_lines);
 345               if (!$hunks)
 346                 {
 347                   $xoff = $cc;
 348                   $yoff = $xoff + $y - $x;
 349                 }
 350               while ($cc < $x)
 351                   $hunk['context'][] = $from_lines[$cc++];
 352
 353               // Copy deletes
 354               for ($i = 0; $i < $edit['del']; $i++)
 355                   $hunk['deletes'][] = $from_lines[$x++];
 356
 357               // Copy adds
 358               if ($adds = $edit['add'])
 359                   for ( reset($adds); $add = current($adds); next($adds) )
 360                     {
 361                       $hunk['adds'][] = $add;
 362                       ++$y;
 363                     }
 364
 365               $hunks[] = $hunk;
 366               $hunk = array();
 367
 368               // Update context pointer
 369               $cc = $x;
 370
 371               if (!($edit = next($edits))
 372                   || $edit['cp'] > 2 * $this->context_lines)
 373                 {
 374                   // Copy trailing context
 375                   while ($cc < min($x + $this->context_lines, $xlim))
 376                     $hunk['context'][] = $from_lines[$cc++];
 377                   $xlen = $cc - $xoff;
 378                   $ylen = $cc + $y - $x - $yoff;;
 379                   unset($cc);
 380                   $hunks[] = $hunk;
 381                   $hunk = array();
 382
 383                   $xbeg = $xlen ? $xoff + 1 : $xoff;
 384                   $ybeg = $ylen ? $yoff + 1 : $yoff;
 385                   $html .= $this->_emit_diff( $xbeg,$xlen,$ybeg,$ylen, $hunks );
 386                   unset($hunks);
 387                 }
 388             }
 389
 390             return $html;
 391         }
 392
 393     function _emit_lines($lines,  $prefix, $color)
 394         {
 395           if (! is_array($lines))
 396               return '';
 397
 398           for (reset($lines); $line = current($lines); next($lines))
 399             {
 400               $html .= "<tr bgcolor=\"$color\"><td><tt>$prefix</tt>";
 401               $html .= htmlspecialchars($line) . "</td></tr>\n";
 402             }
 403
 404           return $html;
 405         }
 406
 407     function _emit_diff ($xbeg,$xlen,$ybeg,$ylen,$hunks)
 408         {
 409           $html = '<tr><td><table width="100%" bgcolor="white"'
 410                 . " cellspacing=0 border=0 cellpadding=4>\n"
 411                 . '<tr bgcolor="#cccccc"><td><tt>'
 412                 . $this->_diff_header($xbeg, $xlen, $ybeg, $ylen)
 413                 . "</tt></td></tr>\n<tr><td>\n"
 414                 . "<table width=\"100%\" cellspacing=0 border=0 cellpadding=2>\n";
 415
 416           for (reset($hunks); $hunk = current($hunks); next($hunks))
 417             {
 418               $html .= $this->_emit_lines($hunk['context'],
 419                                  $this->context_prefix,
 420                                  '#ffffff');
 421               $html .= $this->_emit_lines($hunk['deletes'],
 422                                  $this->deletes_prefix,
 423                                  '#ffcccc');
 424               $html .= $this->_emit_lines($hunk['adds'],
 425                                  $this->adds_prefix,
 426                                  '#ccffcc');
 427             }
 428
 429           $html .= "</table></td></tr></table></td></tr>\n";
 430           return $html;
 431         }
 432
 433     function _diff_header ($xbeg,$xlen,$ybeg,$ylen)
 434         {
 435           $what = $xlen ? ($ylen ? 'c' : 'd') : 'a';
 436           $xlen = $xlen > 1 ? "," . ($xbeg + $xlen - 1) : '';
 437           $ylen = $ylen > 1 ? "," . ($ybeg + $ylen - 1) : '';
 438
 439           return "$xbeg$xlen$what$ybeg$ylen";
 440         }
 441 }
 442
 443 class WikiUnifiedDiffFormatter extends WikiDiffFormatter {
 444     function WikiUnifiedDiffFormatter ($context_lines = 3)
 445         {
 446           $this->context_lines = $context_lines;
 447           $this->context_prefix = '&nbsp;';
 448           $this->deletes_prefix = '-';
 449           $this->adds_prefix = '+';
 450         }
 451
 452     function _diff_header ($xbeg,$xlen,$ybeg,$ylen)
 453         {
 454           $xlen = $xlen == 1 ? '' : ",$xlen";
 455           $ylen = $ylen == 1 ? '' : ",$ylen";
 456
 457           return "@@ -$xbeg$xlen +$ybeg$ylen @@";
 458         }
 459 }
 460
 461
 462
 463 /////////////////////////////////////////////////////////////////
 464
 465 $pagename = $diff;
 466
 467 $wiki = RetrievePage($dbi, $pagename);
 468 $dba = OpenDataBase($ArchiveDataBase);
 469 $archive= RetrievePage($dba, $pagename);
 470
 471 $html = '<table><tr><td align="right">Current page:</td>';
 472 if (is_array($wiki))
 473     $html .= "<td>version $wiki[version],</td><td>last modified on "
 474            . date($datetimeformat, $wiki['lastmodified'])
 475            . "</td><td>by $wiki[author]</td>";
 476 else
 477     $html .= "<td colspan=3><em>None</em></td>";
 478 $html .= '</tr><tr><td align="right">Archived page:</td>';
 479 if (is_array($archive))
 480     $html .= "<td>version $archive[version],</td><td>last modified on "
 481              . date($datetimeformat, $archive['lastmodified'])
 482              . "</td><td>by $archive[author]</td>";
 483 else
 484     $html .= "<td colspan=3><em>None</em></td>";
 485 $html .= "</tr></table><p>\n";
 486
 487
 488 if (is_array($wiki) && is_array($archive))
 489   {
 490     $diff = new WikiDiff($archive['content'], $wiki['content']);
 491     //$fmt = new WikiDiffFormatter();
 492     $fmt = new WikiUnifiedDiffFormatter();
 493     $html .= $fmt->format($diff, $archive['content']);
 494   }
 495
 496 GeneratePage('MESSAGE', $html, 'Diff of '.htmlspecialchars($pagename), 0);
 497 ?>