この記事は、P&Dアドベントカレンダー6日目のものです。
皆さんは車輪の再発明に対して、どのような意見をお持ちですか？
あまりいい印象を受けない言葉ですが、実は一部で積極的に行われていることです。
ここでは、私が一部で'gitの人'と呼ばれるきっかけとなった、車輪ならぬ 'gitの再発明' について綴ろうと思います。
タイトル通り、今回再発明したgitはgitで管理されているため、GitHubからご覧になれます。
この記事では、gitを実装していた中で面白かった実装部分の話をします。
注意
- 部分的に本家のgitと挙動が一致しない箇所があるかもしれません。
- 以降、gitは本家のものを指し、eat(easy-git)は今回再発明したgitを指すことにします。
環境
OS: macOS(10.13.1)
言語: C++
エディタ: Xcode
コンパイラ: Mac標準
テスト環境: zsh(iTerm2上)
デフォルトのターミナルだとログの表示などが異なるかもしれません。
最初の課題
普段、みなさんは何気なく、
$ git add .
$ git commit -m "example commit"
とか、
$ git commit -am "fix many-many bugs"
とコマンドを叩いていると思いますが、add による挙動を意識したことはありますか？
このとき、ステージングという処理が中で実行されています。
ステージングでは、addしたファイルの情報をリポジトリ内にコピーします(ここではコピーだけ)。次に、commit すれば、コピーした情報をコミットツリーと呼ばれる木構造に加えます。
つまり、1段階踏んでから変更を保存(反映)しているので、addしてプログラム内で作った木構造をcommitするまで保存&復元する必要がでてきます。このgitの処理を再現しようとすると、シリアライズとデシリアライズという単語が頭に浮かびますが、バージョン管理システムは如何なる環境でも動作しなければなりません。環境依存が起きる可能性がある実装はよくありません。C++で実装していくなかでデシリアライズできない問題が起こりうるのかは定かではありませんが、確実性の高い方法をとるべきです。最終的に、フォーマットを決めてファイルに書き出すようにしました。
書き出したステージング内容は以下のようになっています。
./dir 8fd2094070b515a8475b5b1a7e5fad3a7243cc8d
./dir/file3 b9370c78bb825938731c633e6ae19d0a878486d4
./file1 9e293468bd5adcfbce75a929c0b2e994aab994c4
./file2 f80275f25936f6b39b3c1a1457e16370ed045ff6
フォーマットは<相対パス> <ハッシュ値>です(ハッシュ値については次のトピック、名前の唯一性を参照)。
このデータに対応するパーサを作り、コミットツリーを復元するようにしました。
これがgitを再発明する上での最初の課題でした。
名前の唯一性
あるプロジェクトにおいて、initial.txt というファイルがコミットされている状態で initial.txt を変更しました。
リポジトリ内に保存したいですが、同じ名前 initial.txt で保存してしまうと、過去のデータが消えてしまいます(バージョン管理出来ないシステム)。
ならばと思い、initial.txt_2 とインデックスを付加するようにしてみました。開発が進むにつれ、変更されていない initial.txt が何度もコミットされました。コミットの度にインデックス付きのファイルを保存していては、内容が全く同じなのに違う名前のファイルが大量生成されます。これではもはや、プロジェクトを圧縮ファイルにして大事に保管してあるのと同じです。これを解決する方法は、ハッシュを利用することです。ハッシュは次の特性を持ちます。
- 同じ入力に対しては必ず同じ出力を返す
- 出力される文字列は唯一無二のものである
- 出力される文字列の長さは固定
- 入力の文字列が1文字でも変われば、出力される文字列も変わる
- 逆変換ができない
今回特に注目すべきは上2つの特徴です。eatでは、ファイルの内容が全く変更されていなければ常に同じ文字列(ファイル名)を返してくれる命名器として使用できます。(実際、gitでも命名にハッシュが使われています。)
Macの方は、次のようにしてハッシュ化を試すことができます。
ハッシュの使い方
$ md5 file #=> MD5ハッシュ
$ openssl sha1 file #=> SHA1ハッシュ
ハッシュの特徴を体験してみる
$ echo "test is here" >> file
$ md5 file #=> ba1d4a40ee18411302b7edc96217f69d #長さ32の文字列
$ echo "insert changes" >> file
$ md5 file #=> a28747665faa34a4e1db51ca9317132c #変更によって違うハッシュ値が得られたが、長さは32のまま
(試しに、1文字だけ変更してからハッシュ値を調べてみるといいかもしれません。全く違う文字列が得られます。)
ハッシュを使うことで、変更があったファイルのみを新規にコピー&命名ができる(ファイルが変更されていれば、ハッシュが異なるから変更の検知が可能)ので、必要最低限のコピーで済みます。
今回は余談ですが、ハッシュが持つ最大とも言える特徴は、5つ目の不可逆性です。ハッシュ化してしまえば、元がなんだったのかわからないので、パスワードの保護に使えます。1意に決まる要素(ユーザidなど)とパスワードを連結した文字列のハッシュ値、そしてid自体をセットにしてパスワードが合っているか(idとハッシュ値の組み合わせが同じか)を検証するようにすれば、セキュリティ対策になります。
ただし、上記で用いたMD5、SHA1ハッシュのうち、SHA1はGoogleによって破られてしまったため、セキュリティには使えません。SHA256を使いましょう。
二分木による多分木の実現
さて、木構造が出てきましたが、git / eatが管理するのはディレクトリの状態です。プロジェクトのルートディレクトリには環境を定めるファイル(Gemfile, Cartfile, etc...)や、ソースコードが置いてあるディレクトリが各々複数あるはずです。ディレクトリの下にはさらに複数のファイルやディレクトリがあるはずで、プロジェクト全体で見ると多分木になっています。
これらをどのように探索し、どのように保管するのかを考えなければなりません。
ここで、探索を容易にするためにファイルを blob、ディレクトリを tree と表します(これは本家の命名に従っています)。
トップの親から走査し、ファイルなら次の子へ、ディレクトリなら孫に...と繰り返します。再帰がわかっていれば、これは特に難しい話ではありません。子をリストとして持てば問題なさそうですが、今回はちょっとこだわって、二分木でこの多分木を再現してみました。
二分木のleftとrightは、子と兄弟に対応します。また、treeのみ子を持つ可能性があります。このようにしてやると、二分木でも多分木を表現できてしまいます。
こちらが参考になると思います。
実装しない人にはどうでもいい話かもしれないですが、深さ優先探索じゃないとスマートに実装できないです。考えてみる面白いかもですね。
Usage
めちゃくちゃ暇で暇で仕方ないから遊んでやるよって人は、brew tapでインストールできるようにしたので遊んでみてください。使える機能とか完全じゃないので、実際の開発には使わない方がいいと思いますが、遊ぶくらいなら十分な気がします。
$ brew tap arabian9ts/easy-git
$ brew install arabian9ts/easy-git/eat
遊び方
$ eat init
$ touch file
$ eat add .
$ eat commit
$ eat branch qiita
$ eat checkout qiita
$ eat reset
これくらいのことができます。おもちゃにしてやってください。
最後に
ここに書いたのは再発明の中で手にした技術と知識の断片ですが、どれも自分には刺激的で楽しかったです。
普段ゴリゴリ再帰書いたりデータ構造とアルゴリズムを意識したりする場面が少ない人ほど、車輪の再発明はやってみるべきだと思いました。
根底にある技術に目を向け、それを再現しようとすることで、また違った問題が見えてきます。
多角的に問題を見ることになるので、思ったよりも多くのことを学べる良い機会になりました。
あと、何より話のネタになりました 笑