lib/diff.php

   1 <?php
   2 // PukiWiki - Yet another WikiWikiWeb clone.
   3 // $Id: diff.php,v 1.6 2005/12/10 12:23:24 henoheno Exp $
   4 // Copyright (C)
   5 //   2003-2005 PukiWiki Developers Team
   6 //   2001-2002 Originally written by yu-ji
   7 // License: GPL v2 or (at your option) any later version
   8 //
   9
  10 // Show more information when it conflicts
  11 define('PKWK_DIFF_SHOW_CONFLICT_DETAIL', 1);
  12
  13 // Create diff-style data between arrays
  14 function do_diff($strlines1, $strlines2)
  15 {
  16         $obj = new line_diff();
  17         $str = $obj->str_compare($strlines1, $strlines2);
  18         return $str;
  19 }
  20
  21 // Merge helper (when it conflicts)
  22 function do_update_diff($pagestr, $poststr, $original)
  23 {
  24         $obj = new line_diff();
  25
  26         $obj->set_str('left', $original, $pagestr);
  27         $obj->compare();
  28         $diff1 = $obj->toArray();
  29
  30         $obj->set_str('right', $original, $poststr);
  31         $obj->compare();
  32         $diff2 = $obj->toArray();
  33
  34         $arr = $obj->arr_compare('all', $diff1, $diff2);
  35
  36         if (PKWK_DIFF_SHOW_CONFLICT_DETAIL) {
  37                 global $do_update_diff_table;
  38
  39                 $do_update_diff_table = <<<EOD
  40 <p>l : between backup data and stored page data.<br />
  41  r : between backup data and your post data.</p>
  42 <table class="style_table">
  43  <tr>
  44   <th>l</th>
  45   <th>r</th>
  46   <th>text</th>
  47  </tr>
  48 EOD;
  49                 $tags = array('th', 'th', 'td');
  50                 foreach ($arr as $_obj) {
  51                         $do_update_diff_table .= '<tr>';
  52                         $params = array($_obj->get('left'), $_obj->get('right'), $_obj->text());
  53                         foreach ($params as $key=>$text) {
  54                                 $text = htmlspecialchars($text);
  55                                 if (trim($text) == '') $text = '&nbsp;';
  56                                 $do_update_diff_table .= '<' . $tags[$key] .
  57                                         ' class="style_' . $tags[$key] . '">' . $text .
  58                                         '</' . $tags[$key] . '>';
  59                         }
  60                         $do_update_diff_table .= '</tr>' . "\n";
  61                 }
  62                 $do_update_diff_table .= '</table>' . "\n";
  63         }
  64
  65         $body = '';
  66         foreach ($arr as $_obj) {
  67                 if ($_obj->get('left') != '-' && $_obj->get('right') != '-')
  68                         $body .= $_obj->text();
  69         }
  70
  71         $auto = 1;
  72
  73         return array(rtrim($body) . "\n", $auto);
  74 }
  75
  76
  77 // References of this class:
  78 // S. Wu, <A HREF="http://www.cs.arizona.edu/people/gene/vita.html">
  79 // E. Myers,</A> U. Manber, and W. Miller,
  80 // <A HREF="http://www.cs.arizona.edu/people/gene/PAPERS/np_diff.ps">
  81 // "An O(NP) Sequence Comparison Algorithm,"</A>
  82 // Information Processing Letters 35, 6 (1990), 317-323.
  83 class line_diff
  84 {
  85         var $arr1, $arr2, $m, $n, $pos, $key, $plus, $minus, $equal, $reverse;
  86
  87         function line_diff($plus = '+', $minus = '-', $equal = ' ')
  88         {
  89                 $this->plus  = $plus;
  90                 $this->minus = $minus;
  91                 $this->equal = $equal;
  92         }
  93
  94         function arr_compare($key, $arr1, $arr2)
  95         {
  96                 $this->key  = $key;
  97                 $this->arr1 = $arr1;
  98                 $this->arr2 = $arr2;
  99                 $this->compare();
 100                 $arr = $this->toArray();
 101                 return $arr;
 102         }
 103
 104         function set_str($key, $str1, $str2)
 105         {
 106                 $this->key  = $key;
 107                 $this->arr1 = array();
 108                 $this->arr2 = array();
 109                 $str1 = str_replace("\r", '', $str1);
 110                 $str2 = str_replace("\r", '', $str2);
 111                 foreach (explode("\n", $str1) as $line) {
 112                         $this->arr1[] = new DiffLine($line);
 113                 }
 114                 foreach (explode("\n", $str2) as $line) {
 115                         $this->arr2[] = new DiffLine($line);
 116                 }
 117         }
 118
 119         function str_compare($str1, $str2)
 120         {
 121                 $this->set_str('diff', $str1, $str2);
 122                 $this->compare();
 123
 124                 $str = '';
 125                 foreach ($this->toArray() as $obj) {
 126                         $str .= $obj->get('diff') . $obj->text();
 127                 }
 128                 return $str;
 129         }
 130
 131         function compare()
 132         {
 133                 $this->m = count($this->arr1);
 134                 $this->n = count($this->arr2);
 135
 136                 if ($this->m == 0 || $this->n == 0) { // No need to compare
 137                         $this->result = array(array('x'=>0, 'y'=>0));
 138                         return;
 139                 }
 140
 141                 // Sentinel
 142                 array_unshift($this->arr1, new DiffLine(''));
 143                 $this->m++;
 144                 array_unshift($this->arr2, new DiffLine(''));
 145                 $this->n++;
 146
 147                 $this->reverse = ($this->n < $this->m);
 148                 if ($this->reverse) {
 149                         // Swap
 150                         $tmp = $this->m; $this->m = $this->n; $this->n = $tmp;
 151                         $tmp = $this->arr1; $this->arr1 = $this->arr2; $this->arr2 = $tmp;
 152                         unset($tmp);
 153                 }
 154
 155                 $delta = $this->n - $this->m; // Must be >=0;
 156
 157                 $fp = array();
 158                 $this->path = array();
 159
 160                 for ($p = -($this->m + 1); $p <= ($this->n + 1); $p++) {
 161                         $fp[$p] = -1;
 162                         $this->path[$p] = array();
 163                 }
 164
 165                 for ($p = 0;; $p++) {
 166                         for ($k = -$p; $k <= $delta - 1; $k++) {
 167                                 $fp[$k] = $this->snake($k, $fp[$k - 1], $fp[$k + 1]);
 168                         }
 169                         for ($k = $delta + $p; $k >= $delta + 1; $k--) {
 170                                 $fp[$k] = $this->snake($k, $fp[$k - 1], $fp[$k + 1]);
 171                         }
 172                         $fp[$delta] = $this->snake($delta, $fp[$delta - 1], $fp[$delta + 1]);
 173                         if ($fp[$delta] >= $this->n) {
 174                                 $this->pos = $this->path[$delta]; // ·ÐÏ©¤ò·èÄê
 175                                 return;
 176                         }
 177                 }
 178         }
 179
 180         function snake($k, $y1, $y2)
 181         {
 182                 if ($y1 >= $y2) {
 183                         $_k = $k - 1;
 184                         $y = $y1 + 1;
 185                 } else {
 186                         $_k = $k + 1;
 187                         $y = $y2;
 188                 }
 189                 $this->path[$k] = $this->path[$_k];// ¤³¤³¤Þ¤Ç¤Î·ÐÏ©¤ò¥³¥Ô¡¼
 190                 $x = $y - $k;
 191                 while ((($x + 1) < $this->m) && (($y + 1) < $this->n)
 192                         and $this->arr1[$x + 1]->compare($this->arr2[$y + 1]))
 193                 {
 194                         ++$x; ++$y;
 195                         $this->path[$k][] = array('x'=>$x, 'y'=>$y); // ·ÐÏ©¤òÄÉ²Ã
 196                 }
 197                 return $y;
 198         }
 199
 200         function toArray()
 201         {
 202                 $arr = array();
 203                 if ($this->reverse) { // ¸ÈÂ©¤Ê¡Ä
 204                         $_x = 'y'; $_y = 'x'; $_m = $this->n; $arr1 =& $this->arr2; $arr2 =& $this->arr1;
 205                 } else {
 206                         $_x = 'x'; $_y = 'y'; $_m = $this->m; $arr1 =& $this->arr1; $arr2 =& $this->arr2;
 207                 }
 208
 209                 $x = $y = 1;
 210                 $this->add_count = $this->delete_count = 0;
 211                 $this->pos[] = array('x'=>$this->m, 'y'=>$this->n); // Sentinel
 212                 foreach ($this->pos as $pos) {
 213                         $this->delete_count += ($pos[$_x] - $x);
 214                         $this->add_count    += ($pos[$_y] - $y);
 215
 216                         while ($pos[$_x] > $x) {
 217                                 $arr1[$x]->set($this->key, $this->minus);
 218                                 $arr[] = $arr1[$x++];
 219                         }
 220
 221                         while ($pos[$_y] > $y) {
 222                                 $arr2[$y]->set($this->key, $this->plus);
 223                                 $arr[] =  $arr2[$y++];
 224                         }
 225
 226                         if ($x < $_m) {
 227                                 $arr1[$x]->merge($arr2[$y]);
 228                                 $arr1[$x]->set($this->key, $this->equal);
 229                                 $arr[] = $arr1[$x];
 230                         }
 231                         ++$x; ++$y;
 232                 }
 233                 return $arr;
 234         }
 235 }
 236
 237 class DiffLine
 238 {
 239         var $text;
 240         var $status;
 241
 242         function DiffLine($text)
 243         {
 244                 $this->text   = $text . "\n";
 245                 $this->status = array();
 246         }
 247
 248         function compare($obj)
 249         {
 250                 return $this->text == $obj->text;
 251         }
 252
 253         function set($key, $status)
 254         {
 255                 $this->status[$key] = $status;
 256         }
 257
 258         function get($key)
 259         {
 260                 return isset($this->status[$key]) ? $this->status[$key] : '';
 261         }
 262
 263         function merge($obj)
 264         {
 265                 $this->status += $obj->status;
 266         }
 267
 268         function text()
 269         {
 270                 return $this->text;
 271         }
 272 }
 273 ?>