calc_test.c (14796B)
1 /* test_calc.c — an embedder: binds the vtable to evaluate arithmetic, lexes a 2 * string into tokens, drives the push parser, and asserts results. Exercises 3 * the value channel (reduce/lift), the list/opt builders, the listener channel 4 * (enter/exit/on_token), and fail-fast errors. */ 5 #ifdef KIT_GRAM_GENERATED 6 #include "generated_calc.h" 7 /* Map generated CALC_-prefixed names to the plain names used in this file. */ 8 #define TOK_NUMBER CALC_TOK_NUMBER 9 #define TOK_PLUS CALC_TOK_PLUS 10 #define TOK_MINUS CALC_TOK_MINUS 11 #define TOK_STAR CALC_TOK_STAR 12 #define TOK_SLASH CALC_TOK_SLASH 13 #define TOK_LPAREN CALC_TOK_LPAREN 14 #define TOK_RPAREN CALC_TOK_RPAREN 15 #define TOK__COUNT CALC_TOK__COUNT 16 #define R_primary CALC_R_primary 17 #define R_factor CALC_R_factor 18 #define R_add_op CALC_R_add_op 19 #define R_mul_op CALC_R_mul_op 20 #define R_expr_tail CALC_R_expr_tail 21 #define R_term_tail CALC_R_term_tail 22 #define R_expr CALC_R_expr 23 #define R_term CALC_R_term 24 #else 25 #include "calc.h" 26 #endif 27 28 #include <ctype.h> 29 #include <stdio.h> 30 #include <stdlib.h> 31 #include <string.h> 32 33 /* ---- embedder semantic value: a tiny tagged node, arena-tracked ---- */ 34 typedef struct Node { 35 int tk; /* token kind, for lifted terminals */ 36 long val; /* numeric result */ 37 char op; /* for expr_tail/term_tail: + - * / */ 38 struct Node *operand; /* for expr_tail/term_tail */ 39 struct Node **items; /* for lists ({ ... }) */ 40 size_t nitems, cap; 41 } Node; 42 43 typedef struct { 44 Node **mem; size_t nmem, capmem; /* all allocations, freed in bulk */ 45 int enters, exits, tokens; /* listener-channel counters */ 46 int err_seen, err_tok, err_col; /* last error captured via on_error */ 47 } Emb; 48 49 static Node *node_new(Emb *e) { 50 Node *n = calloc(1, sizeof *n); 51 if (e->nmem == e->capmem) { 52 e->capmem = e->capmem ? e->capmem * 2 : 16; 53 e->mem = realloc(e->mem, e->capmem * sizeof *e->mem); 54 } 55 e->mem[e->nmem++] = n; 56 return n; 57 } 58 static void emb_free(Emb *e) { 59 for (size_t i = 0; i < e->nmem; i++) { free(e->mem[i]->items); free(e->mem[i]); } 60 free(e->mem); 61 } 62 static Node *mk_num(Emb *e, long v) { Node *n = node_new(e); n->val = v; return n; } 63 static long apply(long a, char op, long b) { 64 switch (op) { case '+': return a + b; case '-': return a - b; 65 case '*': return a * b; case '/': return a / b; } 66 return 0; 67 } 68 69 /* ---- vtable callbacks ---- */ 70 static KitGramSem cb_lift(void *ud, KitGramToken t) { 71 Emb *e = ud; Node *n = node_new(e); n->tk = t.kind; 72 if (t.kind == TOK_NUMBER) { 73 char b[32]; size_t L = t.len < 31 ? t.len : 31; 74 memcpy(b, t.lexeme, L); b[L] = 0; n->val = atol(b); 75 } 76 return n; 77 } 78 static KitGramSem cb_reduce(void *ud, KitGramRuleId r, int prod, KitGramSem *k, size_t n) { 79 Emb *e = ud; (void)n; 80 switch (r) { 81 case R_primary: return mk_num(e, prod == 0 ? ((Node *)k[0])->val : ((Node *)k[1])->val); 82 case R_factor: { long v = ((Node *)k[1])->val; if (k[0]) v = -v; return mk_num(e, v); } 83 case R_add_op: 84 case R_mul_op: return k[0]; /* op carried by token kind */ 85 case R_expr_tail: { Node *x = node_new(e); 86 x->op = ((Node *)k[0])->tk == TOK_PLUS ? '+' : '-'; 87 x->operand = k[1]; return x; } 88 case R_term_tail: { Node *x = node_new(e); 89 x->op = ((Node *)k[0])->tk == TOK_STAR ? '*' : '/'; 90 x->operand = k[1]; return x; } 91 case R_expr: 92 case R_term: { /* k = { head, list<tail> } */ 93 long acc = ((Node *)k[0])->val; 94 Node *list = k[1]; 95 for (size_t i = 0; i < list->nitems; i++) { 96 Node *t = list->items[i]; 97 acc = apply(acc, t->op, t->operand->val); 98 } 99 return mk_num(e, acc); 100 } 101 } 102 return NULL; 103 } 104 static KitGramSem cb_list_empty(void *ud) { return node_new(ud); } 105 static KitGramSem cb_list_push(void *ud, KitGramSem list, KitGramSem item) { 106 (void)ud; Node *l = list; 107 if (l->nitems == l->cap) { 108 l->cap = l->cap ? l->cap * 2 : 4; 109 l->items = realloc(l->items, l->cap * sizeof *l->items); 110 } 111 l->items[l->nitems++] = item; 112 return l; 113 } 114 static KitGramSem cb_opt_none(void *ud) { (void)ud; return NULL; } 115 static KitGramSem cb_opt_some(void *ud, KitGramSem item) { (void)ud; return item; } 116 static void cb_enter(void *ud, KitGramRuleId r, int prod) { (void)r; (void)prod; ((Emb *)ud)->enters++; } 117 static void cb_exit (void *ud, KitGramRuleId r, int prod) { (void)r; (void)prod; ((Emb *)ud)->exits++; } 118 static void cb_token(void *ud, KitGramToken t) { (void)t; ((Emb *)ud)->tokens++; } 119 static KitGramErrorAction cb_error(void *ud, const KitGramError *e) { 120 Emb *x = ud; x->err_seen = 1; x->err_tok = e->found.kind; x->err_col = (int)e->found.col; 121 return KIT_GRAM_ABORT; 122 } 123 124 /* ---- a minimal hand lexer (the parser is token-driven; this is the embedder's job) ---- */ 125 typedef struct { const char *s; size_t i; } Lexer; 126 static int lex_next(Lexer *lx, KitGramToken *out) { 127 while (lx->s[lx->i] && isspace((unsigned char)lx->s[lx->i])) lx->i++; 128 char c = lx->s[lx->i]; 129 if (!c) return 0; 130 out->lexeme = &lx->s[lx->i]; out->len = 1; out->line = 1; out->col = (uint32_t)(lx->i + 1); 131 if (isdigit((unsigned char)c)) { 132 size_t j = lx->i; while (isdigit((unsigned char)lx->s[j])) j++; 133 out->kind = TOK_NUMBER; out->len = j - lx->i; lx->i = j; return 1; 134 } 135 lx->i++; 136 switch (c) { 137 case '+': out->kind = TOK_PLUS; break; 138 case '-': out->kind = TOK_MINUS; break; 139 case '*': out->kind = TOK_STAR; break; 140 case '/': out->kind = TOK_SLASH; break; 141 case '(': out->kind = TOK_LPAREN; break; 142 case ')': out->kind = TOK_RPAREN; break; 143 default: out->kind = TOK__COUNT; break; /* invalid: never matches -> parse error */ 144 } 145 return 1; 146 } 147 148 static int eval(const char *src, long *result, int *enters, int *exits, int *tokens) { 149 Emb e; memset(&e, 0, sizeof e); 150 KitGramActions acts = { 151 .reduce = cb_reduce, .lift_token = cb_lift, 152 .list_empty = cb_list_empty, .list_push = cb_list_push, 153 .opt_none = cb_opt_none, .opt_some = cb_opt_some, 154 .enter = cb_enter, .exit = cb_exit, .on_token = cb_token, 155 }; 156 KitGramParser ps; 157 KitGramSlot ctl_stack[256]; 158 KitGramSem val_stack[256]; 159 KitGramConfig cfg = { .actions = &acts, .ud = &e, .recover = false, 160 .ctl_stack = ctl_stack, .ctl_cap = 256, 161 .val_stack = val_stack, .val_cap = 256 }; 162 calc_parser_init(&ps, &cfg); 163 KitGramParser *p = &ps; 164 165 Lexer lx = { src, 0 }; 166 KitGramToken t; 167 int ok = 1; 168 while (ok && lex_next(&lx, &t)) 169 if (kit_gram_parser_push(p, t) == KIT_GRAM_PARSE_ERROR) { ok = 0; break; } 170 if (ok && kit_gram_parser_finish(p) != KIT_GRAM_PARSE_ACCEPT) ok = 0; 171 if (ok && result) { Node *r = kit_gram_parser_result(p); *result = r ? r->val : 0; } 172 173 if (enters) *enters = e.enters; 174 if (exits) *exits = e.exits; 175 if (tokens) *tokens = e.tokens; 176 177 emb_free(&e); 178 return ok; 179 } 180 181 /* ---- assertions ---- */ 182 static int failures = 0; 183 static void check_val(const char *src, long want) { 184 long got; int en, ex, tk; 185 if (!eval(src, &got, &en, &ex, &tk)) { 186 printf("FAIL %-14s parse error (wanted %ld)\n", src, want); failures++; return; 187 } 188 if (got != want) { 189 printf("FAIL %-14s = %ld (wanted %ld)\n", src, got, want); failures++; return; 190 } 191 if (en != ex || en == 0) { 192 printf("FAIL %-14s enter/exit unbalanced %d/%d\n", src, en, ex); failures++; return; 193 } 194 printf("ok %-14s = %-5ld [enter=%d exit=%d tok=%d]\n", src, got, en, ex, tk); 195 } 196 static void check_err(const char *src) { 197 long got; int en, ex, tk; 198 if (eval(src, &got, &en, &ex, &tk)) { 199 printf("FAIL %-14s parsed = %ld (wanted rejection)\n", src, got); failures++; return; 200 } 201 printf("ok %-14s -> rejected\n", src); 202 } 203 204 /* drive a source to completion or first error; leave the parser live so the 205 * caller can query its stack. */ 206 static KitGramStatus drive(KitGramParser *p, const char *src) { 207 Lexer lx = { src, 0 }; 208 KitGramToken t; 209 KitGramStatus st = KIT_GRAM_NEED_MORE; 210 while (lex_next(&lx, &t)) { st = kit_gram_parser_push(p, t); if (st == KIT_GRAM_PARSE_ERROR) return st; } 211 return kit_gram_parser_finish(p); 212 } 213 214 static KitGramActions ctx_actions(void) { 215 return (KitGramActions){ .reduce = cb_reduce, .lift_token = cb_lift, 216 .list_empty = cb_list_empty, .list_push = cb_list_push, 217 .opt_none = cb_opt_none, .opt_some = cb_opt_some, .on_error = cb_error }; 218 } 219 220 static void test_context(void) { 221 printf("\n== queryable parse stack (error context) ==\n"); 222 223 /* (1) the rule-stack breadcrumb at the point of failure */ 224 { 225 Emb e; memset(&e, 0, sizeof e); 226 KitGramActions acts = ctx_actions(); 227 KitGramParser ps; KitGramSlot ctl[64]; KitGramSem vals[64]; 228 KitGramConfig cfg = { .actions = &acts, .ud = &e, .recover = false, 229 .ctl_stack = ctl, .ctl_cap = 64, .val_stack = vals, .val_cap = 64 }; 230 calc_parser_init(&ps, &cfg); 231 KitGramParser *p = &ps; 232 KitGramStatus st = drive(p, "1 + )"); 233 234 KitGramFrame fr[16]; 235 size_t n = kit_gram_parser_frames(p, fr, 16); 236 printf("ok \"1 + )\": stack = "); 237 for (size_t i = n; i > 0; i--) /* print outermost -> innermost */ 238 printf("%s%s", kit_gram_parser_rule_name(p, fr[i - 1].rule), i > 1 ? " > " : ""); 239 printf(" (unexpected '%s' at col %d)\n", kit_gram_parser_tok_name(p, e.err_tok), e.err_col); 240 241 if (st != KIT_GRAM_PARSE_ERROR) { printf("FAIL: expected error\n"); failures++; } 242 else if (n != 2 || fr[0].rule != R_expr_tail || fr[1].rule != R_expr) 243 { printf("FAIL: chain mismatch (n=%zu)\n", n); failures++; } 244 emb_free(&e); 245 } 246 247 /* (2) locate the open construct via its frame's start token */ 248 { 249 Emb e; memset(&e, 0, sizeof e); 250 KitGramActions acts = ctx_actions(); 251 KitGramParser ps; KitGramSlot ctl[64]; KitGramSem vals[64]; 252 KitGramConfig cfg = { .actions = &acts, .ud = &e, .recover = false, 253 .ctl_stack = ctl, .ctl_cap = 64, .val_stack = vals, .val_cap = 64 }; 254 calc_parser_init(&ps, &cfg); 255 KitGramParser *p = &ps; 256 KitGramStatus st = drive(p, "(1 + 2"); 257 258 KitGramFrame fr[16]; 259 size_t n = kit_gram_parser_frames(p, fr, 16); 260 int found = 0; uint32_t col = 0; 261 for (size_t i = 0; i < n; i++) 262 if (fr[i].rule == R_primary && fr[i].start.kind == TOK_LPAREN) { found = 1; col = fr[i].start.col; break; } 263 printf("ok \"(1 + 2\": unterminated '(' opened at col %u, expected '%s'\n", 264 col, kit_gram_parser_tok_name(p, TOK_RPAREN)); 265 266 if (st != KIT_GRAM_PARSE_ERROR) { printf("FAIL: expected error\n"); failures++; } 267 if (!found || col != 1) { printf("FAIL: open paren not located (col=%u)\n", col); failures++; } 268 emb_free(&e); 269 } 270 } 271 272 static void test_bounds(void) { 273 printf("\n== stack bounds (derived from grammar) ==\n"); 274 275 size_t ctl_cap, val_cap; 276 #ifdef KIT_GRAM_GENERATED 277 calc_stack_bounds(16, &ctl_cap, &val_cap); 278 #else 279 kit_gram_stack_bounds(&calc_grammar, 16, &ctl_cap, &val_cap); 280 #endif 281 printf("ok depth<=16 => ctl_cap>=%zu val_cap>=%zu (max production length drives it)\n", 282 ctl_cap, val_cap); 283 284 /* (1) the derived caps are sufficient: parse within them, no overflow */ 285 { 286 Emb e; memset(&e, 0, sizeof e); 287 KitGramActions acts = ctx_actions(); 288 KitGramParser ps; KitGramSlot ctl[256]; KitGramSem vals[256]; /* physical >= derived */ 289 KitGramConfig cfg = { .actions = &acts, .ud = &e, .recover = false, 290 .ctl_stack = ctl, .ctl_cap = ctl_cap, /* use the derived caps */ 291 .val_stack = vals, .val_cap = val_cap }; 292 calc_parser_init(&ps, &cfg); 293 KitGramParser *p = &ps; 294 KitGramStatus st = drive(p, "2 * -(3 + 1)"); 295 size_t ch = kit_gram_parser_ctl_hwm(p), vh = kit_gram_parser_val_hwm(p); 296 printf("ok \"2 * -(3 + 1)\": peak ctl=%zu val=%zu (within %zu/%zu)\n", 297 ch, vh, ctl_cap, val_cap); 298 if (st != KIT_GRAM_PARSE_ACCEPT || kit_gram_parser_overflowed(p)) { printf("FAIL: should fit\n"); failures++; } 299 if (ch > ctl_cap || vh > val_cap) { printf("FAIL: exceeded derived caps\n"); failures++; } 300 emb_free(&e); 301 } 302 303 /* (2) undersized caps are detected, not corrupted: overflow flag is set */ 304 { 305 Emb e; memset(&e, 0, sizeof e); 306 KitGramActions acts = ctx_actions(); 307 KitGramParser ps; KitGramSlot ctl[4]; KitGramSem vals[4]; 308 KitGramConfig cfg = { .actions = &acts, .ud = &e, .recover = false, 309 .ctl_stack = ctl, .ctl_cap = 4, .val_stack = vals, .val_cap = 4 }; 310 calc_parser_init(&ps, &cfg); 311 KitGramParser *p = &ps; 312 KitGramStatus st = drive(p, "1 + 2 + 3 + 4"); 313 printf("ok tiny caps (4): %s, overflow=%s\n", 314 st == KIT_GRAM_PARSE_ERROR ? "rejected" : "ACCEPTED?!", 315 kit_gram_parser_overflowed(p) ? "true" : "false"); 316 if (st != KIT_GRAM_PARSE_ERROR || !kit_gram_parser_overflowed(p)) { 317 printf("FAIL: overflow not detected\n"); failures++; 318 } 319 emb_free(&e); 320 } 321 } 322 323 int main(void) { 324 printf("== value channel (arithmetic) ==\n"); 325 check_val("1", 1); 326 check_val("1 + 2 * 3", 7); /* precedence */ 327 check_val("(1 + 2) * 3", 9); /* recursion via ( expr ) */ 328 check_val("10 - 2 - 3", 5); /* left associativity */ 329 check_val("100 / 5 / 2", 10); 330 check_val("-3 + 10", 7); /* optional unary minus */ 331 check_val("2 * -(3 + 1)", -8); 332 333 printf("\n== fail-fast errors ==\n"); 334 check_err("1 +"); /* missing operand */ 335 check_err("1 2"); /* trailing input */ 336 check_err("(1 + 2"); /* missing ) */ 337 check_err(""); /* empty input */ 338 check_err("* 3"); /* unexpected op */ 339 340 test_context(); 341 test_bounds(); 342 343 printf("\n%s — %d failure%s\n", 344 failures ? "FAILED" : "PASSED", failures, failures == 1 ? "" : "s"); 345 return failures ? 1 : 0; 346 }