3 # Copyright (c) 2003 The Regents of The University of Michigan
6 # Redistribution and use in source and binary forms, with or without
7 # modification, are permitted provided that the following conditions are
8 # met: redistributions of source code must retain the above copyright
9 # notice, this list of conditions and the following disclaimer;
10 # redistributions in binary form must reproduce the above copyright
11 # notice, this list of conditions and the following disclaimer in the
12 # documentation and/or other materials provided with the distribution;
13 # neither the name of the copyright holders nor the names of its
14 # contributors may be used to endorse or promote products derived from
15 # this software without specific prior written permission.
17 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 # Unlike regular diff, this script does not read in the entire input
32 # before doing a diff, so it can be used on lengthy outputs piped from
33 # other programs (e.g., M5 traces). The best way to do this is to
34 # take advantage of the power of Perl's open function, which will
35 # automatically fork a subprocess if the last character in the
36 # "filename" is a pipe (|). Thus to compare the instruction traces
37 # from two versions of m5 (m5a and m5b), you can do this:
39 # rundiff 'm5a --trace:flags=InstExec |' 'm5b --trace:flags=InstExec |'
48 # -c <n> : print n lines of context before & after changes
49 # -l <n> : use n lines of lookahead
50 # -x : use "complex" diff from Algorithm::Diff (see below)
52 our ($opt_c, $opt_l, $opt_x);
56 # For the highest-quality (minimal) diffs, we can use the
57 # Algorithm::Diff package. By default, a built-in, simple, and
58 # generally quite adequate algorithm will be used. If you have
59 # Algorithm::Diff installed on your system, and don't mind having the
60 # script go slower (like 3-4x slower, based on informal observation),
61 # then specify '-x' on the command line to use it.
62 my $use_complexdiff = defined($opt_x);
64 if ($use_complexdiff) {
65 # Don't use 'use', as that's a compile-time option and will fail
66 # on systems that don't have Algorithm::Diff installed even if
67 # $use_complexdiff is false. 'require' is evaluated at runtime,
69 require Algorithm
::Diff
;
70 import Algorithm
::Diff
qw(traverse_sequences);
73 my $lookahead_lines = $opt_l || 200;
75 # in theory you could have different amounts of context before and
76 # after a diff, but until someone needs that there's only one arg to
78 my $precontext_lines = $opt_c || 3;
79 my $postcontext_lines = $precontext_lines;
84 die "Need two args." if (!(defined($file1) && defined($file2)));
87 open($fh1, $file1) or die "Can't open $file1";
88 open($fh2, $file2) or die "Can't open $file2";
90 # print files to output so we know which is which
94 # buffer of matching lines for pre-diff context
96 # number of post-diff matching lines remaining to print
99 # lookahead buffers for $file1 and $file2 respectively
103 # Next line number available to print from each file. Generally this
104 # corresponds to the oldest line in @precontext, or the oldest line in
105 # @lines1 and @lines2 if @precontext is empty.
109 # Fill a lookahead buffer to $lookahead_lines lines (or until EOF).
112 my ($fh, $array) = @_;
114 while (@
$array < $lookahead_lines) {
116 last if (!defined($line));
121 # Print and delete n lines from front of given array with given prefix.
124 my ($array, $n, $prefix) = @_;
127 my $line = shift @
$array;
128 last if (!defined($line));
129 print $prefix, $line;
133 # Print a difference region where n1 lines of file1 were replaced by
134 # n2 lines of file2 (where either n1 or n2 could be zero).
139 # If the precontext buffer is full or we're at the beginning of a
140 # file, then this is a new diff region, so we should print a
141 # header indicating the current line numbers. If we're past the
142 # beginning and the precontext buffer isn't full, then whatever
143 # we're about to print is contiguous with the end of the last
144 # region we printed, so we just concatenate them on the output.
145 if (@precontext == $precontext_lines || ($lineno1 == 0 && $lineno2 == 0)) {
146 print "@@ -$lineno1 +$lineno2 @@\n";
149 # Print and clear the precontext buffer.
151 print ' ', join(' ', @precontext);
152 $lineno1 += scalar(@precontext);
153 $lineno2 += scalar(@precontext);
157 # Print the differing lines.
158 printlines
(\
@lines1, $n1, '-');
159 printlines
(\
@lines2, $n2, '+');
163 # Set $postcontext to print the next $postcontext_lines matching lines.
164 $postcontext = $postcontext_lines;
168 ########################
170 # Complex diff algorithm
172 ########################
179 sub match
{ $match_found = 1; }
180 sub discard1
{ $discard_lines1++ unless $match_found; }
181 sub discard2
{ $discard_lines2++ unless $match_found; }
189 # See Diff.pm. Note that even though this call generates a
190 # complete diff of both lookahead buffers, all we use it for
191 # is to figure out how many lines to discard off the front of
192 # each buffer to resync the streams.
193 traverse_sequences
( \
@lines1, \
@lines2,
195 DISCARD_A
=> \
&discard1
,
196 DISCARD_B
=> \
&discard2
});
199 printdiff
(scalar(@lines1), scalar(@lines2));
203 # Since we shouldn't get here unless the first lines of the
204 # buffers are different, then we must discard some lines off
205 # at least one of the buffers.
206 die if ($discard_lines1 == 0 && $discard_lines2 == 0);
208 printdiff
($discard_lines1, $discard_lines2);
212 #######################
214 # Simple diff algorithm
216 #######################
218 # Check for a pair of matching lines; if found, generate appropriate
224 # Check if two adjacent lines match, to reduce false resyncs
225 # (particularly on unrelated blank lines). This generates
226 # larger-than-necessary diffs when a single line really should be
227 # treated as common; if that bugs you, use Algorithm::Diff.
228 if ($lines1[$n1] eq $lines2[$n2] && $lines1[$n1+1] eq $lines2[$n2+1]) {
238 # Look for differences of $cnt lines to resync,
239 # increasing $cnt from 1 to $lookahead_lines until we find
241 for (my $cnt = 1; $cnt < $lookahead_lines-1; ++$cnt) {
242 # Check for n lines in one file being replaced by
243 # n lines in the other.
244 return if checkmatch
($cnt, $cnt);
245 # Find differences where n lines in one file were
246 # replaced by m lines in the other. We let m = $cnt
247 # and iterate for n = 0 to $cnt-1.
248 for (my $n = 0; $n < $cnt; ++$n) {
249 return if checkmatch
($n, $cnt);
250 return if checkmatch
($cnt, $n);
254 printdiff
(scalar(@lines1), scalar(@lines2));
258 # Set the pointer to the appropriate diff function.
260 # Note that in either case the function determines how many lines to
261 # discard from the front of each lookahead buffer to resync the
262 # streams, then prints the appropriate diff output and discards them.
263 # After the function returns, it should always be the case that
264 # $lines1[0] eq $lines2[0].
265 my $find_diff = $use_complexdiff ? \
&complex_diff
: \
&simple_diff
;
269 # keep lookahead buffers topped up
270 fill
($fh1, \
@lines1);
271 fill
($fh2, \
@lines2);
273 # peek at first line in each buffer
277 if (!defined($l1) && !defined($l2)) {
278 # reached EOF on both streams: exit
283 # matching lines: delete from lookahead buffer
286 # figure out what to do with this line
287 if ($postcontext > 0) {
288 # we're in the post-context of a diff: print it
295 # we're in the middle of a matching region... save this
296 # line for precontext in case we run into a difference.
297 push @precontext, $l1;
298 # don't let precontext buffer get bigger than needed
299 while (@precontext > $precontext_lines) {
307 # Mismatch. Deal with it.