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 "peg-parser.h"
2
3#include "common.h"
4#include "json-schema-to-grammar.h"
5#include "log.h"
6#include "trie.h"
7#include "unicode.h"
8
9#include <algorithm>
10#include <initializer_list>
11#include <map>
12#include <memory>
13#include <regex>
14#include <set>
15#include <stdexcept>
16
17// Trick to catch missing branches
18template <typename T>
19inline constexpr bool is_always_false_v = false;
20
21const char * common_peg_parse_result_type_name(common_peg_parse_result_type type) {
22    switch (type) {
23        case COMMON_PEG_PARSE_RESULT_FAIL:            return "fail";
24        case COMMON_PEG_PARSE_RESULT_SUCCESS:         return "success";
25        case COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT: return "need_more_input";
26        default:                                      return "unknown";
27    }
28}
29
30static bool is_hex_digit(const char c) {
31    return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F');
32}
33
34static std::pair<uint32_t, size_t> parse_hex_escape(const std::string & str, size_t pos, int hex_count) {
35    if (pos + hex_count > str.length()) {
36        return {0, 0};
37    }
38
39    uint32_t value = 0;
40    for (int i = 0; i < hex_count; i++) {
41        char c = str[pos + i];
42        if (!is_hex_digit(c)) {
43            return {0, 0};
44        }
45        value <<= 4;
46        if ('a' <= c && c <= 'f') {
47            value += c - 'a' + 10;
48        } else if ('A' <= c && c <= 'F') {
49            value += c - 'A' + 10;
50        } else if ('0' <= c && c <= '9') {
51            value += c - '0';
52        } else {
53            break;
54        }
55    }
56    return {value, static_cast<size_t>(hex_count)};
57}
58
59static std::pair<uint32_t, size_t> parse_char_class_char(const std::string & content, size_t pos) {
60    if (content[pos] == '\\' && pos + 1 < content.length()) {
61        switch (content[pos + 1]) {
62            case 'x': {
63                auto result = parse_hex_escape(content, pos + 2, 2);
64                if (result.second > 0) {
65                    return {result.first, 2 + result.second};
66                }
67                // Invalid escape, treat as literal 'x'
68                return {static_cast<uint32_t>('x'), 2};
69            }
70            case 'u': {
71                auto result = parse_hex_escape(content, pos + 2, 4);
72                if (result.second > 0) {
73                    return {result.first, 2 + result.second};
74                }
75                // Invalid escape, treat as literal 'u'
76                return {static_cast<uint32_t>('u'), 2};
77            }
78            case 'U': {
79                auto result = parse_hex_escape(content, pos + 2, 8);
80                if (result.second > 0) {
81                    return {result.first, 2 + result.second};
82                }
83                // Invalid escape, treat as literal 'U'
84                return {static_cast<uint32_t>('U'), 2};
85            }
86            case 'n':  return {'\n', 2};
87            case 't':  return {'\t', 2};
88            case 'r':  return {'\r', 2};
89            case '\\': return {'\\', 2};
90            case ']':  return {']', 2};
91            case '[':  return {'[', 2};
92            default:   return {static_cast<uint32_t>(content[pos + 1]), 2};
93        }
94    }
95
96    // Regular character - return as codepoint
97    return {static_cast<uint32_t>(static_cast<unsigned char>(content[pos])), 1};
98}
99
100static std::pair<std::vector<common_peg_chars_parser::char_range>, bool> parse_char_classes(const std::string & classes) {
101    std::vector<common_peg_chars_parser::char_range> ranges;
102    bool negated = false;
103
104    std::string content = classes;
105    if (content.front() == '[') {
106        content = content.substr(1);
107    }
108
109    if (content.back() == ']') {
110        content.pop_back();
111    }
112
113    // Check for negation
114    if (!content.empty() && content.front() == '^') {
115        negated = true;
116        content = content.substr(1);
117    }
118
119    size_t i = 0;
120    while (i < content.length()) {
121        auto [start, start_len] = parse_char_class_char(content, i);
122        i += start_len;
123
124        if (i + 1 < content.length() && content[i] == '-') {
125            // Range detected
126            auto [end, end_len] = parse_char_class_char(content, i + 1);
127            ranges.push_back(common_peg_chars_parser::char_range{start, end});
128            i += 1 + end_len;
129        } else {
130            ranges.push_back(common_peg_chars_parser::char_range{start, start});
131        }
132    }
133
134    return {ranges, negated};
135}
136
137common_peg_ast_id common_peg_ast_arena::find_by_tag(const common_peg_ast_node & parent, const std::string & tag, int max_depth) const {
138    for (auto child_id : parent.children) {
139        const auto & child = get(child_id);
140        if (child.tag == tag) {
141            return child_id;
142        }
143        if (max_depth > 1) {
144            auto result = find_by_tag(child, tag, max_depth - 1);
145            if (result != COMMON_PEG_INVALID_AST_ID) {
146                return result;
147            }
148        }
149    }
150    return COMMON_PEG_INVALID_AST_ID;
151}
152
153common_peg_ast_id common_peg_ast_arena::find_by_rule(const common_peg_ast_node & parent, const std::string & rule, int max_depth) const {
154    for (auto child_id : parent.children) {
155        const auto & child = get(child_id);
156        if (child.rule == rule) {
157            return child_id;
158        }
159        if (max_depth > 1) {
160            auto result = find_by_rule(child, rule, max_depth - 1);
161            if (result != COMMON_PEG_INVALID_AST_ID) {
162                return result;
163            }
164        }
165    }
166    return COMMON_PEG_INVALID_AST_ID;
167}
168
169void common_peg_ast_arena::visit(common_peg_ast_id id, const common_peg_ast_visitor & visitor) const {
170    if (id == COMMON_PEG_INVALID_AST_ID) {
171        return;
172    }
173    const auto & node = get(id);
174    visitor(node);
175    for (const auto & child : node.children) {
176        visit(child, visitor);
177    }
178}
179
180void common_peg_ast_arena::visit(const common_peg_parse_result & result, const common_peg_ast_visitor & visitor) const {
181    for (const auto & node : result.nodes) {
182        visit(node, visitor);
183    }
184}
185
186struct parser_executor;
187
188common_peg_parser_id common_peg_arena::add_parser(common_peg_parser_variant parser) {
189    common_peg_parser_id id = parsers_.size();
190    parsers_.push_back(std::move(parser));
191    return id;
192}
193
194void common_peg_arena::add_rule(const std::string & name, common_peg_parser_id id) {
195    rules_[name] = id;
196}
197
198common_peg_parser_id common_peg_arena::get_rule(const std::string & name) const {
199    auto it = rules_.find(name);
200    if (it == rules_.end()) {
201        throw std::runtime_error("Rule not found: " + name);
202    }
203    return it->second;
204}
205
206struct parser_executor {
207    const common_peg_arena & arena;
208    common_peg_parse_context & ctx;
209    size_t start_pos;
210
211    parser_executor(const common_peg_arena & arena, common_peg_parse_context & ctx, size_t start)
212        : arena(arena), ctx(ctx), start_pos(start) {}
213
214    std::string debug_indent() const { return std::string(ctx.parse_depth * 2, ' '); }
215
216    std::string debug_input_snippet(size_t pos, size_t len = 60) const {
217        if (pos >= ctx.input.size()) {
218            return "<EOF>";
219        }
220        auto        snippet = ctx.input.substr(pos, len);
221        // Escape newlines for display
222        std::string result;
223        for (char c : snippet) {
224            if (c == '\n') {
225                result += "\\n";
226            } else if (c == '\r') {
227                result += "\\r";
228            } else if (c == '\t') {
229                result += "\\t";
230            } else {
231                result += c;
232            }
233        }
234        if (pos + len < ctx.input.size()) {
235            result += "...";
236        }
237        return result;
238    }
239
240    common_peg_parse_result operator()(const common_peg_epsilon_parser & /* p */) const {
241        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos);
242    }
243
244    common_peg_parse_result operator()(const common_peg_start_parser & /* p */) const {
245        return common_peg_parse_result(
246            start_pos == 0 ? COMMON_PEG_PARSE_RESULT_SUCCESS : COMMON_PEG_PARSE_RESULT_FAIL,
247            start_pos
248        );
249    }
250
251    common_peg_parse_result operator()(const common_peg_end_parser & /* p */) const {
252        return common_peg_parse_result(
253            start_pos >= ctx.input.size() ? COMMON_PEG_PARSE_RESULT_SUCCESS : COMMON_PEG_PARSE_RESULT_FAIL,
254            start_pos
255        );
256    }
257
258    common_peg_parse_result operator()(const common_peg_literal_parser & p) {
259        auto pos = start_pos;
260        for (auto i = 0u; i < p.literal.size(); ++i) {
261            if (pos >= ctx.input.size()) {
262                if (!ctx.is_lenient()) {
263                    return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
264                }
265                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);
266            }
267            if (ctx.input[pos] != p.literal[i]) {
268                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
269            }
270            ++pos;
271        }
272
273        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);
274    }
275
276    common_peg_parse_result operator()(const common_peg_sequence_parser & p) {
277        if (ctx.is_debug()) {
278            LOG_DBG("%sSEQ start at %zu '%s' (%zu children)\n", debug_indent().c_str(), start_pos,
279                    debug_input_snippet(start_pos).c_str(), p.children.size());
280        }
281        ctx.parse_depth++;
282
283        auto pos = start_pos;
284        std::vector<common_peg_ast_id> nodes;
285
286        for (size_t i = 0; i < p.children.size(); i++) {
287            const auto & child_id = p.children[i];
288            if (ctx.is_debug()) {
289                fprintf(stderr, "%sSEQ child %zu: %s\n", debug_indent().c_str(), i, arena.dump(child_id).c_str());
290            }
291            auto result = arena.parse(child_id, ctx, pos);
292
293            if (ctx.is_debug()) {
294                fprintf(stderr, "%sSEQ child %zu: %s at %zu->%zu\n", debug_indent().c_str(), i,
295                        common_peg_parse_result_type_name(result.type), result.start, result.end);
296            }
297
298            if (result.fail()) {
299                ctx.parse_depth--;
300                if (ctx.is_debug()) {
301                    fprintf(stderr, "%sSEQ -> FAIL\n", debug_indent().c_str());
302                }
303                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos, result.end);
304            }
305
306            if (!result.nodes.empty()) {
307                nodes.insert(nodes.end(), result.nodes.begin(), result.nodes.end());
308            }
309
310            if (result.need_more_input()) {
311                ctx.parse_depth--;
312                if (ctx.is_debug()) {
313                    fprintf(stderr, "%sSEQ -> NEED_MORE\n", debug_indent().c_str());
314                }
315                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, result.end, std::move(nodes));
316            }
317
318            pos = result.end;
319        }
320
321        ctx.parse_depth--;
322        if (ctx.is_debug()) {
323            fprintf(stderr, "%sSEQ -> SUCCESS at %zu->%zu\n", debug_indent().c_str(), start_pos, pos);
324        }
325        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos, std::move(nodes));
326    }
327
328    common_peg_parse_result operator()(const common_peg_choice_parser & p) {
329        if (ctx.is_debug()) {
330            fprintf(stderr, "%sCHOICE start at %zu '%s' (%zu options)\n", debug_indent().c_str(), start_pos,
331                    debug_input_snippet(start_pos).c_str(), p.children.size());
332        }
333        ctx.parse_depth++;
334
335        auto pos = start_pos;
336        for (size_t i = 0; i < p.children.size(); i++) {
337            const auto & child_id = p.children[i];
338            if (ctx.is_debug()) {
339                fprintf(stderr, "%sCHOICE option %zu: %s\n", debug_indent().c_str(), i, arena.dump(child_id).c_str());
340            }
341            auto result = arena.parse(child_id, ctx, pos);
342            if (ctx.is_debug()) {
343                fprintf(stderr, "%sCHOICE option %zu: %s\n", debug_indent().c_str(), i,
344                        common_peg_parse_result_type_name(result.type));
345            }
346            if (!result.fail()) {
347                ctx.parse_depth--;
348                if (ctx.is_debug()) {
349                    fprintf(stderr, "%sCHOICE -> %s (option %zu)\n", debug_indent().c_str(),
350                            common_peg_parse_result_type_name(result.type), i);
351                }
352                return result;
353            }
354        }
355
356        ctx.parse_depth--;
357        if (ctx.is_debug()) {
358            fprintf(stderr, "%sCHOICE -> FAIL (no options matched)\n", debug_indent().c_str());
359        }
360        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
361    }
362
363    common_peg_parse_result operator()(const common_peg_repetition_parser & p) {
364        if (ctx.is_debug()) {
365            fprintf(stderr, "%sREPEAT start at %zu '%s' (min=%d, max=%d)\n", debug_indent().c_str(), start_pos,
366                    debug_input_snippet(start_pos).c_str(), p.min_count, p.max_count);
367        }
368        ctx.parse_depth++;
369
370        auto pos = start_pos;
371        int match_count = 0;
372        std::vector<common_peg_ast_id> nodes;
373
374        // Try to match up to max_count times (or unlimited if max_count is -1)
375        while (p.max_count == -1 || match_count < p.max_count) {
376            if (pos >= ctx.input.size()) {
377                if (ctx.is_debug()) {
378                    fprintf(stderr, "%sREPEAT: at end of input, count=%d\n", debug_indent().c_str(), match_count);
379                }
380                break;
381            }
382
383            auto result = arena.parse(p.child, ctx, pos);
384
385            if (ctx.is_debug()) {
386                fprintf(stderr, "%sREPEAT iter %d: %s at %zu->%zu, nodes=%zu\n", debug_indent().c_str(), match_count,
387                        common_peg_parse_result_type_name(result.type), result.start, result.end, result.nodes.size());
388                fprintf(stderr, "%sREPEAT CHILD: %s\n", debug_indent().c_str(), arena.dump(p.child).c_str());
389            }
390
391            if (result.success()) {
392                // Prevent infinite loop on empty matches
393                if (result.end == pos) {
394                    if (ctx.is_debug()) {
395                        fprintf(stderr, "%s  REPEAT: empty match, stopping\n", debug_indent().c_str());
396                    }
397                    break;
398                }
399
400                if (!result.nodes.empty()) {
401                    nodes.insert(nodes.end(), result.nodes.begin(), result.nodes.end());
402                }
403
404                pos = result.end;
405                match_count++;
406                continue;
407            }
408
409            if (result.need_more_input()) {
410                if (!result.nodes.empty()) {
411                    nodes.insert(nodes.end(), result.nodes.begin(), result.nodes.end());
412                }
413
414                ctx.parse_depth--;
415                if (ctx.is_debug()) {
416                    fprintf(stderr, "%sREPEAT -> NEED_MORE (count=%d, nodes=%zu)\n", debug_indent().c_str(),
417                            match_count, nodes.size());
418                }
419                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, result.end, std::move(nodes));
420            }
421
422            // Child failed - stop trying
423            if (ctx.is_debug()) {
424                fprintf(stderr, "%sREPEAT: child failed, stopping\n", debug_indent().c_str());
425            }
426            break;
427        }
428
429        // Check if we got enough matches
430        if (p.min_count > 0 && match_count < p.min_count) {
431            ctx.parse_depth--;
432            if (pos >= ctx.input.size() && ctx.is_lenient()) {
433                if (ctx.is_debug()) {
434                    fprintf(stderr, "%sREPEAT -> NEED_MORE (not enough matches: %d < %d)\n", debug_indent().c_str(),
435                            match_count, p.min_count);
436                }
437                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos, std::move(nodes));
438            }
439            if (ctx.is_debug()) {
440                fprintf(stderr, "%sREPEAT -> FAIL (not enough matches: %d < %d)\n", debug_indent().c_str(), match_count,
441                        p.min_count);
442            }
443            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos, pos);
444        }
445
446        ctx.parse_depth--;
447        if (ctx.is_debug()) {
448            fprintf(stderr, "%sREPEAT -> SUCCESS (count=%d, nodes=%zu)\n", debug_indent().c_str(), match_count,
449                    nodes.size());
450        }
451        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos, std::move(nodes));
452    }
453
454    common_peg_parse_result operator()(const common_peg_and_parser & p) {
455        auto result = arena.parse(p.child, ctx, start_pos);
456        // Pass result but don't consume input
457        return common_peg_parse_result(result.type, start_pos);
458    }
459
460    common_peg_parse_result operator()(const common_peg_not_parser & p) {
461        auto result = arena.parse(p.child, ctx, start_pos);
462
463        if (result.success()) {
464            // Fail if the underlying parser matches
465            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
466        }
467
468        if (result.need_more_input()) {
469            // Propagate - need to know what child would match before negating
470            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos);
471        }
472
473        // Child failed, so negation succeeds
474        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos);
475    }
476
477    common_peg_parse_result operator()(const common_peg_any_parser & /* p */) const {
478        // Parse a single UTF-8 codepoint (not just a single byte)
479        auto result = common_parse_utf8_codepoint(ctx.input, start_pos);
480
481        if (result.status == utf8_parse_result::INCOMPLETE) {
482            if (!ctx.is_lenient()) {
483                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
484            }
485            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos);
486        }
487        if (result.status == utf8_parse_result::INVALID) {
488            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
489        }
490        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, start_pos + result.bytes_consumed);
491    }
492
493    common_peg_parse_result operator()(const common_peg_space_parser & /* p */) {
494        auto pos = start_pos;
495        while (pos < ctx.input.size()) {
496            auto c = static_cast<unsigned char>(ctx.input[pos]);
497            if (std::isspace(c)) {
498                ++pos;
499            } else {
500                break;
501            }
502        }
503
504        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);
505    }
506
507    common_peg_parse_result operator()(const common_peg_chars_parser & p) const {
508        auto pos = start_pos;
509        int match_count = 0;
510
511        // Try to match up to max_count times (or unlimited if max_count is -1)
512        while (p.max_count == -1 || match_count < p.max_count) {
513            auto result = common_parse_utf8_codepoint(ctx.input, pos);
514
515            if (result.status == utf8_parse_result::INCOMPLETE) {
516                if (match_count >= p.min_count) {
517                    // We have enough matches, succeed with what we have
518                    return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);
519                }
520                // Not enough matches yet
521                if (!ctx.is_lenient()) {
522                    return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
523                }
524                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);
525            }
526
527            if (result.status == utf8_parse_result::INVALID) {
528                // Malformed UTF-8 in input
529                if (match_count >= p.min_count) {
530                    // We have enough matches, succeed up to here
531                    return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);
532                }
533                // Not enough matches, fail
534                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
535            }
536
537            // Check if this codepoint matches our character class
538            bool matches = false;
539            for (const auto & range : p.ranges) {
540                if (range.contains(result.codepoint)) {
541                    matches = true;
542                    break;
543                }
544            }
545
546            // If negated, invert the match result
547            if (p.negated) {
548                matches = !matches;
549            }
550
551            if (matches) {
552                pos += result.bytes_consumed;
553                ++match_count;
554            } else {
555                // Character doesn't match, stop matching
556                break;
557            }
558        }
559
560        // Check if we got enough matches
561        if (match_count < p.min_count) {
562            if (pos >= ctx.input.size() && ctx.is_lenient()) {
563                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);
564            }
565            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos, pos);
566        }
567
568        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);
569    }
570
571    static common_peg_parse_result handle_escape_sequence(common_peg_parse_context & ctx, size_t start, size_t & pos, const char delimiter) {
572        auto save = pos;
573
574        ++pos; // consume '\'
575        if (pos >= ctx.input.size()) {
576            if (!ctx.is_lenient()) {
577                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start);
578            }
579            pos = save; // suppress unmatched '\'
580            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start, pos);
581        }
582
583        char c = ctx.input[pos];
584
585        if (c == delimiter || c == '\\' || c == '/' || c == 'b' || c == 'f' || c == 'n' || c == 'r' || c == 't') {
586            ++pos;
587            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start, pos);
588        }
589
590        if (c == 'u') {
591            auto result = handle_unicode_escape(ctx, start, pos);
592            if (result.need_more_input()) {
593                pos = save; // suppress incomplete sequence
594                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start, pos);
595            }
596            return result;
597        }
598
599        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start);
600    }
601
602    static common_peg_parse_result handle_unicode_escape(common_peg_parse_context & ctx, size_t start, size_t & pos) {
603        ++pos; // consume 'u'
604        for (int i = 0; i < 4; ++i) {
605            if (pos >= ctx.input.size()) {
606                if (!ctx.is_lenient()) {
607                    return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start);
608                }
609                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start, pos);
610            }
611            if (!is_hex_digit(ctx.input[pos])) {
612                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start);
613            }
614            ++pos;
615        }
616        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start, pos);
617    }
618
619    common_peg_parse_result operator()(const common_peg_string_parser & p) {
620        auto pos = start_pos;
621
622        // Parse string content (without quotes)
623        while (pos < ctx.input.size()) {
624            char c = ctx.input[pos];
625
626            if (c == p.delimiter) {
627                // Found closing delimiter - success (don't consume it)
628                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);
629            }
630
631            if (c == '\\') {
632                auto result = handle_escape_sequence(ctx, start_pos, pos, p.delimiter);
633                if (!result.success()) {
634                    return result;
635                }
636            } else {
637                auto utf8_result = common_parse_utf8_codepoint(ctx.input, pos);
638
639                if (utf8_result.status == utf8_parse_result::INCOMPLETE) {
640                    if (!ctx.is_lenient()) {
641                        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
642                    }
643                    return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);
644                }
645
646                if (utf8_result.status == utf8_parse_result::INVALID) {
647                    return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
648                }
649
650                pos += utf8_result.bytes_consumed;
651            }
652        }
653
654        // Reached end without finding closing quote
655        if (!ctx.is_lenient()) {
656            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos, pos);
657        }
658        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);
659    }
660
661    common_peg_parse_result operator()(const common_peg_until_parser & p) const {
662        common_trie matcher(p.delimiters);
663
664        // Scan input and check for delimiters
665        size_t pos = start_pos;
666        size_t last_valid_pos = start_pos;
667
668        while (pos < ctx.input.size()) {
669            auto utf8_result = common_parse_utf8_codepoint(ctx.input, pos);
670
671            if (utf8_result.status == utf8_parse_result::INCOMPLETE) {
672                // Incomplete UTF-8 sequence
673                if (!ctx.is_lenient()) {
674                    // Input is complete but UTF-8 is incomplete = malformed
675                    return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
676                }
677                // Return what we have so far (before incomplete sequence)
678                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, last_valid_pos);
679            }
680
681            if (utf8_result.status == utf8_parse_result::INVALID) {
682                // Malformed UTF-8
683                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);
684            }
685
686            // Check if a delimiter starts at this position
687            auto match = matcher.check_at(ctx.input, pos);
688
689            if (match == common_trie::COMPLETE_MATCH) {
690                // Found a complete delimiter, return everything before it
691                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);
692            }
693
694            if (match == common_trie::PARTIAL_MATCH) {
695                // Found a partial match extending to end of input, return everything before it
696                return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);
697            }
698
699            pos += utf8_result.bytes_consumed;
700            last_valid_pos = pos;
701        }
702
703        if (last_valid_pos == ctx.input.size() && ctx.is_lenient()) {
704            // Reached the end of a partial stream, there might still be more input that we need to consume.
705            return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, last_valid_pos);
706        }
707        return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, last_valid_pos);
708    }
709
710    common_peg_parse_result operator()(const common_peg_schema_parser & p) {
711        return arena.parse(p.child, ctx, start_pos);
712    }
713
714    common_peg_parse_result operator()(const common_peg_rule_parser & p) {
715        // Parse the child
716        auto result = arena.parse(p.child, ctx, start_pos);
717
718        if (!result.fail()) {
719            std::string_view text;
720            if (result.start < ctx.input.size()) {
721                text = std::string_view(ctx.input).substr(result.start, result.end - result.start);
722            }
723
724            auto node_id = ctx.ast.add_node(
725                p.name,
726                "",
727                result.start,
728                result.end,
729                text,
730                std::move(result.nodes),
731                result.need_more_input()
732            );
733
734            return common_peg_parse_result(result.type, result.start, result.end, { node_id });
735        }
736
737        return result;
738    }
739
740    common_peg_parse_result operator()(const common_peg_tag_parser & p) {
741        // Parse the child
742        if (ctx.is_debug()) {
743            fprintf(stderr, "%sTAG: %s\n", debug_indent().c_str(), p.tag.c_str());
744        }
745        auto result = arena.parse(p.child, ctx, start_pos);
746
747        if (!result.fail()) {
748            std::string_view text;
749            if (result.start < ctx.input.size()) {
750                text = std::string_view(ctx.input).substr(result.start, result.end - result.start);
751            }
752
753            auto node_id = ctx.ast.add_node(
754                "",
755                p.tag,
756                result.start,
757                result.end,
758                text,
759                std::move(result.nodes),
760                result.need_more_input()
761            );
762
763            return common_peg_parse_result(result.type, result.start, result.end, { node_id });
764        }
765
766        return result;
767    }
768
769    common_peg_parse_result operator()(const common_peg_ref_parser & p) {
770        auto rule_id = arena.get_rule(p.name);
771        return arena.parse(rule_id, ctx, start_pos);
772    }
773
774    common_peg_parse_result operator()(const common_peg_atomic_parser & p) {
775        auto result = arena.parse(p.child, ctx, start_pos);
776        if (result.need_more_input()) {
777            // Clear nodes so they don't propagate up.
778            result.nodes.clear();
779        }
780        return result;
781    }
782
783    common_peg_parse_result operator()(const common_peg_gbnf_parser & p) {
784        return arena.parse(p.child, ctx, start_pos);
785    }
786
787    common_peg_parse_result operator()(const common_peg_ac_parser & p) {
788        return arena.parse(p.child, ctx, start_pos);
789    }
790};
791
792common_peg_parse_result common_peg_arena::parse(common_peg_parse_context & ctx, size_t start) const {
793    if (root_ == COMMON_PEG_INVALID_PARSER_ID) {
794        throw std::runtime_error("No root parser set");
795    }
796    return parse(root_, ctx, start);
797}
798
799common_peg_parse_result common_peg_arena::parse(common_peg_parser_id id, common_peg_parse_context & ctx, size_t start) const {
800    // Execute parser
801    const auto & parser = parsers_.at(id);
802    parser_executor exec(*this, ctx, start);
803    return std::visit(exec, parser);
804}
805
806common_peg_parser_id common_peg_arena::resolve_ref(common_peg_parser_id id) {
807    const auto & parser = parsers_.at(id);
808    if (auto ref = std::get_if<common_peg_ref_parser>(&parser)) {
809        return get_rule(ref->name);
810    }
811    return id;
812}
813
814static void bfs_node(common_peg_ast_arena &arena, std::ostringstream & oss, const common_peg_ast_node & node, int indent) {
815    for (int i = 0; i < indent; i++) {
816        oss << "  ";
817    }
818    oss << "NODE " << node.id;
819    if (!node.rule.empty()) {
820        oss << " (rule " << node.rule << ")";
821    }
822    if (!node.tag.empty()) {
823        oss << " (tag " << node.tag << ")";
824    }
825    oss << " ['" << node.text << "']\n";
826    for (const auto child : node.children) {
827        bfs_node(arena, oss, arena.get(child), indent + 1);
828    }
829}
830
831std::string common_peg_ast_arena::dump() {
832    std::ostringstream oss;
833    for (auto & node : nodes_) {
834        bfs_node(*this, oss, node, 0);
835    }
836    return oss.str();
837}
838
839void common_peg_arena::resolve_refs() {
840    // Walk through all parsers and replace refs with their corresponding rule IDs
841    for (auto & parser : parsers_) {
842        std::visit([this](auto & p) {
843            using T = std::decay_t<decltype(p)>;
844
845            if constexpr (std::is_same_v<T, common_peg_sequence_parser>) {
846                for (auto & child : p.children) {
847                    child = resolve_ref(child);
848                }
849            } else if constexpr (std::is_same_v<T, common_peg_choice_parser>) {
850                for (auto & child : p.children) {
851                    child = resolve_ref(child);
852                }
853            } else if constexpr (std::is_same_v<T, common_peg_repetition_parser> ||
854                                 std::is_same_v<T, common_peg_and_parser> ||
855                                 std::is_same_v<T, common_peg_not_parser> ||
856                                 std::is_same_v<T, common_peg_tag_parser> ||
857                                 std::is_same_v<T, common_peg_atomic_parser> ||
858                                 std::is_same_v<T, common_peg_gbnf_parser> ||
859                                 std::is_same_v<T, common_peg_ac_parser>) {
860                p.child = resolve_ref(p.child);
861            } else if constexpr (std::is_same_v<T, common_peg_rule_parser>) {
862                p.child = resolve_ref(p.child);
863            } else if constexpr (std::is_same_v<T, common_peg_schema_parser>) {
864                p.child = resolve_ref(p.child);
865            } else if constexpr (std::is_same_v<T, common_peg_epsilon_parser> ||
866                                 std::is_same_v<T, common_peg_start_parser> ||
867                                 std::is_same_v<T, common_peg_end_parser> ||
868                                 std::is_same_v<T, common_peg_ref_parser> ||
869                                 std::is_same_v<T, common_peg_until_parser> ||
870                                 std::is_same_v<T, common_peg_literal_parser> ||
871                                 std::is_same_v<T, common_peg_string_parser> ||
872                                 std::is_same_v<T, common_peg_chars_parser> ||
873                                 std::is_same_v<T, common_peg_any_parser> ||
874                                 std::is_same_v<T, common_peg_space_parser>) {
875                // These rules do not have children
876            } else {
877                static_assert(is_always_false_v<T>);
878            }
879        }, parser);
880    }
881
882    // Also flatten root if it's a ref
883    if (root_ != COMMON_PEG_INVALID_PARSER_ID) {
884        root_ = resolve_ref(root_);
885    }
886}
887
888std::string common_peg_arena::dump(common_peg_parser_id id) const {
889    std::set<common_peg_parser_id> visited;
890    return dump_impl(id, visited);
891}
892
893std::string common_peg_arena::dump_impl(common_peg_parser_id                       id,
894                                        std::set<common_peg_parser_id> & visited) const {
895    // Check for cycles
896    if (visited.count(id)) {
897        return "[cycle]";
898    }
899    visited.insert(id);
900
901    const auto & parser = parsers_.at(id);
902
903    return std::visit([this, &visited](const auto & p) -> std::string {
904        using T = std::decay_t<decltype(p)>;
905
906        if constexpr (std::is_same_v<T, common_peg_epsilon_parser>) {
907            return "Epsilon";
908        } else if constexpr (std::is_same_v<T, common_peg_start_parser>) {
909            return "Start";
910        } else if constexpr (std::is_same_v<T, common_peg_end_parser>) {
911            return "End";
912        } else if constexpr (std::is_same_v<T, common_peg_literal_parser>) {
913            return "Literal(" + p.literal + ")";
914        } else if constexpr (std::is_same_v<T, common_peg_sequence_parser>) {
915            std::vector<std::string> parts;
916            for (const auto & child : p.children) {
917                parts.push_back(dump_impl(child, visited));
918            }
919            return "Sequence(" + string_join(parts, ", ") + ")";
920        } else if constexpr (std::is_same_v<T, common_peg_choice_parser>) {
921            std::vector<std::string> parts;
922            for (const auto & child : p.children) {
923                parts.push_back(dump_impl(child, visited));
924            }
925            return "Choice(" + string_join(parts, ", ") + ")";
926        } else if constexpr (std::is_same_v<T, common_peg_repetition_parser>) {
927            if (p.max_count == -1) {
928                return "Repetition(" + dump_impl(p.child, visited) + ", " + std::to_string(p.min_count) +
929                        ", unbounded)";
930            }
931            return "Repetition(" + dump_impl(p.child, visited) + ", " + std::to_string(p.min_count) + ", " + std::to_string(p.max_count) + ")";
932        } else if constexpr (std::is_same_v<T, common_peg_and_parser>) {
933            return "And(" + dump_impl(p.child, visited) + ")";
934        } else if constexpr (std::is_same_v<T, common_peg_not_parser>) {
935            return "Not(" + dump_impl(p.child, visited) + ")";
936        } else if constexpr (std::is_same_v<T, common_peg_atomic_parser>) {
937            return "Atomic(" + dump_impl(p.child, visited) + ")";
938        } else if constexpr (std::is_same_v<T, common_peg_gbnf_parser>) {
939            return "Gbnf(" + p.grammar + ", " + dump_impl(p.child, visited) + ")";
940        } else if constexpr (std::is_same_v<T, common_peg_ac_parser>) {
941            return "Ac(" + string_join(p.delimiters, " | ") + ", " + dump_impl(p.child, visited) + ")";
942        } else if constexpr (std::is_same_v<T, common_peg_any_parser>) {
943            return "Any";
944        } else if constexpr (std::is_same_v<T, common_peg_space_parser>) {
945            return "Space";
946        } else if constexpr (std::is_same_v<T, common_peg_chars_parser>) {
947            if (p.max_count == -1) {
948                return "CharRepeat(" + p.pattern + ", " + std::to_string(p.min_count) + ", unbounded)";
949            }
950            return "CharRepeat(" + p.pattern + ", " + std::to_string(p.min_count) + ", " + std::to_string(p.max_count) + ")";
951        } else if constexpr (std::is_same_v<T, common_peg_string_parser>) {
952            return "String(" + std::string(1, p.delimiter) + ")";
953        } else if constexpr (std::is_same_v<T, common_peg_until_parser>) {
954            return "Until(" + string_join(p.delimiters, " | ") + ")";
955        } else if constexpr (std::is_same_v<T, common_peg_schema_parser>) {
956            return "Schema(" + dump_impl(p.child, visited) + ", " + (p.node ? common_chat_schema::kind_name(p.node->kind()) : "null") + ")";
957        } else if constexpr (std::is_same_v<T, common_peg_rule_parser>) {
958            return "Rule(" + p.name + ", " + dump_impl(p.child, visited) + ")";
959        } else if constexpr (std::is_same_v<T, common_peg_ref_parser>) {
960            return "Ref(" + p.name + ")";
961        } else if constexpr (std::is_same_v<T, common_peg_tag_parser>) {
962            return "Tag(" + p.tag + ", " + dump(p.child) + ")";
963        } else if constexpr (std::is_same_v<T, common_peg_atomic_parser>) {
964            return "Atomic(" + dump(p.child) + ")";
965        } else {
966            return "Unknown";
967        }
968    }, parser);
969}
970
971common_peg_parser & common_peg_parser::operator=(const common_peg_parser & other) {
972    id_ = other.id_;
973    return *this;
974}
975
976common_peg_parser & common_peg_parser::operator+=(const common_peg_parser & other) {
977    id_ = builder_.sequence({id_, other.id_});
978    return *this;
979}
980
981common_peg_parser & common_peg_parser::operator|=(const common_peg_parser & other) {
982    id_ = builder_.choice({id_, other.id_});
983    return *this;
984}
985
986common_peg_parser common_peg_parser::operator+(const common_peg_parser & other) const {
987    return builder_.sequence({id_, other.id_});
988}
989
990common_peg_parser common_peg_parser::operator|(const common_peg_parser & other) const {
991    return builder_.choice({id_, other.id_});
992}
993
994common_peg_parser common_peg_parser::operator<<(const common_peg_parser & other) const {
995    return builder_.sequence({id_, builder_.space(), other.id_});
996}
997
998common_peg_parser common_peg_parser::operator+(const char * str) const {
999    return *this + builder_.literal(str);
1000}
1001
1002common_peg_parser common_peg_parser::operator+(const std::string & str) const {
1003    return *this + builder_.literal(str);
1004}
1005
1006common_peg_parser common_peg_parser::operator<<(const char * str) const {
1007    return *this << builder_.literal(str);
1008}
1009
1010common_peg_parser common_peg_parser::operator<<(const std::string & str) const {
1011    return *this << builder_.literal(str);
1012}
1013
1014common_peg_parser common_peg_parser::operator|(const char * str) const {
1015    return *this | builder_.literal(str);
1016}
1017
1018common_peg_parser common_peg_parser::operator|(const std::string & str) const {
1019    return *this | builder_.literal(str);
1020}
1021
1022common_peg_parser operator+(const char * str, const common_peg_parser & p) {
1023    return p.builder().literal(str) + p;
1024}
1025
1026common_peg_parser operator+(const std::string & str, const common_peg_parser & p) {
1027    return operator+(str.c_str(), p);
1028}
1029
1030common_peg_parser operator<<(const char * str, const common_peg_parser & p) {
1031    return p.builder().literal(str) << p;
1032}
1033
1034common_peg_parser operator<<(const std::string & str, const common_peg_parser & p) {
1035    return operator<<(str.c_str(), p);
1036}
1037
1038common_peg_parser operator|(const char * str, const common_peg_parser & p) {
1039    return p.builder().literal(str) | p;
1040}
1041
1042common_peg_parser operator|(const std::string & str, const common_peg_parser & p) {
1043    return operator|(str.c_str(), p);
1044}
1045
1046static std::string rule_name(const std::string & name) {
1047    static const std::regex invalid_rule_chars_re("[^a-zA-Z0-9-]+");
1048    return std::regex_replace(name, invalid_rule_chars_re, "-");
1049}
1050
1051common_peg_parser_builder::common_peg_parser_builder() {}
1052
1053common_peg_parser common_peg_parser_builder::sequence(const std::vector<common_peg_parser_id> & parsers) {
1054    // Flatten nested sequences
1055    std::vector<common_peg_parser_id> flattened;
1056    for (const auto & p : parsers) {
1057        const auto & parser = arena_.get(p);
1058        if (auto seq = std::get_if<common_peg_sequence_parser>(&parser)) {
1059            flattened.insert(flattened.end(), seq->children.begin(), seq->children.end());
1060        } else {
1061            flattened.push_back(p);
1062        }
1063    }
1064    return wrap(arena_.add_parser(common_peg_sequence_parser{flattened}));
1065}
1066
1067common_peg_parser common_peg_parser_builder::sequence(const std::vector<common_peg_parser> & parsers) {
1068    std::vector<common_peg_parser_id> ids;
1069    ids.reserve(parsers.size());
1070    for (const auto & p : parsers) {
1071        ids.push_back(p.id());
1072    }
1073    return sequence(ids);
1074}
1075
1076common_peg_parser common_peg_parser_builder::sequence(std::initializer_list<common_peg_parser> parsers) {
1077    std::vector<common_peg_parser_id> ids;
1078    ids.reserve(parsers.size());
1079    for (const auto & p : parsers) {
1080        ids.push_back(p.id());
1081    }
1082    return sequence(ids);
1083}
1084
1085common_peg_parser common_peg_parser_builder::choice(const std::vector<common_peg_parser_id> & parsers) {
1086    // Flatten nested choices
1087    std::vector<common_peg_parser_id> flattened;
1088    for (const auto & p : parsers) {
1089        const auto & parser = arena_.get(p);
1090        if (auto choice = std::get_if<common_peg_choice_parser>(&parser)) {
1091            flattened.insert(flattened.end(), choice->children.begin(), choice->children.end());
1092        } else {
1093            flattened.push_back(p);
1094        }
1095    }
1096    return wrap(arena_.add_parser(common_peg_choice_parser{flattened}));
1097}
1098
1099common_peg_parser common_peg_parser_builder::choice(const std::vector<common_peg_parser> & parsers) {
1100    std::vector<common_peg_parser_id> ids;
1101    ids.reserve(parsers.size());
1102    for (const auto & p : parsers) {
1103        ids.push_back(p.id());
1104    }
1105    return choice(ids);
1106}
1107
1108common_peg_parser common_peg_parser_builder::choice(std::initializer_list<common_peg_parser> parsers) {
1109    std::vector<common_peg_parser_id> ids;
1110    ids.reserve(parsers.size());
1111    for (const auto & p : parsers) {
1112        ids.push_back(p.id());
1113    }
1114    return choice(ids);
1115}
1116
1117common_peg_parser common_peg_parser_builder::chars(const std::string & classes, int min, int max) {
1118    auto [ranges, negated] = parse_char_classes(classes);
1119    return wrap(arena_.add_parser(common_peg_chars_parser{classes, ranges, negated, min, max}));
1120}
1121
1122common_peg_parser common_peg_parser_builder::schema(const common_peg_parser & p, const std::string & name, common_chat_schema_document_ptr doc, const common_chat_schema & node, bool raw) {
1123    return wrap(arena_.add_parser(common_peg_schema_parser{p.id(), name, std::move(doc), &node, raw}));
1124}
1125
1126common_peg_parser common_peg_parser_builder::schema(const common_peg_parser & p, const std::string & name, const common_json & schema, bool raw) {
1127    auto doc = std::make_shared<const common_chat_schema_document>(common_chat_schema_from_json(schema));
1128    return this->schema(p, name, doc, *doc->root, raw);
1129}
1130
1131common_peg_parser common_peg_parser_builder::rule(const std::string & name, const common_peg_parser & p, bool trigger) {
1132    auto clean_name = rule_name(name);
1133    auto rule_id = arena_.add_parser(common_peg_rule_parser{clean_name, p.id(), trigger});
1134    arena_.add_rule(clean_name, rule_id);
1135    return ref(clean_name);
1136}
1137
1138common_peg_parser common_peg_parser_builder::rule(const std::string & name, const std::function<common_peg_parser()> & builder_fn, bool trigger) {
1139    auto clean_name = rule_name(name);
1140    if (arena_.has_rule(clean_name)) {
1141        return ref(clean_name);
1142    }
1143
1144    // Create placeholder rule to allow recursive references
1145    auto placeholder = any();  // Temporary placeholder
1146    auto placeholder_rule_id = arena_.add_parser(common_peg_rule_parser{clean_name, placeholder.id(), trigger});
1147    arena_.add_rule(clean_name, placeholder_rule_id);
1148
1149    // Build the actual parser
1150    auto parser = builder_fn();
1151
1152    // Replace placeholder with actual rule
1153    auto rule_id = arena_.add_parser(common_peg_rule_parser{clean_name, parser.id(), trigger});
1154    arena_.rules_[clean_name] = rule_id;
1155
1156    return ref(clean_name);
1157}
1158
1159void common_peg_parser_builder::set_root(const common_peg_parser & p) {
1160    arena_.set_root(p.id());
1161}
1162
1163common_peg_arena common_peg_parser_builder::build() {
1164    arena_.resolve_refs();
1165    return std::move(arena_);
1166}
1167
1168// String primitives
1169
1170common_peg_parser common_peg_parser_builder::string_content(char delimiter) {
1171    return wrap(arena_.add_parser(common_peg_string_parser{delimiter}));
1172}
1173
1174common_peg_parser common_peg_parser_builder::double_quoted_string() {
1175    return rule("double-quoted-string", [this]() {
1176        return sequence({literal("\""), string_content('"'), literal("\"")});
1177    });
1178}
1179
1180common_peg_parser common_peg_parser_builder::single_quoted_string() {
1181    return rule("single-quoted-string", [this]() {
1182        return sequence({literal("'"), string_content('\''), literal("'")});
1183    });
1184}
1185
1186common_peg_parser common_peg_parser_builder::quoted_string() {
1187    return rule("quoted-string", [this]() {
1188        return choice({double_quoted_string(), single_quoted_string()});
1189    });
1190}
1191
1192// JSON parsers
1193
1194common_peg_parser common_peg_parser_builder::json_number() {
1195   return rule("json-number", [this]() {
1196        auto digit1_9 = chars("[1-9]", 1, 1);
1197        auto digits = chars("[0-9]");
1198        auto int_part = choice({literal("0"), sequence({digit1_9, chars("[0-9]", 0, -1)})});
1199        auto frac = sequence({literal("."), digits});
1200        auto exp = sequence({choice({literal("e"), literal("E")}), optional(chars("[+-]", 1, 1)), digits});
1201        // Negative lookahead: only commit the number when the next character can't extend it.
1202        // At EOF in partial mode, chars returns NEED_MORE → negate propagates NEED_MORE → number not committed.
1203        // This prevents premature commits of partial numbers (e.g. "3" when "3.14" is incoming).
1204        auto not_number_continuation = negate(chars("[0-9.eE+-]", 1, 1));
1205        return sequence({ optional(literal("-")), int_part, optional(frac), optional(exp), not_number_continuation });
1206    });
1207}
1208
1209common_peg_parser common_peg_parser_builder::json_string() {
1210    return rule("json-string", [this]() {
1211        return sequence({literal("\""), string_content('"'), literal("\"")});
1212    });
1213}
1214
1215common_peg_parser common_peg_parser_builder::json_bool() {
1216    return rule("json-bool", [this]() {
1217        return choice({literal("true"), literal("false")});
1218    });
1219}
1220
1221common_peg_parser common_peg_parser_builder::json_null() {
1222    return rule("json-null", [this]() {
1223        return literal("null");
1224    });
1225}
1226
1227common_peg_parser common_peg_parser_builder::json_object() {
1228    return rule("json-object", [this]() {
1229        auto ws = space();
1230        auto member = sequence({json_string(), ws, literal(":"), ws, json()});
1231        auto members = sequence({member, zero_or_more(sequence({ws, literal(","), ws, member}))});
1232        return sequence({
1233            literal("{"),
1234            ws,
1235            choice({
1236                literal("}"),
1237                sequence({members, ws, literal("}")})
1238            })
1239        });
1240    });
1241}
1242
1243common_peg_parser common_peg_parser_builder::json_array() {
1244    return rule("json-array", [this]() {
1245        auto ws = space();
1246        auto elements = sequence({json(), zero_or_more(sequence({ws, literal(","), ws, json()}))});
1247        return sequence({
1248            literal("["),
1249            ws,
1250            choice({
1251                literal("]"),
1252                sequence({elements, ws, literal("]")})
1253            })
1254        });
1255    });
1256}
1257
1258common_peg_parser common_peg_parser_builder::json() {
1259    return rule("json-value", [this]() {
1260        return choice({
1261            json_object(),
1262            json_array(),
1263            json_string(),
1264            json_number(),
1265            json_bool(),
1266            json_null()
1267        });
1268    });
1269}
1270
1271common_peg_parser common_peg_parser_builder::python_string() {
1272    return rule("python-string", [this]() {
1273        return choice({double_quoted_string(), single_quoted_string()});
1274    });
1275}
1276
1277common_peg_parser common_peg_parser_builder::python_number() {
1278    return json_number();
1279}
1280
1281common_peg_parser common_peg_parser_builder::python_bool() {
1282    return rule("python-bool", [this]() {
1283        return choice({literal("True"), literal("False")});
1284    });
1285}
1286
1287common_peg_parser common_peg_parser_builder::python_null() {
1288    return rule("python-none", [this]() {
1289        return literal("None");
1290    });
1291}
1292
1293common_peg_parser common_peg_parser_builder::python_dict() {
1294    return rule("python-dict", [this]() {
1295        auto ws = space();
1296        auto member = sequence({python_string(), ws, literal(":"), ws, python_value()});
1297        auto members = sequence({member, zero_or_more(sequence({ws, literal(","), ws, member}))});
1298        return sequence({
1299            literal("{"),
1300            ws,
1301            choice({
1302                literal("}"),
1303                sequence({members, ws, literal("}")})
1304            }),
1305            ws
1306        });
1307    });
1308}
1309
1310common_peg_parser common_peg_parser_builder::python_array() {
1311    return rule("python-array", [this]() {
1312        auto ws = space();
1313        auto elements = sequence({python_value(), zero_or_more(sequence({literal(","), ws, python_value()}))});
1314        return sequence({
1315            literal("["),
1316            ws,
1317            choice({
1318                literal("]"),
1319                sequence({elements, ws, literal("]")})
1320            }),
1321            ws
1322        });
1323    });
1324}
1325
1326common_peg_parser common_peg_parser_builder::python_value() {
1327    return rule("python-value", [this]() {
1328        return choice({
1329            python_dict(),
1330            python_array(),
1331            python_string(),
1332            python_number(),
1333            python_bool(),
1334            python_null()
1335        });
1336    });
1337}
1338
1339common_peg_parser common_peg_parser_builder::marker() {
1340    auto sharp_bracket_parser = literal("<") + until(">") + literal(">");
1341    auto square_bracket_parser = literal("[") + until("]") + literal("]");
1342    return choice({ sharp_bracket_parser, square_bracket_parser });
1343}
1344
1345common_peg_parser common_peg_parser_builder::json_member(const std::string & key, const common_peg_parser & p) {
1346    auto ws = space();
1347    return sequence({
1348        literal("\"" + key + "\""),
1349        ws,
1350        literal(":"),
1351        ws,
1352        p,
1353    });
1354}
1355
1356common_peg_parser common_peg_parser_builder::ac(const common_peg_parser & p, const std::vector<std::string> & delimiters) {
1357    if (delimiters.empty()) {
1358        throw std::runtime_error("ac parser requires at least one delimiter");
1359    }
1360    return add(common_peg_ac_parser{p, delimiters});
1361}
1362
1363static std::string gbnf_escape_char_class(uint32_t c) {
1364    if (c == '-' || c == ']' || c == '[' || c == '\\') {
1365        return "\\" + std::string(1, (char) c);
1366    }
1367    // Escape whitespace control characters
1368    if (c == '\n') {
1369        return "\\n";
1370    }
1371    if (c == '\t') {
1372        return "\\t";
1373    }
1374    if (c == '\r') {
1375        return "\\r";
1376    }
1377
1378    // Printable ASCII
1379    if (c >= 0x20 && c <= 0x7E) {
1380        return std::string(1, (char) c);
1381    }
1382
1383    // Hex escape
1384    char         buf[16];
1385    const char * hex = "0123456789ABCDEF";
1386
1387    if (c <= 0xFF) {
1388        buf[0] = '\\';
1389        buf[1] = 'x';
1390        buf[2] = hex[(c >> 4) & 0xF];
1391        buf[3] = hex[c & 0xF];
1392        buf[4] = '\0';
1393    } else if (c <= 0xFFFF) {
1394        buf[0] = '\\';
1395        buf[1] = 'u';
1396        buf[2] = hex[(c >> 12) & 0xF];
1397        buf[3] = hex[(c >> 8) & 0xF];
1398        buf[4] = hex[(c >> 4) & 0xF];
1399        buf[5] = hex[c & 0xF];
1400        buf[6] = '\0';
1401    } else {
1402        buf[0] = '\\';
1403        buf[1] = 'U';
1404        for (int i = 0; i < 8; i++) {
1405            buf[2 + i] = hex[(c >> ((7 - i) * 4)) & 0xF];
1406        }
1407        buf[10] = '\0';
1408    }
1409
1410    return std::string(buf);
1411}
1412
1413static std::string gbnf_char_class(const std::vector<uint32_t> & chars, bool negate) {
1414    std::string s = negate ? "[^" : "[";
1415    for (uint32_t ch : chars) {
1416        s += gbnf_escape_char_class(ch);
1417    }
1418    return s + "]";
1419}
1420
1421static std::string gbnf_ac_grammar(
1422    const common_grammar_builder &   builder,
1423    const std::string &              prefix,
1424    const std::vector<std::string> & strings,
1425    const std::function<std::string(const std::vector<uint32_t> &,
1426                                    const std::map<size_t, std::vector<uint32_t>> &,
1427                                    const std::vector<uint32_t> &,
1428                                    const std::function<std::string(size_t)> &)> & build_rule) {
1429    common_aho_corasick ac(strings);
1430
1431    auto state_name = [&](size_t s) -> std::string {
1432        if (s == 0) {
1433            return prefix;
1434        }
1435        std::string num = std::to_string(s);
1436        num = num.size() == 1 ? ("0" + num) : num;
1437        return prefix + "-" + num;
1438    };
1439
1440    for (size_t q = 0; q < ac.num_states(); q++) {
1441        if (ac.is_terminal(q)) {
1442            continue; // match states
1443        }
1444
1445        std::map<size_t, std::vector<uint32_t>> buckets;
1446        std::vector<uint32_t> completing;  // chars that complete a delimiter
1447        std::vector<uint32_t> specific;    // chars with an explicit transition
1448        for (uint32_t c : ac.alphabet) {
1449            size_t d = ac.next(q, c);
1450            if (ac.is_terminal(d)) {
1451                completing.push_back(c);
1452                specific.push_back(c);
1453            } else if (d != 0) {
1454                buckets[d].push_back(c); // specific non-root destination
1455                specific.push_back(c);
1456            }
1457        }
1458
1459        builder.add_rule(state_name(q), build_rule(completing, buckets, specific, state_name));
1460    }
1461
1462    // An empty delimiter makes the start state terminal. Emit an entry rule
1463    // that matches the empty string so the returned reference stays valid.
1464    if (ac.is_terminal(0)) {
1465        builder.add_rule(prefix, "|");
1466    }
1467
1468    return state_name(0);
1469}
1470
1471// GBNF grammar matching strings that contain no string in `strings` as a
1472// substring. Emits the complement of an Aho-Corasick automaton DFA and returns
1473// the start state rule name.
1474//
1475// ref: https://github.com/ggml-org/llama.cpp/pull/24839
1476static std::string gbnf_excluding_grammar(const common_grammar_builder & builder,
1477                                          const std::string &            prefix,
1478                                          const std::vector<std::string> & strings) {
1479    return gbnf_ac_grammar(builder, prefix, strings,
1480        [](const std::vector<uint32_t> & /*completing*/,
1481           const std::map<size_t, std::vector<uint32_t>> & buckets,
1482           const std::vector<uint32_t> & specific,
1483           const std::function<std::string(size_t)> & state_name) {
1484            // every state is accepting and completing chars get no
1485            // alternative, so a forbidden string can never be matched
1486            std::string rhs = "|";
1487            for (const auto & [d, chars] : buckets) {
1488                rhs += " " + gbnf_char_class(chars, false) + " " + state_name(d) + " |";
1489            }
1490            rhs += " " + gbnf_char_class(specific, true) + " " + state_name(0);
1491            return rhs;
1492        });
1493}
1494
1495// GBNF grammar matching everything up to and including the first occurrence of
1496// any string in `strings`. Emits the Aho-Corasick automaton DFA and returns
1497// the start state rule name.
1498static std::string gbnf_including_grammar(const common_grammar_builder & builder,
1499                                          const std::string &            prefix,
1500                                          const std::vector<std::string> & strings) {
1501    return gbnf_ac_grammar(builder, prefix, strings,
1502        [](const std::vector<uint32_t> & completing,
1503           const std::map<size_t, std::vector<uint32_t>> & buckets,
1504           const std::vector<uint32_t> & specific,
1505           const std::function<std::string(size_t)> & state_name) {
1506            std::vector<std::string> alts;
1507            if (!completing.empty()) {
1508                alts.push_back(gbnf_char_class(completing, false)); // terminate on match
1509            }
1510            for (const auto & [d, chars] : buckets) {
1511                alts.push_back(gbnf_char_class(chars, false) + " " + state_name(d));
1512            }
1513            // every other character keeps scanning from the start state
1514            alts.push_back(gbnf_char_class(specific, true) + " " + state_name(0));
1515            return string_join(alts, " | ");
1516        });
1517}
1518
1519static std::set<std::string> collect_reachable_rules(
1520    const common_peg_arena & arena,
1521    const common_peg_parser_id & rule
1522) {
1523    std::set<std::string> reachable;
1524    std::set<std::string> visited;
1525
1526    std::function<void(common_peg_parser_id)> visit = [&](common_peg_parser_id id) {
1527        const auto & parser = arena.get(id);
1528
1529        std::visit([&](const auto & p) {
1530            using T = std::decay_t<decltype(p)>;
1531
1532            if constexpr (std::is_same_v<T, common_peg_epsilon_parser> ||
1533                          std::is_same_v<T, common_peg_start_parser> ||
1534                          std::is_same_v<T, common_peg_end_parser> ||
1535                          std::is_same_v<T, common_peg_until_parser> ||
1536                          std::is_same_v<T, common_peg_literal_parser> ||
1537                          std::is_same_v<T, common_peg_chars_parser> ||
1538                          std::is_same_v<T, common_peg_space_parser> ||
1539                          std::is_same_v<T, common_peg_any_parser> ||
1540                          std::is_same_v<T, common_peg_string_parser>) {
1541                // These parsers do not have any children
1542            } else if constexpr (std::is_same_v<T, common_peg_sequence_parser>) {
1543                for (auto child : p.children) {
1544                    visit(child);
1545                }
1546            } else if constexpr (std::is_same_v<T, common_peg_choice_parser>) {
1547                for (auto child : p.children) {
1548                    visit(child);
1549                }
1550            } else if constexpr (std::is_same_v<T, common_peg_repetition_parser> ||
1551                                 std::is_same_v<T, common_peg_and_parser> ||
1552                                 std::is_same_v<T, common_peg_not_parser> ||
1553                                 std::is_same_v<T, common_peg_tag_parser> ||
1554                                 std::is_same_v<T, common_peg_atomic_parser> ||
1555                                 std::is_same_v<T, common_peg_gbnf_parser> ||
1556                                 std::is_same_v<T, common_peg_ac_parser> ||
1557                                 std::is_same_v<T, common_peg_schema_parser>) {
1558                visit(p.child);
1559            } else if constexpr (std::is_same_v<T, common_peg_rule_parser>) {
1560                if (visited.find(p.name) == visited.end()) {
1561                    visited.insert(p.name);
1562                    reachable.insert(p.name);
1563                    visit(p.child);
1564                }
1565            } else if constexpr (std::is_same_v<T, common_peg_ref_parser>) {
1566                // Traverse rules so we pick up everything
1567                auto referenced_rule = arena.get_rule(p.name);
1568                visit(referenced_rule);
1569            } else {
1570                static_assert(is_always_false_v<T>);
1571            }
1572        }, parser);
1573    };
1574
1575    visit(rule);
1576    return reachable;
1577}
1578
1579// GBNF generation implementation
1580void common_peg_arena::build_grammar(const common_grammar_builder & builder, bool lazy) const {
1581    // A raw string value is parsed by the child rather than constrained by the schema
1582    auto schema_delegates = [](const common_peg_schema_parser & s) -> bool {
1583        return !s.node || (s.raw && s.node->may_be_string());
1584    };
1585
1586    // Unwrap the parser so we can properly check if it's a sequence or choice
1587    auto effective_parser = [&](common_peg_parser_id id) -> const common_peg_parser_variant & {
1588        while (true) {
1589            const auto & p = parsers_.at(id);
1590            if (const auto * tag = std::get_if<common_peg_tag_parser>(&p)) {
1591                id = tag->child;
1592            } else if (const auto * atomic = std::get_if<common_peg_atomic_parser>(&p)) {
1593                id = atomic->child;
1594            } else if (const auto * schema = std::get_if<common_peg_schema_parser>(&p)) {
1595                if (schema_delegates(*schema)) {
1596                    id = schema->child;
1597                } else {
1598                    return p;
1599                }
1600            } else {
1601                return p;
1602            }
1603        }
1604    };
1605
1606    // Generate GBNF for a parser
1607    std::function<std::string(common_peg_parser_id)> to_gbnf = [&](common_peg_parser_id id) -> std::string {
1608        const auto & parser = parsers_.at(id);
1609
1610        return std::visit([&](const auto & p) -> std::string {
1611            using T = std::decay_t<decltype(p)>;
1612
1613            if constexpr (std::is_same_v<T, common_peg_epsilon_parser> ||
1614                          std::is_same_v<T, common_peg_start_parser> ||
1615                          std::is_same_v<T, common_peg_end_parser>) {
1616                return "";
1617            } else if constexpr (std::is_same_v<T, common_peg_literal_parser>) {
1618                return gbnf_format_literal(p.literal);
1619            } else if constexpr (std::is_same_v<T, common_peg_sequence_parser>) {
1620                std::string s;
1621                for (const auto & child : p.children) {
1622                    auto child_gbnf = to_gbnf(child);
1623                    if (child_gbnf.empty()) {
1624                        continue;
1625                    }
1626                    if (!s.empty()) {
1627                        s += " ";
1628                    }
1629                    const auto & child_parser = effective_parser(child);
1630                    if (std::holds_alternative<common_peg_choice_parser>(child_parser) ||
1631                        std::holds_alternative<common_peg_sequence_parser>(child_parser)) {
1632                        s += "(" + child_gbnf + ")";
1633                    } else {
1634                        s += child_gbnf;
1635                    }
1636                }
1637                return s;
1638            } else if constexpr (std::is_same_v<T, common_peg_choice_parser>) {
1639                std::string s;
1640                for (const auto & child : p.children) {
1641                    if (!s.empty()) {
1642                        s += " | ";
1643                    }
1644                    auto child_gbnf = to_gbnf(child);
1645                    const auto & child_parser = effective_parser(child);
1646                    if (std::holds_alternative<common_peg_choice_parser>(child_parser)) {
1647                        s += "(" + child_gbnf + ")";
1648                    } else {
1649                        s += child_gbnf;
1650                    }
1651                }
1652                return s;
1653            } else if constexpr (std::is_same_v<T, common_peg_repetition_parser>) {
1654                auto child_gbnf = to_gbnf(p.child);
1655                const auto & child_parser = effective_parser(p.child);
1656                if (std::holds_alternative<common_peg_choice_parser>(child_parser) ||
1657                    std::holds_alternative<common_peg_sequence_parser>(child_parser)) {
1658                    child_gbnf = "(" + child_gbnf + ")";
1659                }
1660                if (p.min_count == 0 && p.max_count == 1) {
1661                    return child_gbnf + "?";
1662                }
1663                if (p.min_count == 0 && p.max_count == -1) {
1664                    return child_gbnf + "*";
1665                }
1666                if (p.min_count == 1 && p.max_count == -1) {
1667                    return child_gbnf + "+";
1668                }
1669                if (p.max_count == -1) {
1670                    return child_gbnf + "{" + std::to_string(p.min_count) + ",}";
1671                }
1672                if (p.min_count == p.max_count) {
1673                    if (p.min_count == 1) {
1674                        return child_gbnf;
1675                    }
1676                    return child_gbnf + "{" + std::to_string(p.min_count) + "}";
1677                }
1678                return child_gbnf + "{" + std::to_string(p.min_count) + "," + std::to_string(p.max_count) + "}";
1679            } else if constexpr (std::is_same_v<T, common_peg_and_parser> || std::is_same_v<T, common_peg_not_parser>) {
1680                return "";  // Lookahead not supported in GBNF
1681            } else if constexpr (std::is_same_v<T, common_peg_any_parser>) {
1682                return ".";
1683            } else if constexpr (std::is_same_v<T, common_peg_space_parser>) {
1684                return "space";
1685            } else if constexpr (std::is_same_v<T, common_peg_chars_parser>) {
1686                std::string result = p.pattern;
1687                if (p.min_count == 0 && p.max_count == 1) {
1688                    return result + "?";
1689                }
1690                if (p.min_count == 0 && p.max_count == -1) {
1691                    return result + "*";
1692                }
1693                if (p.min_count == 1 && p.max_count == -1) {
1694                    return result + "+";
1695                }
1696                if (p.max_count == -1) {
1697                    return result + "{" + std::to_string(p.min_count) + ",}";
1698                }
1699                if (p.min_count == p.max_count) {
1700                    if (p.min_count == 1) {
1701                        return result;
1702                    }
1703                    return result + "{" + std::to_string(p.min_count) + "}";
1704                }
1705                return result + "{" + std::to_string(p.min_count) + "," + std::to_string(p.max_count) + "}";
1706            } else if constexpr (std::is_same_v<T, common_peg_string_parser>) {
1707                const std::string delim(1, p.delimiter);
1708                return R"(( [^)" + delim + R"(\\] | "\\" ( [)" + delim + R"(\\/ bfnrt] | "u" [0-9a-fA-F]{4} ) )*)";
1709            } else if constexpr (std::is_same_v<T, common_peg_until_parser>) {
1710                if (p.delimiters.empty()) {
1711                    return ".*";
1712                }
1713                return gbnf_excluding_grammar(builder, "until-" + std::to_string(id), p.delimiters);
1714            } else if constexpr (std::is_same_v<T, common_peg_schema_parser>) {
1715                if (schema_delegates(p)) {
1716                    return to_gbnf(p.child);
1717                }
1718                return builder.add_schema(p.name, *p.node);
1719            } else if constexpr (std::is_same_v<T, common_peg_rule_parser>) {
1720                return p.name;
1721            } else if constexpr (std::is_same_v<T, common_peg_ref_parser>) {
1722                // Refs should not exist after flattening, but kept just in case
1723                return p.name;
1724            } else if constexpr (std::is_same_v<T, common_peg_tag_parser>) {
1725                return to_gbnf(p.child);
1726            } else if constexpr (std::is_same_v<T, common_peg_atomic_parser>) {
1727                return to_gbnf(p.child);
1728            } else if constexpr (std::is_same_v<T, common_peg_gbnf_parser>) {
1729                return p.grammar;
1730            } else if constexpr (std::is_same_v<T, common_peg_ac_parser>) {
1731                return gbnf_including_grammar(builder, "ac-" + std::to_string(id), p.delimiters);
1732            } else {
1733                static_assert(is_always_false_v<T>);
1734            }
1735        }, parser);
1736    };
1737
1738    // Collect reachable rules
1739    std::set<std::string> reachable_rules;
1740
1741    if (lazy) {
1742        // Collect rules reachable from trigger rules
1743        for (const auto & [name, id] : rules_) {
1744            const auto & parser = parsers_.at(id);
1745            if (auto rule = std::get_if<common_peg_rule_parser>(&parser)) {
1746                if (rule->trigger) {
1747                    // Mark trigger as reachable and visit it
1748                    reachable_rules.insert(name);
1749                    auto add_rules = collect_reachable_rules(*this, id);
1750                    reachable_rules.insert(add_rules.begin(), add_rules.end());
1751                }
1752            }
1753        }
1754    } else {
1755        // Collect rules reachable from root
1756        reachable_rules = collect_reachable_rules(*this, root_);
1757    }
1758
1759    // Create GBNF rules for all reachable rules
1760    for (const auto & [name, rule_id] : rules_) {
1761        if (reachable_rules.find(name) == reachable_rules.end()) {
1762            continue;
1763        }
1764
1765        const auto & parser = parsers_.at(rule_id);
1766        if (auto rule = std::get_if<common_peg_rule_parser>(&parser)) {
1767            builder.add_rule(rule->name, to_gbnf(rule->child));
1768        }
1769    }
1770
1771    if (lazy) {
1772        // Generate root rule from trigger rules only
1773        std::vector<std::string> trigger_names;
1774        for (const auto & [name, rule_id] : rules_) {
1775            const auto & parser = parsers_.at(rule_id);
1776            if (auto rule = std::get_if<common_peg_rule_parser>(&parser)) {
1777                if (rule->trigger) {
1778                    trigger_names.push_back(rule->name);
1779                }
1780            }
1781        }
1782
1783        // Sort for predictable order
1784        std::sort(trigger_names.begin(), trigger_names.end());
1785        builder.add_rule("root", string_join(trigger_names, " | "));
1786    } else if (root_ != COMMON_PEG_INVALID_PARSER_ID) {
1787        builder.add_rule("root", to_gbnf(root_));
1788    }
1789}
1790
1791static common_json serialize_parser_variant(const common_peg_parser_variant & variant) {
1792    using json = common_json;
1793
1794    return std::visit([](const auto & p) -> json {
1795        using T = std::decay_t<decltype(p)>;
1796
1797        if constexpr (std::is_same_v<T, common_peg_epsilon_parser>) {
1798            return json{{"type", "epsilon"}};
1799        } else if constexpr (std::is_same_v<T, common_peg_start_parser>) {
1800            return json{{"type", "start"}};
1801        } else if constexpr (std::is_same_v<T, common_peg_end_parser>) {
1802            return json{{"type", "end"}};
1803        } else if constexpr (std::is_same_v<T, common_peg_literal_parser>) {
1804            return json{{"type", "literal"}, {"literal", p.literal}};
1805        } else if constexpr (std::is_same_v<T, common_peg_sequence_parser>) {
1806            return json{{"type", "sequence"}, {"children", p.children}};
1807        } else if constexpr (std::is_same_v<T, common_peg_choice_parser>) {
1808            return json{{"type", "choice"}, {"children", p.children}};
1809        } else if constexpr (std::is_same_v<T, common_peg_repetition_parser>) {
1810            return json{
1811                {"type", "repetition"},
1812                {"child", p.child},
1813                {"min_count", p.min_count},
1814                {"max_count", p.max_count}
1815            };
1816        } else if constexpr (std::is_same_v<T, common_peg_and_parser>) {
1817            return json{{"type", "and"}, {"child", p.child}};
1818        } else if constexpr (std::is_same_v<T, common_peg_not_parser>) {
1819            return json{{"type", "not"}, {"child", p.child}};
1820        } else if constexpr (std::is_same_v<T, common_peg_any_parser>) {
1821            return json{{"type", "any"}};
1822        } else if constexpr (std::is_same_v<T, common_peg_space_parser>) {
1823            return json{{"type", "space"}};
1824        } else if constexpr (std::is_same_v<T, common_peg_chars_parser>) {
1825            json ranges = json::array();
1826            for (const auto & range : p.ranges) {
1827                ranges.push_back({{"start", range.start}, {"end", range.end}});
1828            }
1829            return json{
1830                {"type", "chars"},
1831                {"pattern", p.pattern},
1832                {"ranges", ranges},
1833                {"negated", p.negated},
1834                {"min_count", p.min_count},
1835                {"max_count", p.max_count}
1836            };
1837        } else if constexpr (std::is_same_v<T, common_peg_string_parser>) {
1838            return json{{"type", "string"}, {"delimiter", std::string(1, p.delimiter)}};
1839        } else if constexpr (std::is_same_v<T, common_peg_until_parser>) {
1840            return json{{"type", "until"}, {"delimiters", p.delimiters}};
1841        } else if constexpr (std::is_same_v<T, common_peg_schema_parser>) {
1842            return json{
1843                {"type", "schema"},
1844                {"child", p.child},
1845                {"name", p.name},
1846                {"raw", p.raw}
1847            };
1848        } else if constexpr (std::is_same_v<T, common_peg_rule_parser>) {
1849            return json{
1850                {"type", "rule"},
1851                {"name", p.name},
1852                {"child", p.child},
1853                {"trigger", p.trigger}
1854            };
1855        } else if constexpr (std::is_same_v<T, common_peg_ref_parser>) {
1856            return json{{"type", "ref"}, {"name", p.name}};
1857        } else if constexpr (std::is_same_v<T, common_peg_atomic_parser>) {
1858            return json{{"type", "atomic"}, {"child", p.child}};
1859        } else if constexpr (std::is_same_v<T, common_peg_tag_parser>) {
1860            return json{
1861                {"type", "tag"},
1862                {"child", p.child},
1863                {"tag", p.tag}
1864            };
1865        } else if constexpr (std::is_same_v<T, common_peg_gbnf_parser>) {
1866            return json{{"type", "gbnf"}, {"child", p.child}, {"grammar", p.grammar}};
1867        } else if constexpr (std::is_same_v<T, common_peg_ac_parser>) {
1868            return json{{"type", "ac"}, {"child", p.child}, {"delimiters", p.delimiters}};
1869        }
1870    }, variant);
1871}
1872
1873common_json common_peg_arena::to_json() const {
1874    auto parsers = common_json::array();
1875    for (const auto & parser : parsers_) {
1876        parsers.push_back(serialize_parser_variant(parser));
1877    }
1878    return common_json{
1879        {"parsers", parsers},
1880        {"rules", rules_},
1881        {"root", root_}
1882    };
1883}
1884
1885static common_peg_parser_variant deserialize_parser_variant(const common_json & j) {
1886    if (!j.contains("type") || !j["type"].is_string()) {
1887        throw std::runtime_error("Parser variant JSON missing or invalid 'type' field");
1888    }
1889
1890    std::string type = j["type"];
1891
1892    if (type == "epsilon") {
1893        return common_peg_epsilon_parser{};
1894    }
1895    if (type == "start") {
1896        return common_peg_start_parser{};
1897    }
1898    if (type == "end") {
1899        return common_peg_end_parser{};
1900    }
1901    if (type == "literal") {
1902        if (!j.contains("literal") || !j["literal"].is_string()) {
1903            throw std::runtime_error("literal parser missing or invalid 'literal' field");
1904        }
1905        return common_peg_literal_parser{j["literal"]};
1906    }
1907    if (type == "sequence") {
1908        if (!j.contains("children") || !j["children"].is_array()) {
1909            throw std::runtime_error("sequence parser missing or invalid 'children' field");
1910        }
1911        return common_peg_sequence_parser{j["children"].get<std::vector<common_peg_parser_id>>()};
1912    }
1913    if (type == "choice") {
1914        if (!j.contains("children") || !j["children"].is_array()) {
1915            throw std::runtime_error("choice parser missing or invalid 'children' field");
1916        }
1917        return common_peg_choice_parser{j["children"].get<std::vector<common_peg_parser_id>>()};
1918    }
1919    if (type == "repetition") {
1920        if (!j.contains("child") || !j.contains("min_count") || !j.contains("max_count")) {
1921            throw std::runtime_error("repetition parser missing required fields");
1922        }
1923        return common_peg_repetition_parser{
1924            j["child"].get<common_peg_parser_id>(),
1925            j["min_count"].get<int>(),
1926            j["max_count"].get<int>()
1927        };
1928    }
1929    if (type == "and") {
1930        if (!j.contains("child")) {
1931            throw std::runtime_error("and parser missing 'child' field");
1932        }
1933        return common_peg_and_parser{j["child"].get<common_peg_parser_id>()};
1934    }
1935    if (type == "not") {
1936        if (!j.contains("child")) {
1937            throw std::runtime_error("not parser missing 'child' field");
1938        }
1939        return common_peg_not_parser{j["child"].get<common_peg_parser_id>()};
1940    }
1941    if (type == "any") {
1942        return common_peg_any_parser{};
1943    }
1944    if (type == "space") {
1945        return common_peg_space_parser{};
1946    }
1947    if (type == "chars") {
1948        if (!j.contains("pattern") || !j.contains("ranges") || !j.contains("negated") ||
1949            !j.contains("min_count") || !j.contains("max_count")) {
1950            throw std::runtime_error("chars parser missing required fields");
1951        }
1952        common_peg_chars_parser parser;
1953        parser.pattern = j["pattern"];
1954        parser.negated = j["negated"].get<bool>();
1955        parser.min_count = j["min_count"].get<int>();
1956        parser.max_count = j["max_count"].get<int>();
1957        for (const auto & range_json : j["ranges"]) {
1958            if (!range_json.contains("start") || !range_json.contains("end")) {
1959                throw std::runtime_error("char_range missing 'start' or 'end' field");
1960            }
1961            parser.ranges.push_back({
1962                range_json["start"].get<uint32_t>(),
1963                range_json["end"].get<uint32_t>()
1964            });
1965        }
1966        return parser;
1967    }
1968    if (type == "string") {
1969        if (!j.contains("delimiter")) {
1970            throw std::runtime_error("string parser missing delimiter field.");
1971        }
1972        std::string delimiter = j["delimiter"];
1973        if (delimiter.empty()) {
1974            throw std::runtime_error("string parser delimiter is empty.");
1975        }
1976        return common_peg_string_parser{delimiter[0]};
1977    }
1978    if (type == "until") {
1979        if (!j.contains("delimiters") || !j["delimiters"].is_array()) {
1980            throw std::runtime_error("until parser missing or invalid 'delimiters' field");
1981        }
1982        return common_peg_until_parser{j["delimiters"].get<std::vector<std::string>>()};
1983    }
1984    if (type == "schema") {
1985        if (!j.contains("child") || !j.contains("name") || !j.contains("raw")) {
1986            throw std::runtime_error("schema parser missing required fields");
1987        }
1988        common_peg_schema_parser parser;
1989        parser.child = j["child"].get<common_peg_parser_id>();
1990        parser.name = j["name"];
1991        parser.raw = j["raw"].get<bool>();
1992        return parser;
1993    }
1994    if (type == "rule") {
1995        if (!j.contains("name") || !j.contains("child") || !j.contains("trigger")) {
1996            throw std::runtime_error("rule parser missing required fields");
1997        }
1998        return common_peg_rule_parser{
1999            j["name"].get<std::string>(),
2000            j["child"].get<common_peg_parser_id>(),
2001            j["trigger"].get<bool>()
2002        };
2003    }
2004    if (type == "ref") {
2005        if (!j.contains("name") || !j["name"].is_string()) {
2006            throw std::runtime_error("ref parser missing or invalid 'name' field");
2007        }
2008        return common_peg_ref_parser{j["name"]};
2009    }
2010    if (type == "atomic") {
2011        if (!j.contains("child")) {
2012            throw std::runtime_error("tag parser missing required fields");
2013        }
2014        return common_peg_atomic_parser{
2015            j["child"].get<common_peg_parser_id>(),
2016        };
2017    }
2018    if (type == "tag") {
2019        if (!j.contains("child") || !j.contains("tag")) {
2020            throw std::runtime_error("tag parser missing required fields");
2021        }
2022        return common_peg_tag_parser{
2023            j["child"].get<common_peg_parser_id>(),
2024            j["tag"].get<std::string>(),
2025        };
2026    }
2027
2028    if (type == "gbnf") {
2029        if (!j.contains("child") || !j.contains("grammar")) {
2030            throw std::runtime_error("gbnf parser missing required fields");
2031        }
2032        return common_peg_gbnf_parser{
2033            j["child"].get<common_peg_parser_id>(),
2034            j["grammar"].get<std::string>(),
2035        };
2036    }
2037
2038    if (type == "ac") {
2039        if (!j.contains("child") || !j.contains("delimiters") || !j["delimiters"].is_array() || j["delimiters"].empty()) {
2040            throw std::runtime_error("ac parser requires 'child' and a non-empty 'delimiters' array");
2041        }
2042        return common_peg_ac_parser{
2043            j["child"].get<common_peg_parser_id>(),
2044            j["delimiters"].get<std::vector<std::string>>(),
2045        };
2046    }
2047
2048    throw std::runtime_error("Unknown parser type: " + type);
2049}
2050
2051common_peg_arena common_peg_arena::from_json(const common_json & j) {
2052    if (!j.contains("parsers") || !j["parsers"].is_array()) {
2053        throw std::runtime_error("JSON missing or invalid 'parsers' array");
2054    }
2055    if (!j.contains("rules") || !j["rules"].is_object()) {
2056        throw std::runtime_error("JSON missing or invalid 'rules' object");
2057    }
2058    if (!j.contains("root")) {
2059        throw std::runtime_error("JSON missing 'root' field");
2060    }
2061
2062    common_peg_arena arena;
2063
2064    const auto & parsers_json = j["parsers"];
2065    arena.parsers_.reserve(parsers_json.size());
2066    for (const auto & parser_json : parsers_json) {
2067        arena.parsers_.push_back(deserialize_parser_variant(parser_json));
2068    }
2069
2070    arena.rules_ = j["rules"].get<std::unordered_map<std::string, common_peg_parser_id>>();
2071
2072    for (const auto & [name, id] : arena.rules_) {
2073        if (id >= arena.parsers_.size()) {
2074            throw std::runtime_error("Rule '" + name + "' references invalid parser ID: " + std::to_string(id));
2075        }
2076    }
2077
2078    arena.root_ = j["root"].get<common_peg_parser_id>();
2079    if (arena.root_ != COMMON_PEG_INVALID_PARSER_ID && arena.root_ >= arena.parsers_.size()) {
2080        throw std::runtime_error("Root references invalid parser ID: " + std::to_string(arena.root_));
2081    }
2082
2083    return arena;
2084}
2085
2086std::string common_peg_arena::save() const {
2087    return to_json().dump();
2088}
2089
2090void common_peg_arena::load(const std::string & data) {
2091    *this = from_json(common_json::parse(data));
2092}
2093
2094common_peg_arena build_peg_parser(const std::function<common_peg_parser(common_peg_parser_builder & builder)> & fn) {
2095    common_peg_parser_builder builder;
2096    builder.set_root(fn(builder));
2097    return builder.build();
2098}