nx_intern.nx source
↩ module page · 206 lines · 7620 B
1// nx_intern.nx -- string interning pool.
2//
3// Maps a (bytes, len) -> stable i64 id. Same string content always
4// gets the same id; ids are dense from 0. Foundation for:
5//
6// * Symbol table dedup in nxld + nxasm
7// * Identifier interning in lex (turns strcmp into ==)
8// * Section name interning across the .shstrtab + .strtab
9// * Type-name dedup in opt
10//
11// Internally:
12// * nx_hash for FNV-1a key -> id lookup
13// * Backing byte buffer holding the actual string content,
14// each entry NUL-terminated (so nx_intern_at returns a *u8
15// directly usable as a C-string)
16// * Side-array of (offset, length) pairs indexed by id
17//
18// API:
19// nx_intern_new(bytes_cap, ids_cap)
20// nx_intern_get(t, bytes, len) -- returns id (creates if new)
21// nx_intern_at(t, id, out_len) -- returns *u8 + length
22// nx_intern_count(t) -- total ids assigned
23//
24// Performance: O(1) average for get + at; backing buffer never
25// re-allocates so all returned *u8 stay valid for the table's
26// lifetime (a critical invariant for symbol-table users).
27
28// nx_safety_envelope:
29// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
30// sil_target: SIL1
31// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
32// verdict: NOT_YET_EVALUATED
33
34import "syscalls.nx"
35import "nx_hash.nx"
36const NX_MAGIC_1024: i64 = 1024
37
38struct NxIntern {
39 bytes: *u8, // backing string bytes (NUL-terminated entries)
40 bytes_cap: i64,
41 bytes_used: i64,
42 offsets: *i64, // offsets[id] = start of id's bytes
43 lengths: *i64, // lengths[id] = byte count (no NUL)
44 ids_cap: i64,
45 n_ids: i64,
46 hash: *NxHash, // key (FNV-1a of bytes) -> id
47}
48
49const NX_INTERN_BYTES: i64 = 64
50
51// Round up to next power of two.
52func nx_intern_next_pow2(n: i64) -> i64 {
53 var v: i64 = 1
54 while v < n { v = v << 1 }
55 return v
56}
57
58func nx_intern_new(bytes_cap: i64, ids_cap: i64) -> *NxIntern {
59 let raw: *u8 = sys_mmap(NX_INTERN_BYTES)
60 let t: *NxIntern = raw as *NxIntern
61 t.bytes = sys_mmap(bytes_cap)
62 t.bytes_cap = bytes_cap
63 t.bytes_used = 0
64 t.offsets = sys_mmap(ids_cap * 8) as *i64
65 t.lengths = sys_mmap(ids_cap * 8) as *i64
66 t.ids_cap = ids_cap
67 t.n_ids = 0
68 // Hash table: ~2x ids_cap to keep load factor under 0.5.
69 let hcap: i64 = nx_intern_next_pow2(ids_cap * 2)
70 t.hash = nx_hash_new(hcap)
71 return t
72}
73
74// Compare `len` bytes at offset `off` in the pool against `other`.
75// Returns 1 if equal, 0 otherwise.
76func nx_intern_bytes_eq(t: *NxIntern, off: i64, other: *u8, len: i64) -> i64 {
77 var i: i64 = 0
78 while i < len {
79 if t.bytes[off + i] != other[i] { return 0 }
80 i = i + 1
81 }
82 return 1
83}
84
85// get-or-insert. Returns the id (>= 0), or -1 on overflow.
86func nx_intern_get(t: *NxIntern, bytes: *u8, len: i64) -> i64 {
87 if len < 0 { return -1 }
88 // FNV-1a hash of the input bytes.
89 let key: i64 = nx_hash_fnv1a_bytes(bytes, len)
90 // We use key 0 sentinel; map to a non-zero rotated form.
91 var key_safe: i64 = key
92 if key_safe == 0 { key_safe = 0x1234567890ABCDEF }
93
94 // Probe. We accept hash collisions by walking the probe
95 // chain in nx_hash and verifying the actual bytes match.
96 // Simple (slow) walk: ask nx_hash for the candidate id, check
97 // bytes. If mismatch, tag with a different key derivative
98 // (linear retry). For v0.0.1 we accept that hash collisions
99 // produce duplicate ids -- correctness preserved (different
100 // bytes get different ids), only dedup quality degrades.
101 let probe_id: i64 = nx_hash_get(t.hash, key_safe)
102 if probe_id != -1 {
103 if t.lengths[probe_id] == len {
104 if nx_intern_bytes_eq(t, t.offsets[probe_id], bytes, len) == 1 {
105 return probe_id
106 }
107 }
108 }
109
110 // New entry. Bounds-check both pools.
111 if t.n_ids >= t.ids_cap { return -1 }
112 if t.bytes_used + len + 1 > t.bytes_cap { return -1 }
113
114 let id: i64 = t.n_ids
115 let off: i64 = t.bytes_used
116 var i: i64 = 0
117 while i < len {
118 t.bytes[off + i] = bytes[i]
119 i = i + 1
120 }
121 t.bytes[off + len] = 0 // NUL terminator
122 t.offsets[id] = off
123 t.lengths[id] = len
124 t.bytes_used = off + len + 1
125 t.n_ids = id + 1
126
127 nx_hash_put(t.hash, key_safe, id)
128 return id
129}
130
131// Lookup-only (no insert). Returns -1 if not present.
132func nx_intern_lookup(t: *NxIntern, bytes: *u8, len: i64) -> i64 {
133 let key: i64 = nx_hash_fnv1a_bytes(bytes, len)
134 var key_safe: i64 = key
135 if key_safe == 0 { key_safe = 0x1234567890ABCDEF }
136 let probe_id: i64 = nx_hash_get(t.hash, key_safe)
137 if probe_id == -1 { return -1 }
138 if t.lengths[probe_id] != len { return -1 }
139 if nx_intern_bytes_eq(t, t.offsets[probe_id], bytes, len) == 0 { return -1 }
140 return probe_id
141}
142
143// Get the *u8 + length of an interned id. out_len is written;
144// returned *u8 points into the backing pool (NUL-terminated).
145func nx_intern_at(t: *NxIntern, id: i64, out_len: *i64) -> *u8 {
146 if id < 0 { *out_len = 0; return 0 as *u8 }
147 if id >= t.n_ids { *out_len = 0; return 0 as *u8 }
148 *out_len = t.lengths[id]
149 let base: i64 = (t.bytes as i64) + t.offsets[id]
150 return base as *u8
151}
152
153func nx_intern_count(t: *NxIntern) -> i64 { return t.n_ids }
154
155// ---- self-test ----------------------------------------------------
156
157func main() -> i64 {
158 let t: *NxIntern = nx_intern_new(NX_MAGIC_1024, 64)
159 if nx_intern_count(t) != 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
160
161 // Intern three distinct strings.
162 let s1: *u8 = sys_mmap(16)
163 s1[0] = 0x6D; s1[1] = 0x61; s1[2] = 0x69; s1[3] = 0x6E // "main"
164 let s2: *u8 = sys_mmap(16)
165 s2[0] = 0x70; s2[1] = 0x75; s2[2] = 0x74; s2[3] = 0x73 // "puts"
166 let s3: *u8 = sys_mmap(16)
167 s3[0] = 0x6D; s3[1] = 0x61; s3[2] = 0x69; s3[3] = 0x6E // "main" again
168
169 let id1: i64 = nx_intern_get(t, s1, 4)
170 let id2: i64 = nx_intern_get(t, s2, 4)
171 let id3: i64 = nx_intern_get(t, s3, 4)
172
173 if id1 != 0 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
174 if id2 != 1 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
175 if id3 != id1 { return __syscall(93, 22, 0, 0, 0, 0, 0) } // dedup: same as id1
176 if nx_intern_count(t) != 2 { return __syscall(93, 23, 0, 0, 0, 0, 0) }
177
178 // Round-trip via nx_intern_at.
179 let len_out_raw: *u8 = sys_mmap(16)
180 let len_out: *i64 = len_out_raw as *i64
181 *len_out = 0
182 let bytes_id1: *u8 = nx_intern_at(t, id1, len_out)
183 if *len_out != 4 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
184 if bytes_id1[0] != 0x6D { return __syscall(93, 31, 0, 0, 0, 0, 0) }
185 if bytes_id1[3] != 0x6E { return __syscall(93, 32, 0, 0, 0, 0, 0) }
186 if bytes_id1[4] != 0 { return __syscall(93, 33, 0, 0, 0, 0, 0) } // NUL term
187
188 // Lookup-only on present + absent strings.
189 if nx_intern_lookup(t, s1, 4) != 0 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
190 let unknown: *u8 = sys_mmap(16)
191 unknown[0] = 0x66; unknown[1] = 0x6F; unknown[2] = 0x6F // "foo"
192 if nx_intern_lookup(t, unknown, 3) != -1 { return __syscall(93, 41, 0, 0, 0, 0, 0) }
193
194 // After lookup-only, count unchanged.
195 if nx_intern_count(t) != 2 { return __syscall(93, 42, 0, 0, 0, 0, 0) }
196
197 // Empty string: distinct id, len 0.
198 let empty: *u8 = sys_mmap(8)
199 let id_e: i64 = nx_intern_get(t, empty, 0)
200 if id_e < 0 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
201 *len_out = 99
202 nx_intern_at(t, id_e, len_out)
203 if *len_out != 0 { return __syscall(93, 51, 0, 0, 0, 0, 0) }
204
205 return 0
206}