Deterministic Matching Invariants

When implementing algorithms for pairing/alignment, matching/routing, search, or event fan-out, require a clearly stated invariant and explicit boundary/edge-case behavior, then back it with targeted tests.

copy reviewer prompt

Prompt

Reviewer Prompt
Deploy Agent

When implementing algorithms for pairing/alignment, matching/routing, search, or event fan-out, require a clearly stated invariant and explicit boundary/edge-case behavior, then back it with targeted tests.

Practical checklist: 1) Define the mapping/invariant precisely

  • Pairing/alignment: state exactly how items align (e.g., “pair min(D,A) in order; pad excess with blanks so row indices always correspond”).
  • Routing/matching: state the match predicate (e.g., longest-prefix-wins; require path-component boundaries) and tie-break rules.
  • Fan-out/lifecycle: state ownership and cleanup guarantees (who subscribes/unsubscribes, what events should reach whom).

2) Make boundary behavior unambiguous

  • Search chunking: if scanning in fixed-size chunks, decide whether matches can cross boundaries; if not possible, prove it; otherwise add tests and/or choose chunk boundaries that preserve correctness (e.g., newline-ended chunks if multi-line matches are possible).
  • Limits/quotas/fallbacks: when retrying with different parameters (depth/max_depth), model how the limit is consumed and add the rare edge case tests (e.g., “>quota at root”) that can re-trigger failure.

3) Use data structures that support required operations directly

  • For subscription/event systems, use bidirectional maps when you need both:
    • fan-out: key -> connections/subscribers
    • cleanup: connection -> keys/subscriptions

4) Test the invariants at the boundaries

  • Add unit/integration tests specifically for:
    • excess deletions/additions (alignment padding correctness)
    • chunk boundary match correctness
    • quota-triggered fallback edge cases
    • prefix match boundaries (path-component boundary)
    • unsubscribe/connection-drop cleanup (no leaks, no missed delivery)

Mini example (alignment invariant style):

// Within each hunk: D deletions followed by A additions.
// Invariant: row indices correspond across panes.
let pairs = d.min(a);
for i in 0..pairs {
  left_row(i) = deleted[i];
  right_row(i) = added[i];
}
// Excess
for i in pairs..d {
  left_row(i) = deleted[i];
  right_row(i) = blank();
}
for i in pairs..a {
  left_row(i) = blank();
  right_row(i) = added[i];
}

Adopting this standard prevents “almost correct” algorithms that break only at boundaries (chunk edges, quota-trigger thresholds, prefix boundary rules, uneven hunk sizes) and makes future maintenance safer because invariants are explicit and testable.

Source discussions