15

それらがどのように機能するかに関して、私は低レベルの作業について疑問に思っていました:

  1. マージの競合を引き起こすのは何ですか?
  2. コンテキストは、パッチを適用するためにツールでも使用されますか?
  3. 実際にはソース コードの動作を変更しない変更にどのように対処するのでしょうか? たとえば、関数定義の場所を交換します。

安全性に関しては、正直なところ、巨大な Linux カーネル リポジトリが安全性の証です。ただ、以下の点が気になります。

  1. ユーザーが知っておくべきツールに関する警告/制限はありますか?
  2. アルゴリズムが間違った結果を生成しないことが証明されていますか?
  3. そうでない場合、少なくとも経験的にエラーがないことを証明する統合テストを提案する実装​​/論文はありますか? これらの論文BrianKorverとJamesCplienの内容のようなもの。
  4. 繰り返しますが、前の点に関しては Linux リポジトリで十分ですが、もっと一般的なものについて疑問に思っていました。ソース コードは、変更されても (特に実装されているアルゴリズムと構文の制限により) あまり変更されませんが、安全性を一般的なテキスト ファイルに一般化できますか?

編集

わかりました、質問があいまいで、回答が詳細に対応していないため、編集しています。

Git/差分/パッチの詳細

Git がデフォルトで使用しているように見える統合 diff 形式は、基本的に 3 つのものを出力します: 変更、変更を取り巻くコンテキスト、およびコンテキストに関連する行番号です。これらのそれぞれが同時に変更されている場合とされていない場合があるため、Git は基本的に 8 つの可能性のあるケースに対処する必要があります。

たとえば、コンテキストの前に行が追加または削除された場合、行番号は異なります。ただし、コンテキストと変更が同じままである場合、diff はコンテキスト自体を使用してテキストを整列させ、パッチを適用できます (これが実際に発生するかどうかはわかりません)。さて、他のケースではどうなるでしょうか？Git が変更を自動的に適用することを決定する方法と、エラーを発行してユーザーに競合を解決させることを決定する時期の詳細を知りたいです。

信頼性

Git にはコミットの完全な履歴があり、履歴をトラバースできるため、Git は完全に信頼できると確信しています。私が望むのは、学術研究へのいくつかの指針と、これに関する参考文献が存在する場合です。

この主題に少し関連していますが、Git/diff はファイルを一般的なテキスト ファイルとして扱い、行で動作することを知っています。さらに、diff で採用されている LCS アルゴリズムは、変更の数を最小限に抑えようとするパッチを生成します。

そこで、私も知りたいことがいくつかあります。

  1. 他の文字列メトリック アルゴリズムの代わりに LCS が使用されるのはなぜですか?
  2. LCS が使用されている場合、基礎となる言語の文法的側面を考慮したメトリックの修正版を使用しないのはなぜですか?
  3. 文法的な側面を考慮したそのような測定基準が使用される場合、それらは利益をもたらすでしょうか? この場合の利点は、たとえば、よりクリーンな「責任ログ」など、何でもかまいません。

繰り返しになりますが、これらは巨大なトピックになる可能性があり、学術論文は大歓迎です。

4

3 に答える 3

6

マージの競合を引き起こすのは何ですか?

最初に、git の最も単純なマージ戦略であるrecursiveを見てみましょう:共通の祖先cを持つaとbなどの2 つのブランチをマージする場合、git はコミットcからコミット ad a の先頭に移動するパッチを作成し、試行します。そのパッチをbの先頭にあるツリーに適用します。パッチが失敗した場合、それはマージの競合です。

git はデフォルトで、再帰戦略である3-way mergeを使用します。一般的な考え方は同じです。異なるブランチからの 2 つのコミットが同じ行を変更したために、リンクに記載されている 3 方向マージ アルゴリズムが失敗した場合、それはマージの競合です。

コンテキストは、パッチを適用するためにツールでも使用されますか?

はい。差分ファイルに保存されている正確な行番号にパッチが適用されない場合、パッチはコンテキストに基づいて、元の行から数行隣接した正しい行を見つけようとします。

実際にはソース コードの動作を変更しない変更にどのように対処するのでしょうか? たとえば、関数定義の場所を交換します。

パッチはインテリジェントではなく、そのような変更を区別できません。移動された関数は、追加された 2 行と削除された 2 行と見なされます。あるブランチでのコミットが関数を変更し、別のブランチでのコミットが変更されていないものを移動する場合、マージを試みると常にマージの競合が発生します。

