拡散テキストに対する変動調整法によるパッチ (Karl Fogel)

拡散テキストに対する変動調整法によるパッチ[Rev:5509 + jp]

Karl Fogel <kfogel@collab.net>

$LastChangedDate: 2003-01-14 07:43:13 +0900 (Tue, 14 Jan 2003) $
Original Date: 22 May, 2001
Canonical URL: http://svn.collab.net/repos/svn/trunk/www/variance-adjusted-patching.html

翻訳: Tez Kamihira <tez@bluegate.org>

Original: https://svn.apache.org/repos/asf/subversion/branches/1.0.x/www/variance-adjusted-patching.html
Latest: https://svn.apache.org/repos/asf/subversion/trunk/notes/variance-adjusted-patching.html

ブランチのマージに伝統的なコンテキスト diff / unidiff 形式を使うバージョン管理システムは「高変動」状況では高い確率で失敗する傾向にあります。ここで「高変動」状況というのは、ブランチのテキストが、ソースのテキストに比べて、変更された行、削除、追加などの合計が、大雑把に言って、5-10%以上異なっているような状況を言います。

普通のパッチアプリケーションの問題は、関連するテキストハンクや、そのハンクのコンテキストが、ソーステキストからそれほど大きく変更されていない、ということに依存していることです。そのようなハンクの位置は変動します。つまり、そのハンクのそばにテキストが挿入されたり削除されたりするので、ターゲットファイル中での位置がそれによって影響を受けます。しかし、ハンクそれ自身は、空白や、他のささいな(つまり、自動的に無視できるような)変更を除いては、変更されていないかもしれません。もしそのような変更があれば、パッチアプリケーションは失敗するでしょう。

変動調整法は、パッチが作成されてからターゲットテキストにおきた差分を補償するためにパッチを変形する手続きです。これによって、新しいパッチは新しいターゲットテキストに適用可能となり、依然として古いパッチと同じ効果をもつようになります。これは本質的には、パッチに対するパッチであると言えます。たとえば、ブランチ B が、トランク T から大きく離れてしまっている状態で、リビジョン T:18 から T:19 への修正内容を、B:10 にマージして B:11 を作りたいとしましょう。もし B:10 が T:18 と非常に異なっていると、マージは、論理的な衝突がないにもかかわらず、テキスト上の衝突によって失敗するかも知れません。変動調整法は T:18-T:19間の変更を修正することで、それをB:10に対してきれいに適用できるようにするものです。

これは可能です。なぜなら、パッチのハンクが、ターゲットテキスト中に現れることを期待している任意の与えられた行について、(たとえば、コンテキスト diff では、それはコンテキスト行と、影響を受けた前のバージョンのことになりますXXX)、バージョン管理システムは、もしそれらに共通の祖先があるなら、ソースとターゲットテキストの両方に存在する行に関する履歴を知ることができるからです。この手続きは "cvs annotate" で実行される計算と非常によく似ています。大雑把に言うと、境界外の挿入や削除による変動を無視する限りにおいて、それぞれの行について以下のどれかが成立します。

その行は、ソースとターゲットの両方で変更せずに存在している
もし行がターゲットとソースの中にまだ存在しているなら、それは共通の先祖以降でどちらからも削除されなかったか、あるいは、削除されたが、その後復活したかのいずれかです。diff は何もする必要がありません。

その行はソースで修正されたが、ターゲットでは修正されていない
diff のハンク中で、行はターゲットのバージョンの行を反映するために変更されなくてはなりません。そうすることで diff はターゲットに適用可能となります。
わたしたちが、その行が"変更された"というとき、それは単にこの行が現れた場所では異なる行が現れる、ということを意味します。(XXX) これは、その行が編集されたのか、あるいはターゲットに新しい行が挿入されたからであるのかは、関係ありません。(べつの言い方をすると、古いバージョンの行がターゲット中のどこか近くに現れるかどうかには関係がない、ということです)XXX 重要なのは新しいテキストはハンクが古いテキストを期待する場所に現れるため、われわれはハンクが新しい行を期待するように変更する方法をもっているということです。

その行はターゲット中では変更されているが、ソースでは変更されていない
上と同じです: diff のハンク中で、行はターゲットのバージョンの行が反映されるように修正すべきであり、これによって diff はターゲットに対して適用可能となります。もし直感的でないようなら、一服してからもう一度読み返してみてください。

