parser_codegen_test.c (14880B)
1 /* test_parser_codegen.c — equivalence of the --parser-codegen pull-RD parser 2 * with the table interpreter. 3 * 4 * A recording KitGramActions logs every value-channel call (lift/reduce/list/opt) and 5 * returns a sequential handle as the KitGramSem, so each event captures the call's 6 * arguments AND the handles of its kids — i.e. the full shape of the value tree. 7 * Running the interpreter and the generated parser over the same token stream 8 * must produce byte-identical event logs. Invalid inputs must fail in both. 9 * 10 * Covers json (LL(1): objects, arrays, optionals, list tails) and clike 11 * (LL(1) + a Pratt expression ladder with prefix and infix operators). */ 12 #define _POSIX_C_SOURCE 200809L 13 14 #include <kit/gram_parse.h> 15 #include <kit/gram_lex.h> 16 17 extern const KitGramGrammar jsonrd_grammar; 18 extern const KitGramLexGrammar jsonrd_lex_grammar; 19 extern const KitGramGrammar clikerd_grammar; 20 extern const KitGramLexGrammar clikerd_lex_grammar; 21 KitGramSem jsonrd_parse_rd (const KitGramToken *toks, size_t ntok, const KitGramActions *act, void *ud, KitGramError *err, int *ok); 22 KitGramSem clikerd_parse_rd(const KitGramToken *toks, size_t ntok, const KitGramActions *act, void *ud, KitGramError *err, int *ok); 23 extern const KitGramGrammar mixfixrd_grammar; 24 extern const KitGramLexGrammar mixfixrd_lex_grammar; 25 KitGramSem mixfixrd_parse_rd (const KitGramToken *toks, size_t ntok, const KitGramActions *act, void *ud, KitGramError *err, int *ok); 26 /* recovery-enabled (--parser-recover) builds, used only by the recovery checks */ 27 extern const KitGramLexGrammar clikerec_lex_grammar; 28 extern const KitGramLexGrammar mixfixrec_lex_grammar; 29 KitGramSem clikerec_parse_rd (const KitGramToken *toks, size_t ntok, const KitGramActions *act, void *ud, KitGramError *err, int *ok); 30 KitGramSem mixfixrec_parse_rd(const KitGramToken *toks, size_t ntok, const KitGramActions *act, void *ud, KitGramError *err, int *ok); 31 32 #include <stdio.h> 33 #include <stdlib.h> 34 #include <string.h> 35 36 static int failures = 0, checks = 0; 37 38 static void *xmalloc(size_t n) { void *p = malloc(n ? n : 1); if (!p) { fputs("oom\n", stderr); exit(2); } return p; } 39 40 /* ---- recording actions ---- */ 41 typedef struct { int type; uint64_t a, b, c; } Ev; 42 typedef struct { Ev *v; size_t n, cap; uint64_t counter; } Rec; 43 44 static void rec_reset(Rec *r) { r->n = 0; r->counter = 0; } 45 static void rec_push(Rec *r, int type, uint64_t a, uint64_t b, uint64_t c) { 46 if (r->n == r->cap) { r->cap = r->cap ? r->cap * 2 : 256; r->v = realloc(r->v, r->cap * sizeof *r->v); } 47 r->v[r->n++] = (Ev){ type, a, b, c }; 48 } 49 static KitGramSem rec_handle(Rec *r) { return (KitGramSem)(uintptr_t)(++r->counter); } 50 51 static KitGramSem rc_lift(void *ud, KitGramToken t) { 52 Rec *r = ud; KitGramSem h = rec_handle(r); 53 rec_push(r, 1, t.kind, (uint64_t)(uintptr_t)h, 0); 54 return h; 55 } 56 static KitGramSem rc_reduce(void *ud, KitGramRuleId rule, int prod, KitGramSem *kids, size_t n) { 57 Rec *r = ud; 58 uint64_t kh = 1469598103934665603ull; 59 for (size_t i = 0; i < n; i++) kh = (kh ^ (uint64_t)(uintptr_t)kids[i]) * 1099511628211ull; 60 KitGramSem h = rec_handle(r); 61 rec_push(r, 2, (uint64_t)rule | ((uint64_t)(unsigned)prod << 16) | ((uint64_t)n << 32), kh, 62 (uint64_t)(uintptr_t)h); 63 return h; 64 } 65 static KitGramSem rc_le(void *ud) { Rec *r = ud; KitGramSem h = rec_handle(r); rec_push(r, 3, (uint64_t)(uintptr_t)h, 0, 0); return h; } 66 static KitGramSem rc_lp(void *ud, KitGramSem l, KitGramSem i) { 67 Rec *r = ud; KitGramSem h = rec_handle(r); 68 rec_push(r, 4, (uint64_t)(uintptr_t)l, (uint64_t)(uintptr_t)i, (uint64_t)(uintptr_t)h); 69 return h; 70 } 71 static KitGramSem rc_on(void *ud) { rec_push(ud, 5, 0, 0, 0); return NULL; } 72 static KitGramSem rc_os(void *ud, KitGramSem i) { 73 Rec *r = ud; KitGramSem h = rec_handle(r); 74 rec_push(r, 6, (uint64_t)(uintptr_t)i, (uint64_t)(uintptr_t)h, 0); 75 return h; 76 } 77 /* listener channel */ 78 static void rc_enter(void *ud, KitGramRuleId r, int prod) { rec_push(ud, 7, r, (uint64_t)(unsigned)prod, 0); } 79 static void rc_exit (void *ud, KitGramRuleId r, int prod) { rec_push(ud, 8, r, (uint64_t)(unsigned)prod, 0); } 80 static void rc_tok (void *ud, KitGramToken t) { rec_push(ud, 9, t.kind, 0, 0); } 81 /* captures the interpreter's diagnostic (it has no err out-param, only on_error) */ 82 static KitGramError g_ierr; static int g_ierr_set; 83 static KitGramErrorAction rc_on_error(void *ud, const KitGramError *e) { (void)ud; g_ierr = *e; g_ierr_set = 1; return KIT_GRAM_ABORT; } 84 static const KitGramActions rec_actions = { 85 .reduce = rc_reduce, .lift_token = rc_lift, 86 .list_empty = rc_le, .list_push = rc_lp, .opt_none = rc_on, .opt_some = rc_os, 87 .enter = rc_enter, .exit = rc_exit, .on_token = rc_tok, 88 .on_error = rc_on_error, 89 }; 90 91 /* ---- recovery: a configurable on_error + a non-recording value channel ---- */ 92 static int g_action, g_ecount; 93 static KitGramErrorAction rec_recover(void *ud, const KitGramError *e) { (void)ud; (void)e; g_ecount++; return (KitGramErrorAction)g_action; } 94 static KitGramSem nv_reduce(void *ud, KitGramRuleId r, int prod, KitGramSem *k, size_t n) { (void)ud;(void)r;(void)prod;(void)k;(void)n; return (KitGramSem)1; } 95 static KitGramSem nv_lift(void *ud, KitGramToken t) { (void)ud;(void)t; return (KitGramSem)1; } 96 static KitGramSem nv_le(void *ud) { (void)ud; return (KitGramSem)1; } 97 static KitGramSem nv_lp(void *ud, KitGramSem a, KitGramSem b) { (void)ud;(void)a;(void)b; return (KitGramSem)1; } 98 static KitGramSem nv_on(void *ud) { (void)ud; return (KitGramSem)0; } 99 static KitGramSem nv_os(void *ud, KitGramSem a) { (void)ud;(void)a; return (KitGramSem)1; } 100 static const KitGramActions recover_actions = { 101 .reduce = nv_reduce, .lift_token = nv_lift, .list_empty = nv_le, .list_push = nv_lp, 102 .opt_none = nv_on, .opt_some = nv_os, .on_error = rec_recover, 103 }; 104 105 /* ---- lexing ---- */ 106 typedef struct { KitGramToken *v; size_t n, cap; } TokVec; 107 static void tv_push(TokVec *t, KitGramToken tok) { 108 if (t->n == t->cap) { t->cap = t->cap ? t->cap * 2 : 256; t->v = realloc(t->v, t->cap * sizeof *t->v); } 109 t->v[t->n++] = tok; 110 } 111 static int lex_all(const KitGramLexGrammar *g, const char *s, TokVec *out) { 112 KitGramLexInput in; kit_gram_lex_input_init(&in, &(KitGramLexInputConfig){0}); 113 KitGramLexInputSpan span = { .bytes = (const unsigned char *)s, .len = strlen(s) }; 114 KitGramLexer lx; kit_gram_lexer_init(&lx, g, &in, &(KitGramLexConfig){0}); 115 kit_gram_lex_input_push(&in, &span); kit_gram_lex_input_finish(&in); 116 for (;;) { 117 KitGramToken tok; KitGramLexStatus st = kit_gram_lexer_next(&lx, &tok); 118 if (st == KIT_GRAM_LEX_TOKEN) { tv_push(out, tok); continue; } 119 return st == KIT_GRAM_LEX_EOF; 120 } 121 } 122 123 static void check_recover(const char *name, const KitGramLexGrammar *lg, 124 KitGramSem (*rd)(const KitGramToken *, size_t, const KitGramActions *, void *, KitGramError *, int *), 125 const char *src, int action, int want_complete, int min_errors) { 126 checks++; 127 g_action = action; g_ecount = 0; 128 TokVec toks = {0}; 129 if (!lex_all(lg, src, &toks)) { failures++; fprintf(stderr, "FAIL %s: lex error\n", name); free(toks.v); return; } 130 int ok = 0; 131 rd(toks.v, toks.n, &recover_actions, NULL, NULL, &ok); 132 free(toks.v); 133 int pass = (ok == want_complete) && (g_ecount >= min_errors) && (g_ecount < 1000); 134 if (pass) printf("ok %s: completed=%d, errors=%d (action=%d)\n", name, ok, g_ecount, action); 135 else { failures++; fprintf(stderr, "FAIL %s: completed=%d (want %d), errors=%d (want >=%d), action=%d\n", 136 name, ok, want_complete, g_ecount, min_errors, action); } 137 } 138 139 static int loc_match(const char *name, const char *tag, const KitGramError *a, const KitGramError *b) { 140 int ok = a->found.kind == b->found.kind && a->in_rule == b->in_rule && a->nexpected == b->nexpected; 141 /* For a real token the line/col must match exactly. For EOF the interpreter has 142 * no position (0:0) while the fused parser reports the true end of input, which 143 * is better, not wrong — so only require line/col parity on real tokens. */ 144 if (a->found.kind != 0 /* TOK_EOF */) 145 ok = ok && a->found.line == b->found.line && a->found.col == b->found.col; 146 for (size_t i = 0; ok && i < a->nexpected; i++) if (a->expected[i] != b->expected[i]) ok = 0; 147 if (!ok) 148 fprintf(stderr, " %s/%s: error loc differs: interp(k=%u @%u:%u rule=%u nexp=%zu) vs codegen(k=%u @%u:%u rule=%u nexp=%zu)\n", 149 name, tag, a->found.kind, a->found.line, a->found.col, a->in_rule, a->nexpected, 150 b->found.kind, b->found.line, b->found.col, b->in_rule, b->nexpected); 151 return ok; 152 } 153 154 static int logs_match(const char *name, const char *tag, Rec *a, Rec *b) { 155 if (a->n != b->n) { fprintf(stderr, " %s/%s: event count %zu vs %zu\n", name, tag, a->n, b->n); return 0; } 156 for (size_t k = 0; k < a->n; k++) 157 if (memcmp(&a->v[k], &b->v[k], sizeof(Ev)) != 0) { 158 fprintf(stderr, " %s/%s: event %zu differs\n", name, tag, k); 159 return 0; 160 } 161 return 1; 162 } 163 164 /* ---- one equivalence check: interpreter vs buffered RD vs fused lex+parse ---- */ 165 static void check(const char *name, const KitGramGrammar *g, const KitGramLexGrammar *lg, 166 KitGramSem (*rd)(const KitGramToken *, size_t, const KitGramActions *, void *, KitGramError *, int *), 167 KitGramSem (*fused)(const unsigned char *, size_t, const KitGramActions *, void *, KitGramError *, int *), 168 const char *src, int expect_ok) { 169 checks++; 170 TokVec toks = {0}; 171 if (!lex_all(lg, src, &toks)) { fprintf(stderr, "FAIL %s: lex error\n", name); failures++; free(toks.v); return; } 172 173 /* interpreter — on_error captures its diagnostic into g_ierr */ 174 Rec ri = {0}; rec_reset(&ri); g_ierr_set = 0; 175 size_t ctl_cap = 0, val_cap = 0; 176 kit_gram_stack_bounds(g, 256, &ctl_cap, &val_cap); 177 KitGramSlot *ctl = xmalloc(ctl_cap * sizeof *ctl); 178 KitGramSem *val = xmalloc(val_cap * sizeof *val); 179 KitGramParser p; 180 KitGramConfig cfg = { .actions = &rec_actions, .ud = &ri, .ctl_stack = ctl, .ctl_cap = ctl_cap, 181 .val_stack = val, .val_cap = val_cap }; 182 kit_gram_parser_init(&p, g, &cfg); 183 int i_ok = kit_gram_parser_push_n(&p, toks.v, toks.n) != KIT_GRAM_PARSE_ERROR && 184 kit_gram_parser_finish(&p) == KIT_GRAM_PARSE_ACCEPT; 185 KitGramError ierr = g_ierr; int ierr_set = g_ierr_set; /* save before RD overwrites it */ 186 187 /* buffered recursive descent (token array) */ 188 Rec rr = {0}; rec_reset(&rr); 189 int r_ok = 0; KitGramError err_rd = {0}; 190 rd(toks.v, toks.n, &rec_actions, &rr, &err_rd, &r_ok); 191 192 /* fused lex+parse (raw bytes) */ 193 Rec rf = {0}; rec_reset(&rf); 194 int f_ok = 0; KitGramError err_fused = {0}; 195 if (fused) fused((const unsigned char *)src, strlen(src), &rec_actions, &rf, &err_fused, &f_ok); 196 197 int ok = (i_ok == r_ok && i_ok == expect_ok); 198 if (fused && i_ok != f_ok) ok = 0; 199 if (ok && i_ok) { 200 if (!logs_match(name, "rd", &ri, &rr)) ok = 0; 201 if (fused && !logs_match(name, "fused", &ri, &rf)) ok = 0; 202 } 203 /* on a syntax error, the codegen parser's location must match the interpreter's */ 204 int loc_ok = 1; 205 if (ok && !i_ok && ierr_set) { 206 if (!loc_match(name, "rd", &ierr, &err_rd)) loc_ok = 0; 207 if (fused && !loc_match(name, "fused", &ierr, &err_fused)) loc_ok = 0; 208 } 209 if (!ok || !loc_ok) { 210 failures++; 211 fprintf(stderr, "FAIL %s: interp ok=%d, rd ok=%d, fused ok=%d, expect=%d, loc_ok=%d\n", 212 name, i_ok, r_ok, f_ok, expect_ok, loc_ok); 213 } else if (i_ok) { 214 printf("ok %s: ok, %zu events match across interp/rd%s\n", name, ri.n, fused ? "/fused" : ""); 215 } else { 216 printf("ok %s: error @ line %u col %u (found kind=%u, nexp=%zu) matches across interp/rd%s\n", 217 name, err_rd.found.line, err_rd.found.col, err_rd.found.kind, err_rd.nexpected, 218 fused ? "/fused" : ""); 219 } 220 free(ctl); free(val); free(ri.v); free(rr.v); free(rf.v); free(toks.v); 221 } 222 223 /* fused is NULL here: parse_fused requires the standalone lexer, so its 224 * equivalence is covered in test_lexer_standalone.c (parse_fused vs parse_rd). 225 * This test pins parse_rd against the interpreter; rd == fused there closes the 226 * loop transitively. */ 227 #define JSON &jsonrd_grammar, &jsonrd_lex_grammar, jsonrd_parse_rd, NULL 228 #define CLIKE &clikerd_grammar, &clikerd_lex_grammar, clikerd_parse_rd, NULL 229 #define MIXFIX &mixfixrd_grammar, &mixfixrd_lex_grammar, mixfixrd_parse_rd, NULL 230 231 int main(void) { 232 check("json/flat", JSON, "{\"a\":1,\"b\":[1,2,3],\"c\":null}", 1); 233 check("json/nested", JSON, "[true,false,{\"x\":{\"y\":[]}},-1.5e3,\"s\\nt\"]", 1); 234 check("json/empty", JSON, "{}", 1); 235 check("json/bad1", JSON, "{\"a\":}", 0); 236 check("json/bad2", JSON, "[1,,2]", 0); 237 238 check("clike/fn", CLIKE, "int f(int a){ int b = a + 1; return b; }", 1); 239 check("clike/expr", CLIKE, "int g(int a, int b){ int c = a + b * a - b / a; " 240 "if (a < b) { c = !a; } else { c = -b == a; } return c = a || b && a; }", 1); 241 check("clike/call", CLIKE, "void h(){ f(1, g(2), 3); x = y(); }", 1); 242 check("clike/bad1", CLIKE, "int f( {", 0); 243 check("clike/bad2", CLIKE, "int x = ;", 0); 244 245 /* mixfix Pratt: ternary ?:, circumfix call/index, member `.`, precedence */ 246 check("mixfix/tern", MIXFIX, "a ? b : c ? d : e", 1); /* right-assoc */ 247 check("mixfix/prec", MIXFIX, "1 + 2 * 3 - foo.bar", 1); 248 check("mixfix/call", MIXFIX, "f(1, 2)(g(), x)[i + 1].m", 1); /* chained mixfix */ 249 check("mixfix/group", MIXFIX, "(a + b) * c ? x[0] : y(z)", 1); 250 check("mixfix/bad1", MIXFIX, "a ? b", 0); /* missing : */ 251 check("mixfix/bad2", MIXFIX, "f(1,", 0); /* unterminated call */ 252 253 /* error recovery (driven by the on_error return) over the buffered RD path; 254 * recovery lives in the shared rd_* rule functions, so this also covers the 255 * fused parser's recovery. */ 256 const char *two_err = 257 "int f() { int a = ; while () { } return a; }\nint g() { return 1; }"; 258 check_recover("recover/resync", &clikerec_lex_grammar, clikerec_parse_rd, two_err, KIT_GRAM_RESYNC, /*complete*/1, /*errs*/2); 259 check_recover("recover/abort", &clikerec_lex_grammar, clikerec_parse_rd, two_err, KIT_GRAM_ABORT, /*complete*/0, /*errs*/1); 260 check_recover("recover/skip", &clikerec_lex_grammar, clikerec_parse_rd, "int f() { return 1;; }", KIT_GRAM_SKIP, 1, 1); 261 check_recover("recover/mixfix", &mixfixrec_lex_grammar, mixfixrec_parse_rd, "a ? b + ", KIT_GRAM_RESYNC, 1, 1); 262 263 fprintf(stderr, "%d checks, %d failures\n", checks, failures); 264 return failures ? 1 : 0; 265 }