1 <?php  if (!defined('PmWiki')) exit();
2 /*  
3     Copyright 2003,2004 Nils Knappmeier (nk@knappi.org)
4     Copyright 2004-2021 Patrick R. Michaud (pmichaud@pobox.com)
5 
6     This file is part of PmWiki; you can redistribute it and/or modify
7     it under the terms of the GNU General Public License as published
8     by the Free Software Foundation; either version 2 of the License, or
9     (at your option) any later version.  See pmwiki.php for full details.
10 
11     This file implements a diff function in native PHP.  It is based
12     upon the PHPDiffEngine code written by Nils Knappmeier, who in turn
13     had used Daniel Unterberger's diff 
14     (http://www.holomind.de/phpnet/diff.php) as the basis for his code.
15 
16     Pm's revision of Nils' code simply attempts to streamline it 
17     for speed (eliminate function calls and unnecessary string ops)
18     and place everything into a single file.
19     
20     Script maintained by Petko YOTOV www.pmwiki.org/petko
21 */
22 
23 ## PHPDiff returns the differences between $old and $new, formatted
24 ## in the standard diff(1) output format.
25 function PHPDiff($old, $new) 
26 {
27    StopWatch("PHPDiff: begin");
28    # split the source text into arrays of lines
29    $t1 = explode("\n", $old);
30    $x = array_pop($t1); 
31    if ($x > '') $t1[] = "$x\n\\ No newline at end of file";
32    $t2 = explode("\n", strval($new));
33    $x = array_pop($t2); 
34    if ($x > '') $t2[] = "$x\n\\ No newline at end of file";
35 
36    $t1_start = 0; $t1_end = count($t1);
37    $t2_start = 0; $t2_end = count($t2);
38 
39    # stop with a common ending
40    while ($t1_start < $t1_end && $t2_start < $t2_end 
41           && $t1[$t1_end-1] == $t2[$t2_end-1]) { $t1_end--; $t2_end--; }
42 
43    # skip over any common beginning
44    while ($t1_start < $t1_end && $t2_start < $t2_end 
45           && $t1[$t1_start] == $t2[$t2_start]) { $t1_start++; $t2_start++; }
46 
47    # build a reverse-index array using the line as key and line number as value
48    # don't store blank lines, so they won't be targets of the shortest distance
49    # search
50    for($i = $t1_start; $i < $t1_end; $i++) if ($t1[$i]>'') $r1[$t1[$i]][] = $i;
51    for($i = $t2_start; $i < $t2_end; $i++) if ($t2[$i]>'') $r2[$t2[$i]][] = $i;
52 
53    $a1 = $t1_start; $a2 = $t2_start;   # start at beginning of each list
54    $actions = array();
55 
56    # walk this loop until we reach the end of one of the lists
57    while ($a1 < $t1_end && $a2 < $t2_end) {
58      # if we have a common element, save it and go to the next
59      if ($t1[$a1] == $t2[$a2]) { $actions[] = 4; $a1++; $a2++; continue; } 
60 
61      # otherwise, find the shortest move (Manhattan-distance) from the
62      # current location
63      $best1 = $t1_end; $best2 = $t2_end;
64      $s1 = $a1; $s2 = $a2;
65      while(($s1 + $s2 - $a1 - $a2) < ($best1 + $best2 - $a1 - $a2)) {
66        $d = -1;
67        foreach((array)@$r1[$t2[$s2]] as $n) 
68          if ($n >= $s1) { $d = $n; break; }
69        if ($d >= $s1 && ($d + $s2 - $a1 - $a2) < ($best1 + $best2 - $a1 - $a2))
70          { $best1 = $d; $best2 = $s2; }
71        $d = -1;
72        foreach((array)@$r2[$t1[$s1]] as $n) 
73          if ($n >= $s2) { $d = $n; break; }
74        if ($d >= $s2 && ($s1 + $d - $a1 - $a2) < ($best1 + $best2 - $a1 - $a2))
75          { $best1 = $s1; $best2 = $d; }
76        $s1++; $s2++;
77      }
78      while ($a1 < $best1) { $actions[] = 1; $a1++; }  # deleted elements
79      while ($a2 < $best2) { $actions[] = 2; $a2++; }  # added elements
80   }
81 
82   # we've reached the end of one list, now walk to the end of the other
83   while($a1 < $t1_end) { $actions[] = 1; $a1++; }  # deleted elements
84   while($a2 < $t2_end) { $actions[] = 2; $a2++; }  # added elements
85 
86   # and this marks our ending point
87   $actions[] = 8;
88 
89   # now, let's follow the path we just took and report the added/deleted
90   # elements into $out.
91   $op = 0;
92   $x0 = $x1 = $t1_start; $y0 = $y1 = $t2_start;
93   $out = array();
94   foreach($actions as $act) {
95     if ($act == 1) { $op |= $act; $x1++; continue; }
96     if ($act == 2) { $op |= $act; $y1++; continue; }
97     if ($op > 0) {
98       $xstr = ($x1 == ($x0+1)) ? $x1 : ($x0+1) . ",$x1";
99       $ystr = ($y1 == ($y0+1)) ? $y1 : ($y0+1) . ",$y1";
100       if ($op == 1) $out[] = "{$xstr}d{$y1}";
101       elseif ($op == 3) $out[] = "{$xstr}c{$ystr}";
102       while ($x0 < $x1) { $out[] = '< ' . $t1[$x0]; $x0++; }   # deleted elems
103       if ($op == 2) $out[] = "{$x1}a{$ystr}";
104       elseif ($op == 3) $out[] = '---';
105       while ($y0 < $y1) { $out[] = '> '.$t2[$y0]; $y0++; }   # added elems
106     }
107     $x1++; $x0 = $x1;
108     $y1++; $y0 = $y1;
109     $op = 0;
110   }
111   $out[] = '';
112   StopWatch("PHPDiff: end");
113   return join("\n",$out);
114 }
115 
116 if (!@$DiffFunction || !function_exists($DiffFunction))
117   $DiffFunction = 'PHPDiff';
118