Gitの内部をPythonで覗いてみた
この記事はCCS †裏† Advent Calendar 2020の20日目の記事です。
前日の記事はスルメちゃんのダイエット記事。楽してダイエットはできないんですね(知ってた)。
わたしの記事ではPythonを使ってGitの中身を覗いてみようと思います。
目次
はじめに
どうも千葉大電子計算機研究会(以下CCS)、老害㌠いかろちゃんです。今回はCCSの人も使うことが多いであろう(?)Gitについて実装しながら解説します。
Gitはバージョン管理システム(VCS; Version Control System)の一つです。Gitを利用することでファイルの変更の歴史を自由に行き来すること、変更や分岐が可能になります。Gitの説明は巷に溢れていますのでここではこれ以上詳しく説明しません。
UNIXでのプログラミングの指標の一つとして挙げられる「Notes on Programming in C」では「プログラミングの中核はデータ構造であり、アルゴリズムではない。よいデータ構造を選び物事をうまく組み合わせれば、アルゴリズムはほとんど自明になる。」と述べています*1。Gitも例に漏れずスマートなデータ構造を採用しています。しかし、一般にGitの入門書では操作に注目されがちで、どうやってデータを管理しているかについてはあまり言及されません。今回はgitがどのようなデータ構造を採用し管理しているのかという視点でGitについて解説していきます。Gitの標準でもそういった低レベルなデータ構造について閲覧や操作を行うコマンドが提供されています。しかし、そういったコマンドを漫然と叩いても理解はしにくいでしょう。まずはGitの内部構造について軽く紹介します。次にGitがバージョン管理に使っている各種ファイルのパーサを実装することで理解を深めます。その後、実際にgitコマンドと作成したコマンドをあわせて使用してどのように各種ファイルが変化するかを見ていきましょう。また今回の大部分は下記のPro Gitのオンライン記事を参考に書かれています。記事内では深い解説はしておりませんのでより詳細に立ち入りたい場合はこちらを参照しつつ読むと良いでしょう。
Gitの内部構造の概観
Gitの内部構造を一言で言えば状態を格納しているKey-Value Storeです。つまり、ある時点の状態毎にあるキーを割り当て、そのキーを用いてその状態を特定、取り出すことができるシステムです。状態(たとえばファイルの内容)に対してSHA1ハッシュを計算したものをキーとして利用することで、キーと状態を結びつけています(Gitを使ったことがある方ならハッシュを使って色々操作したことがありますよね)。従って、内容が同一ならファイル名やいつ作られたかが異なっていても1つのSHA1ハッシュが割り当てられます。また逆に内容が異なれば別のキーが割り当てられます*2。
Gitのパーサを実装する
次はGitが利用しているファイルについて見ていきましょう。Gitは.git配下のファイルによって変更履歴を管理しています。とりあえずどのようなディレクトリ構成になっているか見てみましょう。
.git
├── COMMIT_EDITMSG
├── HEAD
├── config
├── description
├── hooks
│ ├── applypatch-msg.sample
│ ├── commit-msg.sample
│ ├── fsmonitor-watchman.sample
│ ├── post-update.sample
│ ├── pre-applypatch.sample
│ ├── pre-commit.sample
│ ├── pre-merge-commit.sample
│ ├── pre-push.sample
│ ├── pre-rebase.sample
│ ├── pre-receive.sample
│ ├── prepare-commit-msg.sample
│ └── update.sample
├── index
├── info
│ └── exclude
├── logs
│ ├── HEAD
│ └── refs
│ └── heads
│ └── master
├── objects
│ ├── 01
│ │ └── 0d60284bb2e1e442be64d53d135aaafd895386
│ ├── 1d
│ │ └── 17dae13b53adda563547053eb79233b236f797
│ ├── 1f
│ │ └── be2aa5acf4cfb2bda94cbecc2424da56902556
(中略)
│ ├── ff
│ │ └── 42aba00f6dbf5803d00737ecafa6561ec0c878
│ ├── info
│ └── pack
└── refs
├── heads
│ └── master
└── tags
重要なディレクトリ・ファイルは"objects", "refs"の2つのディレクトリ,そして"index"と".git/HEAD"という2つのファイルです。今回はこれらをパースするプログラムを書いていきます。言語は何でも良いのですが、今回はPythonを使って実装します。
.git/objects
まずは.git/objectsからいきましょう。先程のディレクトリ構造を見ればわかるようにSHA1ハッシュの先頭2桁をサブディレクトリに、その下に残り38桁をファイル名にしています。このファイルの中身を見ていく前にまずはキーの一覧を表示するプログラムを作りましょう。下記のようになります。
import os def ls_obj(): object_dirs = os.listdir(path='.git/objects') for object_dir in object_dirs: if len(object_dir) == 2: print(object_dir + (os.listdir(path='.git/objects/' + object_dir)[0]))
文章で書いたことをそのままプログラムに落とし込んだだけですね。
次は.git/objects配下のファイルの中身をいい感じに表示するプログラムを作りましょう。その前にこの.git/objectsに保存されているファイルについての概要を述べます。ここに保存されているファイルはGitオブジェクトです。Gitオブジェクトにはblob, tree, commitの3種類があります。blobはファイルの内容のみを格納しているオブジェクトですblobにはファイル名すら格納されていません。ほんとうに内容だけです。treeはblobと紐づくファイル名を格納し、さらに複数のファイルをまとめることができるオブジェクトです。treeは要素として複数のtreeあるいはblobオブジェクトを含みます。blobとtreeオブジェクトだけではある瞬間の状態を格納することはできても状態の履歴を追跡することができません。状態の履歴を追跡するためのオブジェクトがcommitオブジェクトです。commitオブジェクトは要素として対応するtreeと親コミット、そしてコミットコメント等の付加的情報を持ちます。
すべてのGitオブジェクトは「ヘッダ+\0*3+コンテンツ」がzip圧縮されたものとなっています*4。ヘッダ部分はオブジェクトの種類に関わらず共通で「オブジェクトタイプ コンテンツサイズ」とスペース区切りになっています。コンテンツ部分のフォーマットはオブジェクトの種類によって異なります。BlobとCommitはそのままで読めます。他方Treeは少し複雑で工夫が必要です。「モード ファイル名\0オブジェクトへの参照(SHA1ハッシュ)」が持っている参照の数だけ含まれています。
import zlib class GitObject: @property def object_type(self) -> str: return "unknown" def print(self): print("not implemented") class Blob(GitObject): def __init__(self, data: bytes): self.data = data.decode() pass def print(self): print(self.data) @property def object_type(self) -> str: return "blob" class TreeElement: def __init__(self, mode: str, filename: str, sha1_hash: int): self.mode = mode self.filename = filename self.sha1_hash = sha1_hash def get_tree_elements(data: bytes): if len(data) == 0: return [] else: mode, tmp = data.split(b' ', 1) filename, tmp2 = tmp.split(b'\0', 1) sha1_hash = tmp2[:20] body = tmp2[20:] return [TreeElement(mode.decode(), filename.decode(), sha1_hash.hex())] + get_tree_elements(body) class Tree(GitObject): def __init__(self, data: bytes): self.elements = get_tree_elements(data) @property def object_type(self) -> str: return "tree" def print(self): for element in self.elements: print("{} {} {}".format(element.mode, element.filename, element.sha1_hash)) class Commit(GitObject): def __init__(self, data): self.data = data.decode() pass def print(self): print(self.data) @property def object_type(self) -> str: return "commit" # メタクラス使うともっとスマートにできるが... def create_git_object(obj_type: str, data: bytes): if obj_type == "blob": return Blob(data) elif obj_type == "tree": return Tree(data) elif obj_type == "commit": return Commit(data) else: return GitObject() def cat_obj(hash_val): with open('.git/objects/' + hash_val[:2] + "/" + hash_val[2:], 'rb') as gitobj: res = zlib.decompress(gitobj.read()) print("hash:{}".format(hashlib.sha1(res).hexdigest())) header, body = res.split(b'\0', 1) obj_type, obj_size = header.decode().split() obj = create_git_object(obj_type, body) print("type:{}".format(obj.object_type)) obj.print()
基本的には説明したことをそのままコードに落としただけです。特殊なのといえばget_tree_elements関数でしょうか?これは再帰を使って渡されたバイナリデータを"畳み込む"ことによってTreeの要素のリストを作っています。
.git/index
次は.git/indexを見ていきます。gitではcommit前にaddをします。その時に情報が書き込まれるのがこの.git/indexです。このファイルを元にcommit時にTreeオブジェクトとそれを指しているCommitオブジェクトが生成されます。.git/indexはバイナリファイルです。フォーマットは下記に書いてあるとおりです。 github.com
バイナリファイルである点が厄介ですが、フォーマットに従って読むだけなのでさくっと実装しましょう。 下記のようになります。
import zlib def calc_padding(n: int) -> int: floor = (n - 2) // 8 target = (floor + 1) * 8 + 2 return target - n def cat_index(): with open('.git/index', 'rb') as index_file: index_file_data = index_file.read() header_sig = index_file_data[0:4] header_ver = index_file_data[4:8] header_index_number = int.from_bytes(index_file_data[8:12], byteorder='big') print("version:{}".format(int.from_bytes(header_ver, byteorder='big'))) offset = 12 print("---") for _ in range(header_index_number): ctime_s = index_file_data[offset:offset + 4] ctime_n = index_file_data[offset + 4:offset + 8] mtime_s = index_file_data[offset + 8:offset + 12] mtime_n = index_file_data[offset + 12:offset + 16] dev = index_file_data[offset + 16:offset + 20] inode = index_file_data[offset + 20:offset + 24] mode = int.from_bytes(index_file_data[offset + 24:offset + 28], byteorder='big') uid = int.from_bytes(index_file_data[offset + 28:offset + 32], byteorder='big') gid = index_file_data[offset + 32:offset + 36] file_size = int.from_bytes(index_file_data[offset + 36:offset + 40], byteorder='big') sha1 = index_file_data[offset + 40:offset + 60].hex() assume_valid_flag = int.from_bytes(index_file_data[offset + 60:offset + 62], byteorder='big') & 0x800 extended_flag = int.from_bytes(index_file_data[offset + 60:offset + 62], byteorder='big') & 0x800 stage = int.from_bytes(index_file_data[offset + 60:offset + 62], byteorder='big') & 0x300 name_length = int.from_bytes(index_file_data[offset + 60:offset + 62], byteorder='big') & 0x0FFF name = index_file_data[offset + 62:offset + 62 + name_length].decode() padding = calc_padding(name_length) offset = offset + 62 + name_length + padding print("{} {} {}".format(oct(mode), name, sha1))
今回はとりあえず一部情報のみを表示するようにしてみました。フォーマット通りにパースしただけですが、わかりにくいのはcalc_padding関数でしょうか。これは「1-8 nul bytes as necessary to pad the entry to a multiple of eight bytes while keeping the name NUL-terminated.」という要件を満たすようにいれてあります。つまり各エントリを8 byteの倍数にしたいという要求ですね。途中で出てきている2が唐突ですが、これがファイル名が出てくる前までに62 byteで8 byteの倍数にするには2 byte足りないため、それを調整した上で計算しています。
.git/refs, .git/HEAD
次最後に.git/refs, .git/HEADを見ていきましょう。これは今までのものとくらべて非常に楽です。なお、.git/refs配下にはheadsとtagsがありますが、今回はheadsのみ見ていきます。.git/refs/headsにはbranch名のファイルがそのまま置かれています。そして、その中身はCommitオブジェクトへの参照となっています。.git/HEADは現在のブランチへの参照が入っています。これらは単なるプレーンテキストですので単に下記のようになります。
import os def ls_ref(): ref_files = os.listdir(path='.git/refs/heads') for ref_file in ref_files: print(ref_file) def cat_ref(name: str): with open('.git/refs/heads/' + name, 'r') as ref_file: print(ref_file.read()) def cat_head(): with open('.git/HEAD', 'r') as head_file: print(head_file.read())
作ったプログラムを利用してGitの動作を追う
以上で作成したプログラムを利用してgitの動作を追っていきましょう。念の為全体のソースコードを下記においています。
https://gist.github.com/ikaro1192/933c380635220da7471b422ec1fb60a2
以下authorやcommitterは諸事情で伏せ字にしています。今わたしが使っているリポジトリを下記のように見てみます。
Python 3.8.5 (default, Jul 21 2020, 10:48:26) [Clang 11.0.3 (clang-1103.0.32.62)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> from ccsgit import * >>> ls_ref() test master >>> cat_head() ref: refs/heads/master
testとmasterというrefが存在することがわかりました。 また現在のブランチはmasterです。 ということでmasterを内容を見てみましょう。
>>> cat_ref("master")
5a26fc77e7f35868c5db48ad493ab5fe59605a20
これは先ほど説明したように参照しているCommitオブジェクトのハッシュです。 ということでつぎはこの中身を見てみましょう。
>>> cat_obj("5a26fc77e7f35868c5db48ad493ab5fe59605a20")
type:commit
tree 20972f6e8cc05b659c81ab48ccaa2c0d089920ba
parent 24419734f0f9d1b2ac8e01685b35323da44315e6
author ******
committer ******
色々リファクタリング
コミットオブジェクトが表示されましたね。 これで参照しているTreeオブジェクトを覗いてみましょう。
>>> cat_obj("20972f6e8cc05b659c81ab48ccaa2c0d089920ba")
type:tree
100644 .gitignore c936e61de32da173b7df6221fe72a9525dcb1a2e
100644 ccsgit.py 6427d3b0874af8467aa6c2d74af5477810e5c529
.gitignoreとccsgit.pyというファイルを管理しているようです。 ccsgit.pyの中身を覗いてみましょう。
>>> cat_obj("6427d3b0874af8467aa6c2d74af5477810e5c529")
type:blob
import zlib
import os
def ls_obj():
(後略)
ということで表示できました。 つぎは.git/indexおよび.git/objectがどう変化するかを見ていきます。 最初の状況は下記です。
>>> cat_index() version:2 --- 0o100644 .gitignore c936e61de32da173b7df6221fe72a9525dcb1a2e 0o100644 ccsgit.py 6427d3b0874af8467aa6c2d74af5477810e5c529 >>> ls_obj() 6857e44f33ad9d9a1b5971aab5fc4afdc26aaebb 573085877a591c7adffd937ef83004757ad9b2c1 3d714ec8b91b36cf751362dc57094578cb8772f6 5a26fc77e7f35868c5db48ad493ab5fe59605a20 5f7229d0ceddcc977331db217f66dfcfed0da6ac 9daeafb9864cf43055ae93beb0afd6c7d144bfa4 ee22373afdf41480021030a7cce0b1b277cf23cb c936e61de32da173b7df6221fe72a9525dcb1a2e 20972f6e8cc05b659c81ab48ccaa2c0d089920ba 6427d3b0874af8467aa6c2d74af5477810e5c529 cdb6165514fe83fc41ce1d3f63289aee774765a9 e6c4d2fa76fb4540abd7ead67884e1a0f79d6319 24419734f0f9d1b2ac8e01685b35323da44315e6
この状態から次のようなファイルを作ってみましょう。この操作は通常のターミナルから行います(以降は特に書きませんので文脈で察してください)。
$ vim hoge.txt $ cat hoge.txt hoge
この時点でcat_indexしてみると...
>>> cat_index() version:2 --- 0o100644 .gitignore c936e61de32da173b7df6221fe72a9525dcb1a2e 0o100644 ccsgit.py 6427d3b0874af8467aa6c2d74af5477810e5c529 >>> ls_obj() 6857e44f33ad9d9a1b5971aab5fc4afdc26aaebb 573085877a591c7adffd937ef83004757ad9b2c1 3d714ec8b91b36cf751362dc57094578cb8772f6 5a26fc77e7f35868c5db48ad493ab5fe59605a20 5f7229d0ceddcc977331db217f66dfcfed0da6ac 9daeafb9864cf43055ae93beb0afd6c7d144bfa4 ee22373afdf41480021030a7cce0b1b277cf23cb c936e61de32da173b7df6221fe72a9525dcb1a2e 20972f6e8cc05b659c81ab48ccaa2c0d089920ba 6427d3b0874af8467aa6c2d74af5477810e5c529 cdb6165514fe83fc41ce1d3f63289aee774765a9 e6c4d2fa76fb4540abd7ead67884e1a0f79d6319 24419734f0f9d1b2ac8e01685b35323da44315e6
当然ながらaddしてないのでまだ変わってないですね。addしてみましょう。
git add hoge.txt
0o100644 .gitignore c936e61de32da173b7df6221fe72a9525dcb1a2e 0o100644 ccsgit.py 6427d3b0874af8467aa6c2d74af5477810e5c529 0o100644 hoge.txt 2262de0c121f22df8e78f5a37d6e114fd322c0b0 >>> ls_obj() 6857e44f33ad9d9a1b5971aab5fc4afdc26aaebb 573085877a591c7adffd937ef83004757ad9b2c1 3d714ec8b91b36cf751362dc57094578cb8772f6 5a26fc77e7f35868c5db48ad493ab5fe59605a20 5f7229d0ceddcc977331db217f66dfcfed0da6ac 9daeafb9864cf43055ae93beb0afd6c7d144bfa4 ee22373afdf41480021030a7cce0b1b277cf23cb c936e61de32da173b7df6221fe72a9525dcb1a2e 20972f6e8cc05b659c81ab48ccaa2c0d089920ba 6427d3b0874af8467aa6c2d74af5477810e5c529 cdb6165514fe83fc41ce1d3f63289aee774765a9 e6c4d2fa76fb4540abd7ead67884e1a0f79d6319 24419734f0f9d1b2ac8e01685b35323da44315e6 2262de0c121f22df8e78f5a37d6e114fd322c0b0
と.git/indexにhoge.txtが追加され2262de0c121f22df8e78f5a37d6e114fd322c0b0というオブジェクトが生成されました。中身を確認してみると
>>> cat_obj("2262de0c121f22df8e78f5a37d6e114fd322c0b0")
type:blob
hoge
とたしかに追加したファイルの内容です。 次はcommitしてみましょう。
$ git commit -m 'hogeを追加してみた'
>>> cat_index() version:2 --- 0o100644 .gitignore c936e61de32da173b7df6221fe72a9525dcb1a2e 0o100644 ccsgit.py 6427d3b0874af8467aa6c2d74af5477810e5c529 0o100644 hoge.txt 2262de0c121f22df8e78f5a37d6e114fd322c0b0 >>> ls_obj() 6857e44f33ad9d9a1b5971aab5fc4afdc26aaebb 573085877a591c7adffd937ef83004757ad9b2c1 3d714ec8b91b36cf751362dc57094578cb8772f6 5a26fc77e7f35868c5db48ad493ab5fe59605a20 5f7229d0ceddcc977331db217f66dfcfed0da6ac 9daeafb9864cf43055ae93beb0afd6c7d144bfa4 ee22373afdf41480021030a7cce0b1b277cf23cb c936e61de32da173b7df6221fe72a9525dcb1a2e 20972f6e8cc05b659c81ab48ccaa2c0d089920ba 45f81de3b8e663788264c54dff4802c2609dfd5f 6e2245cfa722e995b72b48e7ec8def3c2f730a25 6427d3b0874af8467aa6c2d74af5477810e5c529 cdb6165514fe83fc41ce1d3f63289aee774765a9 e6c4d2fa76fb4540abd7ead67884e1a0f79d6319 24419734f0f9d1b2ac8e01685b35323da44315e6 2262de0c121f22df8e78f5a37d6e114fd322c0b0
とindexは変わっていませんが、45f81de3b8e663788264c54dff4802c2609dfd5fおよび6e2245cfa722e995b72b48e7ec8def3c2f730a25という新しいオブジェクトができていますね。これらの中身を確認してみると
>>> cat_obj("45f81de3b8e663788264c54dff4802c2609dfd5f")
type:commit
tree 6e2245cfa722e995b72b48e7ec8def3c2f730a25
parent 5a26fc77e7f35868c5db48ad493ab5fe59605a20
author ******
committer ******
hogeを追加してみた
>>> cat_obj("6e2245cfa722e995b72b48e7ec8def3c2f730a25")
type:tree
100644 .gitignore c936e61de32da173b7df6221fe72a9525dcb1a2e
100644 ccsgit.py 6427d3b0874af8467aa6c2d74af5477810e5c529
100644 hoge.txt 2262de0c121f22df8e78f5a37d6e114fd322c0b0
とCommitオブジェクトとTreeオブジェクトであることがわかりました。
以上でaddやcommitしたときの動作が見えてきたのではないでしょうか?
まとめ
今回はGitの内部構造を見るプログラムを実装しました。Gitリポジトリを操作し、作成したプログラムを利用することで各種操作とファイルの内容の対応をみることができました。これにより普段からGitで何を操作しているのかの理解が深まりました。なにをしているのかが見えてくるのでGitの操作でより応用が効くようになることが期待されます。今回実装していないものもまだまだありますので実装すると楽しいかもしれません。
明日の記事はとっちーのUnityの音の扱いに関する記事です。
