feature image

2024年1月6日 | ブログ記事

Rustでmini-gitを作った話

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

git作った

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

Gitを作ってみようとした話
この記事は新歓ブログリレー2023の50日目の記事です。 こんにちは、SysAd班21Bのmehm8128です。 今回はタイトルにもあるように、Gitを自作してみようとした話をしようと思います。 Gitとは? 新入生の皆さんはGitが何なのかを知らない人が多いと思うので、軽く説明します。 Gitは分散型バージョン管理システムで、プログラムのソースコードを管理・共有するために使います。 例えば新しい機能を追加したときに、別の場所でバグが発生してしまったとします。そのとき、バージョン管理をしていなければ機能追加前のコードに戻せなくなってしまいますが、Gitを使えば機能を追加する前の状態で保存してあれば、元に戻ってどこからバグが発生してしまったのかを調査することができます(GitHubというサービスを利用すれば見やすく確認することができます)。 今回はそのバージョン管理システムであるGitの内部の仕組みに軽く触れてみて、一部の機能を自作してみたり自作しようとしてみたりしたので、紹介しようと思います。ただし、実装の仕方の紹介はほとんどせずに僕が理解している範囲で内部の仕組

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

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

GitHub - mehm8128/mini-git
Contribute to mehm8128/mini-git development by creating an account on GitHub.

※前回のブログ記事に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でバイナリを眺めたりしながら、改めて仕様を確認しました。その結果以下のような仕様になりました。

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

git commit

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

  1. indexファイルからファイル一覧を取得
  2. 1.のファイル一覧を上から順に見ていき、ファイルの木構造を生成する(後述)
  3. 2.で作った木構造を左下から見ていき、treeオブジェクトを作り、ルートのtreeオブジェクトhashからcommitオブジェクトを作る
  4. .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 addindexファイルを作成した段階で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 loggit branchをし忘れたのですがこんな感じです↓
code_uuogvakwy1

今後について

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

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

まとめ

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

mehm8128 icon
この記事を書いた人
mehm8128

21BJC。SysAd班で色々やってます

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2023年4月27日
Vulkanのデバイスドライバを自作してみた
kegra icon kegra
2022年9月26日
競プロしかシラン人間が web アプリ QK Judge を作った話
tqk icon tqk
2023年12月25日
オレオレRustプロジェクトテンプレート
H1rono_K icon H1rono_K
2023年12月22日
rust-toolchain.tomlを書こう
H1rono_K icon H1rono_K
2017年12月26日
RustでMCMC(Metropolis-Hasting)
David icon David
2023年4月27日
Gitを作ってみようとした話
mehm8128 icon mehm8128
記事一覧 タグ一覧 Google アナリティクスについて