Invariants before algorithms¶
A useful invariant says what stays true while the algorithm runs. It also says what the caller may rely on when the algorithm stops. Write it before writing the loop.
Preorder subtree intervals¶
Assume a tree is emitted in preorder. Every node is emitted before its children. Assume each subtree is contiguous. Let \(e_i\) be the first index after node \(i\) and all its descendants.
Claim. A traversal can skip the subtree by advancing to \(e_i\).
Proof. Contiguity puts every descendant before \(e_i\). The exclusive-end definition puts every later node at or after \(e_i\). Advancing there therefore skips exactly the subtree. The validator checks the assumptions before a renderer relies on them.
A complete scan visits each node once. Its traversal cost is \(O(N)\). Skipping a subtree takes one index update. Payload work still costs what it uses. Do not confuse a constant-time skip with constant-time rendering.
Measure before emit¶
The renderer first measures the byte count \(m\). Let the caller’s output capacity be \(c\).
The measured and emitted traversals use the same rules. A successful emission must write exactly \(m\) bytes. A failure returns no valid partial artifact. The host owns publication, so incomplete bytes cannot replace a previous output.
Cache validity¶
A cache key must cover the data that can change a result. Sources alone are insufficient. Includes, templates, configuration, reference lookups, resources, and adapter versions can affect the output. Reuse is allowed only when the recorded dependencies still agree. A missing output invalidates reuse even when its key matches.
Tests install failing allocators at the core boundary and compare emitted content. They also audit imports. Counting allocations without checking the result could miss a refusal that silently discarded part of the document.