3 * General API for generating and formatting diffs - the differences between
4 * two sequences of strings.
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.
9 * $Horde: framework/Text_Diff/Diff.php,v 1.26 2008/01/04 10:07:49 jan Exp $
11 * Copyright 2004 Geoffrey T. Dairiki <dairiki@dairiki.org>
12 * Copyright 2004-2008 The Horde Project (http://www.horde.org/)
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.
18 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
30 * Computes diffs between sequences of strings.
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.
38 function Text_Diff($engine, $params)
40 // Backward compatibility workaround.
41 if (!is_string($engine)) {
42 $params = array($engine, $params);
46 if ($engine == 'auto') {
47 $engine = extension_loaded('xdiff') ? 'xdiff' : 'native';
49 $engine = basename($engine);
53 require_once dirname(__FILE__).'/Diff/Engine/' . $engine . '.php';
54 $class = 'Text_Diff_Engine_' . $engine;
55 $diff_engine = new $class();
57 $this->_edits = call_user_func_array(array($diff_engine, 'diff'), $params);
61 * Returns the array of differences.
69 * Computes a reversed diff.
73 * $diff = new Text_Diff($lines1, $lines2);
74 * $rev = $diff->reverse();
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()
84 if (version_compare(zend_version(), '2', '>')) {
89 $rev->_edits = array();
90 foreach ($this->_edits as $edit) {
91 $rev->_edits[] = $edit->reverse();
97 * Checks for an empty diff.
99 * @return boolean True if two sequences were identical.
103 foreach ($this->_edits as $edit) {
104 if (!is_a($edit, 'Text_Diff_Op_copy')) {
112 * Computes the length of the Longest Common Subsequence (LCS).
114 * This is mostly for diagnostic purposes.
116 * @return integer The length of the LCS.
121 foreach ($this->_edits as $edit) {
122 if (is_a($edit, 'Text_Diff_Op_copy')) {
123 $lcs += count($edit->orig);
130 * Gets the original set of lines.
132 * This reconstructs the $from_lines parameter passed to the constructor.
134 * @return array The original sequence of strings.
136 function getOriginal()
139 foreach ($this->_edits as $edit) {
141 array_splice($lines, count($lines), 0, $edit->orig);
148 * Gets the final set of lines.
150 * This reconstructs the $to_lines parameter passed to the constructor.
152 * @return array The sequence of strings.
157 foreach ($this->_edits as $edit) {
159 array_splice($lines, count($lines), 0, $edit->final);
166 * Removes trailing newlines from a line of text. This is meant to be used
169 * @param string $line The line to trim.
170 * @param integer $key The index of the line in the array. Not used.
172 function trimNewlines(&$line, $key)
174 $line = str_replace(array("\n", "\r"), '', $line);
178 * Determines the location of the system temporary directory.
184 * @return string A directory name which can be used for temp files.
185 * Returns false if one could not be found.
187 function _getTempDir()
189 $tmp_locations = array('/tmp', '/var/tmp', 'c:\WUTemp', 'c:\temp',
190 'c:\windows\temp', 'c:\winnt\temp');
192 /* Try PHP's upload_tmp_dir directive. */
193 $tmp = ini_get('upload_tmp_dir');
195 /* Otherwise, try to determine the TMPDIR environment variable. */
197 $tmp = getenv('TMPDIR');
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)) {
209 /* If it is still empty, we have failed, so return false; otherwise
210 * return the directory determined. */
211 return strlen($tmp) ? $tmp : false;
215 * Checks a diff for validity.
217 * This is here only for debugging purposes.
219 function _check($from_lines, $to_lines)
221 if (serialize($from_lines) != serialize($this->getOriginal())) {
222 trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
224 if (serialize($to_lines) != serialize($this->getFinal())) {
225 trigger_error("Reconstructed final doesn't match", E_USER_ERROR);
228 $rev = $this->reverse();
229 if (serialize($to_lines) != serialize($rev->getOriginal())) {
230 trigger_error("Reversed original doesn't match", E_USER_ERROR);
232 if (serialize($from_lines) != serialize($rev->getFinal())) {
233 trigger_error("Reversed final doesn't match", E_USER_ERROR);
237 foreach ($this->_edits as $edit) {
238 if ($prevtype == get_class($edit)) {
239 trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
241 $prevtype = get_class($edit);
251 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
253 class Text_MappedDiff extends Text_Diff {
256 * Computes a diff between sequences of strings.
258 * This can be used to compute things like case-insensitve diffs, or diffs
259 * which ignore changes in white-space.
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.
271 function Text_MappedDiff($from_lines, $to_lines,
272 $mapped_from_lines, $mapped_to_lines)
274 assert(count($from_lines) == count($mapped_from_lines));
275 assert(count($to_lines) == count($mapped_to_lines));
277 parent::Text_Diff($mapped_from_lines, $mapped_to_lines);
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));
287 $final = &$this->_edits[$i]->final;
288 if (is_array($final)) {
289 $final = array_slice($to_lines, $yi, count($final));
290 $yi += count($final);
299 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
310 trigger_error('Abstract method', E_USER_ERROR);
315 return $this->orig ? count($this->orig) : 0;
320 return $this->final ? count($this->final) : 0;
327 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
331 class Text_Diff_Op_copy extends Text_Diff_Op {
333 function Text_Diff_Op_copy($orig, $final = false)
335 if (!is_array($final)) {
339 $this->final = $final;
344 $reverse = &new Text_Diff_Op_copy($this->final, $this->orig);
352 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
356 class Text_Diff_Op_delete extends Text_Diff_Op {
358 function Text_Diff_Op_delete($lines)
360 $this->orig = $lines;
361 $this->final = false;
366 $reverse = &new Text_Diff_Op_add($this->orig);
374 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
378 class Text_Diff_Op_add extends Text_Diff_Op {
380 function Text_Diff_Op_add($lines)
382 $this->final = $lines;
388 $reverse = &new Text_Diff_Op_delete($this->final);
396 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
400 class Text_Diff_Op_change extends Text_Diff_Op {
402 function Text_Diff_Op_change($orig, $final)
405 $this->final = $final;
410 $reverse = &new Text_Diff_Op_change($this->final, $this->orig);