#!/usr/bin/perl -w

# Copyright (C) 2007, 2008 Apple Inc.  All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#
# 1.  Redistributions of source code must retain the above copyright
#     notice, this list of conditions and the following disclaimer. 
# 2.  Redistributions in binary form must reproduce the above copyright
#     notice, this list of conditions and the following disclaimer in the
#     documentation and/or other materials provided with the distribution. 
# 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
#     its contributors may be used to endorse or promote products derived
#     from this software without specific prior written permission. 
#
# THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "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 APPLE OR ITS CONTRIBUTORS 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.

# Merge and resolve ChangeLog conflicts for svn and git repositories

use strict;

use FindBin;
use lib $FindBin::Bin;

use File::Basename;
use File::Path;
use File::Spec;
use Getopt::Long;
use POSIX;
use VCSUtils;

sub conflictFiles($);
sub findChangeLog($);
sub fixChangeLogPatch($);
sub fixMergedChangeLogs($;@);
sub fixOneMergedChangeLog($);
sub mergeChanges($$$);
sub parseFixMerged($$;$);
sub removeChangeLogArguments();
sub resolveChangeLog($);
sub resolveConflict($);
sub showStatus($;$);
sub usageAndExit();

my $SVN = "svn";
my $GIT = "git";

my $fixMerged;
my $printWarnings = 1;
my $showHelp;

my $getOptionsResult = GetOptions(
    'f|fix-merged:s' => \&parseFixMerged,
    'h|help'         => \$showHelp,
    'w|warnings!'    => \$printWarnings,
);

my @changeLogFiles = removeChangeLogArguments();

if (scalar(@ARGV) > 0) {
    print STDERR "ERROR: Files listed on command-line that are not ChangeLogs.\n";
    undef $getOptionsResult;
} elsif (!defined $fixMerged && scalar(@changeLogFiles) == 0) {
    print STDERR "ERROR: No ChangeLog files listed on command-line.\n";
    undef $getOptionsResult;
} elsif (defined $fixMerged && !isGit()) {
    print STDERR "ERROR: --fix-merged may only be used with a git repository\n";
    undef $getOptionsResult;
}

sub usageAndExit()
{
    print STDERR <<__END__;
Usage: @{[ basename($0) ]} [options] path/to/ChangeLog [path/to/another/ChangeLog ...]
  -f|--fix-merged [revision-range] fix git-merged ChangeLog entries; if a revision-range
                                   is specified, run git filter-branch on the range
  -h|--help                        show this help message
  -w|--[no-]warnings               show or suppress warnings (default: show warnings)
__END__
    exit 1;
}

if (!$getOptionsResult || $showHelp) {
    usageAndExit();
}

if (defined $fixMerged && length($fixMerged) > 0) {
    my $commitRange = $fixMerged;
    $commitRange = $commitRange . "..HEAD" if index($commitRange, "..") < 0;
    fixMergedChangeLogs($commitRange, @changeLogFiles);
} elsif (@changeLogFiles) {
    for my $file (@changeLogFiles) {
        if (defined $fixMerged) {
            fixOneMergedChangeLog($file);
        } else {
            resolveChangeLog($file);
        }
    }
} else {
    print STDERR "ERROR: Unknown combination of switches and arguments.\n";
    usageAndExit();
}

exit 0;

