読者です 読者をやめる 読者になる 読者になる

Mercari Engineering Blog

We're the software engineers behind Mercari. Check out our blog to see the tech that powers our marketplace.

Gitのコミットハッシュ値は何を元にどうやって生成されているのか

こんにちは。サーバサイドエンジニアの @DQNEO です。

前回の「Gitのつくりかた」に続いてGitのコアな部分のお話です。

Gitのコミットハッシュ値とは何か

Gitを使っていると必ずコミットハッシュ値というものが出てきます。9e47c22みたいなアレです。 これはある特定のコミットを指し示すIDとして使うことができます。

では質問です。

このコミットハッシュ値は「何を元に」「どうやって」計算されているでしょうか?

「ある特定のコミット」とはそもそも何なのか

この問題を考える前に、まず「コミットとは何か」を明らかにしておきましょう。 コミットというと「コミットする行為」すなわち「動作」のことを想像するかもしれません。 しかしGitの内部構造的観点から言うと、Gitが管理記録しているのはコミット行為の結果生成されたデータの方です。

この「コミットによって生成されたデータ」のことを「コミットオブジェクト」と言います。 Gitはコミットオブジェクトに対して40文字のIDを発行します。 これがコミットハッシュ値です。

$ git clone https://github.com/DQNEO/hello
$ cd hello
$ git log -1
commit 757cd618f38d574238bae4768ff1a1aedfafdb7a
Author: DQNEO <dqneo@example.com>
Date:   Thu Feb 4 21:18:28 2016 +0900

    second commit

上記の例で言うと 757cd618f38d574238bae4768ff1a1aedfafdb7a がコミットハッシュ値です。

コミットオブジェクトを生で見てみる

コミットオブジェクトを生で見たことはあるでしょうか?

git cat-file -pで任意のコミットのコミットオブジェクトを見ることができます。

$ git cat-file -p 757cd618f38d574238bae4768ff1a1aedfafdb7a
tree 05520e3bd0354e823cacf96b244987f235b3c240
parent 2476c4c7bcbf98e444b6851d67036077334502d2
author DQNEO <dqneo@example.com> 1454588308 +0900
committer DQNEO <dqneo@example.com> 1454588308 +0900

second commit

ここに表示されている数行のテキストデータが、ひとつのコミットオブジェクトになります。 注目していただきたいのはコミットオブジェクトはあくまで「数行のテキストデータ」であって、コンテンツ(ソースコードや画像など)の断片などは全く含まれていないということです。 「メタデータ」と言ったほうがわかりやすいかもしれません。

「コミットオブジェクトとはメタデータである」

これは重要なポイントです。 git logと打ったときに一瞬で履歴をさかのぼれるのは、gitがこのような小さいメタデータだけを調べているからです。

コミットオブジェクトの中身

コミットオブジェクトの中身を順に見てみましょう。

  • treeというのはtreeオブジェクトのことで、これはディレクトリツリーに対して割り振られるIDです。 (もうちょっと厳密に言うと、treeオブジェクトは1つ以上のtreeオブジェクトまたはblobオブジェクトを持つツリー構造のデータです)
  • parentというのは親コミットすなわち1個前のコミットのハッシュ値です。Gitのコミットオブジェクトは必ず1つ以上の親コミットを持っており、親を順番にたどっていくことで履歴をさかのぼることができます。
  • authorcommiterは普通同じ人になるのですが、cherry-pickしたりrebaseしたりすると異なる名前になることがあります。
  • 1行空行をはさんでそこから下がコミットメッセージです。

コミットオブジェクトからコミットハッシュ値が算出される

冒頭の質問に戻ると、コミットハッシュ値はこのコミットオブジェクトを入力値として計算されます。

計算式を擬似コードで示すと下記のようになります。

hash = sha1("commit<半角スペース><コミットオブジェクトのバイト数>\0<コミットオブジェクトの中身>")

コミットハッシュ値を自分で計算してみよう!

先ほどの「コミットオブジェクトの中身」をいったん/tmp/commit.txtという名前のテキストファイルに保存します。

