🦉

[Inside Git #2] Gitオブジェクトのこぼれ話

2023/02/05に公開

前回はGitオブジェクトについて勉強して、Gitがどのようにバージョン管理をしているかを学びました。

https://zenn.dev/yusei_sayama/articles/dd6df0effe0970

前回の簡単な復習をすると、以下のようなことが分かったのでしたね。

  • Gitオブジェクトには、コミットを表すcommitオブジェクト、ディレクトリを表すtreeオブジェクト、ファイルを表すblobオブジェクトなどのタイプが存在する。
  • commitオブジェクトは直前のバージョンを表すcommitオブジェクトと、現在のバージョンのファイル群を再構築するために必要なtreeオブジェクトの2つを参照している。
  • ルートディレクトリに対応する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オブジェクトの中身は2つから成り、1つはblob <content-size>\0というヘッダー[1]、もう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オブジェクトの中身も2つから成り、1つは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オブジェクトへの参照値 (ハッシュ値) を1つ保持しているんでしたね。
  • parent : こちらも前回の記事で紹介しました。commitオブジェクトは直前のバージョンであるコミットへの参照値 (ハッシュ値) を保持しているんでしたね。ただし、前回触れなかったparentの数についても追記しておかなければなりません。
    • root commit : git init 後の最初のコミットをよくみてみると、parentの項目が存在しないことがわかると思います。これは一番最初のコミットなので、直前のヒストリが無いということで納得ですね。このようなコミットをルートコミットといいます。
    • multiple parent commit : git merge などをすると、2つ以上[2]の歴史の脈流を受け継いだコミットができ上がります。このようなとき、parentの項目は2行以上になっているはずです。parentを2つ以上もつコミットをマルチペアレントといいます[3]。マルチペアレントコミットの中でもマージによってできたコミットをマージコミット (merge commit) といいます[4]
  • author : コード変更を行なった人物の情報です。一般的には一度記録されてから変更されるような情報ではありません[5]
    • author_name : コード変更を行なった人物の名前。
    • author_email : コード変更を行なった人物のメールアドレス。< > で囲われます。
    • author_date_seconds : コード変更の確定を行ったタイミングのUNIX時間。e.g. 2023/02/03 00:00:00 であれば 1675296000。
    • author_date_timezone : コード変更の確定を行った地域のタイムゾーン。e.g. 日本だと9時間の時差があるため +0900
  • committer : コミットを行なった人物の情報です。Gitでは様々な方法で、ヒストリを編集することができます。この編集に伴いcommitterの情報も更新されます。
    • 各項目はauthorと同様。
  • commit_message : コミットメッセージです。committerの項目のあと、空行1行を挟み、コミットメッセージであるテキストがきます。

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オブジェクトの中に書かれている情報の中にモードというものがありました。これは以下の5種類が存在しています。

  • 100644 : 通常の (実行ファイルではない) ファイルです。
  • 100755 : 実行ファイルです。
  • 120000 : シンボリックリンクです。
  • 160000 : Gitリンクです。git submodule などで使用されます。サブモジュールについてはまた別の機会に解説してみたいと思います。
  • 040000 : サブディレクトリです。

 

DAG

前回の記事では図の見やすさを優先して下のような図を使用していました。

しかし、944b8EF というblobオブジェクトは実際には1つしかなく、こちらをもう少し正確に書くとすれば以下のような図になるでしょう。

さらに、前回作成したリポジトリのGitオブジェクト全体を略図にすると以下のようになります。

このような、有限個の頂点 (vertex) と2点を結ぶ有限個の辺 (edge) の集まりのことをグラフ (graph) といい、各辺に向きのついたグラフを有向グラフ (directed graph) といいます。
また、有向グラフのある頂点から辺の向きに沿って次の頂点、次の頂点へと辿っていくとき、元の頂点に戻ってくるような経路を閉路 (cycle) といいます。閉路を持たない有向グラフをDAG (Directed Acyclic Graph) といいます。

Gitオブジェクト全体が作るグラフはまさしくDAGになっていたんですね!!

DAGはGitの内部だけではなく身近な場面に多く現れます!例えば、パッケージの依存関係[7]や、本の参考文献からなる関係[8]タスクの依存関係[9]などもDAGになっています。他にもコンピュータサイエンスの多くの場面でDAGが大活躍です

ところで、先ほどのGitオブジェクト全体が作るDAGは、下向きの矢印もあれば上向きの矢印もありました。全ての矢印の向きを下向きになるように頂点を並び替えることはできるでしょうか?これは割と簡単にできそうですね。では一般のDAGでそのようなことができるでしょうか?考えてみるととっても愉しいです!!

気づくとあなたもトポロジカルソートの門を潜ってしまいましたね!!良い数学ライフを!!(Gitにはあまり関係ない話でした)

さて、今回はこんなところで内容を終えたいと思います。次回は(いつになるか分かりませんが)、インデックスの中身について記事を書こうと思っています。
御拝読ありがとうございました。

 

Reference

脚注
  1. \0とはヌル文字のことです。 ↩︎

  2. オクトパスマージなどを考えると、合流する歴史の脈流は3つ以上になることも想定されます。 ↩︎

  3. 公式ドキュメントなどに "multiple parent" という言葉は見つけられませんでしたが、少なくともGitユーザーの間では通じる一般的な語彙だと思います。 ↩︎

  4. マルチペアレントなコミットが作成される場面はマージだけではありません。身近な例では git stash などがそうでしょう。こちらはいずれ記事にしたいと思います! ↩︎

  5. 変更する方法はありますが、時間が経ってからコードの作者が変わることは無いでしょう。変更が想定されるのは、コード作者を間違えて登録してしまったので修正したいなどのかなり限定的な場合のみだと思います。 ↩︎

  6. commitオブジェクトではハッシュ値が文字列表現のまま、すなわち40bytes分の幅をとっていましたが、treeオブジェクトではきちんと20bytes分の幅であるバイナリデータを使用しているんですね。何だか対称性がないような気がしますが、僕の予想では、treeオブジェクトの中に書かれるハッシュ値の数が、commitオブジェクトの中に書かれる高々数個のハッシュ値の数よりはるかに多いことが想定されるため、treeオブジェクトではメモリスペース削減のために20bytes分のバイナリデータを使用し、commitオブジェクトでは見やすさを優先して40bytes分のテキストデータを使用しているのではないかなと思っています ↩︎

  7. パッケージAがパッケージBに依存しているとき、A → B とします。依存関係が巡回してしまうと、いったいどのバージョンのパッケージを使用すれば良いか解決できないので困ってしまいますね。 ↩︎

  8. 本Aの参考文献に、本Bが載っていたとき、A → B とします。未来の本を参考文献に書くことはできないのでDAGになりますね。版などによる事情は無視しています。 ↩︎

  9. タスクAが終わらないとタスクBに取りかかることができないとき、A → B とします。タスクの大変さに比例して頂点に重みをつけても面白いかもしれないですね。 ↩︎

Discussion