GitをPythonで自作した

# はじめに

Gitの内部構造を勉強した時に、自分でも実装したくなったのでPythonを使って再現してみました。


https://qiita.com/akstn23456/items/dfbb09410c88853a5857

# 実装する機能

実装する機能は以下の通り

- git add
- git commit
- git branch
- git checkout
- git log

# ディレクトリ構成

ディレクトリ構成は以下のとおり

```
.
├─ git
│   ├─ HEAD
│   ├─ index.pkl
│   ├─ object
│   └─ refs
│       └─ heads
│            └─ master
└─ src
    └─ *.py
```

- git ：ファイル管理を行う上で使用するファイルを保存するディレクトリ（.gitに該当）
    - HEAD：現在作業しているcommitオブジェクトを表すファイル
    - index.pkl：ステージングしたファイルの情報を表すファイル
    - object：gitオブジェクトを管理するディレクトリ
    - refs：ブランチとタグの管理を行うディレクトリ
        - heads：ブランチの管理を行うディレクトリ
            - master：masterブランチの参照先を表すファイル
- src：gitを実装するPythonファイルを置くディレクトリ

# 実装

## git add

`git add`を実行した時に以下の流れが実行されるようにする

1. 指定されたファイルのblobオブジェクトの生成
2. indexファイルの更新

### blobオブジェクトの生成

まず指定したファイルに書かれている内容を読み込み、ヘッダーをつけ、blobオブジェクトの中身を作る。

```python
with open(filepath, "w") as f:
    file_content = f.read()

blob_content = f"blob {len(file_content)}\0{file_content}"
```

その後、中身をSHA-1チェックサムしたものと、zlibで圧縮したものを用意し、それぞれをオブジェクトファイル名とオブジェクトファイルの中身にして、`object/heads` 以下に保存する。

```python
def make_object(object_content):
    encode_content = object_content.encode()
    comp_object = zlib.compress(encode_content, level=1) # zlibで圧縮
		
    h = hashlib.new("sha1")
    h.update(encode_content)
    object_hash = h.hexdigest() # SHA-1チェックサム

    return object_hash, comp_object

def save_object(object_hash, any_object):
    path = os.path.join("git", "object", "heads")
    object_path = os.path.join(path, object_hash[:2], object_hash[2:])

    with open(object_path, "wb") as f:
        f.write(any_object)

blob_hash, blob_object = make_object(blob_content)
save_object(blob_hash, blob_object)
```

### indexファイルの更新

対象のファイルの情報を更新する。実際のindexファイルはファイルのパーミッションや種類、フラッグなどの情報を保持したバイナリファイルだが、今回は簡単のためファイル名とblobハッシュのみを保持する、pickleファイルとした。

```python
with open(index_path, "wb") as f:
    index_dict = pickle.load(f)

index_dict[filename] = blob_hash

with open(index_path, "rb") as f:
    pickle.dump(index_dict, f)
```

## git commit

`git commit`を実行した時に以下の流れが実行されるようにする

1. indexファイルからtreeオブジェクトの生成
2. commitオブジェクトの生成
3. HEADの更新

### treeオブジェクトの生成

indexファイルを基にステージングされたファイルのtreeオブジェクトを生成する。
作業ディレクトリと同階層にファイルがある場合と、作業ディレクトリの直下にファイルがない場合で行う作業が異なる。

例として以下のディレクトリ構成を考える。

```python
.
├─ hoge.txt
└─ foo
    └─ bar.txt
```

以上のファイルをaddするときのコマンドは、`git add hoge.txt foo/bar.txt`となる。

この時、トップレベルのtreeオブジェクトに含まれる情報は、hoge.txtのファイル名(hoge.txt)とblobオブジェクトのハッシュ、fooのディレクトリ名(foo)とfooのtreeオブジェクトのハッシュである。

そのため、トップレベルのtreeオブジェクトを生成するまえに、fooのtreeオブジェクトを生成する必要がある。
なお、fooのtreeオブジェクトにはbar.txtのファイル名とblobオブジェクトのハッシュが含まれる。（bar.txtのblobオブジェクトは`git add foo/bar.txt`時に生成されたもの）

以下の関数でそれを実装できる。

