[Summary view] [Print] [Text view]

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