Felipe97/llama-cpp-compiled
01.1k
1#ifdef NDEBUG2#undef NDEBUG3#endif4 5#include "llama.h"6 7// TODO: shold not include libllama sources8#include "../src/llama-grammar.h"9 10#include <cassert>11 12static const char * type_str(llama_gretype type) {13 switch (type) {14 case LLAMA_GRETYPE_CHAR: return "LLAMA_GRETYPE_CHAR";15 case LLAMA_GRETYPE_CHAR_NOT: return "LLAMA_GRETYPE_CHAR_NOT";16 case LLAMA_GRETYPE_CHAR_ALT: return "LLAMA_GRETYPE_CHAR_ALT";17 case LLAMA_GRETYPE_CHAR_RNG_UPPER: return "LLAMA_GRETYPE_CHAR_RNG_UPPER";18 case LLAMA_GRETYPE_RULE_REF: return "LLAMA_GRETYPE_RULE_REF";19 case LLAMA_GRETYPE_ALT: return "LLAMA_GRETYPE_ALT";20 case LLAMA_GRETYPE_END: return "LLAMA_GRETYPE_END";21 default: return "?";22 }23}24 25static void verify_parsing(const char *grammar_bytes, const std::vector<std::pair<std::string, uint32_t>> expected, const std::vector<llama_grammar_element> &expected_rules) {26 uint32_t index = 0;27 llama_grammar_parser parsed_grammar;28 parsed_grammar.parse(grammar_bytes);29 30 std::map<uint32_t, std::string> symbol_names;31 for (auto it = parsed_grammar.symbol_ids.begin(); it != parsed_grammar.symbol_ids.end(); ++it) {32 symbol_names[it->second] = it->first;33 }34 35 auto print_all = [&]() {36 fprintf(stderr, " verify_parsing(R\"\"\"(%s)\"\"\", {\n", grammar_bytes);37 for (auto it = parsed_grammar.symbol_ids.begin(); it != parsed_grammar.symbol_ids.end(); ++it) {38 fprintf(stderr, " {\"%s\", %u},\n", it->first.c_str(), it->second);39 }40 fprintf(stderr, " }, {\n");41 for (size_t i_rule = 0; i_rule < parsed_grammar.rules.size(); i_rule++) {42 fprintf(stderr, " // %s (index %zu)\n", symbol_names[i_rule].c_str(), i_rule);43 auto & rule = parsed_grammar.rules[i_rule];44 for (uint32_t i = 0; i < rule.size(); i++) {45 std::string rule_str;46 fprintf(stderr, " {%s, ", type_str(rule[i].type));47 if (rule[i].type == LLAMA_GRETYPE_CHAR || rule[i].type == LLAMA_GRETYPE_CHAR_ALT ||48 rule[i].type == LLAMA_GRETYPE_CHAR_NOT || rule[i].type == LLAMA_GRETYPE_CHAR_RNG_UPPER) {49 char c = rule[i].value;50 if (c == '\n') {51 fprintf(stderr, "'\\n'");52 } else if (c == '\t') {53 fprintf(stderr, "'\\t'");54 } else if (c == '\r') {55 fprintf(stderr, "'\\r'");56 } else if (c == '\0') {57 fprintf(stderr, "'\\0'");58 } else {59 fprintf(stderr, "'%c'", c);60 }61 } else if (rule[i].type == LLAMA_GRETYPE_RULE_REF) {62 fprintf(stderr, "/* %s */ %u", symbol_names[rule[i].value].c_str(), rule[i].value);63 } else {64 fprintf(stderr, "%u", rule[i].value);65 }66 fprintf(stderr, "},\n");67 }68 }69 fprintf(stderr, " });\n");70 };71 72 if (getenv("TEST_GRAMMAR_PARSER_PRINT_ALL")) {73 print_all();74 fprintf(stderr, "\n");75 return;76 }77 78 fprintf(stderr, "Testing grammar:%s\n", grammar_bytes);79 80 if (parsed_grammar.symbol_ids.size() != expected.size()) {81 fprintf(stderr, "Code to update expectation (set TEST_GRAMMAR_PARSER_PRINT_ALL=1 to print all):\n");82 print_all();83 assert(parsed_grammar.symbol_ids.size() == expected.size());84 }85 86 for (auto it = parsed_grammar.symbol_ids.begin(); it != parsed_grammar.symbol_ids.end(); ++it)87 {88 std::string key = it->first;89 uint32_t value = it->second;90 std::pair<std::string, uint32_t> expected_pair = expected[index];91 92 // pretty print error message before asserting93 if (expected_pair.first != key || expected_pair.second != value)94 {95 fprintf(stderr, "index: %u\n", index);96 fprintf(stderr, "expected_pair: %s, %u\n", expected_pair.first.c_str(), expected_pair.second);97 fprintf(stderr, "actual_pair: %s, %u\n", key.c_str(), value);98 fprintf(stderr, "expected_pair != actual_pair\n");99 fprintf(stderr, "Code to update expectation (set TEST_GRAMMAR_PARSER_PRINT_ALL=1 to print all):\n");100 print_all();101 }102 103 assert(expected_pair.first == key && expected_pair.second == value);104 105 index++;106 }107 108 index = 0;109 for (auto rule : parsed_grammar.rules)110 {111 // compare rule to expected rule112 for (uint32_t i = 0; i < rule.size(); i++)113 {114 llama_grammar_element element = rule[i];115 llama_grammar_element expected_element = expected_rules[index];116 117 // pretty print error message before asserting118 if (expected_element.type != element.type || expected_element.value != element.value)119 {120 fprintf(stderr, "index: %u\n", index);121 fprintf(stderr, "expected_element: %s, %u\n", type_str(expected_element.type), expected_element.value);122 fprintf(stderr, "actual_element: %s, %u\n", type_str(element.type), element.value);123 fprintf(stderr, "expected_element != actual_element\n");124 fprintf(stderr, "all elements:\n");125 fprintf(stderr, "Code to update expectation (set TEST_GRAMMAR_PARSER_PRINT_ALL=1 to print all):\n");126 print_all();127 }128 129 assert(expected_element.type == element.type && expected_element.value == element.value);130 index++;131 }132 }133}134 135static void verify_failure(const char * grammar_bytes) {136 fprintf(stderr, "Testing expected failure:%s\n", grammar_bytes);137 llama_grammar_parser result;138 result.parse(grammar_bytes);139 assert(result.rules.empty() && "should have failed");140}141 142int main()143{144 verify_failure(R"""(145 root ::= "a"{,}"146 )""");147 148 verify_failure(R"""(149 root ::= (((((([^x]*){0,99}){0,99}){0,99}){0,99}){0,99}){0,99}150 )""");151 152 verify_failure(R"""(153 root ::= "a"{,10}"154 )""");155 156 verify_failure(R"""(157 root ::= "a"{5000}158 )""");159 160 verify_failure(R"""(161 root ::= "a"{5000,}162 )""");163 164 verify_failure(R"""(165 root ::= "a"{5000,6000}166 )""");167 168 verify_parsing(R"""(169 root ::= "a"{0,5000}170 )""", {171 {"root", 0},172 {"root_1", 1},173 }, {174 // root (index 0)175 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},176 {LLAMA_GRETYPE_END, 0},177 // root_1 (index 1)178 {LLAMA_GRETYPE_CHAR, 'a'},179 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},180 {LLAMA_GRETYPE_ALT, 0},181 {LLAMA_GRETYPE_END, 0},182 });183 184 verify_parsing(R"""(185 root ::= "a"{3,5000}186 )""", {187 {"root", 0},188 {"root_1", 1},189 }, {190 // root (index 0)191 {LLAMA_GRETYPE_CHAR, 'a'},192 {LLAMA_GRETYPE_CHAR, 'a'},193 {LLAMA_GRETYPE_CHAR, 'a'},194 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},195 {LLAMA_GRETYPE_END, 0},196 // root_1 (index 1)197 {LLAMA_GRETYPE_CHAR, 'a'},198 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},199 {LLAMA_GRETYPE_ALT, 0},200 {LLAMA_GRETYPE_END, 0},201 });202 203 verify_parsing(R"""(204 root ::= "a"205 )""", {206 {"root", 0},207 }, {208 // root (index 0)209 {LLAMA_GRETYPE_CHAR, 'a'},210 {LLAMA_GRETYPE_END, 0},211 });212 213 verify_parsing(R"""(214 root ::= "a" | [bdx-z] | [^1-3]215 )""", {216 {"root", 0},217 }, {218 // root (index 0)219 {LLAMA_GRETYPE_CHAR, 'a'},220 {LLAMA_GRETYPE_ALT, 0},221 {LLAMA_GRETYPE_CHAR, 'b'},222 {LLAMA_GRETYPE_CHAR_ALT, 'd'},223 {LLAMA_GRETYPE_CHAR_ALT, 'x'},224 {LLAMA_GRETYPE_CHAR_RNG_UPPER, 'z'},225 {LLAMA_GRETYPE_ALT, 0},226 {LLAMA_GRETYPE_CHAR_NOT, '1'},227 {LLAMA_GRETYPE_CHAR_RNG_UPPER, '3'},228 {LLAMA_GRETYPE_END, 0},229 });230 231 verify_parsing(R"""(232 root ::= a+233 a ::= "a"234 )""", {235 {"a", 1},236 {"root", 0},237 {"root_2", 2},238 }, {239 // root (index 0)240 {LLAMA_GRETYPE_RULE_REF, /* a */ 1},241 {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},242 {LLAMA_GRETYPE_END, 0},243 // a (index 1)244 {LLAMA_GRETYPE_CHAR, 'a'},245 {LLAMA_GRETYPE_END, 0},246 // root_2 (index 2)247 {LLAMA_GRETYPE_RULE_REF, /* a */ 1},248 {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},249 {LLAMA_GRETYPE_ALT, 0},250 {LLAMA_GRETYPE_END, 0},251 });252 253 verify_parsing(R"""(254 root ::= "a"+255 )""", {256 {"root", 0},257 {"root_1", 1},258 }, {259 // root (index 0)260 {LLAMA_GRETYPE_CHAR, 'a'},261 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},262 {LLAMA_GRETYPE_END, 0},263 // root_1 (index 1)264 {LLAMA_GRETYPE_CHAR, 'a'},265 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},266 {LLAMA_GRETYPE_ALT, 0},267 {LLAMA_GRETYPE_END, 0},268 });269 270 verify_parsing(R"""(271 root ::= a?272 a ::= "a"273 )""", {274 {"a", 1},275 {"root", 0},276 {"root_2", 2},277 }, {278 // root (index 0)279 {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},280 {LLAMA_GRETYPE_END, 0},281 // a (index 1)282 {LLAMA_GRETYPE_CHAR, 'a'},283 {LLAMA_GRETYPE_END, 0},284 // root_2 (index 2)285 {LLAMA_GRETYPE_RULE_REF, /* a */ 1},286 {LLAMA_GRETYPE_ALT, 0},287 {LLAMA_GRETYPE_END, 0},288 });289 290 verify_parsing(R"""(291 root ::= "a"?292 )""", {293 {"root", 0},294 {"root_1", 1},295 }, {296 // root (index 0)297 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},298 {LLAMA_GRETYPE_END, 0},299 // root_1 (index 1)300 {LLAMA_GRETYPE_CHAR, 'a'},301 {LLAMA_GRETYPE_ALT, 0},302 {LLAMA_GRETYPE_END, 0},303 });304 305 verify_parsing(R"""(306 root ::= a*307 a ::= "a"308 )""", {309 {"a", 1},310 {"root", 0},311 {"root_2", 2},312 }, {313 // root (index 0)314 {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},315 {LLAMA_GRETYPE_END, 0},316 // a (index 1)317 {LLAMA_GRETYPE_CHAR, 'a'},318 {LLAMA_GRETYPE_END, 0},319 // root_2 (index 2)320 {LLAMA_GRETYPE_RULE_REF, /* a */ 1},321 {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},322 {LLAMA_GRETYPE_ALT, 0},323 {LLAMA_GRETYPE_END, 0},324 });325 326 verify_parsing(R"""(327 root ::= "a"*328 )""", {329 {"root", 0},330 {"root_1", 1},331 }, {332 // root (index 0)333 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},334 {LLAMA_GRETYPE_END, 0},335 // root_1 (index 1)336 {LLAMA_GRETYPE_CHAR, 'a'},337 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},338 {LLAMA_GRETYPE_ALT, 0},339 {LLAMA_GRETYPE_END, 0},340 });341 342 verify_parsing(R"""(343 root ::= "a"{2}344 )""", {345 {"root", 0},346 }, {347 // root (index 0)348 {LLAMA_GRETYPE_CHAR, 'a'},349 {LLAMA_GRETYPE_CHAR, 'a'},350 {LLAMA_GRETYPE_END, 0},351 });352 353 verify_parsing(R"""(354 root ::= "a"{2,}355 )""", {356 {"root", 0},357 {"root_1", 1},358 }, {359 // root (index 0)360 {LLAMA_GRETYPE_CHAR, 'a'},361 {LLAMA_GRETYPE_CHAR, 'a'},362 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},363 {LLAMA_GRETYPE_END, 0},364 // root_1 (index 1)365 {LLAMA_GRETYPE_CHAR, 'a'},366 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},367 {LLAMA_GRETYPE_ALT, 0},368 {LLAMA_GRETYPE_END, 0},369 });370 371 verify_parsing(R"""(372 root ::= "a"{ 4}373 )""", {374 {"root", 0},375 }, {376 // root (index 0)377 {LLAMA_GRETYPE_CHAR, 'a'},378 {LLAMA_GRETYPE_CHAR, 'a'},379 {LLAMA_GRETYPE_CHAR, 'a'},380 {LLAMA_GRETYPE_CHAR, 'a'},381 {LLAMA_GRETYPE_END, 0},382 });383 384 verify_parsing(R"""(385 root ::= "a"{2,4}386 )""", {387 {"root", 0},388 {"root_1", 1},389 {"root_2", 2},390 }, {391 // root (index 0)392 {LLAMA_GRETYPE_CHAR, 'a'},393 {LLAMA_GRETYPE_CHAR, 'a'},394 {LLAMA_GRETYPE_RULE_REF, /* root_2 */ 2},395 {LLAMA_GRETYPE_END, 0},396 // root_1 (index 1)397 {LLAMA_GRETYPE_CHAR, 'a'},398 {LLAMA_GRETYPE_ALT, 0},399 {LLAMA_GRETYPE_END, 0},400 // root_2 (index 2)401 {LLAMA_GRETYPE_CHAR, 'a'},402 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},403 {LLAMA_GRETYPE_ALT, 0},404 {LLAMA_GRETYPE_END, 0},405 });406 407 verify_parsing(R"""(408 root ::= (expr "=" term "\n")+409 expr ::= term ([-+*/] term)*410 term ::= [0-9]+411 )""", {412 {"expr", 2},413 {"expr_5", 5},414 {"expr_6", 6},415 {"root", 0},416 {"root_1", 1},417 {"root_4", 4},418 {"term", 3},419 {"term_7", 7},420 }, {421 // root (index 0)422 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},423 {LLAMA_GRETYPE_RULE_REF, /* root_4 */ 4},424 {LLAMA_GRETYPE_END, 0},425 // root_1 (index 1)426 {LLAMA_GRETYPE_RULE_REF, /* expr */ 2},427 {LLAMA_GRETYPE_CHAR, '='},428 {LLAMA_GRETYPE_RULE_REF, /* term */ 3},429 {LLAMA_GRETYPE_CHAR, '\n'},430 {LLAMA_GRETYPE_END, 0},431 // expr (index 2)432 {LLAMA_GRETYPE_RULE_REF, /* term */ 3},433 {LLAMA_GRETYPE_RULE_REF, /* expr_6 */ 6},434 {LLAMA_GRETYPE_END, 0},435 // term (index 3)436 {LLAMA_GRETYPE_CHAR, '0'},437 {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},438 {LLAMA_GRETYPE_RULE_REF, /* term_7 */ 7},439 {LLAMA_GRETYPE_END, 0},440 // root_4 (index 4)441 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},442 {LLAMA_GRETYPE_RULE_REF, /* root_4 */ 4},443 {LLAMA_GRETYPE_ALT, 0},444 {LLAMA_GRETYPE_END, 0},445 // expr_5 (index 5)446 {LLAMA_GRETYPE_CHAR, '-'},447 {LLAMA_GRETYPE_CHAR_ALT, '+'},448 {LLAMA_GRETYPE_CHAR_ALT, '*'},449 {LLAMA_GRETYPE_CHAR_ALT, '/'},450 {LLAMA_GRETYPE_RULE_REF, /* term */ 3},451 {LLAMA_GRETYPE_END, 0},452 // expr_6 (index 6)453 {LLAMA_GRETYPE_RULE_REF, /* expr_5 */ 5},454 {LLAMA_GRETYPE_RULE_REF, /* expr_6 */ 6},455 {LLAMA_GRETYPE_ALT, 0},456 {LLAMA_GRETYPE_END, 0},457 // term_7 (index 7)458 {LLAMA_GRETYPE_CHAR, '0'},459 {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},460 {LLAMA_GRETYPE_RULE_REF, /* term_7 */ 7},461 {LLAMA_GRETYPE_ALT, 0},462 {LLAMA_GRETYPE_END, 0},463 });464 465 verify_parsing(R"""(466 root ::= (expr "=" ws term "\n")+467 expr ::= term ([-+*/] term)*468 term ::= ident | num | "(" ws expr ")" ws469 ident ::= [a-z] [a-z0-9_]* ws470 num ::= [0-9]+ ws471 ws ::= [ \t\n]*472 )""", {473 {"expr", 2},474 {"expr_6", 6},475 {"expr_7", 7},476 {"ident", 8},477 {"ident_10", 10},478 {"num", 9},479 {"num_11", 11},480 {"root", 0},481 {"root_1", 1},482 {"root_5", 5},483 {"term", 4},484 {"ws", 3},485 {"ws_12", 12},486 }, {487 // root (index 0)488 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},489 {LLAMA_GRETYPE_RULE_REF, /* root_5 */ 5},490 {LLAMA_GRETYPE_END, 0},491 // root_1 (index 1)492 {LLAMA_GRETYPE_RULE_REF, /* expr */ 2},493 {LLAMA_GRETYPE_CHAR, '='},494 {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},495 {LLAMA_GRETYPE_RULE_REF, /* term */ 4},496 {LLAMA_GRETYPE_CHAR, '\n'},497 {LLAMA_GRETYPE_END, 0},498 // expr (index 2)499 {LLAMA_GRETYPE_RULE_REF, /* term */ 4},500 {LLAMA_GRETYPE_RULE_REF, /* expr_7 */ 7},501 {LLAMA_GRETYPE_END, 0},502 // ws (index 3)503 {LLAMA_GRETYPE_RULE_REF, /* ws_12 */ 12},504 {LLAMA_GRETYPE_END, 0},505 // term (index 4)506 {LLAMA_GRETYPE_RULE_REF, /* ident */ 8},507 {LLAMA_GRETYPE_ALT, 0},508 {LLAMA_GRETYPE_RULE_REF, /* num */ 9},509 {LLAMA_GRETYPE_ALT, 0},510 {LLAMA_GRETYPE_CHAR, '('},511 {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},512 {LLAMA_GRETYPE_RULE_REF, /* expr */ 2},513 {LLAMA_GRETYPE_CHAR, ')'},514 {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},515 {LLAMA_GRETYPE_END, 0},516 // root_5 (index 5)517 {LLAMA_GRETYPE_RULE_REF, /* root_1 */ 1},518 {LLAMA_GRETYPE_RULE_REF, /* root_5 */ 5},519 {LLAMA_GRETYPE_ALT, 0},520 {LLAMA_GRETYPE_END, 0},521 // expr_6 (index 6)522 {LLAMA_GRETYPE_CHAR, '-'},523 {LLAMA_GRETYPE_CHAR_ALT, '+'},524 {LLAMA_GRETYPE_CHAR_ALT, '*'},525 {LLAMA_GRETYPE_CHAR_ALT, '/'},526 {LLAMA_GRETYPE_RULE_REF, /* term */ 4},527 {LLAMA_GRETYPE_END, 0},528 // expr_7 (index 7)529 {LLAMA_GRETYPE_RULE_REF, /* expr_6 */ 6},530 {LLAMA_GRETYPE_RULE_REF, /* expr_7 */ 7},531 {LLAMA_GRETYPE_ALT, 0},532 {LLAMA_GRETYPE_END, 0},533 // ident (index 8)534 {LLAMA_GRETYPE_CHAR, 'a'},535 {LLAMA_GRETYPE_CHAR_RNG_UPPER, 'z'},536 {LLAMA_GRETYPE_RULE_REF, /* ident_10 */ 10},537 {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},538 {LLAMA_GRETYPE_END, 0},539 // num (index 9)540 {LLAMA_GRETYPE_CHAR, '0'},541 {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},542 {LLAMA_GRETYPE_RULE_REF, /* num_11 */ 11},543 {LLAMA_GRETYPE_RULE_REF, /* ws */ 3},544 {LLAMA_GRETYPE_END, 0},545 // ident_10 (index 10)546 {LLAMA_GRETYPE_CHAR, 'a'},547 {LLAMA_GRETYPE_CHAR_RNG_UPPER, 'z'},548 {LLAMA_GRETYPE_CHAR_ALT, '0'},549 {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},550 {LLAMA_GRETYPE_CHAR_ALT, '_'},551 {LLAMA_GRETYPE_RULE_REF, /* ident_10 */ 10},552 {LLAMA_GRETYPE_ALT, 0},553 {LLAMA_GRETYPE_END, 0},554 // num_11 (index 11)555 {LLAMA_GRETYPE_CHAR, '0'},556 {LLAMA_GRETYPE_CHAR_RNG_UPPER, '9'},557 {LLAMA_GRETYPE_RULE_REF, /* num_11 */ 11},558 {LLAMA_GRETYPE_ALT, 0},559 {LLAMA_GRETYPE_END, 0},560 // ws_12 (index 12)561 {LLAMA_GRETYPE_CHAR, ' '},562 {LLAMA_GRETYPE_CHAR_ALT, '\t'},563 {LLAMA_GRETYPE_CHAR_ALT, '\n'},564 {LLAMA_GRETYPE_RULE_REF, /* ws_12 */ 12},565 {LLAMA_GRETYPE_ALT, 0},566 {LLAMA_GRETYPE_END, 0},567 });568 569 // <[1000]> = "<think>"570 // <[1001]> = "</think>"571 verify_parsing(R"""(572 root ::= <[1000]> !<[1001]> <[1001]>573 )""", {574 {"root", 0}575 }, {576 // root (index 0)577 {LLAMA_GRETYPE_TOKEN, 1000},578 {LLAMA_GRETYPE_TOKEN_NOT, 1001},579 {LLAMA_GRETYPE_TOKEN, 1001},580 {LLAMA_GRETYPE_END, 0},581 });582 583 return 0;584}585