Gitコミットグラフには、コミットOIDのリストと、以下のような関連するメタデータが格納されます:

  • コミットの世代番号。

  • ルートツリーOID。

  • コミット日付。

  • グラフファイル内の位置参照を使用して保存されたコミットの親。

  • 要求された場合、コミットとその最初の親の間で変更されたパスを伝えるコミットのブルームフィルター

これらの位置参照は、コミット OID のリスト内の配列位置に対応する符号なし 32 ビット整数として格納されます。 親を追跡するために使用するいくつかの特別な定数により、最大で (1 << 30) + (1 << 29) + (1 << 28) - 1 (約 18 億) のコミットを格納できます。

Commit graph files have the following format:

グラフに余分なデータを追加する拡張を可能にするために、ボディを「チャンク」に編成し、ぼでぃの先頭にバイナリ ルックアップ テーブルを提供します。 ヘッダーには、チャンク数やハッシュ タイプなどの特定の値が含まれます。

すべての複数バイト数値はネットワークバイトオーダーです。

HEADER

  • 4バイト シグネチャ:

    シグネチャは: {C, G, P, H}

  • 1バイト バージョン番号:

    現在、有効なバージョンは 1 のみです。

  • 1バイト ハッシュバージョン

    以下の値からハッシュ長(H)を推測します:

    1 => SHA-1
2 => SHA-256

    ハッシュタイプがリポジトリのハッシュアルゴリズムと一致しない場合、コミットグラフファイルは無視され、ユーザーに警告が表示されます。

  • 1バイト チャンクの数©

  • 1バイト ベースコミットグラフの数(B)

    この値からベースグラフチャンクの長さ(H*B)を推測します。

CHUNK LOOKUP

  • (C + 1) * 12 バイト チャンクの目次をリストします:

    最初の 4 バイトはチャンク ID を表します。 値 0 は終了ラベルです。 他の 8 バイトは、チャンクが始まる現在のファイル内バイトオフセットを提供します。 (チャンクはファイル内で連続して並べられているため、必要に応じて次のチャンク位置を使用して長さを推測できます。) 各チャンク ID は最大 1 回しか表れせん。

CHUNK LOOKUP は、 the chunk-based file format の目次(the table of contents)と一致します。

ボディ内の残りのデータは一度に 1 つのチャンクで記述され、これらのチャンクは任意の順序で指定できます。 チャンクは特に指定がない限り必須です。

