util/rundiff

   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
  42 use strict;
  43
  44 #
  45 # For the highest-quality (minimal) diffs, we can use the
  46 # Algorithm::Diff package.  If you don't have this installed, or want
  47 # the script to run faster (like 3-4x faster, based on informal
  48 # observation), set $use_complexdiff to 0; then a built-in, simple,
  49 # and generally quite adequate algorithm will be used instead.
  50 my $use_complexdiff = 0;
  51
  52 #if ($use_complexdiff) {
  53 #    use Algorithm::Diff qw(traverse_sequences);
  54 #};
  55
  56 my $lookahead_lines = 200;
  57 my $precontext_lines = 3;
  58 my $postcontext_lines = 3;
  59
  60 my $file1 = $ARGV[0];
  61 my $file2 = $ARGV[1];
  62
  63 die "Need two args." if (!(defined($file1) && defined($file2)));
  64
  65 my ($fh1, $fh2);
  66 open($fh1, $file1) or die "Can't open $file1";
  67 open($fh2, $file2) or die "Can't open $file2";
  68
  69 # buffer of matching lines for pre-diff context
  70 my @precontext = ();
  71 # number of post-diff matching lines remaining to print
  72 my $postcontext = 0;
  73
  74 # lookahead buffers for $file1 and $file2 respectively
  75 my @lines1 = ();
  76 my @lines2 = ();
  77
  78 # Next line number available to print from each file.  Generally this
  79 # corresponds to the oldest line in @precontext, or the oldest line in
  80 # @lines1 and @lines2 if @precontext is empty.
  81 my $lineno1 = 1;
  82 my $lineno2 = 1;
  83
  84 # Fill a lookahead buffer to $lookahead_lines lines (or until EOF).
  85 sub fill
  86 {
  87     my ($fh, $array) = @_;
  88
  89     while (@$array < $lookahead_lines) {
  90         my $line = <$fh>;
  91         last if (!defined($line));
  92         push @$array, $line;
  93     }
  94 }
  95
  96 # Print and delete n lines from front of given array with given prefix.
  97 sub printlines
  98 {
  99     my ($array, $n, $prefix) = @_;
 100
 101     while ($n--) {
 102         my $line = shift @$array;
 103         last if (!defined($line));
 104         print $prefix, $line;
 105     }
 106 }
 107
 108 # Print a difference region where n1 lines of file1 were replaced by
 109 # n2 lines of file2 (where either n1 or n2 could be zero).
 110 sub printdiff
 111 {
 112     my ($n1, $n2)= @_;
 113
 114     # If the precontext buffer is full or we're at the beginning of a
 115     # file, then this is a new diff region, so we should print a
 116     # header indicating the current line numbers.  If we're past the
 117     # beginning and the precontext buffer isn't full, then whatever
 118     # we're about to print is contiguous with the end of the last
 119     # region we printed, so we just concatenate them on the output.
 120     if (@precontext == $precontext_lines || ($lineno1 == 0 && $lineno2 == 0)) {
 121         print "@@ -$lineno1 +$lineno2 @@\n";
 122     }
 123
 124     # Print and clear the precontext buffer.
 125     if (@precontext) {
 126         print ' ', join(' ', @precontext);
 127         $lineno1 += scalar(@precontext);
 128         $lineno2 += scalar(@precontext);
 129         @precontext = ();
 130     }
 131
 132     # Print the differing lines.
 133     printlines(\@lines1, $n1, '-');
 134     printlines(\@lines2, $n2, '+');
 135     $lineno1 += $n1;
 136     $lineno2 += $n2;
 137
 138     # Set $postcontext to print the next $postcontext_lines matching lines.
 139     $postcontext = $postcontext_lines;
 140 }
 141
 142
 143 ########################
 144 #
 145 # Complex diff algorithm
 146 #
 147 ########################
 148
 149 {
 150     my $match_found;
 151     my $discard_lines1;
 152     my $discard_lines2;
 153
 154     sub match { $match_found = 1; }
 155     sub discard1 { $discard_lines1++ unless $match_found; }
 156     sub discard2 { $discard_lines2++ unless $match_found; }
 157
 158     sub complex_diff
 159     {
 160         $match_found = 0;
 161         $discard_lines1 = 0;
 162         $discard_lines2 = 0;
 163
 164         # See Diff.pm.  Note that even though this call generates a
 165         # complete diff of both lookahead buffers, all we use it for
 166         # is to figure out how many lines to discard off the front of
 167         # each buffer to resync the streams.
 168         traverse_sequences( \@lines1, \@lines2,
 169                             { MATCH => \&match,
 170                               DISCARD_A => \&discard1,
 171                               DISCARD_B => \&discard2 });
 172
 173         die "Lost sync!" if (!$match_found);
 174
 175         # Since we shouldn't get here unless the first lines of the
 176         # buffers are different, then we must discard some lines off
 177         # at least one of the buffers.
 178         die if ($discard_lines1 == 0 && $discard_lines2 == 0);
 179
 180         printdiff($discard_lines1, $discard_lines2);
 181     }
 182 }
 183
 184 #######################
 185 #
 186 # Simple diff algorithm
 187 #
 188 #######################
 189
 190 # Check for a pair of matching lines; if found, generate appropriate
 191 # diff output.
 192 sub checkmatch
 193 {
 194     my ($n1, $n2) = @_;
 195
 196     # Check if two adjacent lines match, to reduce false resyncs
 197     # (particularly on unrelated blank lines).  This generates
 198     # larger-than-necessary diffs when a single line really should be
 199     # treated as common; if that bugs you, use Algorithm::Diff.
 200     if ($lines1[$n1] eq $lines2[$n2] && $lines1[$n1+1] eq $lines2[$n2+1]) {
 201         printdiff($n1, $n2);
 202     }
 203 }
 204
 205 sub simple_diff
 206 {
 207     # Look for differences of $cnt lines to resync,
 208     # increasing $cnt from 1 to $lookahead_lines until we find
 209     # something.
 210     for (my $cnt = 1; $cnt < $lookahead_lines-1; ++$cnt) {
 211         # Check for n lines in one file being replaced by
 212         # n lines in the other.
 213         return if checkmatch($cnt, $cnt);
 214         # Find differences where n lines in one file were
 215         # replaced by m lines in the other.  We let m = $cnt
 216         # and iterate for n = 0 to $cnt-1.
 217         for (my $n = 0; $n < $cnt; ++$n) {
 218             return if checkmatch($n, $cnt);
 219             return if checkmatch($cnt, $n);
 220         }
 221     }
 222     die "Lost sync!";
 223 }
 224
 225 # Set the pointer to the appropriate diff function.
 226 #
 227 # Note that in either case the function determines how many lines to
 228 # discard from the front of each lookahead buffer to resync the
 229 # streams, then prints the appropriate diff output and discards them.
 230 # After the function returns, it should always be the case that
 231 # $lines1[0] eq $lines2[0].
 232 my $find_diff = $use_complexdiff ? \&complex_diff : \&simple_diff;
 233
 234 # The main loop.
 235 while (1) {
 236     # keep lookahead buffers topped up
 237     fill($fh1, \@lines1);
 238     fill($fh2, \@lines2);
 239
 240     # peek at first line in each buffer
 241     my $l1 = $lines1[0];
 242     my $l2 = $lines2[0];
 243
 244     if (!defined($l1) && !defined($l2)) {
 245         # reached EOF on both streams: exit
 246         exit(1);
 247     }
 248
 249     if ($l1 eq $l2) {
 250         # matching lines: delete from lookahead buffer
 251         shift @lines1;
 252         shift @lines2;
 253         # figure out what to do with this line
 254         if ($postcontext > 0) {
 255             # we're in the post-context of a diff: print it
 256             $postcontext--;
 257             print ' ', $l1;
 258             $lineno1++;
 259             $lineno2++;
 260         }
 261         else {
 262             # we're in the middle of a matching region... save this
 263             # line for precontext in case we run into a difference.
 264             push @precontext, $l1;
 265             # don't let precontext buffer get bigger than needed
 266             while (@precontext > $precontext_lines) {
 267                 shift @precontext;
 268                 $lineno1++;
 269                 $lineno2++;
 270             }
 271         }
 272     }
 273     else {
 274         # Mismatch.  Deal with it.
 275         &$find_diff();
 276     }
 277 }