dolibarr 20.0.0
utils_diff.class.php
1<?php
2/* Copyright (C) 2016 Jean-François Ferry <hello@librethic.io>
3 * Copyright (C) 2024 MDW <mdeweerd@users.noreply.github.com>
4 *
5 * A class containing a diff implementation
6 *
7 * Created by Stephen Morley - http://stephenmorley.org/ - and released under the
8 * terms of the CC0 1.0 Universal legal code:
9 *
10 * http://creativecommons.org/publicdomain/zero/1.0/legalcode
11 */
12
13
18class Diff
19{
20 // define the constants
21 const UNMODIFIED = 0;
22 const DELETED = 1;
23 const INSERTED = 2;
24
38 public static function compare($string1, $string2, $compareCharacters = false)
39 {
40 // initialise the sequences and comparison start and end positions
41 $start = 0;
42 if ($compareCharacters) {
43 $sequence1 = $string1;
44 $sequence2 = $string2;
45 $end1 = strlen($string1) - 1;
46 $end2 = strlen($string2) - 1;
47 } else {
48 $sequence1 = preg_split('/\R/', $string1);
49 $sequence2 = preg_split('/\R/', $string2);
50 $end1 = count($sequence1) - 1;
51 $end2 = count($sequence2) - 1;
52 }
53
54 // skip any common prefix
55 while ($start <= $end1 && $start <= $end2
56 && $sequence1[$start] == $sequence2[$start]) {
57 $start++;
58 }
59
60 // skip any common suffix
61 while ($end1 >= $start && $end2 >= $start
62 && $sequence1[$end1] == $sequence2[$end2]) {
63 $end1--;
64 $end2--;
65 }
66
67 // compute the table of longest common subsequence lengths
68 $table = self::computeTable($sequence1, $sequence2, $start, $end1, $end2);
69
70 // generate the partial diff
71 $partialDiff = self::generatePartialDiff($table, $sequence1, $sequence2, $start);
72
73 // generate the full diff
74 $diff = array();
75 for ($index = 0; $index < $start; $index++) {
76 $diff[] = array($sequence1[$index], self::UNMODIFIED);
77 }
78 while (count($partialDiff) > 0) {
79 $diff[] = array_pop($partialDiff);
80 }
81
82 $end2 = ($compareCharacters ? strlen($sequence1) : count($sequence1));
83 for ($index = $end1 + 1; $index < $end2; $index++) {
84 $diff[] = array($sequence1[$index], self::UNMODIFIED);
85 }
86
87 // return the diff
88 return $diff;
89 }
90
99 public static function compareFiles(
100 $file1,
101 $file2,
102 $compareCharacters = false
103 ) {
104
105 // return the diff of the files
106 return self::compare(
107 file_get_contents($file1),
108 file_get_contents($file2),
109 $compareCharacters
110 );
111 }
112
123 private static function computeTable($sequence1, $sequence2, $start, $end1, $end2)
124 {
125 // determine the lengths to be compared
126 $length1 = $end1 - $start + 1;
127 $length2 = $end2 - $start + 1;
128
129 // initialise the table
130 $table = array(array_fill(0, $length2 + 1, 0));
131
132 // loop over the rows
133 for ($index1 = 1; $index1 <= $length1; $index1++) {
134 // create the new row
135 $table[$index1] = array(0);
136
137 // loop over the columns
138 for ($index2 = 1; $index2 <= $length2; $index2++) {
139 // store the longest common subsequence length
140 if ($sequence1[$index1 + $start - 1] == $sequence2[$index2 + $start - 1]
141 ) {
142 $table[$index1][$index2] = $table[$index1 - 1][$index2 - 1] + 1;
143 } else {
144 $table[$index1][$index2] = max($table[$index1 - 1][$index2], $table[$index1][$index2 - 1]);
145 }
146 }
147 }
148
149 // return the table
150 return $table;
151 }
152
163 private static function generatePartialDiff($table, $sequence1, $sequence2, $start)
164 {
165 // initialise the diff
166 $diff = array();
167
168 // initialise the indices
169 $index1 = count($table) - 1;
170 $index2 = count($table[0]) - 1;
171
172 // loop until there are no items remaining in either sequence
173 while ($index1 > 0 || $index2 > 0) {
174 // check what has happened to the items at these indices
175 if ($index1 > 0 && $index2 > 0
176 && $sequence1[$index1 + $start - 1] == $sequence2[$index2 + $start - 1]
177 ) {
178 // update the diff and the indices
179 $diff[] = array($sequence1[$index1 + $start - 1], self::UNMODIFIED);
180 $index1--;
181 $index2--;
182 } elseif ($index2 > 0
183 && $table[$index1][$index2] == $table[$index1][$index2 - 1]
184 ) {
185 // update the diff and the indices
186 $diff[] = array($sequence2[$index2 + $start - 1], self::INSERTED);
187 $index2--;
188 } else {
189 // update the diff and the indices
190 $diff[] = array($sequence1[$index1 + $start - 1], self::DELETED);
191 $index1--;
192 }
193 }
194
195 // return the diff
196 return $diff;
197 }
198
208 public static function toString($diff, $separator = "\n")
209 {
210 // initialise the string
211 $string = '';
212
213 // loop over the lines in the diff
214 foreach ($diff as $line) {
215 // extend the string with the line
216 switch ($line[1]) {
217 case self::UNMODIFIED:
218 $string .= ' '.$line[0];
219 break;
220 case self::DELETED:
221 $string .= '- '.$line[0];
222 break;
223 case self::INSERTED:
224 $string .= '+ '.$line[0];
225 break;
226 }
227
228 // extend the string with the separator
229 $string .= $separator;
230 }
231
232 // return the string
233 return $string;
234 }
235
245 public static function toHTML($diff, $separator = '<br>')
246 {
247 // initialise the HTML
248 $html = '';
249
250 // loop over the lines in the diff
251 $element = 'unknown';
252 foreach ($diff as $line) {
253 // extend the HTML with the line
254 switch ($line[1]) {
255 case self::UNMODIFIED:
256 $element = 'span';
257 break;
258 case self::DELETED:
259 $element = 'del';
260 break;
261 case self::INSERTED:
262 $element = 'ins';
263 break;
264 }
265 $html .= '<'.$element.'>'.dol_escape_htmltag($line[0]).'</'.$element.'>';
266
267 // extend the HTML with the separator
268 $html .= $separator;
269 }
270
271 // return the HTML
272 return $html;
273 }
274
283 public static function toTable($diff, $indentation = '', $separator = '<br>')
284 {
285 // initialise the HTML
286 $html = $indentation."<table class=\"diff\">\n";
287
288 $rightCell = $leftCell = '';
289
290 // loop over the lines in the diff
291 $index = 0;
292 $nbdiff = count($diff);
293 while ($index < $nbdiff) {
294 // determine the line type
295 switch ($diff[$index][1]) {
296 // display the content on the left and right
297 case self::UNMODIFIED:
298 $leftCell = self::getCellContent(
299 $diff,
300 $indentation,
301 $separator,
302 $index,
303 self::UNMODIFIED
304 );
305 $rightCell = $leftCell;
306 break;
307
308 // display the deleted on the left and inserted content on the right
309 case self::DELETED:
310 $leftCell = self::getCellContent(
311 $diff,
312 $indentation,
313 $separator,
314 $index,
315 self::DELETED
316 );
317 $rightCell = self::getCellContent(
318 $diff,
319 $indentation,
320 $separator,
321 $index,
322 self::INSERTED
323 );
324 break;
325
326 // display the inserted content on the right
327 case self::INSERTED:
328 $leftCell = '';
329 $rightCell = self::getCellContent(
330 $diff,
331 $indentation,
332 $separator,
333 $index,
334 self::INSERTED
335 );
336 break;
337 }
338
339 // extend the HTML with the new row
340 $html .=
341 $indentation
342 . " <tr>\n"
343 . $indentation
344 . ' <td class="diff'
345 . ($leftCell == $rightCell
346 ? 'Unmodified'
347 : ($leftCell == '' ? 'Blank' : 'Deleted'))
348 . '">'
349 . $leftCell
350 . "</td>\n"
351 . $indentation
352 . ' <td class="diff'
353 . ($leftCell == $rightCell
354 ? 'Unmodified'
355 : ($rightCell == '' ? 'Blank' : 'Inserted'))
356 . '">'
357 . $rightCell
358 . "</td>\n"
359 . $indentation
360 . " </tr>\n";
361 }
362
363 // return the HTML
364 return $html.$indentation."</table>\n";
365 }
366
378 private static function getCellContent($diff, $indentation, $separator, &$index, $type)
379 {
380 // initialise the HTML
381 $html = '';
382
383 // loop over the matching lines, adding them to the HTML
384 while ($index < count($diff) && $diff[$index][1] == $type) {
385 $html .=
386 '<span>'
387 . htmlspecialchars($diff[$index][0])
388 . '</span>'
389 . $separator;
390 $index++;
391 }
392
393 // return the HTML
394 return $html;
395 }
396}
A class containing functions for computing diffs and formatting the output.
static compareFiles( $file1, $file2, $compareCharacters=false)
Returns the diff for two files.
static compare($string1, $string2, $compareCharacters=false)
Returns the diff for two strings.
static toString($diff, $separator="\n")
Returns a diff as a string, where unmodified lines are prefixed by ' ', deletions are prefixed by '- ...
static generatePartialDiff($table, $sequence1, $sequence2, $start)
Returns the partial diff for the specified sequences, in reverse order.
static computeTable($sequence1, $sequence2, $start, $end1, $end2)
Returns the table of longest common subsequence lengths for the specified sequences.
static toHTML($diff, $separator='< br >')
Returns a diff as an HTML string, where unmodified lines are contained within 'span' elements,...
static getCellContent($diff, $indentation, $separator, &$index, $type)
Returns the content of the cell, for use in the toTable function.
static toTable($diff, $indentation='', $separator='< br >')
Returns a diff as an HTML table.
dol_escape_htmltag($stringtoescape, $keepb=0, $keepn=0, $noescapetags='', $escapeonlyhtmltags=0, $cleanalsojavascript=0)
Returns text escaped for inclusion in HTML alt or title or value tags, or into values of HTML input f...