はじめまして。サーバサイドエンジニアの @DQNEO です。

今日はGitのつくりかたをご紹介します。

C言語学習教材としてのGit

Gitと同じものをゼロから作って何の意味があるのか？と思いますよね。
私がこの再発明をやり始めた動機は「C言語を書けるようになりたい」でした。

実際に途中までやってみたところ、

• C言語がチョットデキるようになった
• Gitの内部構造に詳しくなった

というメリットが得られました。

C言語を勉強する題材は、テトリスとかWebサーバとか他にいくらでもあるのですが、Gitを実装してみるのはかなりおすすめです。理由は下記の通りです。

• 内部構造が意外と単純
• (ローカルで動かす分には)ネットワークの知識が不要
• 普段使っているツールで外部仕様がわかっているので、やるべきことが明確

余談ですが、本家Gitのソースコードを参考にしようと思って読んでいたら、Linus Tovalsが書いたコードを目にしてにテンションがあがりました。

Gitのコンテンツ管理の仕組み

誤解を恐れずに言えば、Gitとは一種のコンテンツ管理システムであり、その実体はKVSです。

git checkoutやgit showはKVSからデータを取り出すコマンドで、
git addやgit commitはKVSにデータを保存するコマンドです。

KVSを直接操作する低レイヤなコマンドとして、

• データを取得: git cat-file -p
• データを保存: git hash-object -w

などがあります。

このうち仕組みが最も簡単なのがgit cat-file -pです。
今回はこれを実装してみましょう。

準備

あらかじめgitレポジトリを作ってコンテンツを格納します。
例としてテキストファイルを2つコミットしてみましょう。

• “hello world\n”と書かれたテキストファイル
• 夏目漱石『坊っちゃん』の全文

# レポジトリ作成
$ git init repo
$ cd repo
# hello worldをadd
$ echo "hello world" > helloworld.txt
$ git add helloworld.txt
# 『坊っちゃん』を青空文庫からダウンロードしてadd
$ wget http://www.aozora.gr.jp/cards/000148/files/752_ruby_2438.zip
$ unzip 752_ruby_2438.zip
$ rm 752_ruby_2438.zip
$ git add bocchan.txt
# コミット
$ git commit -m "initial commit"
[master (root-commit) 2b8c1c1] initial commit
2 files changed, 539 insertions(+)
create mode 100644 bocchan.txt
create mode 100644 helloworld.txt

テキストファイルを２つコミットしました。

格納されたコンテンツをgit cat-file -pで取り出す

格納したコンテンツを取り出してみます。
まずコミットオブジェクトの中身をしらべてツリーオブジェクトのhash値を調べます。

$ git cat-file -p HEAD
tree a97f2489fa15982425e3df14dcf7af9947bec21e
author DQNEO <dqneoo@example.com> 1441790109 +0900
committer DQNEO <dqneoo@example.com> 1441790109 +0900

次にツリーオブジェクトの中身をしらべてblobオブジェクトのhash値を調べます。

$ git cat-file -p a97f2489fa15982425e3df14dcf7af9947bec21e
100644 blob a4940ec3db4cd24542203a9447c4259c96294c09    bocchan.txt
100644 blob 3b18e512dba79e4c8300dd08aeb37f8e728b8dad    helloworld.txt

最後にblobオブジェクトの中身を表示します。
これがコンテンツ本体です。

$ git cat-file -p 3b18e512dba79e4c8300dd08aeb37f8e728b8dad
hello world
$ git cat-file -p a4940ec3db4cd24542203a9447c4259c96294c09 | head | nkf -w
坊っちゃん
夏目漱石
-------------------------------------------------------
【テキスト中に現れる記号について】
《》：ルビ
（例）坊《ぼ》っちゃん

KVSからデータを取り出すことができました。

blob objectのデータ構造

さて、gitのコンテンツは”blob object”と呼ばれるzlib圧縮されたファイルになっています。

データ構造の仕様はこのようになっています。

<blob><半角スペース><コンテンツのサイズ><ヌル文字><コンテンツ本体>

例えば”hello world\n” というコンテンツからblob objectを作るとすると、

“hello world\n”のコンテンツの長さは12バイトなので

blob 12\0hello world\n

となります。

コンテンツが巨大な場合も同じで、夏目漱石『坊ちゃん』全文を格納する場合はこうなります

blob 209990\0坊っちゃん\n夏目漱石\n....

git cat-file -p を自分で実装する

では実際に実装してみましょう。

本質的にはzlib解凍して上記フォーマットをパースするだけなので、シンプルです。

git_cat_file-p.c

