3 * This file is part of the Diff package.
5 * (c) Sebastian Bergmann <sebastian@phpunit.de>
7 * For the full copyright and license information, please view the LICENSE
8 * file that was distributed with this source code.
11 namespace SebastianBergmann\Diff;
13 use SebastianBergmann\Diff\LCS\LongestCommonSubsequence;
14 use SebastianBergmann\Diff\LCS\TimeEfficientImplementation;
15 use SebastianBergmann\Diff\LCS\MemoryEfficientImplementation;
18 * Diff implementation.
30 private $showNonDiffLines;
33 * @param string $header
35 public function __construct($header = "--- Original\n+++ New\n", $showNonDiffLines = true)
37 $this->header = $header;
38 $this->showNonDiffLines = $showNonDiffLines;
42 * Returns the diff between two arrays or strings as string.
44 * @param array|string $from
45 * @param array|string $to
46 * @param LongestCommonSubsequence $lcs
50 public function diff($from, $to, LongestCommonSubsequence $lcs = null)
52 if (!is_array($from) && !is_string($from)) {
53 $from = (string) $from;
56 if (!is_array($to) && !is_string($to)) {
60 $buffer = $this->header;
61 $diff = $this->diffToArray($from, $to, $lcs);
67 foreach ($diff as $line) {
68 if ($line[1] === 0 /* OLD */) {
69 if ($inOld === false) {
72 } elseif ($inOld !== false) {
73 if (($i - $inOld) > 5) {
74 $old[$inOld] = $i - 1;
83 $start = isset($old[0]) ? $old[0] : 0;
86 if ($tmp = array_search($end, $old)) {
92 for ($i = $start; $i < $end; $i++) {
93 if (isset($old[$i])) {
100 if ($this->showNonDiffLines === true) {
101 $buffer .= "@@ @@\n";
106 if ($diff[$i][1] === 1 /* ADDED */) {
107 $buffer .= '+' . $diff[$i][0] . "\n";
108 } elseif ($diff[$i][1] === 2 /* REMOVED */) {
109 $buffer .= '-' . $diff[$i][0] . "\n";
110 } elseif ($this->showNonDiffLines === true) {
111 $buffer .= ' ' . $diff[$i][0] . "\n";
119 * Returns the diff between two arrays or strings as array.
121 * Each array element contains two elements:
122 * - [0] => string $token
125 * - 2: REMOVED: $token was removed from $from
126 * - 1: ADDED: $token was added to $from
127 * - 0: OLD: $token is not changed in $to
129 * @param array|string $from
130 * @param array|string $to
131 * @param LongestCommonSubsequence $lcs
135 public function diffToArray($from, $to, LongestCommonSubsequence $lcs = null)
137 preg_match_all('(\r\n|\r|\n)', $from, $fromMatches);
138 preg_match_all('(\r\n|\r|\n)', $to, $toMatches);
140 if (is_string($from)) {
141 $from = preg_split('(\r\n|\r|\n)', $from);
144 if (is_string($to)) {
145 $to = preg_split('(\r\n|\r|\n)', $to);
150 $fromLength = count($from);
151 $toLength = count($to);
152 $length = min($fromLength, $toLength);
154 for ($i = 0; $i < $length; ++$i) {
155 if ($from[$i] === $to[$i]) {
156 $start[] = $from[$i];
157 unset($from[$i], $to[$i]);
165 for ($i = 1; $i < $length; ++$i) {
166 if ($from[$fromLength - $i] === $to[$toLength - $i]) {
167 array_unshift($end, $from[$fromLength - $i]);
168 unset($from[$fromLength - $i], $to[$toLength - $i]);
175 $lcs = $this->selectLcsImplementation($from, $to);
178 $common = $lcs->calculate(array_values($from), array_values($to));
181 if (isset($fromMatches[0]) && $toMatches[0] &&
182 count($fromMatches[0]) === count($toMatches[0]) &&
183 $fromMatches[0] !== $toMatches[0]) {
185 '#Warning: Strings contain different line endings!', 0
189 foreach ($start as $token) {
190 $diff[] = array($token, 0 /* OLD */);
196 foreach ($common as $token) {
197 while ((($fromToken = reset($from)) !== $token)) {
198 $diff[] = array(array_shift($from), 2 /* REMOVED */);
201 while ((($toToken = reset($to)) !== $token)) {
202 $diff[] = array(array_shift($to), 1 /* ADDED */);
205 $diff[] = array($token, 0 /* OLD */);
211 while (($token = array_shift($from)) !== null) {
212 $diff[] = array($token, 2 /* REMOVED */);
215 while (($token = array_shift($to)) !== null) {
216 $diff[] = array($token, 1 /* ADDED */);
219 foreach ($end as $token) {
220 $diff[] = array($token, 0 /* OLD */);
230 * @return LongestCommonSubsequence
232 private function selectLcsImplementation(array $from, array $to)
234 // We do not want to use the time-efficient implementation if its memory
235 // footprint will probably exceed this value. Note that the footprint
236 // calculation is only an estimation for the matrix and the LCS method
237 // will typically allocate a bit more memory than this.
238 $memoryLimit = 100 * 1024 * 1024;
240 if ($this->calculateEstimatedFootprint($from, $to) > $memoryLimit) {
241 return new MemoryEfficientImplementation;
244 return new TimeEfficientImplementation;
248 * Calculates the estimated memory footprint for the DP-based method.
255 private function calculateEstimatedFootprint(array $from, array $to)
257 $itemSize = PHP_INT_SIZE == 4 ? 76 : 144;
259 return $itemSize * pow(min(count($from), count($to)), 2);