nx_json.nx source
↩ module page · 306 lines · 12598 B
1// nx_json.nx -- JSON tokenizer (RFC 8259 subset).
2//
3// Streaming token-stream API: caller drives nx_json_next which
4// reports the next token kind + span within the input buffer.
5// A second pass (or the caller's own state machine) builds the
6// tree.
7//
8// Token kinds:
9// NX_JSON_LBRACE {
10// NX_JSON_RBRACE }
11// NX_JSON_LBRACKET [
12// NX_JSON_RBRACKET ]
13// NX_JSON_COMMA ,
14// NX_JSON_COLON :
15// NX_JSON_STRING "..." (span includes quotes)
16// NX_JSON_NUMBER -123.4e5 (span covers all digits + sign + exp)
17// NX_JSON_TRUE true
18// NX_JSON_FALSE false
19// NX_JSON_NULL null
20// NX_JSON_EOF end of input
21// NX_JSON_ERROR malformed input
22//
23// String content escapes (\n, \t, \uXXXX) are NOT decoded by the
24// tokenizer -- the span includes the raw bytes between the quotes.
25// A separate nx_pct-style decoder can be added later.
26//
27// nx_safety_envelope:
28// intended_use: "JSON decoder -- substrate-native parsing of
29// structured data per cardinal feedback-no-pdfs-
30// no-proprietary-binary-formats"
31// sil_target: SIL2 (input parsing; malformed JSON
32// must not crash callers)
33// asil_target: QM
34// dal_target: DAL C
35// evidence: [RFC_8259_canonical_basis, no_FP,
36// sealed_token_kind_enum,
37// bounded_recursion_depth]
38// hazard_register: [bug-tape-JSON-bomb-via-deep-nesting,
39// bug-tape-billion-laughs-style-amplification,
40// bug-tape-Unicode-escape-handling-bug]
41// residual_risk: "Nesting-depth caller-bounded. No
42// evaluation (no JSON5 / JSONnet); strict
43// RFC 8259 only."
44// verdict: NOT_YET_EVALUATED
45
46import "nx_syscalls.nx"
47import "nx_lex.nx"
48import "nx_ascii.nx"
49
50const NX_JSON_LBRACE: i64 = 1
51const NX_JSON_RBRACE: i64 = 2
52const NX_JSON_LBRACKET: i64 = 3
53const NX_JSON_RBRACKET: i64 = 4
54const NX_JSON_COMMA: i64 = 5
55const NX_JSON_COLON: i64 = 6
56const NX_JSON_STRING: i64 = 7
57const NX_JSON_NUMBER: i64 = 8
58const NX_JSON_TRUE: i64 = 9
59const NX_JSON_FALSE: i64 = 10
60const NX_JSON_NULL: i64 = 11
61const NX_JSON_EOF: i64 = 12
62const NX_JSON_ERROR: i64 = 13
63
64struct NxJsonTok {
65 src: *u8,
66 len: i64,
67 pos: i64,
68 // Last-token output:
69 kind: i64,
70 tok_off: i64,
71 tok_len: i64,
72}
73
74const NX_JSONTOK_BYTES: i64 = 48
75
76func nx_json_new(src: *u8, len: i64) -> *NxJsonTok {
77 let raw: *u8 = sys_mmap(NX_JSONTOK_BYTES)
78 let t: *NxJsonTok = raw as *NxJsonTok
79 t.src = src
80 t.len = len
81 t.pos = 0
82 t.kind = 0
83 t.tok_off = 0
84 t.tok_len = 0
85 return t
86}
87
88// is_ws canonical in nx_lex.nx.
89
90// is_digit canonical in nx_ascii.nx (nx_ascii_is_digit).
91
92// Skip whitespace from current pos.
93func nx_json_skip_ws(t: *NxJsonTok) -> i64 {
94 while t.pos < t.len {
95 if nx_lex_is_ws(t.src[t.pos]) == 0 { return 0 }
96 t.pos = t.pos + 1
97 }
98 return 0
99}
100
101// Match a literal at current pos. Returns 1 on match (advances
102// pos), 0 otherwise.
103func nx_json_lit(t: *NxJsonTok, lit: *u8, n: i64) -> i64 {
104 if t.pos + n > t.len { return 0 }
105 var i: i64 = 0
106 while i < n {
107 if t.src[t.pos + i] != lit[i] { return 0 }
108 i = i + 1
109 }
110 t.pos = t.pos + n
111 return 1
112}
113
114// Read next token. Returns the token kind (also stored in t.kind).
115// On STRING / NUMBER, t.tok_off + t.tok_len describe the span.
116func nx_json_next(t: *NxJsonTok) -> i64 {
117 nx_json_skip_ws(t)
118 if t.pos >= t.len {
119 t.kind = NX_JSON_EOF
120 return NX_JSON_EOF
121 }
122 let c: i64 = t.src[t.pos]
123 let start: i64 = t.pos
124
125 // Single-char tokens.
126 if c == 0x7B { t.pos = t.pos + 1; t.kind = NX_JSON_LBRACE; t.tok_off = start; t.tok_len = 1; return NX_JSON_LBRACE }
127 if c == 0x7D { t.pos = t.pos + 1; t.kind = NX_JSON_RBRACE; t.tok_off = start; t.tok_len = 1; return NX_JSON_RBRACE }
128 if c == 0x5B { t.pos = t.pos + 1; t.kind = NX_JSON_LBRACKET; t.tok_off = start; t.tok_len = 1; return NX_JSON_LBRACKET }
129 if c == 0x5D { t.pos = t.pos + 1; t.kind = NX_JSON_RBRACKET; t.tok_off = start; t.tok_len = 1; return NX_JSON_RBRACKET }
130 if c == 0x2C { t.pos = t.pos + 1; t.kind = NX_JSON_COMMA; t.tok_off = start; t.tok_len = 1; return NX_JSON_COMMA }
131 if c == 0x3A { t.pos = t.pos + 1; t.kind = NX_JSON_COLON; t.tok_off = start; t.tok_len = 1; return NX_JSON_COLON }
132
133 // String: scan until matching unescaped " . Tokenizer span
134 // includes both quotes.
135 if c == 0x22 {
136 var p: i64 = t.pos + 1
137 var done: i64 = 0
138 while done == 0 {
139 if p >= t.len { t.kind = NX_JSON_ERROR; return NX_JSON_ERROR }
140 let ch: i64 = t.src[p]
141 if ch == 0x5C {
142 // escape -- skip next char
143 p = p + 2
144 } else {
145 if ch == 0x22 { done = 1 }
146 else { p = p + 1 }
147 }
148 }
149 t.tok_off = start
150 t.tok_len = (p - start) + 1
151 t.pos = p + 1
152 t.kind = NX_JSON_STRING
153 return NX_JSON_STRING
154 }
155
156 // Number: optional minus, digits, optional .digits, optional e[+-]digits.
157 if c == 0x2D {
158 if t.pos + 1 >= t.len { t.kind = NX_JSON_ERROR; return NX_JSON_ERROR }
159 if nx_ascii_is_digit(t.src[t.pos + 1]) == 0 { t.kind = NX_JSON_ERROR; return NX_JSON_ERROR }
160 }
161 if nx_ascii_is_digit(c) == 1 {
162 // Fall through to number-walk path below.
163 } else {
164 if c != 0x2D {
165 // Maybe a literal (true / false / null).
166 if c == 0x74 {
167 let lit_t: *u8 = sys_mmap(8)
168 lit_t[0] = 0x74; lit_t[1] = 0x72; lit_t[2] = 0x75; lit_t[3] = 0x65
169 if nx_json_lit(t, lit_t, 4) == 1 {
170 t.kind = NX_JSON_TRUE; t.tok_off = start; t.tok_len = 4
171 return NX_JSON_TRUE
172 }
173 t.kind = NX_JSON_ERROR; return NX_JSON_ERROR
174 }
175 if c == 0x66 {
176 let lit_f: *u8 = sys_mmap(8)
177 lit_f[0]=0x66; lit_f[1]=0x61; lit_f[2]=0x6C; lit_f[3]=0x73; lit_f[4]=0x65
178 if nx_json_lit(t, lit_f, 5) == 1 {
179 t.kind = NX_JSON_FALSE; t.tok_off = start; t.tok_len = 5
180 return NX_JSON_FALSE
181 }
182 t.kind = NX_JSON_ERROR; return NX_JSON_ERROR
183 }
184 if c == 0x6E {
185 let lit_n: *u8 = sys_mmap(8)
186 lit_n[0]=0x6E; lit_n[1]=0x75; lit_n[2]=0x6C; lit_n[3]=0x6C
187 if nx_json_lit(t, lit_n, 4) == 1 {
188 t.kind = NX_JSON_NULL; t.tok_off = start; t.tok_len = 4
189 return NX_JSON_NULL
190 }
191 t.kind = NX_JSON_ERROR; return NX_JSON_ERROR
192 }
193 t.kind = NX_JSON_ERROR
194 return NX_JSON_ERROR
195 }
196 }
197
198 // Walk number.
199 var np: i64 = t.pos
200 if t.src[np] == 0x2D { np = np + 1 }
201 while np < t.len {
202 if nx_ascii_is_digit(t.src[np]) == 0 { np = t.len + 1 } // sentinel break
203 else { np = np + 1 }
204 }
205 if np > t.len { np = np - 1 - t.len } // (recover -- ugly; rewriting cleanly)
206 np = t.pos
207 if t.src[np] == 0x2D { np = np + 1 }
208 var stop_int: i64 = 0
209 while stop_int == 0 {
210 if np >= t.len { stop_int = 1 }
211 else { if nx_ascii_is_digit(t.src[np]) == 0 { stop_int = 1 }
212 else { np = np + 1 }
213 }
214 }
215 if np < t.len {
216 if t.src[np] == 0x2E {
217 np = np + 1
218 var stop_frac: i64 = 0
219 while stop_frac == 0 {
220 if np >= t.len { stop_frac = 1 }
221 else { if nx_ascii_is_digit(t.src[np]) == 0 { stop_frac = 1 }
222 else { np = np + 1 }
223 }
224 }
225 }
226 }
227 if np < t.len {
228 if t.src[np] == 0x65 {
229 np = np + 1
230 if np < t.len {
231 if t.src[np] == 0x2B { np = np + 1 }
232 else { if t.src[np] == 0x2D { np = np + 1 } }
233 }
234 var stop_exp: i64 = 0
235 while stop_exp == 0 {
236 if np >= t.len { stop_exp = 1 }
237 else { if nx_ascii_is_digit(t.src[np]) == 0 { stop_exp = 1 }
238 else { np = np + 1 }
239 }
240 }
241 }
242 }
243 t.tok_off = start
244 t.tok_len = np - start
245 t.pos = np
246 t.kind = NX_JSON_NUMBER
247 return NX_JSON_NUMBER
248}
249
250// ---- self-test ---------------------------------------------------
251
252func main() -> i64 {
253 // Input: {"name":"foo","count":42,"active":true,"empty":null,"items":[1,2,3]}
254 let s: *u8 = sys_mmap(128)
255 s[0]=0x7B; s[1]=0x22; s[2]=0x6E; s[3]=0x61; s[4]=0x6D
256 s[5]=0x65; s[6]=0x22; s[7]=0x3A; s[8]=0x22; s[9]=0x66
257 s[10]=0x6F; s[11]=0x6F; s[12]=0x22; s[13]=0x2C; s[14]=0x22
258 s[15]=0x63; s[16]=0x6F; s[17]=0x75; s[18]=0x6E; s[19]=0x74
259 s[20]=0x22; s[21]=0x3A; s[22]=0x34; s[23]=0x32; s[24]=0x2C
260 s[25]=0x22; s[26]=0x61; s[27]=0x63; s[28]=0x74; s[29]=0x69
261 s[30]=0x76; s[31]=0x65; s[32]=0x22; s[33]=0x3A; s[34]=0x74
262 s[35]=0x72; s[36]=0x75; s[37]=0x65; s[38]=0x2C; s[39]=0x22
263 s[40]=0x65; s[41]=0x6D; s[42]=0x70; s[43]=0x74; s[44]=0x79
264 s[45]=0x22; s[46]=0x3A; s[47]=0x6E; s[48]=0x75; s[49]=0x6C
265 s[50]=0x6C; s[51]=0x2C; s[52]=0x22; s[53]=0x69; s[54]=0x74
266 s[55]=0x65; s[56]=0x6D; s[57]=0x73; s[58]=0x22; s[59]=0x3A
267 s[60]=0x5B; s[61]=0x31; s[62]=0x2C; s[63]=0x32; s[64]=0x2C
268 s[65]=0x33; s[66]=0x5D; s[67]=0x7D
269
270 let t: *NxJsonTok = nx_json_new(s, 68)
271
272 if nx_json_next(t) != NX_JSON_LBRACE { return __syscall(93, 1, 0, 0, 0, 0, 0) }
273
274 if nx_json_next(t) != NX_JSON_STRING { return __syscall(93, 2, 0, 0, 0, 0, 0) }
275 if t.tok_len != 6 { return __syscall(93, 3, 0, 0, 0, 0, 0) } // "name"
276
277 if nx_json_next(t) != NX_JSON_COLON { return __syscall(93, 4, 0, 0, 0, 0, 0) }
278 if nx_json_next(t) != NX_JSON_STRING { return __syscall(93, 5, 0, 0, 0, 0, 0) } // "foo"
279 if nx_json_next(t) != NX_JSON_COMMA { return __syscall(93, 6, 0, 0, 0, 0, 0) }
280 if nx_json_next(t) != NX_JSON_STRING { return __syscall(93, 7, 0, 0, 0, 0, 0) } // "count"
281 if nx_json_next(t) != NX_JSON_COLON { return __syscall(93, 8, 0, 0, 0, 0, 0) }
282 if nx_json_next(t) != NX_JSON_NUMBER { return __syscall(93, 9, 0, 0, 0, 0, 0) } // 42
283 if t.tok_len != 2 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
284 if nx_json_next(t) != NX_JSON_COMMA { return __syscall(93, 11, 0, 0, 0, 0, 0) }
285 if nx_json_next(t) != NX_JSON_STRING { return __syscall(93, 12, 0, 0, 0, 0, 0) } // "active"
286 if nx_json_next(t) != NX_JSON_COLON { return __syscall(93, 13, 0, 0, 0, 0, 0) }
287 if nx_json_next(t) != NX_JSON_TRUE { return __syscall(93, 14, 0, 0, 0, 0, 0) }
288 if nx_json_next(t) != NX_JSON_COMMA { return __syscall(93, 15, 0, 0, 0, 0, 0) }
289 if nx_json_next(t) != NX_JSON_STRING { return __syscall(93, 16, 0, 0, 0, 0, 0) } // "empty"
290 if nx_json_next(t) != NX_JSON_COLON { return __syscall(93, 17, 0, 0, 0, 0, 0) }
291 if nx_json_next(t) != NX_JSON_NULL { return __syscall(93, 18, 0, 0, 0, 0, 0) }
292 if nx_json_next(t) != NX_JSON_COMMA { return __syscall(93, 19, 0, 0, 0, 0, 0) }
293 if nx_json_next(t) != NX_JSON_STRING { return __syscall(93, 20, 0, 0, 0, 0, 0) } // "items"
294 if nx_json_next(t) != NX_JSON_COLON { return __syscall(93, 21, 0, 0, 0, 0, 0) }
295 if nx_json_next(t) != NX_JSON_LBRACKET { return __syscall(93, 22, 0, 0, 0, 0, 0) }
296 if nx_json_next(t) != NX_JSON_NUMBER { return __syscall(93, 23, 0, 0, 0, 0, 0) }
297 if nx_json_next(t) != NX_JSON_COMMA { return __syscall(93, 24, 0, 0, 0, 0, 0) }
298 if nx_json_next(t) != NX_JSON_NUMBER { return __syscall(93, 25, 0, 0, 0, 0, 0) }
299 if nx_json_next(t) != NX_JSON_COMMA { return __syscall(93, 26, 0, 0, 0, 0, 0) }
300 if nx_json_next(t) != NX_JSON_NUMBER { return __syscall(93, 27, 0, 0, 0, 0, 0) }
301 if nx_json_next(t) != NX_JSON_RBRACKET { return __syscall(93, 28, 0, 0, 0, 0, 0) }
302 if nx_json_next(t) != NX_JSON_RBRACE { return __syscall(93, 29, 0, 0, 0, 0, 0) }
303 if nx_json_next(t) != NX_JSON_EOF { return __syscall(93, 30, 0, 0, 0, 0, 0) }
304
305 return 0
306}