nx_wiki_bm25_search.nx source
↩ module page · 351 lines · 15568 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 let h: *i64 = ss_open(prefix)
162 if (h as i64) == 0 { return 0 } // empty/absent archive -> zero hits (well-defined)
163
164 // de-dup scratch: pointers+lens of wikiblob keys already accepted
165 let seen_ptr: *i64 = sys_mmap(8 * NX_WBS_ARCH_HITS_CAP) as *i64
166 let seen_len: *i64 = sys_mmap(8 * NX_WBS_ARCH_HITS_CAP) as *i64
167 var nseen: i64 = 0
168
169 // per-term hit buffers (ss_term fills key ptr/len pairs)
170 let kpout: *i64 = sys_mmap(8 * NX_WBS_ARCH_HITS_CAP) as *i64
171 let klout: *i64 = sys_mmap(8 * NX_WBS_ARCH_HITS_CAP) as *i64
172
173 let blobpfx: *u8 = "wikiblob:" as *u8
174
175 var ngot: i64 = 0
176 var t: i64 = 0
177 while t < nterms {
178 // ss_term tokenizes lowercased alnum runs; query terms are already such.
179 // A term that 0-hits or an old-format segment (-2) simply contributes
180 // nothing; we never fail the whole search on a single sparse term.
181 let m: i64 = ss_term(h, q_terms[t], kpout, klout, NX_WBS_ARCH_HITS_CAP)
182 if m > 0 {
183 var i: i64 = 0
184 while i < m {
185 let kp: *u8 = kpout[i] as *u8
186 let kl: i64 = klout[i]
187 // accept ONLY wikiblob:<cid> keys (skip wikicid:<slug> pointers)
188 var is_blob: i64 = 0
189 if kl == NX_WBS_BLOB_PREFIX_N + NX_WBS_CID_LEN {
190 if nx_wbs_bytes_eq(kp, blobpfx, NX_WBS_BLOB_PREFIX_N) == 1 { is_blob = 1 }
191 }
192 if is_blob == 1 {
193 // de-dup against already-accepted blob keys
194 var dup: i64 = 0
195 var s: i64 = 0
196 while s < nseen {
197 if seen_len[s] == kl {
198 if nx_wbs_bytes_eq(seen_ptr[s] as *u8, kp, kl) == 1 { dup = 1 }
199 }
200 s = s + 1
201 }
202 if dup == 0 {
203 if nseen < NX_WBS_ARCH_HITS_CAP {
204 seen_ptr[nseen] = kp as i64
205 seen_len[nseen] = kl
206 nseen = nseen + 1
207 }
208 // recover the cid (NUL-terminated) and fetch the body
209 if ngot < out_cap {
210 let cid: *u8 = sys_mmap(80)
211 var c: i64 = 0
212 while c < NX_WBS_CID_LEN {
213 cid[c] = kp[NX_WBS_BLOB_PREFIX_N + c]
214 c = c + 1
215 }
216 cid[NX_WBS_CID_LEN] = 0 as u8
217 let bptr: *i64 = sys_mmap(16) as *i64
218 let blen: i64 = war_get_by_cid(prefix, cid, bptr, NX_WBS_ARCH_SCAN_CAP)
219 if blen > 0 {
220 out_bodies[ngot] = bptr[0]
221 out_lens[ngot] = blen
222 ngot = ngot + 1
223 }
224 }
225 }
226 }
227 i = i + 1
228 }
229 }
230 t = t + 1
231 }
232 return ngot
233}
234
235// ===== TOP-LEVEL: rank the live doc store + archive by BM25, merged =================================================
236//
237// Builds one unified corpus = [ all live doc-store bodies ] ++ [ archive blob
238// bodies that contain a query term ], BM25-scores the WHOLE corpus together
239// (so doc and archive scores are directly comparable -- same IDF over the same
240// N, same avgdl), then selection-sorts the survivors (score > 0) by descending
241// score into the caller's NxWikiRanked. A doc with zero query-term hits scores
242// 0 and is dropped. Stable tie-break: lower corpus index first (doc-store rows
243// precede archive rows, mirroring "live page beats its own archived copy").
244//
245// REUSE: scoring is nx_bm25_score (the Library BM25). This function only
246// assembles the corpus, calls it, and orders the output.
247
248func nx_wiki_bm25_rank(store: *NxWikiDocStore, archive_prefix: *u8,
249 q_terms: **u8, q_lens: *i64, nterms: i64,
250 out: *NxWikiRanked, max_results: i64) -> i64 {
251 if (store as i64) == 0 { return 0 - NX_WBS_BAD_INPUT }
252 if store.valid != 1 { return 0 - NX_WBS_BAD_INPUT }
253 if out.valid != 1 { return 0 - NX_WBS_BAD_INPUT }
254 if nterms < 0 { return 0 - NX_WBS_BAD_INPUT }
255 if nterms > NX_WBS_MAX_QTERMS { return 0 - NX_WBS_TERMS_OVERFLOW }
256 out.count = 0
257 if nterms == 0 { return NX_WBS_OK } // empty query -> zero results, well-defined
258
259 let ndoc: i64 = store.doc_count
260 // corpus arrays: doc bodies first, then archive bodies
261 let texts: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
262 let blens: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
263 let kinds: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
264 let srcrow: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64 // doc rowid OR archive slot
265
266 var ncorp: i64 = 0
267 var d: i64 = 0
268 while d < ndoc {
269 if ncorp < NX_WBS_MAX_CORPUS {
270 texts[ncorp] = (store.bodies_pool as i64) + store.bodies_offs[d]
271 blens[ncorp] = store.bodies_lens[d]
272 kinds[ncorp] = NX_WBS_SRC_DOC
273 srcrow[ncorp] = d
274 ncorp = ncorp + 1
275 }
276 d = d + 1
277 }
278
279 // fold in archive blob bodies that contain a query term
280 if (archive_prefix as i64) != 0 {
281 let abodies: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
282 let alens: *i64 = sys_mmap(8 * NX_WBS_MAX_CORPUS) as *i64
283 let room: i64 = NX_WBS_MAX_CORPUS - ncorp
284 let na: i64 = nx_wbs_gather_archive(archive_prefix, q_terms, q_lens, nterms,
285 abodies, alens, room)
286 if na > 0 {
287 var a: i64 = 0
288 while a < na {
289 if ncorp < NX_WBS_MAX_CORPUS {
290 texts[ncorp] = abodies[a]
291 blens[ncorp] = alens[a]
292 kinds[ncorp] = NX_WBS_SRC_ARCHIVE
293 srcrow[ncorp] = a // archive slot index (resolver fetches by body ptr)
294 ncorp = ncorp + 1
295 }
296 a = a + 1
297 }
298 }
299 }
300
301 if ncorp == 0 { return NX_WBS_OK }
302
303 // BM25-score the unified corpus (REUSE nx_bm25_score; Q16.16 scores)
304 let scores: *i64 = sys_mmap(8 * ncorp) as *i64
305 nx_bm25_score(texts as **u8, blens, ncorp,
306 q_terms, q_lens, nterms, scores)
307
308 // selection-sort survivors (score > 0) by DESCENDING score into `out`.
309 // small N (wiki corpora are hundreds, not millions); correctness over speed.
310 let taken: *u8 = sys_mmap(ncorp + 8)
311 var k: i64 = 0
312 while k < ncorp { taken[k] = 0 as u8; k = k + 1 }
313
314 var emitted: i64 = 0
315 var cap: i64 = max_results
316 if cap > out.cap { cap = out.cap }
317 var pass: i64 = 0
318 while pass < cap {
319 // find the highest-scoring, not-yet-taken, strictly-positive doc;
320 // ties resolve to the LOWEST corpus index (stable, doc-before-archive).
321 var best: i64 = 0 - 1
322 var bestscore: i64 = 0
323 var i: i64 = 0
324 while i < ncorp {
325 if taken[i] == (0 as u8) {
326 let sc: i64 = scores[i]
327 if sc > 0 {
328 if best < 0 {
329 best = i; bestscore = sc
330 } else {
331 if sc > bestscore { best = i; bestscore = sc }
332 }
333 }
334 }
335 i = i + 1
336 }
337 if best < 0 { pass = cap } // no more positive survivors
338 if best >= 0 {
339 taken[best] = 1 as u8
340 out.kinds[emitted] = kinds[best]
341 out.rowids[emitted] = srcrow[best]
342 out.scores[emitted] = bestscore
343 out.body_ptrs[emitted] = texts[best]
344 out.body_lens[emitted] = blens[best]
345 emitted = emitted + 1
346 pass = pass + 1
347 }
348 }
349 out.count = emitted
350 return NX_WBS_OK
351}