sub conflictFiles($)
{
    my ($file) = @_;
    my $fileMine;
    my $fileOlder;
    my $fileNewer;

    if (-e $file && -e "$file.orig" && -e "$file.rej") {
        return ("$file.rej", "$file.orig", $file);
    }

    if (isSVN()) {
        open STAT, "-|", $SVN, "status", $file || die;
        my $status = <STAT>;
        close STAT;
        if (!$status || $status !~ m/^C\s+/) {
            print STDERR "WARNING: ${file} is not in a conflicted state.\n" if $printWarnings;
            return ();
        }

        $fileMine = "${file}.mine" if -e "${file}.mine";

        my $currentRevision;
        open INFO, "-|", $SVN, "info", $file || die;
        while (my $line = <INFO>) {
            $currentRevision = $1 if $line =~ m/^Revision: ([0-9]+)/;
        }
        close INFO;
        $fileNewer = "${file}.r${currentRevision}" if -e "${file}.r${currentRevision}";

        my @matchingFiles = grep { $_ ne $fileNewer } glob("${file}.r[0-9][0-9]*");
        if (scalar(@matchingFiles) > 1) {
            print STDERR "WARNING: Too many conflict files exist for ${file}!\n" if $printWarnings;
        } else {
            $fileOlder = shift @matchingFiles;
        }
    } elsif (isGit()) {
        my $gitPrefix = `$GIT rev-parse --show-prefix`;
        chomp $gitPrefix;
        open GIT, "-|", $GIT, "ls-files", "--unmerged", $file || die;
        while (my $line = <GIT>) {
            my ($mode, $hash, $stage, $fileName) = split(' ', $line);
            my $outputFile;
            if ($stage == 1) {
                $fileOlder = "${file}.BASE.$$";
                $outputFile = $fileOlder;
            } elsif ($stage == 2) {
                $fileNewer = "${file}.LOCAL.$$";
                $outputFile = $fileNewer;
            } elsif ($stage == 3) {
                $fileMine = "${file}.REMOTE.$$";
                $outputFile = $fileMine;
            } else {
                die "Unknown file stage: $stage";
            }
            system("$GIT cat-file blob :${stage}:${gitPrefix}${file} > $outputFile");
        }
        close GIT;
    } else {
        die "Unknown version control system";
    }

    if (!$fileMine && !$fileOlder && !$fileNewer) {
        print STDERR "WARNING: ${file} does not need merging.\n" if $printWarnings;
    } elsif (!$fileMine || !$fileOlder || !$fileNewer) {
        print STDERR "WARNING: ${file} is missing some conflict files.\n" if $printWarnings;
    }

    return ($fileMine, $fileOlder, $fileNewer);
}

sub findChangeLog($) {
    return $_[0] if basename($_[0]) eq "ChangeLog";

    my $file = File::Spec->catfile($_[0], "ChangeLog");
    return $file if -d $_[0] and -e $file;

    return undef;
}

sub fixChangeLogPatch($)
{
    my $patch = shift;
    my $contextLineCount = 3;

    return $patch if $patch !~ /\n@@ -1,(\d+) \+1,(\d+) @@\n( .*\n)+(\+.*\n)+( .*\n){$contextLineCount}$/m;
    my ($oldLineCount, $newLineCount) = ($1, $2);
    return $patch if $oldLineCount <= $contextLineCount;

    # The diff(1) command is greedy when matching lines, so a new ChangeLog entry will
    # have lines of context at the top of a patch when the existing entry has the same
    # date and author as the new entry.  This nifty loop alters a ChangeLog patch so
    # that the added lines ("+") in the patch always start at the beginning of the
    # patch and there are no initial lines of context.
    my $newPatch;
    my $lineCountInState = 0;
    my $oldContentLineCountReduction = $oldLineCount - $contextLineCount;
    my $newContentLineCountWithoutContext = $newLineCount - $oldLineCount - $oldContentLineCountReduction;
    my ($stateHeader, $statePreContext, $stateNewChanges, $statePostContext) = (1..4);
    my $state = $stateHeader;
    foreach my $line (split(/\n/, $patch)) {
        $lineCountInState++;
        if ($state == $stateHeader && $line =~ /^@@ -1,$oldLineCount \+1,$newLineCount @\@$/) {
            $line = "@@ -1,$contextLineCount +1," . ($newLineCount - $oldContentLineCountReduction) . " @@";
            $lineCountInState = 0;
            $state = $statePreContext;
        } elsif ($state == $statePreContext && substr($line, 0, 1) eq " ") {
            $line = "+" . substr($line, 1);
            if ($lineCountInState == $oldContentLineCountReduction) {
                $lineCountInState = 0;
                $state = $stateNewChanges;
            }
        } elsif ($state == $stateNewChanges && substr($line, 0, 1) eq "+") {
            # No changes to these lines
            if ($lineCountInState == $newContentLineCountWithoutContext) {
                $lineCountInState = 0;
                $state = $statePostContext;
            }
        } elsif ($state == $statePostContext) {
            if (substr($line, 0, 1) eq "+" && $lineCountInState <= $oldContentLineCountReduction) {
                $line = " " . substr($line, 1);
            } elsif ($lineCountInState > $contextLineCount && substr($line, 0, 1) eq " ") {
                next; # Discard
            }
        }
        $newPatch .= $line . "\n";
    }

    return $newPatch;
}

