Beagle SCM

SPOT-003: spot.js tree search — lazy trigram index, seen-tree/blob memo, dirty bypass

Input

Context

SPOT-002 locates within hunks; this ticket is the tree-wide search that feeds it candidate files. The C impl (spot/CAPO.h §"Index entry layout", CAPO.c scan/tip-walk) is the model: an LSM stack of sorted 8-byte postings under .be/*.spot.idx, a per-blob memo that makes indexing incremental, and a worktree scan where the index only ever EARLY-REJECTS clean files.

• C twins: wh64 [off:40|id:20|type:4] postings, SPOTIndexFromTips + BLOBFN memo, CAPOTri40 trigram packing, the capo_class_step dirty-bypass scan.
• JS substrate exists: shared/store.js (object reads), shared/classify.js (wt walk + clean/dirty), tok.parse (postings come off the token stream, no manual parsing).

Goals

shared/spotidx.js (or views/spot/): trigram index maintained lazily AT SEARCH TIME — search never requires a prior index pass, the index only makes it faster.

• 8-byte wh64 entries, one uniform shape [off:40 | path_hl:20 | type:4] (WHIFF: type LS nibble, off MS sorts first); natural u64 sort; sorted runs on disk, merged iteration, compaction (C 1/8 invariant).
• Record types: TRI posting [tri:40 | path_hl:20 | TRI] "this path has ever contained this trigram" (3 RON64 chars, 18 bits used); BLOB memo [blob_hl:40 | path_hl:20 | BLOB] "this blob@path is already tokenized"; TREE memo [tree_hl:40 | dirpath_hl:20 | TREE] "this subtree@dir is already indexed"; free type nibbles reserved (DEF/MEN symbol postings later, [sym_hash:40 | path_hl:20 | type]).
• Memos pair hash WITH path — load-bearing, not C nostalgia: a bare blob memo would skip a known blob at a NEW path (path gets no postings → filter wrongly rejects it); a bare tree memo would prune a MOVED subtree (same tree hash, all full paths new). The pair keying re-walks exactly those cases.
• Lazy indexing during search: walk the tip trees; TREE memo hit → prune the whole subtree; BLOB memo hit → skip the blob; else read blob, tok.parse, emit TRI postings, write the BLOB row; write the TREE row when a subtree completes.
• Search: needle → trigram set → intersect postings → candidate path-hash20 set; clean tracked files not in the set are rejected without opening; candidates are opened and matched by SPOT-002 matchers (RAP20 collisions just rescan — filter, not truth).
• Dirty and untracked files are searched UNCONDITIONALLY, index bypassed — the index is authoritative only for clean tracked content (C: apply_filter iff CLASS_BOTH + known mtime stamp).
• Bro right-click = project-scoped symbol/token grep (the C browser's action, revived): right-clicking a visible token navigates to spot://WT/path#token — the substr locator over the worktree; blocked on THIS ticket, ships with it.
• The right-click search emits hunks like every view: one hunk per match window, 2-3 context lines each way (SPOT-002 window, grepCtx twin), so results page/click/compose as usual.
• Scope rides the PATH slot, never the fragment (ruling 2026-07-18, kills today's #'pattern'.ext): spot:.c#'pattern' = all files of the .c lexer family; spot:/root/path#'pattern' = subtree scope, each file parsed with its OWN grammar (per-ext needle recompile — SPOT-002 compile(loc, ext) / scan already does this); the fragment is the locator, nothing else.
• Wiki drift: /wiki/View.mkd §"Search views" still shows the fragment-.ext form (spot:#'…'.c) — stale under this ruling, needs the hand edit on landing.

Constraints

• A NEW index format (ruling 2026-07-18: no bit-compat with CAPO.h required); the TRI/BLOB shapes still coincide with C's, TREE is the JS addition.
• Growth stays bounded because postings are PATH-keyed: an edited blob re-emits mostly identical (tri, path) entries which dedup at ingest (hash-set) and at compaction — index ~ O(one snapshot's distinct pairs), history costs one BLOB memo row per blob version. Blob-keyed postings would grow linearly with history (every edit mints a fully novel posting set) — rejected.
• Blob bytes come via shared/store.js only; wt walk + clean/dirty verdicts via classify.js — no parallel stat/walk code.
• Trigrams over the RON64 alphabet, CAPOTri40 packing verbatim; needles with <3 such chars get no filter (full scan, like C SPOT_SCAN_NO_FILTER).

WIP

Design decisions

• One search entry: candidates(needle, ref) — opens runs, lazily indexes unseen trees/blobs of ref's tip, returns the path-hash filter set; the caller (spot view / SPOT-002 scan) does the actual matching.
• Trigram-MS order ruled (2026-07-18) over path-MS: filtering intersects a few CONTIGUOUS trigram blocks once per query and can early-out "no matches anywhere" before walking; path-MS would random-probe every clean file across every run and never conclude globally. The filtering algo:

tris = trigrams(needle)                    // a handful
cand = null
for t in tris (rarest range first):
    ids = k-way-merge over runs of the contiguous block [t]   // sorted path_hls
    cand = cand==null ? ids : intersect(cand, ids)            // sorted merge
    if empty(cand): return NO MATCHES ANYWHERE                // early out, no walk
for file in classify(wt):
    dirty/untracked      -> open+match
    path_hl(file) ∈ cand -> open+match     // binary search in cand
    else                 -> reject

• TREE memo is the JS win: the C tip-walk visits every leaf and memo-checks per blob; the tree row prunes whole unchanged directories — O(changed) walk on a warm index.
• Fresh postings buffer in RAM (typed-array sort at flush), flushed as one new run per search session; compaction folds runs when count exceeds the C ratio.
• API sketch (C twins: SPOTOpen, SPOTIndexFromTips, CAPOTri40, CAPOFlushRun, CAPOCompact):

open(repo)              // find + mmap .be/ *.spot.idx runs → idx {runs[], fresh}
close(idx)              // flush fresh as ONE new run; compact past the 1/8 ratio
ent(type, off40, hl20)  // pack; entType/entOff/entHl unpack — SPOT-002 side
                        //  never touches raw entries
trigrams(needle)        // RON64 trigram set, CAPOTri40 packing; null when no
                        //  3-char run → no filter (full scan)
pathHl(relpath)         // the 20-bit full-path hash, ONE fn: postings+memos+gate
ensure(idx, ref)        // lazy tip-walk AT SEARCH TIME: TREE hit → prune subtree,
                        //  BLOB hit → skip blob, else store-read + tok.parse →
                        //  TRI postings + BLOB row; TREE row on subtree complete
candidates(idx, tris)   // the filtering algo above; tris is CNF — AND-list of
                        //  OR-clauses of trigrams (flat needle → singleton
                        //  clauses; regex fold from [/todo/DOG/DOG-022] → real
                        //  clauses); OR = union of blocks, AND = intersect;
                        //  [] = no match anywhere, null = unfiltered
gate(cand, step)        // classify verdict → SCAN | REJECT: dirty/untracked
                        //  always SCAN; clean tracked → binsearch pathHl in cand

• View flow: open → ensure(ref) → candidates(needle) → classify walk with gate, survivors' hunks go to SPOT-002 scan → close persists what the walk learned (next search starts warm). fresh joins candidates as just another run — results never depend on flush timing; a killed session loses warmth, never correctness.
• Rename cost accepted (matches C): a moved file/dir re-indexes under its new path hash; stale entries under the old path linger as false positives — harmless, the index is a reject-filter, never truth.
• 20-bit path hashes are filter-grade (~1/1M collisions): a posting collision only costs a wasted open; a memo-pair collision could wrongly skip indexing — same exposure C accepts with BLOBFN.

TODOs

• wh64 pack/unpack + TRI/BLOB/TREE type constants, one shared module (abc.index u64 lane IS the wh64 substrate)
• run file writer/reader + merged sorted iteration + compaction (abc compact(), 1/8 ratio, *spot.idx family)
• lazy tip-walk: TREE prune, BLOB skip → TRI emit — DEVIATION: trigrams come off a byte-level RON64-run scan, not tok.parse (superset-safe: never ext-gates an unknown-lexer file into a wrong REJECT; identical set for identifier content)
• trigram extraction + candidates() intersection → path-hash set (CNF, early-out)
• classify-driven scan gate: dirty/untracked always SCAN; clean tracked binsearch
• bro right-click → spot://WT/path#token nav; result hunks via window — blocked on SPOT-002 landing (parallel wt), the search.js integration is the join point
• parseURI: .ext / subtree scope from the PATH slot — same join point, with SPOT-002
• repro: golden — cold-indexes/warm-prunes (walk counts), new-session persistence, blob-at-new-path + moved-subtree (memo pair legs), dirty-edit-with-stale-index, edit-dedup growth

Blockers and bummers

• Regex-locator trigram extraction blocks on /todo/DOG/DOG-022 (RXLITS → dog/tok + tok._rx_lits binding); until it lands, /re/ needles run unfiltered (full scan) — correct, just slow.
• View wiring (candidates/gate into search.js) + right-click blocked on SPOT-002 landing; index layer is standalone-complete.
• /wiki/View.mkd §"Search views" still shows the stale fragment-.ext form — hand edit on landing.

Outcome

• Staged (put only, NOT posted) in //SPOT-003 on base //SPOT/#9928a0be: shared/spotidx.js; test sub: test/spotidx.js + CMakeLists.txt registration (be-js-unit-spotidx).
• Worker suite 305/306; the one red is pre-existing be-js-work-getctx (the retired-get pty click, known from WORK-007's side-find). Orchestrator re-ran test/spotidx.js 2026-07-19: OK.
• Suggested commit: SPOT-003: shared/spotidx.js lazy trigram reject-filter + golden test