私はGitXの作者です。GitX の機能の 1 つは、ここで見られるように、ブランチの視覚化です。
この視覚化は現在、git から発行されたコミットを正しい順序で読み取ることによって行われています。コミットごとに親がわかっているため、正しい方法でレーンを構築するのはかなり簡単です。
独自のコミット プールを使用し、コミットを自分で線形化することで、このプロセスをスピードアップしたいと考えています。これにより、既存のロードされたコミットを再利用でき、正しい順序でコミットを発行する必要がないため、git がコミットをより速く発行できるようになります。
ただし、これを達成するためにどのアルゴリズムを使用すればよいかわかりません。コミットのロードには長い時間がかかる可能性があるため (100,000 件のコミットで 5 秒以上、すべて表示される必要があります)、ビルドがインクリメンタルであることが重要です。
Gitk も同じように進んでおり、実装方法を示すパッチがここにありますが、私の TCL スキルは弱く、パッチは十分にコメントされておらず、理解するのが少し難しくなっています。
また、何十万ものコミットを処理する必要があるため、このアルゴリズムが効率的であることも望んでいます。また、表に表示する必要があるため、特定の行へのアクセスが高速であることが重要です。
これまでの入力、必要な出力、およびいくつかの観察事項について説明します。
入力：
- コミット ID をコミット オブジェクトにマップするハッシュ テーブルの形式で、コミットの現在のプールがあります。このプールは完全である必要はありません (すべてのコミットが必要です)
- 新しいコミットがロードされるたびに呼び出すことができるコールバックを使用して、git からの新しいコミットで別のスレッドをロードしています。コミットが行われる順序は保証されていませんが、ほとんどの場合、次のコミットは前のコミットの親になります。
- commit オブジェクトには、独自のリビジョン ID とそのすべての親のリビジョン ID があります
- リストする必要がある支部長のリストがあります。つまり、表示されるべき DAG の単一の「トップ」はありません。また、単一のグラフ ルートである必要もありません。
出力：
- これらのコミットをトポロジー順に線形化する必要があります。つまり、親がリストされた後にコミットをリストすることはできません。
- 上のスクリーンショットに見られる「分岐線」も必要です。それらのほとんどは子に依存しているため、これらはおそらく事前に計算する必要があります。
いくつかの注意事項:
- コミットのリストを再配置する必要があります。たとえば、一方のヘッドを他方の先祖にするコミットが現れるまで、関連のないコミット (ブランチ ヘッド) が必要になる場合があります。
- 複数のブランチ ヒントを表示する必要があります
- データがまだロードされている間、少なくとも部分的なビューを利用できるように、このプロセスは増分的であることが重要です。これは、新しいデータを途中で挿入する必要があり、支線を再調整する必要があることを意味します。