nx_search_linear.nx source
↩ module page · 221 lines · 8410 B
1// nx_search_linear.nx -- substring search over JSONL catalogs.
2//
3// module: nishi-core.search.linear
4// depends: nishi-core.io.syscalls
5// disk_kb: 4
6// capability: CORE_IO
7// wired_status: FULLY_WIRED
8//
9// license_tier: PUBLIC_NISHI_SUBSTRATE
10// genealogy_id: linear_scan_grep_tradition +
11// tfidf_information_retrieval_salton_1971 +
12// nishi_build_the_system_cardinal_2026
13//
14// Bits-up "search engine" Brick #1: linear scan with substring
15// matching + TF-style score (count of query occurrences in each row).
16// O(N * M) where N = file size, M = query length. Adequate for
17// up to ~1M-row JSONL catalogs at <1s qemu-rv64 / <50ms native.
18//
19// Future: inverted-index primitive over the same JSONL (queued as
20// nx_search_inverted) for sub-millisecond random access at scale.
21//
22// This primitive composes against any JSONL catalog produced by
23// nx_ingest_batch -- including but not limited to fixtures/gbif_bulk/
24// ingested_bulk.jsonl (10K+ GBIF Backbone Taxonomy records).
25
26import "syscalls.nx"
27
28// ===== Verdict ====================================================
29
30const NX_SEARCH_OK: i64 = 1
31const NX_SEARCH_FILE_NOT_FOUND: i64 = 2
32const NX_SEARCH_NO_MATCHES: i64 = 3
33const NX_SEARCH_BAD_ARGS: i64 = 4
34
35func nx_search_verdict_name(v: i64) -> *u8 {
36 if v == NX_SEARCH_OK { return "OK" }
37 if v == NX_SEARCH_FILE_NOT_FOUND { return "FILE_NOT_FOUND" }
38 if v == NX_SEARCH_NO_MATCHES { return "NO_MATCHES" }
39 if v == NX_SEARCH_BAD_ARGS { return "BAD_ARGS" }
40 return "UNKNOWN"
41}
42
43// ===== SearchMatch (one row per hit) ==============================
44
45struct NxSearchMatch {
46 match_hk: i64,
47 row_index: i64, // 0-based line number in the JSONL
48 row_offset: i64, // byte offset of the row's first byte
49 row_len: i64, // bytes including newline
50 row_ptr: *u8, // pointer into source bytes (zero-copy)
51 score: i64, // count of query occurrences in row
52}
53
54const NX_SEARCH_MATCH_BYTES: i64 = 48 // 6 fields * 8 bytes
55
56// ===== Search report ==============================================
57
58struct NxSearchReport {
59 report_hk: i64,
60 rows_scanned: i64,
61 rows_matched: i64,
62 bytes_scanned: i64,
63 total_score: i64,
64 truncated_to_cap: i64, // 1 if matches exceeded out_capacity
65 verdict: i64,
66}
67
68const NX_SEARCH_REPORT_BYTES: i64 = 56 // 7 fields * 8 bytes
69
70// ===== Substring counter (bounded per JPL Rule 2) =================
71
72const NX_SEARCH_MAX_SCAN_BYTES: i64 = 4294967296 // 4 GiB
73
74func nx_search_count_substring_in_range(
75 bytes: *u8,
76 start: i64,
77 end: i64,
78 needle: *u8,
79 needle_len: i64
80) -> i64 {
81 let span: i64 = end - start
82 if span < needle_len { return 0 }
83 if needle_len <= 0 { return 0 }
84 let limit: i64 = end - needle_len
85 var i: i64 = start
86 var iter: i64 = 0
87 var verdict: i64 = 0
88 var count: i64 = 0
89 while verdict == 0 && iter < NX_SEARCH_MAX_SCAN_BYTES {
90 if i > limit { verdict = 1 }
91 if verdict == 0 {
92 var j: i64 = 0
93 var inner_iter: i64 = 0
94 var inner_verdict: i64 = 0
95 var matched: i64 = 1
96 while inner_verdict == 0 && inner_iter < needle_len {
97 if bytes[i + j] != needle[j] { matched = 0; inner_verdict = 1 }
98 if inner_verdict == 0 { j = j + 1; inner_iter = inner_iter + 1 }
99 }
100 if matched == 1 { count = count + 1 }
101 i = i + 1
102 iter = iter + 1
103 }
104 }
105 return count
106}
107
108// ===== Linear scan over a JSONL file ==============================
109//
110// Reads the file at path, walks line-by-line, for each non-empty
111// line counts query occurrences; emits a NxSearchMatch when count > 0.
112// Caller supplies out_matches array + capacity + report buffer.
113// Truncates emission at out_capacity but continues scanning to keep
114// rows_scanned + rows_matched honest.
115
116func nx_search_linear_search(
117 jsonl_path: *u8,
118 query_ptr: *u8,
119 query_len: i64,
120 out_matches: *NxSearchMatch,
121 out_capacity: i64,
122 out_report: *NxSearchReport
123) -> i64 {
124 if out_report == 0 as *NxSearchReport { return NX_SEARCH_BAD_ARGS }
125 out_report.report_hk = 0
126 out_report.rows_scanned = 0
127 out_report.rows_matched = 0
128 out_report.bytes_scanned = 0
129 out_report.total_score = 0
130 out_report.truncated_to_cap = 0
131 out_report.verdict = NX_SEARCH_OK
132
133 if jsonl_path == 0 as *u8 { out_report.verdict = NX_SEARCH_BAD_ARGS; return NX_SEARCH_BAD_ARGS }
134 if query_ptr == 0 as *u8 { out_report.verdict = NX_SEARCH_BAD_ARGS; return NX_SEARCH_BAD_ARGS }
135 if query_len <= 0 { out_report.verdict = NX_SEARCH_BAD_ARGS; return NX_SEARCH_BAD_ARGS }
136
137 let lenbox: *u8 = sys_mmap(8)
138 let lp: *i64 = lenbox as *i64
139 let bytes: *u8 = sys_read_file(jsonl_path, lp)
140 if bytes == 0 as *u8 {
141 out_report.verdict = NX_SEARCH_FILE_NOT_FOUND
142 return NX_SEARCH_FILE_NOT_FOUND
143 }
144 let total_len: i64 = *lp
145 out_report.bytes_scanned = total_len
146
147 var row_start: i64 = 0
148 var i: i64 = 0
149 var iter: i64 = 0
150 var verdict: i64 = 0
151 var row_idx: i64 = 0
152 while verdict == 0 && iter < NX_SEARCH_MAX_SCAN_BYTES {
153 if i >= total_len { verdict = 1 }
154 if verdict == 0 {
155 if bytes[i] == 0x0A {
156 // line covers [row_start, i)
157 let row_len: i64 = i - row_start
158 if row_len > 0 {
159 let count: i64 = nx_search_count_substring_in_range(
160 bytes, row_start, i, query_ptr, query_len)
161 if count > 0 {
162 out_report.rows_matched = out_report.rows_matched + 1
163 out_report.total_score = out_report.total_score + count
164 if out_report.rows_matched <= out_capacity {
165 let mp: i64 = (out_matches as i64) + (out_report.rows_matched - 1) * NX_SEARCH_MATCH_BYTES
166 let m: *NxSearchMatch = mp as *NxSearchMatch
167 m.match_hk = 0
168 m.row_index = row_idx
169 m.row_offset = row_start
170 m.row_len = row_len
171 m.row_ptr = ((bytes as i64) + row_start) as *u8
172 m.score = count
173 }
174 if out_report.rows_matched > out_capacity {
175 out_report.truncated_to_cap = 1
176 }
177 }
178 out_report.rows_scanned = out_report.rows_scanned + 1
179 row_idx = row_idx + 1
180 }
181 row_start = i + 1
182 }
183 i = i + 1
184 iter = iter + 1
185 }
186 }
187 // Handle final non-newline-terminated row.
188 if row_start < total_len {
189 let row_len: i64 = total_len - row_start
190 let count: i64 = nx_search_count_substring_in_range(
191 bytes, row_start, total_len, query_ptr, query_len)
192 if count > 0 {
193 out_report.rows_matched = out_report.rows_matched + 1
194 out_report.total_score = out_report.total_score + count
195 if out_report.rows_matched <= out_capacity {
196 let mp: i64 = (out_matches as i64) + (out_report.rows_matched - 1) * NX_SEARCH_MATCH_BYTES
197 let m: *NxSearchMatch = mp as *NxSearchMatch
198 m.match_hk = 0
199 m.row_index = row_idx
200 m.row_offset = row_start
201 m.row_len = row_len
202 m.row_ptr = ((bytes as i64) + row_start) as *u8
203 m.score = count
204 }
205 }
206 out_report.rows_scanned = out_report.rows_scanned + 1
207 }
208
209 if out_report.rows_matched == 0 {
210 out_report.verdict = NX_SEARCH_NO_MATCHES
211 return NX_SEARCH_NO_MATCHES
212 }
213 out_report.verdict = NX_SEARCH_OK
214 return NX_SEARCH_OK
215}
216
217// ===== Accessor helpers ===========================================
218
219func nx_search_match_at(matches: *NxSearchMatch, idx: i64) -> *NxSearchMatch {
220 return ((matches as i64) + idx * NX_SEARCH_MATCH_BYTES) as *NxSearchMatch
221}