MediumRepository SystemsPython 3
Repository Hash Tree
Build a deterministic repository hash tree that updates parent directories after file writes and deletes.
45m3 sample tests7 hidden tests
A repository snapshot needs one stable fingerprint that incorporates all of its files. Adding those same files in a different order should leave the root digest unchanged.
Implement RepoHashTree, an in-memory Merkle-style hash tree.
Requirements
set_file(path, content)stores or replaces one file.delete_path(path)removes a file or directory and returns whether anything was deleted.root_hash()returns a deterministic hash for the whole tree.- File order must not change the root hash.
- Directory hashes must depend on sorted child names, child types, and child hashes.
- Reject empty paths,
..traversal, and file/directory conflicts on bothset_fileanddelete_path(raiseValueErrorfor invalid paths). - After deleting a leaf file, empty intermediate directories may remain and still contribute to the directory hash of their parent. Automatic pruning occurs only when the caller deletes that directory path. Deleting a directory path removes that subtree entry from its parent.
- Normalize both operations the same way: treat backslashes as
/, discard empty and.segments, and reject every..segment before traversal. Leading, repeated, and trailing separators are ignored. A path that normalizes to no segments is invalid. All paths refer to the in-memory tree; host filesystem paths are outside the contract. - A file can replace an existing file, but can't replace a directory. Traversing through a file is a conflict; deleting an existing file or directory itself is valid. Deleting a missing path returns
False.
Example
python
left = RepoHashTree()
left.set_file("src/app.py", b"print('hi')")
left.set_file("README.md", b"hello")
right = RepoHashTree()
right.set_file("README.md", b"hello")
right.set_file("src/app.py", b"print('hi')")
assert left.root_hash() == right.root_hash()Constraints
- Keep the tree in memory.
- Use a deterministic stable hash. Avoid process-randomized hashes.
- The classroom hash supports deterministic comparison. Repository authenticity requires a cryptographic hash and a trusted way to verify its root.
- Treat paths as POSIX-style
/paths after normalization. - Exact hexadecimal values and a cross-language wire format aren't prescribed. Consistently include file content and normalized path, plus sorted directory child names, types, and digests. Different stable hash implementations needn't produce identical roots.
Editor