'git log --graph'または 'hg graphlog'はどのように動作しますか？

Question

私はGitの履歴がDAGというデータ構造に格納されていることを知っています。私はDFSについて聞いたことがあり、それは多少関連していることを知っています。

私は好奇心が強いです。git log --graphやhg graphlogなどのプログラムはどのようにして歴史を描きますか？私はいつも車線やそのすべてを素敵なやり方で描くことはかなり複雑だと思っていました。

誰かがそれを実証する疑似コードを書くことができますか？

注：私はGitまたはhgのコードを見てみましたが、何が起こっているのかについての一般的な考えを追跡するのは非常に難しいです。

Answer 1

一般的なグラフ表示と比べて、この特定の問題はそれほど難しくありません。ノードをコミットした順番に保ちたいので、問題はずっと簡単になります。

また、ディスプレイモデルはグリッドベースで、行はコミットされ、列は過去/未来のエッジです。

私はgitソースを読んでいませんでしたが、おそらく最新のものからコミットのリストを歩いて、開いているエッジのリストを過去のものに保ちます。エッジの後には自然にカラムの分割/マージが行われ、git/hgツリーの種類の表示になります。

エッジをマージするときは、他のエッジとの交差を避けたいので、事前に列を並べ替える必要があります。これは実際には単純ではないかもしれない唯一の部分です。例えば、第1パスのエッジの列順序を構成し、第2パスの描画を行う2パスアルゴリズムを行うことができる。

Answer 2

私はGitまたはhgのコードを見てみましたが、何が起こっているのかについての一般的な考え方を理解するのは非常に難しいです。

hgの場合、hg自体のコードまたはグラフログのコードに従ってみましたか？

graphlogのコードがかなり短いためです。あなたはhgext/graphlog.pyで見つけることができます。そして本当に重要な部分はトップ200行です。残りは、拡張機能のブートストラップと選択されたリビジョングラフの検索です。コード生成関数は、最後のパラメータは、asciiedgeの呼び出し（コール自体はgraphlogによってgenerateに提供される機能、generateの最後の行で実行される）

Answer 3

まず、一つはA取得の結果であると、asciiありますコミットのリスト（git rev-listのように）、および各コミットの親。 「列予約リスト」はメモリ内に保持される。それぞれについて、

は、コミット：

• コミットがそれのために予約なしの列を持っていない場合は、無料の列に割り当てます。これがブランチヘッドの開始方法です。
• 列の予約リストに従ってコミットメッセージを印刷します。
• 現在のコミットの予約のリストエントリは、現在のコミットの最初の親で更新されます。同じ列に印刷する。
• 他の親は新しい空き列を取得します。の出力を示す
• これは、マージした場合は、次の行が期待されているコミットの列に2つ目の親をリンクしようとしますが（これはループと「≡ブリッジ」になり）

例aufs2-utilにgit-forestを追加すると、複数のブランチを持つことになります）。先読みして

、一つはマージポイントダウンし、より美的結果を与えることと2つの列の間の木材を絞るだろうどこまで予想することができます。