[Summary view] [Print] [Text view]

   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      static 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  }