行はターゲット中に存在しない
二つの理由のどちらかが考えられます:
1. その行はソース中で新規に作られ、それはターゲットがブランチ化された後のことであるか、
2. その行はブランチ化の後でターゲットから削除された
どちらの場合でも、行はターゲットテキスト中の"対応した"行に対する変更を必要とします -- "対応した"行とはつまり、ターゲット中で以前に期待されていた行の場所を占めるようになった行のことです。バージョン管理システムは上記どちらの場合を適用すればよいかを決定するための十分な情報を持っていて、その情報を使って、ターゲット中に現在あるどの行が、欠落している行の置き換えとしての最良の候補であるかを決めることができます。(XXX)

ソースに存在しない行のケースは起こりえません: もし現在のソースに存在しないのなら、それは diff の期待されるテキスト部分の中に現れることはできないからです。

パッチプログラムは適用される時点での変動を修正することができますが、バージョン管理システムも、ハンク中の行番号を調整することができますがそれは、ソースまたはターゲット中の、ハンクによって覆われた範囲の外側でおきた挿入や削除を補償することによっておこないます。もちろんターゲットに対する、まだコミットされていないローカル編集は diff 中で補償されることはできませんが -- その場合でも、私たちはパッチプログラム自身のオフセット調整機能と、それを扱う場合のあいまいな要因を信頼することができるはずです。(XXX)

上の決まりはどのようにして変動調整法が動くかのあまり形式的ではない説明です。以下では、アルゴリズムをもう少し形式的に記述し、バージョン管理システムが任意の状況下で、どのようにして変動調整を実行するかを見ていきます。このアルゴリズムは実際には強力すぎるものです -- 論理的な最大限度まで許容すれば、それは、実際にはユーザがほとんど衝突と解釈して欲しいような状況にまで、きれいに適用することができるパッチを生成してしまいます。それで、調整レベルを選択させることが必要になります。デフォルトの選択レベルとして良いものは、多分コンテキストの変動を補償することを許しはするが、期待されるターゲットの行にある変動については、補償しない、というものでしょう。いずれにせよ、完全な、非選択的なアルゴリズムは以下ですが、必要に応じて選択レベルのつまみをつける場所は明らかでしょう。

変動調整法のアルゴリズム

いくつかの定義:

挿入: 共通の祖先以降で、ソースまたはターゲットのどちらかに追加された新しい行のこと
削除: 共通の祖先以降で、ソースまたはターゲットのどちらかから削除された行のこと
編集: 共通の祖先以降で、ソースまたはターゲットのどちらかで修正された行のこと
範囲外: 共通の祖先以降でソースまたはターゲットでおきた出来事のうち、変動調整するパッチ中の diff ハンクのどれにも現れないような行にたいしておきたもののことを言います。たとえば、範囲外挿入とは、パッチ中のどのハンクにも直接関係しないどこかの領域で追加された行のことを意味します。範囲外削除とは、どのハンクにも属さないどこかの領域でおきた削除行のことを意味します。
範囲内: 共通の祖先以降でソースまたはターゲットでおきた出来事のうち、変動調整するパッチの diff ハンクのどれかに含まれる行でおきたもののことを言います。たとえば、範囲内挿入とは、どれかのハンクによって影響を受ける領域中に対する追加行を意味します。範囲内削除はハンクによって影響を受けるどこかの領域からの削除行を意味します。
文脈: 文脈だけのためにハンク中に含まれる行のことを言います -- そのような行はパッチによって影響を受けません。
目的行、影響行: (同じ意味で使われます)。パッチによって実際に影響を受ける行のことを言います。編集または削除される行の場合、その行はターゲットテキスト中にすでに存在しています。追加される行の場合、その行はパッチが適用された後でだけ存在します。どの場合でも、パッチ中のあるハンクには存在しています。

シナリオの説明:

二つの作業ラインが "trunk"/"branch"である必要はありませんが、理解を容易にするため、以下ではそのような言葉を使います。現実的な観点から、その二つは、共通の祖先を持つ二つの開発ラインであるとします。

ブランチ B はトランク T の T:8 で分岐したものだとしましょう。つまり、T:8 == B:1 です。最新のトランクのリビジョンは T:20 で、最新のブランチのリビジョンは B:15 です。ブランチ B 上の作業コピーを持ったユーザが T:19-T:20 間の変更をマージしたいとします。簡単のためにこの変更を"patch"の頭文字をとって P とします。(一般性を失うことなく、一つのファイルだけがパッチされると仮定することができます。マージ中に複数のファイルがある場合は、すべてのファイルに対して同じアルゴリズムを適用することになります。)

