39

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

気になるのですが、git log --graphやなどのプログラムはどのようhg graphlogに歴史を描いているのでしょうか? レーンやすべてを素敵な方法で描くのはかなり複雑だといつも思っていました。

誰かがそれを示す擬似コードを書くことができますか?

注: Git または hg のコードを調べてみましたが、何が起こっているのかを理解して理解するのは非常に困難です。

4

4 に答える 4

7

最初に、( と同様にgit rev-list) コミットのリストと、各コミットの親を取得します。「列予約リスト」がメモリに保持されます。

コミットごとに次のようにします。

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

git-forest複数のブランチを持つ追加のコミットを含む aufs2-utilの出力を示す例)。

例

先読みを使用すると、マージ ポイントがどれだけ下にあるかを予測し、2 つの柱の間で木を絞ることで、より美的に満足できる結果を得ることができます。

于 2011-02-15T14:45:58.380 に答える
5

Git や hg のコードを調べてみましたが、何が起こっているのかを理解して把握するのは非常に困難です。

hg については、hg 自体またはグラフログのコードをたどろうとしましたか?

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

于 2011-02-15T12:22:48.413 に答える
4

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

また、表示モデルはグリッド ベースであり、行はコミット、列は過去/未来へのエッジであることにも注意してください。

私は git ソースを読んでいませんでしたが、おそらく最新のものから始めてコミットのリストをたどり、過去に開いたエッジのリストを維持しているだけでしょう。エッジをたどると、自然に列の分割/マージが行われ、一種のツリー git/hg 表示になります。

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

于 2011-01-19T20:48:42.143 に答える