test_json.c (17122B)
1 /* Realistic JSON lexer+parser test driver. 2 * 3 * Three layers of checks: 4 * 1. token-level: feed tricky strings/numbers straight to the lexer and assert 5 * the (kind, lexeme) the DFA produces — this is where number/string sharp 6 * edges live. 7 * 2. accept/reject: a corpus of whole documents driven lexer -> parser. 8 * 3. round-trip: rebuild each value through the value channel into canonical 9 * (whitespace-free) JSON and compare to an expected string. 10 * 11 * This driver is written to the natural expectation and left red where the 12 * implementation disagrees. 13 */ 14 #include "generated_rjson.h" 15 16 #include <stdarg.h> 17 #include <stdio.h> 18 #include <stdlib.h> 19 #include <string.h> 20 21 static int failures = 0; 22 static void okfail(int ok, const char *fmt, ...) { 23 va_list ap; va_start(ap, fmt); 24 char buf[512]; vsnprintf(buf, sizeof buf, fmt, ap); va_end(ap); 25 printf("%s %s\n", ok ? "ok " : "FAIL", buf); 26 if (!ok) failures++; 27 } 28 29 /* ------------------------------------------------------------------ arena -- */ 30 /* Every reduce/lift allocates a heap C-string; we track them all and free at 31 * the end of each parse. Strings are the semantic value. */ 32 typedef struct { 33 char **mem; size_t n, cap; 34 } Arena; 35 static char *areg(Arena *a, char *s) { 36 if (a->n == a->cap) { a->cap = a->cap ? a->cap * 2 : 64; a->mem = realloc(a->mem, a->cap * sizeof *a->mem); } 37 a->mem[a->n++] = s; 38 return s; 39 } 40 static char *adup(Arena *a, const char *s, size_t len) { 41 char *p = malloc(len + 1); memcpy(p, s, len); p[len] = 0; return areg(a, p); 42 } 43 static char *acat(Arena *a, const char *x, const char *y) { 44 size_t lx = strlen(x), ly = strlen(y); 45 char *p = malloc(lx + ly + 1); memcpy(p, x, lx); memcpy(p + lx, y, ly); p[lx + ly] = 0; 46 return areg(a, p); 47 } 48 static char *acat3(Arena *a, const char *x, const char *y, const char *z) { 49 return acat(a, acat(a, x, y), z); 50 } 51 static void afree(Arena *a) { for (size_t i = 0; i < a->n; i++) free(a->mem[i]); free(a->mem); a->mem = 0; a->n = a->cap = 0; } 52 53 /* ----------------------------------------------------------- value channel -- */ 54 static KitGramSem cb_lift(void *ud, KitGramToken t) { 55 return adup(ud, t.lexeme, t.len); /* raw lexeme, including quotes */ 56 } 57 static KitGramSem cb_list_empty(void *ud) { return adup(ud, "", 0); } 58 static KitGramSem cb_list_push(void *ud, KitGramSem list, KitGramSem item) { 59 const char *l = list; 60 return *l ? acat3(ud, l, ",", item) : (char *)item; 61 } 62 static KitGramSem cb_opt_none(void *ud) { return adup(ud, "", 0); } 63 static KitGramSem cb_opt_some(void *ud, KitGramSem item) { (void)ud; return item; } 64 65 static KitGramSem cb_reduce(void *ud, KitGramRuleId r, int prod, KitGramSem *k, size_t n) { 66 Arena *a = ud; (void)prod; (void)n; 67 switch (r) { 68 case JSON_R_value: return k[0]; /* always pass through */ 69 case JSON_R_member: return acat3(a, k[0], ":", k[2]); /* "key":value */ 70 case JSON_R_member_tail: return k[1]; /* drop the comma */ 71 case JSON_R_members: return *(char *)k[1] ? acat3(a, k[0], ",", k[1]) : (char *)k[0]; 72 case JSON_R_object: return acat3(a, "{", k[1], "}"); 73 case JSON_R_array: return acat3(a, "[", k[1], "]"); 74 case JSON_R_elements: return *(char *)k[1] ? acat3(a, k[0], ",", k[1]) : (char *)k[0]; 75 case JSON_R_element_tail: return k[1]; 76 } 77 return NULL; 78 } 79 80 /* The value-channel vtable that rebuilds canonical JSON. Shared verbatim by the 81 * table parser and the generated pull-RD parser below, so both run the *same* 82 * real actions. */ 83 static KitGramActions json_value_actions(void) { 84 return (KitGramActions){ 85 .reduce = cb_reduce, .lift_token = cb_lift, 86 .list_empty = cb_list_empty, .list_push = cb_list_push, 87 .opt_none = cb_opt_none, .opt_some = cb_opt_some, 88 }; 89 } 90 91 /* ----------------------------------------------------------------- driver --- */ 92 /* Returns 1 on accept. On accept, *out points into the arena (canonical text). 93 * `cap` sizes both parse stacks; `*overflowed` (optional) reports a cap hit. */ 94 static int parse_json_cap(const char *src, Arena *a, const char **out, size_t cap, int *overflowed) { 95 KitGramActions acts = json_value_actions(); 96 unsigned char carry[64]; 97 KitGramLexInput in; kit_gram_lex_input_init(&in, &(KitGramLexInputConfig){ .carry = carry, .carry_cap = sizeof carry }); 98 KitGramLexer lx; json_lexer_init(&lx, &in, &(KitGramLexConfig){0}); 99 KitGramParser ps; 100 KitGramSlot *ctl = malloc(cap * sizeof *ctl); KitGramSem *vals = malloc(cap * sizeof *vals); 101 KitGramConfig cfg = { .actions = &acts, .ud = a, .ctl_stack = ctl, .ctl_cap = cap, .val_stack = vals, .val_cap = cap }; 102 json_parser_init(&ps, &cfg); 103 104 KitGramLexInputSpan span = { .bytes = (const unsigned char *)src, .len = strlen(src) }; 105 kit_gram_lex_input_push(&in, &span); 106 kit_gram_lex_input_finish(&in); 107 108 int ret = 0; 109 for (;;) { 110 KitGramToken tok; 111 KitGramLexStatus st = kit_gram_lexer_next(&lx, &tok); 112 if (st == KIT_GRAM_LEX_TOKEN) { 113 if (kit_gram_parser_push(&ps, tok) == KIT_GRAM_PARSE_ERROR) { ret = 0; break; } 114 continue; 115 } 116 if (st == KIT_GRAM_LEX_NEED_MORE || st == KIT_GRAM_LEX_ERROR) { ret = 0; break; } 117 /* KIT_GRAM_LEX_EOF */ 118 if (kit_gram_parser_finish(&ps) != KIT_GRAM_PARSE_ACCEPT) { ret = 0; break; } 119 if (out) *out = kit_gram_parser_result(&ps); 120 ret = 1; 121 break; 122 } 123 if (overflowed) *overflowed = kit_gram_parser_overflowed(&ps); 124 free(ctl); free(vals); 125 return ret; 126 } 127 static int parse_json(const char *src, Arena *a, const char **out) { 128 return parse_json_cap(src, a, out, 512, NULL); 129 } 130 131 /* ---- the same real actions, driven through the generated parsers ---------- */ 132 /* parse_rd consumes a token array (lexed here with the table lexer). It runs the 133 * canonical-rebuild value channel above and returns the start rule's KitGramSem 134 * (the canonical string), so its output can be compared to the table parser's. */ 135 static const char *parse_json_rd(const char *src, Arena *a, int *ok) { 136 KitGramLexInput in; kit_gram_lex_input_init(&in, &(KitGramLexInputConfig){0}); 137 KitGramLexer lx; json_lexer_init(&lx, &in, &(KitGramLexConfig){0}); 138 KitGramLexInputSpan span = { .bytes = (const unsigned char *)src, .len = strlen(src) }; 139 kit_gram_lex_input_push(&in, &span); kit_gram_lex_input_finish(&in); 140 KitGramToken *toks = NULL; size_t n = 0, cap = 0; 141 for (;;) { 142 KitGramToken t; KitGramLexStatus st = kit_gram_lexer_next(&lx, &t); 143 if (st == KIT_GRAM_LEX_TOKEN) { 144 if (n == cap) { cap = cap ? cap * 2 : 64; toks = realloc(toks, cap * sizeof *toks); } 145 toks[n++] = t; continue; 146 } 147 if (st != KIT_GRAM_LEX_EOF) { free(toks); *ok = 0; return NULL; } /* lex error */ 148 break; 149 } 150 KitGramActions acts = json_value_actions(); 151 KitGramError err = {0}; int okv = 0; 152 KitGramSem r = json_parse_rd(toks, n, &acts, a, &err, &okv); 153 free(toks); 154 *ok = okv; 155 return okv ? (const char *)r : NULL; 156 } 157 158 /* ----------------------------------------------------------- token checks --- */ 159 static int lex_one(const char *src, KitGramToken *out) { 160 /* Lex `src`; require exactly one token covering the whole input. */ 161 KitGramLexInput in; kit_gram_lex_input_init(&in, &(KitGramLexInputConfig){0}); 162 KitGramLexer lx; json_lexer_init(&lx, &in, &(KitGramLexConfig){0}); 163 KitGramLexInputSpan span = { .bytes = (const unsigned char *)src, .len = strlen(src) }; 164 kit_gram_lex_input_push(&in, &span); kit_gram_lex_input_finish(&in); 165 if (kit_gram_lexer_next(&lx, out) != KIT_GRAM_LEX_TOKEN) return 0; 166 KitGramToken next; 167 return kit_gram_lexer_next(&lx, &next) == KIT_GRAM_LEX_EOF; /* and nothing after it */ 168 } 169 static void check_tok(const char *src, KitGramTokenKind kind) { 170 KitGramToken t; 171 int ok = lex_one(src, &t) && t.kind == kind && t.len == strlen(src); 172 okfail(ok, "lex %-26s -> kind=%u len=%zu (want kind=%u, single token)", src, 173 ok ? (unsigned)t.kind : 0u, ok ? t.len : 0u, (unsigned)kind); 174 } 175 static void check_not_single(const char *src) { 176 KitGramToken t; 177 int single = lex_one(src, &t) && t.len == strlen(src); 178 okfail(!single, "lex %-26s -> NOT one whole-input token (spec-invalid)", src); 179 } 180 181 static void check_doc(const char *src, int want_accept, const char *canon) { 182 Arena a = {0}; 183 const char *got = NULL; 184 int acc = parse_json(src, &a, &got); 185 if (acc != want_accept) { 186 okfail(0, "%-32s -> %s (wanted %s)", src, acc ? "accept" : "reject", 187 want_accept ? "accept" : "reject"); 188 } else if (want_accept && canon) { 189 okfail(got && strcmp(got, canon) == 0, "%-32s -> canon \"%s\" (wanted \"%s\")", 190 src, got ? got : "(null)", canon); 191 } else { 192 okfail(1, "%-32s -> %s", src, acc ? "accept" : "reject"); 193 } 194 195 /* The generated pull-RD parser runs the same real actions and must agree 196 * with the table parser: same accept/reject, and the same canonical string 197 * on accept. This is where "actions that do things" get exercised on the 198 * codegen path, not just the table interpreter. */ 199 int rd_ok = 0; 200 const char *rd = parse_json_rd(src, &a, &rd_ok); 201 int cg = rd_ok == acc; 202 if (cg && acc) cg = got && rd && strcmp(rd, got) == 0; 203 okfail(cg, "%-32s -> rd matches table (acc=%d, rd=\"%s\")", 204 src, acc, rd ? rd : "(null)"); 205 afree(&a); 206 } 207 208 /* ---------------------------------------------------- SAX-style listener -- */ 209 /* The listener channel (enter/exit/on_token) is the streaming, value-free side 210 * of the action vtable. This turns it into a SAX-style JSON event consumer: 211 * structural tokens and the `member` rule drive object/array/key/value events, 212 * with no value tree built (the value channel is left NULL). */ 213 typedef enum { 214 EV_OBJ_BEG, EV_OBJ_END, EV_ARR_BEG, EV_ARR_END, EV_KEY, EV_STR, EV_NUM, EV_LIT 215 } EvKind; 216 typedef struct { EvKind kind; char text[32]; } Ev; 217 typedef struct { Ev *v; size_t n, cap; int expect_key; } Sax; 218 219 static void sax_emit(Sax *s, EvKind k, const char *txt, size_t len) { 220 if (s->n == s->cap) { s->cap = s->cap ? s->cap * 2 : 32; s->v = realloc(s->v, s->cap * sizeof *s->v); } 221 Ev *e = &s->v[s->n++]; 222 e->kind = k; 223 size_t n = len < sizeof e->text - 1 ? len : sizeof e->text - 1; 224 if (txt && n) memcpy(e->text, txt, n); else n = 0; 225 e->text[n] = 0; 226 } 227 228 /* member = STRING ":" value, so the first STRING after entering `member` is a 229 * key; every other STRING is a value. */ 230 static void sax_enter(void *ud, KitGramRuleId r, int prod) { 231 (void)prod; 232 if (r == JSON_R_member) ((Sax *)ud)->expect_key = 1; 233 } 234 235 static void sax_on_token(void *ud, KitGramToken t) { 236 Sax *s = ud; 237 if (t.len == 1) { 238 switch (t.lexeme[0]) { 239 case '{': sax_emit(s, EV_OBJ_BEG, NULL, 0); return; 240 case '}': sax_emit(s, EV_OBJ_END, NULL, 0); return; 241 case '[': sax_emit(s, EV_ARR_BEG, NULL, 0); return; 242 case ']': sax_emit(s, EV_ARR_END, NULL, 0); return; 243 case ':': case ',': return; /* structural punctuation */ 244 default: break; 245 } 246 } 247 if (t.kind == JSON_TOK_STRING) { 248 sax_emit(s, s->expect_key ? EV_KEY : EV_STR, t.lexeme + 1, 249 t.len >= 2 ? t.len - 2 : 0); /* drop the surrounding quotes */ 250 s->expect_key = 0; 251 return; 252 } 253 if (t.kind == JSON_TOK_NUMBER) { sax_emit(s, EV_NUM, t.lexeme, t.len); return; } 254 sax_emit(s, EV_LIT, t.lexeme, t.len); /* true / false / null */ 255 } 256 257 static void test_sax_listener(void) { 258 const char *src = "{\"a\": 1, \"b\": [true, null]}"; 259 KitGramActions acts = { .enter = sax_enter, .on_token = sax_on_token }; 260 Sax sax = {0}; 261 262 KitGramLexInput in; kit_gram_lex_input_init(&in, &(KitGramLexInputConfig){0}); 263 KitGramLexer lx; json_lexer_init(&lx, &in, &(KitGramLexConfig){0}); 264 KitGramSlot ctl[128]; KitGramSem vals[128]; 265 KitGramParser ps; 266 json_parser_init(&ps, &(KitGramConfig){ .actions = &acts, .ud = &sax, 267 .ctl_stack = ctl, .ctl_cap = 128, .val_stack = vals, .val_cap = 128 }); 268 KitGramLexInputSpan span = { .bytes = (const unsigned char *)src, .len = strlen(src) }; 269 kit_gram_lex_input_push(&in, &span); kit_gram_lex_input_finish(&in); 270 271 int ok = 1; 272 for (;;) { 273 KitGramToken tok; 274 KitGramLexStatus st = kit_gram_lexer_next(&lx, &tok); 275 if (st == KIT_GRAM_LEX_TOKEN) { if (kit_gram_parser_push(&ps, tok) == KIT_GRAM_PARSE_ERROR) { ok = 0; break; } continue; } 276 if (st == KIT_GRAM_LEX_EOF) { ok = kit_gram_parser_finish(&ps) == KIT_GRAM_PARSE_ACCEPT; break; } 277 ok = 0; break; 278 } 279 okfail(ok, "SAX: document parses with listener-only actions"); 280 281 static const Ev want[] = { 282 { EV_OBJ_BEG, "" }, { EV_KEY, "a" }, { EV_NUM, "1" }, { EV_KEY, "b" }, 283 { EV_ARR_BEG, "" }, { EV_LIT, "true" }, { EV_LIT, "null" }, 284 { EV_ARR_END, "" }, { EV_OBJ_END, "" }, 285 }; 286 size_t nwant = sizeof want / sizeof want[0]; 287 int seq_ok = ok && sax.n == nwant; 288 for (size_t i = 0; seq_ok && i < nwant; i++) 289 seq_ok = sax.v[i].kind == want[i].kind && strcmp(sax.v[i].text, want[i].text) == 0; 290 okfail(seq_ok, "SAX: events for {\"a\":1,\"b\":[true,null]} match (%zu events)", sax.n); 291 free(sax.v); 292 } 293 294 int main(void) { 295 printf("== JSON lexer token edges ==\n"); 296 check_tok("0", JSON_TOK_NUMBER); 297 check_tok("-0", JSON_TOK_NUMBER); 298 check_tok("42", JSON_TOK_NUMBER); 299 check_tok("-3.14", JSON_TOK_NUMBER); 300 check_tok("1e10", JSON_TOK_NUMBER); 301 check_tok("1E+10", JSON_TOK_NUMBER); 302 check_tok("-2.5e-3", JSON_TOK_NUMBER); 303 check_tok("\"\"", JSON_TOK_STRING); 304 check_tok("\"hello\"", JSON_TOK_STRING); 305 check_tok("\"a\\\"b\"", JSON_TOK_STRING); /* "a\"b" */ 306 check_tok("\"\\u00e9\"", JSON_TOK_STRING); /* "é" */ 307 check_tok("\"\\n\\t\\r\\b\\f\\/\\\\\"", JSON_TOK_STRING); 308 /* Spec-invalid number forms: must NOT be one whole-input token. */ 309 check_not_single("01"); /* leading zero */ 310 check_not_single("1."); /* trailing dot, no frac */ 311 check_not_single(".5"); /* leading dot */ 312 check_not_single("+1"); /* leading plus */ 313 check_not_single("1e"); /* dangling exponent */ 314 315 printf("\n== JSON document accept/reject + round-trip ==\n"); 316 check_doc("null", 1, "null"); 317 check_doc("true", 1, "true"); 318 check_doc("123", 1, "123"); 319 check_doc("\"hi\"", 1, "\"hi\""); 320 check_doc("[]", 1, "[]"); 321 check_doc("{}", 1, "{}"); 322 check_doc("[1, 2, 3]", 1, "[1,2,3]"); 323 check_doc("{\"a\": 1}", 1, "{\"a\":1}"); 324 check_doc("{ \"a\" : 1 , \"b\" : [true, null] }", 1, "{\"a\":1,\"b\":[true,null]}"); 325 check_doc("[[[]]]", 1, "[[[]]]"); 326 check_doc("{\"k\": {\"k\": {\"k\": []}}}", 1, "{\"k\":{\"k\":{\"k\":[]}}}"); 327 check_doc(" \n\t 7 ", 1, "7"); /* surrounding whitespace */ 328 329 /* rejects */ 330 check_doc("", 0, NULL); /* empty input */ 331 check_doc("[1,]", 0, NULL); /* trailing comma */ 332 check_doc("{\"a\":1,}", 0, NULL); /* trailing comma */ 333 check_doc("{\"a\" 1}", 0, NULL); /* missing colon */ 334 check_doc("[1 2]", 0, NULL); /* missing comma */ 335 check_doc("{1: 2}", 0, NULL); /* non-string key */ 336 check_doc("[1, 2", 0, NULL); /* unclosed array */ 337 check_doc("nul", 0, NULL); /* bad keyword */ 338 check_doc("[1] [2]", 0, NULL); /* trailing content */ 339 340 /* deep nesting — exercises recursion / stack, and graceful overflow */ 341 printf("\n== JSON deep nesting (stack discipline) ==\n"); 342 { 343 size_t d = 200; 344 char deep[1024]; 345 size_t p = 0; 346 for (size_t i = 0; i < d; i++) deep[p++] = '['; 347 for (size_t i = 0; i < d; i++) deep[p++] = ']'; 348 deep[p] = 0; 349 350 /* Undersized stack must fail gracefully: overflow flag set, no crash. */ 351 Arena a1 = {0}; 352 int ovf = 0; 353 int acc_small = parse_json_cap(deep, &a1, NULL, 256, &ovf); 354 okfail(!acc_small && ovf, "200-deep at cap=256 -> overflow flag set, rejected (acc=%d ovf=%d)", 355 acc_small, ovf); 356 afree(&a1); 357 358 /* Properly sized via kit_gram_stack_bounds: must accept. */ 359 size_t cc = 0, vc = 0; 360 json_stack_bounds(d + 4, &cc, &vc); 361 size_t cap = cc > vc ? cc : vc; 362 Arena a2 = {0}; 363 int ovf2 = 0; 364 int acc_big = parse_json_cap(deep, &a2, NULL, cap, &ovf2); 365 okfail(acc_big && !ovf2, "200-deep at kit_gram_stack_bounds cap=%zu -> accept (acc=%d ovf=%d)", 366 cap, acc_big, ovf2); 367 afree(&a2); 368 } 369 370 printf("\n== JSON SAX-style listener channel ==\n"); 371 test_sax_listener(); 372 373 return failures ? 1 : 0; 374 }