Hash a Repository with a Merkle Tree and Find Changed Files

Design a Merkle-tree representation of a repository. Compute a hash for the complete repository, use it to locate a modified file, and extend the comparison to inspect changed directories and report the changed files inside them. ### Constraints & Assumptions - The source describes repository/file operations without supplying an in-memory serialization or a hash function. Discuss a real filesystem scan and choose an explicit canonical hashing policy. - Define whether metadata, symlinks, renames, and ignored paths affect equality. - Compare coherent snapshots or state the limits of scanning files while they are changing. ### Clarifying Questions to Ask - Does equality mean file bytes only, or also executable bits and other metadata? - Should symlinks be hashed as links or followed, and how are cycles handled if followed? - Should a rename be reported as delete-plus-add or detected as a separate operation? - Is an old Merkle manifest available, or must both snapshots be scanned? ```hint Hash boundaries and names as well as contents A directory digest must distinguish two differently named children and must encode concatenated fields unambiguously. ``` ### What a Strong Answer Covers - Domain-separated leaf/directory hashing with canonical child order and unambiguous encoding. - A repository root digest and retained per-node digests. - Comparison that prunes equal subtrees and descends into changed directories. - Added, removed, modified, and type-changed entries under the declared policy. - Hash-collision assumptions, I/O cost, and snapshot consistency. ### Follow-up Questions - How would a cached tree update after one known file change? - What extra work is needed for byte-exact equality rather than equality under a collision-resistance assumption?