match_test.c (18218B)
1 /* test_match.c - exercises the Tier-1 anchor + re2::Set match API and the 2 * gramregex single-pattern facade, plus tokenizer-side anchor enforcement. */ 3 #include <kit/gram.h> 4 5 #include <stdio.h> 6 #include <stdlib.h> 7 #include <string.h> 8 9 #include "gram_test.h" 10 11 static int failures = 0; 12 static int checks = 0; 13 14 static void check(int cond, const char *msg) { 15 checks++; 16 if (cond) { 17 printf("ok %s\n", msg); 18 } else { 19 printf("FAIL %s\n", msg); 20 failures++; 21 } 22 } 23 24 /* Bind a resident single-span buffer as a finished input. */ 25 static void input_set(KitGramLexInput *in, KitGramLexInputSpan *span, 26 const char *bytes, size_t len) { 27 kit_gram_lex_input_init(in, NULL); 28 *span = (KitGramLexInputSpan){ .bytes = (const unsigned char *)bytes, .len = len }; 29 kit_gram_lex_input_push(in, span); 30 kit_gram_lex_input_finish(in); 31 } 32 33 static int match_eq(const KitGramMatch *m, size_t start, size_t end) { 34 return m->start == start && m->end == end; 35 } 36 37 /* Drain the find iterator into a caller buffer — the bulk-collect convenience 38 * the removed kit_gram_match_find_all used to provide, now built on KitGramMatchIter. */ 39 static size_t drain(KitGramMatcher *m, KitGramLexInput *in, 40 const KitGramMatchOpts *opts, KitGramMatch *out, size_t cap) { 41 KitGramMatchIter it; 42 kit_gram_match_iter_init(&it, m, in, opts); 43 size_t n = 0; 44 while (n < cap && kit_gram_match_iter_next(&it, &out[n])) n++; 45 return n; 46 } 47 48 /* --- match API over gramregex single patterns ----------------------------- */ 49 50 static void test_regex_find(void) { 51 KitGramOptions opts = {0}; 52 KitGramCompiled *re = NULL; 53 KitStatus st = kit_gram_regex_compile(gram_test_ctx(), KIT_SLICE_LIT("[0-9][0-9]*"), &opts, &re); 54 check(st == KIT_OK && re != NULL, "kit_gram_regex_compile digit pattern"); 55 if (st != KIT_OK || !re) return; 56 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_regex_grammar(re)); 57 KitGramTokenKind kind = kit_gram_regex_kind(re); 58 check(kit_gram_regex_grammar(re) != NULL && kind != 0, "kit_gram_regex_grammar/kind available"); 59 60 KitGramLexInput in; 61 KitGramLexInputSpan span; 62 KitGramMatch m; 63 64 input_set(&in, &span, "abc123def45", 11); 65 check(kit_gram_match_find(&mx, &in, NULL, &m) && match_eq(&m, 3, 6) && m.kind == kind, 66 "find leftmost digit run (123)"); 67 68 KitGramMatch all[8]; 69 input_set(&in, &span, "abc123def45", 11); 70 size_t n = drain(&mx, &in, NULL, all, 8); 71 check(n == 2 && match_eq(&all[0], 3, 6) && match_eq(&all[1], 9, 11), 72 "find_all two digit runs"); 73 74 input_set(&in, &span, "123abc", 6); 75 check(kit_gram_match_anchored(&mx, &in, NULL, &m) && match_eq(&m, 0, 3), 76 "anchored matches at start"); 77 78 input_set(&in, &span, "abc123", 6); 79 check(!kit_gram_match_anchored(&mx, &in, NULL, &m), "anchored fails off start"); 80 81 input_set(&in, &span, "123", 3); 82 check(kit_gram_match_full(&mx, &in, NULL, &m) && match_eq(&m, 0, 3), "full matches whole input"); 83 84 input_set(&in, &span, "123x", 4); 85 check(!kit_gram_match_full(&mx, &in, NULL, &m), "full rejects trailing bytes"); 86 87 input_set(&in, &span, "", 0); 88 check(!kit_gram_match_find(&mx, &in, NULL, &m), "find on empty input is no match"); 89 90 kit_gram_free(re); 91 } 92 93 /* The find iterator: successive non-overlapping matches pulled lazily, the 94 * caller deciding when to stop (no caller-sized result buffer). */ 95 static void test_match_iter(void) { 96 KitGramOptions opts = {0}; 97 KitGramCompiled *re = NULL; 98 KitStatus st = kit_gram_regex_compile(gram_test_ctx(), KIT_SLICE_LIT("[0-9][0-9]*"), &opts, &re); 99 check(st == KIT_OK && re != NULL, "kit_gram_regex_compile for iter"); 100 if (st != KIT_OK || !re) return; 101 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_regex_grammar(re)); 102 KitGramTokenKind kind = kit_gram_regex_kind(re); 103 104 KitGramLexInput in; 105 KitGramLexInputSpan span; 106 KitGramMatch m; 107 108 /* a1 22 333b -> "1"@[1,2) "22"@[3,5) "333"@[6,9) */ 109 input_set(&in, &span, "a1 22 333b", 10); 110 KitGramMatchIter it; 111 kit_gram_match_iter_init(&it, &mx, &in, NULL); 112 check(kit_gram_match_iter_next(&it, &m) && match_eq(&m, 1, 2) && m.kind == kind, 113 "iter pull 1 = '1'"); 114 check(kit_gram_match_iter_next(&it, &m) && match_eq(&m, 3, 5), "iter pull 2 = '22'"); 115 /* Stop early after two pulls — the third match is simply never requested. */ 116 check(kit_gram_match_iter_next(&it, &m) && match_eq(&m, 6, 9), "iter pull 3 = '333'"); 117 check(!kit_gram_match_iter_next(&it, &m), "iter exhausted -> false"); 118 check(!kit_gram_match_iter_next(&it, &m), "iter stays exhausted (idempotent)"); 119 120 /* No match anywhere: the very first pull reports exhaustion. */ 121 input_set(&in, &span, "abc", 3); 122 kit_gram_match_iter_init(&it, &mx, &in, NULL); 123 check(!kit_gram_match_iter_next(&it, &m), "iter on no-match input is immediately false"); 124 125 kit_gram_free(re); 126 } 127 128 static void test_regex_inpattern_anchors(void) { 129 KitGramOptions opts = {0}; 130 /* \A ... \z : the whole text must be the match, even under find. */ 131 KitGramCompiled *re = NULL; 132 KitStatus st = kit_gram_regex_compile(gram_test_ctx(), KIT_SLICE_LIT("\\A[0-9][0-9]*\\z"), &opts, &re); 133 check(st == KIT_OK && re != NULL, "kit_gram_regex_compile \\A..\\z"); 134 if (st != KIT_OK || !re) return; 135 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_regex_grammar(re)); 136 KitGramLexInput in; 137 KitGramLexInputSpan span; 138 KitGramMatch m; 139 140 input_set(&in, &span, "123", 3); 141 check(kit_gram_match_find(&mx, &in, NULL, &m) && match_eq(&m, 0, 3), "\\A..\\z find on exact"); 142 143 input_set(&in, &span, "x123", 4); 144 check(!kit_gram_match_find(&mx, &in, NULL, &m), "\\A..\\z rejects leading junk (start anchor)"); 145 146 input_set(&in, &span, "123x", 4); 147 check(!kit_gram_match_find(&mx, &in, NULL, &m), "\\A..\\z rejects trailing junk (end anchor)"); 148 149 kit_gram_free(re); 150 } 151 152 static void test_regex_multiline(void) { 153 KitGramOptions opts = {0}; 154 KitGramCompiled *re = NULL; 155 KitStatus st = kit_gram_regex_compile(gram_test_ctx(), KIT_SLICE_LIT("[a-z][a-z]*$"), &opts, &re); 156 check(st == KIT_OK && re != NULL, "kit_gram_regex_compile [a-z]+$"); 157 if (st != KIT_OK || !re) return; 158 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_regex_grammar(re)); 159 KitGramLexInput in; 160 KitGramLexInputSpan span; 161 KitGramMatch m; 162 KitGramMatchOpts ml = { .multiline = true }; 163 164 /* Without multiline, $ == \z (end of text), so only the final run matches. */ 165 input_set(&in, &span, "foo\nbar", 7); 166 check(kit_gram_match_find(&mx, &in, NULL, &m) && match_eq(&m, 4, 7), 167 "$ default: only end-of-text run matches"); 168 169 /* With multiline, $ also matches right before a newline. */ 170 input_set(&in, &span, "foo\nbar", 7); 171 check(kit_gram_match_find(&mx, &in, &ml, &m) && match_eq(&m, 0, 3), 172 "$ multiline: matches before newline"); 173 174 KitGramMatch all[8]; 175 input_set(&in, &span, "foo\nbar", 7); 176 size_t n = drain(&mx, &in, &ml, all, 8); 177 check(n == 2 && match_eq(&all[0], 0, 3) && match_eq(&all[1], 4, 7), 178 "$ multiline find_all both lines"); 179 180 kit_gram_free(re); 181 } 182 183 static void test_caret_multiline(void) { 184 KitGramOptions opts = {0}; 185 KitGramCompiled *re = NULL; 186 KitStatus st = kit_gram_regex_compile(gram_test_ctx(), KIT_SLICE_LIT("^[a-z][a-z]*"), &opts, &re); 187 check(st == KIT_OK && re != NULL, "kit_gram_regex_compile ^[a-z]+"); 188 if (st != KIT_OK || !re) return; 189 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_regex_grammar(re)); 190 KitGramLexInput in; 191 KitGramLexInputSpan span; 192 KitGramMatch m; 193 KitGramMatchOpts ml = { .multiline = true }; 194 195 input_set(&in, &span, "foo\nbar", 7); 196 check(kit_gram_match_find(&mx, &in, NULL, &m) && match_eq(&m, 0, 3), 197 "^ default: only start-of-text run"); 198 199 KitGramMatch all[8]; 200 input_set(&in, &span, "foo\nbar", 7); 201 size_t n = drain(&mx, &in, &ml, all, 8); 202 check(n == 2 && match_eq(&all[0], 0, 3) && match_eq(&all[1], 4, 7), 203 "^ multiline matches after newline"); 204 205 kit_gram_free(re); 206 } 207 208 /* --- Set (multi-pattern) via a full grammar ----------------------------- */ 209 210 static void test_set_find_all(void) { 211 static const char SRC[] = 212 "%lex {\n" 213 " INT = [0-9][0-9]*;\n" 214 " WORD = [a-z][a-z]*;\n" 215 "}\n" 216 "start = INT | WORD;\n"; 217 KitGramOptions opts = {0}; 218 KitGramCompiled *c = NULL; 219 KitStatus st = kit_gram_compile_text(gram_test_ctx(), (KitSlice){.s=SRC,.len=strlen(SRC)}, KIT_SLICE_LIT("<set>"), &opts, &c); 220 check(st == KIT_OK && c != NULL, "compile Set grammar"); 221 if (st != KIT_OK || !c) return; 222 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_lexer_grammar(c)); 223 KitGramTokenKind k_int = 0, k_word = 0; 224 kit_gram_find_token(c, "INT", &k_int); 225 kit_gram_find_token(c, "WORD", &k_word); 226 227 KitGramLexInput in; 228 KitGramLexInputSpan span; 229 KitGramMatch all[8]; 230 input_set(&in, &span, "ab12 cd", 7); 231 size_t n = drain(&mx, &in, NULL, all, 8); 232 check(n == 3, "Set find_all count"); 233 check(n == 3 && all[0].kind == k_word && match_eq(&all[0], 0, 2), "Set match 0 = WORD ab"); 234 check(n == 3 && all[1].kind == k_int && match_eq(&all[1], 2, 4), "Set match 1 = INT 12"); 235 check(n == 3 && all[2].kind == k_word && match_eq(&all[2], 5, 7), "Set match 2 = WORD cd"); 236 237 kit_gram_free(c); 238 } 239 240 #ifndef KIT_GRAM_NO_UNICODE 241 /* utf8 grammar: ^/$ multiline must recognize a multi-byte newline scalar 242 * (U+2028 LINE SEPARATOR, bytes E2 80 A8) on both sides of the cursor. */ 243 static void test_utf8_multiline(void) { 244 static const char SRC[] = 245 "%lex :utf8 {\n" 246 " W = [a-z] [a-z]*;\n" 247 "}\n" 248 "start = W;\n"; 249 KitGramOptions opts = {0}; 250 KitGramCompiled *c = NULL; 251 KitStatus st = kit_gram_compile_text(gram_test_ctx(), (KitSlice){.s=SRC,.len=strlen(SRC)}, KIT_SLICE_LIT("<u8>"), &opts, &c); 252 check(st == KIT_OK && c != NULL, "compile utf8 Set grammar"); 253 if (st != KIT_OK || !c) return; 254 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_lexer_grammar(c)); 255 KitGramMatchOpts ml = { .multiline = true }; 256 KitGramLexInput in; 257 KitGramLexInputSpan span; 258 KitGramMatch all[8]; 259 260 /* "foo" U+2028 "bar" => 3 + 3 + 3 = 9 bytes. */ 261 const char *text = "foo\xE2\x80\xA8" "bar"; 262 input_set(&in, &span, text, 9); 263 size_t n = drain(&mx, &in, &ml, all, 8); 264 check(n == 2 && match_eq(&all[0], 0, 3) && match_eq(&all[1], 6, 9), 265 "utf8 multiline find_all splits on U+2028"); 266 267 kit_gram_free(c); 268 } 269 #endif 270 271 /* --- tokenizer-side anchor enforcement ---------------------------------- */ 272 273 static void test_tokenizer_anchor(void) { 274 static const char SRC[] = 275 "%lex {\n" 276 " HEAD = \\A \"a\";\n" 277 " %skip WS = \" \";\n" 278 "}\n" 279 "start = HEAD;\n"; 280 KitGramOptions opts = {0}; 281 KitGramCompiled *c = NULL; 282 KitStatus cst = kit_gram_compile_text(gram_test_ctx(), (KitSlice){.s=SRC,.len=strlen(SRC)}, KIT_SLICE_LIT("<anchortok>"), &opts, &c); 283 check(cst == KIT_OK && c != NULL, "compile tokenizer-anchor grammar"); 284 if (cst != KIT_OK || !c) return; 285 const KitGramLexGrammar *g = kit_gram_lexer_grammar(c); 286 287 KitGramLexInput in; 288 KitGramLexInputSpan span; 289 input_set(&in, &span, "a a", 3); 290 KitGramLexer lx; 291 kit_gram_lexer_init(&lx, g, &in, &(KitGramLexConfig){0}); 292 293 KitGramToken tok; 294 KitGramLexStatus st = kit_gram_lexer_next(&lx, &tok); 295 check(st == KIT_GRAM_LEX_TOKEN && tok.len == 1, "anchored token matches at text start"); 296 /* Second 'a' is not at text start, so \A is not satisfied: winner-only error. */ 297 st = kit_gram_lexer_next(&lx, &tok); 298 check(st == KIT_GRAM_LEX_ERROR, "anchored token off start is a lex error"); 299 300 kit_gram_free(c); 301 } 302 303 /* Regression: a winning anchored recognizer whose anchor fails must fall back to 304 * a lower-priority recognizer that also matches, instead of dropping the match. 305 * Previously winner-only anchoring collapsed each accept state to one recognizer 306 * and filtered it after selection, so the fallback was lost. */ 307 static void test_anchor_start_fallback(void) { 308 /* No %skip: the match API is a raw Set and would surface a skip recognizer as 309 * a match, so the unmatched space is just advanced past by find. */ 310 static const char SRC[] = 311 "%lex {\n" 312 " KW = \\A \"if\";\n" 313 " ID = [a-z][a-z]*;\n" 314 "}\n" 315 "start = KW | ID;\n"; 316 KitGramOptions opts = {0}; 317 KitGramCompiled *c = NULL; 318 KitStatus st = kit_gram_compile_text(gram_test_ctx(), (KitSlice){.s=SRC,.len=strlen(SRC)}, KIT_SLICE_LIT("<fallback>"), &opts, &c); 319 check(st == KIT_OK && c != NULL, "compile start-anchor fallback grammar"); 320 if (st != KIT_OK || !c) return; 321 KitGramTokenKind k_kw = 0, k_id = 0; 322 kit_gram_find_token(c, "KW", &k_kw); 323 kit_gram_find_token(c, "ID", &k_id); 324 325 /* Match API: the mid-text "if" falls back to ID, not a one-byte advance. */ 326 KitGramLexInput in; 327 KitGramLexInputSpan span; 328 KitGramMatch all[8]; 329 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_lexer_grammar(c)); 330 input_set(&in, &span, "if if", 5); 331 size_t n = drain(&mx, &in, NULL, all, 8); 332 check(n == 2 && all[0].kind == k_kw && match_eq(&all[0], 0, 2), "find_all: leading if = KW"); 333 check(n == 2 && all[1].kind == k_id && match_eq(&all[1], 3, 5), "find_all: mid-text if falls back to ID"); 334 335 kit_gram_free(c); 336 337 /* Tokenizer: same fallback, with a skip rule so the cursor reaches the second 338 * "if" mid-text — it must be ID, not the old winner-only anchor error. */ 339 static const char TSRC[] = 340 "%lex {\n" 341 " KW = \\A \"if\";\n" 342 " ID = [a-z][a-z]*;\n" 343 " %skip WS = \" \";\n" 344 "}\n" 345 "start = KW | ID;\n"; 346 st = kit_gram_compile_text(gram_test_ctx(), (KitSlice){.s=TSRC,.len=strlen(TSRC)}, KIT_SLICE_LIT("<fallbacktok>"), &opts, &c); 347 check(st == KIT_OK && c != NULL, "compile start-anchor tokenizer grammar"); 348 if (st != KIT_OK || !c) return; 349 const KitGramLexGrammar *g = kit_gram_lexer_grammar(c); 350 kit_gram_find_token(c, "KW", &k_kw); 351 kit_gram_find_token(c, "ID", &k_id); 352 input_set(&in, &span, "if if", 5); 353 KitGramLexer lx; 354 kit_gram_lexer_init(&lx, g, &in, &(KitGramLexConfig){0}); 355 KitGramToken tok; 356 check(kit_gram_lexer_next(&lx, &tok) == KIT_GRAM_LEX_TOKEN && tok.kind == k_kw && tok.len == 2, 357 "tokenizer: leading if = KW"); 358 check(kit_gram_lexer_next(&lx, &tok) == KIT_GRAM_LEX_TOKEN && tok.kind == k_id && tok.len == 2, 359 "tokenizer: mid-text if falls back to ID"); 360 361 kit_gram_free(c); 362 } 363 364 /* End-anchor counterpart: a \z recognizer wins at text end (priority tie) but a 365 * mid-text occurrence falls back to the unanchored recognizer. */ 366 static void test_anchor_end_fallback(void) { 367 static const char SRC[] = 368 "%lex {\n" 369 " END = \"ab\" \\z;\n" 370 " ID = [a-z][a-z]*;\n" 371 "}\n" 372 "start = END | ID;\n"; 373 KitGramOptions opts = {0}; 374 KitGramCompiled *c = NULL; 375 KitStatus st = kit_gram_compile_text(gram_test_ctx(), (KitSlice){.s=SRC,.len=strlen(SRC)}, KIT_SLICE_LIT("<endfb>"), &opts, &c); 376 check(st == KIT_OK && c != NULL, "compile end-anchor fallback grammar"); 377 if (st != KIT_OK || !c) return; 378 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_lexer_grammar(c)); 379 KitGramTokenKind k_end = 0, k_id = 0; 380 kit_gram_find_token(c, "END", &k_end); 381 kit_gram_find_token(c, "ID", &k_id); 382 383 KitGramLexInput in; 384 KitGramLexInputSpan span; 385 KitGramMatch all[8]; 386 input_set(&in, &span, "ab ab", 5); 387 size_t n = drain(&mx, &in, NULL, all, 8); 388 check(n == 2 && all[0].kind == k_id && match_eq(&all[0], 0, 2), "find_all: mid-text ab falls back to ID"); 389 check(n == 2 && all[1].kind == k_end && match_eq(&all[1], 3, 5), "find_all: trailing ab = END (\\z)"); 390 391 kit_gram_free(c); 392 } 393 394 #ifndef KIT_GRAM_NO_UNICODE 395 /* utf8 pipeline: start/end edge anchors must work there too. */ 396 static void test_utf8_anchor_fallback(void) { 397 static const char SRC[] = 398 "%lex :utf8 {\n" 399 " KW = \\A \"if\";\n" 400 " ID = [a-z][a-z]*;\n" 401 "}\n" 402 "start = KW | ID;\n"; 403 KitGramOptions opts = {0}; 404 KitGramCompiled *c = NULL; 405 KitStatus st = kit_gram_compile_text(gram_test_ctx(), (KitSlice){.s=SRC,.len=strlen(SRC)}, KIT_SLICE_LIT("<u8fb>"), &opts, &c); 406 check(st == KIT_OK && c != NULL, "compile utf8 anchor grammar"); 407 if (st != KIT_OK || !c) return; 408 KitGramMatcher mx; kit_gram_matcher_bind(&mx, kit_gram_lexer_grammar(c)); 409 KitGramTokenKind k_kw = 0, k_id = 0; 410 kit_gram_find_token(c, "KW", &k_kw); 411 kit_gram_find_token(c, "ID", &k_id); 412 413 KitGramLexInput in; 414 KitGramLexInputSpan span; 415 KitGramMatch all[8]; 416 input_set(&in, &span, "if if", 5); 417 size_t n = drain(&mx, &in, NULL, all, 8); 418 check(n == 2 && all[0].kind == k_kw && match_eq(&all[0], 0, 2), "utf8 find_all: leading if = KW"); 419 check(n == 2 && all[1].kind == k_id && match_eq(&all[1], 3, 5), "utf8 find_all: mid-text if = ID"); 420 421 kit_gram_free(c); 422 } 423 #endif 424 425 static void test_midpattern_anchor_error(void) { 426 static const char SRC[] = 427 "%lex {\n" 428 " BAD = [a-z] \\A [a-z];\n" 429 "}\n" 430 "start = BAD;\n"; 431 KitGramOptions opts = {0}; 432 KitGramCompiled *c = NULL; 433 KitStatus st = kit_gram_compile_text(gram_test_ctx(), (KitSlice){.s=SRC,.len=strlen(SRC)}, KIT_SLICE_LIT("<bad>"), &opts, &c); 434 check(st != KIT_OK && c == NULL, "mid-pattern anchor is rejected"); 435 } 436 437 int main(void) { 438 test_regex_find(); 439 test_match_iter(); 440 test_regex_inpattern_anchors(); 441 test_regex_multiline(); 442 test_caret_multiline(); 443 test_set_find_all(); 444 #ifndef KIT_GRAM_NO_UNICODE 445 test_utf8_multiline(); 446 #endif 447 test_tokenizer_anchor(); 448 test_anchor_start_fallback(); 449 test_anchor_end_fallback(); 450 #ifndef KIT_GRAM_NO_UNICODE 451 test_utf8_anchor_fallback(); 452 #endif 453 test_midpattern_anchor_error(); 454 printf("\n%d checks, %d failures\n", checks, failures); 455 return failures ? 1 : 0; 456 }