1#! /usr/bin/env perl
2
3# Copyright (c) 2003 The Regents of The University of Michigan
4# All rights reserved.
5#
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.
16#
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.
| 1#! /usr/bin/env perl
2
3# Copyright (c) 2003 The Regents of The University of Michigan
4# All rights reserved.
5#
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.
16#
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.
|
28
29# Diff two streams.
30#
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:
38#
39# rundiff 'm5a --trace:flags=InstExec |' 'm5b --trace:flags=InstExec |'
40#
41
42use strict;
43
44use Getopt::Std;
45
46#
47# Options:
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)
51#
52our ($opt_c, $opt_l, $opt_x);
53getopts('c:l:x');
54
55#
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.
62my $use_complexdiff = defined($opt_x);
63
64if ($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,
68 # so it's OK.
69 require Algorithm::Diff;
70 import Algorithm::Diff qw(traverse_sequences);
71};
72
73my $lookahead_lines = $opt_l || 200;
74
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
77# set both.
78my $precontext_lines = $opt_c || 3;
79my $postcontext_lines = $precontext_lines;
80
81my $file1 = $ARGV[0];
82my $file2 = $ARGV[1];
83
84die "Need two args." if (!(defined($file1) && defined($file2)));
85
86my ($fh1, $fh2);
87open($fh1, $file1) or die "Can't open $file1";
88open($fh2, $file2) or die "Can't open $file2";
89
90# print files to output so we know which is which
91print "-$file1\n";
92print "+$file2\n";
93
94# buffer of matching lines for pre-diff context
95my @precontext = ();
96# number of post-diff matching lines remaining to print
97my $postcontext = 0;
98
99# lookahead buffers for $file1 and $file2 respectively
100my @lines1 = ();
101my @lines2 = ();
102
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.
106my $lineno1 = 1;
107my $lineno2 = 1;
108
109# Fill a lookahead buffer to $lookahead_lines lines (or until EOF).
110sub fill
111{
112 my ($fh, $array) = @_;
113
114 while (@$array < $lookahead_lines) {
115 my $line = <$fh>;
116 last if (!defined($line));
117 push @$array, $line;
118 }
119}
120
121# Print and delete n lines from front of given array with given prefix.
122sub printlines
123{
124 my ($array, $n, $prefix) = @_;
125
126 while ($n--) {
127 my $line = shift @$array;
128 last if (!defined($line));
129 print $prefix, $line;
130 }
131}
132
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).
135sub printdiff
136{
137 my ($n1, $n2)= @_;
138
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";
147 }
148
149 # Print and clear the precontext buffer.
150 if (@precontext) {
151 print ' ', join(' ', @precontext);
152 $lineno1 += scalar(@precontext);
153 $lineno2 += scalar(@precontext);
154 @precontext = ();
155 }
156
157 # Print the differing lines.
158 printlines(\@lines1, $n1, '-');
159 printlines(\@lines2, $n2, '+');
160 $lineno1 += $n1;
161 $lineno2 += $n2;
162
163 # Set $postcontext to print the next $postcontext_lines matching lines.
164 $postcontext = $postcontext_lines;
165}
166
167
168########################
169#
170# Complex diff algorithm
171#
172########################
173
174{
175 my $match_found;
176 my $discard_lines1;
177 my $discard_lines2;
178
179 sub match { $match_found = 1; }
180 sub discard1 { $discard_lines1++ unless $match_found; }
181 sub discard2 { $discard_lines2++ unless $match_found; }
182
183 sub complex_diff
184 {
185 $match_found = 0;
186 $discard_lines1 = 0;
187 $discard_lines2 = 0;
188
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,
194 { MATCH => \&match,
195 DISCARD_A => \&discard1,
196 DISCARD_B => \&discard2 });
197
198 if (!$match_found) {
199 printdiff(scalar(@lines1), scalar(@lines2));
200 die "Lost sync!";
201 }
202
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);
207
208 printdiff($discard_lines1, $discard_lines2);
209 }
210}
211
212#######################
213#
214# Simple diff algorithm
215#
216#######################
217
218# Check for a pair of matching lines; if found, generate appropriate
219# diff output.
220sub checkmatch
221{
222 my ($n1, $n2) = @_;
223
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]) {
229 printdiff($n1, $n2);
230 return 1;
231 }
232
233 return 0;
234}
235
236sub simple_diff
237{
238 # Look for differences of $cnt lines to resync,
239 # increasing $cnt from 1 to $lookahead_lines until we find
240 # something.
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);
251 }
252 }
253
254 printdiff(scalar(@lines1), scalar(@lines2));
255 die "Lost sync!";
256}
257
258# Set the pointer to the appropriate diff function.
259#
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].
265my $find_diff = $use_complexdiff ? \&complex_diff : \&simple_diff;
266
267# The main loop.
268while (1) {
269 # keep lookahead buffers topped up
270 fill($fh1, \@lines1);
271 fill($fh2, \@lines2);
272
273 # peek at first line in each buffer
274 my $l1 = $lines1[0];
275 my $l2 = $lines2[0];
276
277 if (!defined($l1) && !defined($l2)) {
278 # reached EOF on both streams: exit
279 exit(1);
280 }
281
282 if ($l1 eq $l2) {
283 # matching lines: delete from lookahead buffer
284 shift @lines1;
285 shift @lines2;
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
289 $postcontext--;
290 print ' ', $l1;
291 $lineno1++;
292 $lineno2++;
293 }
294 else {
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) {
300 shift @precontext;
301 $lineno1++;
302 $lineno2++;
303 }
304 }
305 }
306 else {
307 # Mismatch. Deal with it.
308 &$find_diff();
309 }
310}
| 31
32# Diff two streams.
33#
34# Unlike regular diff, this script does not read in the entire input
35# before doing a diff, so it can be used on lengthy outputs piped from
36# other programs (e.g., M5 traces). The best way to do this is to
37# take advantage of the power of Perl's open function, which will
38# automatically fork a subprocess if the last character in the
39# "filename" is a pipe (|). Thus to compare the instruction traces
40# from two versions of m5 (m5a and m5b), you can do this:
41#
42# rundiff 'm5a --trace:flags=InstExec |' 'm5b --trace:flags=InstExec |'
43#
44
45use strict;
46
47use Getopt::Std;
48
49#
50# Options:
51# -c <n> : print n lines of context before & after changes
52# -l <n> : use n lines of lookahead
53# -x : use "complex" diff from Algorithm::Diff (see below)
54#
55our ($opt_c, $opt_l, $opt_x);
56getopts('c:l:x');
57
58#
59# For the highest-quality (minimal) diffs, we can use the
60# Algorithm::Diff package. By default, a built-in, simple, and
61# generally quite adequate algorithm will be used. If you have
62# Algorithm::Diff installed on your system, and don't mind having the
63# script go slower (like 3-4x slower, based on informal observation),
64# then specify '-x' on the command line to use it.
65my $use_complexdiff = defined($opt_x);
66
67if ($use_complexdiff) {
68 # Don't use 'use', as that's a compile-time option and will fail
69 # on systems that don't have Algorithm::Diff installed even if
70 # $use_complexdiff is false. 'require' is evaluated at runtime,
71 # so it's OK.
72 require Algorithm::Diff;
73 import Algorithm::Diff qw(traverse_sequences);
74};
75
76my $lookahead_lines = $opt_l || 200;
77
78# in theory you could have different amounts of context before and
79# after a diff, but until someone needs that there's only one arg to
80# set both.
81my $precontext_lines = $opt_c || 3;
82my $postcontext_lines = $precontext_lines;
83
84my $file1 = $ARGV[0];
85my $file2 = $ARGV[1];
86
87die "Need two args." if (!(defined($file1) && defined($file2)));
88
89my ($fh1, $fh2);
90open($fh1, $file1) or die "Can't open $file1";
91open($fh2, $file2) or die "Can't open $file2";
92
93# print files to output so we know which is which
94print "-$file1\n";
95print "+$file2\n";
96
97# buffer of matching lines for pre-diff context
98my @precontext = ();
99# number of post-diff matching lines remaining to print
100my $postcontext = 0;
101
102# lookahead buffers for $file1 and $file2 respectively
103my @lines1 = ();
104my @lines2 = ();
105
106# Next line number available to print from each file. Generally this
107# corresponds to the oldest line in @precontext, or the oldest line in
108# @lines1 and @lines2 if @precontext is empty.
109my $lineno1 = 1;
110my $lineno2 = 1;
111
112# Fill a lookahead buffer to $lookahead_lines lines (or until EOF).
113sub fill
114{
115 my ($fh, $array) = @_;
116
117 while (@$array < $lookahead_lines) {
118 my $line = <$fh>;
119 last if (!defined($line));
120 push @$array, $line;
121 }
122}
123
124# Print and delete n lines from front of given array with given prefix.
125sub printlines
126{
127 my ($array, $n, $prefix) = @_;
128
129 while ($n--) {
130 my $line = shift @$array;
131 last if (!defined($line));
132 print $prefix, $line;
133 }
134}
135
136# Print a difference region where n1 lines of file1 were replaced by
137# n2 lines of file2 (where either n1 or n2 could be zero).
138sub printdiff
139{
140 my ($n1, $n2)= @_;
141
142 # If the precontext buffer is full or we're at the beginning of a
143 # file, then this is a new diff region, so we should print a
144 # header indicating the current line numbers. If we're past the
145 # beginning and the precontext buffer isn't full, then whatever
146 # we're about to print is contiguous with the end of the last
147 # region we printed, so we just concatenate them on the output.
148 if (@precontext == $precontext_lines || ($lineno1 == 0 && $lineno2 == 0)) {
149 print "@@ -$lineno1 +$lineno2 @@\n";
150 }
151
152 # Print and clear the precontext buffer.
153 if (@precontext) {
154 print ' ', join(' ', @precontext);
155 $lineno1 += scalar(@precontext);
156 $lineno2 += scalar(@precontext);
157 @precontext = ();
158 }
159
160 # Print the differing lines.
161 printlines(\@lines1, $n1, '-');
162 printlines(\@lines2, $n2, '+');
163 $lineno1 += $n1;
164 $lineno2 += $n2;
165
166 # Set $postcontext to print the next $postcontext_lines matching lines.
167 $postcontext = $postcontext_lines;
168}
169
170
171########################
172#
173# Complex diff algorithm
174#
175########################
176
177{
178 my $match_found;
179 my $discard_lines1;
180 my $discard_lines2;
181
182 sub match { $match_found = 1; }
183 sub discard1 { $discard_lines1++ unless $match_found; }
184 sub discard2 { $discard_lines2++ unless $match_found; }
185
186 sub complex_diff
187 {
188 $match_found = 0;
189 $discard_lines1 = 0;
190 $discard_lines2 = 0;
191
192 # See Diff.pm. Note that even though this call generates a
193 # complete diff of both lookahead buffers, all we use it for
194 # is to figure out how many lines to discard off the front of
195 # each buffer to resync the streams.
196 traverse_sequences( \@lines1, \@lines2,
197 { MATCH => \&match,
198 DISCARD_A => \&discard1,
199 DISCARD_B => \&discard2 });
200
201 if (!$match_found) {
202 printdiff(scalar(@lines1), scalar(@lines2));
203 die "Lost sync!";
204 }
205
206 # Since we shouldn't get here unless the first lines of the
207 # buffers are different, then we must discard some lines off
208 # at least one of the buffers.
209 die if ($discard_lines1 == 0 && $discard_lines2 == 0);
210
211 printdiff($discard_lines1, $discard_lines2);
212 }
213}
214
215#######################
216#
217# Simple diff algorithm
218#
219#######################
220
221# Check for a pair of matching lines; if found, generate appropriate
222# diff output.
223sub checkmatch
224{
225 my ($n1, $n2) = @_;
226
227 # Check if two adjacent lines match, to reduce false resyncs
228 # (particularly on unrelated blank lines). This generates
229 # larger-than-necessary diffs when a single line really should be
230 # treated as common; if that bugs you, use Algorithm::Diff.
231 if ($lines1[$n1] eq $lines2[$n2] && $lines1[$n1+1] eq $lines2[$n2+1]) {
232 printdiff($n1, $n2);
233 return 1;
234 }
235
236 return 0;
237}
238
239sub simple_diff
240{
241 # Look for differences of $cnt lines to resync,
242 # increasing $cnt from 1 to $lookahead_lines until we find
243 # something.
244 for (my $cnt = 1; $cnt < $lookahead_lines-1; ++$cnt) {
245 # Check for n lines in one file being replaced by
246 # n lines in the other.
247 return if checkmatch($cnt, $cnt);
248 # Find differences where n lines in one file were
249 # replaced by m lines in the other. We let m = $cnt
250 # and iterate for n = 0 to $cnt-1.
251 for (my $n = 0; $n < $cnt; ++$n) {
252 return if checkmatch($n, $cnt);
253 return if checkmatch($cnt, $n);
254 }
255 }
256
257 printdiff(scalar(@lines1), scalar(@lines2));
258 die "Lost sync!";
259}
260
261# Set the pointer to the appropriate diff function.
262#
263# Note that in either case the function determines how many lines to
264# discard from the front of each lookahead buffer to resync the
265# streams, then prints the appropriate diff output and discards them.
266# After the function returns, it should always be the case that
267# $lines1[0] eq $lines2[0].
268my $find_diff = $use_complexdiff ? \&complex_diff : \&simple_diff;
269
270# The main loop.
271while (1) {
272 # keep lookahead buffers topped up
273 fill($fh1, \@lines1);
274 fill($fh2, \@lines2);
275
276 # peek at first line in each buffer
277 my $l1 = $lines1[0];
278 my $l2 = $lines2[0];
279
280 if (!defined($l1) && !defined($l2)) {
281 # reached EOF on both streams: exit
282 exit(1);
283 }
284
285 if ($l1 eq $l2) {
286 # matching lines: delete from lookahead buffer
287 shift @lines1;
288 shift @lines2;
289 # figure out what to do with this line
290 if ($postcontext > 0) {
291 # we're in the post-context of a diff: print it
292 $postcontext--;
293 print ' ', $l1;
294 $lineno1++;
295 $lineno2++;
296 }
297 else {
298 # we're in the middle of a matching region... save this
299 # line for precontext in case we run into a difference.
300 push @precontext, $l1;
301 # don't let precontext buffer get bigger than needed
302 while (@precontext > $precontext_lines) {
303 shift @precontext;
304 $lineno1++;
305 $lineno2++;
306 }
307 }
308 }
309 else {
310 # Mismatch. Deal with it.
311 &$find_diff();
312 }
313}
|