« Phase 15 README · Warmup · Hitchhiker's · Principal Deep Dive · Core Contributor · Staff Notes

Phase 15 — Deep Dive: The Coding Agent's plan → patch → verify Mechanism

The load-bearing idea in a coding agent is not "an LLM that writes code." It is a control loop whose observation is a verdict, not a lookup, wrapped around a transactional edit primitive that fails closed. Everything a coding agent gets right — recovery from a wrong first patch, never corrupting a file, stopping instead of spinning — falls out of those two mechanisms. This doc traces them at the level someone implementing them has to reason about: the data structures, the ordering, the invariants, the complexity, and a step-by-step trace of the loop the lab builds.

The three data structures that carry the whole mechanism

The repo is a dict[str, str]. Repo wraps path → text with read, write, exists, paths, and the pair that matters: snapshot() returns dict(self._files) and restore(snap) sets self._files = dict(snap). The subtle correctness property: because Python strings are immutable, a shallow dict copy is already a deep copy of the working tree — no path's text can be mutated in place, so a snapshot taken before an edit is a frozen witness of the tree, and restore is a total rollback. This is not an incidental convenience; it is the invariant the whole loop's atomicity rests on.

A patch is a tagged union expressed as a dict. Two shapes: a full-file write {path, content} and a search/replace hunk {path, old, new}. apply_patch returns a PatchResult(ok, path, kind, error) — a structured outcome, never an exception on a bad patch. That return-not- raise choice is what lets a failed apply be an observation the agent recovers from rather than a crash that unwinds the loop.

Verification is a list of named predicates. A Check is (name, predicate: Repo → bool), and Check.run wraps the predicate in try/except so a check that raises (reading a missing file, parsing a syntactically broken file) returns False — a failed check, not a crashed verifier. A Spec is (description, acceptance_checks); verify produces VerifyResult(passed, results, failures) where passed = not failures. The failures list — the names of the checks that did not pass — is the reward signal that flows back into the next iteration.

apply_patch: the fail-closed edit algorithm, step by step

This is the core mechanism and the one interviewers probe. The order of operations is itself an invariant:

1. Validate the path. No path, or a non-string path → invalid, nothing written.
2. Guardrail first. If allowed_paths is set and path is not in it → reject before touching the repo. The check precedes every write so a rejected edit can never leave a side effect.
3. Dispatch on shape. content present and old absent → full-file write. old and new present → search/replace.
4. The count-the-matches rule (search/replace). Read the file, compute count = text.count(old). Then: count == 0 → not found, fail, write nothing. count > 1 → ambiguous, fail, write nothing. count == 1 → text.replace(old, new, 1), write once.

The invariant across every branch: ok=False implies zero bytes changed. The complexity is O(len(file)) for the substring count and replace — cheap, and deterministic. The load-bearing line is the count > 1 rejection. A fuzzy tool would "replace the first match"; that is a coin flip that looks like it worked and silently corrupts one of ten return 0 sites. Exact-once-or-fail converts a class of silent-corruption bugs into a loud, recoverable observation. This is the same discipline as parsing in Phase 01 and schema validation in Phase 02, specialized to file edits.