tree 05520e3bd0354e823cacf96b244987f235b3c240
parent 2476c4c7bcbf98e444b6851d67036077334502d2
author DQNEO <dqneo@example.com> 1454588308 +0900
committer DQNEO <dqneo@example.com> 1454588308 +0900

second commit

次にバイト数を数えます。

$ wc --bytes /tmp/commit.txt
212 /tmp/commit.txt

では上記の計算式にしたがって計算してみましょう。sha1の計算はLinuxのopensslコマンドを使います。

$ (echo -en "commit 212\0" && cat /tmp/commit.txt) | openssl sha1
(stdin)= 757cd618f38d574238bae4768ff1a1aedfafdb7a

これがコミットハッシュ値です。 さっきgit logで見たときのコミットハッシュ値と全く同一になっていますね。

C言語を使って自前でコミットハッシュ値を計算してみる

opensslコマンドを使えば簡単にできることはわかりましたが、これでは面白くないのでC言語を使って自分で計算してみましょう。

calc_hash.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <openssl/sha.h>
#include <sys/stat.h>

/**
 *   Linus Torvalds
 *
 *   GNU GENERAL PUBLIC LICENSE
 *   Version 2, June 1991 GNU GENERAL PUBLIC LICENSE
 */
char * sha1_to_hex(unsigned char *sha1)
{
    static char buffer[50];
    static const char hex[] = "0123456789abcdef";
    char *buf = buffer;
    int i;

    for (i = 0; i < 20; i++) {
        unsigned int val = *sha1++;
        *buf++ = hex[val >> 4];
        *buf++ = hex[val & 0xf];
    }
    return buffer;
}

void calc_sha1(const char *body, unsigned long len)
{
    char *type = "commit";
    int hdrlen;
    char hdr[256];
    unsigned char sha1[41];
    SHA_CTX c;

    sprintf(hdr, "%s %ld", type, len);
    hdrlen = strlen(hdr) + 1;

    SHA1_Init(&c);
    SHA1_Update(&c, hdr, hdrlen);
    SHA1_Update(&c, body, len);
    SHA1_Final(sha1, &c);

    printf("%s\n", sha1_to_hex(sha1));
}


int main(int argc, char **argv)
{
    FILE *fp;
    char *filename;
    char *content;
    struct stat st;
    unsigned long len;

    filename = argv[1];
    stat(filename, &st);
    len = st.st_size;

    content = malloc(len);

    fp = fopen(filename, "r");
    fread(content, len, 1, fp);
    
    calc_sha1(content, len);
    fclose(fp);
    free(content);
    return 0;
}

(エラー処理は省いています)

sha1_to_hex関数のビット演算のところが若干読みづらいかもしれません。バイナリのsha1を文字列に変換する処理です。 これは自分で考案したわけではなくGitのソースコードからコピペしてきました。

実はこの関数は、Linus Torvalds氏が2005年4月8日にGitの開発をはじめた際の第一コミット(つまり世界初のGitコミット)のときから存在しています。

https://github.com/git/git/commit/e83c5163316f89bfbde7d9ab23ca2e25604af290#diff-f0bb13c0dd1f6ca9159716c0624f0679R37

私が世界で一番好きなコミットです。 胸が熱くなりますね。

ではコンパイルします。

$ gcc -g -Wall -lssl calc_hash.c -o calc_hash

実行してみます。

$ ./calc_hash /tmp/commit.txt
757cd618f38d574238bae4768ff1a1aedfafdb7a

はい、見事にコミットハッシュ値を自分で算出することができました!

まとめ

  • Gitのコミットハッシュ値の計算方法を解説しました
  • 実際に自分でC言語で計算してみると楽しいです
  • Gitの低レイヤ部分はこのようにシンプルに作られています

みなさんもよかったらGitのソースコードをのぞいてみてください。 きっと新しい発見があると思います。

メルカリでは、身近な技術を深掘りするエンジニアを絶賛募集しています!

参考記事