Git: Compute a tree id

Compute the id Git gives a directory, as git write-tree does.

What to build

A program that computes the Git tree id of a flat directory of text files.

Requirements

  • Every file is a regular file (mode 100644) whose content is its text followed by a newline. A tree entry is 100644 NAME\0 followed by the 20-byte (binary) blob id; entries are sorted by name in byte order; the tree id is SHA-1 of tree <size>\0 followed by the entries.
  • Print the 40-digit tree id.

Input

Line 1: n. Then n lines: a file name, a space, and the file's text (which may contain spaces).

Output

One line.

Constraints

n ≤ 100; names are unique ASCII without spaces or slashes.

Example

Input:

2
a.txt hello
b.txt world

Output:

18eb80fbbbf9160491c007668d5298f1e86cd40a

Why it works

A tree lists names next to the ids of their contents, so its own id fingerprints the whole directory: change any file and the tree id changes too.

Examples

Example 1 · Input
2
a.txt hello
b.txt world
Expected output
18eb80fbbbf9160491c007668d5298f1e86cd40a
Example 2 · Input
1
README.md # Notes
Expected output
dea27f15582084abf07db303c2309878ef4f595c

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Each entry is b"100644 " + name + b"\0" + the 20 raw bytes of the blob id (bytes.fromhex).

Hint 2

Sort the entries by name as bytes, join them, and hash b"tree " + length + b"\0" + entries.

Solution

Show one correct solution (try it yourself first)
import hashlib


def object_id(kind, data):
    return hashlib.sha1(kind + b" " + str(len(data)).encode() + b"\0" + data)


files = []
for _ in range(int(input())):
    name, text = input().split(" ", 1)
    files.append((name.encode(), (text + "\n").encode()))
entries = b""
for name, content in sorted(files):
    entries += b"100644 " + name + b"\0" + object_id(b"blob", content).digest()
print(object_id(b"tree", entries).hexdigest())

Lesson: Inside Git: objects and hashes →