調整されていない P を B:15 に直接パッチすることには二つの問題があります。T:19 のソーステキストを元にした P は、

B:15 に現れない変更が含まれています。つまり、T:9 から T:19 までの変更です。

B:15に現れる変更のなかで含まれていないものがあります。つまり、 B:2からB:15までの変更です。

P を調整するためには、まず diff T:8-T:19 の間を一通り見ていき、適切な形でハンクを調整します。T:8-T:19 間のそれぞれの行は以下のどれかのタイプに帰着します:

範囲外の追加行: 追加された場所の後にくる P のすべてのハンクの行番号を 1 減らします。これは B では追加がおきていないので、追加の影響を取り消すためのものです。

範囲外の削除行: 削除された場所の後にくる P のすべてのハンクの行番号を 1 増やします。これは B では削除がおきていないので、削除の影響を取り消すためのものです。

範囲外の編集行: なにもしません。範囲外の編集は P とは無関係です。

P の文脈範囲中での追加行: 文脈から対応する行を削除し、必要に応じて、B:15 中の領域の内容にもとづいて新しい文脈で置き換え、行番号とマッピングを適切な形に調整します。

P の中の影響のあるテキスト範囲での追加行: これは依存問題をひきおこします -- B が分岐したあと、T におきた変更に依存しているような、T:18-T:19 の変更の部分です。これには、ユーザが何を期待するかに応じて、いくつもの可能な動作が考えられます。一つは、有用な情報を含むエラーを生成することで、T:18-T:19 は、なにか別の変更に依存している、と報告します。(T:N-T:M ここで、N>=8, M<=18 そして　M-N == 1 です。) 正確なリビジョンは、少し時間がかかるにせよ、"cvs annotate" と同じ手続きをとることによって自動的に発見することができます。別の選択は、P の中に変更を含ませてしまうことで、その変更は、テキストの"後の"バージンへの挿入として扱われ、行番号と対応は適切に調整されます。(そして、もしこれらすべてがディレクトリマージのアルゴリズムによく似ていると感じないようでしたらもう一服してください) 三番目の選択は、挿入としてそれを含めはしますが、メタデータを使って(たとえば、CVSのような衝突マーカ)、パッチされようとしている行は、 B の中には存在していないということを示すことです。

P の範囲内であるような削除行: 別の世界が必要になります-- この状況は私たちのものでは起こりえません。

範囲内の編集行: P の中の適切なハンク中での対応する行の "前の"バージョン中での編集を戻して、P が適用されるときに、B の中に現れるような行のバージョンを取得します。(XXX)

つぎに、diff B:1-B:15 間を一通りたどって、 P をさらに調整します。

範囲外の追加行: 追加行のあとにくる P のすべてのハンクの行番号を 1 増やします。

範囲外の削除行: 削除行のあとにくる P のすべてのハンクの行番号を 1 減らします。

範囲外の編集行: なにもしません。範囲外の編集は P とは無関係です。

P の文脈範囲中での追加行: 適切なハンク中での両方の側での文脈にその行を追加し、そのハンクと、それ以降のすべてのハンク中での行番号を調整します。

P の影響を受けるテキスト範囲中での追加行: P 中での文脈にその行を追加し、行番号を適切に調整します。

P の範囲内での削除行: 依存の問題がおきます。前述の"P での影響を受けるテキスト範囲への追加行" の、最初のパスを参照してください。

範囲内での編集行: P の適切なハンク中での対応する行の "前の"バージョンに対して、その編集を適用します。

これで P は B:15 に対して適用する準備は整っていて、ローカル編集に対する適用に対しても十分な文脈を持っています。

両方のループ中のステップは圧縮することができます。たとえば、ハンク中の追加行と削除行の数がバランスしている場合、後のハンク中での行番号調整は不要となります。バランスしているかどうかは、問題のハンク中の行の数を調べるだけで簡単に知ることができます。

アルゴリズムは、情報を失うことなしに、"本来の"衝突を柔軟に扱います。"本来の"衝突というのは、T:8-T:19 の変更のうち、B:1-B:15 の変更と重なっているもののことです。それは、文脈と、"前の"行の状態によって、できるだけ目立つ形で取り扱われます。依存情報を含む形でエラーを報告するか、両者の重なった部分を、CVSスタイルの衝突マーカでくくった形で、ユーザに処理させることもできます。あるいはもし衝突マーカが望むようなインターフェースではない場合、パッチは衝突を何か別のメタデータ形式(パッチ形式のコメントの部分を使って)で保存することもでき、他のツールはそれを報告し、解消するのを助けることができます。

