Rustでmini-gitを作った話

こんにちは、21Bのmehm8128です。
ついに今年も授業が始まってしまいました。
今回は風邪と戦いながら冬休みにやっていたことを書きます。

git作った

1年前にこんな記事を出していました。

このときはgoで書いていたのですが、gitの仕様をちゃんと理解できていなくてgit addは最低限動作するようには作れたのですが、git commitは途中で諦めてしまいました。
しかし今回ついにgit commitの実装を完成させることができたので、記事を書いています。

リポジトリはこちらです↓

※前回のブログ記事にgo実装でのリポジトリへのリンクを隠しておいたのですが、今はprivateリポジトリにしてしまったため見れない状態になっています。

Rust信者について

traPにはRust信者が何人かいます。traPのRust信者たちは、隙あらばRustを布教してくるのですが、夏インターンや冬ハッカソンなどでバックエンドの人たちがRustを使っている機会がある度にそろそろ本当に勉強しないとなという気持ちになっていたので、夏とこの冬休みに少しずつ勉強しました。他にも、特に最近だとbiomeがRustで書かれていたことに強く影響を受けて、Rust勉強してcontributeしたいなという気持ちになっていました。

ということで、今回はRustで書きました。
まだまだ理解できていないことが多くて、ファイル分割のしかたがあんまりよく分かってなかったり、Rustの特徴でもある所有権周りや型などの理解が微妙ですが、copilotくんの力も借りながら一旦動く形にはなったのでよしということにしています。

↓部内SNSのtraQでRust信者に隙あらばRustスタンプを使ってRustを布教されている様子
chrome_r5z6b2iry5
chrome_xprxarbtgs
chrome_zqagufzcxj

実装について

技術的な話になるので、動いている動画が見たい方はちょっと下までスクロールしてください。

git add

前回git addがバグっていて、1回目のaddは上手くいくけどcommit後に再度addしたり、一旦stagingから降ろして再度addしたりすると上手くいかないという状態でした。そのため、公式ドキュメントを読んだり、実際のgitコマンドを使って小さいリポジトリでaddなどの操作をしてhexdump -C .git/indexでバイナリを眺めたりしながら、改めて仕様を確認しました。その結果以下のような仕様になりました。

git addしたファイルがindexファイルのentryに追加される
2回目以降は前回addしたものと今回addしたものの両方がindexファイルに載っている状態になる。ただし、同じファイル名のものは最新の方で上書きされる
- ここで、indexファイル内のentryの順序は保たなければならないらしいです。最後の最後にここが間違っていて、ファイルを編集しただけなのに「ファイルが削除され、新しく同じ名前のファイルが作成された」という謎の状態とみなされてしまっていました

前回commit時のindexファイルの中身といい感じにマージしないといけないので、indexファイルの書き込みだけでなく読み込みもしないといけないのが大変でした。
また、本家gitではgit add .で全部addできたりするので、ディレクトリを選択すると再帰的にaddできるようにする機能も入れました。

git commit

前回諦めた部分です。indexファイルからcommitオブジェクトを生成する部分で木の探索をしないといけなくて、仕様の勘違いをしていたのと単純にアルゴリズム力が足りなかったので前回はできなかったのですが、今回は上手くいきました。手順は以下のようになりました。

indexファイルからファイル一覧を取得
1.のファイル一覧を上から順に見ていき、ファイルの木構造を生成する(後述)
2.で作った木構造を左下から見ていき、treeオブジェクトを作り、ルートのtreeオブジェクトhashからcommitオブジェクトを作る
.git/refs/heads/{現在のブランチ}のhash値を最新のcommitオブジェクトのhash値に更新

2.の木構造は以下のようなものにしました。

enum NodeType {
    Blob,
    Tree,
}

struct Node {
    node_type: NodeType,
    mode: u32,
    name: String,
    hash: String,
    children: Vec<Node>,
}