/**
 * git cat-file -p 相当のことをするコマンド
 *
 * original from http://oku.edu.mie-u.ac.jp/~okumura/compression/comptest.c
 * licensed under http://creativecommons.org/licenses/by/4.0/
 */
#include <stdio.h>
#include <stdlib.h>
#include <zlib.h>
#include <string.h>
#define INBUFSIZ   1024
#define OUTBUFSIZ  1024
int _write_skipping_header(char *outbuf, size_t size, size_t n ,FILE *fout)
{
static int is_header = 1;
int tmp_n = n;
if (is_header) {
while (*outbuf) {outbuf++; tmp_n--;}
fwrite(outbuf, size, tmp_n, fout);
is_header = 0;
return n;
}
return fwrite(outbuf, size, n, fout);
}
void _decompress(FILE *fin, FILE *fout)
{
z_stream z;
char inbuf[INBUFSIZ];
char outbuf[OUTBUFSIZ];
int count, status;
z.zalloc = Z_NULL;
z.zfree = Z_NULL;
z.opaque = Z_NULL;
z.next_in = Z_NULL;
z.avail_in = 0;
if (inflateInit(&z) != Z_OK) {
fprintf(stderr, "inflateInit: %s\n", (z.msg) ? z.msg : "???");
exit(1);
}
z.next_out = (Bytef *)outbuf;
z.avail_out = OUTBUFSIZ;
status = Z_OK;
while (status != Z_STREAM_END) {
if (z.avail_in == 0) {
z.next_in = (Bytef *)inbuf;
z.avail_in = fread(inbuf, 1, INBUFSIZ, fin);
}
status = inflate(&z, Z_NO_FLUSH);
if (status == Z_STREAM_END) break;
if (status != Z_OK) {
fprintf(stderr, "inflate: %s\n", (z.msg) ? z.msg : "???");
exit(1);
}
if (z.avail_out == 0) {
if (_write_skipping_header(outbuf, 1, OUTBUFSIZ, fout) != OUTBUFSIZ) {
fprintf(stderr, "Write error\n");
exit(1);
}
z.next_out = (Bytef *)outbuf;
z.avail_out = OUTBUFSIZ;
}
}
if ((count = OUTBUFSIZ - z.avail_out) != 0) {
if (_write_skipping_header(outbuf, 1, count, fout) != count) {
fprintf(stderr, "Write error\n");
exit(1);
}
}
if (inflateEnd(&z) != Z_OK) {
fprintf(stderr, "inflateEnd: %s\n", (z.msg) ? z.msg : "???");
exit(1);
}
}
void usage()
{
fprintf(stderr, "Usage:\n");
fprintf(stderr, "  git_cat_file-p blob_file\n");
}
int main(int argc, char *argv[])
{
FILE *fin;
if (argc == 1) {
usage();
exit(0);
}
if ((fin = fopen(argv[1], "r")) == NULL) {
fprintf(stderr, "Can't open %s\n", argv[1]);
exit(1);
}
_decompress(fin, stdout);
return 0;
}

zlib解凍する部分がちょっと難解ですが、これは自分で書いたわけではなく三重大学の奥村教授が公開されていたサンプルコード
をコピペしてきただけです。(奥村先生ありがとうございます！)

ではコンパイルして実行してみます。

$ gcc -g -Wall -O0 -std=c99 -lz -o git_cat_file-p  git_cat_file-p.c
$  ./git_cat_file-p .git/objects/3b/18e512dba79e4c8300dd08aeb37f8e728b8dad
hello world
$  ./git_cat_file-p .git/objects/a4/940ec3db4cd24542203a9447c4259c96294c09 | head | nkf -w
坊っちゃん
夏目漱石
-------------------------------------------------------
【テキスト中に現れる記号について】
《》：ルビ
（例）坊《ぼ》っちゃん

git cat-file -pと同じもの*1ができました！！

こんな感じでGitのサブコマンドをつくることができます。*2

ここでやったのは「解凍」ですが、これを逆にして「圧縮」を実装すれば git add (のコアの部分)をつくることができます。

YAPC::AsiaでのLT資料

参考資料

• Gitが連想配列記憶装置であることを低レイヤーな操作を通して体感しよう！
• 実践 Git – 低レベルに知る Git
• Git をボトムアップから理解する
• Gitの内側 – Gitオブジェクト
• サブコマンド一覧
• gitcore-tutorial(7)
• gitのソースコードを読む – より良い環境を求めて
• ファイルシステムとしての Git – 言語ゲーム

まとめ

Gitのサブコマンドをひとつ実装することができました。

Gitを作ってみるとC言語の勉強になるしGitの内部構造にも詳しくなれます。
興味があればぜひチャレンジしてみてください！