Fuzzy title search on the ledger — implementation plan

Status: scoped and agreed, not implemented. No code, schema, or dependency changes have landed.

Goal: a search bar on / that finds pages by title and tolerates typos — kubrenetes finds Kubernetes migration plan.

Decisions recorded in MEMORY.md as D56–D61.

Agreed constraints

1. Why SQLite stays, and why FTS5 is the wrong instinct

The obvious move — "add FTS5" — does not work here:

• FTS5 cannot do what was asked. Its trigram tokenizer (present in our build: SQLite 3.45.1 locally, comparable in python:3.12-slim) does substring matching. A MATCH requires every 3-gram of the query to be present in the row. kubrenetes and kubernetes share almost no trigrams, so a single transposed character returns zero rows. It also silently matches nothing below 3 characters. It is a good substring index and not a fuzzy matcher.
• No SQL engine gives typo tolerance for free. spellfix1 is not compiled into the stdlib build (verified: no such module: spellfix1). Postgres pg_trgm genuinely would — the one honest argument for switching — but it buys a server process, a pool, migrations, backups, and Compose surface to replace ~40 lines of Python.
• So the scoring lives in Python either way. Once that is true, SQLite's only remaining job is "hand me the active rows", which it already does.
• The corpus is trivially small. Titles only, String(512), ~10k rows target — well under 1 MB total.

Second payoff: rule 6 in AGENTS.md says the next nontrivial schema change should introduce Alembic. An FTS5 virtual table plus sync triggers is that change. This design sidesteps the migration story entirely.

Escalation trigger — write it down so nobody re-litigates it

Add FTS5 trigram as a recall prefilter feeding the same Python ranker when either holds:

• active page count > 25,000, or
• measured p95 for GET /search > 50 ms.

The upgrade is deliberately one function wide: _candidate_rows(db, query). Everything downstream keeps working.

2. Ranking

rapidfuzz (MIT, C++/SIMD, manylinux wheels, no runtime deps). process.cdist over 10k short strings runs in single-digit milliseconds.

The stdlib alternative, difflib.SequenceMatcher, is pure Python at roughly 50–100 µs per pair → ~0.5–1 s per request at 10k rows. Not viable. A compiled wheel is not a new precedent: nh3 (Rust) and boto3 are already dependencies.

• Scorer: fuzz.WRatio with utils.default_process (casefold, strip non-alphanumerics). WRatio blends ratio, partial_ratio, token_sort and token_set with length penalties — substring, typo, and word-order in one call, which is exactly the requirement.
• Cutoff: 70, settings-tunable.
• Ordering: (-score, -updated_at, -id). The tie-break is mandatory. WRatio produces many exact-100 ties, and rule 14 already records what SQLite's one-second timestamp resolution does to unstable sorts.

rapidfuzz is the first dependency added since the repo noted a lockfile as a v1.1 gap — accepted. Confirm the manylinux wheel resolves on python:3.12-slim at implementation time rather than discovering a source build in Docker.

3. Architecture

New service — app/services/search.py

Kept out of services/pages.py: that module is publish/write business logic, this is a read model. It also gives the future FTS5 index an obvious home. The storage rule is unaffected — still app/services/ + app/storage/ only, nothing new for mcp_server/.

@dataclass(frozen=True)
class SearchHit:
    summary: PageSummary
    score: float

@dataclass(frozen=True)
class SearchResult:
    hits: list[SearchHit]
    total_matched: int
    truncated: bool

def search_pages(db, query, *, limit=50, settings=None) -> SearchResult: ...

Pipeline:

1. normalize_query(raw) — NFKC, casefold, collapse whitespace, cap 64 chars. Under 2 characters returns empty without touching the database.
2. Candidate fetch reuses page_is_active_clause(now) and Page.purge_started_at.is_(None) from app/lifecycle.py — imported, never reimplemented. A hand-rolled predicate here is how an expired or purge-claimed page leaks into results and breaks rule 21.
3. rapidfuzz scoring, cutoff applied.
4. Sort (-score, -updated_at, -id); record total_matched before truncating to limit.

