Brunobkr/llama.cpp_AlgMor24_github
ΩFFFΣLLIa • llama.cpp • AlgMor24 ██████╗ ███████╗███████╗███████╗██╗ ██╗ ██╗ █████╗ ██╔═══██╗██╔════╝██╔════╝██╔════╝██║ ██║ ██║██╔══██╗ ██║ ██║█████╗ █████╗ █████╗ ██║ ██║ ██║███████║ ██║ ██║██╔══╝ ██╔══╝ ██╔══╝ ██║ ██║ ██║██╔══██║ ╚██████╔╝██║ ██║ ███████╗███████╗███████╗██║██║ ██║ ╚═════╝ ╚═╝ ╚═╝ ╚══════╝╚══════╝╚══════╝╚═╝╚═╝ ╚═╝ High-Performance LLM / VLM Inference & Autonomous Agentic Ecosystem… See the full description on the dataset page: https://huggingface.co/datasets/Brunobkr/llama.cpp_AlgMor24_github.
03k
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 <nlohmann/json.hpp>14#include <regex>15#include <set>16#include <stdexcept>17 18// Trick to catch missing branches19template <typename T>20inline constexpr bool is_always_false_v = false;21 22const char * common_peg_parse_result_type_name(common_peg_parse_result_type type) {23 switch (type) {24 case COMMON_PEG_PARSE_RESULT_FAIL: return "fail";25 case COMMON_PEG_PARSE_RESULT_SUCCESS: return "success";26 case COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT: return "need_more_input";27 default: return "unknown";28 }29}30 31static bool is_hex_digit(const char c) {32 return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F');33}34 35static std::pair<uint32_t, size_t> parse_hex_escape(const std::string & str, size_t pos, int hex_count) {36 if (pos + hex_count > str.length()) {37 return {0, 0};38 }39 40 uint32_t value = 0;41 for (int i = 0; i < hex_count; i++) {42 char c = str[pos + i];43 if (!is_hex_digit(c)) {44 return {0, 0};45 }46 value <<= 4;47 if ('a' <= c && c <= 'f') {48 value += c - 'a' + 10;49 } else if ('A' <= c && c <= 'F') {50 value += c - 'A' + 10;51 } else if ('0' <= c && c <= '9') {52 value += c - '0';53 } else {54 break;55 }56 }57 return {value, static_cast<size_t>(hex_count)};58}59 60static std::pair<uint32_t, size_t> parse_char_class_char(const std::string & content, size_t pos) {61 if (content[pos] == '\\' && pos + 1 < content.length()) {62 switch (content[pos + 1]) {63 case 'x': {64 auto result = parse_hex_escape(content, pos + 2, 2);65 if (result.second > 0) {66 return {result.first, 2 + result.second};67 }68 // Invalid escape, treat as literal 'x'69 return {static_cast<uint32_t>('x'), 2};70 }71 case 'u': {72 auto result = parse_hex_escape(content, pos + 2, 4);73 if (result.second > 0) {74 return {result.first, 2 + result.second};75 }76 // Invalid escape, treat as literal 'u'77 return {static_cast<uint32_t>('u'), 2};78 }79 case 'U': {80 auto result = parse_hex_escape(content, pos + 2, 8);81 if (result.second > 0) {82 return {result.first, 2 + result.second};83 }84 // Invalid escape, treat as literal 'U'85 return {static_cast<uint32_t>('U'), 2};86 }87 case 'n': return {'\n', 2};88 case 't': return {'\t', 2};89 case 'r': return {'\r', 2};90 case '\\': return {'\\', 2};91 case ']': return {']', 2};92 case '[': return {'[', 2};93 default: return {static_cast<uint32_t>(content[pos + 1]), 2};94 }95 }96 97 // Regular character - return as codepoint98 return {static_cast<uint32_t>(static_cast<unsigned char>(content[pos])), 1};99}100 101static std::pair<std::vector<common_peg_chars_parser::char_range>, bool> parse_char_classes(const std::string & classes) {102 std::vector<common_peg_chars_parser::char_range> ranges;103 bool negated = false;104 105 std::string content = classes;106 if (content.front() == '[') {107 content = content.substr(1);108 }109 110 if (content.back() == ']') {111 content.pop_back();112 }113 114 // Check for negation115 if (!content.empty() && content.front() == '^') {116 negated = true;117 content = content.substr(1);118 }119 120 size_t i = 0;121 while (i < content.length()) {122 auto [start, start_len] = parse_char_class_char(content, i);123 i += start_len;124 125 if (i + 1 < content.length() && content[i] == '-') {126 // Range detected127 auto [end, end_len] = parse_char_class_char(content, i + 1);128 ranges.push_back(common_peg_chars_parser::char_range{start, end});129 i += 1 + end_len;130 } else {131 ranges.push_back(common_peg_chars_parser::char_range{start, start});132 }133 }134 135 return {ranges, negated};136}137 138common_peg_ast_id common_peg_ast_arena::find_by_tag(const common_peg_ast_node & parent, const std::string & tag, int max_depth) const {139 for (auto child_id : parent.children) {140 const auto & child = get(child_id);141 if (child.tag == tag) {142 return child_id;143 }144 if (max_depth > 1) {145 auto result = find_by_tag(child, tag, max_depth - 1);146 if (result != COMMON_PEG_INVALID_AST_ID) {147 return result;148 }149 }150 }151 return COMMON_PEG_INVALID_AST_ID;152}153 154common_peg_ast_id common_peg_ast_arena::find_by_rule(const common_peg_ast_node & parent, const std::string & rule, int max_depth) const {155 for (auto child_id : parent.children) {156 const auto & child = get(child_id);157 if (child.rule == rule) {158 return child_id;159 }160 if (max_depth > 1) {161 auto result = find_by_rule(child, rule, max_depth - 1);162 if (result != COMMON_PEG_INVALID_AST_ID) {163 return result;164 }165 }166 }167 return COMMON_PEG_INVALID_AST_ID;168}169 170void common_peg_ast_arena::visit(common_peg_ast_id id, const common_peg_ast_visitor & visitor) const {171 if (id == COMMON_PEG_INVALID_AST_ID) {172 return;173 }174 const auto & node = get(id);175 visitor(node);176 for (const auto & child : node.children) {177 visit(child, visitor);178 }179}180 181void common_peg_ast_arena::visit(const common_peg_parse_result & result, const common_peg_ast_visitor & visitor) const {182 for (const auto & node : result.nodes) {183 visit(node, visitor);184 }185}186 187struct parser_executor;188 189common_peg_parser_id common_peg_arena::add_parser(common_peg_parser_variant parser) {190 common_peg_parser_id id = parsers_.size();191 parsers_.push_back(std::move(parser));192 return id;193}194 195void common_peg_arena::add_rule(const std::string & name, common_peg_parser_id id) {196 rules_[name] = id;197}198 199common_peg_parser_id common_peg_arena::get_rule(const std::string & name) const {200 auto it = rules_.find(name);201 if (it == rules_.end()) {202 throw std::runtime_error("Rule not found: " + name);203 }204 return it->second;205}206 207struct parser_executor {208 const common_peg_arena & arena;209 common_peg_parse_context & ctx;210 size_t start_pos;211 212 parser_executor(const common_peg_arena & arena, common_peg_parse_context & ctx, size_t start)213 : arena(arena), ctx(ctx), start_pos(start) {}214 215 std::string debug_indent() const { return std::string(ctx.parse_depth * 2, ' '); }216 217 std::string debug_input_snippet(size_t pos, size_t len = 60) const {218 if (pos >= ctx.input.size()) {219 return "<EOF>";220 }221 auto snippet = ctx.input.substr(pos, len);222 // Escape newlines for display223 std::string result;224 for (char c : snippet) {225 if (c == '\n') {226 result += "\\n";227 } else if (c == '\r') {228 result += "\\r";229 } else if (c == '\t') {230 result += "\\t";231 } else {232 result += c;233 }234 }235 if (pos + len < ctx.input.size()) {236 result += "...";237 }238 return result;239 }240 241 common_peg_parse_result operator()(const common_peg_epsilon_parser & /* p */) const {242 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos);243 }244 245 common_peg_parse_result operator()(const common_peg_start_parser & /* p */) const {246 return common_peg_parse_result(247 start_pos == 0 ? COMMON_PEG_PARSE_RESULT_SUCCESS : COMMON_PEG_PARSE_RESULT_FAIL,248 start_pos249 );250 }251 252 common_peg_parse_result operator()(const common_peg_end_parser & /* p */) const {253 return common_peg_parse_result(254 start_pos >= ctx.input.size() ? COMMON_PEG_PARSE_RESULT_SUCCESS : COMMON_PEG_PARSE_RESULT_FAIL,255 start_pos256 );257 }258 259 common_peg_parse_result operator()(const common_peg_literal_parser & p) {260 auto pos = start_pos;261 for (auto i = 0u; i < p.literal.size(); ++i) {262 if (pos >= ctx.input.size()) {263 if (!ctx.is_lenient()) {264 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);265 }266 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);267 }268 if (ctx.input[pos] != p.literal[i]) {269 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);270 }271 ++pos;272 }273 274 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);275 }276 277 common_peg_parse_result operator()(const common_peg_sequence_parser & p) {278 if (ctx.is_debug()) {279 LOG_DBG("%sSEQ start at %zu '%s' (%zu children)\n", debug_indent().c_str(), start_pos,280 debug_input_snippet(start_pos).c_str(), p.children.size());281 }282 ctx.parse_depth++;283 284 auto pos = start_pos;285 std::vector<common_peg_ast_id> nodes;286 287 for (size_t i = 0; i < p.children.size(); i++) {288 const auto & child_id = p.children[i];289 if (ctx.is_debug()) {290 fprintf(stderr, "%sSEQ child %zu: %s\n", debug_indent().c_str(), i, arena.dump(child_id).c_str());291 }292 auto result = arena.parse(child_id, ctx, pos);293 294 if (ctx.is_debug()) {295 fprintf(stderr, "%sSEQ child %zu: %s at %zu->%zu\n", debug_indent().c_str(), i,296 common_peg_parse_result_type_name(result.type), result.start, result.end);297 }298 299 if (result.fail()) {300 ctx.parse_depth--;301 if (ctx.is_debug()) {302 fprintf(stderr, "%sSEQ -> FAIL\n", debug_indent().c_str());303 }304 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos, result.end);305 }306 307 if (!result.nodes.empty()) {308 nodes.insert(nodes.end(), result.nodes.begin(), result.nodes.end());309 }310 311 if (result.need_more_input()) {312 ctx.parse_depth--;313 if (ctx.is_debug()) {314 fprintf(stderr, "%sSEQ -> NEED_MORE\n", debug_indent().c_str());315 }316 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, result.end, std::move(nodes));317 }318 319 pos = result.end;320 }321 322 ctx.parse_depth--;323 if (ctx.is_debug()) {324 fprintf(stderr, "%sSEQ -> SUCCESS at %zu->%zu\n", debug_indent().c_str(), start_pos, pos);325 }326 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos, std::move(nodes));327 }328 329 common_peg_parse_result operator()(const common_peg_choice_parser & p) {330 if (ctx.is_debug()) {331 fprintf(stderr, "%sCHOICE start at %zu '%s' (%zu options)\n", debug_indent().c_str(), start_pos,332 debug_input_snippet(start_pos).c_str(), p.children.size());333 }334 ctx.parse_depth++;335 336 auto pos = start_pos;337 for (size_t i = 0; i < p.children.size(); i++) {338 const auto & child_id = p.children[i];339 if (ctx.is_debug()) {340 fprintf(stderr, "%sCHOICE option %zu: %s\n", debug_indent().c_str(), i, arena.dump(child_id).c_str());341 }342 auto result = arena.parse(child_id, ctx, pos);343 if (ctx.is_debug()) {344 fprintf(stderr, "%sCHOICE option %zu: %s\n", debug_indent().c_str(), i,345 common_peg_parse_result_type_name(result.type));346 }347 if (!result.fail()) {348 ctx.parse_depth--;349 if (ctx.is_debug()) {350 fprintf(stderr, "%sCHOICE -> %s (option %zu)\n", debug_indent().c_str(),351 common_peg_parse_result_type_name(result.type), i);352 }353 return result;354 }355 }356 357 ctx.parse_depth--;358 if (ctx.is_debug()) {359 fprintf(stderr, "%sCHOICE -> FAIL (no options matched)\n", debug_indent().c_str());360 }361 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);362 }363 364 common_peg_parse_result operator()(const common_peg_repetition_parser & p) {365 if (ctx.is_debug()) {366 fprintf(stderr, "%sREPEAT start at %zu '%s' (min=%d, max=%d)\n", debug_indent().c_str(), start_pos,367 debug_input_snippet(start_pos).c_str(), p.min_count, p.max_count);368 }369 ctx.parse_depth++;370 371 auto pos = start_pos;372 int match_count = 0;373 std::vector<common_peg_ast_id> nodes;374 375 // Try to match up to max_count times (or unlimited if max_count is -1)376 while (p.max_count == -1 || match_count < p.max_count) {377 if (pos >= ctx.input.size()) {378 if (ctx.is_debug()) {379 fprintf(stderr, "%sREPEAT: at end of input, count=%d\n", debug_indent().c_str(), match_count);380 }381 break;382 }383 384 auto result = arena.parse(p.child, ctx, pos);385 386 if (ctx.is_debug()) {387 fprintf(stderr, "%sREPEAT iter %d: %s at %zu->%zu, nodes=%zu\n", debug_indent().c_str(), match_count,388 common_peg_parse_result_type_name(result.type), result.start, result.end, result.nodes.size());389 fprintf(stderr, "%sREPEAT CHILD: %s\n", debug_indent().c_str(), arena.dump(p.child).c_str());390 }391 392 if (result.success()) {393 // Prevent infinite loop on empty matches394 if (result.end == pos) {395 if (ctx.is_debug()) {396 fprintf(stderr, "%s REPEAT: empty match, stopping\n", debug_indent().c_str());397 }398 break;399 }400 401 if (!result.nodes.empty()) {402 nodes.insert(nodes.end(), result.nodes.begin(), result.nodes.end());403 }404 405 pos = result.end;406 match_count++;407 continue;408 }409 410 if (result.need_more_input()) {411 if (!result.nodes.empty()) {412 nodes.insert(nodes.end(), result.nodes.begin(), result.nodes.end());413 }414 415 ctx.parse_depth--;416 if (ctx.is_debug()) {417 fprintf(stderr, "%sREPEAT -> NEED_MORE (count=%d, nodes=%zu)\n", debug_indent().c_str(),418 match_count, nodes.size());419 }420 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, result.end, std::move(nodes));421 }422 423 // Child failed - stop trying424 if (ctx.is_debug()) {425 fprintf(stderr, "%sREPEAT: child failed, stopping\n", debug_indent().c_str());426 }427 break;428 }429 430 // Check if we got enough matches431 if (p.min_count > 0 && match_count < p.min_count) {432 ctx.parse_depth--;433 if (pos >= ctx.input.size() && ctx.is_lenient()) {434 if (ctx.is_debug()) {435 fprintf(stderr, "%sREPEAT -> NEED_MORE (not enough matches: %d < %d)\n", debug_indent().c_str(),436 match_count, p.min_count);437 }438 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos, std::move(nodes));439 }440 if (ctx.is_debug()) {441 fprintf(stderr, "%sREPEAT -> FAIL (not enough matches: %d < %d)\n", debug_indent().c_str(), match_count,442 p.min_count);443 }444 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos, pos);445 }446 447 ctx.parse_depth--;448 if (ctx.is_debug()) {449 fprintf(stderr, "%sREPEAT -> SUCCESS (count=%d, nodes=%zu)\n", debug_indent().c_str(), match_count,450 nodes.size());451 }452 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos, std::move(nodes));453 }454 455 common_peg_parse_result operator()(const common_peg_and_parser & p) {456 auto result = arena.parse(p.child, ctx, start_pos);457 // Pass result but don't consume input458 return common_peg_parse_result(result.type, start_pos);459 }460 461 common_peg_parse_result operator()(const common_peg_not_parser & p) {462 auto result = arena.parse(p.child, ctx, start_pos);463 464 if (result.success()) {465 // Fail if the underlying parser matches466 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);467 }468 469 if (result.need_more_input()) {470 // Propagate - need to know what child would match before negating471 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos);472 }473 474 // Child failed, so negation succeeds475 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos);476 }477 478 common_peg_parse_result operator()(const common_peg_any_parser & /* p */) const {479 // Parse a single UTF-8 codepoint (not just a single byte)480 auto result = common_parse_utf8_codepoint(ctx.input, start_pos);481 482 if (result.status == utf8_parse_result::INCOMPLETE) {483 if (!ctx.is_lenient()) {484 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);485 }486 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos);487 }488 if (result.status == utf8_parse_result::INVALID) {489 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);490 }491 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, start_pos + result.bytes_consumed);492 }493 494 common_peg_parse_result operator()(const common_peg_space_parser & /* p */) {495 auto pos = start_pos;496 while (pos < ctx.input.size()) {497 auto c = static_cast<unsigned char>(ctx.input[pos]);498 if (std::isspace(c)) {499 ++pos;500 } else {501 break;502 }503 }504 505 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);506 }507 508 common_peg_parse_result operator()(const common_peg_chars_parser & p) const {509 auto pos = start_pos;510 int match_count = 0;511 512 // Try to match up to max_count times (or unlimited if max_count is -1)513 while (p.max_count == -1 || match_count < p.max_count) {514 auto result = common_parse_utf8_codepoint(ctx.input, pos);515 516 if (result.status == utf8_parse_result::INCOMPLETE) {517 if (match_count >= p.min_count) {518 // We have enough matches, succeed with what we have519 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);520 }521 // Not enough matches yet522 if (!ctx.is_lenient()) {523 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);524 }525 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);526 }527 528 if (result.status == utf8_parse_result::INVALID) {529 // Malformed UTF-8 in input530 if (match_count >= p.min_count) {531 // We have enough matches, succeed up to here532 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);533 }534 // Not enough matches, fail535 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);536 }537 538 // Check if this codepoint matches our character class539 bool matches = false;540 for (const auto & range : p.ranges) {541 if (range.contains(result.codepoint)) {542 matches = true;543 break;544 }545 }546 547 // If negated, invert the match result548 if (p.negated) {549 matches = !matches;550 }551 552 if (matches) {553 pos += result.bytes_consumed;554 ++match_count;555 } else {556 // Character doesn't match, stop matching557 break;558 }559 }560 561 // Check if we got enough matches562 if (match_count < p.min_count) {563 if (pos >= ctx.input.size() && ctx.is_lenient()) {564 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);565 }566 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos, pos);567 }568 569 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);570 }571 572 static common_peg_parse_result handle_escape_sequence(common_peg_parse_context & ctx, size_t start, size_t & pos, const char delimiter) {573 ++pos; // consume '\'574 if (pos >= ctx.input.size()) {575 if (!ctx.is_lenient()) {576 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start);577 }578 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start, pos);579 }580 581 char c = ctx.input[pos];582 if (c == delimiter || c == '\\' || c == '/' || c == 'b' || c == 'f' || c == 'n' || c == 'r' || c == 't') {583 ++pos;584 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start, pos);585 } else if (c == 'u') {586 return handle_unicode_escape(ctx, start, pos);587 } else {588 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start);589 }590 }591 592 static common_peg_parse_result handle_unicode_escape(common_peg_parse_context & ctx, size_t start, size_t & pos) {593 ++pos; // consume 'u'594 for (int i = 0; i < 4; ++i) {595 if (pos >= ctx.input.size()) {596 if (!ctx.is_lenient()) {597 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start);598 }599 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start, pos);600 }601 if (!is_hex_digit(ctx.input[pos])) {602 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start);603 }604 ++pos;605 }606 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start, pos);607 }608 609 common_peg_parse_result operator()(const common_peg_string_parser & p) {610 auto pos = start_pos;611 612 // Parse string content (without quotes)613 while (pos < ctx.input.size()) {614 char c = ctx.input[pos];615 616 if (c == p.delimiter) {617 // Found closing delimiter - success (don't consume it)618 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);619 }620 621 if (c == '\\') {622 auto result = handle_escape_sequence(ctx, start_pos, pos, p.delimiter);623 if (!result.success()) {624 return result;625 }626 } else {627 auto utf8_result = common_parse_utf8_codepoint(ctx.input, pos);628 629 if (utf8_result.status == utf8_parse_result::INCOMPLETE) {630 if (!ctx.is_lenient()) {631 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);632 }633 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);634 }635 636 if (utf8_result.status == utf8_parse_result::INVALID) {637 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);638 }639 640 pos += utf8_result.bytes_consumed;641 }642 }643 644 // Reached end without finding closing quote645 if (!ctx.is_lenient()) {646 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos, pos);647 }648 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, pos);649 }650 651 common_peg_parse_result operator()(const common_peg_until_parser & p) const {652 common_trie matcher(p.delimiters);653 654 // Scan input and check for delimiters655 size_t pos = start_pos;656 size_t last_valid_pos = start_pos;657 658 while (pos < ctx.input.size()) {659 auto utf8_result = common_parse_utf8_codepoint(ctx.input, pos);660 661 if (utf8_result.status == utf8_parse_result::INCOMPLETE) {662 // Incomplete UTF-8 sequence663 if (!ctx.is_lenient()) {664 // Input is complete but UTF-8 is incomplete = malformed665 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);666 }667 // Return what we have so far (before incomplete sequence)668 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, last_valid_pos);669 }670 671 if (utf8_result.status == utf8_parse_result::INVALID) {672 // Malformed UTF-8673 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_FAIL, start_pos);674 }675 676 // Check if a delimiter starts at this position677 auto match = matcher.check_at(ctx.input, pos);678 679 if (match == common_trie::COMPLETE_MATCH) {680 // Found a complete delimiter, return everything before it681 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);682 }683 684 if (match == common_trie::PARTIAL_MATCH) {685 // Found a partial match extending to end of input, return everything before it686 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, pos);687 }688 689 pos += utf8_result.bytes_consumed;690 last_valid_pos = pos;691 }692 693 if (last_valid_pos == ctx.input.size() && ctx.is_lenient()) {694 // Reached the end of a partial stream, there might still be more input that we need to consume.695 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT, start_pos, last_valid_pos);696 }697 return common_peg_parse_result(COMMON_PEG_PARSE_RESULT_SUCCESS, start_pos, last_valid_pos);698 }699 700 common_peg_parse_result operator()(const common_peg_schema_parser & p) {701 return arena.parse(p.child, ctx, start_pos);702 }703 704 common_peg_parse_result operator()(const common_peg_rule_parser & p) {705 // Parse the child706 auto result = arena.parse(p.child, ctx, start_pos);707 708 if (!result.fail()) {709 std::string_view text;710 if (result.start < ctx.input.size()) {711 text = std::string_view(ctx.input).substr(result.start, result.end - result.start);712 }713 714 auto node_id = ctx.ast.add_node(715 p.name,716 "",717 result.start,718 result.end,719 text,720 std::move(result.nodes),721 result.need_more_input()722 );723 724 return common_peg_parse_result(result.type, result.start, result.end, { node_id });725 }726 727 return result;728 }729 730 common_peg_parse_result operator()(const common_peg_tag_parser & p) {731 // Parse the child732 if (ctx.is_debug()) {733 fprintf(stderr, "%sTAG: %s\n", debug_indent().c_str(), p.tag.c_str());734 }735 auto result = arena.parse(p.child, ctx, start_pos);736 737 if (!result.fail()) {738 std::string_view text;739 if (result.start < ctx.input.size()) {740 text = std::string_view(ctx.input).substr(result.start, result.end - result.start);741 }742 743 auto node_id = ctx.ast.add_node(744 "",745 p.tag,746 result.start,747 result.end,748 text,749 std::move(result.nodes),750 result.need_more_input()751 );752 753 return common_peg_parse_result(result.type, result.start, result.end, { node_id });754 }755 756 return result;757 }758 759 common_peg_parse_result operator()(const common_peg_ref_parser & p) {760 auto rule_id = arena.get_rule(p.name);761 return arena.parse(rule_id, ctx, start_pos);762 }763 764 common_peg_parse_result operator()(const common_peg_atomic_parser & p) {765 auto result = arena.parse(p.child, ctx, start_pos);766 if (result.need_more_input()) {767 // Clear nodes so they don't propagate up.768 result.nodes.clear();769 }770 return result;771 }772 773 common_peg_parse_result operator()(const common_peg_gbnf_parser & p) {774 return arena.parse(p.child, ctx, start_pos);775 }776 777 common_peg_parse_result operator()(const common_peg_ac_parser & p) {778 return arena.parse(p.child, ctx, start_pos);779 }780};781 782common_peg_parse_result common_peg_arena::parse(common_peg_parse_context & ctx, size_t start) const {783 if (root_ == COMMON_PEG_INVALID_PARSER_ID) {784 throw std::runtime_error("No root parser set");785 }786 return parse(root_, ctx, start);787}788 789common_peg_parse_result common_peg_arena::parse(common_peg_parser_id id, common_peg_parse_context & ctx, size_t start) const {790 // Execute parser791 const auto & parser = parsers_.at(id);792 parser_executor exec(*this, ctx, start);793 return std::visit(exec, parser);794}795 796common_peg_parser_id common_peg_arena::resolve_ref(common_peg_parser_id id) {797 const auto & parser = parsers_.at(id);798 if (auto ref = std::get_if<common_peg_ref_parser>(&parser)) {799 return get_rule(ref->name);800 }801 return id;802}803 804static void bfs_node(common_peg_ast_arena &arena, std::ostringstream & oss, const common_peg_ast_node & node, int indent) {805 for (int i = 0; i < indent; i++) {806 oss << " ";807 }808 oss << "NODE " << node.id;809 if (!node.rule.empty()) {810 oss << " (rule " << node.rule << ")";811 }812 if (!node.tag.empty()) {813 oss << " (tag " << node.tag << ")";814 }815 oss << " ['" << node.text << "']\n";816 for (const auto child : node.children) {817 bfs_node(arena, oss, arena.get(child), indent + 1);818 }819}820 821std::string common_peg_ast_arena::dump() {822 std::ostringstream oss;823 for (auto & node : nodes_) {824 bfs_node(*this, oss, node, 0);825 }826 return oss.str();827}828 829void common_peg_arena::resolve_refs() {830 // Walk through all parsers and replace refs with their corresponding rule IDs831 for (auto & parser : parsers_) {832 std::visit([this](auto & p) {833 using T = std::decay_t<decltype(p)>;834 835 if constexpr (std::is_same_v<T, common_peg_sequence_parser>) {836 for (auto & child : p.children) {837 child = resolve_ref(child);838 }839 } else if constexpr (std::is_same_v<T, common_peg_choice_parser>) {840 for (auto & child : p.children) {841 child = resolve_ref(child);842 }843 } else if constexpr (std::is_same_v<T, common_peg_repetition_parser> ||844 std::is_same_v<T, common_peg_and_parser> ||845 std::is_same_v<T, common_peg_not_parser> ||846 std::is_same_v<T, common_peg_tag_parser> ||847 std::is_same_v<T, common_peg_atomic_parser> ||848 std::is_same_v<T, common_peg_gbnf_parser> ||849 std::is_same_v<T, common_peg_ac_parser>) {850 p.child = resolve_ref(p.child);851 } else if constexpr (std::is_same_v<T, common_peg_rule_parser>) {852 p.child = resolve_ref(p.child);853 } else if constexpr (std::is_same_v<T, common_peg_schema_parser>) {854 p.child = resolve_ref(p.child);855 } else if constexpr (std::is_same_v<T, common_peg_epsilon_parser> ||856 std::is_same_v<T, common_peg_start_parser> ||857 std::is_same_v<T, common_peg_end_parser> ||858 std::is_same_v<T, common_peg_ref_parser> ||859 std::is_same_v<T, common_peg_until_parser> ||860 std::is_same_v<T, common_peg_literal_parser> ||861 std::is_same_v<T, common_peg_string_parser> ||862 std::is_same_v<T, common_peg_chars_parser> ||863 std::is_same_v<T, common_peg_any_parser> ||864 std::is_same_v<T, common_peg_space_parser>) {865 // These rules do not have children866 } else {867 static_assert(is_always_false_v<T>);868 }869 }, parser);870 }871 872 // Also flatten root if it's a ref873 if (root_ != COMMON_PEG_INVALID_PARSER_ID) {874 root_ = resolve_ref(root_);875 }876}877 878std::string common_peg_arena::dump(common_peg_parser_id id) const {879 std::set<common_peg_parser_id> visited;880 return dump_impl(id, visited);881}882 883std::string common_peg_arena::dump_impl(common_peg_parser_id id,884 std::set<common_peg_parser_id> & visited) const {885 // Check for cycles886 if (visited.count(id)) {887 return "[cycle]";888 }889 visited.insert(id);890 891 const auto & parser = parsers_.at(id);892 893 return std::visit([this, &visited](const auto & p) -> std::string {894 using T = std::decay_t<decltype(p)>;895 896 if constexpr (std::is_same_v<T, common_peg_epsilon_parser>) {897 return "Epsilon";898 } else if constexpr (std::is_same_v<T, common_peg_start_parser>) {899 return "Start";900 } else if constexpr (std::is_same_v<T, common_peg_end_parser>) {901 return "End";902 } else if constexpr (std::is_same_v<T, common_peg_literal_parser>) {903 return "Literal(" + p.literal + ")";904 } else if constexpr (std::is_same_v<T, common_peg_sequence_parser>) {905 std::vector<std::string> parts;906 for (const auto & child : p.children) {907 parts.push_back(dump_impl(child, visited));908 }909 return "Sequence(" + string_join(parts, ", ") + ")";910 } else if constexpr (std::is_same_v<T, common_peg_choice_parser>) {911 std::vector<std::string> parts;912 for (const auto & child : p.children) {913 parts.push_back(dump_impl(child, visited));914 }915 return "Choice(" + string_join(parts, ", ") + ")";916 } else if constexpr (std::is_same_v<T, common_peg_repetition_parser>) {917 if (p.max_count == -1) {918 return "Repetition(" + dump_impl(p.child, visited) + ", " + std::to_string(p.min_count) +919 ", unbounded)";920 }921 return "Repetition(" + dump_impl(p.child, visited) + ", " + std::to_string(p.min_count) + ", " + std::to_string(p.max_count) + ")";922 } else if constexpr (std::is_same_v<T, common_peg_and_parser>) {923 return "And(" + dump_impl(p.child, visited) + ")";924 } else if constexpr (std::is_same_v<T, common_peg_not_parser>) {925 return "Not(" + dump_impl(p.child, visited) + ")";926 } else if constexpr (std::is_same_v<T, common_peg_atomic_parser>) {927 return "Atomic(" + dump_impl(p.child, visited) + ")";928 } else if constexpr (std::is_same_v<T, common_peg_gbnf_parser>) {929 return "Gbnf(" + p.grammar + ", " + dump_impl(p.child, visited) + ")";930 } else if constexpr (std::is_same_v<T, common_peg_ac_parser>) {931 return "Ac(" + string_join(p.delimiters, " | ") + ", " + dump_impl(p.child, visited) + ")";932 } else if constexpr (std::is_same_v<T, common_peg_any_parser>) {933 return "Any";934 } else if constexpr (std::is_same_v<T, common_peg_space_parser>) {935 return "Space";936 } else if constexpr (std::is_same_v<T, common_peg_chars_parser>) {937 if (p.max_count == -1) {938 return "CharRepeat(" + p.pattern + ", " + std::to_string(p.min_count) + ", unbounded)";939 }940 return "CharRepeat(" + p.pattern + ", " + std::to_string(p.min_count) + ", " + std::to_string(p.max_count) + ")";941 } else if constexpr (std::is_same_v<T, common_peg_string_parser>) {942 return "String(" + std::string(1, p.delimiter) + ")";943 } else if constexpr (std::is_same_v<T, common_peg_until_parser>) {944 return "Until(" + string_join(p.delimiters, " | ") + ")";945 } else if constexpr (std::is_same_v<T, common_peg_schema_parser>) {946 return "Schema(" + dump_impl(p.child, visited) + ", " + (p.schema ? p.schema->dump() : "null") + ")";947 } else if constexpr (std::is_same_v<T, common_peg_rule_parser>) {948 return "Rule(" + p.name + ", " + dump_impl(p.child, visited) + ")";949 } else if constexpr (std::is_same_v<T, common_peg_ref_parser>) {950 return "Ref(" + p.name + ")";951 } else if constexpr (std::is_same_v<T, common_peg_tag_parser>) {952 return "Tag(" + p.tag + ", " + dump(p.child) + ")";953 } else if constexpr (std::is_same_v<T, common_peg_atomic_parser>) {954 return "Atomic(" + dump(p.child) + ")";955 } else {956 return "Unknown";957 }958 }, parser);959}960 961common_peg_parser & common_peg_parser::operator=(const common_peg_parser & other) {962 id_ = other.id_;963 return *this;964}965 966common_peg_parser & common_peg_parser::operator+=(const common_peg_parser & other) {967 id_ = builder_.sequence({id_, other.id_});968 return *this;969}970 971common_peg_parser & common_peg_parser::operator|=(const common_peg_parser & other) {972 id_ = builder_.choice({id_, other.id_});973 return *this;974}975 976common_peg_parser common_peg_parser::operator+(const common_peg_parser & other) const {977 return builder_.sequence({id_, other.id_});978}979 980common_peg_parser common_peg_parser::operator|(const common_peg_parser & other) const {981 return builder_.choice({id_, other.id_});982}983 984common_peg_parser common_peg_parser::operator<<(const common_peg_parser & other) const {985 return builder_.sequence({id_, builder_.space(), other.id_});986}987 988common_peg_parser common_peg_parser::operator+(const char * str) const {989 return *this + builder_.literal(str);990}991 992common_peg_parser common_peg_parser::operator+(const std::string & str) const {993 return *this + builder_.literal(str);994}995 996common_peg_parser common_peg_parser::operator<<(const char * str) const {997 return *this << builder_.literal(str);998}999 1000common_peg_parser common_peg_parser::operator<<(const std::string & str) const {1001 return *this << builder_.literal(str);1002}1003 1004common_peg_parser common_peg_parser::operator|(const char * str) const {1005 return *this | builder_.literal(str);1006}1007 1008common_peg_parser common_peg_parser::operator|(const std::string & str) const {1009 return *this | builder_.literal(str);1010}1011 1012common_peg_parser operator+(const char * str, const common_peg_parser & p) {1013 return p.builder().literal(str) + p;1014}1015 1016common_peg_parser operator+(const std::string & str, const common_peg_parser & p) {1017 return operator+(str.c_str(), p);1018}1019 1020common_peg_parser operator<<(const char * str, const common_peg_parser & p) {1021 return p.builder().literal(str) << p;1022}1023 1024common_peg_parser operator<<(const std::string & str, const common_peg_parser & p) {1025 return operator<<(str.c_str(), p);1026}1027 1028common_peg_parser operator|(const char * str, const common_peg_parser & p) {1029 return p.builder().literal(str) | p;1030}1031 1032common_peg_parser operator|(const std::string & str, const common_peg_parser & p) {1033 return operator|(str.c_str(), p);1034}1035 1036static std::string rule_name(const std::string & name) {1037 static const std::regex invalid_rule_chars_re("[^a-zA-Z0-9-]+");1038 return std::regex_replace(name, invalid_rule_chars_re, "-");1039}1040 1041common_peg_parser_builder::common_peg_parser_builder() {}1042 1043common_peg_parser common_peg_parser_builder::sequence(const std::vector<common_peg_parser_id> & parsers) {1044 // Flatten nested sequences1045 std::vector<common_peg_parser_id> flattened;1046 for (const auto & p : parsers) {1047 const auto & parser = arena_.get(p);1048 if (auto seq = std::get_if<common_peg_sequence_parser>(&parser)) {1049 flattened.insert(flattened.end(), seq->children.begin(), seq->children.end());1050 } else {1051 flattened.push_back(p);1052 }1053 }1054 return wrap(arena_.add_parser(common_peg_sequence_parser{flattened}));1055}1056 1057common_peg_parser common_peg_parser_builder::sequence(const std::vector<common_peg_parser> & parsers) {1058 std::vector<common_peg_parser_id> ids;1059 ids.reserve(parsers.size());1060 for (const auto & p : parsers) {1061 ids.push_back(p.id());1062 }1063 return sequence(ids);1064}1065 1066common_peg_parser common_peg_parser_builder::sequence(std::initializer_list<common_peg_parser> parsers) {1067 std::vector<common_peg_parser_id> ids;1068 ids.reserve(parsers.size());1069 for (const auto & p : parsers) {1070 ids.push_back(p.id());1071 }1072 return sequence(ids);1073}1074 1075common_peg_parser common_peg_parser_builder::choice(const std::vector<common_peg_parser_id> & parsers) {1076 // Flatten nested choices1077 std::vector<common_peg_parser_id> flattened;1078 for (const auto & p : parsers) {1079 const auto & parser = arena_.get(p);1080 if (auto choice = std::get_if<common_peg_choice_parser>(&parser)) {1081 flattened.insert(flattened.end(), choice->children.begin(), choice->children.end());1082 } else {1083 flattened.push_back(p);1084 }1085 }1086 return wrap(arena_.add_parser(common_peg_choice_parser{flattened}));1087}1088 1089common_peg_parser common_peg_parser_builder::choice(const std::vector<common_peg_parser> & parsers) {1090 std::vector<common_peg_parser_id> ids;1091 ids.reserve(parsers.size());1092 for (const auto & p : parsers) {1093 ids.push_back(p.id());1094 }1095 return choice(ids);1096}1097 1098common_peg_parser common_peg_parser_builder::choice(std::initializer_list<common_peg_parser> parsers) {1099 std::vector<common_peg_parser_id> ids;1100 ids.reserve(parsers.size());1101 for (const auto & p : parsers) {1102 ids.push_back(p.id());1103 }1104 return choice(ids);1105}1106 1107common_peg_parser common_peg_parser_builder::chars(const std::string & classes, int min, int max) {1108 auto [ranges, negated] = parse_char_classes(classes);1109 return wrap(arena_.add_parser(common_peg_chars_parser{classes, ranges, negated, min, max}));1110}1111 1112common_peg_parser common_peg_parser_builder::schema(const common_peg_parser & p, const std::string & name, const nlohmann::ordered_json & schema, bool raw) {1113 return wrap(arena_.add_parser(common_peg_schema_parser{p.id(), name, std::make_shared<nlohmann::ordered_json>(schema), raw}));1114}1115 1116common_peg_parser common_peg_parser_builder::rule(const std::string & name, const common_peg_parser & p, bool trigger) {1117 auto clean_name = rule_name(name);1118 auto rule_id = arena_.add_parser(common_peg_rule_parser{clean_name, p.id(), trigger});1119 arena_.add_rule(clean_name, rule_id);1120 return ref(clean_name);1121}1122 1123common_peg_parser common_peg_parser_builder::rule(const std::string & name, const std::function<common_peg_parser()> & builder_fn, bool trigger) {1124 auto clean_name = rule_name(name);1125 if (arena_.has_rule(clean_name)) {1126 return ref(clean_name);1127 }1128 1129 // Create placeholder rule to allow recursive references1130 auto placeholder = any(); // Temporary placeholder1131 auto placeholder_rule_id = arena_.add_parser(common_peg_rule_parser{clean_name, placeholder.id(), trigger});1132 arena_.add_rule(clean_name, placeholder_rule_id);1133 1134 // Build the actual parser1135 auto parser = builder_fn();1136 1137 // Replace placeholder with actual rule1138 auto rule_id = arena_.add_parser(common_peg_rule_parser{clean_name, parser.id(), trigger});1139 arena_.rules_[clean_name] = rule_id;1140 1141 return ref(clean_name);1142}1143 1144void common_peg_parser_builder::set_root(const common_peg_parser & p) {1145 arena_.set_root(p.id());1146}1147 1148common_peg_arena common_peg_parser_builder::build() {1149 arena_.resolve_refs();1150 return std::move(arena_);1151}1152 1153// String primitives1154 1155common_peg_parser common_peg_parser_builder::string_content(char delimiter) {1156 return wrap(arena_.add_parser(common_peg_string_parser{delimiter}));1157}1158 1159common_peg_parser common_peg_parser_builder::double_quoted_string() {1160 return rule("double-quoted-string", [this]() {1161 return sequence({literal("\""), string_content('"'), literal("\"")});1162 });1163}1164 1165common_peg_parser common_peg_parser_builder::single_quoted_string() {1166 return rule("single-quoted-string", [this]() {1167 return sequence({literal("'"), string_content('\''), literal("'")});1168 });1169}1170 1171common_peg_parser common_peg_parser_builder::quoted_string() {1172 return rule("quoted-string", [this]() {1173 return choice({double_quoted_string(), single_quoted_string()});1174 });1175}1176 1177// JSON parsers1178 1179common_peg_parser common_peg_parser_builder::json_number() {1180 return rule("json-number", [this]() {1181 auto digit1_9 = chars("[1-9]", 1, 1);1182 auto digits = chars("[0-9]");1183 auto int_part = choice({literal("0"), sequence({digit1_9, chars("[0-9]", 0, -1)})});1184 auto frac = sequence({literal("."), digits});1185 auto exp = sequence({choice({literal("e"), literal("E")}), optional(chars("[+-]", 1, 1)), digits});1186 // Negative lookahead: only commit the number when the next character can't extend it.1187 // At EOF in partial mode, chars returns NEED_MORE → negate propagates NEED_MORE → number not committed.1188 // This prevents premature commits of partial numbers (e.g. "3" when "3.14" is incoming).1189 auto not_number_continuation = negate(chars("[0-9.eE+-]", 1, 1));1190 return sequence({ optional(literal("-")), int_part, optional(frac), optional(exp), not_number_continuation });1191 });1192}1193 1194common_peg_parser common_peg_parser_builder::json_string() {1195 return rule("json-string", [this]() {1196 return sequence({literal("\""), string_content('"'), literal("\"")});1197 });1198}1199 1200common_peg_parser common_peg_parser_builder::json_bool() {