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 https://opensource.org/license/lgpl-2-1/.
14 *
15 * @package Text_Diff
16 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
17 */
18class 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 int 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 int 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 bool 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 int 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 int $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 * @access protected
224 *
225 * @return string A directory name which can be used for temp files.
226 */
227 static function _getTempDir()
228 {
229 return get_temp_dir();
230 }
231
232 /**
233 * Checks a diff for validity.
234 *
235 * This is here only for debugging purposes.
236 */
237 function _check($from_lines, $to_lines)
238 {
239 if (serialize($from_lines) != serialize($this->getOriginal())) {
240 throw new Text_Exception("Reconstructed original does not match");
241 }
242 if (serialize($to_lines) != serialize($this->getFinal())) {
243 throw new Text_Exception("Reconstructed final does not match");
244 }
245
246 $rev = $this->reverse();
247 if (serialize($to_lines) != serialize($rev->getOriginal())) {
248 throw new Text_Exception("Reversed original does not match");
249 }
250 if (serialize($from_lines) != serialize($rev->getFinal())) {
251 throw new Text_Exception("Reversed final does not match");
252 }
253
254 $prevtype = null;
255 foreach ($this->_edits as $edit) {
256 if ($prevtype !== null && $edit instanceof $prevtype) {
257 throw new Text_Exception("Edit sequence is non-optimal");
258 }
259 $prevtype = get_class($edit);
260 }
261
262 return true;
263 }
264
265}
266
267/**
268 * @package Text_Diff
269 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
270 */
271class Text_MappedDiff extends Text_Diff {
272
273 /**
274 * Computes a diff between sequences of strings.
275 *
276 * This can be used to compute things like case-insensitive diffs, or diffs
277 * which ignore changes in white-space.
278 *
279 * @param array $from_lines An array of strings.
280 * @param array $to_lines An array of strings.
281 * @param array $mapped_from_lines This array should have the same size
282 * number of elements as $from_lines. The
283 * elements in $mapped_from_lines and
284 * $mapped_to_lines are what is actually
285 * compared when computing the diff.
286 * @param array $mapped_to_lines This array should have the same number
287 * of elements as $to_lines.
288 */
289 function __construct($from_lines, $to_lines,
290 $mapped_from_lines, $mapped_to_lines)
291 {
292 assert(count($from_lines) == count($mapped_from_lines));
293 assert(count($to_lines) == count($mapped_to_lines));
294
295 parent::Text_Diff($mapped_from_lines, $mapped_to_lines);
296
297 $xi = $yi = 0;
298 for ($i = 0; $i < count($this->_edits); $i++) {
299 $orig = &$this->_edits[$i]->orig;
300 if (is_array($orig)) {
301 $orig = array_slice($from_lines, $xi, count($orig));
302 $xi += count($orig);
303 }
304
305 $final = &$this->_edits[$i]->final;
306 if (is_array($final)) {
307 $final = array_slice($to_lines, $yi, count($final));
308 $yi += count($final);
309 }
310 }
311 }
312
313 /**
314 * PHP4 constructor.
315 */
316 public function Text_MappedDiff( $from_lines, $to_lines,
317 $mapped_from_lines, $mapped_to_lines ) {
318 self::__construct( $from_lines, $to_lines,
319 $mapped_from_lines, $mapped_to_lines );
320 }
321
322}
323
324/**
325 * @package Text_Diff
326 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
327 *
328 * @access private
329 */
330abstract class Text_Diff_Op {
331
332 var $orig;
333 var $final;
334
335 abstract function &reverse();
336
337 function norig()
338 {
339 return $this->orig ? count($this->orig) : 0;
340 }
341
342 function nfinal()
343 {
344 return $this->final ? count($this->final) : 0;
345 }
346
347}
348
349/**
350 * @package Text_Diff
351 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
352 *
353 * @access private
354 */
355class Text_Diff_Op_copy extends Text_Diff_Op {
356
357 /**
358 * PHP5 constructor.
359 */
360 function __construct( $orig, $final = false )
361 {
362 if (!is_array($final)) {
363 $final = $orig;
364 }
365 $this->orig = $orig;
366 $this->final = $final;
367 }
368
369 /**
370 * PHP4 constructor.
371 */
372 public function Text_Diff_Op_copy( $orig, $final = false ) {
373 self::__construct( $orig, $final );
374 }
375
376 function &reverse()
377 {
378 $reverse = new Text_Diff_Op_copy($this->final, $this->orig);
379 return $reverse;
380 }
381
382}
383
384/**
385 * @package Text_Diff
386 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
387 *
388 * @access private
389 */
390class Text_Diff_Op_delete extends Text_Diff_Op {
391
392 /**
393 * PHP5 constructor.
394 */
395 function __construct( $lines )
396 {
397 $this->orig = $lines;
398 $this->final = false;
399 }
400
401 /**
402 * PHP4 constructor.
403 */
404 public function Text_Diff_Op_delete( $lines ) {
405 self::__construct( $lines );
406 }
407
408 function &reverse()
409 {
410 $reverse = new Text_Diff_Op_add($this->orig);
411 return $reverse;
412 }
413
414}
415
416/**
417 * @package Text_Diff
418 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
419 *
420 * @access private
421 */
422class Text_Diff_Op_add extends Text_Diff_Op {
423
424 /**
425 * PHP5 constructor.
426 */
427 function __construct( $lines )
428 {
429 $this->final = $lines;
430 $this->orig = false;
431 }
432
433 /**
434 * PHP4 constructor.
435 */
436 public function Text_Diff_Op_add( $lines ) {
437 self::__construct( $lines );
438 }
439
440 function &reverse()
441 {
442 $reverse = new Text_Diff_Op_delete($this->final);
443 return $reverse;
444 }
445
446}
447
448/**
449 * @package Text_Diff
450 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
451 *
452 * @access private
453 */
454class Text_Diff_Op_change extends Text_Diff_Op {
455
456 /**
457 * PHP5 constructor.
458 */
459 function __construct( $orig, $final )
460 {
461 $this->orig = $orig;
462 $this->final = $final;
463 }
464
465 /**
466 * PHP4 constructor.
467 */
468 public function Text_Diff_Op_change( $orig, $final ) {
469 self::__construct( $orig, $final );
470 }
471
472 function &reverse()
473 {
474 $reverse = new Text_Diff_Op_change($this->final, $this->orig);
475 return $reverse;
476 }
477
478}
479