いくつかのパッチに対して、調整法がどのように働くかを簡単に見て見ましょう。ここでは簡単な例を用意しました。トランクからブランチへ、個別の変更を移そうという場合です。トランク T 上のリビジョン 1 は以下のようになっています:

int main (int argc, char **argv)
{
  /* line minus-five of context */
  /* line minus-four of context */
  /* line minus-three of context */
  /* line minus-two of context */
  /* line minus-one of context */
  printf ("Hello, world!\n");
  /* line plus-one of context */
  /* line plus-two of context */
  /* line plus-three of context */
  /* line plus-four of context */
  /* line plus-five of context */
}

ブランチ B も存在し、トランクのリビジョン T:1 から分岐したものだとします。ブランチ B 上で、文脈に対する変更をコミットします(単語で表した数値を数字に置き換えます)。するとB:2 は以下のような感じになります:

int main (int argc, char **argv)
{
  /* line -5 of context */
  /* line -4 of context */
  /* line -3 of context */
  /* line -2 of context */
  /* line -1 of context */
  printf ("Hello, world!\n");
  /* line +1 of context */
  /* line +2 of context */
  /* line +3 of context */
  /* line +4 of context */
  /* line +5 of context */
}

一方トランクでは、中間の行だけを変更します。それで T:2 は以下のようにコミットされました。

int main (int argc, char **argv)
{
  /* line minus-five of context */
  /* line minus-four of context */
  /* line minus-three of context */
  /* line minus-two of context */
  /* line minus-one of context */
  printf ("Good-bye, cruel world!\n");
  /* line plus-one of context */
  /* line plus-two of context */
  /* line plus-three of context */
  /* line plus-four of context */
  /* line plus-five of context */
}

通常の文脈ベースの対処法を使うと、T:1->T:2 の変更に対する B:2 のパッチの適用は失敗します。純正の`patch'を使った場合にはリジェクトファイルができますし、`rcsmerge' を使った場合は衝突マーカーが書き込まれます:

$ cvs up -j 1.1 -j 1.2 foo.c
### Purists will note that -j HEAD would have been sufficient; however, ###
### two -j's more clearly reflects the intent of the example.           ###
RCS file: /usr/local/cvs/vap0/foo.c,v
retrieving revision 1.1
retrieving revision 1.2
Merging differences between 1.1 and 1.2 into foo.c
rcsmerge: warning: conflicts during merge
$ cat foo.c
int main (int argc, char **argv)
{
<<<<<<< foo.c
  /* line -5 of context */
  /* line -4 of context */
  /* line -3 of context */
  /* line -2 of context */
  /* line -1 of context */
  printf ("Hello, world!\n");
  /* line +1 of context */
  /* line +2 of context */
  /* line +3 of context */
  /* line +4 of context */
  /* line +5 of context */
=======
  /* line minus-five of context */
  /* line minus-four of context */
  /* line minus-three of context */
  /* line minus-two of context */
  /* line minus-one of context */
  printf ("Good-bye, cruel world!\n");
  /* line plus-one of context */
  /* line plus-two of context */
  /* line plus-three of context */
  /* line plus-four of context */
  /* line plus-five of context */
>>>>>>> 1.2
}

文脈は変更されたので、中間の行に対する変更は見つけることができません。もしパッチをT:1->T:2で調整すれば、このようになります:

*** foo.c	2001/05/18 08:15:28	1.1
--- foo.c	2001/05/18 08:20:59	1.2
***************
*** 5,11 ****
    /* line -3 of context */
    /* line -2 of context */
    /* line -1 of context */
!   printf ("Hello, world!\n");
    /* line +1 of context */
    /* line +2 of context */
    /* line +3 of context */
--- 5,11 ----
    /* line -3 of context */
    /* line -2 of context */
    /* line -1 of context */
!   printf ("Goodbye, cruel world!\n");
    /* line +1 of context */
    /* line +2 of context */
    /* line +3 of context */

これだと、B:2 に対して完璧に適用することができます。この diff はどの二つのコミットバージョン間でも存在しないにもかかわらず、です。

もう少しだけ複雑な場合を考えてみます。T:1 と B:1 は同じもので始めます:

int main (int argc, char **argv)
{
  /* line minus-five of context */
  /* line minus-four of context */
  /* line minus-three of context */
  /* line minus-two of context */
  /* line minus-one of context */
  printf ("Hello, world!\n");
  /* line plus-one of context */
  /* line plus-two of context */
  /* line plus-three of context */
  /* line plus-four of context */
  /* line plus-five of context */
}

