Felipe97/llama-cpp-compiled
01.1k
1#include "tests.h"2 3#include "json-schema-to-grammar.h"4 5#include <regex>6 7static std::string trim_leading_space(const std::string & s) {8 static const std::regex leading_ws_re = std::regex(R"((^|\n)\s+)");9 return std::regex_replace(s, leading_ws_re, "$1");10}11 12static void assert_gbnf_equal(testing & t, const std::string & expected, const std::string & actual) {13 t.assert_equal("gbnf are equal", trim_leading_space(expected), trim_leading_space(actual));14}15 16void test_gbnf_generation(testing &t) {17 t.test("literal grammar generation", [](testing &t) {18 auto parser = build_peg_parser([](common_peg_parser_builder & p) {19 return p.literal("hello");20 });21 22 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {23 parser.build_grammar(builder);24 });25 26 assert_gbnf_equal(t, R"""(27 root ::= "hello"28 space ::= | " " | "\n"{1,2} [ \t]{0,20}29 )""", gbnf);30 });31 32 t.test("char class grammar", [](testing &t) {33 auto parser = build_peg_parser([](common_peg_parser_builder & p) {34 return p.chars("[a-z]", 1, 1);35 });36 37 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {38 parser.build_grammar(builder);39 });40 41 assert_gbnf_equal(t, R"""(42 root ::= [a-z]43 space ::= | " " | "\n"{1,2} [ \t]{0,20}44 )""", gbnf);45 });46 47 t.test("sequence grammar", [](testing &t) {48 auto parser = build_peg_parser([](common_peg_parser_builder & p) {49 return p.literal("hello") + p.literal(" ") + p.literal("world");50 });51 52 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {53 parser.build_grammar(builder);54 });55 56 assert_gbnf_equal(t, R"""(57 root ::= "hello" " " "world"58 space ::= | " " | "\n"{1,2} [ \t]{0,20}59 )""", gbnf);60 });61 62 t.test("choice grammar", [](testing &t) {63 auto parser = build_peg_parser([](common_peg_parser_builder & p) {64 return p.literal("cat") | p.literal("dog");65 });66 67 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {68 parser.build_grammar(builder);69 });70 71 assert_gbnf_equal(t, R"""(72 root ::= "cat" | "dog"73 space ::= | " " | "\n"{1,2} [ \t]{0,20}74 )""", gbnf);75 });76 77 t.test("one_or_more grammar", [](testing &t) {78 auto parser = build_peg_parser([](common_peg_parser_builder & p) {79 return p.one_or_more(p.literal("a"));80 });81 82 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {83 parser.build_grammar(builder);84 });85 86 assert_gbnf_equal(t, R"""(87 root ::= "a"+88 space ::= | " " | "\n"{1,2} [ \t]{0,20}89 )""", gbnf);90 });91 92 t.test("zero_or_more grammar", [](testing &t) {93 auto parser = build_peg_parser([](common_peg_parser_builder & p) {94 return p.zero_or_more(p.literal("a"));95 });96 97 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {98 parser.build_grammar(builder);99 });100 101 assert_gbnf_equal(t, R"""(102 root ::= "a"*103 space ::= | " " | "\n"{1,2} [ \t]{0,20}104 )""", gbnf);105 });106 107 t.test("optional grammar", [](testing &t) {108 auto parser = build_peg_parser([](common_peg_parser_builder & p) {109 return p.literal("hello") + p.optional(p.literal(" world"));110 });111 112 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {113 parser.build_grammar(builder);114 });115 116 assert_gbnf_equal(t, R"""(117 root ::= "hello" " world"?118 space ::= | " " | "\n"{1,2} [ \t]{0,20}119 )""", gbnf);120 });121 122 t.test("until grammar", [](testing &t) {123 auto parser = build_peg_parser([](common_peg_parser_builder & p) {124 return p.until("</tag>");125 });126 127 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {128 parser.build_grammar(builder);129 });130 131 assert_gbnf_equal(t, R"""(132 root ::= until-0133 space ::= | " " | "\n"{1,2} [ \t]{0,20}134 until-0 ::= | [<] until-0-01 | [^<] until-0135 until-0-01 ::= | [<] until-0-01 | [/] until-0-02 | [^/<] until-0136 until-0-02 ::= | [<] until-0-01 | [t] until-0-03 | [^<t] until-0137 until-0-03 ::= | [<] until-0-01 | [a] until-0-04 | [^<a] until-0138 until-0-04 ::= | [<] until-0-01 | [g] until-0-05 | [^<g] until-0139 until-0-05 ::= | [<] until-0-01 | [^<>] until-0140 )""", gbnf);141 });142 143 t.test("until grammar overlapping delimiter", [](testing &t) {144 auto parser = build_peg_parser([](common_peg_parser_builder & p) {145 return p.until("\n</parameter>\n");146 });147 148 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {149 parser.build_grammar(builder);150 });151 152 assert_gbnf_equal(t, R"""(153 root ::= until-0154 space ::= | " " | "\n"{1,2} [ \t]{0,20}155 until-0 ::= | [\n] until-0-01 | [^\n] until-0156 until-0-01 ::= | [\n] until-0-01 | [<] until-0-02 | [^\n<] until-0157 until-0-02 ::= | [\n] until-0-01 | [/] until-0-03 | [^\n/] until-0158 until-0-03 ::= | [\n] until-0-01 | [p] until-0-04 | [^\np] until-0159 until-0-04 ::= | [\n] until-0-01 | [a] until-0-05 | [^\na] until-0160 until-0-05 ::= | [\n] until-0-01 | [r] until-0-06 | [^\nr] until-0161 until-0-06 ::= | [\n] until-0-01 | [a] until-0-07 | [^\na] until-0162 until-0-07 ::= | [\n] until-0-01 | [m] until-0-08 | [^\nm] until-0163 until-0-08 ::= | [\n] until-0-01 | [e] until-0-09 | [^\ne] until-0164 until-0-09 ::= | [\n] until-0-01 | [t] until-0-10 | [^\nt] until-0165 until-0-10 ::= | [\n] until-0-01 | [e] until-0-11 | [^\ne] until-0166 until-0-11 ::= | [\n] until-0-01 | [r] until-0-12 | [^\nr] until-0167 until-0-12 ::= | [\n] until-0-01 | [>] until-0-13 | [^\n>] until-0168 until-0-13 ::= | [^\n] until-0169 )""", gbnf);170 });171 172 // DeepSeek-V3.2 tag prefix. The DSML token (｜DSML｜) embeds U+FF5C,173 // so the delimiter mixes ASCII and multi-byte codepoints.174 t.test("until grammar unicode delimiter", [](testing &t) {175 auto parser = build_peg_parser([](common_peg_parser_builder & p) {176 return p.until("<｜DSML｜");177 });178 179 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {180 parser.build_grammar(builder);181 });182 183 assert_gbnf_equal(t, R"""(184 root ::= until-0185 space ::= | " " | "\n"{1,2} [ \t]{0,20}186 until-0 ::= | [<] until-0-01 | [^<] until-0187 until-0-01 ::= | [<] until-0-01 | [\uFF5C] until-0-02 | [^<\uFF5C] until-0188 until-0-02 ::= | [<] until-0-01 | [D] until-0-03 | [^<D] until-0189 until-0-03 ::= | [<] until-0-01 | [S] until-0-04 | [^<S] until-0190 until-0-04 ::= | [<] until-0-01 | [M] until-0-05 | [^<M] until-0191 until-0-05 ::= | [<] until-0-01 | [L] until-0-06 | [^<L] until-0192 until-0-06 ::= | [<] until-0-01 | [^<\uFF5C] until-0193 )""", gbnf);194 });195 196 t.test("until grammar multiple delimiters", [](testing &t) {197 auto parser = build_peg_parser([](common_peg_parser_builder & p) {198 return p.until_one_of({"ab", "cd", "ef"});199 });200 201 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {202 parser.build_grammar(builder);203 });204 205 assert_gbnf_equal(t, R"""(206 root ::= until-0207 space ::= | " " | "\n"{1,2} [ \t]{0,20}208 until-0 ::= | [a] until-0-01 | [c] until-0-03 | [e] until-0-05 | [^ace] until-0209 until-0-01 ::= | [a] until-0-01 | [c] until-0-03 | [e] until-0-05 | [^abce] until-0210 until-0-03 ::= | [a] until-0-01 | [c] until-0-03 | [e] until-0-05 | [^acde] until-0211 until-0-05 ::= | [a] until-0-01 | [c] until-0-03 | [e] until-0-05 | [^acef] until-0212 )""", gbnf);213 });214 215 t.test("ac grammar", [](testing &t) {216 auto parser = build_peg_parser([](common_peg_parser_builder & p) {217 return p.ac(p.until("</tag>") + p.literal("</tag>"), "</tag>");218 });219 220 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {221 parser.build_grammar(builder);222 });223 224 assert_gbnf_equal(t, R"""(225 ac-3 ::= [<] ac-3-01 | [^<] ac-3226 ac-3-01 ::= [<] ac-3-01 | [/] ac-3-02 | [^/<] ac-3227 ac-3-02 ::= [<] ac-3-01 | [t] ac-3-03 | [^<t] ac-3228 ac-3-03 ::= [<] ac-3-01 | [a] ac-3-04 | [^<a] ac-3229 ac-3-04 ::= [<] ac-3-01 | [g] ac-3-05 | [^<g] ac-3230 ac-3-05 ::= [>] | [<] ac-3-01 | [^<>] ac-3231 root ::= ac-3232 space ::= | " " | "\n"{1,2} [ \t]{0,20}233 )""", gbnf);234 });235 236 t.test("ac grammar terminates at first delimiter", [](testing &t) {237 auto parser = build_peg_parser([](common_peg_parser_builder & p) {238 return p.ac(p.until("\n</parameter>\n") + p.literal("\n</parameter>\n"), "\n</parameter>\n");239 });240 241 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {242 parser.build_grammar(builder);243 });244 245 assert_gbnf_equal(t, R"""(246 ac-3 ::= [\n] ac-3-01 | [^\n] ac-3247 ac-3-01 ::= [\n] ac-3-01 | [<] ac-3-02 | [^\n<] ac-3248 ac-3-02 ::= [\n] ac-3-01 | [/] ac-3-03 | [^\n/] ac-3249 ac-3-03 ::= [\n] ac-3-01 | [p] ac-3-04 | [^\np] ac-3250 ac-3-04 ::= [\n] ac-3-01 | [a] ac-3-05 | [^\na] ac-3251 ac-3-05 ::= [\n] ac-3-01 | [r] ac-3-06 | [^\nr] ac-3252 ac-3-06 ::= [\n] ac-3-01 | [a] ac-3-07 | [^\na] ac-3253 ac-3-07 ::= [\n] ac-3-01 | [m] ac-3-08 | [^\nm] ac-3254 ac-3-08 ::= [\n] ac-3-01 | [e] ac-3-09 | [^\ne] ac-3255 ac-3-09 ::= [\n] ac-3-01 | [t] ac-3-10 | [^\nt] ac-3256 ac-3-10 ::= [\n] ac-3-01 | [e] ac-3-11 | [^\ne] ac-3257 ac-3-11 ::= [\n] ac-3-01 | [r] ac-3-12 | [^\nr] ac-3258 ac-3-12 ::= [\n] ac-3-01 | [>] ac-3-13 | [^\n>] ac-3259 ac-3-13 ::= [\n] | [^\n] ac-3260 root ::= ac-3261 space ::= | " " | "\n"{1,2} [ \t]{0,20}262 )""", gbnf);263 });264 265 t.test("ac grammar multiple delimiters", [](testing &t) {266 auto parser = build_peg_parser([](common_peg_parser_builder & p) {267 return p.ac(p.eps(), std::vector<std::string>{"ab", "cd", "ef"});268 });269 270 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {271 parser.build_grammar(builder);272 });273 274 assert_gbnf_equal(t, R"""(275 ac-1 ::= [a] ac-1-01 | [c] ac-1-03 | [e] ac-1-05 | [^ace] ac-1276 ac-1-01 ::= [b] | [a] ac-1-01 | [c] ac-1-03 | [e] ac-1-05 | [^abce] ac-1277 ac-1-03 ::= [d] | [a] ac-1-01 | [c] ac-1-03 | [e] ac-1-05 | [^acde] ac-1278 ac-1-05 ::= [f] | [a] ac-1-01 | [c] ac-1-03 | [e] ac-1-05 | [^acef] ac-1279 root ::= ac-1280 space ::= | " " | "\n"{1,2} [ \t]{0,20}281 )""", gbnf);282 });283 284 t.test("complex expressions with parentheses", [](testing &t) {285 auto parser = build_peg_parser([](common_peg_parser_builder & p) {286 return p.one_or_more(p.literal("a") | p.literal("b"));287 });288 289 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {290 parser.build_grammar(builder);291 });292 293 assert_gbnf_equal(t, R"""(294 root ::= ("a" | "b")+295 space ::= | " " | "\n"{1,2} [ \t]{0,20}296 )""", gbnf);297 });298 299 t.test("rule references", [](testing &t) {300 auto parser = build_peg_parser([](common_peg_parser_builder & p) {301 auto digit = p.rule("digit", p.chars("[0-9]", 1, 1));302 return p.one_or_more(digit);303 });304 305 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {306 parser.build_grammar(builder);307 });308 309 assert_gbnf_equal(t, R"""(310 digit ::= [0-9]311 root ::= digit+312 space ::= | " " | "\n"{1,2} [ \t]{0,20}313 )""", gbnf);314 });315 316 t.test("escaping in literals", [](testing &t) {317 auto parser = build_peg_parser([](common_peg_parser_builder & p) {318 return p.literal("hello\nworld\n!");319 });320 321 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {322 parser.build_grammar(builder);323 });324 325 assert_gbnf_equal(t, R"""(326 root ::= "hello\nworld\n!"327 space ::= | " " | "\n"{1,2} [ \t]{0,20}328 )""", gbnf);329 });330 331 t.test("operator<< (whitespace insertion)", [](testing &t) {332 auto parser = build_peg_parser([](common_peg_parser_builder & p) {333 return p.literal("hello") << p.literal("world");334 });335 336 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {337 parser.build_grammar(builder);338 });339 340 assert_gbnf_equal(t, R"""(341 root ::= "hello" space "world"342 space ::= | " " | "\n"{1,2} [ \t]{0,20}343 )""", gbnf);344 });345 346 t.test("emit only reachable rules", [](testing &t) {347 auto parser = build_peg_parser([](common_peg_parser_builder & p) {348 p.rule("orphan", p.literal("orphan"));349 return p.literal("hello") + p.rule("child", p.literal(" world"));350 });351 352 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {353 parser.build_grammar(builder);354 });355 356 assert_gbnf_equal(t, R"""(357 child ::= " world"358 root ::= "hello" child359 space ::= | " " | "\n"{1,2} [ \t]{0,20}360 )""", gbnf);361 });362 363 t.test("tagged choice inside sequence gets parenthesized", [](testing &t) {364 auto parser = build_peg_parser([](common_peg_parser_builder & p) {365 return p.literal("a") + p.tag("t", p.literal("b") | p.literal("c"));366 });367 368 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {369 parser.build_grammar(builder);370 });371 372 assert_gbnf_equal(t, R"""(373 root ::= "a" ("b" | "c")374 space ::= | " " | "\n"{1,2} [ \t]{0,20}375 )""", gbnf);376 });377 378 t.test("tagged sequence inside choice gets parenthesized", [](testing &t) {379 auto parser = build_peg_parser([](common_peg_parser_builder & p) {380 return p.tag("t", p.literal("a") + p.literal("b")) | p.literal("c");381 });382 383 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {384 parser.build_grammar(builder);385 });386 387 assert_gbnf_equal(t, R"""(388 root ::= "a" "b" | "c"389 space ::= | " " | "\n"{1,2} [ \t]{0,20}390 )""", gbnf);391 });392 393 t.test("atomic choice inside repetition gets parenthesized", [](testing &t) {394 auto parser = build_peg_parser([](common_peg_parser_builder & p) {395 return p.one_or_more(p.atomic(p.literal("a") | p.literal("b")));396 });397 398 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {399 parser.build_grammar(builder);400 });401 402 assert_gbnf_equal(t, R"""(403 root ::= ("a" | "b")+404 space ::= | " " | "\n"{1,2} [ \t]{0,20}405 )""", gbnf);406 });407 408 t.test("silent parser emits nothing in gbnf", [](testing &t) {409 auto parser = build_peg_parser([](common_peg_parser_builder & p) {410 return p.literal("hello") + p.gbnf(p.literal("world"), "");411 });412 413 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {414 parser.build_grammar(builder);415 });416 417 assert_gbnf_equal(t, R"""(418 root ::= "hello"419 space ::= | " " | "\n"{1,2} [ \t]{0,20}420 )""", gbnf);421 });422 423 t.test("silent choice inside sequence emits nothing", [](testing &t) {424 auto parser = build_peg_parser([](common_peg_parser_builder & p) {425 return p.literal("a") + p.gbnf(p.literal("b") | p.literal("c"), "") + p.literal("d");426 });427 428 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {429 parser.build_grammar(builder);430 });431 432 assert_gbnf_equal(t, R"""(433 root ::= "a" "d"434 space ::= | " " | "\n"{1,2} [ \t]{0,20}435 )""", gbnf);436 });437 438 t.test("silent wrapped in tag emits nothing", [](testing &t) {439 auto parser = build_peg_parser([](common_peg_parser_builder & p) {440 return p.literal("a") + p.tag("t", p.gbnf(p.literal("b"), ""));441 });442 443 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {444 parser.build_grammar(builder);445 });446 447 assert_gbnf_equal(t, R"""(448 root ::= "a"449 space ::= | " " | "\n"{1,2} [ \t]{0,20}450 )""", gbnf);451 });452 453 t.test("gbnf parser emits custom grammar", [](testing &t) {454 auto parser = build_peg_parser([](common_peg_parser_builder & p) {455 return p.literal("a") + p.gbnf(p.literal("b"), "[a-z]+");456 });457 458 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {459 parser.build_grammar(builder);460 });461 462 assert_gbnf_equal(t, R"""(463 root ::= "a" [a-z]+464 space ::= | " " | "\n"{1,2} [ \t]{0,20}465 )""", gbnf);466 });467 468 t.test("nested transparent wrappers get parenthesized", [](testing &t) {469 auto parser = build_peg_parser([](common_peg_parser_builder & p) {470 return p.literal("x") + p.tag("outer", p.atomic(p.literal("a") | p.literal("b")));471 });472 473 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {474 parser.build_grammar(builder);475 });476 477 assert_gbnf_equal(t, R"""(478 root ::= "x" ("a" | "b")479 space ::= | " " | "\n"{1,2} [ \t]{0,20}480 )""", gbnf);481 });482 483 t.test("emit only trigger rules (and references)", [](testing &t) {484 auto parser = build_peg_parser([](common_peg_parser_builder & p) {485 auto rule1 = p.rule("rule-1", p.literal("a") + p.ref("rule-2"));486 p.rule("rule-2", p.literal("b") + p.ref("rule-3"), true);487 p.rule("rule-3", p.literal("c") + p.ref("rule-4"));488 p.rule("rule-4", p.literal("d"), true);489 return rule1;490 });491 492 auto gbnf = build_grammar([&](const common_grammar_builder & builder) {493 parser.build_grammar(builder);494 });495 496 assert_gbnf_equal(t, R"""(497 root ::= rule-1498 rule-1 ::= "a" rule-2499 rule-2 ::= "b" rule-3500 rule-3 ::= "c" rule-4501 rule-4 ::= "d"502 space ::= | " " | "\n"{1,2} [ \t]{0,20}503 )""", gbnf);504 505 auto gbnf_lazy = build_grammar([&](const common_grammar_builder & builder) {506 parser.build_grammar(builder, true);507 });508 509 assert_gbnf_equal(t, R"""(510 root ::= rule-2 | rule-4511 rule-2 ::= "b" rule-3512 rule-3 ::= "c" rule-4513 rule-4 ::= "d"514 space ::= | " " | "\n"{1,2} [ \t]{0,20}515 )""", gbnf_lazy);516 });517}518