[Inside Git #2] Gitオブジェクトのこぼれ話
前回はGitオブジェクトについて勉強して、Gitがどのようにバージョン管理をしているかを学びました。
前回の簡単な復習をすると、以下のようなことが分かったのでしたね。
- Gitオブジェクトには、コミットを表すcommitオブジェクト、ディレクトリを表すtreeオブジェクト、ファイルを表すblobオブジェクトなどのタイプが存在する。
- commitオブジェクトは直前のバージョンを表すcommitオブジェクトと、現在のバージョンのファイル群を再構築するために必要なtreeオブジェクトの２つを参照している。
- ルートディレクトリに対応するtreeオブジェクトがあれば、その時のファイル群を再構築することができる。
- blobオブジェクトやtreeオブジェクトが変更されると、その変更がルートディレクトリに対応するtreeオブジェクトまで伝播する。
- HEADやブランチとはただの参照値のことで、簡単にいえばただの文字列である。
今回は、混乱を避けるために前回あえて触れなかった、Gitオブジェクトの実際の中身やハッシュ値の計算について簡単に紹介しようと思います。この記事を読めば、おそらくblobオブジェクトやtreeオブジェクトなどを0から作成し、ハッシュ値を計算することもできるようになるはずです！
環境
- MacOS Monterey 12.6
- git version 2.39.0
対象読者
- 前回の記事を読んでいれば理解できると思います
- 今回はPythonを少しだけ使いますが必須ではないです
Gitオブジェクトの作り方
早速Gitオブジェクトのレシピを紹介していきましょう！
Gitオブジェクトを作成するPythonスクリプトを用意しておきましたが、文法を知らなくても何となくの理解で読み進められるようにしています。
blobオブジェクト
blobオブジェクトの中身は２つから成り、１つはblob <content-size>\0というヘッダー[1]、もう１つは対応するファイルの中身 (コンテンツ) になります。これらヘッダーとコンテンツをくっ付けてZlibにより圧縮したものが実際のblobオブジェクトの中身になります！
そしてこのヘッダー+コンテンツからSHA-1というハッシュ関数によりハッシュ値が計算されます！
.git/objects/の中には無数にバイナリファイル (Gitオブジェクト) があり、blobオブジェクトを表すものもあれば、treeオブジェクトを表すものもある、という混沌とした状態でした。しかし、Gitはこの一行目にあるヘッダーを見ることで、それがblobオブジェクトであることに気づくことができるんですね。
実際に既存のGitオブジェクトを0から作成して、本当にあっているか確かめてみます。前回作成したblobオブジェクト 944b8ef を作ってみましょう！
import hashlib
import zlib
# blobオブジェクトの中身
content = """# カレーのレシピ
美味しいカレーを作ろう！
""".encode()
# headerのフォーマットは「blob <content_size>\0」
content_size = len(content)
header = f'blob {content_size}\0'.encode()
# zlibによる圧縮
blob = zlib.compress(header + content, level=1)
purity_show_binary_data(blob)
# SHA-1によるハッシュ値の計算
hash = hashlib.sha1(header + content).hexdigest()
print(hash)
結果はこのようになります。確かにGitオブジェクトの中身も、ハッシュ値も一致していますね！0からblobオブジェクトを作ることに成功しました！
# purity_show_binary_data(blob)の出力結果
78 01 4b ca c9 4f 52 30 33 64 50 56 78 dc b4 fa
71 f3 9a c7 cd 7b 1e 37 ae 03 31 9a b6 3f 6e 9e
c2 f5 7c 5f df d3 89 9b 1f 37 4e 7f dc d8 82 50
d1 34 e9 c9 de 39 8f 9b 7a 1f 37 b6 bd df d3 c8
05 00 51 6e 29 bb
# print(hash)の出力結果
944b8ef2e83aea596fd2a662d629042f3e92edc3
# 実際のblobオブジェクト「944b8ef」の中身
% od -tx1 .git/objects/94/4b8ef2e83aea596fd2a662d629042f3e92edc3
0000000 78 01 4b ca c9 4f 52 30 33 64 50 56 78 dc b4 fa
0000020 71 f3 9a c7 cd 7b 1e 37 ae 03 31 9a b6 3f 6e 9e
0000040 c2 f5 7c 5f df d3 89 9b 1f 37 4e 7f dc d8 82 50
0000060 d1 34 e9 c9 de 39 8f 9b 7a 1f 37 b6 bd df d3 c8
0000100 05 00 51 6e 29 bb
0000106
バイナリデータの表示 🧸
上記のスクリプトで使用した、バイナリデータをきれいに出力するメソッドです。
def purity_show_binary_data(input_bytes: bytes):
line: List[str] = []
for byte in input_bytes:
line.append('{0:02x}'.format(byte))
output: str = ''
for idx in range(len(line)):
if idx % 16 != 15:
output += f'{line[idx]} '
else:
output += f'{line[idx]}\n'
output.rstrip()
print(output)
commitオブジェクト
commitオブジェクトの中身も２つから成り、１つはcommit <content-size>\0というヘッダー、もう一つはコミットの中身 (コンテンツ) になります。これらヘッダーとコンテンツをくっ付けてZlibにより圧縮したものが実際のcommitオブジェクトの中身になります！
そしてこのヘッダー+コンテンツからSHA-1というハッシュ関数によりハッシュ値が計算されます！先ほどのblobオブジェクトと全く同様ですね！
実際に既存のGitオブジェクトを0から作成して、本当にあっているか確かめてみます。前回作成したcommitオブジェクト 845a32f を作ってみましょう！
import hashlib
import zlib
# commitオブジェクトの中身
content = """tree 0cdbafebf15332c0788686f2457a87d8ea3ddbf5
parent 8add7f0af64c4166aa39f3b2430c07c2f3bd3d4f
author Sayama <sayama@example.co.jp> 1673766412 +0900
committer Sayama <sayama@example.co.jp> 1673766412 +0900
README.mdと同じ内容のファイルを作成
""".encode()
# headerのフォーマットは「commit <content_size>\0」
content_size = len(content)
header = f'commit {content_size}\0'.encode()
# zlibによる圧縮
commit = zlib.compress(header + content, level=1)
purity_show_binary_data(commit)
# SHA-1によるハッシュ値の計算
hash = hashlib.sha1(header + content).hexdigest()
print(hash)
結果はこのようになります。確かにGitオブジェクトの中身も、ハッシュ値も一致していますね！0からcommitオブジェクトを作ることに成功しました！
# purity_show_binary_data(commit)の出力結果
78 01 95 8e 3d 4a 03 41 18 40 ad e7 14 d3 0b cb
ec fc 07 44 14 4c 69 a3 27 f8 76 be 19 8c 38 ee
b2 8e a0 e5 6e 50 2c 52 84 80 90 22 8d 90 22 10
48 6f e1 69 c6 f5 1c 09 b9 81 d5 7b cd 83 e7 ea
18 27 89 72 a5 4e 52 eb 3d 65 0e 2b 08 be 0a a5
12 82 3b 66 ac d5 56 07 2e 95 01 6b d0 7a 10 88
55 50 a4 81 d6 3f 26 6a 01 d1 04 06 41 4b 27 4b
ad 01 c4 28 88 8a 4b c1 0e b1 e3 07 47 81 32 10
78 4e 77 75 4b 6f e1 15 22 d0 b3 a7 23 2f fc 0b
c4 e6 c1 17 ae 2e ee 9b 73 5a 6a 23 8c d6 b2 e4
f4 94 8d 18 23 ee b8 97 fc bf 43 72 33 be bc ba
1e 17 11 73 b7 19 e6 b3 dc 2d 87 f7 b7 61 f7 9d
bb 5d 9e 7e e6 fe 2b f7 eb 3c dd e6 7e f1 fb b3
fa fb 98 93 3d 68 fd 5e bd
# print(hash)の出力結果
845a32fccb8e575edc52ad3bf44aa45b97638fae
# 実際のcommitオブジェクト「845a32f」の中身
% od -tx1 .git/objects/84/5a32fccb8e575edc52ad3bf44aa45b97638fae
0000000 78 01 95 8e 3d 4a 03 41 18 40 ad e7 14 d3 0b cb
0000020 ec fc 07 44 14 4c 69 a3 27 f8 76 be 19 8c 38 ee
0000040 b2 8e a0 e5 6e 50 2c 52 84 80 90 22 8d 90 22 10
0000060 48 6f e1 69 c6 f5 1c 09 b9 81 d5 7b cd 83 e7 ea
0000100 18 27 89 72 a5 4e 52 eb 3d 65 0e 2b 08 be 0a a5
0000120 12 82 3b 66 ac d5 56 07 2e 95 01 6b d0 7a 10 88
0000140 55 50 a4 81 d6 3f 26 6a 01 d1 04 06 41 4b 27 4b
0000160 ad 01 c4 28 88 8a 4b c1 0e b1 e3 07 47 81 32 10
0000200 78 4e 77 75 4b 6f e1 15 22 d0 b3 a7 23 2f fc 0b
0000220 c4 e6 c1 17 ae 2e ee 9b 73 5a 6a 23 8c d6 b2 e4
0000240 f4 94 8d 18 23 ee b8 97 fc bf 43 72 33 be bc ba
0000260 1e 17 11 73 b7 19 e6 b3 dc 2d 87 f7 b7 61 f7 9d
0000300 bb 5d 9e 7e e6 fe 2b f7 eb 3c dd e6 7e f1 fb b3
0000320 fa fb 98 93 3d 68 fd 5e bd
0000331
blobオブジェクトと全く同じようにして計算することができましたが、少しだけ注意点があります。それは、commitオブジェクトのコンテンツのフォーマットについてです。
commitオブジェクトのコンテンツのフォーマット
先ほどのblobオブジェクトのコンテンツは、実際のファイルの中身なので、どんな内容が来ても問題ありません。しかし、commitオブジェクトではコンテンツが意味不明な内容ですと、Gitシステムくんは何のことやら、それを正しくコミットとして扱うことができません。そこでcommitオブジェクトのコンテンツにはこのフォーマットで記載しましょうというルールがあります。それは次のようなフォーマットになります。
tree {tree_sha}
[parent {parent_sha}]
author {author_name} <{author_email}> {author_date_seconds} {author_date_timezone}
committer {committer_name} <{committer_email}> {committer_date_seconds} {committer_date_timezone}
{commit_message}
- tree : こちらは前回の記事で紹介しました。commitオブジェクトはルートディレクトリに対応するtreeオブジェクトへの参照値 (ハッシュ値) を１つ保持しているんでしたね。
-
parent : こちらも前回の記事で紹介しました。commitオブジェクトは直前のバージョンであるコミットへの参照値 (ハッシュ値) を保持しているんでしたね。ただし、前回触れなかったparentの数についても追記しておかなければなりません。
-
root commit :
git init後の最初のコミットをよくみてみると、parentの項目が存在しないことがわかると思います。これは一番最初のコミットなので、直前のヒストリが無いということで納得ですね。このようなコミットをルートコミットといいます。 -
multiple parent commit :
git mergeなどをすると、２つ以上[2]の歴史の脈流を受け継いだコミットができ上がります。このようなとき、parentの項目は２行以上になっているはずです。parentを２つ以上もつコミットをマルチペアレントといいます[3]。マルチペアレントコミットの中でもマージによってできたコミットをマージコミット (merge commit) といいます[4]。
-
root commit :
-
author : コード変更を行なった人物の情報です。一般的には一度記録されてから変更されるような情報ではありません[5]。
- author_name : コード変更を行なった人物の名前。
-
author_email : コード変更を行なった人物のメールアドレス。
< >で囲われます。 - author_date_seconds : コード変更の確定を行ったタイミングのUNIX時間。e.g. 2023/02/03 00:00:00 であれば 1675296000。
-
author_date_timezone : コード変更の確定を行った地域のタイムゾーン。e.g. 日本だと９時間の時差があるため
+0900。
-
committer : コミットを行なった人物の情報です。Gitでは様々な方法で、ヒストリを編集することができます。この編集に伴いcommitterの情報も更新されます。
- 各項目はauthorと同様。
- commit_message : コミットメッセージです。committerの項目のあと、空行１行を挟み、コミットメッセージであるテキストがきます。
treeオブジェクト
もう予想がつくかもしれませんが、treeオブジェクトはtree <content-size>\0というヘッダーを、treeオブジェクトの中身 (コンテンツ) にくっ付けてZlibにより圧縮したものになります！
そしてこのヘッダー+コンテンツからSHA-1というハッシュ関数によりハッシュ値が計算されます！下のコードをチラッと見ると、明らかにtreeオブジェクトのコンテンツにもフォーマットがありそうですが、こちらは後で触れます。
実際に既存のGitオブジェクトを0から作成して、本当にあっているか確かめてみます。前回作成したtreeオブジェクト 0cdbafe を作ってみましょう！
import hashlib
import zlib
# treeオブジェクトの中身
content = '100644 README.md'.encode() + b'\0' + bytes.fromhex('944b8ef2e83aea596fd2a662d629042f3e92edc3') \
+ '100644 curry-ingredients.md'.encode() + b'\0' + bytes.fromhex('87f3f8afa28796b2eeda4094bee471acbde78dcc') \
+ '40000 dir'.encode() + b'\0' + bytes.fromhex('6fc8f11b5d479640d1c79f9f8697c35f66d08f67')
# headerのフォーマットは「tree <content_size>\0」
content_size = len(content)
header = f'tree {content_size}\0'.encode()
# zlibによる圧縮
tree = zlib.compress(header + content, level=1)
purity_show_binary_data(tree)
# SHA-1によるハッシュ値の計算
hash = hashlib.sha1(header + content).hexdigest()
print(hash)
結果はこのようになります。確かにGitオブジェクトの中身も、ハッシュ値も一致していますね！0からtreeオブジェクトを作ることに成功しました！
# purity_show_binary_data(tree)の出力結果
78 01 2b 29 4a 4d 55 30 34 34 65 30 34 30 30 33
31 51 08 72 75 74 f1 75 d5 cb 4d 61 98 e2 dd f7
e9 85 d5 ab c8 fc 4b cb 92 ae 69 b2 e8 db 4d 7a
7b 18 aa 28 b9 b4 a8 a8 52 37 33 2f bd 28 35 25
33 35 af a4 18 a4 be fd f3 8f f5 8b da a7 6d 7a
77 cb 61 ca be 27 85 6b f6 3e ef 3d 63 62 00 04
0a 29 99 45 0c f9 27 3e 4a c7 ba 4f 73 b8 78 7c
fe fc b6 e9 87 e3 d3 2e f4 a7 03 00 b7 8f 35 aa
# print(hash)の出力結果
0cdbafebf15332c0788686f2457a87d8ea3ddbf5
# 実際のcommitオブジェクト「0cdbafe」の中身
% od -tx1 .git/objects/0c/dbafebf15332c0788686f2457a87d8ea3ddbf5
0000000 78 01 2b 29 4a 4d 55 30 34 34 65 30 34 30 30 33
0000020 31 51 08 72 75 74 f1 75 d5 cb 4d 61 98 e2 dd f7
0000040 e9 85 d5 ab c8 fc 4b cb 92 ae 69 b2 e8 db 4d 7a
0000060 7b 18 aa 28 b9 b4 a8 a8 52 37 33 2f bd 28 35 25
0000100 33 35 af a4 18 a4 be fd f3 8f f5 8b da a7 6d 7a
0000120 77 cb 61 ca be 27 85 6b f6 3e ef 3d 63 62 00 04
0000140 0a 29 99 45 0c f9 27 3e 4a c7 ba 4f 73 b8 78 7c
0000160 fe fc b6 e9 87 e3 d3 2e f4 a7 03 00 b7 8f 35 aa
0000200
treeオブジェクトコンテンツのフォーマット
treeオブジェクトも、commitオブジェクトと同様にコンテンツにフォーマットが存在しています。それは次のようになっています。
{mode} {file/directory_name}\0{git_object_sha}
100644 などのモードの後にスペースを挟み、ファイル名やディレクトリ名などが来ます。ファイル名やディレクトリ名にはもちろんスペースが含まれる可能性があるので、どこまでがファイル名/ディレクトリ名なのかを知るための目印としてヌル文字 \0 が使用されています。この後に続くハッシュ値は必ず20bytesということが分かっているので、ハッシュ値と次のモードの間に目印を入れる必要はありません[6]。
モードとその種類
treeオブジェクトの中に書かれている情報の中にモードというものがありました。これは以下の５種類が存在しています。
-
100644: 通常の (実行ファイルではない) ファイルです。 -
100755: 実行ファイルです。 -
120000: シンボリックリンクです。 -
160000: Gitリンクです。git submoduleなどで使用されます。サブモジュールについてはまた別の機会に解説してみたいと思います。 -
040000: サブディレクトリです。
DAG
前回の記事では図の見やすさを優先して下のような図を使用していました。
しかし、944b8EF というblobオブジェクトは実際には１つしかなく、こちらをもう少し正確に書くとすれば以下のような図になるでしょう。
さらに、前回作成したリポジトリのGitオブジェクト全体を略図にすると以下のようになります。
このような、有限個の頂点 (vertex) と２点を結ぶ有限個の辺 (edge) の集まりのことをグラフ (graph) といい、各辺に向きのついたグラフを有向グラフ (directed graph) といいます。
また、有向グラフのある頂点から辺の向きに沿って次の頂点、次の頂点へと辿っていくとき、元の頂点に戻ってくるような経路を閉路 (cycle) といいます。閉路を持たない有向グラフをDAG (Directed Acyclic Graph) といいます。
Gitオブジェクト全体が作るグラフはまさしくDAGになっていたんですね！！
DAGはGitの内部だけではなく身近な場面に多く現れます！例えば、パッケージの依存関係[7]や、本の参考文献からなる関係[8]、タスクの依存関係[9]などもDAGになっています。他にもコンピュータサイエンスの多くの場面でDAGが大活躍です。
ところで、先ほどのGitオブジェクト全体が作るDAGは、下向きの矢印もあれば上向きの矢印もありました。全ての矢印の向きを下向きになるように頂点を並び替えることはできるでしょうか？これは割と簡単にできそうですね。では一般のDAGでそのようなことができるでしょうか？考えてみるととっても愉しいです！！
気づくとあなたもトポロジカルソートの門を潜ってしまいましたね！！良い数学ライフを！！(Gitにはあまり関係ない話でした)
さて、今回はこんなところで内容を終えたいと思います。次回は（いつになるか分かりませんが）、インデックスの中身について記事を書こうと思っています。
御拝読ありがとうございました。
Reference
-
What is the file format of a git commit object data structure? - stackoverflow
commitオブジェクトのコンテンツのフォーマットについて参考にしました。 -
Git - git-fast-import Documentation
treeオブジェクト内のエントリのモードの種類について参考にしました。 -
Difference between author and committer in Git? - stackoverflow
コミットのAuthorとCommitterの違いについて参考にしました。
-
\0とはヌル文字のことです。 ↩︎ -
オクトパスマージなどを考えると、合流する歴史の脈流は３つ以上になることも想定されます。 ↩︎
-
公式ドキュメントなどに "multiple parent" という言葉は見つけられませんでしたが、少なくともGitユーザーの間では通じる一般的な語彙だと思います。 ↩︎
-
マルチペアレントなコミットが作成される場面はマージだけではありません。身近な例では
git stashなどがそうでしょう。こちらはいずれ記事にしたいと思います！ ↩︎ -
変更する方法はありますが、時間が経ってからコードの作者が変わることは無いでしょう。変更が想定されるのは、コード作者を間違えて登録してしまったので修正したいなどのかなり限定的な場合のみだと思います。 ↩︎
-
commitオブジェクトではハッシュ値が文字列表現のまま、すなわち40bytes分の幅をとっていましたが、treeオブジェクトではきちんと20bytes分の幅であるバイナリデータを使用しているんですね。何だか対称性がないような気がしますが、僕の予想では、treeオブジェクトの中に書かれるハッシュ値の数が、commitオブジェクトの中に書かれる高々数個のハッシュ値の数よりはるかに多いことが想定されるため、treeオブジェクトではメモリスペース削減のために20bytes分のバイナリデータを使用し、commitオブジェクトでは見やすさを優先して40bytes分のテキストデータを使用しているのではないかなと思っています ↩︎
-
パッケージAがパッケージBに依存しているとき、A → B とします。依存関係が巡回してしまうと、いったいどのバージョンのパッケージを使用すれば良いか解決できないので困ってしまいますね。 ↩︎
-
本Aの参考文献に、本Bが載っていたとき、A → B とします。未来の本を参考文献に書くことはできないのでDAGになりますね。版などによる事情は無視しています。 ↩︎
-
タスクAが終わらないとタスクBに取りかかることができないとき、A → B とします。タスクの大変さに比例して頂点に重みをつけても面白いかもしれないですね。 ↩︎
Discussion