0

Repository Merkle tree hashing and change detection

by Frontier Interview· about 3 hours ago· ⑂ 0 remixes

Question: Repository Merkle tree hashing and change detection

Companies: Cursor

Difficulty: Medium

Problem statement

Hash a code repository into a Merkle tree over files and directories so changed paths are found by comparing hashes top-down instead of rescanning everything. Reported on 1point3acres' Cursor bank; reconstructed in our own words.

Clarify the setup

The use case: a code editor keeps a search index of a repository on a server. When the user reopens the project, the client must find which files changed since the last sync without uploading or rehashing everything. Ask:

  • Input shape. A real directory, or (simpler for an interview) a map from path to file bytes. Use the map; the walk over a real directory is a small adapter.
  • What is "changed"? Added, removed or modified files. A rename shows up as one removal and one addition unless we detect it (follow-up).
  • Which side computes what? Both sides hold a tree. They exchange hashes top-down, so the number of round trips and hashes sent matter, not just CPU.
  • Ignored files (.gitignore, build output) are dropped before hashing.

Approach

Build. A file node's hash is H("blob" | content). A directory node's hash is H("tree" | for each child, sorted by name: kind, name, child hash). Sorting makes the hash independent of listing order; including the name and kind means renaming a file or turning a file into a folder changes the parent's hash. Prefix tags (blob, tree) stop a file's content from colliding with a directory's encoding.

Detect changes. Compare the two roots. Equal hashes mean the whole subtree is identical, so stop. Otherwise, for a directory, match children by name:

  • only in old: every file under it was removed;
  • only in new: every file under it was added;
  • in both with different hashes: recurse (or, if one is a file and the other a directory, remove one subtree and add the other);
  • in both with equal hashes: skip.

The work is proportional to the changed paths times their depth and the fan-out of the directories along the way, not to the repository size. One changed file in a 100,000-file repo with depth 8 and about 30 entries per directory touches about 8 × 30 = 240 child comparisons.

Update in place. When the editor saves a file, rehash that file and then each ancestor up to the root: O(depth × fan-out), the same 240 operations, instead of rebuilding.

Sync protocol. The client sends the root hash. If the server's matches, done in one round trip. Otherwise the server returns the child hashes of differing directories and the client answers with which children differ, level by level. That is at most depth round trips; batch every differing directory at one level into one request.

Code

import hashlib
from typing import Dict, List, Optional, Tuple


def _h(*parts: bytes) -> str:
    d = hashlib.sha256()
    for p in parts:
        d.update(len(p).to_bytes(8, "big"))  # length-prefix each part: no ambiguity
        d.update(p)
    return d.hexdigest()


class Node:
    __slots__ = ("name", "is_dir", "children", "hash")

    def __init__(self, name: str, is_dir: bool) -> None:
        self.name = name
        self.is_dir = is_dir
        self.children: Dict[str, "Node"] = {}
        self.hash = ""

    def rehash(self, content: Optional[bytes] = None) -> None:
        if not self.is_dir:
            self.hash = _h(b"blob", content or b"")
            return
        parts: List[bytes] = [b"tree"]
        for name in sorted(self.children):
            child = self.children[name]
            parts += [b"d" if child.is_dir else b"f", name.encode(), child.hash.encode()]
        self.hash = _h(*parts)


class MerkleTree:
    def __init__(self, files: Optional[Dict[str, bytes]] = None) -> None:
        self.root = Node("", True)
        self.root.rehash()
        for path, content in sorted((files or {}).items()):
            self._insert(path, content, rehash=False)
        self._rehash_all(self.root, files or {}, "")

    # ---- build ----------------------------------------------------------
    def _insert(self, path: str, content: bytes, rehash: bool) -> List[Node]:
        parts = path.strip("/").split("/")
        chain = [self.root]
        node = self.root
        for name in parts[:-1]:
            nxt = node.children.get(name)
            if nxt is None or not nxt.is_dir:
                nxt = Node(name, True)
                node.children[name] = nxt
            node = nxt
            chain.append(node)
        leaf = Node(parts[-1], False)
        node.children[parts[-1]] = leaf
        if rehash:
            leaf.rehash(content)
        return chain

    def _rehash_all(self, node: Node, files: Dict[str, bytes], path: str) -> None:
        for name, child in node.children.items():
            child_path = f"{path}/{name}" if path else name
            if child.is_dir:
                self._rehash_all(child, files, child_path)
            else:
                child.rehash(files[child_path])
        node.rehash()

    # ---- incremental updates ---------------------------------------------
    def upsert(self, path: str, content: bytes) -> None:
        chain = self._insert(path, content, rehash=True)
        for node in reversed(chain):
            node.rehash()

    def delete(self, path: str) -> None:
        parts = path.strip("/").split("/")
        chain = [self.root]
        for name in parts[:-1]:
            chain.append(chain[-1].children[name])
        del chain[-1].children[parts[-1]]
        # prune directories left empty, bottom-up
        for i in range(len(chain) - 1, 0, -1):
            if chain[i].children:
                break
            del chain[i - 1].children[chain[i].name]
            chain = chain[:i]
        for node in reversed(chain):
            node.rehash()


def _all_files(node: Node, path: str) -> List[str]:
    if not node.is_dir:
        return [path]
    out: List[str] = []
    for name in sorted(node.children):
        out += _all_files(node.children[name], f"{path}/{name}" if path else name)
    return out


