hey! this is a static git repo viewer. commit diffs, file history, older commits and other revisions won't load without javascript.

you are still able to view source files on branch/tag tips, but the experience is degraded.

char-fork/llama.cpp

git clone https://git.t4t.associates/char-fork/llama.cpp

Aldehir Rojascommon : implement common_schema internal representation for JSON schemas (#28736)acecd56032026-09-12

1#include "chat-peg-parser.h"
2#include "chat.h"
3#include "common.h"
4#include "json-schema-to-grammar.h"
5#include "peg-parser.h"
6#include "testing.h"
7#include "peg-parser/simple-tokenize.h"
8
9#include <iostream>
10#include <numeric>
11#include <regex>
12#include <string>
13
14#include "json.h"
15
16using json = common_json;
17
18static json create_tools();
19static void test_example_native(testing & t);
20static void test_example_qwen3_coder(testing & t);
21static void test_example_qwen3_non_coder(testing & t);
22static void test_command7_parser_compare(testing & t);
23static void test_prefix_tool_names(testing & t);
24static void test_tagged_peg_parser(testing & t);
25static void test_permute(testing & t);
26
27int main(int argc, char * argv[]) {
28    testing t(std::cout);
29    if (argc >= 2) {
30        t.set_filter(argv[1]);
31    }
32
33    const char * verbose = getenv("LLAMA_TEST_VERBOSE");
34    if (verbose) {
35        t.verbose = std::string(verbose) == "1";
36    }
37
38    t.test("native", test_example_native);
39    t.test("qwen3 coder", test_example_qwen3_coder);
40    t.test("qwen3 non-coder", test_example_qwen3_non_coder);
41    t.test("comparison", test_command7_parser_compare);
42    t.test("prefix tool names", test_prefix_tool_names);
43    t.test("tagged peg parser", test_tagged_peg_parser);
44    t.test("permute", test_permute);
45
46    return t.summary();
47}
48
49static json create_tools() {
50    json tools = json::array();
51
52    json tool_weather = {
53        { "type",     "function" },
54        { "function",
55         {
56              { "name", "get_current_weather" },
57              { "description", "Get the current weather in a given location" },
58              { "parameters",
59                {
60                    { "type", "object" },
61                    { "properties",
62                      { { "location",
63                          { { "type", "string" }, { "description", "The city and state, e.g. San Francisco, CA" } } },
64                        { "unit",
65                          { { "type", "string" },
66                            { "enum", json::array({ "celsius", "fahrenheit" }) },
67                            { "description",
68                              "The temperature unit to use. Infer this from the users location." } } } } },
69                    { "required", json::array({ "location", "unit" }) },
70                } },
71          }                      }
72    };
73    tools.push_back(tool_weather);
74
75    json tool_forecast = {
76        { "type",     "function" },
77        { "function",
78         {
79              { "name", "get_forecast" },
80              { "description", "Get the weather forecast for a given location" },
81              { "parameters",
82                {
83                    { "type", "object" },
84                    { "properties",
85                      { { "location",
86                          { { "type", "string" }, { "description", "The city and state, e.g. San Francisco, CA" } } },
87                        { "unit",
88                          { { "type", "string" },
89                            { "enum", json::array({ "celsius", "fahrenheit" }) },
90                            { "description", "The temperature unit to use. Infer this from the users location." } } },
91                        { "days",
92                          { { "type", "integer" },
93                            { "description", "Number of days to forecast (1-10)" },
94                            { "minimum", 1 },
95                            { "maximum", 10 } } } } },
96                    { "required", json::array({ "location", "unit" }) },
97                } },
98          }                      }
99    };
100    tools.push_back(tool_forecast);
101
102    json tool_search = {
103        { "type",     "function" },
104        { "function",
105         { { "name", "search_knowledge_base" },
106            { "description", "Search the internal technical documentation knowledge base." },
107            { "parameters",
108              { { "type", "object" },
109                { "properties",
110                  { { "query", { { "type", "string" }, { "description", "The search query string." } } },
111                    { "max_results",
112                      { { "type", "integer" },
113                        { "description", "The maximum number of results to return." },
114                        { "default", 5 } } },
115                    { "category",
116                      { { "type", "string" },
117                        { "enum", json::array({ "api", "troubleshooting", "billing", "general" }) },
118                        { "description", "Filter search by specific category." } } } } },
119                { "required", json::array({ "query", "category" }) },
120                { "additionalProperties", false } } },
121            { "strict", true } } }
122    };
123    tools.push_back(tool_search);
124
125    return tools;
126}
127
128struct tool_argument {
129    std::string name;
130    std::string type;
131    bool        is_required;
132    json        schema;
133};
134
135struct tool_definition {
136    std::string                name;
137    std::vector<tool_argument> arguments;
138    json                       schema;
139};
140
141// Test fictitious model output that emits arguments as JSON.
142static void test_example_native(testing & t) {
143    struct test_case {
144        // Parameters
145        std::string             name;
146        json                    tools;
147        common_chat_tool_choice tool_choice;
148        common_reasoning_format reasoning_format;
149        json                    json_schema;
150        bool                    parallel_tool_calls;
151        std::string             generation_prompt;
152        std::string             input;
153
154        // Expect
155        std::string                        expect_reasoning;
156        std::string                        expect_content;
157        std::vector<common_chat_tool_call> expect_tool_calls;
158    };
159
160    auto build_parser = [](const test_case & tc) {
161        return build_chat_peg_parser([&](common_chat_peg_builder & p) {
162            auto reasoning_in_content = (tc.reasoning_format == COMMON_REASONING_FORMAT_NONE);
163            // Always use optional TAG_BASED pattern; generation_prompt is prepended to input
164            auto reasoning = p.optional("<think>" + p.reasoning(p.until("</think>")) + "</think>" + p.space());
165
166            // tool calling parser
167            if (tc.tools.is_array() && !tc.tools.empty()) {
168                auto tool_call =
169                    p.standard_json_tools("<tool_call>[", "]</tool_call>", tc.tools, tc.parallel_tool_calls,
170                                          tc.tool_choice == COMMON_CHAT_TOOL_CHOICE_REQUIRED);
171
172                return p.sequence({ (reasoning_in_content ? p.eps() : reasoning), p.content(p.until("<tool_call>")),
173                                    p.optional(p.space() + tool_call), p.space(), p.end() });
174            }
175
176            // response_format parser
177            if (tc.json_schema.is_object() && !tc.json_schema.empty()) {
178                return p.sequence({ (reasoning_in_content ? p.eps() : reasoning),
179                                    p.content(p.schema(p.json(), "response-output", tc.json_schema)), p.space(),
180                                    p.end() });
181            }
182
183            // Content-only parser
184            return p.sequence({ (reasoning_in_content ? p.eps() : reasoning), p.content(p.rest()), p.end() });
185        });
186    };
187
188    std::vector<test_case> test_cases = std::vector<test_case>{
189        {
190         /* .name =                 */ "content with reasoning (no generation_prompt)",
191         /* .tools =                */ {},
192         /* .tool_choice =          */ COMMON_CHAT_TOOL_CHOICE_NONE,
193         /* .reasoning_format =     */ COMMON_REASONING_FORMAT_AUTO,
194         /* .json_schema =          */ {},
195         /* .parallel_tool_calls =  */ false,
196         /* .generation_prompt =    */ "",
197         /* .input =                */ ("<think>The user said hello, I must say hello back</think>\nHello"),
198         /* .expect_reasoning =     */ "The user said hello, I must say hello back",
199         /* .expect_content =       */ "Hello",
200         /* .expect_tool_calls =    */ {},
201         },
202        {
203         /* .name =                 */ "content without reasoning (no generation_prompt)",
204         /* .tools =                */ {},
205         /* .tool_choice =          */ COMMON_CHAT_TOOL_CHOICE_NONE,
206         /* .reasoning_format =     */ COMMON_REASONING_FORMAT_AUTO,
207         /* .json_schema =          */ {},
208         /* .parallel_tool_calls =  */ false,
209         /* .generation_prompt =    */ "",
210         /* .input =                */ ("Hello"),
211         /* .expect_reasoning =     */ "",
212         /* .expect_content =       */ "Hello",
213         /* .expect_tool_calls =    */ {},
214         },
215        {
216         /* .name =                 */ "content with reasoning_format = none (tags appear in content)",
217         /* .tools =                */ {},
218         /* .tool_choice =          */ COMMON_CHAT_TOOL_CHOICE_NONE,
219         /* .reasoning_format =     */ COMMON_REASONING_FORMAT_NONE,
220         /* .json_schema =          */ {},
221         /* .parallel_tool_calls =  */ false,
222         /* .generation_prompt =    */ "",
223         /* .input =                */ ("<think>The user said hello, I must say hello back</think>\nHello"),
224         /* .expect_reasoning =     */ "",
225         /* .expect_content =       */ "<think>The user said hello, I must say hello back</think>\nHello",
226         /* .expect_tool_calls =    */ {},
227         },
228        {
229         /* .name =                 */ "content with reasoning generation_prompt",
230         /* .tools =                */ {},
231         /* .tool_choice =          */ COMMON_CHAT_TOOL_CHOICE_NONE,
232         /* .reasoning_format =     */ COMMON_REASONING_FORMAT_AUTO,
233         /* .json_schema =          */ {},
234         /* .parallel_tool_calls =  */ false,
235         /* .generation_prompt =    */ "<think>",
236         /* .input =                */ ("The user said hello, I must say hello back</think>\nHello"),
237         /* .expect_reasoning =     */ "The user said hello, I must say hello back",
238         /* .expect_content =       */ "Hello",
239         /* .expect_tool_calls =    */ {},
240         },
241        {
242         /* .name =                 */ "content with reasoning generation_prompt and reasoning_format = none",
243         /* .tools =                */ {},
244         /* .tool_choice =          */ COMMON_CHAT_TOOL_CHOICE_NONE,
245         /* .reasoning_format =     */ COMMON_REASONING_FORMAT_NONE,
246         /* .json_schema =          */ {},
247         /* .parallel_tool_calls =  */ false,
248         /* .generation_prompt =    */ "",
249         /* .input =                */ ("The user said hello, I must say hello back</think>\nHello"),
250         /* .expect_reasoning =     */ "",
251         /* .expect_content =       */ "The user said hello, I must say hello back</think>\nHello",
252         /* .expect_tool_calls =    */ {},
253         },
254        {
255         /* .name =                 */ "content with closed reasoning generation_prompt (empty reasoning discarded)",
256         /* .tools =                */ {},
257         /* .tool_choice =          */ COMMON_CHAT_TOOL_CHOICE_NONE,
258         /* .reasoning_format =     */ COMMON_REASONING_FORMAT_AUTO,
259         /* .json_schema =          */ {},
260         /* .parallel_tool_calls =  */ false,
261         /* .generation_prompt =    */ "<think></think>",
262         /* .input =                */ ("Hello"),
263         /* .expect_reasoning =     */ "",
264         /* .expect_content =       */ "Hello",
265         /* .expect_tool_calls =    */ {},
266         },
267        {
268         /* .name =                 */ "tools with reasoning generation_prompt",
269         /* .tools =                */ create_tools(),
270         /* .tool_choice =          */ COMMON_CHAT_TOOL_CHOICE_AUTO,
271         /* .reasoning_format =     */ COMMON_REASONING_FORMAT_AUTO,
272         /* .json_schema =          */ {},
273         /* .parallel_tool_calls =  */ false,
274         /* .generation_prompt =    */ "<think>",
275         /* .input =                */
276            ("I must get the weather in New York</think>\n"
277             "<tool_call>["
278             R"({"name": "get_current_weather", "arguments": {"location": "New York City, NY", "unit": "fahrenheit"}})"
279             "]</tool_call>"),
280         /* .expect_reasoning =     */ "I must get the weather in New York",
281         /* .expect_content =       */ "",
282         /* .expect_tool_calls =    */
283            { {
284                /* .name =      */ "get_current_weather",
285                /* .arguments = */ R"({"location": "New York City, NY", "unit": "fahrenheit"})",
286                /* .id =        */ "",
287            } },
288         },
289        {
290         /* .name =                 */ "parallel tools with reasoning generation_prompt",
291         /* .tools =                */ create_tools(),
292         /* .tool_choice =          */ COMMON_CHAT_TOOL_CHOICE_AUTO,
293         /* .reasoning_format =     */ COMMON_REASONING_FORMAT_AUTO,
294         /* .json_schema =          */ {},
295         /* .parallel_tool_calls =  */ true,
296         /* .generation_prompt =    */ "<think>",
297         /* .input =                */
298            ("I must get the weather in New York and San Francisco and a 3 day forecast of each.</think>\nLet me "
299             "search that for you."
300             "<tool_call>["
301             R"({"name": "get_current_weather", "arguments": {"location": "New York City, NY", "unit": "fahrenheit"}})"
302             ", "
303             R"({"name": "get_current_weather", "arguments": {"location": "San Francisco, CA", "unit": "fahrenheit"}})"
304             ", "
305             R"({"name": "get_forecast", "arguments": {"location": "New York City, NY", "unit": "fahrenheit", "days": 3}})"
306             ", "
307             R"({"name": "get_forecast", "arguments": {"location": "San Francisco, CA", "unit": "fahrenheit", "days": 3}})"
308             "]</tool_call>"),
309         /* .expect_reasoning =     */
310            "I must get the weather in New York and San Francisco and a 3 day forecast of each.",                                                                     /* .expect_content =       */ "Let me search that for you.",
311         /* .expect_tool_calls =    */
312            { {
313                  /* .name =      */ "get_current_weather",
314                  /* .arguments = */ R"({"location": "New York City, NY", "unit": "fahrenheit"})",
315                  /* .id =        */ "",
316              },
317              {
318                  /* .name =      */ "get_current_weather",
319                  /* .arguments = */ R"({"location": "San Francisco, CA", "unit": "fahrenheit"})",
320                  /* .id =        */ "",
321              },
322              {
323                  /* .name =      */ "get_forecast",
324                  /* .arguments = */ R"({"location": "New York City, NY", "unit": "fahrenheit", "days": 3})",
325                  /* .id =        */ "",
326              },
327              {
328                  /* .name =      */ "get_forecast",
329                  /* .arguments = */ R"({"location": "San Francisco, CA", "unit": "fahrenheit", "days": 3})",
330                  /* .id =        */ "",
331              } },
332         },
333        {
334         /* .name =                 */ "response_format with reasoning generation_prompt",
335         /* .tools =                */ {},
336         /* .tool_choice =          */ COMMON_CHAT_TOOL_CHOICE_NONE,
337         /* .reasoning_format =     */ COMMON_REASONING_FORMAT_AUTO,
338         /* .json_schema =          */
339            { { "type", "object" },
340              { "properties",
341                { { "invoice_number", { { "type", "string" } } },
342                  { "amount", { { "type", "number" } } },
343                  { "due_date", { { "type", "string" } } } } },
344              { "required", json::array({ "invoice_number", "amount", "due_date" }) } },
345         /* .parallel_tool_calls =  */ false,
346         /* .generation_prompt =    */ "<think>",
347         /* .input =                */
348            ("I must produce the invoice in the requested format</think>\n"
349             R"({"invoice_number": "INV-2025-001", "amount": 1250.50, "due_date": "2025-12-31"})"),
350         /* .expect_reasoning =     */ "I must produce the invoice in the requested format",
351         /* .expect_content =       */
352            R"({"invoice_number": "INV-2025-001", "amount": 1250.50, "due_date": "2025-12-31"})", /* .expect_tool_calls =    */ {},
353         },
354    };
355
356    for (const auto & tc : test_cases) {
357        t.test(tc.name, [&](testing & t) {
358            auto parser  = build_parser(tc);
359            auto lazy    = !tc.tools.empty() && tc.tool_choice != COMMON_CHAT_TOOL_CHOICE_REQUIRED;
360            auto grammar = build_grammar([&](const common_grammar_builder & builder) {
361                parser.build_grammar(builder, lazy);
362            });
363
364            t.log("Grammar:");
365            for (const auto & line : string_split(grammar, "\n")) {
366                t.log(line);
367            }
368
369            std::string              effective_input = tc.generation_prompt + tc.input;
370            common_peg_parse_context ctx(effective_input);
371            auto                     result = parser.parse(ctx);
372
373            t.assert_true("success", result.success());
374
375            common_chat_msg msg;
376            auto            mapper = common_chat_peg_mapper(msg);
377            mapper.from_ast(ctx.ast, result);
378
379            t.assert_equal("content equal", tc.expect_content, msg.content);
380            t.assert_equal("reasoning equal", tc.expect_reasoning, msg.reasoning_content);
381            t.assert_equal("number of tool calls", tc.expect_tool_calls.size(), msg.tool_calls.size());
382            for (auto i = 0u; i < std::min(tc.expect_tool_calls.size(), msg.tool_calls.size()); i++) {
383                t.assert_equal("tool name", tc.expect_tool_calls[i].name, msg.tool_calls[i].name);
384                t.assert_equal("tool args", tc.expect_tool_calls[i].arguments, msg.tool_calls[i].arguments);
385            }
386        });
387    }
388}
389
390static void test_example_qwen3_coder(testing & t) {
391    auto tools  = create_tools();
392    auto parser = build_chat_peg_parser([&](common_chat_peg_builder & p) {
393        auto content = p.rule("content", p.content(p.until("<tool_call>")));
394
395        std::vector<common_peg_parser> tool_parsers;
396        for (const auto & def : tools) {
397            auto        function   = def.at("function");
398            std::string name       = function.at("name");
399            auto        parameters = function.at("parameters");
400            auto        properties = parameters.at("properties");
401
402            std::set<std::string> required_properties;
403            if (function.contains("required")) {
404                required_properties = function.at("required").get<std::set<std::string>>();
405            }
406
407            std::vector<common_peg_parser> arg_parsers;
408            for (const auto & [param_name, param_schema] : properties.items()) {
409                bool is_required = required_properties.find(param_name) != required_properties.end();
410                auto type        = param_schema.value("type", "object");
411
412                auto arg = p.tool_arg(
413                    p.sequence({ p.tool_arg_open("<parameter=" + p.tool_arg_name(p.literal(param_name)) + ">"),
414                                 (type == "string" ?
415                                      p.tool_arg_string_value(p.schema(
416                                          p.until_one_of({ "</parameter>\n<parameter=", "</parameter>\n</function>" }),
417                                          "tool-" + name + "-arg-" + param_name + "-schema", param_schema, true)) :
418                                      p.tool_arg_json_value(p.schema(
419                                          p.json(), "tool-" + name + "-arg-" + param_name + "-schema", param_schema))),
420                                 p.tool_arg_close("</parameter>\n" +
421                                                  p.peek(p.literal("<parameter=") | p.literal("</function>"))) }));
422
423                arg_parsers.push_back(is_required ? p.rule("tool-" + name + "-arg-" + param_name, arg) :
424                                                    p.optional(p.rule("tool-" + name + "-arg-" + param_name, arg)));
425            }
426
427            tool_parsers.push_back(p.rule("tool-" + name, p.tool_open("<function=" + p.tool_name(p.literal(name)) + ">")
428                                                              << p.sequence(arg_parsers)
429                                                              << p.tool_close(p.literal("</function>"))));
430        };
431
432        auto tool_call = p.trigger_rule("tool-call", "<tool_call>" << p.choice(tool_parsers) << "</tool_call>");
433
434        return content + p.zero_or_more(p.space() + tool_call) + p.end();
435    });
436
437    auto grammar = build_grammar([&](const common_grammar_builder & builder) {
438        parser.build_grammar(builder);
439    });
440
441    t.log("Grammar:");
442    for (const auto & line : string_split(grammar, "\n")) {
443        t.log(line);
444    }
445
446    t.test("incremental parsing", [&](testing & t) {
447        std::string input =
448            "Let me search the knowledge base for cat pictures."
449            "<tool_call>\n"
450            "<function=search_knowledge_base>\n"
451            "<parameter=query>cat pictures</parameter>\n"
452            "<parameter=category>general</parameter>\n"
453            "</function>\n"
454            "</tool_call>";
455
456        std::vector<std::string> tokens = simple_tokenize(input);
457
458        common_chat_msg prev;
459        for (auto it = tokens.begin(); it != tokens.end(); it++) {
460            std::string in = std::accumulate(tokens.begin(), it + 1, std::string());
461
462            common_peg_parse_context ctx(in, (it + 1 < tokens.end()) ? COMMON_PEG_PARSE_FLAG_LENIENT : COMMON_PEG_PARSE_FLAG_NONE);
463
464            auto result = parser.parse(ctx);
465            if (!t.assert_equal("not fail", false, result.fail())) {
466                t.log(in.substr(0, result.end) + "[failed->]" + in.substr(result.end));
467            }
468
469            common_chat_msg msg;
470            auto            mapper = common_chat_peg_mapper(msg);
471            mapper.from_ast(ctx.ast, result);
472
473            //t.log("Input: " + input);
474            t.log("===========================================");
475            t.log("Iteration " + std::to_string(in.size()));
476            t.log("Reasoning: " + msg.reasoning_content);
477            t.log("Content  : " + msg.content);
478            for (const auto & tc : msg.tool_calls) {
479                t.log("Tool name: " + tc.name);
480                t.log("Tool args: " + tc.arguments);
481            }
482
483            try {
484                // This shouldn't emit any runtime errors
485                auto diffs = common_chat_msg_diff::compute_diffs(prev, msg);
486            } catch (const std::exception & e) {
487                t.log(in.substr(0, result.end) + "[failed->]" + in.substr(result.end));
488                t.assert_true(std::string("failed with ") + e.what(), false);
489            }
490
491            prev = msg;
492        }
493    });
494}
495
496static void test_example_qwen3_non_coder(testing & t) {
497    auto tools  = create_tools();
498    auto parser = build_chat_peg_parser([&](common_chat_peg_builder & p) {
499        // tool calling parser using standard JSON format
500        auto tool_call = p.standard_json_tools("<tool_call>", "</tool_call>", tools, true, false);
501
502        return p.sequence({ p.content(p.until("<tool_call>")), p.optional(p.space() + tool_call), p.end() });
503    });
504
505    auto grammar = build_grammar([&](const common_grammar_builder & builder) {
506        parser.build_grammar(builder);
507    });
508
509    t.log("Grammar:");
510    for (const auto & line : string_split(grammar, "\n")) {
511        t.log(line);
512    }
513
514    t.test("tool call parsing", [&](testing & t) {
515        std::string input =
516            "I need to get the weather.\n"
517            "<tool_call>"
518            "{\"name\": \"get_current_weather\", \"arguments\": {\"location\": \"New York City, NY\", \"unit\": "
519            "\"fahrenheit\"}}"
520            "</tool_call>";
521
522        common_peg_parse_context ctx(input);
523        auto                     result = parser.parse(ctx);
524
525        t.assert_true("success", result.success());
526
527        common_chat_msg msg;
528        auto            mapper = common_chat_peg_mapper(msg);
529        mapper.from_ast(ctx.ast, result);
530
531        t.assert_equal("content", "I need to get the weather.\n", msg.content);
532        t.assert_equal("reasoning", "", msg.reasoning_content);
533        t.assert_equal("tool calls count", 1u, msg.tool_calls.size());
534        if (!msg.tool_calls.empty()) {
535            t.assert_equal("tool name", "get_current_weather", msg.tool_calls[0].name);
536            t.assert_equal("tool args", "{\"location\": \"New York City, NY\", \"unit\": \"fahrenheit\"}",
537                           msg.tool_calls[0].arguments);
538        }
539    });
540
541    t.test("incremental parsing", [&](testing & t) {
542        std::string input =
543            "I need to get the weather.\n"
544            "<tool_call>"
545            "{\"name\": \"get_current_weather\", \"arguments\": {\"location\": \"New York City, NY\", \"unit\": "
546            "\"fahrenheit\"}}"
547            "</tool_call>";
548
549        std::vector<std::string> tokens = simple_tokenize(input);
550
551        common_chat_msg prev;
552        for (auto it = tokens.begin(); it != tokens.end(); it++) {
553            std::string in = std::accumulate(tokens.begin(), it + 1, std::string());
554
555            common_peg_parse_context ctx(in, (it + 1 < tokens.end()) ? COMMON_PEG_PARSE_FLAG_LENIENT : COMMON_PEG_PARSE_FLAG_NONE);
556
557            auto result = parser.parse(ctx);
558            if (!t.assert_equal("not fail", false, result.fail())) {
559                t.log(in.substr(0, result.end) + "[failed->]" + in.substr(result.end));
560            }
561
562            common_chat_msg msg;
563            auto            mapper = common_chat_peg_mapper(msg);
564            mapper.from_ast(ctx.ast, result);
565
566            //t.log("Input: " + input);
567            t.log("===========================================");
568            t.log("Iteration " + std::to_string(in.size()));
569            t.log("Reasoning: " + msg.reasoning_content);
570            t.log("Content  : " + msg.content);
571            for (const auto & tc : msg.tool_calls) {
572                t.log("Tool name: " + tc.name);
573                t.log("Tool args: " + tc.arguments);
574            }
575
576            try {
577                // This shouldn't emit any runtime errors
578                auto diffs = common_chat_msg_diff::compute_diffs(prev, msg);
579            } catch (const std::exception & e) {
580                t.log(in.substr(0, result.end) + "[failed->]" + in.substr(result.end));
581                t.assert_true(std::string("failed with ") + e.what(), false);
582            }
583
584            prev = msg;
585        }
586    });
587}
588
589void test_command7_parser_compare(testing & t) {
590    auto parser = build_chat_peg_parser([](common_chat_peg_builder & p) {
591        auto thinking =
592            p.reasoning_block("<|START_THINKING|>" << p.reasoning(p.until("<|END_THINKING|>")) << "<|END_THINKING|>");
593
594        auto response = "<|START_RESPONSE|>" << p.content(p.until("<|END_RESPONSE|>")) << "<|END_RESPONSE|>";
595
596        auto tool_call_id = p.atomic("\"tool_call_id\"" << (":" << ("\"" + p.tool_id(p.string_content('"')) + "\"")));
597        auto tool_call_name =
598            p.atomic("\"tool_name\"" << (":" << ("\"" + p.tool_name(p.string_content('"')) + "\"")));
599        auto tool_call_args = "\"parameters\"" << (":" << p.tool_args(p.json()));
600
601        auto tool_call_fields = p.rule("tool-call-fields", tool_call_id | tool_call_name | tool_call_args);
602        auto tool_call =
603            p.rule("tool-call", p.tool(p.tool_open(p.literal("{"))
604                                       << tool_call_fields << p.zero_or_more(p.literal(",") << tool_call_fields)
605                                       << p.tool_close(p.literal("}"))));
606
607        auto tool_calls = p.rule(
608            "tool-calls", "<|START_ACTION|>" << ("[" << tool_call << p.zero_or_more(p.literal(",") << tool_call) << "]")
609                                             << "<|END_ACTION|>");
610
611        return p.optional(thinking) << (tool_calls | response) + p.end();
612    });
613
614    auto test_current = [&](const common_peg_arena & p, const std::string & input, bool is_partial,
615                            bool print_results) {
616        common_peg_parse_context ctx(input, is_partial ? COMMON_PEG_PARSE_FLAG_LENIENT : COMMON_PEG_PARSE_FLAG_NONE);
617        auto                     result = p.parse(ctx);
618
619        common_chat_msg msg;
620        auto            mapper = common_chat_peg_mapper(msg);
621        mapper.from_ast(ctx.ast, result);
622
623        if (print_results) {
624            std::cout << "== Parsed (new) ==\n";
625            std::cout << "=== Reasoning ===\n";
626            std::cout << msg.reasoning_content << "\n";
627            std::cout << "\n\n=== Content ===\n";
628            std::cout << msg.content << "\n";
629            std::cout << "\n\n=== Tool Calls ===\n";
630            for (const auto & tc : msg.tool_calls) {
631                std::cout << "id: " << tc.id << "\n";
632                std::cout << "name: " << tc.name << "\n";
633                std::cout << "args: " << tc.arguments << "\n";
634            }
635        }
636    };
637
638    std::string reasoning =
639        "To plan an effective trip to Japan that includes both historical sites and modern attractions within a "
640        "budget of $4000 for a two-week stay, we need to:\n\n"
641        "1. Identify key historical sites and modern attractions in Japan.\n"
642        "2. Find affordable accommodation options that provide a balance between comfort and cost.\n"
643        "3. Determine the best modes of transportation for getting around Japan.\n"
644        "4. Create a day-by-day itinerary that ensures the user gets to see a variety of attractions without "
645        "overspending.\n"
646        "5. Provide a detailed cost breakdown that includes accommodation, transportation, meals, and entry fees "
647        "to attractions.";
648
649    std::vector<std::tuple<std::string, std::string, common_json>> tool_calls = {
650        { "call_0", "plan_trip", common_json::parse(R"({
651            "destination": "Japan",
652            "duration": 14,
653            "budget": 4000,
654            "interests": ["historical sites", "modern attractions"],
655            "accommodation_preferences": "affordable",
656            "transportation_preferences": "efficient",
657            "meal_preferences": "local cuisine"
658        })") }
659    };
660
661    std::vector<std::string> tokens;
662
663    // Build tokens
664    if (!reasoning.empty()) {
665        auto tokenized = simple_tokenize(reasoning);
666        tokens.emplace_back("<|START_THINKING|>");
667        tokens.insert(tokens.end(), tokenized.begin(), tokenized.end());
668        tokens.emplace_back("<|END_THINKING|>");
669    }
670
671    if (!tool_calls.empty()) {
672        tokens.emplace_back("<|START_ACTION|>");
673
674        auto json = common_json::array();
675        for (const auto & tc : tool_calls) {
676            auto tc_json            = common_json::object();
677            tc_json["tool_call_id"] = std::get<0>(tc);
678            tc_json["tool_name"]    = std::get<1>(tc);
679            tc_json["parameters"]   = std::get<2>(tc);
680            json.push_back(tc_json);
681        }
682
683        auto tokenized = simple_tokenize(json.dump(-1));
684        tokens.insert(tokens.end(), tokenized.begin(), tokenized.end());
685
686        tokens.emplace_back("<|END_ACTION|>");
687    }
688
689    std::string input = std::accumulate(tokens.begin(), tokens.end(), std::string());
690
691    t.test("current_parse", [&](testing & /* t */) { test_current(parser, input, false, false); });
692    t.bench("current_parse_benchmark complete", [&]() { test_current(parser, input, false, false); }, 100);
693    t.bench(
694        "current_parse_benchmark incremental",
695        [&]() {
696            std::string in;
697            for (auto i = 0u; i < tokens.size(); i++) {
698                in += tokens[i];
699                test_current(parser, in, i + 1 < tokens.size(), false);
700            }
701        },
702        20);
703}
704
705// Test that tool names that are proper prefixes of other tool names don't cause
706// premature matching during incremental parsing.
707// For example, "special_function" should not match when parsing "special_function_with_opt".
708static void test_prefix_tool_names(testing & t) {
709    // Create tools where one name is a proper prefix of another
710    json tools = json::array();
711
712    json tool_short = {
713        { "type", "function" },
714        { "function",
715          {
716              { "name", "special_function" },
717              { "description", "A special function" },
718              { "parameters",
719                {
720                    { "type", "object" },
721                    { "properties",
722                      {
723                          { "arg1", { { "type", "integer" } } },
724                      } },
725                    { "required", json::array({ "arg1" }) },
726                } },
727          } }
728    };
729    tools.push_back(tool_short);
730
731    json tool_long = {
732        { "type", "function" },
733        { "function",
734          {
735              { "name", "special_function_with_opt" },
736              { "description", "A special function with optional params" },
737              { "parameters",
738                {
739                    { "type", "object" },
740                    { "properties",
741                      {
742                          { "arg1", { { "type", "integer" } } },
743                          { "arg2", { { "type", "integer" } } },
744                      } },
745                    { "required", json::array({ "arg1" }) },
746                } },
747          } }
748    };
749    tools.push_back(tool_long);
750
751    // Use standard_constructed_tools which had the prefix matching bug
752    std::map<std::string, std::string> markers = {
753        { "tool_call_start_marker", "<tool_call>" },
754        { "tool_call_end_marker", "</tool_call>" },
755        { "function_opener", "<function=" },
756        { "function_closer", "</function>" },
757        { "function_name_suffix", ">" },
758        { "parameter_key_prefix", "<param=" },
759        { "parameter_key_suffix", ">" },
760        { "parameter_closer", "</param>" },
761    };
762
763    auto parser = build_chat_peg_parser([&](common_chat_peg_builder & p) {
764        auto content   = p.rule("content", p.content(p.until("<tool_call>")));
765        auto tool_call = p.standard_constructed_tools(markers, tools, false, false);
766        return content + p.zero_or_more(p.space() + tool_call) + p.end();
767    });
768
769    // Test parsing the long tool name - this should NOT trigger the short tool name
770    t.test("parse long tool name", [&](testing & t) {
771        std::string input =
772            "Let me call the function."
773            "<tool_call>"
774            "<function=special_function_with_opt>"
775            "<param=arg1>42</param>"
776            "</function>"
777            "</tool_call>";
778
779        common_peg_parse_context ctx(input);
780        auto                     result = parser.parse(ctx);
781
782        t.assert_true("success", result.success());
783
784        common_chat_msg msg;
785        auto            mapper = common_chat_peg_mapper(msg);
786        mapper.from_ast(ctx.ast, result);
787
788        t.assert_equal("content", "Let me call the function.", msg.content);
789        t.assert_equal("tool calls count", 1u, msg.tool_calls.size());
790        if (!msg.tool_calls.empty()) {
791            t.assert_equal("tool name", "special_function_with_opt", msg.tool_calls[0].name);
792        }
793    });
794
795    // Test incremental parsing - the key test case
796    // This ensures that when incrementally parsing "special_function_with_opt",
797    // we don't prematurely emit "special_function" as a tool call
798    t.test("incremental parse long tool name", [&](testing & t) {
799        std::string input =
800            "Let me call the function."
801            "<tool_call>"
802            "<function=special_function_with_opt>"
803            "<param=arg1>42</param>"
804            "</function>"
805            "</tool_call>";
806
807        std::vector<std::string> tokens = simple_tokenize(input);
808
809        common_chat_msg prev;
810        for (auto it = tokens.begin(); it != tokens.end(); it++) {
811            std::string in = std::accumulate(tokens.begin(), it + 1, std::string());
812
813            common_peg_parse_context ctx(in, (it + 1 < tokens.end()) ? COMMON_PEG_PARSE_FLAG_LENIENT : COMMON_PEG_PARSE_FLAG_NONE);
814            auto                     result = parser.parse(ctx);
815
816            if (!t.assert_equal("not fail", false, result.fail())) {
817                t.log(in.substr(0, result.end) + "[failed->]" + in.substr(result.end));
818                return;
819            }
820
821            common_chat_msg msg;
822            auto            mapper = common_chat_peg_mapper(msg);
823            mapper.from_ast(ctx.ast, result);
824
825            // The critical check: during incremental parsing, we should never
826            // see "special_function" as the tool name when parsing "special_function_with_opt"
827            for (const auto & tc : msg.tool_calls) {
828                if (!t.assert_equal("tool name should not be short prefix", false,
829                                    tc.name == "special_function")) {
830                    t.log("Premature tool name match at input: " + in);
831                    return;
832                }
833            }
834
835            try {
836                auto diffs = common_chat_msg_diff::compute_diffs(prev, msg);
837            } catch (const std::exception & e) {
838                t.log(in.substr(0, result.end) + "[failed->]" + in.substr(result.end));
839                t.assert_true(std::string("diff failed with ") + e.what(), false);
840                return;
841            }
842
843            prev = msg;
844        }
845
846        // Final check: the complete parse should have the correct tool name
847        t.assert_equal("final tool calls count", 1u, prev.tool_calls.size());
848        if (!prev.tool_calls.empty()) {
849            t.assert_equal("final tool name", "special_function_with_opt", prev.tool_calls[0].name);
850        }
851    });
852
853    // Test parsing the short tool name still works
854    t.test("parse short tool name", [&](testing & t) {
855        std::string input =
856            "Let me call the function."
857            "<tool_call>"
858            "<function=special_function>"
859            "<param=arg1>42</param>"
860            "</function>"
861            "</tool_call>";
862
863        common_peg_parse_context ctx(input);
864        auto                     result = parser.parse(ctx);
865
866        t.assert_true("success", result.success());
867
868        common_chat_msg msg;
869        auto            mapper = common_chat_peg_mapper(msg);
870        mapper.from_ast(ctx.ast, result);
871
872        t.assert_equal("content", "Let me call the function.", msg.content);
873        t.assert_equal("tool calls count", 1u, msg.tool_calls.size());
874        if (!msg.tool_calls.empty()) {
875            t.assert_equal("tool name", "special_function", msg.tool_calls[0].name);
876        }
877    });
878}
879
880static void test_tagged_peg_parser(testing & t) {
881    t.test("basic tag extraction", [&](testing & t) {
882        auto parser = build_tagged_peg_parser([](common_peg_parser_builder & p) {
883            return p.tag("greeting", p.until(" ")) + " " + p.tag("name", p.rest()) + p.end();
884        });
885
886        auto result = parser.parse_and_extract("Hello World");
887        t.assert_true("success", result.result.success());
888        t.assert_equal("greeting tag", "Hello", result.tags.at("greeting"));
889        t.assert_equal("name tag", "World", result.tags.at("name"));
890    });
891
892    t.test("duplicate tags overwrite", [&](testing & t) {
893        auto parser = build_tagged_peg_parser([](common_peg_parser_builder & p) {
894            return p.tag("item", p.until(",")) + "," + p.tag("item", p.rest()) + p.end();
895        });
896
897        auto result = parser.parse_and_extract("first,second");
898        t.assert_true("success", result.result.success());
899        t.assert_equal("item tag", "second", result.tags.at("item"));
900    });
901
902    t.test("no tags extracted", [&](testing & t) {
903        auto parser = build_tagged_peg_parser([](common_peg_parser_builder & p) {
904            return p.rest() + p.end();
905        });
906
907        auto result = parser.parse_and_extract("Hello");
908        t.assert_true("success", result.result.success());
909        t.assert_equal("empty tags", 0u, result.tags.size());
910    });
911
912    t.test("structured extraction", [&](testing & t) {
913        auto parser = build_tagged_peg_parser([](common_peg_parser_builder & p) {
914            auto header = p.tag("header", p.until("\n"));
915            auto body = p.tag("body", p.rest());
916            return header + "\n" + body + p.end();
917        });
918
919        auto result = parser.parse_and_extract("Title\nBody content here");
920        t.assert_true("success", result.result.success());
921        t.assert_equal("header", "Title", result.tags.at("header"));
922        t.assert_equal("body", "Body content here", result.tags.at("body"));
923    });
924
925    t.test("partial parse", [&](testing & t) {
926        auto parser = build_tagged_peg_parser([](common_peg_parser_builder & p) {
927            return p.tag("prefix", p.until(":")) + ":" + p.tag("value", p.rest()) + p.end();
928        });
929
930        auto result = parser.parse_and_extract("key:val", COMMON_PEG_PARSE_FLAG_LENIENT);
931        t.assert_true("not fail", !result.result.fail());
932        t.assert_equal("prefix tag", "key", result.tags.at("prefix"));
933        t.assert_equal("value tag", "val", result.tags.at("value"));
934    });
935
936    t.test("find in the middle", [&](testing & t) {
937        auto parser = build_tagged_peg_parser([](common_peg_parser_builder & p) {
938            return p.choice({ p.literal("{"), p.literal(":") }) + p.space() + p.literal("\"") + p.atomic(p.literal("fun_name"));
939        });
940
941        std::string tpl = "This is a very long jinja template string. We have tools. We will try to call them now: <tool_call>{ \"fun_name\" : { \"arg\" : 1 }</tool_call>";
942        auto result = parser.parse_anywhere_and_extract(tpl);
943        t.assert_true("success", result.result.success());
944    });
945
946    t.test("fail find in the middle", [&](testing & t) {
947        auto parser = build_tagged_peg_parser([](common_peg_parser_builder & p) {
948            return p.choice({ p.literal("{"), p.literal(":") }) + p.space() + p.literal("\"") + p.atomic(p.literal("fun_name"));
949        });
950
951        std::string tpl = "This is a very long jinja template string. We have tools. We will try to call them now: <tool_call><fun=fun_name><arg name=arg>1</arg></tool_call>";
952        auto result = parser.parse_anywhere_and_extract(tpl);
953        t.assert_true("failure", result.result.fail());
954    });
955
956    t.test("find function tag with name", [&](testing &t) {
957        std::string haystack = "\n<tool_call>\n<function=foofoo>\n<parameter=first>\nXXXX\n</parameter>\n<parameter=second>\nYYYY\n</parameter>\n</function>\n</tool_call>\n";
958        auto parser = build_tagged_peg_parser([](common_peg_parser_builder & p) {
959            std::string needle = "foofoo";
960            return p.tag("fun_marker", p.choice({
961            p.tag("fun_pre", p.literal("<") + p.until_one_of({ ">", needle })) + p.literal(needle) +
962                p.tag("fun_post", p.negate(p.space() + p.literal("<")) + p.until(">") + p.literal(">")) + p.space(),
963            p.tag("fun_pre", p.literal("[") + p.until_one_of({ "]", needle })) + p.literal(needle) +
964                p.tag("fun_post", p.negate(p.space() + p.literal("[") + p.until("]") + p.literal("]")) + p.space()) }));
965        });
966        auto result = parser.parse_anywhere_and_extract(haystack);
967        t.assert_true("success", result.result.success());
968        t.assert_equal("fun_pre should be '<function='", "<function=", result.tags["fun_pre"]);
969        t.assert_equal("fun_post should be '>'", ">", result.tags["fun_post"]);
970    });
971}
972
973static void test_permute(testing & t) {
974    auto accepts = [](const common_peg_arena & parser, const std::string & input) {
975        common_peg_parse_context ctx(input);
976        return parser.parse(ctx).success();
977    };
978
979    auto gbnf_of = [](const common_peg_arena & parser) {
980        return build_grammar([&](const common_grammar_builder & builder) { parser.build_grammar(builder); });
981    };
982
983    auto assert_gbnf_equal = [](testing & t, const std::string & expected, const std::string & actual) {
984        static const std::regex leading_ws_re = std::regex(R"((^|\n)\s+)");
985        t.assert_equal("gbnf are equal", std::regex_replace(expected, leading_ws_re, "$1"), actual);
986    };
987
988    auto count_rules = [](const std::string & gbnf, const std::string & prefix) {
989        size_t count = 0;
990        for (const auto & line : string_split<std::string>(gbnf, '\n')) {
991            if (line.rfind(prefix, 0) == 0) {
992                count++;
993            }
994        }
995        return count;
996    };
997
998    t.test("accepts every ordering", [&](testing & t) {
999        auto parser = build_chat_peg_parser([](common_chat_peg_builder & p) {
1000            return p.permute("abc", { p.literal("a"), p.literal("b"), p.literal("c") }) + p.end();
1001        });
1002
1003        for (const std::string input : { "abc", "acb", "bac", "bca", "cab", "cba" }) {
1004            t.assert_true("accepts " + input, accepts(parser, input));
1005        }
1006    });
1007
1008    t.test("single element", [&](testing & t) {
1009        auto parser = build_chat_peg_parser([](common_chat_peg_builder & p) {
1010            return p.permute("a", { p.literal("a") }) + p.end();
1011        });
1012
1013        t.assert_true("accepts a", accepts(parser, "a"));
1014        t.assert_true("rejects aa", !accepts(parser, "aa"));
1015    });
1016
1017    t.test("grammar left-factorizes shared tails", [&](testing & t) {
1018        auto parser = build_chat_peg_parser([](common_chat_peg_builder & p) {
1019            return p.permute("abc", { p.literal("a"), p.literal("b"), p.literal("c") }) + p.end();
1020        });
1021
1022        // Every rule is one remaining subset, keyed by bitmask: abc-3 is {a,b}, abc-7 is {a,b,c}.
1023        // Each subset is emitted once and shared by every branch that leads into it.
1024        assert_gbnf_equal(t, R"""(
1025            abc-1 ::= "a"
1026            abc-2 ::= "b"
1027            abc-3 ::= "a" abc-2 | "b" abc-1
1028            abc-4 ::= "c"
1029            abc-5 ::= "a" abc-4 | "c" abc-1
1030            abc-6 ::= "b" abc-4 | "c" abc-2
1031            abc-7 ::= "a" abc-6 | "b" abc-5 | "c" abc-3
1032            root ::= abc-7
1033            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1034        )""", gbnf_of(parser));
1035    });
1036
1037    t.test("grammar emits one rule per remaining subset", [&](testing & t) {
1038        auto parser = build_chat_peg_parser([](common_chat_peg_builder & p) {
1039            return p.permute("abcd", { p.literal("a"), p.literal("b"), p.literal("c"), p.literal("d") }) + p.end();
1040        });
1041
1042        // 2^4 - 1 non-empty subsets, one rule each - not the 4! = 24 orderings.
1043        t.assert_equal("permute rule count", 15u, count_rules(gbnf_of(parser), "abcd-"));
1044    });
1045
1046    t.test("grammar emits no rules for a single element", [&](testing & t) {
1047        auto parser = build_chat_peg_parser([](common_chat_peg_builder & p) {
1048            return p.permute("a", { p.literal("a") }) + p.end();
1049        });
1050
1051        assert_gbnf_equal(t, R"""(
1052            root ::= "a"
1053            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1054        )""", gbnf_of(parser));
1055    });
1056
1057    t.test("grammar falls back to the given order when too large", [&](testing & t) {
1058        auto parser = build_chat_peg_parser([](common_chat_peg_builder & p) {
1059            std::vector<common_peg_parser> parsers;
1060            for (size_t i = 0; i <= COMMON_CHAT_MAX_PERMUTE; i++) {
1061                parsers.push_back(p.literal(std::string(1, (char) ('a' + i))));
1062            }
1063            return p.permute("big", parsers) + p.end();
1064        });
1065
1066        assert_gbnf_equal(t, R"""(
1067            root ::= "a" "b" "c" "d" "e" "f" "g"
1068            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1069        )""", gbnf_of(parser));
1070    });
1071}