New route module — app/viewer/search.py

GET/HEAD /search?q=…, sibling to index.py so the ledger module keeps its pagination doctrine uncluttered. HEAD is included because / is deliberately api_route(methods=["GET", "HEAD"]) and an asymmetry here would read as accidental.

Headers match the ledger exactly: Cache-Control: private, no-store, Vary: Cookie, plus _base_security_headers() — which already carries X-Robots-Tag: noindex, nofollow, noarchive and Referrer-Policy: no-referrer, the latter keeping queries out of third-party referer logs.

Two representations of the query — do not conflate them:

• match_query — normalized, used for scoring.
• display_query — the raw input, length-capped and stripped of control characters, echoed into the input box and the empty state.

display_query reuses the sanitizer already in viewer/errors.py (display_path, _MAX_DISPLAY_PATH). Extract it to a shared sanitize_display_text rather than copying — same threat, same treatment.

Shared row builder — app/viewer/rows.py

index.py currently owns _row(), _as_utc(), _expiry_label() and _FORMAT_SIGILS. Search needs all of them. Move them to a shared module and import from both; do not fork a second copy that will drift.

Template

Reuse _ledger.html. Give the band row a conditional: search passes a single pseudo-group with label=None and the template skips the date band when the label is falsy. Date bands are meaningless once rows are relevance-ordered, but the table, ARIA roles, and the sub-48rem grid collapse are all worth keeping — duplicating that markup is exactly the maintenance cost to avoid.

The form, on /, /page/{n}, and /search (prefilled):

<form class="ledger-search" role="search" method="get" action="/search">
  <label class="sr-only" for="q">Search page titles</label>
  <input id="q" name="q" type="search" maxlength="64" value="{{ display_query }}"
         placeholder="Search titles" autocomplete="off" spellcheck="false">
  <button type="submit">Search</button>
</form>

maxlength is a UX affordance only; the server caps independently.

4. Accessibility

The ledger has unusually careful ARIA — explicit roles specifically so the mobile grid collapse cannot strip table semantics. Search must hold that bar.

• The result count is visible page content, not a screen-reader-only aside: a "12 matches for kubernetes" line sits directly above the results table, in the slot the ledger uses for its N pages · M versions stats line. Sighted users need the count as much as anyone, and one visible element that is already in the reading order beats a duplicated live region.
• Since results arrive by full-page navigation (not an in-place update), no aria-live is needed — the new document is announced normally. Making the count a real heading-adjacent line is what ensures it is reached early rather than after the whole table.
• The form carries role="search" and a real <label> (visually hidden, not a placeholder — placeholders are not accessible names).
• The empty state ("No titles match …") occupies the same slot, so the outcome is announced in the same place whether or not there were hits.

5. The two doctrine changes

5a. Replace the CSP enumeration with a trust-tier rule

A no-JS search bar is a GET form, and the home shell currently serves _VIEWER_CSP with form-action 'none' — the browser blocks submission outright. _home_headers() must switch to allow_forms=True.

That contradicts AGENTS.md rule 8 / MEMORY.md rule 13 ("form-action 'self' is for the unlock shell only"). Rather than bolt on a second named exception, the operator's amendment — trusted shells may use JS and forms; untrusted content may not — is the better invariant, and it makes the rule tell a future agent how to decide instead of listing what happens to be true today:

The middle tier is the one an enumeration keeps losing: the Mermaid helper is our JavaScript, so a flat "trusted code may use JS" rule would wrongly imply it can relax the rest of its policy. It cannot — it is trusted code in an untrusted position.

Risk assessment for the specific change: form-action 'self' permits our page to submit forms to our own origin only. This form is GET, carries no credentials, and mutates nothing, so CSRF is inapplicable. The old rule was defense-in-depth minimization, not a defense against a specific attack on this page.

Touch points: app/viewer/shell.py (the docstring at lines 13–14 asserts the old invariant), tests/test_home_index.py:349, tests/test_viewer_security.py:359, tests/test_viewer_theme.py:314.

5b. ?q= without weakening validate_next_path

