nx_wiki_bm25_search.nx source
↩ module page · 359 lines · 16390 B
1// nx_wiki_bm25_search.nx -- RANKED (BM25) wiki search that ALSO searches the
2// no-link-rot archive, unifying the live wiki doc corpus with the
3// content-addressed archive blobs toward the Nishi Library.
4//
5// THE UPGRADE (wiki R3): the wiki's prior onsite ranker (nx_search_onsite_engine)
6// scored by AND-presence + count-of-matched-terms -- it could not tell a
7// SUBSTANTIVE page from a thin one that merely mentions the term. This module
8// scores by what each document ACTUALLY CONTAINS via Okapi BM25 (term frequency
9// SATURATED by k1, LENGTH-NORMALIZED by b, IDF-weighted), so a page that mentions
10// "sovereign" five times ranks ABOVE one that mentions it once. That is real
11// relevance ranking, not presence.
12//
13// REUSE, NOT REINVENT (the Library's BM25 engine):
14// runtime/nx_bm25.nx -- the canonical sovereign Okapi BM25 (Q16.16 via fx.nx),
15// genealogy robertson_sparck-jones_bm25. It shares the
16// SAME FNV-1a tokenizer as nx_search_inverted (the wiki
17// index), so wiki-doc scoring and index tokenization
18// agree by construction. nx_bm25_score() takes doc-text
19// pointers + lengths + query terms and writes a Q16.16
20// score per doc. We hand it the doc-store bodies and the
21// archive blob bodies, then sort by descending score.
22//
23// THE ARCHIVE UNIFICATION (no-link-rot content is searchable too):
24// The no-rot archive (nx_wiki_archive.nx) stores each page's bytes under
25// wikiblob:<cid> in the seg_store at prefix knowledge/store/wikiarchive-. The
26// seg_store ALREADY term-indexes every value (nx_seg_store.nx ss_build_terms),
27// so ss_term(handle, term) returns the KEYS (wikiblob:<cid>) of archived blobs
28// whose body contains the term. We fold those archive hits in: for each blob
29// key found, recover its <cid>, fetch the body via war_get_by_cid, BM25-score
30// it in the SAME corpus, and merge it into the ranked list. So a term that
31// lives ONLY in the archive (never in the live doc store) is still found.
32//
33// SEPARATION: this module owns BM25 ranking + archive folding. It does NOT own
34// HTTP/render (hub primitives) or the index lifecycle (the site builds the
35// store). It is a pure scorer/merger over caller-provided corpora.
36//
37// IMPORTS: de-duped by module identity. nx_search_inverted imports syscalls.nx
38// which is an alias-stub that splices nx_syscalls.nx (path-dedup, no dup
39// symbols); nx_bm25 / nx_seg_store / nx_wiki_archive import nx_syscalls.nx
40// directly -> all resolve to the one canonical syscall shelf. Single import of
41// each module here.
42// Pure NishiLang, NO SQL, NO .sh/.py/.js, no new .tsv/.conf. license_tier: ORIGINAL
43
44import "nx_syscalls.nx"
45import "nx_bm25.nx"
46import "nx_seg_store.nx"
47import "wiki/nx_wiki_archive.nx"
48import "wiki/nx_wiki_index_builder.nx"
49
50// ===== Sealed verdict surface (codes 2700-2719) =================================================
51const NX_WBS_OK: i64 = 0
52const NX_WBS_BAD_INPUT: i64 = 2700
53const NX_WBS_CORPUS_OVERFLOW: i64 = 2701
54const NX_WBS_TERMS_OVERFLOW: i64 = 2702
55
56// ===== Named sizing constants (M7 no magic numbers) =================================================
57const NX_WBS_MAX_CORPUS: i64 = 4096 // total docs scored per query (wiki + archive)
58const NX_WBS_MAX_QTERMS: i64 = 32 // per nx_search query-term cap
59const NX_WBS_ARCH_SCAN_CAP: i64 = 256 // seg_store manifest segment-scan cap
60const NX_WBS_BLOB_PREFIX_N: i64 = 9 // strlen("wikiblob:")
61const NX_WBS_CID_LEN: i64 = 69 // strlen("nxc1-" + 64 hex)
62const NX_WBS_ARCH_HITS_CAP: i64 = 1024 // per-term archive key hits buffer
63
64// ===== Result kinds (so the resolver knows where a ranked row lives) =================================================
65const NX_WBS_SRC_DOC: i64 = 0 // a live wiki doc-store rowid
66const NX_WBS_SRC_ARCHIVE: i64 = 1 // an archive blob (body recovered by CID)
67
68// ===== NxWikiRanked: the merged, score-sorted result set =================================================
69//
70// Parallel arrays, caller-allocated (cap NX_WBS_MAX_CORPUS). For each ranked
71// row i: kinds[i] says doc vs archive; rowids[i] is the doc-store rowid (DOC) or
72// the archive corpus slot (ARCHIVE); scores[i] is the Q16.16 BM25 score;
73// body_ptrs[i]/body_lens[i] point at the scored body (so the resolver can build
74// title/url/snippet without re-fetching).
75
76struct NxWikiRanked {
77 kinds: *i64
78 rowids: *i64
79 scores: *i64
80 body_ptrs: *i64
81 body_lens: *i64
82 count: i64
83 cap: i64
84 valid: i64
85}
86
87func nx_wiki_ranked_init(r: *NxWikiRanked, cap: i64) -> i64 {
88 if (r as i64) == 0 { return 0 - NX_WBS_BAD_INPUT }
89 if cap < 1 { return 0 - NX_WBS_BAD_INPUT }
90 if cap > NX_WBS_MAX_CORPUS { return 0 - NX_WBS_BAD_INPUT }
91 r.kinds = sys_mmap(cap * 8) as *i64
92 r.rowids = sys_mmap(cap * 8) as *i64
93 r.scores = sys_mmap(cap * 8) as *i64
94 r.body_ptrs = sys_mmap(cap * 8) as *i64
95 r.body_lens = sys_mmap(cap * 8) as *i64
96 r.count = 0
97 r.cap = cap
98 r.valid = 1
99 return NX_WBS_OK
100}
101
102func nx_wiki_ranked_count(r: *NxWikiRanked) -> i64 {
103 if r.valid != 1 { return 0 }
104 return r.count
105}
106
107func nx_wiki_ranked_rowid_at(r: *NxWikiRanked, i: i64) -> i64 {
108 if r.valid != 1 { return 0 - 1 }
109 if i < 0 { return 0 - 1 }
110 if i >= r.count { return 0 - 1 }
111 return r.rowids[i]
112}
113
114func nx_wiki_ranked_score_at(r: *NxWikiRanked, i: i64) -> i64 {
115 if r.valid != 1 { return 0 }
116 if i < 0 { return 0 }
117 if i >= r.count { return 0 }
118 return r.scores[i]
119}
120
121func nx_wiki_ranked_kind_at(r: *NxWikiRanked, i: i64) -> i64 {
122 if r.valid != 1 { return 0 - 1 }
123 if i < 0 { return 0 - 1 }
124 if i >= r.count { return 0 - 1 }
125 return r.kinds[i]
126}
127
128// ===== byte-equal over a fixed length =================================================
129func nx_wbs_bytes_eq(a: *u8, b: *u8, n: i64) -> i64 {
130 var i: i64 = 0
131 var eq: i64 = 1
132 while i < n {
133 if a[i] != b[i] { eq = 0 }
134 i = i + 1
135 }
136 return eq
137}
138
139// ===== Collect ARCHIVE blob bodies that contain ANY query term =================================================
140//
141// For each query term, ss_term over the archive store returns the KEYS of blobs
142// whose CURRENT value contains the term. Archive keys are either wikiblob:<cid>
143// (the page bytes -- what we want) or wikicid:<slug> (a pointer to a cid string;
144// skipped). For each NEW wikiblob:<cid> key seen, recover the cid and fetch the
145// body via war_get_by_cid, appending (body_ptr, body_len, cid-as-rowid-surrogate)
146// into the parallel out arrays. De-dups blob keys across terms so a blob with two
147// query terms is scored once. Returns the number of distinct archive bodies
148// gathered (>= 0), or a negative verdict.
149//
150// out_bodies / out_lens : caller-allocated (cap NX_WBS_MAX_CORPUS) -- receive the
151// archive blob body pointer + length.
152// seen_keys / seen_n : caller scratch holding the wikiblob keys already taken
153// (pointer + key length) for O(n^2) small-n de-dup.
154
155func nx_wbs_gather_archive(prefix: *u8,
156 q_terms: **u8, q_lens: *i64, nterms: i64,
157 out_bodies: *i64, out_lens: *i64, out_cap: i64) -> i64 {
158 if nterms <= 0 { return 0 }
159 if nterms > NX_WBS_MAX_QTERMS { return 0 - NX_WBS_TERMS_OVERFLOW }
160
161 // ss_open_cached -- the seg_store CLASS fix, promoted into the primitive 2026-07-30. ss_open reads
162 // EVERY live segment into anonymous RAM and there is NO ss_close in the tree, so opening PER QUERY
163 // leaks the whole archive shard per query. That is the exact fingerprint nx_seg_store's own header
164 // measured at ~23.6 GiB across nine long-lived organs, "which drove swap to 92.3% and the box into
165 // sustained thrash" -- and this search path is reached once per wiki query on a LIVE daemon.
166 // Handle semantics are identical (every ss_hget / ss_term reader below is untouched); invalidation is
167 // the manifest (st_size, st_mtime), so a live edit is still picked up on the next call; and it is
168 // fail-open -- a full cache table falls back to a plain ss_open rather than refusing.
169 let h: *i64 = ss_open_cached(prefix)
170 if (h as i64) == 0 { return 0 } // empty/absent archive -> zero hits (well-defined)
171
172 // de-dup scratch: pointers+lens of wikiblob keys already accepted
173 let seen_ptr: *i64 = sys_mmap(8 * NX_WBS_ARCH_HITS_CAP) as *i64
174 let seen_len: *i64 = sys_mmap(8 * NX_WBS_ARCH_HITS_CAP) as *i64
175 var nseen: i64 = 0
176
177 // per-term hit buffers (ss_term fills key ptr/len pairs)
178 let kpout: *i64 = sys_mmap(8 * NX_WBS_ARCH_HITS_CAP) as *i64
179 let klout: *i64 = sys_mmap(8 * NX_WBS_ARCH_HITS_CAP) as *i64
180
181 let blobpfx: *u8 = "wikiblob:" as *u8
182
183 var ngot: i64 = 0
184 var t: i64 = 0
185 while t < nterms {
186 // ss_term tokenizes lowercased alnum runs; query terms are already such.
187 // A term that 0-hits or an old-format segment (-2) simply contributes
188 // nothing; we never fail the whole search on a single sparse term.
189 let m: i64 = ss_term(h, q_terms[t], kpout, klout, NX_WBS_ARCH_HITS_CAP)
190 if m > 0 {
191 var i: i64 = 0
192 while i < m {
193 let kp: *u8 = kpout[i] as *u8
194 let kl: i64 = klout[i]
195 // accept ONLY wikiblob:<cid> keys (skip wikicid:<slug> pointers)
196 var is_blob: i64 = 0
197 if kl == NX_WBS_BLOB_PREFIX_N + NX_WBS_CID_LEN {
198 if nx_wbs_bytes_eq(kp, blobpfx, NX_WBS_BLOB_PREFIX_N) == 1 { is_blob = 1 }
199 }
200 if is_blob == 1 {
201 // de-dup against already-accepted blob keys
202 var dup: i64 = 0
203 var s: i64 = 0
204 while s < nseen {
205 if seen_len[s] == kl {
206 if nx_wbs_bytes_eq(seen_ptr[s] as *u8, kp, kl) == 1 { dup = 1 }
207 }
208 s = s + 1
209 }
210 if dup == 0 {
211 if nseen < NX_WBS_ARCH_HITS_CAP {
212 seen_ptr[nseen] = kp as i64
213 seen_len[nseen] = kl
214 nseen = nseen + 1
215 }
216 // recover the cid (NUL-terminated) and fetch the body
217 if ngot < out_cap {
218 let cid: *u8 = sys_mmap(80)
219 var c: i64 = 0
220 while c < NX_WBS_CID_LEN {
221 cid[c] = kp[NX_WBS_BLOB_PREFIX_N + c]
222 c = c + 1
223 }
224 cid[NX_WBS_CID_LEN] = 0 as u8
225 let bptr: *i64 = sys_mmap(16) as *i64
226 let blen: i64 = war_get_by_cid(prefix, cid, bptr, NX_WBS_ARCH_SCAN_CAP)
227 if blen > 0 {
228 out_bodies[ngot] = bptr[0]
229 out_lens[ngot] = blen
230 ngot = ngot + 1
231 }
232 }
233 }
234 }
235 i = i + 1
236 }
237 }
238 t = t + 1
239 }
240 return ngot
241}
242
243// ===== TOP-LEVEL: rank the live doc store + archive by BM25, merged =================================================
244//
245// Builds one unified corpus = [ all live doc-store bodies ] ++ [ archive blob
246// bodies that contain a query term ], BM25-scores the WHOLE corpus together
247// (so doc and archive scores are directly comparable -- same IDF over the same
248// N, same avgdl), then selection-sorts the survivors (score > 0) by descending
249// score into the caller's NxWikiRanked. A doc with zero query-term hits scores
250// 0 and is dropped. Stable tie-break: lower corpus index first (doc-store rows
251// precede archive rows, mirroring "live page beats its own archived copy").
252//
253// REUSE: scoring is nx_bm25_score (the Library BM25). This function only
254// assembles the corpus, calls it, and orders the output.
255
256func nx_wiki_bm25_rank(store: *NxWikiDocStore, archive_prefix: *u8,
257 q_terms: **u8, q_lens: *i64, nterms: i64,
258 out: *NxWikiRanked, max_results: i64) -> i64 {
259 if (store as i64) == 0 { return 0 - NX_WBS_BAD_INPUT }
260 if store.valid != 1 { return 0 - NX_WBS_BAD_INPUT }
261 if out.valid != 1 { return 0 - NX_WBS_BAD_INPUT }
262 if nterms < 0 { return 0 - NX_WBS_BAD_INPUT }
263 if nterms > NX_WBS_MAX_QTERMS { return 0 - NX_WBS_TERMS_OVERFLOW }
264 out.count = 0
265 if nterms == 0 { return NX_WBS_OK } // empty query -> zero results, well-defined
266
267 let ndoc: i64 = store.doc_count
268 // corpus arrays: doc bodies first, then archive bodies
269 let texts: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
270 let blens: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
271 let kinds: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
272 let srcrow: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64 // doc rowid OR archive slot
273
274 var ncorp: i64 = 0
275 var d: i64 = 0
276 while d < ndoc {
277 if ncorp < NX_WBS_MAX_CORPUS {
278 texts[ncorp] = (store.bodies_pool as i64) + store.bodies_offs[d]
279 blens[ncorp] = store.bodies_lens[d]
280 kinds[ncorp] = NX_WBS_SRC_DOC
281 srcrow[ncorp] = d
282 ncorp = ncorp + 1
283 }
284 d = d + 1
285 }
286
287 // fold in archive blob bodies that contain a query term
288 if (archive_prefix as i64) != 0 {
289 let abodies: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
290 let alens: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
291 let room: i64 = NX_WBS_MAX_CORPUS - ncorp
292 let na: i64 = nx_wbs_gather_archive(archive_prefix, q_terms, q_lens, nterms,
293 abodies, alens, room)
294 if na > 0 {
295 var a: i64 = 0
296 while a < na {
297 if ncorp < NX_WBS_MAX_CORPUS {
298 texts[ncorp] = abodies[a]
299 blens[ncorp] = alens[a]
300 kinds[ncorp] = NX_WBS_SRC_ARCHIVE
301 srcrow[ncorp] = a // archive slot index (resolver fetches by body ptr)
302 ncorp = ncorp + 1
303 }
304 a = a + 1
305 }
306 }
307 }
308
309 if ncorp == 0 { return NX_WBS_OK }
310
311 // BM25-score the unified corpus (REUSE nx_bm25_score; Q16.16 scores)
312 let scores: *i64 = sys_mmap(8 * ncorp) as *i64
313 nx_bm25_score(texts as **u8, blens, ncorp,
314 q_terms, q_lens, nterms, scores)
315
316 // selection-sort survivors (score > 0) by DESCENDING score into `out`.
317 // small N (wiki corpora are hundreds, not millions); correctness over speed.
318 let taken: *u8 = sys_mmap(ncorp + 8)
319 var k: i64 = 0
320 while k < ncorp { taken[k] = 0 as u8; k = k + 1 }
321
322 var emitted: i64 = 0
323 var cap: i64 = max_results
324 if cap > out.cap { cap = out.cap }
325 var pass: i64 = 0
326 while pass < cap {
327 // find the highest-scoring, not-yet-taken, strictly-positive doc;
328 // ties resolve to the LOWEST corpus index (stable, doc-before-archive).
329 var best: i64 = 0 - 1
330 var bestscore: i64 = 0
331 var i: i64 = 0
332 while i < ncorp {
333 if taken[i] == (0 as u8) {
334 let sc: i64 = scores[i]
335 if sc > 0 {
336 if best < 0 {
337 best = i; bestscore = sc
338 } else {
339 if sc > bestscore { best = i; bestscore = sc }
340 }
341 }
342 }
343 i = i + 1
344 }
345 if best < 0 { pass = cap } // no more positive survivors
346 if best >= 0 {
347 taken[best] = 1 as u8
348 out.kinds[emitted] = kinds[best]
349 out.rowids[emitted] = srcrow[best]
350 out.scores[emitted] = bestscore
351 out.body_ptrs[emitted] = texts[best]
352 out.body_lens[emitted] = blens[best]
353 emitted = emitted + 1
354 pass = pass + 1
355 }
356 }
357 out.count = emitted
358 return NX_WBS_OK
359}