Felipe97/llama-cpp-compiled
01.1k
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 branches18template <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 codepoint97 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 negation114 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 detected126 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 display222 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_pos248 );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_pos255 );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 matches393 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 trying423 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 matches430 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 input457 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 matches465 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 negating470 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos);471 }472 473 // Child failed, so negation succeeds474 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 have518 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);519 }520 // Not enough matches yet521 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 input529 if (match_count >= p.min_count) {530 // We have enough matches, succeed up to here531 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);532 }533 // Not enough matches, fail534 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);535 }536 537 // Check if this codepoint matches our character class538 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 result547 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 matching556 break;557 }558 }559 560 // Check if we got enough matches561 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 sequence594 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 quote655 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 delimiters665 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 sequence673 if (!ctx.is_lenient()) {674 // Input is complete but UTF-8 is incomplete = malformed675 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-8683 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);684 }685 686 // Check if a delimiter starts at this position687 auto match = matcher.check_at(ctx.input, pos);688 689 if (match == common_trie::COMPLETE_MATCH) {690 // Found a complete delimiter, return everything before it691 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 it696 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 child716 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 child742 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 parser801 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 IDs841 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 children876 } else {877 static_assert(is_always_false_v<T>);878 }879 }, parser);880 }881 882 // Also flatten root if it's a ref883 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 cycles896 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 sequences1055 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 choices1087 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 references1145 auto placeholder = any(); // Temporary placeholder1146 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 parser1150 auto parser = builder_fn();1151 1152 // Replace placeholder with actual rule1153 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 primitives1169 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 parsers1193 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});