こんにちは、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を布教されている様子
実装について
技術的な話になるので、動いている動画が見たい方はちょっと下までスクロールしてください。
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
内を映し忘れたのですが、こんな感じです↓
※git log
とgit branch
をし忘れたのですがこんな感じです↓
今後について
まだ開発は続けたいと思っていて、今のところ以下を予定しています。
- テストを増やす
- ほんのちょっとだけ書いてあるので、もうちょっと増やしていけたらなーと思っています
- リファクタリング
- やっぱりかなりコードが汚いので、全体的にリファクタリングしたいと思っています
git log
やgit branch
など現在の状態を表示するだけのコマンド- goの実装のときは
git log
はあったのですが、現状を表示するだけ(=readのみでwriteをしない)なので今回はまだやってませんでした
- goの実装のときは
- コマンドを増やす
- 表示する系の以外にも
git reset
やgit cherry-pick
など
- 表示する系の以外にも
他にもつけたい機能があったらつけたりするかもです。
まとめ
楽しかったです。
4Q終了まであと1ヶ月頑張りましょう。