#!/usr/bin/perl

# Copyright (c) 2001 Nathan L. Binkert
# All rights reserved.
#
# Permission to redistribute, use, copy, and modify this software
# without fee is hereby granted, provided that the following
# conditions are met:
#
# 1. This entire notice is included in all source code copies of any
#    software which is or includes a copy or modification of this
#    software.
# 2. The name of the author may not be used to endorse or promote
#    products derived from this software without specific prior
#    written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
# OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#

use Algorithm::Diff qw(diff);
use vars qw ($opt_C $opt_c $opt_u $opt_U);

$opt_u = "";
$opt_c = undef;

$diffsize = 2000;
# After we've read up to a certain point in each file, the number of items
# we've read from each file will differ by $FLD (could be 0)
my $File_Length_Difference = 0;
my $Context_Lines = 9;

$progname = $0;
if (scalar(@ARGV) != 2) {
  usage();
}

my ($filename1, $filename2);
($filename1, $start1) = parse_filearg($ARGV[0]);
($filename2, $start2) = parse_filearg($ARGV[1]);

if ($filename1 eq "-" && $filename2 eq "-") {
  die "Only one of the inputs may be standard in\n";
}

my ($file1, $file2);
if ($filename1 eq "-") {
  $file1 = STDIN;
} else {
  open(FILE1, $filename1) || die "can't open $file1: $!\n";
  $file1 = FILE1;
}

if ($filename2 eq "-") {
  $file2 = STDIN;
} else {
  open(FILE2, $filename2) || die "can't open $file2: $!\n";
  $file2 = FILE2;
}

my $file_offset1 = ffw($file1, $start1);
my $file_offset2 = ffw($file2, $start2);

$skip_first = 0;
my (@buf1, @buf2, @printbuf1, @printbuf2);

$Compare_Ahead = 0;

