diffの出力形式をちゃんと理解していなかったのでpatchを実装してみた

diffはプログラマ七つ道具のひとつというか、よく使うんですが、diffの出力については大体の読み方は理解しているものの、細かなところまでは理解できていませんでした。

なんで、diffの生成した差分出力をオリジナルファイルに適応する、これまたプログラマ七つ道具*1といえそうなpatchを勉強がてら実装してみました。

まず、diffの形式ですが、一般的なunified diffを対象にします。例えば、以下のようなものです。

--- hello1.pl   2007-10-12 04:51:39.000000000 +0900
+++ hello2.pl   2007-10-12 04:52:11.000000000 +0900
@@ -1,5 +1,5 @@
 #!/usr/bin/env perl
-#hello1.pl
+#hello2.pl
 use strict;
 use warnings;
 
@@ -7,3 +7,6 @@
     my $m = 'hello';
     print "$m\n";
 }
+
+# call hello
+hello();

これは、つぎの二つのファイルに対してdiff -uすると取得できました。

hello1.pl

#!/usr/bin/env perl
#hello1.pl
use strict;
use warnings;

sub hello {
    my $m = 'hello';
    print "$m\n";
}

hello2.pl

#!/usr/bin/env perl
#hello2.pl
use strict;
use warnings;

sub hello {
    my $m = 'hello';
    print "$m\n";
}

# call hello
hello();

diffの出力は、まず差分をとった二つのファイルの情報から始まります。そのあとに続く@@で始まる行以下が差分情報です。@@で始まる行から、次に@@が始まるまでが一つの差分情報のかたまりになります。一番始めに示したdiffの出力の例だと、一つ目の差分情報のかたまりは以下になります。

@@ -1,5 +1,5 @@
 #!/usr/bin/env perl
-#hello1.pl
+#hello2.pl
 use strict;
 use warnings;

この差分情報の中には、元のファイルから、どの範囲が変わったのかという情報と、どう変わったかという情報、さらに変わってからのどの範囲にあたるかという情報が含まれています。

一番先頭の@@で囲まれた部分が、差分の範囲に関する情報をもっています。

@@ -1,5 +1,5 @@

これを例にとって説明します。
@@の次に現れる"-1,5"は、変更がなされる前のファイルのどの部分に対しての差分情報であるかを示します。これは、変更前のファイルの1行目から5行分についての差分であることを示しています。
その次に現れる"+1.5"は、変更がなされた後のファイルのどの部分に対しての差分情報であるかを示します。これも同様に、変更前のファイルの1行目から5行分についての差分であることを示しています。

@@の行につづく行が、どのように変更されたのかという情報です。上の例だと以下の部分になります。

 #!/usr/bin/env perl
-#hello1.pl
+#hello2.pl
 use strict;
 use warnings;

この部分の行の一番左の文字が、変更の種類を示します。' '(空白)ならば、変更なし、'+'ならば追加、'-'ならば削除されたことを意味します。

さて、これだけの情報があればpatchは実装できるはずです。おおまかに以下のようにPerlで実装してみました。ちなみに、UNIXで標準でついているpatchはもっと高機能で、パッチを外したり、変更場所が多少かわっていてもパターンマッチで見つけてくれたりします。今回作ったのは、本当に単純に、unified diffを読み込んでその通りにパッチするソフトウェアです。

use strict;
use warnings;
use Perl6::Slurp;

my ($ORIGFILE, $PATCHFILE) = @ARGV;

my $orig_contents  = slurp $ORIGFILE;
my $patch_contents = slurp $PATCHFILE;

# @@の単位に分ける
my @diffs = split m/^(?=@@)/xms, $patch_contents; shift @diffs;
my @orig_lines = split m/\n/, $orig_contents;

# @@の単位ごとに処理する
for my $diff (@diffs) {
    my @diff_lines = split /\n/, $diff;

    # @@でかこまれた行範囲情報を取得する
    my $range_line = shift @diff_lines;
    my ($before_start, $before_amount, $after_start, $after_amount)
        = $range_line =~ m{
            ^
            \@\@ \s 
            -(\d+?),(\d+?) \s 
            \+(\d+?),(\d+?) \s
            \@\@
            $
        }xms;
    $before_start--; $before_amount--; $after_start--; $after_amount--;
        # 配列の添字と行数を合わせる

    my $count = $after_start;
    for my $diff_line (@diff_lines) {
        # 変更方法を取得
        my ($op) = $diff_line =~ m/^(.)/xms;
        $diff_line =~ s/^.//xms;

        # ' 'なら何もしない
        if ($op eq ' ') {
            $count += 1;
        }
        # +なら行を挿入
        elsif ($op eq '+') {
            @orig_lines = (
                $count > 0 ? @orig_lines[0..$count-1] : (),
                $diff_line,
                @orig_lines[$count..$#orig_lines],
            );
            $count += 1;
        }
        # -なら行を削除
        elsif ($op eq '-') {
            @orig_lines = (
                @orig_lines[0..$count-1],
                $count < $#orig_lines 
                    ? @orig_lines[$count+1..$#orig_lines] : (),
            );
        }
    }
}

# 出力
print join "\n", @orig_lines;