Implement Deterministic Merkle Hashing for a Repository

Problem Statement

Modern developer tools like IDEs and version control systems rely on content-addressable storage and Merkle trees to detect file changes, synchronize state, and deduplicate data across workspaces.

Implement an in-memory repository structure MerkleRepo that supports file creation, modification, deletion, and efficient root/sub-tree hash retrieval. Hash values must be deterministic, meaning identical repository contents and structures must always yield identical hashes regardless of insertion order.

Requirements

1. Deterministic Hashing Specification:

   • File Node: The SHA-256 hex digest of: b"blob\x00" + (b"1" if is_executable else b"0") + b"\x00" + content
   • Directory Node: The SHA-256 hex digest computed over direct child entries sorted in ascending lexicographical order by their base name (UTF-8 bytes): b"tree\x00" + b"".join(name.encode() + b"\x00" + child_hash.encode() + b"\x00" for name, child_hash in sorted_entries)
   • An empty directory evaluates to the hash of b"tree\x00".

2. Cache Invalidation & Performance:

   • Recomputing get_hash after an edit should run in O(d) time, where d is the directory depth of the modified path, rather than O(N) over the entire repository.

3. Interface:

class MerkleRepo:
    def __init__(self):
        pass

    def put_file(self, path: str, content: bytes, is_executable: bool = False) -> None:
        """Creates or overwrites a file at the given absolute POSIX path."""
        pass

    def delete(self, path: str) -> None:
        """Deletes the file or directory (recursively) at the given path."""
        pass

    def get_hash(self, path: str = "/") -> str:
        """Returns the 64-character lowercase SHA-256 hex digest for the node at path."""
        pass

Constraints

• Paths are normalized absolute paths (e.g., "/src/index.ts"). Paths will not contain . or .. components.
• Path depth d <= 64.
• Total number of files and directories N <= 100,000.
• Overwriting a directory with a file or a file with a directory should replace the node and prune any dangling subtrees.

Example

repo = MerkleRepo()

repo.put_file("/a/b.txt", b"hello", is_executable=False)
repo.put_file("/a/c.txt", b"world", is_executable=False)

hash_root_1 = repo.get_hash("/")

# Modifying a file invalidates only /a/b.txt, /a, and /
repo.put_file("/a/b.txt", b"hello world", is_executable=False)
hash_root_2 = repo.get_hash("/")
assert hash_root_1 != hash_root_2

# Deleting and restoring gives the exact same hash
repo.delete("/a/b.txt")
repo.put_file("/a/b.txt", b"hello", is_executable=False)
assert repo.get_hash("/") == hash_root_1