Nodeはファイル(blob)かディレクトリ(tree)を表し、ディレクトリの場合はchildrenにディレクトリ内のファイル・ディレクトリが入っています。

commitオブジェクトを作るにはルートのtreeオブジェクトのhash値が必要で、treeオブジェクトを作るにはそのディレクトリ内の全てのファイル・ディレクトリのblobオブジェクト・treeオブジェクトのhash値が必要で...となっているので、最終的に末端の葉ノードであるファイルのblobオブジェクトのhash値が必要になります。なので、木構造を左下から見ていくことで、下から順に深さ優先探索的にhash値を求めていき、最終的に一番上まで求めていくと上手くいきます。ただし、blobオブジェクトのhash値は2.で木構造を作った段階で得られているので(もっと言うとgit addでindexファイルを作成した段階でhash値は全て保存してあります)、今回はtreeオブジェクトのhash値を求めているだけです。

一番苦戦したのは、作成したtreeオブジェクトがcat-file -p {tree オブジェクトのhash}したときに上手く表示されず、fatal: too-short tree objectというエラーになってしまったことです。gitの実装を見てみたらエラーが出る部分は分かったのですが、Cが読めないこともあって原因がよく分かりませんでした。おそらく作ったtreeオブジェクトのフォーマットに問題があるのだと思ったのですが、公式ドキュメントを読んでも問題ないように思えて分かりませんでした。結局いくつかのブログ記事や他の人の実装などを読んで、

{mode} {pathname}\0{hash}

という形式であることが分かりました(結果的にバグってた実装よりも中身は短くなったのでtoo-short tree objectというエラーは適切でない気がしますが...)。僕は最初、cat-file -pしたときと同じ順に書き込めば問題ないと思い込んでしまっていたのでバグらせていました(実際そのように実装していた記事をいくつか見たので...)。また、後から存在を思い出したのですが、Giteaなどでも使われているgitのgoの実装リポジトリがあるのでこれを見ればよかったです。

ということで、無事commitもできるようになりました。

git branch

branch {branch name}でブランチの作成、branch -d {branch name}でブランチの削除、checkout {branch name}でブランチの移動ができるようにしました。

実装自体は特に難しくなくて、.git/refs/heads以下にブランチ名のファイルを作成して中にそのブランチが指す最新のcommit hashを書き込んだらブランチの作成ができます。削除はこのファイルを消すだけです。.git/HEADに現在のブランチを表すものが書き込まれているので、それを編集すればブランチの移動もできました。

下に載せる動画を撮る準備してて気づいたのですが、別ブランチでcommitしてから元のブランチに戻ってくるとstagingされた状態になってしまいますね。indexファイルを最新commitオブジェクトから復元する必要がある気がします。

動画

では実際に操作している動画をご覧ください。

※../target/debug/gitは事前にcargo buildしたものです
※oisu-はtraPでの挨拶です
※補完をそのまま確定していないのは、VSCodeのターミナルでctrl+fすると補完の確定ではなくてターミナル内検索になってしまうためです
※最後の.git内を映し忘れたのですが、こんな感じです↓
code_vhx75jwaue
※git logとgit branchをし忘れたのですがこんな感じです↓
code_uuogvakwy1

今後について

まだ開発は続けたいと思っていて、今のところ以下を予定しています。

テストを増やす
- ほんのちょっとだけ書いてあるので、もうちょっと増やしていけたらなーと思っています
リファクタリング
- やっぱりかなりコードが汚いので、全体的にリファクタリングしたいと思っています
git logやgit branchなど現在の状態を表示するだけのコマンド
- goの実装のときはgit logはあったのですが、現状を表示するだけ(=readのみでwriteをしない)なので今回はまだやってませんでした
コマンドを増やす
- 表示する系の以外にもgit resetやgit cherry-pickなど

他にもつけたい機能があったらつけたりするかもです。

まとめ

楽しかったです。
4Q終了まであと1ヶ月頑張りましょう。