sub fixMergedChangeLogs($;@)
{
    my $revisionRange = shift;
    my @changedFiles = @_;

    if (scalar(@changedFiles) < 1) {
        # Read in list of files changed in $revisionRange
        open GIT, "-|", $GIT, "diff", "--name-only", $revisionRange || die;
        push @changedFiles, <GIT>;
        close GIT || die;
        die "No changed files in $revisionRange" if scalar(@changedFiles) < 1;
        chomp @changedFiles;
    }

    my @changeLogs = grep { defined $_ } map { findChangeLog($_) } @changedFiles;
    die "No changed ChangeLog files in $revisionRange" if scalar(@changeLogs) < 1;

    system("$GIT filter-branch --tree-filter 'PREVIOUS_COMMIT=\`$GIT rev-parse \$GIT_COMMIT^\` && MAPPED_PREVIOUS_COMMIT=\`map \$PREVIOUS_COMMIT\` $0 -f \"" . join('" "', @changeLogs) . "\"' $revisionRange");

    # On success, remove the backup refs directory
    if (WEXITSTATUS($?) == 0) {
        rmtree(qw(.git/refs/original));
    }
}

sub fixOneMergedChangeLog($)
{
    my $file = shift;
    my $patch;

    # Read in patch for incorrectly merged ChangeLog entry
    {
        local $/ = undef;
        open GIT, "-|", $GIT, "diff", ($ENV{GIT_COMMIT} || "HEAD") . "^", $file || die;
        $patch = <GIT>;
        close GIT || die;
    }

    # Always checkout the previous commit's copy of the ChangeLog
    system($GIT, "checkout", $ENV{MAPPED_PREVIOUS_COMMIT} || "HEAD^", $file);

    # The patch must have 0 or more lines of context, then 1 or more lines
    # of additions, and then 1 or more lines of context.  If not, we skip it.
    if ($patch =~ /\n@@ -(\d+),(\d+) \+(\d+),(\d+) @@\n( .*\n)*((\+.*\n)+)( .*\n)+$/m) {
        # Copy the header from the original patch.
        my $newPatch = substr($patch, 0, index($patch, "@@ -${1},${2} +${3},${4} @@"));

        # Generate a new set of line numbers and patch lengths.  Our new
        # patch will start with the lines for the fixed ChangeLog entry,
        # then have 3 lines of context from the top of the current file to
        # make the patch apply cleanly.
        $newPatch .= "@@ -1,3 +1," . ($4 - $2 + 3) . " @@\n";

        # We assume that top few lines of the ChangeLog entry are actually
        # at the bottom of the list of added lines (due to the way the patch
        # algorithm works), so we simply search through the lines until we
        # find the date line, then move the rest of the lines to the top.
        my @patchLines = map { $_ . "\n" } split(/\n/, $6);
        foreach my $i (0 .. $#patchLines) {
            if ($patchLines[$i] =~ /^\+\d{4}-\d{2}-\d{2}  /) {
                unshift(@patchLines, splice(@patchLines, $i, scalar(@patchLines) - $i));
                last;
            }
        }

        $newPatch .= join("", @patchLines);

        # Add 3 lines of context to the end
        open FILE, "<", $file || die;
        for (my $i = 0; $i < 3; $i++) {
            $newPatch .= " " . <FILE>;
        }
        close FILE;

        # Apply the new patch
        open(PATCH, "| patch -p1 $file > /dev/null") || die;
        print PATCH $newPatch;
        close(PATCH) || die;

        # Run "git add" on the fixed ChangeLog file
        system($GIT, "add", $file);

        showStatus($file, 1);
    } elsif ($patch) {
        # Restore the current copy of the ChangeLog file since we can't repatch it
        system($GIT, "checkout", $ENV{GIT_COMMIT} || "HEAD", $file);
        print STDERR "WARNING: Last change to ${file} could not be fixed and re-merged.\n" if $printWarnings;
    }
}