validate_next_path rejects query strings, which is why pagination is path-based. Free text cannot go in a path: slashes and dots need encoding, many proxies reject %2F, length is unbounded, and case/encoding aliasing gives one search several URLs — the same defect the codebase deliberately 404s /page/007 to avoid.

Resolution: leave validate_next_path byte-for-byte unchanged. It keeps rejecting ? and keeps returning a bare path. Add /search to its allowlist as a bare path only.

For the theme round-trip, pass the query beside the path, not inside it, and reassemble it server-side from independently validated input:

# theme.py
def theme_set_href(theme, next_path, *, next_query=None) -> str:
    href = f"/viewer/theme/{theme}?next={quote(next_path, safe='')}"
    if next_query:
        href += f"&q={quote(next_query, safe='')}"
    return href

In GET /viewer/theme/{theme} (routes.py:287), after validate_next_path succeeds, append ?q= only when the validated path is exactly /search, and only from a re-normalized, re-encoded q — never echoed raw. The redirect target is therefore still assembled from a validator that only ever emits paths, plus one server-synthesized parameter. The open-redirect surface is unchanged.

Recorded as: pagination stays path-based; /search is the single route permitted a query string, and the theme round-trip reconstructs that query from re-validated input rather than passing it through the path validator.

Why no JavaScript, given the amendment permits it

The doctrine now allows JS on trusted shells, but this feature should not spend it. Type-and-enter is the right interaction: a full-page GET keeps results linkable, back-button-able, and working with JS off. Debounced typeahead would multiply requests per search on a small VPS and shift results under the user while they are still typing — worse for a ledger where you usually know roughly what you are looking for.

There is also a tempting shortcut to avoid: keeping form-action 'none' and having a click handler call location.assign('/search?q=' + …), since form-action does not constrain script navigation. That trades a robust HTML primitive for a JS dependency purely to dodge one CSP directive, and breaks entirely with JS disabled. The form is correct; the directive change is its honest cost.

Shipping the whole title list to the client for offline filtering is not worth considering either: it leaks nothing (the ledger is public) but 10k titles is ~600 KB on every ledger load.

6. Rate limiting

/search is the first unauthenticated, unbounded-input, compute-bearing endpoint on the instance. Every other public route is a fixed lookup. An O(N) scan per request, on a single-process uvicorn on a small VPS that also serves R2-backed page reads, is a request-amplification vector.

The design goal is asymmetric: invisible to a human, hard-capped against a bot. That is achievable because the two have very different shapes — a person refines a query 5–10 times in a burst and then stops for minutes; a bot sustains a flat rate forever.

The scheme

Why two fixed windows rather than one

One window cannot do both jobs. A single generous limit (60/5 min) lets a user who burns it in the first 30 seconds sit locked out for 4½ minutes; a single tight limit blocks ordinary refinement. Two windows — a loose short one and a firm long one — approximate a token bucket's "burst then sustain" shape.

This is also the existing unlock precedent: consume_pin_unlock_rate_limits already stacks a per-page+IP counter and a global-per-IP counter. Search reuses consume_rate_limit twice with different keys, so it needs no new table, no new columns, and no Alembic — preserving the §1 payoff.

A real token bucket (tokens, last_refill, refill computed inside one atomic conditional UPDATE) is a better fit in the abstract and would still satisfy rule 4. It is not worth a schema change here; note it as the upgrade path if the two windows prove too coarse.

Keys: sha256("search-ip-min:" + client_ip) and sha256("search-ip-hr:" + client_ip). Consume the burst window first, so requests already rejected by the tight limit do not also spend sustained budget. (The reverse order over-counts; unlock has the same imprecision and it is accepted there too.)

Do these numbers bother a daily user?

• A heavy human does 20–40 searches a day. The hourly cap alone is ~10× that.
• Rapid refinement is ~6–10 searches in a minute against a 20/min ceiling.
• A NAT'd 20-person office on one egress IP: ~800 searches/day over 8 hours ≈ 100/hour, inside 200/hour — but the margin is thin, so all four numbers are settings-driven (SEARCH_RATE_LIMIT_BURST_MAX, SEARCH_RATE_LIMIT_BURST_WINDOW_SECONDS, SEARCH_RATE_LIMIT_SUSTAINED_MAX, SEARCH_RATE_LIMIT_SUSTAINED_WINDOW_SECONDS) and a large shared-IP deployment should raise them.