def diff(old: MerkleTree, new: MerkleTree) -> Tuple[Dict[str, List[str]], int]:
    """Changed file paths, and how many node pairs were compared."""
    result: Dict[str, List[str]] = {"added": [], "removed": [], "modified": []}
    compared = 0

    def walk(a: Node, b: Node, path: str) -> None:
        nonlocal compared
        compared += 1
        if a.hash == b.hash:
            return
        if not a.is_dir and not b.is_dir:
            result["modified"].append(path)
            return
        if a.is_dir != b.is_dir:
            result["removed"] += _all_files(a, path)
            result["added"] += _all_files(b, path)
            return
        for name in sorted(a.children.keys() | b.children.keys()):
            child_path = f"{path}/{name}" if path else name
            ca, cb = a.children.get(name), b.children.get(name)
            if cb is None:
                result["removed"] += _all_files(ca, child_path)
            elif ca is None:
                result["added"] += _all_files(cb, child_path)
            else:
                walk(ca, cb, child_path)

    walk(old.root, new.root, "")
    return result, compared

Complexity

  • Build: O(total bytes) for hashing plus O(F log k) for sorting children, with F files and k entries per directory.
  • Diff: O(c × d × k) for c changed files at depth d, plus the size of any added or removed subtree. O(1) when nothing changed.
  • Update: O(d × k) hashing per saved file (the directory hash rehashes all its children's hashes).
  • Space: O(F) nodes, 32 bytes of hash each. 100,000 files are a few MB.

Test cases

FILES = {
    "README.md": b"hello",
    "src/app.py": b"print(1)",
    "src/util/strings.py": b"def f(): pass",
    "src/util/nums.py": b"x = 1",
    "docs/guide.md": b"guide",
}


def test_same_content_same_hash_regardless_of_order():
    a = MerkleTree(FILES)
    b = MerkleTree(dict(reversed(list(FILES.items()))))
    assert a.root.hash == b.root.hash
    changes, compared = diff(a, b)
    assert changes == {"added": [], "removed": [], "modified": []} and compared == 1


def test_detects_added_removed_modified():
    new = dict(FILES)
    new["src/util/nums.py"] = b"x = 2"
    del new["docs/guide.md"]
    new["src/new.py"] = b"new"
    changes, _ = diff(MerkleTree(FILES), MerkleTree(new))
    assert changes == {"added": ["src/new.py"], "removed": ["docs/guide.md"],
                       "modified": ["src/util/nums.py"]}


def test_file_replaced_by_directory():
    old = {"a": b"file"}
    new = {"a/b.txt": b"inner"}
    changes, _ = diff(MerkleTree(old), MerkleTree(new))
    assert changes == {"added": ["a/b.txt"], "removed": ["a"], "modified": []}


def test_rename_changes_hash():
    assert MerkleTree({"a.py": b"x"}).root.hash != MerkleTree({"b.py": b"x"}).root.hash

def test_diff_skips_unchanged_subtrees():
    big = {f"pkg{i}/mod{j}.py": f"{i}-{j}".encode() for i in range(50) for j in range(50)}
    new = dict(big)
    new["pkg7/mod3.py"] = b"changed"
    changes, compared = diff(MerkleTree(big), MerkleTree(new))
    assert changes["modified"] == ["pkg7/mod3.py"]
    assert compared <= 1 + 50 + 50  # root, its children, one directory's children


def test_incremental_update_matches_rebuild():
    t = MerkleTree(FILES)
    t.upsert("src/util/nums.py", b"x = 3")
    t.upsert("lib/extra/deep.py", b"deep")
    t.delete("docs/guide.md")
    expected = dict(FILES)
    expected["src/util/nums.py"] = b"x = 3"
    expected["lib/extra/deep.py"] = b"deep"
    del expected["docs/guide.md"]
    assert t.root.hash == MerkleTree(expected).root.hash
    assert "docs" not in t.root.children  # empty directory pruned

Follow-ups

  1. Skip hashing unchanged files. Hashing a large repo is I/O bound. Cache (path, size, mtime, inode) -> hash locally and only rehash files whose metadata changed. Watch the file system (FSEvents, inotify) to update the tree as files are saved.
  2. Renames and moves. Match removed and added files by content hash: an equal blob hash under a new path is a move, so the server can reuse its embeddings instead of re-indexing.
  3. Privacy. The server only needs hashes and the content of changed files. Hashes of short, guessable files can leak content, so salt them per user or workspace, and obfuscate path names before they leave the machine.
  4. Large directories. A node_modules-sized directory with 50,000 entries makes every rehash of its parent O(50,000). Split huge directories into hash buckets by name prefix (an intermediate tree level), or exclude them.
  5. Chunk-level change detection. For indexing, the unit is a code chunk (a function or class), not a file. Hash chunks inside each file the same way, so editing one function re-embeds one chunk.

Interviewer expectations

Mid-level (L4)

  • Builds the tree with file hashes from content and directory hashes from sorted children.
  • Diffs two trees recursively and stops at equal hashes.
  • Handles added and removed subtrees and writes a test for each kind of change.

Senior (L5)

  • Gets the hash encoding right: names and kinds in the directory hash, sorted order, unambiguous framing.
  • Implements incremental updates by rehashing the path to the root and pruning empty directories, and verifies against a rebuild.
  • States the diff cost in terms of changed paths, depth and fan-out, with numbers.

Staff (L6+)

  • Designs the client-server sync: one round trip when nothing changed, a batched round trip per level otherwise.
  • Raises the practical issues: mtime caches, file watchers, ignored and huge directories, rename detection to reuse embeddings, and what hashes reveal about private code.
  • Moves the change unit to code chunks for indexing.

Sign in to comment, vote or remix.