Wordpress 3.6
[autoinstalls/wordpress.git] / 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 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 }