```python
def make_tree_object(index):
    already_check_dir = []
    tree_content = ""
    for filename in index:
        if "/" in filename: # 下の階層がある場合
            dirname = filename.split("/")[0]
            if dirname in already_check_dir:
                break
            child_path = filename[len(dirname)+1:]
            child_index = {child_path: index[filename]}

            for name in index: # 他に同ディレクトリ下のファイルがある場合
                if name == filename: continue
                if name.startswith(dirname + "/"):
                    child_path = name[len(dirname)+1:] # "dirname/"以下のpathを取得
                    hash_tmp = index[name]
                    child_index[child_path] = hash_tmp
            
            tree_hash = make_tree_object(child_index)
            tree_content += f"\0{tree_hash} {dirname}"
            
            already_check_dir.append(dirname)

        else:
            blob_hash = index[filename]
            tree_content += f"\0{blob_hash} {filename}"
    
    header = f"tree {len(tree_content)}"
    tree = header + tree_content
    tree_hash, tree_object = make_object(tree)

    save_object(tree_hash, tree_object)
    return tree_hash
```

この関数にindex.pklに記述されている情報をいれると、返り値としてトップレベルのtreeオブジェクトのhashが返ってくる。

### commitオブジェクトの生成

生成したトップレベルのtreeオブジェクトをもとにcommitオブジェクトを生成する。
なお、生成するcommitオブジェクトに親commitオブジェクトがある場合は、そのハッシュもオブジェクトに付け加える。（最初のコミット以外は親コミットが存在する）

```python
toptree_hash = make_tree_object(index_dict)
commit_content = f"tree {toptree_hash}\n" #トップレベルのtreeオブジェクトのハッシュ

parent_hash = fetch_head_commit_hash() #HEADが参照しているcommitオブジェクトがあればそのハッシュをとってくる
if len(parent_hash) > 0:
    commit_content += f"parent {parent_hash}\n"

commit_content += f"\n{commit_message}\n" #コミットメッセージ

header = f"commit {len(commit_content)}\0" #ヘッダー

commit_hash, commit_object = make_object(header + commit_content)
save_object(commit_hash, commit_object)
```

### HEADの更新

最後にHEADの参照するcommitオブジェクトを更新する。
detached HEAD状態の場合は、HEADファイルに直接commitオブジェクトのハッシュが記述されており、そうでない場合は現在のブランチのブランチファイルへの参照先が記述されている。

HEADファイルにハッシュが書かれている場合は、HEADファイルを新しいハッシュに更新。
HEADファイルに参照先が書かれている場合は、参照先のブランチファイルを新しいハッシュに更新する。

なお、参照先が書かれている場合は、HEADファイルの先頭に`refs:`という文字列が必ず記述されているため、これを基に判断を行う。

```python
with open(os.path.join("git", "HEAD"), "r") as f:
    head = f.read()
  
if head.startswith("refs:"):
    dirpath = os.path.join("git", head.split()[1])
else:
    dirpath = os.path.join("git", "HEAD")

with open(dirpath, "w") as f:
    f.write(commit_hash)
```

## git branch

ブランチを生成する時は、指定されたブランチ名のブランチファイルを作成するだけである。
ブランチファイルにはその時のHEADが参照しているcommitオブジェクトのハッシュを記述する。

```python
head_hash = fetch_head_commit_hash() #HEADに書かれているハッシュor参照先のブランチファイルに書かれているハッシュ

path = os.path.join("git", "refs", "heads", branch_name)
with open(path, "w") as f:
    f.write(commit_hash)
```

## git checkout

`git checkout`を実行した時に以下の流れが実行されるようにする

1. 該当するcommitオブジェクトのハッシュを取得
2. HEADの参照先の変更
3. commitオブジェクトをもとに管理しているファイルの情報を変更
4. indexの更新

### commitオブジェクトのハッシュを取得

`git checkout` ブランチ名もしくは直接commitオブジェクトのハッシュを指定することができる。
ブランチ名が指定された場合はブランチファイルに記述されたハッシュを取りに行くことで、該当するcommitオブジェクトのハッシュを得ることができる。

### HEADの参照先変更

チェックアウト先にブランチ名が指定された場合は、HEADの参照先を指定されたブランチファイルに変更する。

```python
with open(head_path, "w") as f:
    header = "refs: "
    content = header + branch_path
    f.write(content)
```

commitオブジェクトのハッシュが指定された場合は、そのハッシュに変更する。

```python
with open(head_path, "w") as f:
    f.write(commit_hash)
```

### 管理しているファイルの情報を更新

管理しているファイルの情報を更新するためには、commitオブジェクトが保持しているtreeオブジェクトを展開し、各ファイルのblobオブジェクトを取得することが必要である。

