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 __construct( $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          * PHP4 constructor.
  60          */
  61         public function Text_Diff( $engine, $params ) {
  62                 self::__construct( $engine, $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      *
  78      * @return integer The number of new lines
  79      */
  80     function countAddedLines()
  81     {
  82         $count = 0;
  83         foreach ($this->_edits as $edit) {
  84             if (is_a($edit, 'Text_Diff_Op_add') ||
  85                 is_a($edit, 'Text_Diff_Op_change')) {
  86                 $count += $edit->nfinal();
  87             }
  88         }
  89         return $count;
  90     }
  91
  92     /**
  93      * Returns the number of deleted (removed) lines in a given diff.
  94      *
  95      * @since Text_Diff 1.1.0
  96      *
  97      * @return integer The number of deleted lines
  98      */
  99     function countDeletedLines()
 100     {
 101         $count = 0;
 102         foreach ($this->_edits as $edit) {
 103             if (is_a($edit, 'Text_Diff_Op_delete') ||
 104                 is_a($edit, 'Text_Diff_Op_change')) {
 105                 $count += $edit->norig();
 106             }
 107         }
 108         return $count;
 109     }
 110
 111     /**
 112      * Computes a reversed diff.
 113      *
 114      * Example:
 115      * <code>
 116      * $diff = new Text_Diff($lines1, $lines2);
 117      * $rev = $diff->reverse();
 118      * </code>
 119      *
 120      * @return Text_Diff  A Diff object representing the inverse of the
 121      *                    original diff.  Note that we purposely don't return a
 122      *                    reference here, since this essentially is a clone()
 123      *                    method.
 124      */
 125     function reverse()
 126     {
 127         if (version_compare(zend_version(), '2', '>')) {
 128             $rev = clone($this);
 129         } else {
 130             $rev = $this;
 131         }
 132         $rev->_edits = array();
 133         foreach ($this->_edits as $edit) {
 134             $rev->_edits[] = $edit->reverse();
 135         }
 136         return $rev;
 137     }
 138
 139     /**
 140      * Checks for an empty diff.
 141      *
 142      * @return boolean  True if two sequences were identical.
 143      */
 144     function isEmpty()
 145     {
 146         foreach ($this->_edits as $edit) {
 147             if (!is_a($edit, 'Text_Diff_Op_copy')) {
 148                 return false;
 149             }
 150         }
 151         return true;
 152     }
 153
 154     /**
 155      * Computes the length of the Longest Common Subsequence (LCS).
 156      *
 157      * This is mostly for diagnostic purposes.
 158      *
 159      * @return integer  The length of the LCS.
 160      */
 161     function lcs()
 162     {
 163         $lcs = 0;
 164         foreach ($this->_edits as $edit) {
 165             if (is_a($edit, 'Text_Diff_Op_copy')) {
 166                 $lcs += count($edit->orig);
 167             }
 168         }
 169         return $lcs;
 170     }
 171
 172     /**
 173      * Gets the original set of lines.
 174      *
 175      * This reconstructs the $from_lines parameter passed to the constructor.
 176      *
 177      * @return array  The original sequence of strings.
 178      */
 179     function getOriginal()
 180     {
 181         $lines = array();
 182         foreach ($this->_edits as $edit) {
 183             if ($edit->orig) {
 184                 array_splice($lines, count($lines), 0, $edit->orig);
 185             }
 186         }
 187         return $lines;
 188     }
 189
 190     /**
 191      * Gets the final set of lines.
 192      *
 193      * This reconstructs the $to_lines parameter passed to the constructor.
 194      *
 195      * @return array  The sequence of strings.
 196      */
 197     function getFinal()
 198     {
 199         $lines = array();
 200         foreach ($this->_edits as $edit) {
 201             if ($edit->final) {
 202                 array_splice($lines, count($lines), 0, $edit->final);
 203             }
 204         }
 205         return $lines;
 206     }
 207
 208     /**
 209      * Removes trailing newlines from a line of text. This is meant to be used
 210      * with array_walk().
 211      *
 212      * @param string $line  The line to trim.
 213      * @param integer $key  The index of the line in the array. Not used.
 214      */
 215     static function trimNewlines(&$line, $key)
 216     {
 217         $line = str_replace(array("\n", "\r"), '', $line);
 218     }
 219
 220     /**
 221      * Determines the location of the system temporary directory.
 222      *
 223      * @static
 224      *
 225      * @access protected
 226      *
 227      * @return string  A directory name which can be used for temp files.
 228      *                 Returns false if one could not be found.
 229      */
 230     function _getTempDir()
 231     {
 232         $tmp_locations = array('/tmp', '/var/tmp', 'c:\WUTemp', 'c:\temp',
 233                                'c:\windows\temp', 'c:\winnt\temp');
 234
 235         /* Try PHP's upload_tmp_dir directive. */
 236         $tmp = ini_get('upload_tmp_dir');
 237
 238         /* Otherwise, try to determine the TMPDIR environment variable. */
 239         if (!strlen($tmp)) {
 240             $tmp = getenv('TMPDIR');
 241         }
 242
 243         /* If we still cannot determine a value, then cycle through a list of
 244          * preset possibilities. */
 245         while (!strlen($tmp) && count($tmp_locations)) {
 246             $tmp_check = array_shift($tmp_locations);
 247             if (@is_dir($tmp_check)) {
 248                 $tmp = $tmp_check;
 249             }
 250         }
 251
 252         /* If it is still empty, we have failed, so return false; otherwise
 253          * return the directory determined. */
 254         return strlen($tmp) ? $tmp : false;
 255     }
 256
 257     /**
 258      * Checks a diff for validity.
 259      *
 260      * This is here only for debugging purposes.
 261      */
 262     function _check($from_lines, $to_lines)
 263     {
 264         if (serialize($from_lines) != serialize($this->getOriginal())) {
 265             trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
 266         }
 267         if (serialize($to_lines) != serialize($this->getFinal())) {
 268             trigger_error("Reconstructed final doesn't match", E_USER_ERROR);
 269         }
 270
 271         $rev = $this->reverse();
 272         if (serialize($to_lines) != serialize($rev->getOriginal())) {
 273             trigger_error("Reversed original doesn't match", E_USER_ERROR);
 274         }
 275         if (serialize($from_lines) != serialize($rev->getFinal())) {
 276             trigger_error("Reversed final doesn't match", E_USER_ERROR);
 277         }
 278
 279         $prevtype = null;
 280         foreach ($this->_edits as $edit) {
 281             if ($prevtype == get_class($edit)) {
 282                 trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
 283             }
 284             $prevtype = get_class($edit);
 285         }
 286
 287         return true;
 288     }
 289
 290 }
 291
 292 /**
 293  * @package Text_Diff
 294  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 295  */
 296 class Text_MappedDiff extends Text_Diff {
 297
 298     /**
 299      * Computes a diff between sequences of strings.
 300      *
 301      * This can be used to compute things like case-insensitve diffs, or diffs
 302      * which ignore changes in white-space.
 303      *
 304      * @param array $from_lines         An array of strings.
 305      * @param array $to_lines           An array of strings.
 306      * @param array $mapped_from_lines  This array should have the same size
 307      *                                  number of elements as $from_lines.  The
 308      *                                  elements in $mapped_from_lines and
 309      *                                  $mapped_to_lines are what is actually
 310      *                                  compared when computing the diff.
 311      * @param array $mapped_to_lines    This array should have the same number
 312      *                                  of elements as $to_lines.
 313      */
 314     function __construct($from_lines, $to_lines,
 315                              $mapped_from_lines, $mapped_to_lines)
 316     {
 317         assert(count($from_lines) == count($mapped_from_lines));
 318         assert(count($to_lines) == count($mapped_to_lines));
 319
 320         parent::Text_Diff($mapped_from_lines, $mapped_to_lines);
 321
 322         $xi = $yi = 0;
 323         for ($i = 0; $i < count($this->_edits); $i++) {
 324             $orig = &$this->_edits[$i]->orig;
 325             if (is_array($orig)) {
 326                 $orig = array_slice($from_lines, $xi, count($orig));
 327                 $xi += count($orig);
 328             }
 329
 330             $final = &$this->_edits[$i]->final;
 331             if (is_array($final)) {
 332                 $final = array_slice($to_lines, $yi, count($final));
 333                 $yi += count($final);
 334             }
 335         }
 336     }
 337
 338         /**
 339          * PHP4 constructor.
 340          */
 341         public function Text_MappedDiff( $from_lines, $to_lines,
 342                              $mapped_from_lines, $mapped_to_lines ) {
 343                 self::__construct( $from_lines, $to_lines,
 344                              $mapped_from_lines, $mapped_to_lines );
 345         }
 346
 347 }
 348
 349 /**
 350  * @package Text_Diff
 351  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 352  *
 353  * @access private
 354  */
 355 class Text_Diff_Op {
 356
 357     var $orig;
 358     var $final;
 359
 360     function &reverse()
 361     {
 362         trigger_error('Abstract method', E_USER_ERROR);
 363     }
 364
 365     function norig()
 366     {
 367         return $this->orig ? count($this->orig) : 0;
 368     }
 369
 370     function nfinal()
 371     {
 372         return $this->final ? count($this->final) : 0;
 373     }
 374
 375 }
 376
 377 /**
 378  * @package Text_Diff
 379  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 380  *
 381  * @access private
 382  */
 383 class Text_Diff_Op_copy extends Text_Diff_Op {
 384
 385         /**
 386          * PHP5 constructor.
 387          */
 388     function __construct( $orig, $final = false )
 389     {
 390         if (!is_array($final)) {
 391             $final = $orig;
 392         }
 393         $this->orig = $orig;
 394         $this->final = $final;
 395     }
 396
 397         /**
 398          * PHP4 constructor.
 399          */
 400         public function Text_Diff_Op_copy( $orig, $final = false ) {
 401                 self::__construct( $orig, $final );
 402         }
 403
 404     function &reverse()
 405     {
 406         $reverse = new Text_Diff_Op_copy($this->final, $this->orig);
 407         return $reverse;
 408     }
 409
 410 }
 411
 412 /**
 413  * @package Text_Diff
 414  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 415  *
 416  * @access private
 417  */
 418 class Text_Diff_Op_delete extends Text_Diff_Op {
 419
 420         /**
 421          * PHP5 constructor.
 422          */
 423         function __construct( $lines )
 424     {
 425         $this->orig = $lines;
 426         $this->final = false;
 427     }
 428
 429         /**
 430          * PHP4 constructor.
 431          */
 432         public function Text_Diff_Op_delete( $lines ) {
 433                 self::__construct( $lines );
 434         }
 435
 436     function &reverse()
 437     {
 438         $reverse = new Text_Diff_Op_add($this->orig);
 439         return $reverse;
 440     }
 441
 442 }
 443
 444 /**
 445  * @package Text_Diff
 446  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 447  *
 448  * @access private
 449  */
 450 class Text_Diff_Op_add extends Text_Diff_Op {
 451
 452         /**
 453          * PHP5 constructor.
 454          */
 455     function __construct( $lines )
 456     {
 457         $this->final = $lines;
 458         $this->orig = false;
 459     }
 460
 461         /**
 462          * PHP4 constructor.
 463          */
 464         public function Text_Diff_Op_add( $lines ) {
 465                 self::__construct( $lines );
 466         }
 467
 468     function &reverse()
 469     {
 470         $reverse = new Text_Diff_Op_delete($this->final);
 471         return $reverse;
 472     }
 473
 474 }
 475
 476 /**
 477  * @package Text_Diff
 478  * @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
 479  *
 480  * @access private
 481  */
 482 class Text_Diff_Op_change extends Text_Diff_Op {
 483
 484         /**
 485          * PHP5 constructor.
 486          */
 487     function __construct( $orig, $final )
 488     {
 489         $this->orig = $orig;
 490         $this->final = $final;
 491     }
 492
 493         /**
 494          * PHP4 constructor.
 495          */
 496         public function Text_Diff_Op_change( $orig, $final ) {
 497                 self::__construct( $orig, $final );
 498         }
 499
 500     function &reverse()
 501     {
 502         $reverse = new Text_Diff_Op_change($this->final, $this->orig);
 503         return $reverse;
 504     }
 505
 506 }