ユーザーが知っておくべきツールに関する警告/制限はありますか?

patch と diff について: いいえ。どちらも 1970 年代初頭から存在し、非常に堅牢なアルゴリズムを使用しています。彼らが文句を言わない限り、彼らがあなたの意図したことをしたとかなり確信で​​きます。

つまり、git mergeマージの競合を独自に解決しようとします。まれに、ここで問題が発生することがあります。このページには、最後に近い例があります。

アルゴリズムが間違った結果を生成しないことが証明されていますか? そうでない場合、少なくとも経験的にエラーがないことを証明する統合テストを提案する実装​​/論文はありますか?

「間違った結果」は、この文脈ではかなり曖昧な用語です。証明できないと断言します。経験的に証明されているのは、diff a bto fileによって生成されたパッチを適用するaと、いずれにしてもfile が生成されるということですb。

ソース コードは、変更されても (特に実装されているアルゴリズムと構文の制限により) あまり変更されませんが、安全性を一般的なテキスト ファイルに一般化できますか?

繰り返しますが、diff/patch/git はソース コードと他のテキスト ファイルを区別しません。git は、ソース コードと同様に一般的なテキスト ファイルでも機能します。

Git にはコミットの完全な履歴があり、履歴をトラバースできるため、Git は完全に信頼できると確信しています。私が望むのは、学術研究へのいくつかの指針と、これに関する参考文献が存在する場合です。

git でのコミットは、隣接するバージョンとの差分ではなく、メタ データを含むツリーのスナップショットです。patch と diff は、リビジョン トラバーサルにはまったく関与しません。(しかし、表面の 1 レベル下で、git は、デルタ圧縮アルゴリズムを使用するパック ファイルにブロブを編成します。git は内部で sha1 合計を使用してファイルを識別し、エラーが発生すると合計が変化するため、ここでのエラーは簡単に見つけることができます。 )

他の文字列メトリック アルゴリズムの代わりに LCS が使用されるのはなぜですか?

git はデフォルトで Myers のアルゴリズムを使用します。元の論文では、なぜそのように機能するのかを説明しています。(純粋な LCS ではありません。)

于 2015-11-09T18:14:46.990 に答える
4

diff/patch 形式は安全ではありません。=) 彼らはあなたの情報源について何も知らないからです。

(OMG) 2008年に描いたフォーマットの説明です。 統一された差分形式

  1. ソース チャンク内の行が実際のソース ファイルで異なるか変更されている場合、マージの競合がトリガーされます。ソース チャンクは、「+」で始まらない黄色の線で構成されます。赤い色は、パッチ プログラムがパッチを適用する前にこのソース チャンクを見つけると予想する行番号の輪郭を示しています。これらの行が履歴のどこかで既に変更されている場合、マージの競合が発生します。

  2. はい、コンテキスト行は、パッチが正しく適用されているかどうかを確認するために使用されます。また、これらの行の前に何かが挿入されているために行番号情報 (赤) が正しくない場合に、正しい場所を見つけるためにも使用されます。

  3. patch ユーティリティは、コードの動作について何も知りません。行を挿入して削除するだけで、予期される行が見つからない場合 (失敗したり、オフセットを見つけようとしたりすることもあります)、またはそれらが既に変更されている場合 (マージの競合) に警告が表示されます。

この説明が 2 番目の質問のブロックに役立つことを願っています。

何ができるかというと、私は Extensible Changeset Format を思いついたことがあります。これにより、diff 形式がよりインテリジェントなパッチ ツール用の追加データを保持できるようになりました。2011 年に Subversion メーリング リストにアイデアを送信しましたが、当時は非常に熱狂的でした。

Google Code でアイデアを文書化しましたが、閉鎖されたため、現在は (履歴なしで) GitHub に埋め込まれています: https://github.com/techtonik/rainforce/blob/wiki/ExtensibleChangesetFormat.md

その恩恵を受けることができる実際のプロジェクトがなかったため、どこにも行きませんでした。実際には、ファイルとディレクトリを認識するパッチ形式の拡張バージョン (または代替と言うほうがよい) を作成しました。2008 年に Wesnoth のインクリメンタル アップデートをビルドするために使用されましたhttp://forums.wesnoth.org/viewtopic.php?f=5&t=20132が、貪欲すぎてオープン ソースにリリースできませんでした (または、公開しないことを恐れていました)。ツールを適切にサポートすることができれば、大金を稼ぐ営利企業によってフォークされるでしょう)。パス形式の拡張/代替バージョンは次のようになります。

