nx_record.nx source
↩ module page · 365 lines · 15160 B
1// nx_record.nx -- NXR1: the TYPED, SELF-DESCRIBING record encoding for sovereign planes.
2//
3// WHY THIS EXISTS (debt seq1326). The TSV->plane migration moved the CONTAINER, not the ENCODING:
4// nx_store_seed_lib stores each flat LINE as an opaque blob under a POSITIONAL key q:<seq> and is
5// contractually required to rebuild the flat file byte-identically. So a "migrated" plane still holds
6// tab-delimited untyped text. A plane-ified TSV is still a TSV. Its failure modes are structural, not
7// sloppiness: a TAB inside a value corrupts the row; a record missing one column SHIFTS THE MEANING OF
8// EVERY COLUMN AFTER IT (the live debt- plane already carries mixed 5-col and 7-col rows); there are no
9// types, so every reader re-parses text and hopes; and there is no way to add a field without rewriting
10// every existing record.
11//
12// NXR1 fixes all four AT THE REPRESENTATION, which is the only place they can be fixed:
13// - FIELD IDS, not positions -> a missing field is simply absent. It cannot shift its neighbours.
14// - LENGTH-PREFIXED values -> a tab, a newline, a NUL inside a value is just bytes. No escaping,
15// no quoting, no delimiter to collide with.
16// - EXPLICIT TYPES -> i64 is stored as i64, not as text a reader must trust.
17// - SKIP-UNKNOWN + DEFAULTS -> a reader steps over field ids it does not know (forward compatible,
18// rule 19 at the DATA layer), and an absent field reads as a caller
19// default. That is Iceberg v3's default-value semantics: a new column
20// costs zero backfill.
21//
22// LAYOUT (big-endian throughout, matching the seg-store's on-disk convention):
23// record: ['N']['X']['R']['1'] [u16 nfields] then nfields x field
24// field: [u16 field_id] [u8 type] [u32 len] [len bytes]
25//
26// This is a LEAF: it imports nx_syscalls ONLY. A record codec that had to pull in the storage engine
27// just to read a u32 would be backwards -- the record layer sits UNDER the store, not beside it.
28// license_tier: ORIGINAL No hw writes (Rule 26).
29import "nx_syscalls.nx"
30
31const NXR_MAGIC_N: i64 = 78
32const NXR_MAGIC_X: i64 = 88
33const NXR_MAGIC_R: i64 = 82
34const NXR_MAGIC_1: i64 = 49
35const NXR_HDR: i64 = 6 // magic(4) + u16 field count
36const NXR_FHDR: i64 = 7 // field id(2) + type(1) + len(4)
37const NXR_T_I64: i64 = 1
38const NXR_T_STR: i64 = 2
39const NXR_T_BYTES: i64 = 3
40const NXR_T_BOOL: i64 = 4
41const NXR_I64_BYTES: i64 = 8
42const NXR_ABSENT: i64 = 0
43const NXR_FOUND: i64 = 1
44const NXR_MAXF: i64 = 4096 // sanity bound on field count (fail-closed, never a silent cap)
45const NXR_OUTS_BYTES: i64 = 32 // scratch cell for the 3 out-params
46const NXR_BYTE_MASK: i64 = 255
47const NXR_SHIFT56: i64 = 56
48
49func nxr_w16(p: *u8, off: i64, v: i64) -> i64 {
50 p[off] = ((v >> 8) & NXR_BYTE_MASK) as u8
51 p[off + 1] = (v & NXR_BYTE_MASK) as u8
52 return off + 2
53}
54func nxr_r16(p: *u8, off: i64) -> i64 {
55 let a: i64 = p[off]
56 let b: i64 = p[off + 1]
57 return (a << 8) | b
58}
59func nxr_w32(p: *u8, off: i64, v: i64) -> i64 {
60 p[off] = ((v >> 24) & NXR_BYTE_MASK) as u8
61 p[off + 1] = ((v >> 16) & NXR_BYTE_MASK) as u8
62 p[off + 2] = ((v >> 8) & NXR_BYTE_MASK) as u8
63 p[off + 3] = (v & NXR_BYTE_MASK) as u8
64 return off + 4
65}
66func nxr_r32(p: *u8, off: i64) -> i64 {
67 let a: i64 = p[off]
68 let b: i64 = p[off + 1]
69 let c: i64 = p[off + 2]
70 let d: i64 = p[off + 3]
71 return (a << 24) | (b << 16) | (c << 8) | d
72}
73func nxr_w64(p: *u8, off: i64, v: i64) -> i64 {
74 var i: i64 = 0
75 while i < NXR_I64_BYTES {
76 p[off + i] = ((v >> (NXR_SHIFT56 - 8 * i)) & NXR_BYTE_MASK) as u8
77 i = i + 1
78 }
79 return off + NXR_I64_BYTES
80}
81func nxr_r64(p: *u8, off: i64) -> i64 {
82 var v: i64 = 0
83 var i: i64 = 0
84 while i < NXR_I64_BYTES {
85 let c: i64 = p[off + i]
86 v = (v << 8) | c
87 i = i + 1
88 }
89 return v
90}
91
92// start a record: magic + zero field count. returns the write offset.
93func nxr_init(b: *u8) -> i64 {
94 b[0] = NXR_MAGIC_N as u8
95 b[1] = NXR_MAGIC_X as u8
96 b[2] = NXR_MAGIC_R as u8
97 b[3] = NXR_MAGIC_1 as u8
98 nxr_w16(b, 4, 0)
99 return NXR_HDR
100}
101
102// append one field of arbitrary bytes; bumps the header count. returns the new offset.
103// vlen is written explicitly, so the value may contain ANY byte -- tab, newline, NUL.
104func nxr_add(b: *u8, off: i64, fid: i64, ty: i64, val: *u8, vlen: i64) -> i64 {
105 var o: i64 = off
106 o = nxr_w16(b, o, fid)
107 b[o] = ty as u8
108 o = o + 1
109 o = nxr_w32(b, o, vlen)
110 var i: i64 = 0
111 while i < vlen {
112 b[o + i] = val[i]
113 i = i + 1
114 }
115 o = o + vlen
116 nxr_w16(b, 4, nxr_r16(b, 4) + 1)
117 return o
118}
119
120// append a typed i64 field (stored as 8 big-endian bytes, never as text).
121func nxr_add_i64(b: *u8, off: i64, fid: i64, v: i64) -> i64 {
122 var o: i64 = off
123 o = nxr_w16(b, o, fid)
124 b[o] = NXR_T_I64 as u8
125 o = o + 1
126 o = nxr_w32(b, o, NXR_I64_BYTES)
127 o = nxr_w64(b, o, v)
128 nxr_w16(b, 4, nxr_r16(b, 4) + 1)
129 return o
130}
131
132func nxr_count(b: *u8) -> i64 { return nxr_r16(b, 4) }
133
134// FAIL-CLOSED structural validation: magic, a sane field count, and every field header AND value must
135// fit inside n. A truncated or corrupt record is REFUSED WHOLE -- it is never partially read, because a
136// partially-read record is exactly how a positional format silently hands back shifted data.
137func nxr_valid(b: *u8, n: i64) -> i64 {
138 if n < NXR_HDR { return 0 }
139 if (b[0] as i64) != NXR_MAGIC_N { return 0 }
140 if (b[1] as i64) != NXR_MAGIC_X { return 0 }
141 if (b[2] as i64) != NXR_MAGIC_R { return 0 }
142 if (b[3] as i64) != NXR_MAGIC_1 { return 0 }
143 let nf: i64 = nxr_r16(b, 4)
144 if nf > NXR_MAXF { return 0 }
145 var o: i64 = NXR_HDR
146 var i: i64 = 0
147 var ok: i64 = 1
148 while i < nf {
149 if o + NXR_FHDR > n { ok = 0; i = nf } else {
150 let vl: i64 = nxr_r32(b, o + 3)
151 if vl < 0 { ok = 0; i = nf } else {
152 if o + NXR_FHDR + vl > n { ok = 0; i = nf } else {
153 o = o + NXR_FHDR + vl
154 i = i + 1
155 }
156 }
157 }
158 }
159 return ok
160}
161
162// locate a field BY ID. outs[0]=value offset, outs[1]=len, outs[2]=type.
163// Returns NXR_ABSENT when the field is not present -- ABSENCE IS NORMAL, NOT AN ERROR. That is what
164// makes schema evolution free, and it is precisely why a record missing a field can never shift the
165// meaning of the fields around it. Unknown ids are stepped over by their own length, so a reader built
166// today reads a record written by a newer writer without knowing its new fields.
167func nxr_find(b: *u8, n: i64, fid: i64, outs: *i64) -> i64 {
168 if nxr_valid(b, n) == 0 { return NXR_ABSENT }
169 let nf: i64 = nxr_r16(b, 4)
170 var o: i64 = NXR_HDR
171 var i: i64 = 0
172 var got: i64 = NXR_ABSENT
173 while i < nf {
174 let id: i64 = nxr_r16(b, o)
175 let ty: i64 = b[o + 2]
176 let vl: i64 = nxr_r32(b, o + 3)
177 if id == fid {
178 outs[0] = o + NXR_FHDR
179 outs[1] = vl
180 outs[2] = ty
181 got = NXR_FOUND
182 i = nf
183 } else {
184 o = o + NXR_FHDR + vl
185 i = i + 1
186 }
187 }
188 return got
189}
190
191// i64 accessor with a caller DEFAULT for an absent field (Iceberg v3 default-value semantics: adding a
192// column costs zero backfill). Type-checked: a field that is present but NOT an i64 yields the default
193// rather than a reinterpreted byte range.
194func nxr_get_i64(b: *u8, n: i64, fid: i64, defval: i64) -> i64 {
195 let outs: *i64 = sys_mmap(NXR_OUTS_BYTES) as *i64
196 var r: i64 = defval
197 if nxr_find(b, n, fid, outs) == NXR_FOUND {
198 if outs[2] == NXR_T_I64 {
199 if outs[1] == NXR_I64_BYTES { r = nxr_r64(b, outs[0]) }
200 }
201 }
202 sys_munmap(outs as *u8, NXR_OUTS_BYTES)
203 return r
204}
205
206// ---------------------------------------------------------------------------
207// NXR1-X -- THE RANDOM-ACCESS DIRECTORY (rung 3, added 2026-08-08).
208//
209// WHY. nxr_find walks the fields linearly, so one lookup costs O(nfields) and reading k fields costs
210// O(k*nfields). That is the ONE axis where NXR1 sat BEHIND the July-2026 state of the art: Cap'n Proto,
211// FlatBuffers and Arrow all reach ANY field without traversing the fields before it. Our evolution
212// semantics (skip-unknown + caller defaults) already matched Avro and Iceberg v3; random access did not.
213//
214// SHAPE. The directory goes at the TAIL -- the same choice Parquet makes for its footer and ZIP makes for
215// its central directory, for the same reason: a writer streams the payload first and only then knows
216// where everything landed, so a LEADING directory would force either two passes or a reserved hole.
217//
218// [ ...NXR1 fields... ][ nfields x (u16 fid, u32 field_off), sorted by fid ][ u32 idx_off ]['N']['X']['R']['X']
219//
220// BACKWARD COMPATIBLE BY CONSTRUCTION. nxr_valid only ever required each field to FIT within n; it never
221// required the fields to FILL n. So a sealed record still validates, and nxr_find still walks it correctly
222// while ignoring the tail. Sealing is OPTIONAL and an unsealed record stays legal.
223//
224// THE LINEAR PATH IS KEPT, NOT REPLACED. nxr_find remains the brute-force ORACLE that the gate
225// cross-checks the binary search against. Deleting it would leave the fast path with nothing independent
226// to be wrong against, which is how a fast path ships agreeing only with itself.
227//
228// FAIL-CLOSED. A trailer is believed ONLY when the directory exactly accounts for the tail
229// (idx_off + nfields*NXR_IDXENT + NXR_TRAILER == n). A record whose last four bytes happen to spell the
230// magic but whose arithmetic does not reconcile is treated as UNSEALED and read linearly -- never as a
231// directory of garbage offsets.
232// ---------------------------------------------------------------------------
233const NXR_IDXENT: i64 = 6 // u16 field id + u32 absolute field offset
234const NXR_TRAILER: i64 = 8 // u32 idx_off + 4 magic bytes
235const NXR_NOIDX: i64 = 0 - 1
236
237// ROW LINEAGE (Iceberg v3 semantics, GA 2026-05-07): a row carries a stable identity and the sequence
238// number of the commit that last updated it. Reserved HIGH ids so they can never collide with a
239// TSV-bridged column -- nx_record_tsv maps column i -> field id i+1, bounded by RTV_MAXCOL (512).
240const NXR_FID_ROW_ID: i64 = 65024
241const NXR_FID_SEQ: i64 = 65025
242
243// SEAL a finished record: append the sorted directory + trailer. Returns the new total length.
244// The caller's buffer must have nfields*NXR_IDXENT + NXR_TRAILER bytes of room beyond off.
245func nxr_seal(b: *u8, off: i64) -> i64 {
246 let nf: i64 = nxr_r16(b, 4)
247 let idx: i64 = off
248 var o: i64 = NXR_HDR
249 var i: i64 = 0
250 while i < nf {
251 let id: i64 = nxr_r16(b, o)
252 let vl: i64 = nxr_r32(b, o + 3)
253 nxr_w16(b, idx + i * NXR_IDXENT, id)
254 nxr_w32(b, idx + i * NXR_IDXENT + 2, o)
255 o = o + NXR_FHDR + vl
256 i = i + 1
257 }
258 // Insertion sort by field id. nf is bounded by NXR_MAXF and records are small, so the simple sort is
259 // the right complexity budget: the win being bought here is the READ path, not the write path.
260 var a: i64 = 1
261 while a < nf {
262 let kf: i64 = nxr_r16(b, idx + a * NXR_IDXENT)
263 let ko: i64 = nxr_r32(b, idx + a * NXR_IDXENT + 2)
264 var j: i64 = a - 1
265 var placed: i64 = 0
266 while placed == 0 {
267 if j < 0 { placed = 1 } else {
268 if nxr_r16(b, idx + j * NXR_IDXENT) <= kf { placed = 1 } else {
269 nxr_w16(b, idx + (j + 1) * NXR_IDXENT, nxr_r16(b, idx + j * NXR_IDXENT))
270 nxr_w32(b, idx + (j + 1) * NXR_IDXENT + 2, nxr_r32(b, idx + j * NXR_IDXENT + 2))
271 j = j - 1
272 }
273 }
274 }
275 nxr_w16(b, idx + (j + 1) * NXR_IDXENT, kf)
276 nxr_w32(b, idx + (j + 1) * NXR_IDXENT + 2, ko)
277 a = a + 1
278 }
279 var t: i64 = idx + nf * NXR_IDXENT
280 t = nxr_w32(b, t, idx)
281 b[t] = NXR_MAGIC_N as u8
282 b[t + 1] = NXR_MAGIC_X as u8
283 b[t + 2] = NXR_MAGIC_R as u8
284 b[t + 3] = NXR_MAGIC_X as u8
285 return t + 4
286}
287
288// Resolve the directory offset, or NXR_NOIDX when this record is not CREDIBLY sealed.
289func nxr_idx_off(b: *u8, n: i64) -> i64 {
290 if n < NXR_HDR + NXR_TRAILER { return NXR_NOIDX }
291 if (b[n - 4] as i64) != NXR_MAGIC_N { return NXR_NOIDX }
292 if (b[n - 3] as i64) != NXR_MAGIC_X { return NXR_NOIDX }
293 if (b[n - 2] as i64) != NXR_MAGIC_R { return NXR_NOIDX }
294 if (b[n - 1] as i64) != NXR_MAGIC_X { return NXR_NOIDX }
295 let io: i64 = nxr_r32(b, n - NXR_TRAILER)
296 let nf: i64 = nxr_r16(b, 4)
297 if io < NXR_HDR { return NXR_NOIDX }
298 if io + nf * NXR_IDXENT + NXR_TRAILER != n { return NXR_NOIDX }
299 return io
300}
301
302// Does this record carry a usable directory?
303func nxr_sealed(b: *u8, n: i64) -> i64 {
304 if nxr_idx_off(b, n) == NXR_NOIDX { return 0 }
305 return 1
306}
307
308// RANDOM-ACCESS find: O(log nfields) through the directory, falling back to the linear walk when the
309// record is unsealed. The CONTRACT IS IDENTICAL to nxr_find -- same outs, same NXR_FOUND/NXR_ABSENT --
310// which is what lets the gate assert the two paths agree field-for-field.
311func nxr_find_fast(b: *u8, n: i64, fid: i64, outs: *i64) -> i64 {
312 let io: i64 = nxr_idx_off(b, n)
313 if io == NXR_NOIDX { return nxr_find(b, n, fid, outs) }
314 if nxr_valid(b, io) == 0 { return NXR_ABSENT }
315 let nf: i64 = nxr_r16(b, 4)
316 var lo: i64 = 0
317 var hi: i64 = nf - 1
318 var got: i64 = NXR_ABSENT
319 var done: i64 = 0
320 while done == 0 {
321 if lo > hi { done = 1 } else {
322 let mid: i64 = (lo + hi) / 2
323 let id: i64 = nxr_r16(b, io + mid * NXR_IDXENT)
324 if id == fid {
325 let fo: i64 = nxr_r32(b, io + mid * NXR_IDXENT + 2)
326 let ty: i64 = b[fo + 2]
327 outs[0] = fo + NXR_FHDR
328 outs[1] = nxr_r32(b, fo + 3)
329 outs[2] = ty
330 got = NXR_FOUND
331 done = 1
332 } else {
333 if id < fid { lo = mid + 1 } else { hi = mid - 1 }
334 }
335 }
336 }
337 return got
338}
339
340// i64 accessor over the random-access path; identical default and type-check semantics to nxr_get_i64.
341func nxr_get_i64_fast(b: *u8, n: i64, fid: i64, defval: i64) -> i64 {
342 let outs: *i64 = sys_mmap(NXR_OUTS_BYTES) as *i64
343 var r: i64 = defval
344 if nxr_find_fast(b, n, fid, outs) == NXR_FOUND {
345 if outs[2] == NXR_T_I64 {
346 if outs[1] == NXR_I64_BYTES { r = nxr_r64(b, outs[0]) }
347 }
348 }
349 sys_munmap(outs as *u8, NXR_OUTS_BYTES)
350 return r
351}
352
353// ROW LINEAGE writers and readers.
354func nxr_add_lineage(b: *u8, off: i64, row_id: i64, seq: i64) -> i64 {
355 var o: i64 = off
356 o = nxr_add_i64(b, o, NXR_FID_ROW_ID, row_id)
357 o = nxr_add_i64(b, o, NXR_FID_SEQ, seq)
358 return o
359}
360func nxr_row_id(b: *u8, n: i64, defval: i64) -> i64 {
361 return nxr_get_i64_fast(b, n, NXR_FID_ROW_ID, defval)
362}
363func nxr_seq(b: *u8, n: i64, defval: i64) -> i64 {
364 return nxr_get_i64_fast(b, n, NXR_FID_SEQ, defval)
365}