while (!eof($file1) && !eof($file2)) {
  my $line1 = <$file1>; chomp $line1;
  my $line2 = <$file2>; chomp $line2;
  my $printline1 = $line1;
  my $printline2 = $line2;

  push @buf1, $line1;
  push @buf2, $line2;
  push @printbuf1, $printline1;
  push @printbuf2, $printline2;

#  while ($Compare_Ahead < $Context_Lines) {
#    $line1 = @buf1[$Compare_Ahead];
#    $line2 = @buf2[$Compare_Ahead];
#    $line2 =~ s/ *--.*$//;
#    if ($line1 ne $line2) { last; }
#    ++$Compare_Ahead;
#  }

  $line1 = @buf1[$Compare_Ahead];
  $line2 = @buf2[$Compare_Ahead];
  $line2 =~ s/ *--.*$//;

  if ($line1 ne $line2) {
    while (!eof($file1) && scalar(@buf1) < $diffsize) {
      $line = <$file1>; chomp $line;
      my $printline = $line;

      push @printbuf1, $printline;
      push @buf1, $line;
    }
    
    while (!eof($file2) && scalar(@buf2) < $diffsize) {
      $line = <$file2>; chomp $line;
      my $printline = $line;
#      $line =~ s/ *--.*$//;

      push @printbuf2, $printline;
      push @buf2, $line;
    }

    my $diffs = diff(\@buf1, \@buf2);

    next unless @$diffs;

    my @hunklist;
    my ($hunk,$oldhunk);
    # Loop over hunks. If a hunk overlaps with the last hunk, join them.
    # Otherwise, print out the old one.
    foreach my $piece (@$diffs) {
      $hunk = new Hunk ($piece, $Context_Lines, scalar(@buf1));
      next unless $oldhunk;

      if ($hunk->does_overlap($oldhunk)) {
	$hunk->prepend_hunk($oldhunk);
      } else {
	push @hunklist, $oldhunk;
      }
    } continue {
      $oldhunk = $hunk;
    }
      
    my $change = 0;
    while (scalar(@hunklist) && !$change) {
      $hunk = pop @hunklist;
      $change = $hunk->{"change"};
    }
    push @hunklist, $hunk;
    $last_start1 = $hunk->{"start1"};
    $last_start2 = $hunk->{"start2"};
    $last_end1 = $hunk->{"end1"};
    $last_end2 = $hunk->{"end2"};

    while (scalar(@hunklist)) {
      $hunk = shift @hunklist;
#      $hunk->output_diff(\@buf1, \@buf2);
      $hunk->output_diff(\@printbuf1, \@printbuf2);
    }

    $last_end1 -=  $Context_Lines - 1;
    $last_end2 -=  $Context_Lines - 1;
    $file_offset1 += $last_end1;
    $file_offset2 += $last_end2;
    @printbuf1 = @printbuf1[$last_end1..$#printbuf1];
    @printbuf2 = @printbuf2[$last_end2..$#printbuf2];
    @buf1 = @buf1[$last_end1..$#buf1];
    @buf2 = @buf2[$last_end2..$#buf2];
    while (scalar(@buf1) > $Context_Lines &&
	   scalar(@buf2) > $Context_Lines) {
      $foo1 = @buf1[$Context_Lines];
      $foo2 = @buf2[$Context_Lines];
      if (scalar($foo1) != scalar($foo2) || $foo1 ne $foo2) { last; }
      $foo1 = shift @printbuf1;
      $foo2 = shift @printbuf2;
      $foo1 = shift @buf1;
      $foo2 = shift @buf2;
      ++$file_offset1;
      ++$file_offset2;
    }
  } else {
    ++$file_offset1;
    ++$file_offset2;
    $foo1 = shift @printbuf1;
    $foo2 = shift @printbuf2;
    $foo1 = shift @buf1;
    $foo2 = shift @buf2;
  }
}

close $file1;
close $file2;

sub ffw() {
  if (scalar(@_) != 2) { die "improper usage of ffw\n"; }

  my $FILE = $_[0];
  my $start = $_[1];
  my $count = 0;

  while ($start-- > 0 && !eof($FILE)) {
    <$FILE>;
    $count++;
  }

  if ($start > 0) {die "File too short for ffw amount\n"; }
  return $count;
}

sub parse_filearg() {
  $start = 0;
  split /:/, @_[0];
  if (scalar(@_) > 2) { usage(); }

  $file = $_[0];
  if (scalar(@_) > 1) { $start = $_[1]; }

  return ($file, $start);
}

sub usage() {
  printf "usage: $progname <file1>[:start] <file2>[:start]\n";
  exit 1;
}


# Package Hunk. A Hunk is a group of Blocks which overlap because of the
# context surrounding each block. (So if we're not using context, every
# hunk will contain one block.)
{
package Hunk;

sub new {
# Arg1 is output from &LCS::diff (which corresponds to one Block)
# Arg2 is the number of items (lines, e.g.,) of context around each block
#
# This subroutine changes $File_Length_Difference
#
# Fields in a Hunk:
# blocks      - a list of Block objects
# start       - index in file 1 where first block of the hunk starts
# end         - index in file 1 where last block of the hunk ends
#
# Variables:
# before_diff - how much longer file 2 is than file 1 due to all hunks
#               until but NOT including this one
# after_diff  - difference due to all hunks including this one
    my ($class, $piece, $context_items, $maxlen) = @_;

    my $block = new Block ($piece); # this modifies $FLD!

    my $before_diff = $File_Length_Difference; # BEFORE this hunk
    my $after_diff = $before_diff + $block->{"length_diff"};
    $File_Length_Difference += $block->{"length_diff"};

    # @remove_array and @insert_array hold the items to insert and remove
    # Save the start & beginning of each array. If the array doesn't exist
    # though (e.g., we're only adding items in this block), then figure
    # out the line number based on the line number of the other file and
    # the current difference in file lenghts
    my @remove_array = $block->remove;
    my @insert_array = $block->insert;
    my ($a1, $a2, $b1, $b2, $start1, $start2, $end1, $end2, $change);
    $a1 = @remove_array ? $remove_array[0 ]->{"item_no"} : -1;
    $a2 = @remove_array ? $remove_array[-1]->{"item_no"} : -1;
    $b1 = @insert_array ? $insert_array[0 ]->{"item_no"} : -1;
    $b2 = @insert_array ? $insert_array[-1]->{"item_no"} : -1;

    $start1 = $a1 == -1 ? $b1 - $before_diff : $a1;
    $end1   = $a2 == -1 ? $b2 - $after_diff  : $a2;
    $start2 = $b1 == -1 ? $a1 + $before_diff : $b1;
    $end2   = $b2 == -1 ? $a2 + $after_diff  : $b2;
    $change = scalar(@remove_array) && scalar(@insert_array);

    # At first, a hunk will have just one Block in it
    my $hunk = {
		"start1" => $start1,
		"start2" => $start2,
		"end1" => $end1,
		"end2" => $end2,
		"maxlen" => $maxlen,
		"change" => $change,
		"blocks" => [$block],
              };
    bless $hunk, $class;

    $hunk->flag_context($context_items);

    return $hunk;
}

# Change the "start" and "end" fields to note that context should be added
# to this hunk
sub flag_context {
    my ($hunk, $context_items) = @_;
    return unless $context_items; # no context

    # add context before
    my $start1 = $hunk->{"start1"};
    my $num_added = $context_items > $start1 ? $start1 : $context_items;
    $hunk->{"start1"} -= $num_added;
    $hunk->{"start2"} -= $num_added;

    # context after
    my $end1 = $hunk->{"end1"};
    $num_added = ($end1+$context_items > $hunk->{"maxlen"}) ?
                  $hunk->{"maxlen"} - $end1 :
                  $context_items;
    $hunk->{"end1"} += $num_added;
    $hunk->{"end2"} += $num_added;
}

# Is there an overlap between hunk arg0 and old hunk arg1?
# Note: if end of old hunk is one less than beginning of second, they overlap
sub does_overlap {
    my ($hunk, $oldhunk) = @_;
    return "" unless $oldhunk; # first time through, $oldhunk is empty

    # Do I actually need to test both?
    return ($hunk->{"start1"} - $oldhunk->{"end1"} <= 1 ||
            $hunk->{"start2"} - $oldhunk->{"end2"} <= 1);
}

# Prepend hunk arg1 to hunk arg0
# Note that arg1 isn't updated! Only arg0 is.
sub prepend_hunk {
    my ($hunk, $oldhunk) = @_;

    $hunk->{"start1"} = $oldhunk->{"start1"};
    $hunk->{"start2"} = $oldhunk->{"start2"};

    unshift (@{$hunk->{"blocks"}}, @{$oldhunk->{"blocks"}});
}


# DIFF OUTPUT ROUTINES. THESE ROUTINES CONTAIN DIFF FORMATTING INFO...
sub output_diff {
    if    (defined $main::opt_u) {&output_unified_diff(@_)}
    elsif (defined $main::opt_c) {&output_context_diff(@_)}
    else {die "unknown diff"}
}

sub output_unified_diff {
    my ($hunk, $fileref1, $fileref2) = @_;
    my @blocklist;

    # Calculate item number range.
    my $range1 = $hunk->unified_range(1, $file_offset1);
    my $range2 = $hunk->unified_range(2, $file_offset2);
    print "@@ -$range1 +$range2 @@\n";

    # Outlist starts containing the hunk of file 1.
    # Removing an item just means putting a '-' in front of it.
    # Inserting an item requires getting it from file2 and splicing it in.
    #    We splice in $num_added items. Remove blocks use $num_added because
    # splicing changed the length of outlist.
    #    We remove $num_removed items. Insert blocks use $num_removed because
    # their item numbers---corresponding to positions in file *2*--- don't take
    # removed items into account.
    my $low = $hunk->{"start1"};
    my $hi = $hunk->{"end1"};
    my ($num_added, $num_removed) = (0,0);
    my @outlist = @$fileref1[$low..$hi];
    map {s/^/ /} @outlist; # assume it's just context

    foreach my $block (@{$hunk->{"blocks"}}) {
	foreach my $item ($block->remove) {
	    my $op = $item->{"sign"}; # -
	    my $offset = $item->{"item_no"} - $low + $num_added;
	    $outlist[$offset] =~ s/^ /$op/;
	    $num_removed++;
	}
	foreach my $item ($block->insert) {
	    my $op = $item->{"sign"}; # +
	    my $i = $item->{"item_no"};
	    my $offset = $i - $hunk->{"start2"} + $num_removed;
	    splice(@outlist,$offset,0,"$op$$fileref2[$i]");
	    $num_added++;
	}
    }

    map {s/$/\n/} @outlist; # add \n's
    print @outlist;

}

sub output_context_diff {
    my ($hunk, $fileref1, $fileref2) = @_;
    my @blocklist;

    print "***************\n";
    # Calculate item number range.
    my $range1 = $hunk->context_range(1, $file_offset1);
    my $range2 = $hunk->context_range(2, $file_offset2);

    # Print out file 1 part for each block in context diff format if there are
    # any blocks that remove items
    print "*** $range1 ****\n";
    my $low = $hunk->{"start1"};
    my $hi  = $hunk->{"end1"};
    if (@blocklist = grep {$_->remove} @{$hunk->{"blocks"}}) {
	my @outlist = @$fileref1[$low..$hi];
	map {s/^/  /} @outlist; # assume it's just context
	foreach my $block (@blocklist) {
	    my $op = $block->op; # - or !
	    foreach my $item ($block->remove) {
		$outlist[$item->{"item_no"} - $low] =~ s/^ /$op/;
	    }
	}
	map {s/$/\n/} @outlist; # add \n's
	print @outlist;
    }

    print "--- $range2 ----\n";
    $low = $hunk->{"start2"};
    $hi  = $hunk->{"end2"};
    if (@blocklist = grep {$_->insert} @{$hunk->{"blocks"}}) {
	my @outlist = @$fileref2[$low..$hi];
	map {s/^/  /} @outlist; # assume it's just context
	foreach my $block (@blocklist) {
	    my $op = $block->op; # + or !
	    foreach my $item ($block->insert) {
		$outlist[$item->{"item_no"} - $low] =~ s/^ /$op/;
	    }
	}
	map {s/$/\n/} @outlist; # add \n's
	print @outlist;
    }
}

sub context_range {
# Generate a range of item numbers to print. Only print 1 number if the range
# has only one item in it. Otherwise, it's 'start,end'
    my ($hunk, $flag, $offset) = @_;
    my ($start, $end) = ($hunk->{"start$flag"},$hunk->{"end$flag"});

    # index from 1, not zero
    $start += $offset + 1;
    $end += $offset + 1;
    my $range = ($start < $end) ? "$start,$end" : $end;
    return $range;
}

sub unified_range {
# Generate a range of item numbers to print for unified diff
# Print number where block starts, followed by number of lines in the block
# (don't print number of lines if it's 1)
    my ($hunk, $flag, $offset) = @_;
    my ($start, $end) = ($hunk->{"start$flag"},$hunk->{"end$flag"});

    # index from 1, not zero
    $start += $offset + 1;
    $end += $offset + 1;
    my $length = $end - $start + 1;
    my $first = $length < 2 ? $end : $start; # strange, but correct...
    my $range = $length== 1 ? $first : "$first,$length";
    return $range;
}
} # end Package Hunk

# Package Block. A block is an operation removing, adding, or changing
# a group of items. Basically, this is just a list of changes, where each
# change adds or deletes a single item.
# (Change could be a separate class, but it didn't seem worth it)
{
package Block;
sub new {
# Input is a chunk from &Algorithm::LCS::diff
# Fields in a block:
# length_diff - how much longer file 2 is than file 1 due to this block
# Each change has:
# sign        - '+' for insert, '-' for remove
# item_no     - number of the item in the file (e.g., line number)
# We don't bother storing the text of the item
#
    my ($class,$chunk) = @_;
    my @changes = ();

# This just turns each change into a hash.
    foreach my $item (@$chunk) {
	my ($sign, $item_no, $text) = @$item;
	my $hashref = {"sign" => $sign, "item_no" => $item_no};
	push @changes, $hashref;
    }

    my $block = { "changes" => \@changes };
    bless $block, $class;

    $block->{"length_diff"} = $block->insert - $block->remove;
    return $block;
}


# LOW LEVEL FUNCTIONS
sub op {
# what kind of block is this?
    my $block = shift;
    my $insert = $block->insert;
    my $remove = $block->remove;

    $remove && $insert and return '!';
    $remove and return '-';
    $insert and return '+';
    warn "unknown block type";
    return '^'; # context block
}

# Returns a list of the changes in this block that remove items
# (or the number of removals if called in scalar context)
sub remove { return grep {$_->{"sign"} eq '-'} @{shift->{"changes"}}; }

# Returns a list of the changes in this block that insert items
sub insert { return grep {$_->{"sign"} eq '+'} @{shift->{"changes"}}; }

} # end of package Block