Why the naive alternative fails at the mechanism level. "Have the model regenerate the whole file" removes the match step entirely — and with it every failure signal. Whitespace drift (the model's old has four spaces, the file has a tab), stale context (the file moved on since the model read it), and overlapping hunks all become invisible: the model emits a plausible full file, you write it, and the corruption surfaces later as a mysterious test failure with no edit to point at. Search/replace surfaces exactly those four failure modes at the edit boundary, where they are knowable and cheap to fix by widening the old context.

Atomicity: snapshot per patch, restore on failure

The agent applies each patch under its own snapshot:

snap := repo.snapshot()
pr   := apply_patch(repo, patch, allowed_paths)
if pr.ok:  record "applied"
else:      repo.restore(snap); record "apply failed"

Two properties matter. First, granularity: because the snapshot is per-patch, one failed edit in a multi-edit step cannot poison the sibling edits that already landed — each is its own transaction. Second, the invariant it guarantees: after any failed apply, the repo is byte-for-byte what it was before the apply. Without it, a failed edit leaves a half-written tree, the next verify runs against corruption, and the agent chases a ghost — a failure that looks like the model's fault but is the harness's. Real agents get this same invariant from git (git stash, a scratch branch, checkout -- file) or a copy-on-write overlay; the mechanism differs, the invariant is identical: an edit lands whole or not at all.

The loop, and why it starts with a verify

result := verify(repo, spec)          # iterations stays 0 if already satisfied
iterations := 0
while iterations < max_iters and not result.passed:
    iterations += 1
    plan := planner(spec, result)                  # reason, informed by failures
    for step in plan:
        for patch in patcher(spec, step, result, repo):   # act
            snap := repo.snapshot()
            if apply_patch(repo, patch, allowed_paths).ok: record "applied"
            else: repo.restore(snap); record "apply failed"
    result := verify(repo, spec)       # observe — the REWARD
return RunResult(result.passed, iterations, result, transcript)

The verify-first structure is deliberate: if the spec is already satisfied, the agent does zero work — the correct behavior and a clean determinism test. max_iters is a guard, not a target (the Phase 00 discipline): a model can propose a non-fix forever, so the cap converts an infinite token-burn into a bounded run that returns passed=False with a partial transcript. The transcript — every plan, apply, and verify event — is the reviewable diff-and-trail a human approves.

A worked trace: wrong once, then fixed

The lab's greet spec has five checks, including file_contains("util.py", "Hi {name}"). The scripted patcher is a pure function of observed repo state: on its first touch of util.py (the file does not yet exist) it writes the buggy return f"Hey {name}"; once the file exists it writes the corrected Hi version.

• iteration 1 — plan ["write util.greet", "write test_util"]. Patcher writes buggy util.py (Hey) and the test file. verify → the contains:"Hi {name}" check is False; failures = ["contains:util.py:'Hi {name}'"]; passed=False.
• iteration 2 — the failure flows into the next call. Patcher sees util.py now exists and writes the corrected Hi version. verify → all five checks pass; passed=True.
• The loop exits with iterations == 2, and a test asserts exactly that.

That trace is the thesis: loop correctness must not depend on the model's first patch being right. The reward (an objective pass/fail against the spec) catches the wrong patch, and the failures list tells the next iteration what to fix. Flip the patcher to always write the buggy version and the loop runs exactly max_iters times and returns passed=False — the guard firing, also asserted. A harness that only works when the model is right the first time is a demo, not a harness.

Verification is a reward, not a lookup — and never an eval

The one structural difference from a generic ReAct agent: a search tool returns text the model interprets; the verifier returns pass/fail against the spec — an objective reward the loop closes on. That objectivity is why coding agents outperform fuzzier agent categories. The security invariant that keeps the reward honest: the checks are provided callables, never eval of the agent's output. The lab's checks are static — string membership, and defines_function uses Python's ast to parse for a FunctionDef without executing a line. A model could write os.system(...) in util.py and the AST check would confirm it "defines greet" while running nothing. In production the check is the real test suite, but it runs inside a Phase 09 sandbox, never in the agent's process. Verification must never become the arbitrary-code-execution hole.

What to hold onto

Strip the tool branding and the mechanism is provider-agnostic: an edit primitive that fails closed on ambiguity, wrapped in per-edit transactional rollback, driven by a loop whose observation is an objective verdict fed back on failure and bounded by a hard guard. Get those invariants right — exactly-one-match-or-fail, restore-on-failure, verify-as-reward, max_iters as a guard — and you have built the thing Claude Code, Codex, Cursor, and Aider hide behind a UI. Get any one wrong and you have a plausible-looking demo that corrupts a file at 2 a.m.