sub mergeChanges($$$)
{
    my ($fileMine, $fileOlder, $fileNewer) = @_;

    my $traditionalReject = $fileMine =~ /\.rej$/ ? 1 : 0;

    local $/ = undef;

    my $patch;
    if ($traditionalReject) {
        open(DIFF, "<", $fileMine);
        $patch = <DIFF>;
        close(DIFF);
        rename($fileMine, "$fileMine.save");
        rename($fileOlder, "$fileOlder.save");
    } else {
        open(DIFF, "-|", qw(diff -u), $fileOlder, $fileMine) || die;
        $patch = <DIFF>;
        close(DIFF);
    }

    unlink("${fileNewer}.orig");
    unlink("${fileNewer}.rej");

    open(PATCH, "| patch --fuzz=3 $fileNewer > /dev/null") || die;
    print PATCH fixChangeLogPatch($patch);
    close(PATCH);

    my $result;

    # Refuse to merge the patch if it did not apply cleanly
    if (-e "${fileNewer}.rej") {
        unlink("${fileNewer}.rej");
        unlink($fileNewer);
        rename("${fileNewer}.orig", $fileNewer);
        $result = 0;
    } else {
        unlink("${fileNewer}.orig");
        $result = 1;
    }

    if ($traditionalReject) {
        rename("$fileMine.save", $fileMine);
        rename("$fileOlder.save", $fileOlder);
    }

    return $result;
}

sub parseFixMerged($$;$)
{
    my ($switchName, $key, $value) = @_;
    if (defined $key) {
        if (defined findChangeLog($key)) {
            unshift(@ARGV, $key);
            $fixMerged = "";
        } else {
            $fixMerged = $key;
        }
    } else {
        $fixMerged = "";
    }
}

sub removeChangeLogArguments()
{
    my @results = ();

    for (my $i = 0; $i < scalar(@ARGV); ) {
        my $file = findChangeLog($ARGV[$i]);
        if (defined $file) {
            splice(@ARGV, $i, 1);
            push @results, $file;
        } else {
            $i++;
        }
    }

    return @results;
}

sub resolveChangeLog($)
{
    my ($file) = @_;

    my ($fileMine, $fileOlder, $fileNewer) = conflictFiles($file);

    return unless $fileMine && $fileOlder && $fileNewer;

    if (mergeChanges($fileMine, $fileOlder, $fileNewer)) {
        if ($file ne $fileNewer) {
            unlink($file);
            rename($fileNewer, $file) || die;
        }
        unlink($fileMine, $fileOlder);
        resolveConflict($file);
        showStatus($file, 1);
    } else {
        showStatus($file);
        print STDERR "WARNING: ${file} could not be merged using fuzz level 3.\n" if $printWarnings;
        unlink($fileMine, $fileOlder, $fileNewer) if isGit();
    }
}

sub resolveConflict($)
{
    my ($file) = @_;

    if (isSVN()) {
        system($SVN, "resolved", $file);
    } elsif (isGit()) {
        system($GIT, "add", $file);
    } else {
        die "Unknown version control system";
    }
}

sub showStatus($;$)
{
    my ($file, $isConflictResolved) = @_;

    if (isSVN()) {
        system($SVN, "status", $file);
    } elsif (isGit()) {
        my @args = qw(--name-status);
        unshift @args, qw(--cached) if $isConflictResolved;
        system($GIT, "diff", @args, $file);
    } else {
        die "Unknown version control system";
    }
}