resolve_client_ip returns a shared flag when it cannot attribute a peer. For that bucket the per-IP layers are advisory at best — everyone lands in one counter. Give it a larger ceiling and let layer 3 do the real work.

Layer 3 is the one that matters on a small VPS

Per-IP counters do nothing against 50 IPs sending one request each. What actually takes the box down is concurrent CPU-bound scoring starving the event loop. Cap it directly, mirroring the PIN_UNLOCK_HASH_CONCURRENCY pattern that rule 19 already establishes for scrypt: a BoundedSemaphore with non-blocking acquire, SEARCH_CONCURRENCY default 4, returning 503 + Retry-After when full rather than queueing. Release it in a finally so a raising scorer cannot leak a slot.

This is IP-independent, so it survives distributed abuse, and it is a hard ceiling on how much CPU search can ever consume — the property worth having when the same process serves page reads.

Layer 4 — the result cache ships in Phase 1

Originally deferred; the VPS constraint argues for shipping it now. It is ~15 lines and converts the worst repeated-query attack into a dict lookup. Key on (normalized_query, corpus_version) where corpus_version is a cheap SELECT COUNT(*), MAX(updated_at) over the active predicate — microseconds in C against 10k rows, versus milliseconds of scoring. Bound at 256 entries, LRU.

Safe under today's single-process uvicorn; under multiple workers it degrades to a per-worker read cache, which is still correct.

Observability — you cannot tune what you cannot see

Emit a structured log line on every 429 and 503, carrying the limit kind (burst / sustained / concurrency), the current count against its ceiling, and the (already-bucketed) client key. Without this, the first sign of a too-tight limit is a user complaint and the first sign of a too-loose one is the box getting slow. Five tunable numbers with no telemetry is five guesses.

Keep it to counters and kinds — never log the query text. It is unauthenticated user input and would put arbitrary strings into the log stream.

Two counter-table details that are easy to miss

Both concern publish_rate_limits, the shared table holding (key, window_start, request_count) rows. Deleting a row is identical to resetting its counter to zero — harmless only when the row's window has already expired, since the next request would reset it anyway. The invariant is therefore retention >= the longest window: purge corpses, never live counters.

1. Add the search windows to _rate_limit_retention_seconds() (viewer/unlock.py:106), which today returns max(publish_window=3600, pin_unlock_window=900).

   To be precise: the proposed 200/hour window is exactly 3600 s, so retention already equals it and nothing is broken today. It is safe by coincidence, not by design — the moment anyone tunes the sustained cap to 6 or 24 hours, the 1-in-32 probabilistic purge starts deleting live counter rows. Worked example at a 6-hour window: an attacker exhausts 200 searches by 12:20 and is correctly blocked until 18:00; at 13:05 an unrelated visitor's request rolls the dice, the purge drops every row with window_start < 12:05 including the attacker's live one, and their next search starts a fresh count. No error, no log, triggered by third-party traffic at random — effectively unreproducible from a bug report. Folding the search windows into the max() makes it correct by construction.

2. /search must call maybe_purge_expired_rate_limit_rows itself. The purge has exactly one caller today — unlock.py:151. On an instance with no PIN-locked pages the unlock route is never hit, so the purge never runs at all. Search would then add one permanent row per distinct IP to a table nothing cleans, growing without bound under a distributed scan. Wire the same p = 1/32 best-effort call into the search path.

Degrade, don't error

On 429 and 503, render the search shell with an inline "too many searches — try again in N seconds" state, keeping the search box and a link back to the ledger, rather than bouncing to the full error page. Retry-After is still set. /search is a page, not an API; a dead end is the wrong response to someone typing too fast.

7. Route handlers stay sync (AGENTS.md rule 22 / D56)

