include/libs/diff/class.simplediff.php

   1 <?php
   2
   3 /*
   4     Simple diff library, using diff php implementation by nils
   5     Copyleft (C) 2009 BohwaZ - http://bohwaz.net/
   6
   7     This program is free software; you can redistribute it and/or
   8     modify it under the terms of the GNU General Public License
   9     as published by the Free Software Foundation; version 3
  10     of the License.
  11
  12     This program is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with this program; if not, write to the Free Software
  19     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  20
  21     http://www.gnu.org/licenses/gpl.html
  22 */
  23
  24 class simpleDiff
  25 {
  26     const SAME = 0;
  27     const INS = 1;
  28     const DEL = -1;
  29     const CHANGED = 2;
  30
  31     /**
  32      * Generates a normal diff (like GNU diff utility)
  33      *
  34      * @param string $old Old text to compare (could be an array of lines)
  35      * @param string $new New text to compare (could be an array of lines)
  36      * @param bool $return_as_array Returns the diff as an array
  37      */
  38     static public function diff($old, $new, $return_as_array = false)
  39     {
  40         /**
  41             Diff implemented in pure php, written from scratch.
  42             Copyright (C) 2003  Daniel Unterberger <diff.phpnet@holomind.de>
  43             Copyright (C) 2005  Nils Knappmeier next version
  44
  45             This program is free software; you can redistribute it and/or
  46             modify it under the terms of the GNU General Public License
  47             as published by the Free Software Foundation; either version 2
  48             of the License, or (at your option) any later version.
  49
  50             This program is distributed in the hope that it will be useful,
  51             but WITHOUT ANY WARRANTY; without even the implied warranty of
  52             MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  53             GNU General Public License for more details.
  54
  55             You should have received a copy of the GNU General Public License
  56             along with this program; if not, write to the Free Software
  57             Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  58
  59             http://www.gnu.org/licenses/gpl.html
  60
  61             About:
  62             I searched a function to compare arrays and the array_diff()
  63             was not specific enough. It ignores the order of the array-values.
  64             So I reimplemented the diff-function which is found on unix-systems
  65             but this you can use directly in your code and adopt for your needs.
  66             Simply adopt the formatline-function. with the third-parameter of arr_diff()
  67             you can hide matching lines. Hope someone has use for this.
  68
  69             Contact: d.u.diff@holomind.de <daniel unterberger>
  70         **/
  71
  72         # split the source text into arrays of lines
  73         if (is_array($old))
  74             $t1 = $old;
  75         else
  76             $t1 = explode("\n",$old);
  77
  78         $x = array_pop($t1);
  79         if ($x>'') $t1[]="$x\n\\ No newline at end of file";
  80
  81         if (is_array($new))
  82             $t2 = $new;
  83         else
  84             $t2 = explode("\n",$new);
  85
  86         $x=array_pop($t2);
  87         if ($x>'') $t2[]="$x\n\\ No newline at end of file";
  88
  89         # build a reverse-index array using the line as key and line number as value
  90         # don't store blank lines, so they won't be targets of the shortest distance
  91         # search
  92         foreach($t1 as $i=>$x)
  93         {
  94             if ($x>'') $r1[$x][]=$i;
  95         }
  96         foreach($t2 as $i=>$x) if ($x>'') $r2[$x][]=$i;
  97
  98         $a1=0; $a2=0;   # start at beginning of each list
  99         $actions=array();
 100
 101         # walk this loop until we reach the end of one of the lists
 102         while ($a1<count($t1) && $a2<count($t2)) {
 103             # if we have a common element, save it and go to the next
 104             if ($t1[$a1]==$t2[$a2]) { $actions[]=4; $a1++; $a2++; continue; }
 105
 106             # otherwise, find the shortest move (Manhattan-distance) from the
 107             # current location
 108             $best1=count($t1); $best2=count($t2);
 109             $s1=$a1; $s2=$a2;
 110             while(($s1+$s2-$a1-$a2) < ($best1+$best2-$a1-$a2)) {
 111                 $d=-1;
 112                 if (isset($t2[$s2]) && isset($r1[$t2[$s2]]))
 113                 {
 114                     foreach((array)@$r1[$t2[$s2]] as $n)
 115                     {
 116                         if ($n>=$s1) { $d=$n; break; }
 117                     }
 118                 }
 119                 if ($d>=$s1 && ($d+$s2-$a1-$a2)<($best1+$best2-$a1-$a2))
 120                 { $best1=$d; $best2=$s2; }
 121                 $d=-1;
 122                 if (isset($t1[$s1]) && isset($r2[$t1[$s1]]))
 123                 {
 124                     foreach((array)@$r2[$t1[$s1]] as $n)
 125                     {
 126                         if ($n>=$s2) { $d=$n; break; }
 127                     }
 128                 }
 129                 if ($d>=$s2 && ($s1+$d-$a1-$a2)<($best1+$best2-$a1-$a2))
 130                 { $best1=$s1; $best2=$d; }
 131                 $s1++; $s2++;
 132             }
 133             while ($a1<$best1) { $actions[]=1; $a1++; }  # deleted elements
 134             while ($a2<$best2) { $actions[]=2; $a2++; }  # added elements
 135         }
 136
 137         # we've reached the end of one list, now walk to the end of the other
 138         while($a1<count($t1)) { $actions[]=1; $a1++; }  # deleted elements
 139         while($a2<count($t2)) { $actions[]=2; $a2++; }  # added elements
 140
 141         # and this marks our ending point
 142         $actions[]=8;
 143
 144         # now, let's follow the path we just took and report the added/deleted
 145         # elements into $out.
 146         $op = 0;
 147         $x0=$x1=0; $y0=$y1=0;
 148         $out = array();
 149         foreach($actions as $act) {
 150             if ($act==1) { $op|=$act; $x1++; continue; }
 151             if ($act==2) { $op|=$act; $y1++; continue; }
 152             if ($op>0) {
 153                 $xstr = ($x1==($x0+1)) ? $x1 : ($x0+1).",$x1";
 154                 $ystr = ($y1==($y0+1)) ? $y1 : ($y0+1).",$y1";
 155                 if ($op==1) $out[] = "{$xstr}d{$y1}";
 156                 elseif ($op==3) $out[] = "{$xstr}c{$ystr}";
 157                 while ($x0<$x1) { $out[] = '< '.$t1[$x0]; $x0++; }   # deleted elems
 158                 if ($op==2) $out[] = "{$x1}a{$ystr}";
 159                 elseif ($op==3) $out[] = '---';
 160                 while ($y0<$y1) { $out[] = '> '.$t2[$y0]; $y0++; }   # added elems
 161             }
 162             $x1++; $x0=$x1;
 163             $y1++; $y0=$y1;
 164             $op=0;
 165         }
 166         $out[] = '';
 167
 168         if ($return_as_array)
 169             return $out;
 170         else
 171             return implode("\n",$out);
 172     }
 173
 174     /**
 175      * Applies a diff to a text
 176      *
 177      * @param string $original Original text to patch
 178      * @param string $patch Diff text
 179      * @param bool $return_as_array Returns the patched text as an array
 180      */
 181     static public function patch($original, $patch, $return_as_array = false)
 182     {
 183         $new = array();
 184
 185         if (!is_array($patch))
 186             $patch = explode("\n", $patch);
 187
 188         if (!is_array($original))
 189             $original = explode("\n", str_replace("\r", "", $original));
 190
 191         $i = 0;
 192         foreach ($patch as $line)
 193         {
 194             if (empty($line))
 195                 continue;
 196
 197             $line = str_replace("\n\\ No newline at end of file", "", $line);
 198
 199             if ($line[0] == '>')
 200             {
 201                 $new[] = substr($line, 2);
 202             }
 203             elseif (preg_match('!^(?P<ob>[0-9]+)(?:,(?P<oe>[0-9]+))?(?P<mode>[acd])(?P<nb>[0-9]+)(?:,(?<ne>[0-9]+))?$!', trim($line), $match))
 204             {
 205                 $sub = ($match['mode'] == 'a') ? 0 : 1;
 206                 for ($a = $i; $a < ($match['ob'] - $sub); $a++)
 207                 {
 208                     $new[] = $original[$a];
 209                 }
 210                 $i = $match['oe'] ? (int) $match['oe'] : (int) $match['ob'];
 211             }
 212         }
 213         for ($a = $i; $a < count($original); $a++)
 214         {
 215             $new[] = $original[$a];
 216         }
 217
 218         return $return_as_array ? $new : implode("\n", $new);
 219     }
 220
 221     /**
 222      * Returns an array showing differences between two arrays
 223      *
 224      * @param string $diff Diff text, set to false and the diff will be made from $old and $new
 225      * @param string $old Old text
 226      * @param string $new New text, could be set to false if the diff is supplied
 227      * @param bool $show_context Include context in the array? Set to false to avoid context,
 228         set to true to have all the context and set to an (int) to have this number of lines of
 229         context before and after each modified line
 230      */
 231     static public function diff_to_array($diff = false, $old, $new = false, $show_context = true)
 232     {
 233         if ($diff === false && $new === false)
 234         {
 235             throw new Exception("diff_to_array needs either the diff text or the new text file");
 236         }
 237
 238         if ($diff === false)
 239         {
 240             $diff = self::diff($old, $new, true);
 241         }
 242
 243         if (!is_array($diff))
 244             $old = explode("\n", $diff);
 245
 246         if (!is_array($old))
 247             $old = explode("\n", $old);
 248
 249         if ($new === false)
 250             $new = self::patch($old, $diff, true);
 251
 252         if (!is_array($new))
 253             $new = explode("\n", $new);
 254
 255         $left = $right = $context = array();
 256         $max_lines = max(count($new), count($old));
 257
 258         // Creating an array of changed lines for left and right texts
 259         foreach ($diff as $line)
 260         {
 261             if (preg_match('!^(?P<ob>[0-9]+)(?:,(?P<oe>[0-9]+))?(?P<mode>[acd])(?P<nb>[0-9]+)(?:,(?<ne>[0-9]+))?$!', trim($line), $match))
 262             {
 263                 if (empty($match['oe']))
 264                     $match['oe'] = $match['ob'];
 265
 266                 if (empty($match['ne']))
 267                     $match['ne'] = $match['nb'];
 268
 269                 if ($match['mode'] == 'a')
 270                 {
 271                     for ($i = $match['nb']; $i <= $match['ne']; $i++)
 272                     {
 273                         $right[$i - 1] = true;
 274                         $max_lines++;
 275                     }
 276                 }
 277                 elseif ($match['mode'] == 'd')
 278                 {
 279                     for ($i = $match['ob']; $i <= $match['oe']; $i++)
 280                     {
 281                         $left[$i - 1] = true;
 282                         $max_lines++;
 283                     }
 284                 }
 285                 else
 286                 {
 287                     for ($i = $match['nb']; $i <= $match['ne']; $i++)
 288                     {
 289                         $right[$i - 1] = true;
 290                     }
 291                     for ($i = $match['ob']; $i <= $match['oe']; $i++)
 292                     {
 293                         $left[$i - 1] = true;
 294                     }
 295                 }
 296
 297                 if ($show_context && $show_context !== true)
 298                 {
 299                     $min = $match['ob'] - (int) $show_context;
 300                     if ($min < 1) $min = 1;
 301                     $max = $match['oe'] + (int) $show_context;
 302                     if ($max > count($new)) $max = count($new);
 303
 304                     for ($i = $min; $i <= $max; $i++)
 305                     {
 306                         $context[$i - 1] = true;
 307                     }
 308                 }
 309             }
 310         }
 311
 312         $out = array();
 313
 314         $left_index = 0;
 315         $right_index = 0;
 316         $i = 0;
 317
 318         // Then we can compile this to an array of changed things
 319         while ($i < $max_lines)
 320         {
 321             $row = array();
 322
 323             // Line present in left but not in right ? deleted
 324             if (isset($left[$left_index]) && !isset($right[$right_index]))
 325             {
 326                 $row = array(self::DEL, $old[$left_index], '');
 327                 $left_index++;
 328             }
 329             // Line present in right but not in left ? added
 330             elseif (isset($right[$right_index]) && !isset($left[$left_index]))
 331             {
 332                 $row = array(self::INS, '', $new[$right_index]);
 333                 $right_index++;
 334             }
 335             else
 336             {
 337                 // Changed line
 338                 if (isset($left[$left_index]) && isset($right[$right_index]))
 339                 {
 340                     $row = array(self::CHANGED, $old[$left_index], $new[$right_index]);
 341                 }
 342                 // Or nothing happened
 343                 else
 344                 {
 345                     // We want all the context, ok
 346                     if ($show_context === true || isset($context[$left_index]))
 347                     {
 348                         $l = isset($old[$left_index]) ? $old[$left_index] : '';
 349                         $r = isset($new[$right_index]) ? $new[$right_index] : '';
 350                         $row = array(self::SAME, $l, $r);
 351                     }
 352                 }
 353
 354                 $right_index++;
 355                 $left_index++;
 356             }
 357
 358             $i++;
 359
 360             if (!empty($row))
 361             {
 362                 $out[($i - 1)] = $row;
 363             }
 364         }
 365
 366         return $out;
 367     }
 368
 369     /**
 370      * Generates a word-diff, like the GNU wdiff utility (kind of)
 371      *
 372      * @param string $old Left right to compare
 373      * @param string $new Right line to compare
 374      * @param string $union Union string to assemble words (default is whitespace)
 375      */
 376     static public function wdiff($old, $new, $union = ' ')
 377     {
 378         $diff = self::diff_to_array(false, explode(' ', $old), explode(' ', $new));
 379         $out = '';
 380
 381         foreach ($diff as $line)
 382         {
 383             list ($change, $old, $new) = $line;
 384
 385             if ($change == self::CHANGED)
 386             {
 387                 $out .= '[-' . $old . '-]';
 388                 $out .= $union;
 389                 $out .= '{+' . $new . '+}';
 390             }
 391             elseif ($change == self::DEL)
 392             {
 393                 $out .= '[-' . $old . '-]';
 394             }
 395             elseif ($change == self::INS)
 396             {
 397                 $out .= '{+' . $new . '+}';
 398             }
 399             else
 400             {
 401                 $out .= $old;
 402             }
 403
 404             $out .= $union;
 405         }
 406
 407         $out = str_replace('+}' . $union . '{+', ' ', $out);
 408         $out = str_replace('-]' . $union . '[-', ' ', $out);
 409
 410         return $out;
 411     }
 412 }
 413
 414 ?>