treeオブジェクト — ディレクトリ構造をどう表すかのサンプルコード — Gitの内部構造から理解する

1実際のリポジトリのtreeを覗く

README.md と src/index.js だけの小さなリポジトリで、ルートのtreeを表示した実際の出力です。ファイルは blob、ディレクトリは tree として並んでいます。ファイル名がここで初めて登場する点に注目してください。

# 最新コミットが指すルートtreeを表示する
$ git cat-file -p HEAD^{tree}
100644 blob 058ac035da0ee55124820835a80687441880d04b	README.md
040000 tree 7022c258ebb3ee9cab60b56bc770cc9a5997104f	src

# src ディレクトリのtreeをさらに辿る
$ git cat-file -p 7022c258ebb3ee9cab60b56bc770cc9a5997104f
100644 blob bf6b8179632b5711ffa21a9869186fae9199d99c	index.js

# 葉のblobまで辿り着くと、中身が出てくる
$ git cat-file -p bf6b8179632b5711ffa21a9869186fae9199d99c
console.log("Hello");

# tree → tree → blob と辿れる。これがディレクトリ階層の実体

2treeを木構造として辿ってみる

実際のリポジトリのtreeをデータとして再現し、再帰的に辿ってファイル一覧を復元します。「ある時点のディレクトリ全体」がtreeから完全に決まる、という感覚をつかむためのサンプルです。

Python

# 実機のgitから取ってきた、あるコミット時点のオブジェクト
objects = {
    "b4b9a853": ("tree", [
        ("100644", "blob", "058ac035", "README.md"),
        ("040000", "tree", "7022c258", "src"),
    ]),
    "7022c258": ("tree", [
        ("100644", "blob", "bf6b8179", "index.js"),
    ]),
    "058ac035": ("blob", "# 社内ツール\n"),
    "bf6b8179": ("blob", 'console.log("Hello");\n'),
}

def walk(tree_hash, prefix=""):
    kind, entries = objects[tree_hash]
    for mode, etype, ehash, name in entries:
        path = f"{prefix}{name}"
        if etype == "tree":
            print(f"[dir ] {path}/")
            walk(ehash, prefix=f"{path}/")
        else:
            content = objects[ehash][1]
            print(f"[file] {path:20} {ehash}  {content!r}")

print("ルートtree b4b9a853 を展開:")
walk("b4b9a853")
print("\n→ tree1つで、その時点のディレクトリ全体が決まる")

3変えていないディレクトリは使い回される(実機での証明)

README.md だけを編集して2回目のコミットをしました。ルートtreeのハッシュは変わりますが、触っていない src の tree は1回目と全く同じハッシュのままです。これが「変更に関係する部分しか増えない」の実例です。

# 1回目のコミットのルートtree
$ git cat-file -p 3a72bb1^{tree}
100644 blob 058ac035da0ee55124820835a80687441880d04b	README.md
040000 tree 7022c258ebb3ee9cab60b56bc770cc9a5997104f	src

# README.md だけ編集して2回目をコミット
$ git cat-file -p dd2818b^{tree}
100644 blob 4afe36f627e0582eed8581aca4414a6e7e522b37	README.md   ← 変わった
040000 tree 7022c258ebb3ee9cab60b56bc770cc9a5997104f	src         ← 同じ!

# src を一度も触っていないので、そのtreeは共有される
# 2コミットあってもオブジェクトの総数はたったの8個
$ git rev-list --objects --all | wc -l
8

4「毎回全部コピー」と何が違うのか

スナップショットと聞くと毎回まるごと複製する印象を持ちますが、実際に増えるのは変更したファイルから根までの経路だけです。深い階層で1ファイルだけ直したときの増加量を数えて比べます。

Python

# src/components/button/index.js だけを1文字直した場合
all_files = 500       # リポジトリ全体のファイル数
changed_files = 1     # 実際に変えたファイル
depth = 3             # src / components / button の3階層

naive = all_files                       # 全部コピーする方式
git = changed_files + depth + 1         # 変更blob + 経路上のtree + ルートtree

print(f"全部コピーする方式 : {naive} オブジェクト")
print(f"Gitの方式          : {git} オブジェクト")
print(f"                     (blob 1 + 経路のtree {depth} + ルートtree 1)")
print()
print("変えていない499ファイルと、無関係なディレクトリのtreeは")
print("前のコミットのものをそのまま指すだけ。だからコミットは軽い")

5treeのハッシュも中身から決まる

treeもblobと同じで、エントリを並べたバイト列から機械的にIDが決まります。だから中のファイルが1つでも変われば、そのtreeのハッシュも必ず変わります。実際のGitのバイト形式で計算して確かめます。

Python

import hashlib

def tree_id(entries):
    """entries: [(mode, name, 40桁のhash)] からtreeのIDを計算"""
    body = b""
    # gitはエントリを名前順に並べる
    for mode, name, hexhash in sorted(entries, key=lambda e: e[1]):
        body += f"{mode} {name}".encode() + b"\x00" + bytes.fromhex(hexhash)
    header = f"tree {len(body)}".encode() + b"\x00"
    return hashlib.sha1(header + body).hexdigest()

# src/ ディレクトリ(index.js だけが入っている)
src = [
    ("100644", "index.js", "bf6b8179632b5711ffa21a9869186fae9199d99c"),
]
print("src の tree :", tree_id(src))
print("実機のgit   : 7022c258ebb3ee9cab60b56bc770cc9a5997104f")
print("→ 一致する")

print("\n中のファイルを1つ差し替えると:")
changed = [
    ("100644", "index.js", "0000000000000000000000000000000000000001"),
]
print("  ", tree_id(changed), "(全く別のtreeになる)")

サンプルコードで身につける: treeオブジェクト — ディレクトリ構造をどう表すか

1実際のリポジトリのtreeを覗く

2treeを木構造として辿ってみる

3変えていないディレクトリは使い回される(実機での証明)

4「毎回全部コピー」と何が違うのか

5treeのハッシュも中身から決まる