```python
def deployment_tree(object_hash, filename, blob_objects_array):
    separete_content = fetch_object(object_hash).split("\0") #fetch_object()でzlibを解凍、デコードをおこなってオブジェクトを文字列に直している

    if "blob" in separete_content[0]: #separate_content[0]は各オブジェクトのヘッダー
        content = fetch_object(object_hash).split("\0")[-1]
        blob_objects_array.append([filename, object_hash, content])
        return blob_objects_array
    else:
        for content in separete_content[1:]: #separate_content[1:]は各オブジェクトの中身
            try:
                tmp_hash = content.split()[0]
                tmp_name = os.path.join(filename, content.split()[1])
            except:
                return blob_objects_array
            blob_objects_array = deployment_tree(tmp_hash, tmp_name, blob_objects_array)
        return blob_objects_array

blob_objects_array = deployment_tree(toptree_hash, "", [])
```

以上のコードを実行すると、該当するblob_objects_arrayにコミットされたすべてのファイルのファイル名、blobオブジェクトのハッシュ、ファイルの中身が格納される。

その後、すべてのファイルの中身を取得したものに変更する。

```python
for blob_object in blob_objects_array:
		file_path = blob_object[0]
    blob_content = blob_object[2]
    with open(file_path, "w") as f:
        f.write(blob_content)
```

### indexの更新

indexの更新をしないと、チェックアウト前のブランチでステージングした記録が残ってしまう。そうなると、チェックアウト後のブランチで、あるファイルをステージングせずにコミットを行った場合、そのファイルの中身がチェックアウト前のblobオブジェクトを参照することになってしまい、意図した挙動とならない。

更新するindexの情報は、チェックアウトしたcommitオブジェクトから取得する。
ファイルの情報を更新したときと同じように、トップレベルのtreeオブジェクトを展開し、各ファイルのblobオブジェクトをindexに登録する。

```python
blob_objects_array = deployment_tree(top_tree_hash, "", [])

for blob_object in blob_objects_array:
		file_name = blob_object[0]
    blob_hash = blob_object[1]
		index_dict[filename] = blob_hash

with open(index_path, "wb") as f:
    pickle.dump(index_dict, f)
```

## git log

`git log`は現在参照しているcommitオブジェクトからたどれるすべてのcommitオブジェクトを表示するコマンドである。

やることは、commitオブジェクトの`parent`に書いてあるcommitオブジェクトをたどっていき、`parent`が書かれていない、すなわち最初のcommitオブジェクトにあたるまで、表示を続けることだけ。

```python
def print_commit_log(commit_hash):
    commit_object = fetch_object(commit_hash)
    _, content = commit_object.split("\0")
    print_message = f"commit {commit_hash}"
    print_message += f"\n{content}"
    print(print_message)

    if "parent" in content:
        parent = content.split("\n")[1]
        parent_hash = parent.split()[-1]
        print_commit_log(parent_hash)
```

## まとめ

さいごに実装した機能を呼び出す際のコマンドを、実際のgitによせる。

```python
if __name__ == "__main__":
    args = sys.argv
    
    if command == "add":
        try:
            argument = args[2]
        except:
            print("add command require the filename")
            sys.exit()
        add_file(argument) # git addの実行
        print(f"add {argument}")

    elif command == "commit":
        try:
            argument = args[2]
        except:
            print("you need set the commit message")
            sys.exit()
        commit(argument) # git commitの実行

    elif command == "branch":
        try:
            argument = args[2]
            make_branch(argument)　# git branchの実行
            print(f"create {argument}")
        except:
            print_branch_name() # ブランチ名が指定されていない時はすべてのブランチ名を表示

    elif command == "checkout":
        try:
            argument = args[2]
        except:
            print("you need set the branch name")
            sys.exit()
        checkout_branch(argument) # git checkout(ブランチ名指定)の実行
        print(f"check out to {argument}")
    
    elif command == "checkout-hash":
        try:
            argument = args[2]
        except:
            print("you need set the commit hash")
            sys.exit()
        checkout_hash(argument) # git checkout(ハッシュ指定)の実行
        print(f"check out to {argument}")

    elif command == "log":
        check_log()

    else:
        print("you type the wrong command")
```

このファイルを`git.py`とすると以下のようなコマンドでそれぞれ実行できる。

- `python src/git.py add hoge.txt`
- `python src/git.py commit`
- `python src/git.py branch feature`
- `python src/git.py checkout master`
- `python src/git.py log`

# さいごに

自分で実装したことで、いままでなんとなくでやってた、gitの操作が明確になった気がします。
心残りとしては、mergeを実装できていないことです。
mergeを実行するのに、diffという機能（？）計算（？）を使う必要があるらしく、それの理解が追いついていないので、とりあえずmergeはおいておきました。
diffについて理解を深めた後にmergeも実装できればなと思っています。