Blame
Date:
Mon Jan 23 05:00:25 2023 UTC
Message:
Daily backup
001
2021-12-17
jrmu
<?php if (!defined('PmWiki')) exit();
002
2021-12-17
jrmu
/*
003
2021-12-17
jrmu
Copyright 2003,2004 Nils Knappmeier (nk@knappi.org)
004
2021-12-17
jrmu
Copyright 2004-2015 Patrick R. Michaud (pmichaud@pobox.com)
005
2021-12-17
jrmu
006
2021-12-17
jrmu
This file is part of PmWiki; you can redistribute it and/or modify
007
2021-12-17
jrmu
it under the terms of the GNU General Public License as published
008
2021-12-17
jrmu
by the Free Software Foundation; either version 2 of the License, or
009
2021-12-17
jrmu
(at your option) any later version. See pmwiki.php for full details.
010
2021-12-17
jrmu
011
2021-12-17
jrmu
This file implements a diff function in native PHP. It is based
012
2021-12-17
jrmu
upon the PHPDiffEngine code written by Nils Knappmeier, who in turn
013
2021-12-17
jrmu
had used Daniel Unterberger's diff
014
2021-12-17
jrmu
(http://www.holomind.de/phpnet/diff.php) as the basis for his code.
015
2021-12-17
jrmu
016
2021-12-17
jrmu
Pm's revision of Nils' code simply attempts to streamline it
017
2021-12-17
jrmu
for speed (eliminate function calls and unnecessary string ops)
018
2021-12-17
jrmu
and place everything into a single file.
019
2021-12-17
jrmu
020
2021-12-17
jrmu
Script maintained by Petko YOTOV www.pmwiki.org/petko
021
2021-12-17
jrmu
*/
022
2021-12-17
jrmu
023
2021-12-17
jrmu
## PHPDiff returns the differences between $old and $new, formatted
024
2021-12-17
jrmu
## in the standard diff(1) output format.
025
2021-12-17
jrmu
function PHPDiff($old, $new)
026
2021-12-17
jrmu
{
027
2021-12-17
jrmu
StopWatch("PHPDiff: begin");
028
2021-12-17
jrmu
# split the source text into arrays of lines
029
2021-12-17
jrmu
$t1 = explode("\n", $old);
030
2021-12-17
jrmu
$x = array_pop($t1);
031
2021-12-17
jrmu
if ($x > '') $t1[] = "$x\n\\ No newline at end of file";
032
2021-12-17
jrmu
$t2 = explode("\n", $new);
033
2021-12-17
jrmu
$x = array_pop($t2);
034
2021-12-17
jrmu
if ($x > '') $t2[] = "$x\n\\ No newline at end of file";
035
2021-12-17
jrmu
036
2021-12-17
jrmu
$t1_start = 0; $t1_end = count($t1);
037
2021-12-17
jrmu
$t2_start = 0; $t2_end = count($t2);
038
2021-12-17
jrmu
039
2021-12-17
jrmu
# stop with a common ending
040
2021-12-17
jrmu
while ($t1_start < $t1_end && $t2_start < $t2_end
041
2021-12-17
jrmu
&& $t1[$t1_end-1] == $t2[$t2_end-1]) { $t1_end--; $t2_end--; }
042
2021-12-17
jrmu
043
2021-12-17
jrmu
# skip over any common beginning
044
2021-12-17
jrmu
while ($t1_start < $t1_end && $t2_start < $t2_end
045
2021-12-17
jrmu
&& $t1[$t1_start] == $t2[$t2_start]) { $t1_start++; $t2_start++; }
046
2021-12-17
jrmu
047
2021-12-17
jrmu
# build a reverse-index array using the line as key and line number as value
048
2021-12-17
jrmu
# don't store blank lines, so they won't be targets of the shortest distance
049
2021-12-17
jrmu
# search
050
2021-12-17
jrmu
for($i = $t1_start; $i < $t1_end; $i++) if ($t1[$i]>'') $r1[$t1[$i]][] = $i;
051
2021-12-17
jrmu
for($i = $t2_start; $i < $t2_end; $i++) if ($t2[$i]>'') $r2[$t2[$i]][] = $i;
052
2021-12-17
jrmu
053
2021-12-17
jrmu
$a1 = $t1_start; $a2 = $t2_start; # start at beginning of each list
054
2021-12-17
jrmu
$actions = array();
055
2021-12-17
jrmu
056
2021-12-17
jrmu
# walk this loop until we reach the end of one of the lists
057
2021-12-17
jrmu
while ($a1 < $t1_end && $a2 < $t2_end) {
058
2021-12-17
jrmu
# if we have a common element, save it and go to the next
059
2021-12-17
jrmu
if ($t1[$a1] == $t2[$a2]) { $actions[] = 4; $a1++; $a2++; continue; }
060
2021-12-17
jrmu
061
2021-12-17
jrmu
# otherwise, find the shortest move (Manhattan-distance) from the
062
2021-12-17
jrmu
# current location
063
2021-12-17
jrmu
$best1 = $t1_end; $best2 = $t2_end;
064
2021-12-17
jrmu
$s1 = $a1; $s2 = $a2;
065
2021-12-17
jrmu
while(($s1 + $s2 - $a1 - $a2) < ($best1 + $best2 - $a1 - $a2)) {
066
2021-12-17
jrmu
$d = -1;
067
2021-12-17
jrmu
foreach((array)@$r1[$t2[$s2]] as $n)
068
2021-12-17
jrmu
if ($n >= $s1) { $d = $n; break; }
069
2021-12-17
jrmu
if ($d >= $s1 && ($d + $s2 - $a1 - $a2) < ($best1 + $best2 - $a1 - $a2))
070
2021-12-17
jrmu
{ $best1 = $d; $best2 = $s2; }
071
2021-12-17
jrmu
$d = -1;
072
2021-12-17
jrmu
foreach((array)@$r2[$t1[$s1]] as $n)
073
2021-12-17
jrmu
if ($n >= $s2) { $d = $n; break; }
074
2021-12-17
jrmu
if ($d >= $s2 && ($s1 + $d - $a1 - $a2) < ($best1 + $best2 - $a1 - $a2))
075
2021-12-17
jrmu
{ $best1 = $s1; $best2 = $d; }
076
2021-12-17
jrmu
$s1++; $s2++;
077
2021-12-17
jrmu
}
078
2021-12-17
jrmu
while ($a1 < $best1) { $actions[] = 1; $a1++; } # deleted elements
079
2021-12-17
jrmu
while ($a2 < $best2) { $actions[] = 2; $a2++; } # added elements
080
2021-12-17
jrmu
}
081
2021-12-17
jrmu
082
2021-12-17
jrmu
# we've reached the end of one list, now walk to the end of the other
083
2021-12-17
jrmu
while($a1 < $t1_end) { $actions[] = 1; $a1++; } # deleted elements
084
2021-12-17
jrmu
while($a2 < $t2_end) { $actions[] = 2; $a2++; } # added elements
085
2021-12-17
jrmu
086
2021-12-17
jrmu
# and this marks our ending point
087
2021-12-17
jrmu
$actions[] = 8;
088
2021-12-17
jrmu
089
2021-12-17
jrmu
# now, let's follow the path we just took and report the added/deleted
090
2021-12-17
jrmu
# elements into $out.
091
2021-12-17
jrmu
$op = 0;
092
2021-12-17
jrmu
$x0 = $x1 = $t1_start; $y0 = $y1 = $t2_start;
093
2021-12-17
jrmu
$out = array();
094
2021-12-17
jrmu
foreach($actions as $act) {
095
2021-12-17
jrmu
if ($act == 1) { $op |= $act; $x1++; continue; }
096
2021-12-17
jrmu
if ($act == 2) { $op |= $act; $y1++; continue; }
097
2021-12-17
jrmu
if ($op > 0) {
098
2021-12-17
jrmu
$xstr = ($x1 == ($x0+1)) ? $x1 : ($x0+1) . ",$x1";
099
2021-12-17
jrmu
$ystr = ($y1 == ($y0+1)) ? $y1 : ($y0+1) . ",$y1";
100
2021-12-17
jrmu
if ($op == 1) $out[] = "{$xstr}d{$y1}";
101
2021-12-17
jrmu
elseif ($op == 3) $out[] = "{$xstr}c{$ystr}";
102
2021-12-17
jrmu
while ($x0 < $x1) { $out[] = '< ' . $t1[$x0]; $x0++; } # deleted elems
103
2021-12-17
jrmu
if ($op == 2) $out[] = "{$x1}a{$ystr}";
104
2021-12-17
jrmu
elseif ($op == 3) $out[] = '---';
105
2021-12-17
jrmu
while ($y0 < $y1) { $out[] = '> '.$t2[$y0]; $y0++; } # added elems
106
2021-12-17
jrmu
}
107
2021-12-17
jrmu
$x1++; $x0 = $x1;
108
2021-12-17
jrmu
$y1++; $y0 = $y1;
109
2021-12-17
jrmu
$op = 0;
110
2021-12-17
jrmu
}
111
2021-12-17
jrmu
$out[] = '';
112
2021-12-17
jrmu
StopWatch("PHPDiff: end");
113
2021-12-17
jrmu
return join("\n",$out);
114
2021-12-17
jrmu
}
115
2021-12-17
jrmu
116
2021-12-17
jrmu
if (!function_exists(@$DiffFunction))
117
2021-12-17
jrmu
$DiffFunction = 'PHPDiff';
118
2021-12-17
jrmu
IRCNow