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