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