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\0followed by the 20-byte (binary) blob id; entries are sorted by name in byte order; the tree id is SHA-1 oftree <size>\0followed 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())