widgets/wiki_main/include/lib/diff.php

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