machine_test.c (12331B)
1 /* test_machine.c - %machine (token-alphabet) verifier + sampler. 2 * 3 * Built from the generated test/machine.ebnf output ONLY (generated_machine.o + 4 * this file), with NO build/libgram.a: a %machine emits self-contained codegen 5 * (steppable DFA + AST-directed sampler) that links nothing from the runtime, so 6 * this binary doubles as the table-free link check. */ 7 #include "generated_machine.h" 8 9 #include <stdio.h> 10 #include <string.h> 11 12 static int failures = 0; 13 #define CHECK(cond) do { \ 14 if (!(cond)) { printf("FAIL %s:%d: %s\n", __FILE__, __LINE__, #cond); failures++; } \ 15 } while (0) 16 17 /* ---- conn: SYN SYNACK ACK (SEND|RECV)* FIN FINACK ----------------------- */ 18 static void test_conn(void) { 19 conn_kind k = (conn_kind)-1; 20 21 conn_sym ok1[] = { CONN_SYN, CONN_SYNACK, CONN_ACK, CONN_FIN, CONN_FINACK }; 22 CHECK(conn_fsm_accepts(ok1, 5, &k) && k == CONN_session); 23 24 conn_sym ok2[] = { CONN_SYN, CONN_SYNACK, CONN_ACK, CONN_SEND, CONN_RECV, CONN_SEND, CONN_FIN, CONN_FINACK }; 25 CHECK(conn_fsm_accepts(ok2, 8, NULL)); 26 27 conn_sym bad_order[] = { CONN_SYN, CONN_ACK, CONN_SYNACK }; 28 CHECK(!conn_fsm_accepts(bad_order, 3, NULL)); 29 CHECK(!conn_fsm_accepts(NULL, 0, NULL)); /* not ε-accepting */ 30 conn_sym prefix[] = { CONN_SYN, CONN_SYNACK, CONN_ACK }; 31 CHECK(!conn_fsm_accepts(prefix, 3, NULL)); /* prefix, not complete */ 32 33 /* Steppable surface: enabled / live / accepting at each step. */ 34 conn_fsm m; conn_fsm_init(&m); 35 CHECK(!conn_fsm_accepting(&m, NULL)); 36 CHECK(conn_fsm_live(&m)); 37 conn_sym en[16]; 38 CHECK(conn_fsm_enabled(&m, en, 16) == 1 && en[0] == CONN_SYN); 39 CHECK(conn_fsm_step(&m, CONN_SYN) == KIT_GRAM_FSM_OK); 40 CHECK(conn_fsm_step(&m, CONN_ACK) == KIT_GRAM_FSM_DEAD); /* ACK not enabled here */ 41 conn_fsm_init(&m); 42 conn_fsm_step(&m, CONN_SYN); conn_fsm_step(&m, CONN_SYNACK); conn_fsm_step(&m, CONN_ACK); 43 /* In the data-loop state SEND, RECV and FIN are enabled. */ 44 CHECK(conn_fsm_enabled(&m, en, 16) == 3); 45 conn_fsm_step(&m, CONN_FIN); 46 conn_fsm_step(&m, CONN_FINACK); 47 CHECK(conn_fsm_accepting(&m, &k) && k == CONN_session); 48 CHECK(conn_fsm_live(&m)); 49 50 /* sym_name table. */ 51 CHECK(strcmp(conn_sym_name[CONN_SYN], "SYN") == 0); 52 CHECK(strcmp(conn_sym_name[CONN_FINACK], "FINACK") == 0); 53 } 54 55 /* ---- sampler round-trip: every sampled trace must verify ----------------- */ 56 static void test_conn_sampler(void) { 57 conn_gen_config cfg = { .seed = 0xC0FFEE, .stop_prob = 0.4, .max_repeat = 5, .max_tokens = 64 }; 58 for (int i = 0; i < 5000; i++) { 59 conn_sym buf[64]; size_t n = 0; 60 KitGramGenStatus st = conn_sample(CONN_session, &cfg, buf, 64, &n); 61 CHECK(st == KIT_GRAM_GEN_DONE); 62 conn_kind k; 63 CHECK(conn_fsm_accepts(buf, n, &k) && k == CONN_session); 64 } 65 66 /* Determinism: same seed -> same trace. */ 67 conn_gen_config a = { .seed = 7, .stop_prob = 0.5, .max_repeat = 3, .max_tokens = 64 }; 68 conn_gen_config b = a; 69 conn_sym ba[64], bb[64]; size_t na, nb; 70 conn_sample(CONN_session, &a, ba, 64, &na); 71 conn_sample(CONN_session, &b, bb, 64, &nb); 72 CHECK(na == nb && memcmp(ba, bb, na * sizeof *ba) == 0); 73 74 /* stop_prob = 1.0 -> loops never extend -> minimum length (5 symbols). */ 75 conn_gen_config mn = { .seed = 1, .stop_prob = 1.0, .max_repeat = 9, .max_tokens = 64 }; 76 conn_sym bm[64]; size_t nm = 0; 77 CHECK(conn_sample(CONN_session, &mn, bm, 64, &nm) == KIT_GRAM_GEN_DONE && nm == 5); 78 79 /* max_tokens overflow -> LIMIT, truncated. */ 80 conn_gen_config lim = { .seed = 1, .stop_prob = 0.0, .max_repeat = 100, .max_tokens = 4 }; 81 conn_sym bl[8]; size_t nl = 0; 82 CHECK(conn_sample(CONN_session, &lim, bl, 8, &nl) == KIT_GRAM_GEN_LIMIT && nl == 4); 83 } 84 85 /* ---- kinds: distinct accept kinds + source-order priority ---------------- */ 86 static void test_kinds(void) { 87 kinds_kind k = (kinds_kind)-1; 88 kinds_sym hw[] = { KINDS_HELLO, KINDS_WORLD }; 89 /* greet and greet2 share the language "HELLO WORLD"; greet (declared first) 90 * wins the same-length tie. */ 91 CHECK(kinds_fsm_accepts(hw, 2, &k) && k == KINDS_greet); 92 kinds_sym by[] = { KINDS_BYE }; 93 CHECK(kinds_fsm_accepts(by, 1, &k) && k == KINDS_bye); 94 kinds_sym bad[] = { KINDS_HELLO }; 95 CHECK(!kinds_fsm_accepts(bad, 1, NULL)); 96 97 /* Sampling each rule reaches its own kind. */ 98 kinds_gen_config cfg = { .seed = 3, .stop_prob = 0.5, .max_repeat = 2, .max_tokens = 16 }; 99 kinds_sym buf[16]; size_t n; 100 kinds_kind which; 101 CHECK(kinds_sample(KINDS_bye, &cfg, buf, 16, &n) == KIT_GRAM_GEN_DONE); 102 CHECK(kinds_fsm_accepts(buf, n, &which) && which == KINDS_bye); 103 } 104 105 /* ---- shapes: +, ?, {n,m}, [^...], . -------------------------------------- */ 106 static void test_shapes(void) { 107 shapes_kind k; 108 /* word = START (vowel|CONS)+ STOP */ 109 shapes_sym w1[] = { SHAPES_START, SHAPES_A, SHAPES_STOP }; 110 CHECK(shapes_fsm_accepts(w1, 3, &k) && k == SHAPES_word); 111 shapes_sym w2[] = { SHAPES_START, SHAPES_CONS, SHAPES_E, SHAPES_CONS, SHAPES_STOP }; 112 CHECK(shapes_fsm_accepts(w2, 5, NULL)); 113 shapes_sym w0[] = { SHAPES_START, SHAPES_STOP }; 114 CHECK(!shapes_fsm_accepts(w0, 2, NULL)); /* need >= 1 body symbol */ 115 116 /* pair = L . R (any single symbol between) */ 117 shapes_sym p1[] = { SHAPES_L, SHAPES_Z, SHAPES_R }; 118 CHECK(shapes_fsm_accepts(p1, 3, &k) && k == SHAPES_pair); 119 shapes_sym p2[] = { SHAPES_L, SHAPES_R }; 120 CHECK(!shapes_fsm_accepts(p2, 2, NULL)); 121 122 /* notv = N [^ vowel ] (a set reference inside the complement) */ 123 shapes_sym nv_ok[] = { SHAPES_N, SHAPES_CONS }; 124 CHECK(shapes_fsm_accepts(nv_ok, 2, &k) && k == SHAPES_notv); 125 shapes_sym nv_bad[] = { SHAPES_N, SHAPES_A }; /* A is a vowel -> excluded */ 126 CHECK(!shapes_fsm_accepts(nv_bad, 2, NULL)); 127 128 /* reps = X{2,3} */ 129 shapes_sym r1[] = { SHAPES_X }; 130 shapes_sym r2[] = { SHAPES_X, SHAPES_X }; 131 shapes_sym r3[] = { SHAPES_X, SHAPES_X, SHAPES_X }; 132 shapes_sym r4[] = { SHAPES_X, SHAPES_X, SHAPES_X, SHAPES_X }; 133 CHECK(!shapes_fsm_accepts(r1, 1, NULL)); 134 CHECK(shapes_fsm_accepts(r2, 2, &k) && k == SHAPES_reps); 135 CHECK(shapes_fsm_accepts(r3, 3, NULL)); 136 CHECK(!shapes_fsm_accepts(r4, 4, NULL)); 137 138 /* maybe = P Q? Z */ 139 shapes_sym mb1[] = { SHAPES_P, SHAPES_Z }; 140 shapes_sym mb2[] = { SHAPES_P, SHAPES_Q, SHAPES_Z }; 141 CHECK(shapes_fsm_accepts(mb1, 2, &k) && k == SHAPES_maybe); 142 CHECK(shapes_fsm_accepts(mb2, 3, NULL)); 143 144 /* Round-trip each rule's sampler. */ 145 for (shapes_kind rule = 0; rule < SHAPES_KIND__COUNT; rule++) { 146 shapes_gen_config cfg = { .seed = 100u + rule, .stop_prob = 0.5, .max_repeat = 3, .max_tokens = 64 }; 147 for (int i = 0; i < 500; i++) { 148 shapes_sym buf[64]; size_t n; 149 CHECK(shapes_sample(rule, &cfg, buf, 64, &n) == KIT_GRAM_GEN_DONE); 150 shapes_kind which; 151 CHECK(shapes_fsm_accepts(buf, n, &which)); 152 } 153 } 154 } 155 156 /* ---- sets: set references + set algebra (&&, --, ^) inside [ ] ----------- */ 157 static void test_sets(void) { 158 sets_kind k; 159 /* anyv = V [ vowel ] : a vowel, named by set reference */ 160 sets_sym av_ok[] = { SETS_V, SETS_A }; 161 sets_sym av_bad[] = { SETS_V, SETS_B }; /* B is not a vowel */ 162 CHECK(sets_fsm_accepts(av_ok, 2, &k) && k == SETS_anyv); 163 CHECK(!sets_fsm_accepts(av_bad, 2, NULL)); 164 165 /* notv = N [^ vowel ] : complement of a set */ 166 sets_sym nv_ok[] = { SETS_N, SETS_B }; /* B is not a vowel */ 167 sets_sym nv_bad[] = { SETS_N, SETS_A }; 168 CHECK(sets_fsm_accepts(nv_ok, 2, &k) && k == SETS_notv); 169 CHECK(!sets_fsm_accepts(nv_bad, 2, NULL)); 170 171 /* inboth = P [ both ] : both = vowel | cons (union of two sets) */ 172 sets_sym ib_v[] = { SETS_P, SETS_E }; /* a vowel -> in both */ 173 sets_sym ib_c[] = { SETS_P, SETS_C }; /* a cons -> in both */ 174 sets_sym ib_no[] = { SETS_P, SETS_Y }; /* Y in neither set */ 175 CHECK(sets_fsm_accepts(ib_v, 2, &k) && k == SETS_inboth); 176 CHECK(sets_fsm_accepts(ib_c, 2, NULL)); 177 CHECK(!sets_fsm_accepts(ib_no, 2, NULL)); 178 179 /* outb = M [^ both ] : complement of the union set */ 180 sets_sym ob_ok[] = { SETS_M, SETS_Y }; /* Y outside both */ 181 sets_sym ob_v[] = { SETS_M, SETS_A }; /* vowel -> in both */ 182 sets_sym ob_c[] = { SETS_M, SETS_B }; /* cons -> in both */ 183 CHECK(sets_fsm_accepts(ob_ok, 2, &k) && k == SETS_outb); 184 CHECK(!sets_fsm_accepts(ob_v, 2, NULL)); 185 CHECK(!sets_fsm_accepts(ob_c, 2, NULL)); 186 187 /* vy = W [ vowy ] : vowy = [ vow Y ] (set ref + symbol in a bracket) */ 188 sets_sym vy_v[] = { SETS_W, SETS_O }; /* a vowel -> in vowy */ 189 sets_sym vy_y[] = { SETS_W, SETS_Y }; /* Y -> in vowy */ 190 sets_sym vy_no[] = { SETS_W, SETS_B }; /* B not in vowy */ 191 CHECK(sets_fsm_accepts(vy_v, 2, &k) && k == SETS_vy); 192 CHECK(sets_fsm_accepts(vy_y, 2, NULL)); 193 CHECK(!sets_fsm_accepts(vy_no, 2, NULL)); 194 195 /* inter = I [ both && con ] : intersection -> con (= {B,C}) */ 196 sets_sym it_ok[] = { SETS_I, SETS_B }; 197 sets_sym it_bad[] = { SETS_I, SETS_A }; /* vowel, not in con */ 198 CHECK(sets_fsm_accepts(it_ok, 2, &k) && k == SETS_inter); 199 CHECK(!sets_fsm_accepts(it_bad, 2, NULL)); 200 201 /* diff = D [ both -- vow ] : difference -> con */ 202 sets_sym df_ok[] = { SETS_D, SETS_C }; 203 sets_sym df_bad[] = { SETS_D, SETS_E }; /* vowel removed */ 204 CHECK(sets_fsm_accepts(df_ok, 2, &k) && k == SETS_diff); 205 CHECK(!sets_fsm_accepts(df_bad, 2, NULL)); 206 207 /* cnv = K [ notvw && both ] : (complement of vow) ∩ both -> con */ 208 sets_sym cn_ok[] = { SETS_K, SETS_B }; 209 sets_sym cn_bad[] = { SETS_K, SETS_A }; /* A is a vowel */ 210 CHECK(sets_fsm_accepts(cn_ok, 2, &k) && k == SETS_cnv); 211 CHECK(!sets_fsm_accepts(cn_bad, 2, NULL)); 212 213 /* Round-trip each rule's sampler: every sampled trace must verify. */ 214 for (sets_kind rule = 0; rule < SETS_KIND__COUNT; rule++) { 215 sets_gen_config cfg = { .seed = 200u + rule, .stop_prob = 0.5, .max_repeat = 3, .max_tokens = 64 }; 216 for (int i = 0; i < 500; i++) { 217 sets_sym buf[64]; size_t n; 218 CHECK(sets_sample(rule, &cfg, buf, 64, &n) == KIT_GRAM_GEN_DONE); 219 sets_kind which; 220 CHECK(sets_fsm_accepts(buf, n, &which)); 221 } 222 } 223 } 224 225 /* ---- overlap: overlapping alts resolved by the subset construction ------- */ 226 static void test_overlap(void) { 227 overlap_kind k; 228 overlap_sym ab[] = { OVERLAP_A, OVERLAP_B }; 229 overlap_sym ac[] = { OVERLAP_A, OVERLAP_C }; 230 overlap_sym abd[] = { OVERLAP_A, OVERLAP_B, OVERLAP_D }; 231 overlap_sym a[] = { OVERLAP_A }; 232 overlap_sym abx[] = { OVERLAP_A, OVERLAP_B, OVERLAP_A }; 233 CHECK(overlap_fsm_accepts(ab, 2, &k) && k == OVERLAP_r); 234 CHECK(overlap_fsm_accepts(ac, 2, NULL)); 235 CHECK(overlap_fsm_accepts(abd, 3, NULL)); 236 CHECK(!overlap_fsm_accepts(a, 1, NULL)); 237 CHECK(!overlap_fsm_accepts(abx, 3, NULL)); 238 } 239 240 /* ---- epsilon: ε-accepting machine (empty trace is valid) ----------------- */ 241 static void test_epsilon(void) { 242 epsilon_kind k = (epsilon_kind)-1; 243 CHECK(epsilon_fsm_accepts(NULL, 0, &k) && k == EPSILON_opt); /* empty accepts */ 244 epsilon_sym h[] = { EPSILON_HEAD }; 245 epsilon_sym t[] = { EPSILON_TAIL }; 246 epsilon_sym ht[] = { EPSILON_HEAD, EPSILON_TAIL }; 247 epsilon_sym th[] = { EPSILON_TAIL, EPSILON_HEAD }; 248 CHECK(epsilon_fsm_accepts(h, 1, NULL)); 249 CHECK(epsilon_fsm_accepts(t, 1, NULL)); 250 CHECK(epsilon_fsm_accepts(ht, 2, NULL)); 251 CHECK(!epsilon_fsm_accepts(th, 2, NULL)); /* order: HEAD before TAIL */ 252 253 /* The start state is accepting and live. */ 254 epsilon_fsm m; epsilon_fsm_init(&m); 255 CHECK(epsilon_fsm_accepting(&m, NULL)); 256 CHECK(epsilon_fsm_live(&m)); 257 } 258 259 int main(void) { 260 test_conn(); 261 test_conn_sampler(); 262 test_kinds(); 263 test_shapes(); 264 test_sets(); 265 test_overlap(); 266 test_epsilon(); 267 if (failures) { 268 printf("test_machine: %d failure(s)\n", failures); 269 return 1; 270 } 271 printf("test_machine: all %%machine verifier + sampler checks passed\n"); 272 return 0; 273 }