Snapshot Diff

Snapshot Diff

You've joined the team that owns snapdiff, the library behind a backup tool's "what changed since last time?" screen. It compares two directory snapshots and reports which files were added, removed or modified. Support has a bug report, and two feature tickets are waiting behind it.

Codebase

How your code is run

The grader calls run(operations) from snapdiff/app.py with a list of operations and compares the list of results with the expected one. There is one result per operation, in order. Every operation returns a value; errors are strings starting with error:, never exceptions.

Snapshots. A snapshot is a nested object. A directory is an object mapping entry names to nodes. A file is a non-empty string, its content digest. Entry names are non-empty and contain no /. A *path* is the names from the root joined with /, for example src/util/fmt.py. Empty directories are allowed but contain no files, so they never appear in a diff.

A change object is {"op": "added" | "removed" | "modified", "path": ...}. Changes are ordered by path segment by segment: a/b.txt sorts before a.txt because a < a.txt. A file is *modified* when it exists on both sides with different digests.

Errors, checked in this order: an operation that is not a non-empty list starting with a string gives error: malformed operation; unknown operation error: unknown operation 'x'; wrong argument count error: bad arguments for 'diff'; unknown snapshot error: unknown snapshot 'name' (old checked before new); then the options errors below.

Example:

[["load", "v1", {"README": "9f86d081", "lib": {"a.py": "2c26b46b"}}],
 ["load", "v2", {"lib": {"a.py": "2c26b46b", "util": {"fmt.py": "fcde2b2e"}}}],
 ["diff", "v1", "v2"]]

returns

[{"files": 2, "dirs": 1}, {"files": 2, "dirs": 2},
 [{"op": "removed", "path": "README"}, {"op": "added", "path": "lib/util/fmt.py"}]]

diff and summary take an optional options object (null or absent means defaults). Anything other than an object is error: invalid options; an unknown key is error: unknown option 'key'. The keys are renames (Part 2) and ignore (Part 3).

Part 1 — Wrong paths and odd results in diffs

Goal: Diffs should always report correct paths and sensible changes.

Support reports: "after we moved a file into a nested folder, the diff shows the new file at the wrong path", and "when a file was replaced by a folder of the same name the diff just says it was modified".

Rules

1. Every reported path is the full path from the snapshot root, however deeply the file is nested and whichever side it exists on.
2. If a name is a file on one side and a directory on the other, the old side's files are all removed and the new side's files are all added. It is never modified.
3. Everything else about diff and summary keeps working as described above.

Example: the worked example above. lib/util/fmt.py must not appear as util/fmt.py.

Part 2 — Rename detection (SNAP-47)

Goal: Report moved files as renames when asked.

With option "renames": true, a removed file and an added file with the same digest are replaced by one change {"op": "renamed", "from": old_path, "path": new_path}.

Rules

1. renames must be a boolean, otherwise error: invalid option 'renames'. Default false: output is exactly as in Part 1.
2. Only files that are removed or added can be paired. A file that moved *and* changed has a different digest, so stays removed plus added. A copy of a file that still exists is just added.
3. Files whose digest equals EMPTY_HASH (in snapdiff/config.py) are never paired.
4. When several files share a digest, pair them in two passes. Pass 1 goes through the removed files in path order and pairs each with the first unpaired added file that has the same file name (last path segment). Pass 2 pairs the remaining removed files, in path order, with the remaining added files in path order. Unpaired files stay removed or added.
5. A renamed change is sorted by its new path, among all other changes.
6. summary counts renamed changes under renamed, and they are not counted as added or removed.

Example: old {"README.md": "aaaa1111", "notes.txt": "bbbb2222"}, new {"docs": {"README.md": "aaaa1111"}, "notes.txt": "cccc3333"} with {"renames": true} gives [{"op": "renamed", "from": "README.md", "path": "docs/README.md"}, {"op": "modified", "path": "notes.txt"}].

Part 3 — Ignore patterns (SNAP-52)

Goal: Let users hide build output and logs, .gitignore style.

Option "ignore" is a list of pattern strings. Ignored files are dropped from the results before anything else is computed, so they take no part in rename detection and are not counted in summary.

Rules

1. ignore must be a list of strings, otherwise error: invalid option 'ignore'. An empty list ignores nothing.
2. Each pattern is trimmed of surrounding whitespace. Empty patterns and patterns starting with # are skipped.
3. A leading ! negates a pattern. For any one path, the last pattern that matches decides whether it is ignored.
4. A trailing / makes the pattern match directories only. A pattern with no / apart from a trailing one matches the entry name at any depth. Otherwise the pattern is anchored to the snapshot root (a leading / is allowed and dropped) and matched against the whole path.
5. Matching uses fnmatch semantics, case-sensitive: *, ? and [abc] work, and * also matches / (so docs/*.md matches docs/sub/x.md). There is no **.
6. Ignoring a directory ignores every file inside it. A ! pattern can never re-include a file whose parent directory (at any level) is ignored.
7. A pattern matches a file or directory by its own path: build/ does not match a *file* called build.

Example: {"ignore": ["*.log", "build/"]} hides server.log, src/debug.log and everything under build/ (or lib/build/), but not app.py.

Notes

• store.py, tree.py, paths.py and report.py have been in production for a while and are well tested.
• You may use the AI assistant freely. Later parts must not break earlier ones; the visible tests are a starting point, not the full suite.
• Completing Parts 1 to 3 is a strong result.