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