[PatchPlan version 0.1]------------------------------------
* Description   : 
* Old Version   :
* New Version   :
* URL       :
* Patch made by : 
* Comments  :
* Used tools    :
-----------------------------------------------------------
[C ] ... "dir1/dir2/filename.ext" MD5
         N:"dir3/dir4/newfile.ext" MD5
[C ] ... "dir1/dir3/filename.ext" MD5
         P:"dir1/dir3/patchfile.ext.patch" TYPE MD5
[D ] ... "dir1/dir2/filename.ext" MD5
[A ] ... "dir1/dir2/filename.ext"
         N:"dir3/dir4/newfile.ext" MD5
[AD] ... "dir1/dir2/newdirname"
-----------------------------------------------------------

[C ] ... - Status field

         C  - Changed
         D  - Deleted
         A  - Added
         DE - Deleted empty directory
         DD - Deleted directory
         AD - Added directory
         ... - place reserved for flags like overwrite,
               force deletion etc. flags are separated by
               spaces from other fields




"dir1/dir2/filename.ext" - relative path of patched file


MD5    - 32 letters, i.e. cb5bc9f48388568178f24e6294ea782b


N:"dir3/dir4/newfile.ext" MD5
       - path for replacement file relative to directory
         with new files, i.e. temp directory where they
         were extracted, for example

P:"dir3/dir4/patchfile.ext.patch" TYPE MD5
       - path for patch file that should be applied
         TYPE is one of the supported 
         - VPATCH (DIFF, BSDIFF are planned)
       - .patch extensions is not a requirement, but
         merely a convention
       - MD5 in this case is MD5 of the new patched file
         and not of the patch itself


[D ] ... - MD5 of the file to be deleted

それを考えると、ディレクトリを比較してパッチを当てたり、バイナリ パッチやテキスト パッチを作成したりするためのツールを自分で派生させることができます。詳細な情報を掲載する場所はまだありません。もちろん、私はそのようなツールのフルタイムの開発に参加することに興味があります (または、自分のツールをオープンソース化します)。

今日は、リポジトリに関する知識、パッチが適用される前に失敗するはずのテスト、レビュー担当者に役立つ追加情報 (レビューに必要な資格やコード レベルの検出など)、およびその他の多くのアイデアを追加します。パッチシリーズから、パッチがソースコードツリー全体の他の変更と直交しているかどうかを検出するマルチレベルツール。しかし、これには資金と複数の軍隊が必要です。

于 2015-11-09T19:45:07.997 に答える
2
  1. マージの競合を引き起こすのは何ですか?

両方のブランチが開始された元のバージョンを見つけます。元のバージョンに対して 2 つの diff を実行します。1 つは左側のブランチ チップ バージョン、もう 1 つは右側です。重複する変更ハンクで 2 つの変更が異なる場合は、競合が発生し、git は自動解決を拒否します。それでおしまい。

  1. コンテキストは、パッチを適用するためにツールでも使用されますか?

Merge はそれを必要としません。両方の差分があり、元の各行が各ヒントのどこで終わったかを示しています。変更された行を取得して配置する場所を正確に認識しています。

  1. 実際にはソース コードの動作を変更しない変更にどのように対処するのでしょうか? たとえば、関数定義の場所を交換します。

彼らはしません。どのセマンティクスがどこに適用されるかを git に教えようとすることを考えてみてください。あなたが恐怖で精神的に叫んでいないなら、あなたはそれをしていません:-)

独自のマージ ドライバを指定できます。それは簡単です。自動的に処理したい一般的な特殊なケースがある場合は、それを実行してください。ビルトインドライバーを呼び出す単純なシェルスクリプトから始めて、次にseds またはawks または自動的に正しく処理できる競合のために何でもします。

Git にはコミットの完全な履歴があり、履歴をトラバースできるため、Git は完全に信頼できると確信しています。私が望むのは、学術研究へのいくつかの指針と、これに関する参考文献が存在する場合です。

Git の内部構造は信じられないほどシンプルです。冗談じゃないよ。モデルの信頼性は検査によって確認できます。木の枝の構造とマージの動作を念頭に置き、その信頼性に関する具体的な懸念や疑問を見つけてみてください。形成しようとするのと同じくらい早く解決できると思います。

代わりに、実装された操作の信頼性について質問している場合、それが圧縮を正しく行うか、プッシュやフェッチなどを満たすために適切なオブジェクトを送信するかどうか、それは「gitにはバグがありますか?」と綴られています.

于 2015-11-10T19:25:42.803 に答える