wp-includes/Text/Diff.php

   1 <?php
   2 /**
   3  * General API for generating and formatting diffs - the differences between
   4  * two sequences of strings.
   5  *
   6  * The original PHP version of this code was written by Geoffrey T. Dairiki
   7  * <dairiki@dairiki.org>, and is used/adapted with his permission.
   8  *
   9  * Copyright 2004 Geoffrey T. Dairiki <dairiki@dairiki.org>
  10  * Copyright 2004-2010 The Horde Project (http://www.horde.org/)
  11  *
  12  * See the enclosed file COPYING for license information (LGPL). If you did
  13  * not receive this file, see http://opensource.org/licenses/lgpl-license.php.
  14  *
  15  * @package Text_Diff
  16  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
  17  */
  18 class Text_Diff {
  19
  20     /**
  21      * Array of changes.
  22      *
  23      * @var array
  24      */
  25     var $_edits;
  26
  27     /**
  28      * Computes diffs between sequences of strings.
  29      *
  30      * @param string $engine     Name of the diffing engine to use.  'auto'
  31      *                           will automatically select the best.
  32      * @param array $params      Parameters to pass to the diffing engine.
  33      *                           Normally an array of two arrays, each
  34      *                           containing the lines from a file.
  35      */
  36     function Text_Diff($engine, $params)
  37     {
  38         // Backward compatibility workaround.
  39         if (!is_string($engine)) {
  40             $params = array($engine, $params);
  41             $engine = 'auto';
  42         }
  43
  44         if ($engine == 'auto') {
  45             $engine = extension_loaded('xdiff') ? 'xdiff' : 'native';
  46         } else {
  47             $engine = basename($engine);
  48         }
  49
  50         // WP #7391
  51         require_once dirname(__FILE__).'/Diff/Engine/' . $engine . '.php';
  52         $class = 'Text_Diff_Engine_' . $engine;
  53         $diff_engine = new $class();
  54
  55         $this->_edits = call_user_func_array(array($diff_engine, 'diff'), $params);
  56     }
  57
  58     /**
  59      * Returns the array of differences.
  60      */
  61     function getDiff()
  62     {
  63         return $this->_edits;
  64     }
  65
  66     /**
  67      * returns the number of new (added) lines in a given diff.
  68      *
  69      * @since Text_Diff 1.1.0
  70      *
  71      * @return integer The number of new lines
  72      */
  73     function countAddedLines()
  74     {
  75         $count = 0;
  76         foreach ($this->_edits as $edit) {
  77             if (is_a($edit, 'Text_Diff_Op_add') ||
  78                 is_a($edit, 'Text_Diff_Op_change')) {
  79                 $count += $edit->nfinal();
  80             }
  81         }
  82         return $count;
  83     }
  84
  85     /**
  86      * Returns the number of deleted (removed) lines in a given diff.
  87      *
  88      * @since Text_Diff 1.1.0
  89      *
  90      * @return integer The number of deleted lines
  91      */
  92     function countDeletedLines()
  93     {
  94         $count = 0;
  95         foreach ($this->_edits as $edit) {
  96             if (is_a($edit, 'Text_Diff_Op_delete') ||
  97                 is_a($edit, 'Text_Diff_Op_change')) {
  98                 $count += $edit->norig();
  99             }
 100         }
 101         return $count;
 102     }
 103
 104     /**
 105      * Computes a reversed diff.
 106      *
 107      * Example:
 108      * <code>
 109      * $diff = new Text_Diff($lines1, $lines2);
 110      * $rev = $diff->reverse();
 111      * </code>
 112      *
 113      * @return Text_Diff  A Diff object representing the inverse of the
 114      *                    original diff.  Note that we purposely don't return a
 115      *                    reference here, since this essentially is a clone()
 116      *                    method.
 117      */
 118     function reverse()
 119     {
 120         if (version_compare(zend_version(), '2', '>')) {
 121             $rev = clone($this);
 122         } else {
 123             $rev = $this;
 124         }
 125         $rev->_edits = array();
 126         foreach ($this->_edits as $edit) {
 127             $rev->_edits[] = $edit->reverse();
 128         }
 129         return $rev;
 130     }
 131
 132     /**
 133      * Checks for an empty diff.
 134      *
 135      * @return boolean  True if two sequences were identical.
 136      */
 137     function isEmpty()
 138     {
 139         foreach ($this->_edits as $edit) {
 140             if (!is_a($edit, 'Text_Diff_Op_copy')) {
 141                 return false;
 142             }
 143         }
 144         return true;
 145     }
 146
 147     /**
 148      * Computes the length of the Longest Common Subsequence (LCS).
 149      *
 150      * This is mostly for diagnostic purposes.
 151      *
 152      * @return integer  The length of the LCS.
 153      */
 154     function lcs()
 155     {
 156         $lcs = 0;
 157         foreach ($this->_edits as $edit) {
 158             if (is_a($edit, 'Text_Diff_Op_copy')) {
 159                 $lcs += count($edit->orig);
 160             }
 161         }
 162         return $lcs;
 163     }
 164
 165     /**
 166      * Gets the original set of lines.
 167      *
 168      * This reconstructs the $from_lines parameter passed to the constructor.
 169      *
 170      * @return array  The original sequence of strings.
 171      */
 172     function getOriginal()
 173     {
 174         $lines = array();
 175         foreach ($this->_edits as $edit) {
 176             if ($edit->orig) {
 177                 array_splice($lines, count($lines), 0, $edit->orig);
 178             }
 179         }
 180         return $lines;
 181     }
 182
 183     /**
 184      * Gets the final set of lines.
 185      *
 186      * This reconstructs the $to_lines parameter passed to the constructor.
 187      *
 188      * @return array  The sequence of strings.
 189      */
 190     function getFinal()
 191     {
 192         $lines = array();
 193         foreach ($this->_edits as $edit) {
 194             if ($edit->final) {
 195                 array_splice($lines, count($lines), 0, $edit->final);
 196             }
 197         }
 198         return $lines;
 199     }
 200
 201     /**
 202      * Removes trailing newlines from a line of text. This is meant to be used
 203      * with array_walk().
 204      *
 205      * @param string $line  The line to trim.
 206      * @param integer $key  The index of the line in the array. Not used.
 207      */
 208     function trimNewlines(&$line, $key)
 209     {
 210         $line = str_replace(array("\n", "\r"), '', $line);
 211     }
 212
 213     /**
 214      * Determines the location of the system temporary directory.
 215      *
 216      * @static
 217      *
 218      * @access protected
 219      *
 220      * @return string  A directory name which can be used for temp files.
 221      *                 Returns false if one could not be found.
 222      */
 223     function _getTempDir()
 224     {
 225         $tmp_locations = array('/tmp', '/var/tmp', 'c:\WUTemp', 'c:\temp',
 226                                'c:\windows\temp', 'c:\winnt\temp');
 227
 228         /* Try PHP's upload_tmp_dir directive. */
 229         $tmp = ini_get('upload_tmp_dir');
 230
 231         /* Otherwise, try to determine the TMPDIR environment variable. */
 232         if (!strlen($tmp)) {
 233             $tmp = getenv('TMPDIR');
 234         }
 235
 236         /* If we still cannot determine a value, then cycle through a list of
 237          * preset possibilities. */
 238         while (!strlen($tmp) && count($tmp_locations)) {
 239             $tmp_check = array_shift($tmp_locations);
 240             if (@is_dir($tmp_check)) {
 241                 $tmp = $tmp_check;
 242             }
 243         }
 244
 245         /* If it is still empty, we have failed, so return false; otherwise
 246          * return the directory determined. */
 247         return strlen($tmp) ? $tmp : false;
 248     }
 249
 250     /**
 251      * Checks a diff for validity.
 252      *
 253      * This is here only for debugging purposes.
 254      */
 255     function _check($from_lines, $to_lines)
 256     {
 257         if (serialize($from_lines) != serialize($this->getOriginal())) {
 258             trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
 259         }
 260         if (serialize($to_lines) != serialize($this->getFinal())) {
 261             trigger_error("Reconstructed final doesn't match", E_USER_ERROR);
 262         }
 263
 264         $rev = $this->reverse();
 265         if (serialize($to_lines) != serialize($rev->getOriginal())) {
 266             trigger_error("Reversed original doesn't match", E_USER_ERROR);
 267         }
 268         if (serialize($from_lines) != serialize($rev->getFinal())) {
 269             trigger_error("Reversed final doesn't match", E_USER_ERROR);
 270         }
 271
 272         $prevtype = null;
 273         foreach ($this->_edits as $edit) {
 274             if ($prevtype == get_class($edit)) {
 275                 trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
 276             }
 277             $prevtype = get_class($edit);
 278         }
 279
 280         return true;
 281     }
 282
 283 }
 284
 285 /**
 286  * @package Text_Diff
 287  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 288  */
 289 class Text_MappedDiff extends Text_Diff {
 290
 291     /**
 292      * Computes a diff between sequences of strings.
 293      *
 294      * This can be used to compute things like case-insensitve diffs, or diffs
 295      * which ignore changes in white-space.
 296      *
 297      * @param array $from_lines         An array of strings.
 298      * @param array $to_lines           An array of strings.
 299      * @param array $mapped_from_lines  This array should have the same size
 300      *                                  number of elements as $from_lines.  The
 301      *                                  elements in $mapped_from_lines and
 302      *                                  $mapped_to_lines are what is actually
 303      *                                  compared when computing the diff.
 304      * @param array $mapped_to_lines    This array should have the same number
 305      *                                  of elements as $to_lines.
 306      */
 307     function Text_MappedDiff($from_lines, $to_lines,
 308                              $mapped_from_lines, $mapped_to_lines)
 309     {
 310         assert(count($from_lines) == count($mapped_from_lines));
 311         assert(count($to_lines) == count($mapped_to_lines));
 312
 313         parent::Text_Diff($mapped_from_lines, $mapped_to_lines);
 314
 315         $xi = $yi = 0;
 316         for ($i = 0; $i < count($this->_edits); $i++) {
 317             $orig = &$this->_edits[$i]->orig;
 318             if (is_array($orig)) {
 319                 $orig = array_slice($from_lines, $xi, count($orig));
 320                 $xi += count($orig);
 321             }
 322
 323             $final = &$this->_edits[$i]->final;
 324             if (is_array($final)) {
 325                 $final = array_slice($to_lines, $yi, count($final));
 326                 $yi += count($final);
 327             }
 328         }
 329     }
 330
 331 }
 332
 333 /**
 334  * @package Text_Diff
 335  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 336  *
 337  * @access private
 338  */
 339 class Text_Diff_Op {
 340
 341     var $orig;
 342     var $final;
 343
 344     function &reverse()
 345     {
 346         trigger_error('Abstract method', E_USER_ERROR);
 347     }
 348
 349     function norig()
 350     {
 351         return $this->orig ? count($this->orig) : 0;
 352     }
 353
 354     function nfinal()
 355     {
 356         return $this->final ? count($this->final) : 0;
 357     }
 358
 359 }
 360
 361 /**
 362  * @package Text_Diff
 363  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 364  *
 365  * @access private
 366  */
 367 class Text_Diff_Op_copy extends Text_Diff_Op {
 368
 369     function Text_Diff_Op_copy($orig, $final = false)
 370     {
 371         if (!is_array($final)) {
 372             $final = $orig;
 373         }
 374         $this->orig = $orig;
 375         $this->final = $final;
 376     }
 377
 378     function &reverse()
 379     {
 380         $reverse = &new Text_Diff_Op_copy($this->final, $this->orig);
 381         return $reverse;
 382     }
 383
 384 }
 385
 386 /**
 387  * @package Text_Diff
 388  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 389  *
 390  * @access private
 391  */
 392 class Text_Diff_Op_delete extends Text_Diff_Op {
 393
 394     function Text_Diff_Op_delete($lines)
 395     {
 396         $this->orig = $lines;
 397         $this->final = false;
 398     }
 399
 400     function &reverse()
 401     {
 402         $reverse = &new Text_Diff_Op_add($this->orig);
 403         return $reverse;
 404     }
 405
 406 }
 407
 408 /**
 409  * @package Text_Diff
 410  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 411  *
 412  * @access private
 413  */
 414 class Text_Diff_Op_add extends Text_Diff_Op {
 415
 416     function Text_Diff_Op_add($lines)
 417     {
 418         $this->final = $lines;
 419         $this->orig = false;
 420     }
 421
 422     function &reverse()
 423     {
 424         $reverse = &new Text_Diff_Op_delete($this->final);
 425         return $reverse;
 426     }
 427
 428 }
 429
 430 /**
 431  * @package Text_Diff
 432  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 433  *
 434  * @access private
 435  */
 436 class Text_Diff_Op_change extends Text_Diff_Op {
 437
 438     function Text_Diff_Op_change($orig, $final)
 439     {
 440         $this->orig = $orig;
 441         $this->final = $final;
 442     }
 443
 444     function &reverse()
 445     {
 446         $reverse = &new Text_Diff_Op_change($this->final, $this->orig);
 447         return $reverse;
 448     }
 449
 450 }