Felipe97/llama-cpp-compiled

1#pragma once2 3#include "json-schema.h"4#include "json.h"5 6#include <memory>7#include <set>8#include <unordered_map>9#include <string>10#include <string_view>11#include <functional>12#include <vector>13#include <variant>14 15struct common_grammar_builder;16 17class common_peg_parser_builder;18 19using common_peg_parser_id = size_t;20constexpr common_peg_parser_id COMMON_PEG_INVALID_PARSER_ID = static_cast<common_peg_parser_id>(-1);21 22using common_peg_ast_id = size_t;23constexpr common_peg_ast_id COMMON_PEG_INVALID_AST_ID = static_cast<common_peg_ast_id>(-1);24 25// Lightweight wrapper around common_peg_parser_id for convenience26class common_peg_parser {27    common_peg_parser_id id_;28    common_peg_parser_builder & builder_;29 30  public:31    common_peg_parser(const common_peg_parser & other) : id_(other.id_), builder_(other.builder_) {}32    common_peg_parser(common_peg_parser_id id, common_peg_parser_builder & builder) : id_(id), builder_(builder) {}33 34    common_peg_parser & operator=(const common_peg_parser & other);35    common_peg_parser & operator+=(const common_peg_parser & other);36    common_peg_parser & operator|=(const common_peg_parser & other);37 38    operator common_peg_parser_id() const { return id_; }39    common_peg_parser_id id() const { return id_; }40 41    common_peg_parser_builder & builder() const { return builder_; }42 43    // Creates a sequence44    common_peg_parser operator+(const common_peg_parser & other) const;45 46    // Creates a sequence separated by spaces.47    common_peg_parser operator<<(const common_peg_parser & other) const;48 49    // Creates a choice50    common_peg_parser operator|(const common_peg_parser & other) const;51 52    common_peg_parser operator+(const char * str) const;53    common_peg_parser operator+(const std::string & str) const;54    common_peg_parser operator<<(const char * str) const;55    common_peg_parser operator<<(const std::string & str) const;56    common_peg_parser operator|(const char * str) const;57    common_peg_parser operator|(const std::string & str) const;58};59 60common_peg_parser operator+(const char * str, const common_peg_parser & p);61common_peg_parser operator+(const std::string & str, const common_peg_parser & p);62common_peg_parser operator<<(const char * str, const common_peg_parser & p);63common_peg_parser operator<<(const std::string & str, const common_peg_parser & p);64common_peg_parser operator|(const char * str, const common_peg_parser & p);65common_peg_parser operator|(const std::string & str, const common_peg_parser & p);66 67enum common_peg_parse_result_type {68    COMMON_PEG_PARSE_RESULT_FAIL            = 0,69    COMMON_PEG_PARSE_RESULT_SUCCESS         = 1,70    COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT = 2,71};72 73const char * common_peg_parse_result_type_name(common_peg_parse_result_type type);74 75struct common_peg_ast_node {76    common_peg_ast_id id;77    std::string rule;78    std::string tag;79    size_t start;80    size_t end;81    std::string_view text;82    std::vector<common_peg_ast_id> children;83 84    bool is_partial = false;85};86 87struct common_peg_parse_result;88 89using common_peg_ast_visitor = std::function<void(const common_peg_ast_node & node)>;90 91class common_peg_ast_arena {92    std::vector<common_peg_ast_node> nodes_;93  public:94    common_peg_ast_id add_node(95        const std::string & rule,96        const std::string & tag,97        size_t start,98        size_t end,99        std::string_view text,100        std::vector<common_peg_ast_id> children,101        bool is_partial = false102    ) {103        common_peg_ast_id id = nodes_.size();104        nodes_.push_back({id, rule, tag, start, end, text, std::move(children), is_partial});105        return id;106    }107 108    const common_peg_ast_node & get(common_peg_ast_id id) const { return nodes_.at(id); }109 110    common_peg_ast_id find_by_tag(const common_peg_ast_node & parent, const std::string & tag, int max_depth = 3) const;111    common_peg_ast_id find_by_rule(const common_peg_ast_node & parent, const std::string & tag, int max_depth = 3) const;112 113    size_t size() const { return nodes_.size(); }114 115    void clear() { nodes_.clear(); }116 117    void visit(common_peg_ast_id id, const common_peg_ast_visitor & visitor) const;118    void visit(const common_peg_parse_result & result, const common_peg_ast_visitor & visitor) const;119 120    std::string dump();121};122 123struct common_peg_parse_result {124    common_peg_parse_result_type type = COMMON_PEG_PARSE_RESULT_FAIL;125    size_t start = 0;126    size_t end = 0;127 128    std::vector<common_peg_ast_id> nodes;129 130    common_peg_parse_result() = default;131 132    common_peg_parse_result(common_peg_parse_result_type type, size_t start)133        : type(type), start(start), end(start) {}134 135    common_peg_parse_result(common_peg_parse_result_type type, size_t start, size_t end)136        : type(type), start(start), end(end) {}137 138    common_peg_parse_result(common_peg_parse_result_type type, size_t start, size_t end, std::vector<common_peg_ast_id> nodes)139        : type(type), start(start), end(end), nodes(std::move(nodes)) {}140 141    bool fail() const { return type == COMMON_PEG_PARSE_RESULT_FAIL; }142    bool need_more_input() const { return type == COMMON_PEG_PARSE_RESULT_NEED_MORE_INPUT; }143    bool success() const { return type == COMMON_PEG_PARSE_RESULT_SUCCESS; }144};145 146enum common_peg_parse_flags {147    COMMON_PEG_PARSE_FLAG_NONE    = 0,148    COMMON_PEG_PARSE_FLAG_LENIENT = 1 << 0,149    COMMON_PEG_PARSE_FLAG_DEBUG   = 1 << 1,150};151 152inline common_peg_parse_flags operator|(common_peg_parse_flags a, common_peg_parse_flags b) {153    return static_cast<common_peg_parse_flags>(int(a) | int(b));154}155 156inline common_peg_parse_flags & operator|=(common_peg_parse_flags & a, common_peg_parse_flags b) {157    return a = a | b;158}159 160inline common_peg_parse_flags operator&(common_peg_parse_flags a, common_peg_parse_flags b) {161    return static_cast<common_peg_parse_flags>(int(a) & int(b));162}163 164inline common_peg_parse_flags operator~(common_peg_parse_flags a) {165    return static_cast<common_peg_parse_flags>(~int(a));166}167 168struct common_peg_parse_context {169    std::string input;170    common_peg_parse_flags flags;171    common_peg_ast_arena ast;172 173    int parse_depth;174 175    common_peg_parse_context(common_peg_parse_flags flags = COMMON_PEG_PARSE_FLAG_NONE)176        : flags(flags), parse_depth(0) {}177 178    common_peg_parse_context(const std::string & input, common_peg_parse_flags flags = COMMON_PEG_PARSE_FLAG_NONE)179        : input(input), flags(flags), parse_depth(0) {}180 181    bool is_lenient() const { return flags & COMMON_PEG_PARSE_FLAG_LENIENT; }182    bool is_debug() const { return flags & COMMON_PEG_PARSE_FLAG_DEBUG; }183};184 185class common_peg_arena;186 187// Parser variants188struct common_peg_epsilon_parser {};189 190struct common_peg_start_parser {};191 192struct common_peg_end_parser {};193 194struct common_peg_literal_parser {195    std::string literal;196};197 198struct common_peg_sequence_parser {199    std::vector<common_peg_parser_id> children;200};201 202struct common_peg_choice_parser {203    std::vector<common_peg_parser_id> children;204};205 206struct common_peg_repetition_parser {207    common_peg_parser_id child;208    int min_count;209    int max_count;  // -1 for unbounded210};211 212struct common_peg_and_parser {213    common_peg_parser_id child;214};215 216struct common_peg_not_parser {217    common_peg_parser_id child;218};219 220struct common_peg_any_parser {};221 222struct common_peg_space_parser {};223 224struct common_peg_chars_parser {225    struct char_range {226        uint32_t start;227        uint32_t end;228        bool contains(uint32_t codepoint) const { return codepoint >= start && codepoint <= end; }229    };230 231    std::string pattern;232    std::vector<char_range> ranges;233    bool negated;234    int min_count;235    int max_count;  // -1 for unbounded236};237 238struct common_peg_string_parser {239    char delimiter;240};241 242struct common_peg_until_parser {243    std::vector<std::string> delimiters;244};245 246struct common_peg_schema_parser {247    common_peg_parser_id child;248    std::string name;249    common_chat_schema_document_ptr doc;  // owns node250    const common_chat_schema * node = nullptr;251 252    // Indicates if the GBNF should accept a raw string that matches the schema.253    bool raw;254};255 256struct common_peg_rule_parser {257    std::string name;258    common_peg_parser_id child;259    bool trigger;260};261 262struct common_peg_ref_parser {263    std::string name;264};265 266struct common_peg_atomic_parser {267    common_peg_parser_id child;268};269 270struct common_peg_tag_parser {271    common_peg_parser_id child;272    std::string tag;273};274 275struct common_peg_gbnf_parser {276    common_peg_parser_id child;277    std::string grammar;278};279 280struct common_peg_ac_parser {281    common_peg_parser_id child;282    std::vector<std::string> delimiters;283};284 285// Variant holding all parser types286using common_peg_parser_variant = std::variant<287    common_peg_epsilon_parser,288    common_peg_start_parser,289    common_peg_end_parser,290    common_peg_literal_parser,291    common_peg_sequence_parser,292    common_peg_choice_parser,293    common_peg_repetition_parser,294    common_peg_and_parser,295    common_peg_not_parser,296    common_peg_any_parser,297    common_peg_space_parser,298    common_peg_chars_parser,299    common_peg_string_parser,300    common_peg_until_parser,301    common_peg_schema_parser,302    common_peg_rule_parser,303    common_peg_ref_parser,304    common_peg_atomic_parser,305    common_peg_tag_parser,306    common_peg_gbnf_parser,307    common_peg_ac_parser308>;309 310class common_peg_arena {311    std::vector<common_peg_parser_variant> parsers_;312    std::unordered_map<std::string, common_peg_parser_id> rules_;313    common_peg_parser_id root_ = COMMON_PEG_INVALID_PARSER_ID;314 315  public:316    const common_peg_parser_variant & get(common_peg_parser_id id) const { return parsers_.at(id); }317    common_peg_parser_variant & get(common_peg_parser_id id) { return parsers_.at(id); }318 319    size_t size() const { return parsers_.size(); }320    bool empty() const { return parsers_.empty(); }321 322    common_peg_parser_id get_rule(const std::string & name) const;323    bool has_rule(const std::string & name) const { return rules_.find(name) != rules_.end(); }324 325    common_peg_parser_id root() const { return root_; }326    void set_root(common_peg_parser_id id) { root_ = id; }327 328    common_peg_parse_result parse(common_peg_parse_context & ctx, size_t start = 0) const;329    common_peg_parse_result parse(common_peg_parser_id id, common_peg_parse_context & ctx, size_t start) const;330 331    void resolve_refs();332 333    void build_grammar(const common_grammar_builder & builder, bool lazy = false) const;334 335    std::string dump(common_peg_parser_id id) const;336 337    common_json to_json() const;338    static common_peg_arena from_json(const common_json & j);339 340    std::string save() const;341    void load(const std::string & data);342 343    friend class common_peg_parser_builder;344 345  private:346    std::string dump_impl(common_peg_parser_id id, std::set<common_peg_parser_id> & visited) const;347 348    common_peg_parser_id add_parser(common_peg_parser_variant parser);349    void add_rule(const std::string & name, common_peg_parser_id id);350 351    common_peg_parser_id resolve_ref(common_peg_parser_id id);352};353 354class common_peg_parser_builder {355    common_peg_arena arena_;356 357    common_peg_parser wrap(common_peg_parser_id id) { return common_peg_parser(id, *this); }358    common_peg_parser add(const common_peg_parser_variant & p) { return wrap(arena_.add_parser(p)); }359 360  public:361    common_peg_parser_builder();362 363    // Match nothing, always succeed.364    //   S -> ε365    common_peg_parser eps() { return add(common_peg_epsilon_parser{}); }366 367    // Matches the start of the input.368    //   S -> ^369    common_peg_parser start() { return add(common_peg_start_parser{}); }370 371    // Matches the end of the input.372    //   S -> $373    common_peg_parser end() { return add(common_peg_end_parser{}); }374 375    // Matches an exact literal string.376    //   S -> "hello"377    common_peg_parser literal(const std::string & literal) { return add(common_peg_literal_parser{literal}); }378 379    // Matches a sequence of parsers in order, all must succeed.380    //   S -> A B C381    common_peg_parser sequence() { return add(common_peg_sequence_parser{}); }382    common_peg_parser sequence(const std::vector<common_peg_parser_id> & parsers);383    common_peg_parser sequence(const std::vector<common_peg_parser> & parsers);384    common_peg_parser sequence(std::initializer_list<common_peg_parser> parsers);385 386    // Matches the first parser that succeeds from a list of alternatives.387    //   S -> A | B | C388    common_peg_parser choice() { return add(common_peg_choice_parser{}); }389    common_peg_parser choice(const std::vector<common_peg_parser_id> & parsers);390    common_peg_parser choice(const std::vector<common_peg_parser> & parsers);391    common_peg_parser choice(std::initializer_list<common_peg_parser> parsers);392 393    // Matches one or more repetitions of a parser.394    //   S -> A+395    common_peg_parser one_or_more(const common_peg_parser & p) { return repeat(p, 1, -1); }396 397    // Matches zero or more repetitions of a parser, always succeeds.398    //   S -> A*399    common_peg_parser zero_or_more(const common_peg_parser & p) { return repeat(p, 0, -1); }400 401    // Matches zero or one occurrence of a parser, always succeeds.402    //   S -> A?403    common_peg_parser optional(const common_peg_parser & p) { return repeat(p, 0, 1); }404 405    // Positive lookahead: succeeds if child parser succeeds, consumes no input.406    //   S -> &A407    common_peg_parser peek(const common_peg_parser & p) { return add(common_peg_and_parser{p}); }408 409    // Negative lookahead: succeeds if child parser fails, consumes no input.410    //   S -> !A411    common_peg_parser negate(const common_peg_parser & p) { return add(common_peg_not_parser{p}); }412 413    // Matches any single character.414    //   S -> .415    common_peg_parser any() { return add(common_peg_any_parser{}); }416 417    // Matches between min and max repetitions of characters from a character class.418    //   S -> [a-z]{m,n}419    //420    // Use -1 for max to represent unbounded repetition (equivalent to {m,})421    common_peg_parser chars(const std::string & classes, int min = 1, int max = -1);422 423    // Creates a lightweight reference to a named rule (resolved during build()).424    // Use this for forward references in recursive grammars.425    //   expr_ref -> expr426    common_peg_parser ref(const std::string & name) { return add(common_peg_ref_parser{name}); }427 428    // Matches zero or more whitespace characters (space, tab, newline).429    //   S -> [ \t\n]*430    common_peg_parser space() { return add(common_peg_space_parser{}); }431 432    // Matches all characters until a delimiter is found (delimiter not consumed).433    //   S -> (!delim .)*434    common_peg_parser until(const std::string & delimiter) { return add(common_peg_until_parser{{delimiter}}); }435 436    // Matches all characters until one of the delimiters in the list is found (delimiter not consumed).437    //   S -> (!delim .)*438    common_peg_parser until_one_of(const std::vector<std::string> & delimiters) { return add(common_peg_until_parser{delimiters}); }439 440    // Matches everything441    //   S -> .*442    common_peg_parser rest() { return until_one_of({}); }443 444    // Matches between min and max repetitions of a parser (inclusive).445    //   S -> A{m,n}446    // Use -1 for max to represent unbounded repetition (equivalent to {m,})447    common_peg_parser repeat(const common_peg_parser & p, int min, int max) { return add(common_peg_repetition_parser{p, min,max}); }448 449    // Matches exactly n repetitions of a parser.450    //   S -> A{n}451    common_peg_parser repeat(const common_peg_parser & p, int n) { return repeat(p, n, n); }452 453    // Matches a double-quoted string: '"' content '"' space454    common_peg_parser double_quoted_string();455 456    // Matches a single-quoted string: "'" content "'" space457    common_peg_parser single_quoted_string();458 459    // Matches a string that accepts both double-quoted and single-quoted styles.460    common_peg_parser quoted_string();461 462    // Matches string content without the surrounding delimiter.463    common_peg_parser string_content(char delimiter);464 465    // Creates a complete JSON parser supporting objects, arrays, strings, numbers, booleans, and null.466    //   value -> object | array | string | number | true | false | null467    common_peg_parser json();468    common_peg_parser json_object();469    common_peg_parser json_string();470    common_peg_parser json_array();471    common_peg_parser json_number();472    common_peg_parser json_bool();473    common_peg_parser json_null();474 475    // Matches a JSON object member with a key and associated parser as the476    // value.477    common_peg_parser json_member(const std::string & key, const common_peg_parser & p);478 479    // Creates a complete Python format parser supporting dicts, arrays, strings, numbers, booleans, and None.480    // Differs from JSON: uses True/False/None, accepts both single and double-quoted strings.481    //   value -> dict | array | string | number | True | False | None482    common_peg_parser python_value();483    common_peg_parser python_dict();484    common_peg_parser python_string();485    common_peg_parser python_array();486    common_peg_parser python_number();487    common_peg_parser python_bool();488    common_peg_parser python_null();489 490    // A marker, i.e. text delimited by a pair of <> or []491    common_peg_parser marker();492 493    // Wraps a parser with the schema its GBNF is generated from, a node of the document that owns it494    common_peg_parser schema(const common_peg_parser & p, const std::string & name, common_chat_schema_document_ptr doc, const common_chat_schema & node, bool raw = false);495 496    // Parses the JSON schema into a document of its own497    common_peg_parser schema(const common_peg_parser & p, const std::string & name, const common_json & schema, bool raw = false);498 499    // Creates a named rule, stores it in the grammar, and returns a ref.500    // If trigger=true, marks this rule as an entry point for lazy grammar generation.501    //   auto json = p.rule("json", json_obj | json_arr | ...)502    common_peg_parser rule(const std::string & name, const common_peg_parser & p, bool trigger = false);503 504    // Creates a named rule using a builder function, and returns a ref.505    // If trigger=true, marks this rule as an entry point for lazy grammar generation.506    //   auto json = p.rule("json", [&]() { return json_object() | json_array() | ... })507    common_peg_parser rule(const std::string & name, const std::function<common_peg_parser()> & builder, bool trigger = false);508 509    // Creates a trigger rule. When generating a lazy grammar from the parser,510    // only trigger rules and descendents are emitted.511    common_peg_parser trigger_rule(const std::string & name, const common_peg_parser & p) { return rule(name, p, true); }512    common_peg_parser trigger_rule(const std::string & name, const std::function<common_peg_parser()> & builder) { return rule(name, builder, true); }513 514    // Creates an atomic parser. Atomic parsers do not create an AST node if515    // the child results in a partial parse, i.e. NEEDS_MORE_INPUT. This is516    // intended for situations where partial output is undesirable.517    common_peg_parser atomic(const common_peg_parser & p) { return add(common_peg_atomic_parser{p}); }518 519    // Tags create nodes in the generated AST for semantic purposes.520    // Unlike rules, you can tag multiple nodes with the same tag.521    common_peg_parser tag(const std::string & tag, const common_peg_parser & p) { return add(common_peg_tag_parser{p.id(), tag}); }522 523    // Wraps a child parser but emits a custom GBNF grammar string instead of524    // the child's grammar. Parsing delegates entirely to the child.525    common_peg_parser gbnf(const common_peg_parser & p, const std::string & grammar) { return add(common_peg_gbnf_parser{p, grammar}); }526 527    // Wraps a child parser but emits a GBNF grammar built from the Aho-Corasick528    // automaton of `delimiters`, matching everything up to and including the529    // first delimiter. Parsing delegates entirely to the child, which is530    // responsible for consuming the delimiter (e.g. until(D) + literal(D)).531    common_peg_parser ac(const common_peg_parser & p, const std::vector<std::string> & delimiters);532    common_peg_parser ac(const common_peg_parser & p, const std::string & delimiter) { return ac(p, std::vector<std::string>{delimiter}); }533 534    void set_root(const common_peg_parser & p);535 536    common_peg_arena build();537};538 539// Helper function for building parsers540common_peg_arena build_peg_parser(const std::function<common_peg_parser(common_peg_parser_builder & builder)> & fn);541