nx_search_snippet_extract.nx source
↩ module page · 298 lines · 11398 B
1// nx_search_snippet_extract.nx -- V1 search snippet extractor.
2// Context window around query-term matches + <mark>...</mark> highlight.
3//
4// COMPOSES (per NISHI_SMALL_SHARP_COMPOSABLE_STANDARD §4.1 M7):
5// hub/nx_search_query_parser (NxSearchQuery + iter accessors)
6// nx_html_escape (html_escape for safe emit)
7// nx_search_inverted (lowercase + token-char convention)
8//
9// COMPOSED BY:
10// wiki/nx_wiki_search_render (next commit)
11// (future) any site rendering search results
12//
13// Status: V1. 2026-05-27.
14//
15// WINNER-TIER: BASELINE-C provisional
16// INCUMBENTS: Lucene's PostingsHighlighter / FastVectorHighlighter,
17// Tantivy's SnippetGenerator, Bleve's SearchResult.Hit
18// Fragments, Whoosh's whoosh.highlight, Algolia's
19// _snippetResult
20// NUMBERS: V1 ships first-match-centered window + per-term
21// <mark>; paired latency bench vs Lucene Postings-
22// Highlighter pending real workload
23// GAP: Lucene picks densest-cluster window (more relevant
24// snippet); V1 picks first-match (simpler, deterministic).
25// V2 ships densest-cluster scorer.
26// PLAN: M-next: V2 cluster-density window picker per
27// charter §5.2
28// EXEMPTION REASON: n/a; provisional pending measurement
29//
30// V1 SCOPE per NISHI_SEARCH_CHARTER.md §5.1:
31// - Caller-allocated output buffer
32// - Case-insensitive term matching (ASCII lowercase fold)
33// - Window: NX_SSE_WIN_BEFORE bytes before first match +
34// NX_SSE_WIN_AFTER bytes after; clipped to doc bounds
35// - Each query-term occurrence inside the window wrapped in
36// <mark>...</mark>; rest of bytes html_escape'd
37// - "..." prefix/suffix when window doesn't reach doc bounds
38// - Empty doc + empty query both well-defined (no error)
39//
40// V2 SCOPE (TODO):
41// - Densest-cluster window picker (more terms per snippet)
42// - Multi-snippet emit (top-K per doc)
43// - UTF-8 codepoint awareness (no mid-codepoint truncation)
44// - Word-boundary clipping (no mid-word "...")
45
46import "nx_syscalls.nx"
47import "nx_search_query_parser.nx"
48import "nx_search_inverted.nx"
49import "nx_html_escape.nx"
50
51// ===== Sealed verdict surface (codes 1700-1709) =================================================
52const NX_SSE_OK: i64 = 0
53const NX_SSE_BAD_INPUT: i64 = 1700
54const NX_SSE_OUTPUT_OVERFLOW: i64 = 1701
55const NX_SSE_DOC_TOO_LARGE: i64 = 1702
56const NX_SSE_LOOP_BUDGET: i64 = 1703
57const NX_SSE_ESCAPE_FAIL: i64 = 1704
58const NX_SSE_NOT_IMPLEMENTED: i64 = 1705
59
60// ===== Named sizing constants (M7) =================================================
61const NX_SSE_WIN_BEFORE: i64 = 64
62const NX_SSE_WIN_AFTER: i64 = 192
63const NX_SSE_DEFAULT_OUTPUT_CAP: i64 = 2048
64const NX_SSE_MAX_DOC_BYTES: i64 = 1048576 // 1 MB cap per snippet input
65const NX_SSE_LOOP_BUDGET_CAP: i64 = 10000000
66const NX_SSE_ELLIPSIS: *u8 = "..." as *u8
67const NX_SSE_ELLIPSIS_N: i64 = 3
68const NX_SSE_MARK_OPEN: *u8 = "<mark>" as *u8
69const NX_SSE_MARK_OPEN_N: i64 = 6
70const NX_SSE_MARK_CLOSE: *u8 = "</mark>" as *u8
71const NX_SSE_MARK_CLOSE_N: i64 = 7
72const NX_SSE_MAX_TERMS_CONSIDER: i64 = 32
73
74// ===== ASCII lowercase fold helper =================================================
75
76func nx_sse_lower(c: i64) -> i64 {
77 if c >= 0x41 { if c <= 0x5A { return c + 32 } }
78 return c
79}
80
81// ===== Case-insensitive substring match at position =================================================
82//
83// Returns 1 if src[pos..pos+term_n] case-insensitively equals term;
84// 0 otherwise. Bounded.
85
86func nx_sse_match_at(src: *u8, src_n: i64, pos: i64,
87 term: *u8, term_n: i64) -> i64 {
88 if pos < 0 { return 0 }
89 if term_n < 1 { return 0 }
90 if pos + term_n > src_n { return 0 }
91 var i: i64 = 0
92 while i < term_n {
93 if i >= NX_SQP_MAX_TERM_LEN { return 0 }
94 let sc: i64 = nx_sse_lower(src[pos + i] as i64)
95 let tc: i64 = nx_sse_lower(term[i] as i64)
96 if sc != tc { return 0 }
97 i = i + 1
98 }
99 return 1
100}
101
102// ===== Find first match of any query term in source =================================================
103//
104// Returns position of earliest match (>= 0) or -1 if no term matches.
105// Bounded by src_n + n_terms iterations.
106
107func nx_sse_find_first_match(src: *u8, src_n: i64,
108 q: *NxSearchQuery) -> i64 {
109 if src_n < 1 { return 0 - 1 }
110 if q.valid != 1 { return 0 - 1 }
111 let n_terms: i64 = nx_search_query_count(q)
112 if n_terms < 1 { return 0 - 1 }
113
114 var pos: i64 = 0
115 var iter: i64 = 0
116 while pos < src_n {
117 if iter >= NX_SSE_LOOP_BUDGET_CAP { return 0 - 1 }
118 iter = iter + 1
119 var ti: i64 = 0
120 while ti < n_terms {
121 if ti >= NX_SSE_MAX_TERMS_CONSIDER { ti = n_terms + 1 }
122 if ti < n_terms {
123 let term_ptr_out: *i64 = (sys_mmap(8)) as *i64
124 let term_len_out: *i64 = (sys_mmap(8)) as *i64
125 term_ptr_out[0] = 0
126 term_len_out[0] = 0
127 let rc: i64 = nx_search_query_term_at(q, ti, term_ptr_out, term_len_out)
128 if rc == NX_SQP_OK {
129 let tp: *u8 = term_ptr_out[0] as *u8
130 let tn: i64 = term_len_out[0]
131 if nx_sse_match_at(src, src_n, pos, tp, tn) == 1 {
132 return pos
133 }
134 }
135 ti = ti + 1
136 }
137 }
138 pos = pos + 1
139 }
140 return 0 - 1
141}
142
143// ===== Check if pos starts a match for ANY query term =================================================
144//
145// Returns the matched term length (>0) or 0 if no term matches.
146// Used by emit loop to wrap matches in <mark>.
147
148func nx_sse_match_len_at(src: *u8, src_n: i64, pos: i64,
149 q: *NxSearchQuery) -> i64 {
150 if q.valid != 1 { return 0 }
151 let n_terms: i64 = nx_search_query_count(q)
152 if n_terms < 1 { return 0 }
153 var ti: i64 = 0
154 while ti < n_terms {
155 if ti >= NX_SSE_MAX_TERMS_CONSIDER { return 0 }
156 let term_ptr_out: *i64 = (sys_mmap(8)) as *i64
157 let term_len_out: *i64 = (sys_mmap(8)) as *i64
158 term_ptr_out[0] = 0
159 term_len_out[0] = 0
160 let rc: i64 = nx_search_query_term_at(q, ti, term_ptr_out, term_len_out)
161 if rc == NX_SQP_OK {
162 let tp: *u8 = term_ptr_out[0] as *u8
163 let tn: i64 = term_len_out[0]
164 if nx_sse_match_at(src, src_n, pos, tp, tn) == 1 {
165 return tn
166 }
167 }
168 ti = ti + 1
169 }
170 return 0
171}
172
173// ===== Append raw bytes to output (bounded) =================================================
174
175func nx_sse_put_raw(out: *u8, cap: i64, off: i64,
176 src: *u8, n: i64) -> i64 {
177 if off < 0 { return 0 - NX_SSE_BAD_INPUT }
178 if off + n > cap { return 0 - NX_SSE_OUTPUT_OVERFLOW }
179 var i: i64 = 0
180 while i < n {
181 if i >= NX_SSE_MAX_DOC_BYTES { return 0 - NX_SSE_OUTPUT_OVERFLOW }
182 out[off + i] = src[i]
183 i = i + 1
184 }
185 return off + n
186}
187
188// ===== Append html-escaped bytes to output =================================================
189
190func nx_sse_put_escaped(out: *u8, cap: i64, off: i64,
191 src: *u8, n: i64) -> i64 {
192 if off < 0 { return 0 - NX_SSE_BAD_INPUT }
193 if n < 1 { return off }
194 if cap - off < n * 6 + 1 { return 0 - NX_SSE_OUTPUT_OVERFLOW } // worst-case & = 5x
195 let written: i64 = html_escape((out as i64 + off) as *u8, cap - off, src, n)
196 if written < 0 { return 0 - NX_SSE_ESCAPE_FAIL }
197 return off + written
198}
199
200// ===== Top-level: extract a snippet =================================================
201//
202// Output format example:
203// "...the hygiene <mark>standard</mark> defines ten bug classes..."
204
205func nx_search_snippet_extract(out: *u8, out_cap: i64,
206 src: *u8, src_n: i64,
207 q: *NxSearchQuery,
208 out_len_p: *i64) -> i64 {
209 if (out as i64) == 0 { return 0 - NX_SSE_BAD_INPUT }
210 if (src as i64) == 0 { return 0 - NX_SSE_BAD_INPUT }
211 if (q as i64) == 0 { return 0 - NX_SSE_BAD_INPUT }
212 if (out_len_p as i64) == 0 { return 0 - NX_SSE_BAD_INPUT }
213 if out_cap < NX_SSE_DEFAULT_OUTPUT_CAP / 4 { return 0 - NX_SSE_OUTPUT_OVERFLOW }
214 if src_n < 0 { return 0 - NX_SSE_BAD_INPUT }
215 if src_n > NX_SSE_MAX_DOC_BYTES { return 0 - NX_SSE_DOC_TOO_LARGE }
216
217 out_len_p[0] = 0
218 if src_n == 0 {
219 // Empty doc: emit empty snippet.
220 return NX_SSE_OK
221 }
222
223 let first_match: i64 = nx_sse_find_first_match(src, src_n, q)
224
225 // Compute window bounds.
226 var win_start: i64 = 0
227 var win_end: i64 = src_n
228 if first_match >= 0 {
229 win_start = first_match - NX_SSE_WIN_BEFORE
230 if win_start < 0 { win_start = 0 }
231 win_end = first_match + NX_SSE_WIN_AFTER
232 if win_end > src_n { win_end = src_n }
233 }
234 // No match found: emit doc-start window (first NX_SSE_WIN_AFTER bytes).
235 if first_match < 0 {
236 win_start = 0
237 win_end = NX_SSE_WIN_AFTER
238 if win_end > src_n { win_end = src_n }
239 }
240
241 var off: i64 = 0
242
243 // Leading "..." if window doesn't start at doc-start.
244 if win_start > 0 {
245 let r: i64 = nx_sse_put_raw(out, out_cap, off,
246 NX_SSE_ELLIPSIS, NX_SSE_ELLIPSIS_N)
247 if r < 0 { return r }
248 off = r
249 }
250
251 // Walk window byte-by-byte; wrap matches in <mark>; escape rest.
252 var pos: i64 = win_start
253 var iter: i64 = 0
254 while pos < win_end {
255 if iter >= NX_SSE_LOOP_BUDGET_CAP { return 0 - NX_SSE_LOOP_BUDGET }
256 iter = iter + 1
257
258 let mlen: i64 = nx_sse_match_len_at(src, src_n, pos, q)
259 if mlen > 0 {
260 // Emit <mark>...</mark> around the matched span.
261 let r1: i64 = nx_sse_put_raw(out, out_cap, off,
262 NX_SSE_MARK_OPEN, NX_SSE_MARK_OPEN_N)
263 if r1 < 0 { return r1 }
264 off = r1
265 // Match span itself: html-escape (in case term contains '<' etc).
266 let term_src: *u8 = (src as i64 + pos) as *u8
267 var emit_n: i64 = mlen
268 if pos + emit_n > win_end { emit_n = win_end - pos }
269 let r2: i64 = nx_sse_put_escaped(out, out_cap, off, term_src, emit_n)
270 if r2 < 0 { return r2 }
271 off = r2
272 let r3: i64 = nx_sse_put_raw(out, out_cap, off,
273 NX_SSE_MARK_CLOSE, NX_SSE_MARK_CLOSE_N)
274 if r3 < 0 { return r3 }
275 off = r3
276 pos = pos + mlen
277 }
278 if mlen == 0 {
279 // Single byte; escape it.
280 let byte_src: *u8 = (src as i64 + pos) as *u8
281 let r: i64 = nx_sse_put_escaped(out, out_cap, off, byte_src, 1)
282 if r < 0 { return r }
283 off = r
284 pos = pos + 1
285 }
286 }
287
288 // Trailing "..." if window doesn't reach doc-end.
289 if win_end < src_n {
290 let r: i64 = nx_sse_put_raw(out, out_cap, off,
291 NX_SSE_ELLIPSIS, NX_SSE_ELLIPSIS_N)
292 if r < 0 { return r }
293 off = r
294 }
295
296 out_len_p[0] = off
297 return NX_SSE_OK
298}