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 }