T:2 はファイルの先頭の近くで何行か挿入されます:

#include <stdio.h>

int main (int argc, char **argv)
{
  /* line minus-five of context */
  /* line minus-four of context */
  /* line minus-three of context */
  /* line minus-two of context */
  /* line minus-one of context */
  printf ("Hello, world!\n");
  /* line plus-one of context */
  /* line plus-two of context */
  /* line plus-three of context */
  /* line plus-four of context */
  /* line plus-five of context */
}

それから別の変更がトランクでコミットされ、中間の行が編集されました。 T:3 はこんな感じになります:

#include <stdio.h>

int main (int argc, char **argv)
{
  /* line minus-five of context */
  /* line minus-four of context */
  /* line minus-three of context */
  /* line minus-two of context */
  /* line minus-one of context */
  printf ("Good-bye, cruel world!\n");
  /* line plus-one of context */
  /* line plus-two of context */
  /* line plus-three of context */
  /* line plus-four of context */
  /* line plus-five of context */
}

一方、一つの複雑な変更がブランチ上でコミットされ、そのため B:2 はこんな感じになります:

int main (int argc, char **argv)
{
  /* line minus-five of context */
  /* line minus-four of context */
  /* line minus-three of context */
  /* line -1 of context */
  printf ("Hello, world!\n");
  /* newly inserted line of context */
  /* line plus-one of context */
  /* line plus-two of context */
  /* line plus-three of context */
  /* line plus-four of context */
  /* line plus-five of context */
}

文脈の minus-two の行は削除され、minus-one の行は "-1" に変更され、文脈の新しい行がずっと下のほうで挿入されました。この状態でブランチ上の開発者が T:2-T:3 間の変更をマージしたいとします。調整されていないパッチは以下のような感じになります:

Index: foo.c
===================================================================
RCS file: /usr/local/cvs/vap1/foo.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -c -r1.2 -r1.3
*** foo.c	2001/05/22 21:17:14	1.2
--- foo.c	2001/05/22 21:19:42	1.3
***************
*** 7,13 ****
    /* line minus-three of context */
    /* line minus-two of context */
    /* line minus-one of context */
!   printf ("Hello, world!\n");
    /* line plus-one of context */
    /* line plus-two of context */
    /* line plus-three of context */
--- 7,13 ----
    /* line minus-three of context */
    /* line minus-two of context */
    /* line minus-one of context */
!   printf ("Good-bye, cruel world!\n");
    /* line plus-one of context */
    /* line plus-two of context */
    /* line plus-three of context */

調整アルゴリズムの後では、以下のようになります:

Index: foo.c
===================================================================
RCS file: /usr/local/cvs/vap1/foo.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -c -r1.2 -r1.3
*** foo.c	2001/05/22 21:17:14	1.2
--- foo.c	2001/05/22 21:19:42	1.3
***************
*** 5,11 ****
    /* line minus-four of context */
    /* line minus-three of context */
    /* line -1 of context */
!   printf ("Hello, world!\n");
    /* newly inserted line of context */
    /* line plus-one of context */
    /* line plus-two of context */
--- 5,11 ----
    /* line minus-four of context */
    /* line minus-three of context */
    /* line -1 of context */
!   printf ("Good-bye, cruel world!\n");
    /* newly inserted line of context */
    /* line plus-one of context */
    /* line plus-two of context */

T:1-T:2 間の変更の不在(なぜなら、適用しているパッチは T:2-T:3 間のことしか考慮していないからです)を補償するためにどのようにして行番号が調整されたか、またその文脈が B:1-B:2 間の差分を取り込むためにどのように変更されたか、に注意してください。

ここでも、このパッチはどの二つのリビジョン間でも存在していないにもかかわらず、B:2 にたいしてきれいに適用することができます。

調整アルゴリズムのコストは、分岐地点からトランクのヘッドまでの diff の大きさと、分岐地点からブランチのヘッドまでの diff、そして、適用される diff にあるサイズの合計に比例します。これは、最初から逆-差分の保存を使う場合のコストと比較することができます -- 必要なものは、それぞれの終端に対する diff 、二つのラインの共通の祖先、パッチが適用されるリビジョン、これらに対するアクセス許可のみです。中間のリビジョンにユーザがアクセスする必要はありません。

変動調整法にるパッチを使えば、引き続くリビジョンを保存しているリポジトリはどれも、大きくかけ離れてしまったブランチ間であっても、それらが共通の先祖を持つ限り、パッチを適用することができます。