#!/usr/bin/perl

$VERSION='1.1';

use Getopt::Std;
use Algorithm::Diff qw(traverse_sequences);

getopts('ucrbtw');

undef $opt_c if $opt_u;

while(1) {
  # skip garbage
  while(1) {
    if(/^[-*]{3} /)
    {
      $_.=<>;
      last if /^\*\*\* .*\n--- / || /^--- .*\n\+\+\+ /;
    }
    print;
    exit 0 unless $_=<>;
  };
  # print header
  s/^(.*)\n(.*)$/$2\n$1/ if $opt_r;
  if($opt_c) {
    s/^... /*** /; s/\n... /\n--- /;
  } else {
    s/^... /--- /; s/\n... /\n+++ /;
  }
  $output=$_;
  while(1) {
    # get hunk
    $_=$preread || <>;
    $preread='';
    if(/^@@ -(\d+),(\d+) \+(\d+),(\d+) @@\n$/) {
      #unified hunk
      $S='';
      ($os, $ol, $ns, $nl)=($1,$2,$3,$4);
      $oe=$os+$ol-1;
      $ne=$ns+$nl-1;
      @o=@n=();
      while($ol > @o || $nl > @n) {
        $a=expand($_=<>);
        push @o, $a if /^[- ]/;
        push @n, $a if /^[+ ]/;
      }
      die "Corrupted diff 1 ($#o,$#n): $. => $_" unless $ol == @o && $nl == @n;
    } elsif($_ eq "***************\n") {
      # context hunk
      $S=' ';
      die "Corrupted diff 2: $. => $_" unless $_=<>;
      die "Corrupted diff 3: $. => $_" unless /^\*\*\* (\d+),(\d+) \*\*\*\*\n/;
      ($os,$oe)=($1,$2);
      $ol=$oe-$os+1;
      @o=@n=();
      $_=<>;
      if (/^[-+! ] /) {
        $f=(/^  /);
        push @o, $_=expand($_);
        push @n, $_ if $f;
        while($ol > @o) {
          $_=<>;
          $f=(/^  /);
          push @o, $_=expand($_);
          push @n, $_ if $f;
        }
        die "Corrupted diff 4: $. => $_" unless $_=<>;
      }
      die "Corrupted diff 5 ($#o): $. => $_" unless /^--- (\d+),(\d+) ----\n/;
      ($ns,$ne)=($1,$2);
      $nl=$ne-$ns+1;
      $_=<>;
      if (/^[-+! ] /) {
        @n=();
        $o=!@o;
        $f=(/^  /);
        push @n, $_=expand($_);
        push @o, $_ if $o && $f;
        while($nl > @n) {
          $_=<>;
          $f=(/^  /);
          push @n, $_=expand($_);
          push @o, $_ if $o && $f;
        }
      }
      else {
        $preread=$_;
      }
      die "Corrupted diff 7 ($#o,$#n): $. => $_" unless $ol == @o && $nl == @n;
    } else {
      last;
    }
    # output
    @retval=();
    $hunk=[], $m=0;

sub discard { unless ($m) { $m=1; push @retval, $hunk; $hunk=[]; } push @$hunk, ['-', $_[1]] }
sub add     { unless ($m) { $m=1; push @retval, $hunk; $hunk=[]; } push @$hunk, ['+', $_[1]] }
sub match   { if     ($m) { $m=0; push @retval, $hunk; $hunk=[]; } push @$hunk, [' ', $_[1]] }

    if ($opt_r) { my @tmp=@o; @o=@n; @n=@tmp; }
    traverse_sequences( \@o, \@n,
            { MATCH => \&match, DISCARD_A => \&discard,DISCARD_B => \&add },
            \&diffpack );
    push @retval, $hunk;

# use Data::Dumper;
# $Data::Dumper::Terse=1;
# $Data::Dumper::Indent=1;
# print Dumper(\@retval);
    
    $hunks='';
    
    for $N (0..$#retval) {
      my $hunk=@retval[$N];
      my $hl=$#$hunk;
      my $a=$hunk->[0]->[0];
      my $b=$hunk->[$hl]->[0];
      $type=($a eq ' ' ? ' ' :
             $a eq '+' ? '+' :
             $b eq '-' ? '-' : '!');
      if ($type eq ' ') {
        print_lines(@$hunk[0..2]) if $N;
        ($N && $hl < 8)
        ? print_lines(@$hunk[3..$hl])
        : open_hunk(@$hunk[-3..-1]) if $N < $#retval;
      } else {
        $N ? print_lines(@$hunk) : open_hunk(@$hunk);
      }
    }
    open_hunk();
  }
  print $output;
}

sub open_hunk {
  if ($hunks) {
    # closing previous hunk first
    if ($opt_c) {
      $output.= sprintf "***************\n*** %d,%d ****\n", $hos, $hos+$hol-1;
      $output.= $hunks;
      $output.= sprintf "--- %d,%d ----\n", $hns, $hns+$hnl-1;
      $output.= $hunks2;
    } else {
      $output.= sprintf "@@ -%d,%d +%d,%d @@\n", $hos, $hol, $hns, $hnl;
      $output.= $hunks;
    }
  }
  $hos=$hns=$hol=$hnl=0;
  $hunks=$hunks2='';
  for (reverse @_) {
    $hos=$_->[1] if $_->[0] ne '+';
    $hns=$_->[1] if $_->[0] ne '-';
  }
  $hos+=$os;
  $hns+=$ns;
  print_lines(@_);
}

sub print_lines {
  for (@_) {
    next unless $_;
    if ($_->[0] eq '+') {
      if ($opt_c) {
        $hunks2.="$type ".@n[$_->[1]];
      } else {
        $hunks.='+'.@n[$_->[1]];
      }
      $hnl++;
      unshift @o, "<<EOF>>\n";
    } elsif ($_->[0] eq '-') {
      if ($opt_c) {
        $hunks.="$type ".@o[$_->[1]];
      } else {
        $hunks.='-'.@o[$_->[1]];
      }
      shift @o;
      $hol++;
    } else {
      if ($opt_c) {
        $hunks.='  '.@o[$_->[1]];
        $hunks2.='  '.@o[$_->[1]];
      } else {
        $hunks.=' '.@o[$_->[1]];
      }
      $hol++;
      $hnl++;
    }
  }
}

sub expand {
  local $_=shift;
  die "Corrupted diff 6: $. => $_" unless s/^[-!+ ]$S//;
  if ($opt_t)
  {
    1 while s/^([^\t]*)(\t+)/$1.(" "x(length($2)*8-length($1)%8))/e;
  }
  $_;
}

sub diffpack {
  local $_=shift;
  if ($opt_b) {
    s/\s+/ /g;
    s/^ //;
    s/ $//;
  }
  s/\s//g if $opt_w;
  $_;
}

=head1 NAME

rediff - Diff format converted (unified <-> context).

=head1 README

Diff format converted (unified <-> context).
This script takes context or unified diff, and produces a diff,
that would be created by C<diff> program if it would be run with command-line
options passed to this script. C<-c>, C<-u>, C<-b>, C<-w>, C<-t> options are
supported. Non-diff C<-r> option can be used to reverse the diff.
E.g. convert to unified diff with tabs expanded:

  rediff -ut <old_diff >new_diff

=head1 PREREQUISITES

Algorithm::Diff

=head1 SCRIPT CATEGORIES

UNIX/System_administration
VersionControl/CVS

=cut