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