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