wiki_diff.php3

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