lib/diff.php

   1 <?php
   2 // PukiWiki - Yet another WikiWikiWeb clone.
   3 // diff.php
   4 // Copyright
   5 //   2003-2016 PukiWiki Development 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 // Visualize diff-style-text to text-with-CSS
  22 //   '+Added'   => '<span added>Added</span>'
  23 //   '-Removed' => '<span removed>Removed</span>'
  24 //   ' Nothing' => 'Nothing'
  25 function diff_style_to_css($str = '')
  26 {
  27         // Cut diff markers ('+' or '-' or ' ')
  28         $str = preg_replace('/^\-(.*)$/m', '<span class="diff_removed">$1</span>', $str);
  29         $str = preg_replace('/^\+(.*)$/m', '<span class="diff_added"  >$1</span>', $str);
  30         return preg_replace('/^ (.*)$/m',  '$1', $str);
  31 }
  32
  33 // Merge helper (when it conflicts)
  34 function do_update_diff($pagestr, $poststr, $original)
  35 {
  36         $obj = new line_diff();
  37
  38         $obj->set_str('left', $original, $pagestr);
  39         $obj->compare();
  40         $diff1 = $obj->toArray();
  41
  42         $obj->set_str('right', $original, $poststr);
  43         $obj->compare();
  44         $diff2 = $obj->toArray();
  45
  46         $arr = $obj->arr_compare('all', $diff1, $diff2);
  47
  48         if (PKWK_DIFF_SHOW_CONFLICT_DETAIL) {
  49                 global $do_update_diff_table;
  50                 $table = array();
  51                 $table[] = <<<EOD
  52 <p>l : between backup data and stored page data.<br />
  53  r : between backup data and your post data.</p>
  54 <table class="style_table">
  55  <tr>
  56   <th>l</th>
  57   <th>r</th>
  58   <th>text</th>
  59  </tr>
  60 EOD;
  61                 $tags = array('th', 'th', 'td');
  62                 foreach ($arr as $_obj) {
  63                         $table[] = ' <tr>';
  64                         $params = array($_obj->get('left'), $_obj->get('right'), $_obj->text());
  65                         foreach ($params as $key => $text) {
  66                                 $text = htmlsc(rtrim($text));
  67                                 if (empty($text)) $text = '&nbsp;';
  68                                 $table[] =
  69                                         '  <' . $tags[$key] . ' class="style_' . $tags[$key] . '">' .
  70                                         $text .
  71                                         '</' . $tags[$key] . '>';
  72                         }
  73                         $table[] = ' </tr>';
  74                 }
  75                 $table[] =  '</table>';
  76
  77                 $do_update_diff_table = implode("\n", $table) . "\n";
  78                 unset($table);
  79         }
  80
  81         $body = array();
  82         foreach ($arr as $_obj) {
  83                 if ($_obj->get('left') != '-' && $_obj->get('right') != '-') {
  84                         $body[] = $_obj->text();
  85                 }
  86         }
  87
  88         return array(rtrim(implode('', $body)) . "\n", 1);
  89 }
  90
  91
  92 // References of this class:
  93 // S. Wu, <A HREF="http://www.cs.arizona.edu/people/gene/vita.html">
  94 // E. Myers,</A> U. Manber, and W. Miller,
  95 // <A HREF="http://www.cs.arizona.edu/people/gene/PAPERS/np_diff.ps">
  96 // "An O(NP) Sequence Comparison Algorithm,"</A>
  97 // Information Processing Letters 35, 6 (1990), 317-323.
  98 class line_diff
  99 {
 100         var $arr1, $arr2, $m, $n, $pos, $key, $plus, $minus, $equal, $reverse;
 101
 102         function line_diff($plus = '+', $minus = '-', $equal = ' ')
 103         {
 104                 $this->__construct($plus, $minus, $equal);
 105         }
 106         function __construct($plus = '+', $minus = '-', $equal = ' ')
 107         {
 108                 $this->plus  = $plus;
 109                 $this->minus = $minus;
 110                 $this->equal = $equal;
 111         }
 112
 113         function arr_compare($key, $arr1, $arr2)
 114         {
 115                 $this->key  = $key;
 116                 $this->arr1 = $arr1;
 117                 $this->arr2 = $arr2;
 118                 $this->compare();
 119                 $arr = $this->toArray();
 120                 return $arr;
 121         }
 122
 123         function set_str($key, $str1, $str2)
 124         {
 125                 $this->key  = $key;
 126                 $this->arr1 = array();
 127                 $this->arr2 = array();
 128                 $str1 = str_replace("\r", '', $str1);
 129                 $str2 = str_replace("\r", '', $str2);
 130                 foreach (explode("\n", $str1) as $line) {
 131                         $this->arr1[] = new DiffLine($line);
 132                 }
 133                 foreach (explode("\n", $str2) as $line) {
 134                         $this->arr2[] = new DiffLine($line);
 135                 }
 136         }
 137
 138         function str_compare($str1, $str2)
 139         {
 140                 $this->set_str('diff', $str1, $str2);
 141                 $this->compare();
 142
 143                 $str = '';
 144                 foreach ($this->toArray() as $obj) {
 145                         $str .= $obj->get('diff') . $obj->text();
 146                 }
 147                 return $str;
 148         }
 149
 150         function compare()
 151         {
 152                 $this->m = count($this->arr1);
 153                 $this->n = count($this->arr2);
 154
 155                 if ($this->m == 0 || $this->n == 0) { // No need to compare
 156                         $this->result = array(array('x'=>0, 'y'=>0));
 157                         return;
 158                 }
 159
 160                 // Sentinel
 161                 array_unshift($this->arr1, new DiffLine(''));
 162                 $this->m++;
 163                 array_unshift($this->arr2, new DiffLine(''));
 164                 $this->n++;
 165
 166                 $this->reverse = ($this->n < $this->m);
 167                 if ($this->reverse) {
 168                         // Swap
 169                         $tmp = $this->m; $this->m = $this->n; $this->n = $tmp;
 170                         $tmp = $this->arr1; $this->arr1 = $this->arr2; $this->arr2 = $tmp;
 171                         unset($tmp);
 172                 }
 173
 174                 $delta = $this->n - $this->m; // Must be >=0;
 175
 176                 $fp = array();
 177                 $this->path = array();
 178
 179                 for ($p = -($this->m + 1); $p <= ($this->n + 1); $p++) {
 180                         $fp[$p] = -1;
 181                         $this->path[$p] = array();
 182                 }
 183
 184                 for ($p = 0;; $p++) {
 185                         for ($k = -$p; $k <= $delta - 1; $k++) {
 186                                 $fp[$k] = $this->snake($k, $fp[$k - 1], $fp[$k + 1]);
 187                         }
 188                         for ($k = $delta + $p; $k >= $delta + 1; $k--) {
 189                                 $fp[$k] = $this->snake($k, $fp[$k - 1], $fp[$k + 1]);
 190                         }
 191                         $fp[$delta] = $this->snake($delta, $fp[$delta - 1], $fp[$delta + 1]);
 192                         if ($fp[$delta] >= $this->n) {
 193                                 $this->pos = $this->path[$delta]; // 経路を決定
 194                                 return;
 195                         }
 196                 }
 197         }
 198
 199         function snake($k, $y1, $y2)
 200         {
 201                 if ($y1 >= $y2) {
 202                         $_k = $k - 1;
 203                         $y = $y1 + 1;
 204                 } else {
 205                         $_k = $k + 1;
 206                         $y = $y2;
 207                 }
 208                 $this->path[$k] = $this->path[$_k];// ここまでの経路をコピー
 209                 $x = $y - $k;
 210                 while ((($x + 1) < $this->m) && (($y + 1) < $this->n)
 211                         and $this->arr1[$x + 1]->compare($this->arr2[$y + 1]))
 212                 {
 213                         ++$x; ++$y;
 214                         $this->path[$k][] = array('x'=>$x, 'y'=>$y); // 経路を追加
 215                 }
 216                 return $y;
 217         }
 218
 219         function toArray()
 220         {
 221                 $arr = array();
 222                 if ($this->reverse) { // 姑息な…
 223                         $_x = 'y'; $_y = 'x'; $_m = $this->n; $arr1 =& $this->arr2; $arr2 =& $this->arr1;
 224                 } else {
 225                         $_x = 'x'; $_y = 'y'; $_m = $this->m; $arr1 =& $this->arr1; $arr2 =& $this->arr2;
 226                 }
 227
 228                 $x = $y = 1;
 229                 $this->add_count = $this->delete_count = 0;
 230                 $this->pos[] = array('x'=>$this->m, 'y'=>$this->n); // Sentinel
 231                 foreach ($this->pos as $pos) {
 232                         $this->delete_count += ($pos[$_x] - $x);
 233                         $this->add_count    += ($pos[$_y] - $y);
 234
 235                         while ($pos[$_x] > $x) {
 236                                 $arr1[$x]->set($this->key, $this->minus);
 237                                 $arr[] = $arr1[$x++];
 238                         }
 239
 240                         while ($pos[$_y] > $y) {
 241                                 $arr2[$y]->set($this->key, $this->plus);
 242                                 $arr[] =  $arr2[$y++];
 243                         }
 244
 245                         if ($x < $_m) {
 246                                 $arr1[$x]->merge($arr2[$y]);
 247                                 $arr1[$x]->set($this->key, $this->equal);
 248                                 $arr[] = $arr1[$x];
 249                         }
 250                         ++$x; ++$y;
 251                 }
 252                 return $arr;
 253         }
 254 }
 255
 256 class DiffLine
 257 {
 258         var $text;
 259         var $status;
 260
 261         function DiffLine($text)
 262         {
 263                 $this->__construct($text);
 264         }
 265         function __construct($text)
 266         {
 267                 $this->text   = $text . "\n";
 268                 $this->status = array();
 269         }
 270
 271         function compare($obj)
 272         {
 273                 return $this->text == $obj->text;
 274         }
 275
 276         function set($key, $status)
 277         {
 278                 $this->status[$key] = $status;
 279         }
 280
 281         function get($key)
 282         {
 283                 return isset($this->status[$key]) ? $this->status[$key] : '';
 284         }
 285
 286         function merge($obj)
 287         {
 288                 $this->status += $obj->status;
 289         }
 290
 291         function text()
 292         {
 293                 return $this->text;
 294         }
 295 }