Git の内部構造を勉強したので、理解をスナップショットしておきます。 Git の内部構造はシンプルに整理されているため、それぞれの概念に型をつけると理解しやすいように感じ、最近勉強している F# で整理していたらいい感じになったので、F# のコードを示しながら Git のモデルを説明してみようと思います。 一般的な ML を読めればコードは読めると思いますが、F# に特有の事情がある部分はよしなに補足します。 実際のコードはここにあります:https://github.com/atree4728/gitmodel
F# に習熟しているわけではないので、よりよい書き方・設計などあればぜひ教えていただきたいです。
Git の管理対象
プロジェクトの履歴を保存したり、ブランチを切り替えたりするために Git が管理するのは次の二つです。
- Git オブジェクト
.git/objectsに保存されています。- 主に履歴の保存に関係します。
- Git リファレンス
.git/refsに保存されています。- 主にブランチに関係しています。
Git オブジェクト
先に Git オブジェクトについて説明します。
Git オブジェクトには Blob・Tree・Commit・Tag の 4 つのタイプがあります1。
1: ML に親しみがない場合わかりにくいですが、ここで of の左側の識別子は型コンストラクタで、右側の識別子は型です。
type Object =
| Blob of Blob
| Tree of Tree
| Commit of Commit
| Tag of AnnotatedTagBlob Tree Commit AnnotatedTag 型はこのあと定義します。
Blob; Binary Large Object はファイルに対応し、Tree はディレクトリに対応する概念です。
Commit はその名の通りで、Tag は 注釈付きのタグ(annotated tag) に対応します。
Git で利用できるタグは二種類存在し、注釈付きでないタグは 軽量タグ(lightweight tag) と呼ばれます。
特別なオプションなしで git tag した場合に生成されるのは軽量タグであるのに対し、注釈付きのタグを作成するには -a オプションを必要とし、commit 時と同様にタグをつけたユーザーや日時、メッセージといった情報を含みます。
軽量タグについては後に補足しますが、重要な違いとして、Git オブジェクトとして管理されるのは注釈付きのタグのみであるということがあります。
したがって、Object.Tag の引数が AnnotatedTag のみであることに注意してください。
ストアとオブジェクト ID
それぞれの Git オブジェクトに対して、その内容を表現するための文字列フォーマットが規定されています。
この文字列に対する一般的な名称は存在しないようですが、ここでは git Book に合わせて2 ストア(store) と呼ぶことにします。
これからそれぞれのオブジェクトをレコードとして記述しますが、ストアはそのレコードの内容だけで生成されることを覚えておいてください。
2: 10.2 の最後の Ruby コードで、この文字列に store という変数名を用いていて、これに従いました。
また、すべての Git オブジェクトは固有の ID を持っています。 これはストアの SHA-1 ハッシュであり、オブジェクトの内容が同じなら ID も同じになります。 SHA-1 は長さ 40 のバイト列なので、通常 ID は 40 桁の 16 進文字列として扱われます。
type Id<'T> = Id of byte array型パラメータ
'Tについて
'Tは ID がどのタイプのオブジェクトから生成されたのかを表現する型パラメータです。 元がどのオブジェクトであったとしても ID は無作為な文字列に見えるので、実際には'Tの情報は ID には含まれません(よって、Idのメンバにはこの情報を持たせていません)。 しかし、後に ID を元のタイプで制約したい場面が登場するので、そのような制約を F# のレベルで表現するためのタグとして型パラメータを持つようにしています。
Git オブジェクトはどのように保管されるのでしょう?
Git は ID を 2 文字目で区切り、先頭の 2 文字分に対応したサブディレクトリの下に、残りの 38 文字をファイル名としたバイナリを配置します。
ファイルの中身は、ストアを Zlib で圧縮したバイナリになっています。
例えば ID が e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 であるオブジェクトのストアは、Zlib で圧縮され .git/objects/e6/9de29bb2d1d6434b8b29ae775ad8c2e48c5391 に配置されています。
Git はそれぞれのオブジェクトを ID で識別し、必要に応じて .git/objects/ にアクセスし、バイナリを解凍することでオブジェクトの中身を参照できます。
つまり、Git はオブジェクトを key-value 型のテーブルのように扱うのです。
type ObjectId =
| BlobId of Id<Blob>
| TreeId of Id<Tree>
| CommitId of Id<Commit>
| TagId of Id<Tag>
let generateId object = // Object -> ObjectId
....
let mutable objects = Map<ObjectId, Object> []
ObjectIdについてここでは
ObjectIdを判別共用体として定義しましたが、気持ちとしてはObjectId = Id<(Blob | Tree | Commit | Tag)>です。 コンストラクタのない無名判別共用体を現行の F# で記述することはできない3ため、このようなワークアラウンドが用いられています。 3: 提案はされているようです。早く採用されてほしい。。。
Blob オブジェクト
先述の通り Blob オブジェクトはファイルに対応しますが、通常のファイルシステムにおけるファイルと全く同様というわけではありません。
重要な違いとして、Blob を構成する情報には自身のファイル名は含まれません。
Blob オブジェクトが保持するのはそれ自身の内容のみです。
これはメンバに content: string をもつレコードだと思うことができます。
type Blob = { content: string }Tree オブジェクト
Tree オブジェクトはディレクトリに対応し、そのディレクトリの子への辺を保持します。 ここでは、子への辺を エントリ(entry) と呼ぶことにします4。 4: 子自体にもエントリという名前をふわっと使います。
type Tree = { children: Entry array }子はディレクトリ、実行可能なバイナリ、通常のテキストファイル、シンボリックリンク、サブモジュールのいずれかです。
type EntryKind =
| Directory
| Executable
| TextFile
| Symlink
| SubModuleエントリは具体的には次の情報の組になっています:
- 子の種類(
EntryKind) - 子の名前
- 子の ID
type EntryId =
| BlobId of Id<Blob>
| TreeId of Id<Tree>
type Entry =
{ kind: EntryKind
name: string
id: EntryId }Blob オブジェクトと Tree オブジェクトを理解した現時点で、Commit オブジェクトの前にいくつかの注意点を Remark しておきます。
Blob オブジェクトと Tree オブジェクトのなす根付き木によって、ワーキングディレクトリ5はそのまま表現できています。 また、この木は親が子のリストを保持することで表現されることに注意してください。 履歴は Commit オブジェクトによって表現されるので、最初に commit した時点では Git オブジェクト群が表現するものは Blob オブジェクトと Tree オブジェクトによる単なる根付き木になっています。 5: Git の管理対象となるディレクトリ及びその子孫のこと。また、その根をリポジトリルートと呼ぶ。
Blob オブジェクトと Tree オブジェクトは git add git commit などによって、対応するファイル・ディレクトリが Git に管理されるようになった瞬間に作成され、.git/objects/ に保存されます。
重要なこととして、一度作成されたオブジェクトは、ファイル・ディレクトリが編集されたり削除されても削除されません6。
また、Blob オブジェクトと Tree オブジェクトの構成からわかる通り、Git はワーキングディレクトリをそのままスナップショットしており、差分を保存しているわけではありません6。
6: 実はこれは嘘で、プロジェクトが大きくなってきたり、git gc によりガベージコレクトしたりすると、Git は複数のオブジェクトをまとめて差分を計算し、packfile という形式で保存します。詳しくは git Bookを参照してください。
Commit オブジェクト
Commit オブジェクトはその名の通り一つの commit に対応し、commit 時に作成されます。 普通 commit を識別するために利用されている長さ 7 の文字列は Commit オブジェクトの ID の prefix です。
Commit オブジェクトの保持する情報のうち、本質的なのは 2 つです:
- commit 時点でのリポジトリルート(に対応する Tree オブジェクトの ID)
- commit の歴史を表現する DAG における親(に対応する Commit オブジェクトの ID)
- この DAG は
git mergeやgit rebaseの解説でよく見る DAG です。
- この DAG は
これらの他にも、パッチの作者や commit の作者に関する情報、commit メッセージが Commit オブジェクトに含まれます。
type Commit =
{ tree: Id<Tree>
parent: Id<Commit> array
authorInfo: User * TimeInfo
committerInfo: User * TimeInfo
message: string }User や TimeInfo は trivial ですが、気持ち悪いかもしれないので一応定義しておきます。
type TimeInfo =
{ unixTimestamp: uint
timezoneOffset: System.TimeSpan }
type User =
{ name: string
email: string }Commit オブジェクトはそれぞれリポジトリルートへの参照を持っています。 ということは、commit レベルの DAG のそれぞれの頂点がワーキングディレクトリを木として持っているのでしょうか? いいえ、そうではありません。 Blob・Tree オブジェクトの ID は、ワーキングディレクトリ上の部分木の情報により計算されることを思い出してください。 その頂点を根とした部分木が一致していれば ID は一致するため、Commit オブジェクト配下の頂点は自動的に共有され、変更の無かった部分のオブジェクトが新たに生成されることはありません。 したがって、Commit オブジェクト配下の構造は木ではなく、それぞれの木の頂点が部分的に共有された DAG になっています。
Tag オブジェクト
Tag オブジェクトは注釈付きタグに対応し、git tag -a 時に作成されます。
注釈の有無にかかわらず、タグは単なる Git オブジェクトへの参照 です。
Git オブジェクトとして扱われるのは注釈付きタグのみで、これには commit と同様に作成者やメッセージといった情報が含まれます。
type AnnotatedTag =
{ name: string
id: ObjectId
taggerInfo: User * TimeInfo
message: string }タグの参照先は commit とは限らない
commit に
v1.2のようなラベルをつけるのがタグの典型的な利用法ですが、id: ObjectIdとある通り、タグの参照先は commit だけではありません。 例えば、Git のソースコードリポジトリではメンテナが自分の GPG 公開鍵を Blob オブジェクトとして追加しタグ付けしているそうです。
Tag オブジェクトから伸びる辺は一本のみで、これは既に存在するオブジェクトに向かうため、Git オブジェクトが全体でなす構造は依然として DAG になっています。
ストアのフォーマット
ここまでで Git オブジェクトの構造は説明できています。
ここからは、ストアのフォーマットを理解することで実際に .git/objects/ がどうなっているかを確認していくことにします。
Zlib の解凍
初めに、ストアのフォーマットを自分の手で確認する方法を解説しておきます。 先述の通り、Git はオブジェクトの ID、つまりストアのハッシュを名前として、ストアを Zlib 圧縮して保存しています。 よって、ストアの中身を直接確認するにはオブジェクトを解凍するしかありません。 自分は Python スクリプトをコンソール上で実行して Zlib を解凍していました。
$ python3 -c "import zlib, sys; sys.stdout.buffer.write(zlib.decompress(sys.stdin.buffer.read()))" < .git/objects/XX/XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX出力には空白や制御文字が含まれますが、これを陽に確認したいです。
cat -v や bat --show-all に渡すだとか、一度ファイルに dump してからバイナリエディタで開くかするとこれを確認できます。
VS Code だと Microsoft が Hex Editor を公開していて、これは使いやすかったです。
ストアを生の文字列で確認しなくてもよい場合は、git cat-file (-t | -p) <ID> を用いることができます。
-t を指定するとオブジェクトのタイプ、-p を指定するとオブジェクトの内容を確認することができます。
header と content
すべてのストアは header と content の連結になっています。
オブジェクトのタイプによって content は別々のフォーマットになっていますが、header は共通のフォーマットになっています。
header はオブジェクトのタイプと content の長さを表現しています(ハイライト参照)。
content の定義を省略すると、store: Object -> string の定義は次のようになっています。
let store object =
let content =
match object with
| Blob blob -> ....
| Tree tree -> ....
| Commit commit -> ....
| Tag tag -> ....
let header =
let objectType =
match object with
| Blob _ -> "blob"
| Tree _ -> "tree"
| Commit _ -> "commit"
| Tag _ -> "tag"
$"{objectType} {content.Length}\x00"
header + content文字列の表現について
$が prefix されている文字列は Interpolated strings で、文字列内に{}で囲んだ識別子があるとその部分を適切に置換してくれます。 また、\x00は null 文字です。
それぞれのオブジェクトの content のフォーマットはどうなっているのでしょうか?
Blob オブジェクトのストア
Blob オブジェクトは最も単純で、content はファイルの内容と一致します。
// when `object` matches the pattern `Blob blob`.
let content = blob.content例えば、次のようにファイルを作成し、ステージしたとします。
$ git init test && cd test
$ echo "Hello, world!" > hello.txt
$ ls
.git hello.txt
$ git add hello.txtこのとき、hello.txt に対応する Blob オブジェクトのストアは次のような文字列です。
blob·14␀Hello,·world!␊
· は半角空白、␀ は null 文字、␊ は Unix の改行文字です。
このフォーマットを見ればわかる通り、いつ誰がどんな名前でファイルを作成しても、同じストアができるはずです。
試しに同様の手順(文字列の内容さえ同じなら、リポジトリやファイルの名前は違っていても構いません)を踏んでみてください。
.git/objects/af/5626b4a114abcb82d63db7c8082c3c4756e51b が作成されて、これを先程のように解凍すれば同じ文字列を得ることができるはずです。
Tree オブジェクトのストア
Tree オブジェクトは些か複雑です。
それぞれのエントリについての情報が一行1にまとめられ、その連結が Tree オブジェクトの content になっています。
エントリを表現するブロックの先頭は EntryKind に対応する 5 ないし 6 桁の数字列です。
空白を挟んだ後、エントリの名前が続きます。
null 文字を挟んだ後、エントリの ID が続きます2。
// when `object` matches the pattern `Tree tree`.
let content =
tree.children
|> Array.map (fun entry ->
let kind =
match entry.kind with
| Directory -> 40000
| Executable -> 100755
| TextFile -> 100644
| Symlink -> 120000
| SubModule -> 160000
let id =
match entry.id with
| EntryId.BlobId(Id bytes)
| EntryId.TreeId(Id bytes) -> Id bytes
$"{kind} {entry.name}\x00{id}")
|> Aist.fold (fun str child -> str + child) ""先程 hello.txt を ステージしました。
この時点ではまだリポジトリルートに対応する Tree オブジェクトはまだ生成されていません。
Commit オブジェクトのストアを説明する前ですが、先に commit をして Tree オブジェクトを生成します。
$ git commit -m "First commit."
[main (root-commit) 5ee2919] First commit.
1 file changed, 1 insertion(+)
create mode 100644 hello.txtリポジトリルートに対応する Tree オブジェクトのストアにより、.git/objects/ec/947e3dd7a7752d078f1ed0cfde7457b21fef58 が作成されているはずです。
ストアは次のような形式になっています2。
tree·37␀100644·hello.txt␀af5626b4a114abcb82d63db7c8082c3c4756e51b
Commit オブジェクトのストア
Blob・Tree オブジェクトと異なり、Commit オブジェクトは author や comitter、時刻情報を含むので、それぞれの環境で別のオブジェクトが生成されるはずです。
// when `object` matches the pattern `Commit commit`.
let content =
let tree = $"tree {commit.tree}\n"
let parents =
commit.parent
|> Aist.map (fun id -> $"parent {id}")
|> Aist.fold (fun str parent -> str + parent + "\n") ""
let author =
let (user, time) = commit.authorInfo
$"author {user} {time}\n"
let committer =
let (user, time) = commit.committerInfo
$"committer {user} {time}\n"
let message = commit.message + "\n"
tree + parents + author + committer + "\n" + message先程の commit により、私の環境では .git/objects/5e/e2919f4f238deefe79d78e30ea934f2241d5e9 に次のストアの Zlib 圧縮が生成されました。
[at] は @ に置換してください。
commit·182␀tree·ec947e3dd7a7752d078f1ed0cfde7457b21fef58␊
author·atree4728·<atree.public[at]gmail.com>·1724832676·+0900␊
committer·atree4728·<atree.public[at]gmail.com>·1724832676·+0900␊
␊
First·commit.␊
一行目の tree に続くのはリポジトリルートに対応する ID です。先に確認した Tree オブジェクトの ID を一致していることがわかります。
Tag オブジェクトのストア
Tag オブジェクトのストアは Commit オブジェクトのストアと同様です。
// when `object` matches the pattern `Tag tag`.
let content =
let objectId = $"object {tag.id}\n"
let objectType =
let objectType =
match tag.id with
| BlobId _ -> "blob"
| TreeId _ -> "tree"
| CommitId _ -> "commit"
| TagId _ -> "tag"
$"type {objectType}\n"
let name = $"tag {tag.name}\n"
let tagger =
let (user, time) = tag.taggerInfo
$"tagger {user} {time}\n"
let message = tag.message + "\n"
objectId + objectType + name + tagger + "\n" + message注釈付きのタグを作成して、そのオブジェクトを確認してみましょう。
今回は先程の commit に version 0 というメッセージをつけ、v0 という名前でタグを付けます。
$ git tag -a -m "version 0" v0最後の引数として任意に ID を追加すればそのオブジェクトがタグされますが、省略すると直前の commit にタグすることができます。
.git/objects/18/242f926dd097886d3420ff038a2bb6f9765038 にオブジェクトが生成され、ストアは次のようになりました。
tag·137␀object·5ee2919f4f238deefe79d78e30ea934f2241d5e9␊
type·commit␊
tag·v0␊
tagger·atree4728·<atree.public[at]gmail.com>·1724834089·+0900␊
␊
version·0␊
Git リファレンス
Git リファレンスはいずれも .git/refs/ に保存され、本質的には単なる Git オブジェクトへの参照です。
注釈付きタグ・軽量タグ・ブランチ・リファレンスのリファレンスの 4 種類に分類されます。
type Reference =
| AnnotatedTag of {| tagName: string; id: Id<AnnotatedTag> |}
| LightweightTag of {| tagName: string; id: ObjectId |}
| Branch of Branch
| Reference of Reference
let refs: Reference list = []Git リファレンスはどれもオブジェクトではないので、ストアや ID という概念は存在しないことに注意してください。
注釈付きタグ
先程注釈付きタグとして v0 を追加し、対応する Tag オブジェクトが .git/objects/ に保存されていました。
しかし、現時点では v0 という生の文字列はどこにも保存されていません。
git show v0 によりこのタグを参照できるのは、これが Git リファレンスとして .git/refs/tags/v0 に保存されているためです。
しかしその内容はいたって単純で、v0 Tag オブジェクトの ID がそのまま保存されています。
18242f926dd097886d3420ff038a2bb6f9765038軽量タグ
注釈付きタグは Tag オブジェクトを介して目当ての Git オブジェクトを参照していました。
一方で、軽量タグは直接 Git オブジェクトを参照します。
このため、Reference.AnnotatedTag の引数である無名レコードの id には Id<AnnotatedTag> 型がついている9一方、Reference.LightweightTag の id には ObjectId 型がついています。
9: Reference.AnnotatedTag は Reference 型のコンストラクタであり、Id<AnnotatedTag> の 型引数は Git オブジェクトとして定義した AnnotatedTag 型です。
実際に軽量タグを作成して確認してみます。
ここでは、初めに作成した hello.txt に hello_txt タグをつけることにします。
hello.txt に対応する Blob オブジェクト ID は af5626b4a114abcb82d63db7c8082c3c4756e51b だったので、次のコマンドにより軽量タグを作成できます。
$ git tag hello_txt af5626b4a114abcb82d63db7c8082c3c4756e51b.git/refs/tags/hello_txt が生成され、中身は参照先の ID そのものになっていることがわかります。
af5626b4a114abcb82d63db7c8082c3c4756e51bブランチ
ブランチも本質的には Commit オブジェクトへの参照です。 Git オブジェクトのなす DAG の構造10に思いを馳せると、私たちが普段「ブランチ」という言葉で指しているのは、「Git オブジェクトのなす DAG 上で、参照先の Commit オブジェクトから到達可能な頂点の集合」だと思うことができます。 10: Commit オブジェクトの下流にワーキングディレクトリがあり、Commit オブジェクト間の辺は過去方向に伸びていました。
ブランチはローカルブランチとリモートブランチに分けられ、Branch 型は次のように定義できます。
type Branch =
| Heads of {| branchName: string; id: Id<Commit> |}
| Remote of {| remoteName: string; branchName: string; id: Id<Commit> |}これらの情報がどのように保管されるかはタグのときと同様です。
ローカルブランチは .git/refs/heads/<branchName>、リモートブランチは .git/refs/remote/<remoteName>/<branchName> に Commit オブジェクトの ID を直接保存することで管理されています。
例えば現在 checkout しているブランチは main なので、.git/refs/heads/main に最新の Commit オブジェクトの ID が保存されています。
このファイルは最初に commit した時点で作成されます。
5ee2919f4f238deefe79d78e30ea934f2241d5e9ブランチとタグの違い
ブランチと(軽量)タグの型定義を観察すると、いずれも名前と参照を持つ構造になっていて、違いは参照先の型の制限11だけのように思えます。 ブランチとタグの本質的な違いはなんなのでしょうか? 11: ブランチの参照は
Id<Commit>であるのに対し、タグの参照先はObjectIdでした。答えは可変性です。 タグは一度作成されると通常の操作では編集されたり削除されたりすることはありませんが、ブランチ(の参照先)は commit や fetch をした際に変更されます。
リファレンスのリファレンス
リファレンス自体をリファレンスすることができます。 このとき、リファレンスには ID がついていないので、リファレンスの名前で直接参照することになります。
リファレンスのリファレンスの例としてわかりやすいのは HEAD です12。
HEAD は現在 checkout しているブランチを参照します。
例えば、現時点で checkout しているブランチはローカルの main なので、.git/HEAD は次のようになっています。
12: 逆に HEAD 以外に思い付かず……
ref: refs/heads/mainこれまでにいくつもの参照がありましたが、ID ではなく直接名前で参照するのはリファレンスのリファレンスだけです。 それ以外の全ての参照は ID によるものでした。 ストアのフォーマットを思い出すと、この ID は Git オブジェクトのなす DAG における子の ID により計算されています。 つまり、Git オブジェクトの IDは、当の DAG 上でそのオブジェクトから到達可能な全ての頂点の情報を含んでいます。 この性質により履歴の改竄が困難になり、閉路が作られることがなくなっています。
F# によるツアー
ストアのフォーマットを説明する過程でリポジトリを作成し、その中でいくつかの Git 操作を行いました。 このときに裏で行われていた処理も F# で表現できるので、これを示して終わりにしようと思います13。 13: F# が偉くて束縛のときに型情報を書く必要が全然無いので、LSP なしでコードを読むのはつらいかもしれません。
// $ git init
let mutable objects = Map<ObjectId, Object> []
let mutable refs: Reference list = []
// $ echo "Hello, world!" > hello.txt
// $ git add hello.txt
let blob = Blob { content = "Hello, world!\n" }
let blob_id = generateId blob
objects.Add(blob_id, blob)
// $ git commit -m "First commit."
let tree =
Tree { children = [| { kind = TextFile
name = "hello.txt"
id =
let (BlobId inner) = blob_id
EntryId.BlobId inner } |] }
let tree_id = generateId tree
objects.Add(tree_id, tree)
let atree =
{ name = "atree4728"
email = "atree.public[at]gmail.com" }
let now = getTimeInfo ()
let commit =
Commit { tree =
let (TreeId inner) = tree_id
inner
parent = [||]
authorInfo = atree, now
committerInfo = atree, now
message = "First commit." }
let commit_id = generateId commit
objects.Add(tree_id, tree)
let mutable main =
{| branchName = "main"
id =
let (CommitId inner) = commit_id
inner |} // Anonymous record
|> Heads // Branch
|> Branch // Reference
let mutable HEAD = Reference main
// $ git tag -a -m "version 0" v0
let tag =
Tag { name = "v0"
id = commit_id
taggerInfo = atree, now
message = "version 0" }
let tag_id = generateId tag
objects.Add(tag_id, tag)
refs <- List.append refs [ AnnotatedTag {| tagName = "v0"
id =
let (TagId inner) = tag_id
inner |} ]
// $ git tag "hello_txt" <blob_id>
refs <- List.append refs [ LightweightTag {| tagName = "hello_txt"; id = blob_id |} ]References
- git Book
- koseki2, Git の仕組み(1)
- koseki2, Git の仕組み(2)
- うじまる, RustでつくるGit入門
- Rui Ueyama, 低レイヤを知りたい人のためのCコンパイラ作成入門