dolibarr  20.0.0-beta
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 
18 class 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...