Keep the route a plain def, never async def. FastAPI runs async def endpoints on the single event-loop thread, so 50 ms of scoring freezes every other request — it cannot even read the next one off the socket. A sync def endpoint runs in a worker thread instead, and because rapidfuzz.process.cdist releases the GIL during its C++ work, the event loop keeps running Python at full speed on another core.

Both halves are required. A worker thread running pure-Python scoring would hold the GIL and starve the loop anyway — that is the difference between rapidfuzz and difflib here, independent of raw speed.

Every endpoint in the codebase is already sync, so this is a don't break it rather than a change. The realistic failure is a future contributor "modernising" the route to async def — it looks like a cleanup and silently converts search into a whole-app stall.

8. Security constraints to lock in

Proposed additions to "do not regress":

1. Search covers pages.title only — never version bodies. Bodies live in R2 and some are PIN-locked; a body index would be a PIN-bypass oracle and would require reading every object. Titles are already fully public on the ledger, so title search leaks nothing new. This is a permanent boundary, not a v1 shortcut.
2. Search reuses page_is_active_clause + purge_started_at IS NULL. Expired and purge-claimed pages must never surface (rule 21: expired ≡ missing).
3. PIN-locked pages are included. Their titles are already listed on the ledger; excluding them would be inconsistent and would itself be a signal. Rows keep the lock sigil, and clicking through still hits the unlock gate.
4. Reflected q goes through the shared display sanitizer, Jinja autoescape, and script-src 'none'.
5. Query text never reaches the logs.

AGENTS.md's non-goal wording ("search-engine discovery beyond the ledger") needs a clarifying clause so a future agent does not read in-app title search as a violation. In-app search over an already-public ledger is a better view of public data; it is not external discovery, and X-Robots-Tag: noindex still applies.

Slugs are deliberately not matched. Slugs derive from titles, so recall overlaps heavily, and the random 8-character suffix makes partial-slug matching unreliable enough to be misleading.

9. Tests

tests/test_search.py

• typo tolerance: publish Kubernetes migration plan, query kubrenetes → hit
• substring: migra → hit
• ranking: exact title outranks partial
• deterministic tie-break: two identically-titled pages hold a stable order across repeated calls
• expired excluded; purge_started_at claimed excluded; locked included
• q absent → 303 /; q too short → guidance, no scan
• q over 64 chars truncated, no 500; emoji/unicode title does not crash
• <script> in q is escaped in the reflected output
• HEAD /search?q=… matches GET status and headers
• the match count renders as visible content above the table, and the empty state occupies the same slot

tests/test_search_rate_limit.py

• burst window: 21st request in a minute → 429 + Retry-After, rendered as the inline degraded state (not the full error page)
• sustained window: burst respected but hourly exhausted → 429
• consumption order: a request rejected by the burst window does not decrement the sustained counter
• layer 0: q under 2 chars and q absent consume no budget
• concurrency: with the semaphore saturated, the next request gets 503 + Retry-After, and the slot is released even when scoring raises
• retention: _rate_limit_retention_seconds() covers the longest search window, asserted against settings rather than a hardcoded number
• the search path invokes the row purge (so it does not depend on unlock traffic)
• a 429/503 emits the structured log line, and it does not contain the query
• the route handler is not a coroutine function — guards the §7 regression

tests/test_viewer_security.py — /search CSP carries form-action 'self', script-src 'none', no-store, Vary: Cookie; /p/* and /raw still form-action 'none'.

tests/test_viewer_theme.py — theme round-trip from /search preserves ?q=; a q alongside any next other than /search is dropped.

Plus the three flipped form-action assertions and a test_home_css.py-style assertion for the new search CSS.

10. Files and effort

New dependency: rapidfuzz>=3.9.

Estimate: 1.5–2 days, tests and docs included.

11. Out of scope

• Searching body content — permanently, per §8.1.
• Matching slugs — per §8.
• Typeahead / autocomplete — permitted by the doctrine now, declined on merit per §5.
• GET /v1/pages?q= API search — v1.1; the ranker is reusable when wanted.
• Facets (format, locked, expiry filters).
• Any second datastore.