CHUNK DATA

  • OID Fanout (ID: {O, I, D, F}) (256 * 4 バイト)

    i 番目のエントリ F[i] には、最初のバイトが最大で i 個の OID の数が格納されます。 したがって、F[255] にはコミットの総数 (N) が格納されます。

  • OID Lookup (ID: {O, I, D, L}) (N * H バイト)

    昇順でソートされた、グラフ内のすべてのコミットの OID。

  • コミットデータ (ID: {C, D, A, T }) (N * (H + 16) バイト)

    • 最初の H バイトは、ルートツリーの OID 用です。

    • 次の 8 バイトは、i 番目のコミットの最初の 2 つの親の位置用です。 その位置に親がいない場合は、値 0x70000000 を格納します。 親が 3 つ以上ある場合、2 番目の値の最上位ビットがオンになり、他のビットは配列位置を Extra Edge List チャンクに格納します。

    • その次の 8 バイトには、コミットのトポロジレベル(世代番号 v1)とエポックからのコミット時間(秒単位)が格納されます。 世代番号は最初の 4 バイトの上位 30 ビットを使用し、コミット時間はその次の 4 バイトの 32 ビットと最下位バイトの下位 2 ビットを使用して、コミット時間の 33 番目と 34 番目のビットを格納します。

  • 世代データ (ID: {G, D, A, T }) (N * 4 bytes) [オプション]

    • この 4 バイト値のリストには、コミットデータチャンクと同じ順序で配置された、コミットの修正されたコミット日付オフセットが格納されます。

    • 修正されたコミット日付オフセットが 31 ビット以内に格納できない場合、値の最上位ビットがオンになり、他のビットは修正されたコミット日付の位置をジェネレーション データ オーバーフロー チャンク(Generation Data Overflow chunk)に格納します。

    • ジェネレーション データ チャンクは、互換性のあるバージョンの Git によってコミット グラフ ファイルが書き込まれた場合にのみ存在し、分割されたコミット グラフ チェーンの場合、最上層にもジェネレーション データ チャンクがあります。

  • Generation Data Overflow (ID: {G, D, O, V }) [Optional]

    • この 8 バイト値のリストには、31 ビット内に格納できない修正されたコミット日付オフセットを持つコミットの修正されたコミット日付オフセットが格納されます。

    • ジェネレーション データ オーバーフロー チャンクは、ジェネレーション データ チャンクが存在し、少なくとも 1 つ以上修正されたコミット日付オフセットが 31 ビット内に格納できない場合にのみ存在します。

  • Extra Edge List (ID: {E, D, G, E}) [Optional]

    この 4 バイト値のリストには、すべてのオクトパス マージの 2 番目から n 番目の親が格納されます。 コミット データの 2 番目の親の値は、このリスト内の配列位置を最上位ビットをオンにして格納します。 その配列位置から開始して、最上位ビットがオンの値に到達するまで、親のコミット位置のこのリストを繰り返します。 他のビットは、最後の親の位置に対応します。

  • Bloom Filter Index (ID: {B, I, D, X}) (N * 4 bytes) [Optional]

    • i 番目のエントリ BIDX[i] には、コミット 0 からコミット i までのすべてのブルームフィルターのバイト数が、辞書順で格納されます。 i 番目のコミットのブルーム フィルターは、BIDX[i-1] から BIDX[i] (およびヘッダー長) に及びます。ここで、BIDX[-1] は 0 です。

    • BDAT チャンクが存在しない場合、BIDX チャンクは無視されます。

  • Bloom Filter Data (ID: {B, D, A, T}) [Optional]

    • 3 つの符号なし 32 ビット整数で構成されるヘッダーで始まります:

      • 使用されているハッシュ アルゴリズムのバージョン。 現在、 https://en.wikipedia.org/wiki/MurmurHash#Algorithm で説明されているとおりに実装された murmur3 ハッシュの 32 ビット バージョンに対応する値 1 と、シード値 0x293ae76f および 0x7e646e2 を使用した二重ハッシュ技術のみをサポートしています。 https://doi.org/10.1007/978-3-540-30494-4_26「Bloom Filters in Probabilistic Verification」(確率論的検証におけるブルームフィルター)に記載

      • パスがハッシュされる回数、つまりファイルがコミットに存在するかどうかを累積的に決定するビット位置の数。

      • ブルーム フィルターのエントリあたりのビット「b」の最小数。 フィルタに「n」個のエントリが含まれる場合、フィルタ サイズは、n*b ビットを含む 64 ビット ワードの最小数です。

    • チャンクの残りの部分は、コミットに対して計算されたすべてのブルーム フィルターを辞書順で連結したものです。

    • 注意: 変更がないコミット、または 512 を超える変更があるコミットには、長さ 1 のブルーム フィルターがあり、すべてのビットがそれぞれ 0 または 1 に設定されます。

    • BDAT チャンクは、BIDX が存在する場合にのみ存在します。

  • Base Graphs List (ID: {B, A, S, E}) [Optional]

    この H バイト ハッシュのリストは、コミット グラフ チェーンを形成する一連の B コミット グラフ ファイルを記述します。 このファイルの OID ルックアップ チャンクの i 番目のコミットのグラフ位置は、i にすべてのベース グラフのコミット数を加えた値に等しくなります。 B がゼロでない場合、このチャンクが存在する必要があります。

TRAILER

  • 上記すべての H バイト ハッシュ チェックサム。