echodict/llama.cpp

1#include "json-schema-to-grammar.h"2#include "common.h"3 4#include <nlohmann/json.hpp>5 6#include <algorithm>7#include <map>8#include <regex>9#include <sstream>10#include <string>11#include <unordered_map>12#include <unordered_set>13#include <vector>14 15using json = nlohmann::ordered_json;16 17static std::string build_repetition(const std::string & item_rule, int min_items, int max_items, const std::string & separator_rule = "") {18    auto has_max = max_items != std::numeric_limits<int>::max();19 20    if (max_items == 0) {21        return "";22    }23    if (min_items == 0 && max_items == 1) {24        return item_rule + "?";25    }26 27    if (separator_rule.empty()) {28        if (min_items == 1 && !has_max) {29            return item_rule + "+";30        }31        if (min_items == 0 && !has_max) {32            return item_rule + "*";33        }34        return item_rule + "{" + std::to_string(min_items) + "," + (has_max ? std::to_string(max_items) : "") + "}";35    }36 37    auto result = item_rule + " " + build_repetition("(" + separator_rule + " " + item_rule + ")", min_items == 0 ? 0 : min_items - 1, has_max ? max_items - 1 : max_items);38    if (min_items == 0) {39        result = "(" + result + ")?";40    }41    return result;42}43 44static void build_min_max_int(int64_t min_value, int64_t max_value, std::stringstream & out, int decimals_left = 16, bool top_level = true) {45    auto has_min = min_value != std::numeric_limits<int64_t>::min();46    auto has_max = max_value != std::numeric_limits<int64_t>::max();47 48    auto digit_range = [&](char from, char to) {49        out << "[";50        if (from == to) {51            out << from;52        } else {53            out << from << "-" << to;54        }55        out << "]";56    };57    auto more_digits = [&](int min_digits, int max_digits) {58        out << "[0-9]";59        if (min_digits == max_digits && min_digits == 1) {60            return;61        }62        out << "{";63        out << min_digits;64        if (max_digits != min_digits) {65            out << ",";66            if (max_digits != std::numeric_limits<int>::max()) {67                out << max_digits;68            }69        }70        out << "}";71    };72    std::function<void(const std::string_view &, const std::string_view &)> uniform_range =73        [&](const std::string_view & from, const std::string_view & to) {74            size_t i = 0;75            while (i < from.length() && i < to.length() && from[i] == to[i]) {76                i++;77            }78            if (i > 0) {79                out << "\"" << from.substr(0, i) << "\"";80            }81            if (i < from.length() && i < to.length()) {82                if (i > 0) {83                    out << " ";84                }85                auto sub_len = from.length() - i - 1;86                if (sub_len > 0) {87                    auto from_sub = from.substr(i + 1);88                    auto to_sub = to.substr(i + 1);89                    auto sub_zeros = string_repeat("0", sub_len);90                    auto sub_nines = string_repeat("9", sub_len);91 92                    auto to_reached = false;93                    out << "(";94                    if (from_sub == sub_zeros) {95                        digit_range(from[i], to[i] - 1);96                        out << " ";97                        more_digits(sub_len, sub_len);98                    } else {99                        out << "[" << from[i] << "] ";100                        out << "(";101                        uniform_range(from_sub, sub_nines);102                        out << ")";103                        if (from[i] < to[i] - 1) {104                            out << " | ";105                            if (to_sub == sub_nines) {106                                digit_range(from[i] + 1, to[i]);107                                to_reached = true;108                            } else {109                                digit_range(from[i] + 1, to[i] - 1);110                            }111                            out << " ";112                            more_digits(sub_len, sub_len);113                        }114                    }115                    if (!to_reached) {116                        out << " | ";117                        digit_range(to[i], to[i]);118                        out << " ";119                        uniform_range(sub_zeros, to_sub);120                    }121                    out << ")";122                } else {123                    out << "[" << from[i] << "-" << to[i] << "]";124                }125            }126        };127 128    if (has_min && has_max) {129        if (min_value < 0 && max_value < 0) {130            out << "\"-\" (";131            build_min_max_int(-max_value, -min_value, out, decimals_left, /* top_level= */ true);132            out << ")";133            return;134        }135 136        if (min_value < 0) {137            out << "\"-\" (";138            build_min_max_int(0, -min_value, out, decimals_left, /* top_level= */ true);139            out << ") | ";140            min_value = 0;141        }142 143        auto min_s = std::to_string(min_value);144        auto max_s = std::to_string(max_value);145        auto min_digits = min_s.length();146        auto max_digits = max_s.length();147 148        for (auto digits = min_digits; digits < max_digits; digits++) {149            uniform_range(min_s, string_repeat("9", digits));150            min_s = "1" + string_repeat("0", digits);151            out << " | ";152        }153        uniform_range(min_s, max_s);154        return;155    }156 157    auto less_decimals = std::max(decimals_left - 1, 1);158 159    if (has_min) {160        if (min_value < 0) {161            out << "\"-\" (";162            build_min_max_int(std::numeric_limits<int64_t>::min(), -min_value, out, decimals_left, /* top_level= */ false);163            out << ") | [0] | [1-9] ";164            more_digits(0, decimals_left - 1);165        } else if (min_value == 0) {166            if (top_level) {167                out << "[0] | [1-9] ";168                more_digits(0, less_decimals);169            } else {170                more_digits(1, decimals_left);171            }172        } else if (min_value <= 9) {173            char c = '0' + min_value;174            auto range_start = top_level ? '1' : '0';175            if (c > range_start) {176                digit_range(range_start, c - 1);177                out << " ";178                more_digits(1, less_decimals);179                out << " | ";180            }181            digit_range(c, '9');182            out << " ";183            more_digits(0, less_decimals);184        } else {185            auto min_s = std::to_string(min_value);186            auto len = min_s.length();187            auto c = min_s[0];188 189            if (c > '1') {190                digit_range(top_level ? '1' : '0', c - 1);191                out << " ";192                more_digits(len, less_decimals);193                out << " | ";194            }195            digit_range(c, c);196            out << " (";197            build_min_max_int(std::stoll(min_s.substr(1)), std::numeric_limits<int64_t>::max(), out, less_decimals, /* top_level= */ false);198            out << ")";199            if (c < '9') {200                out << " | ";201                digit_range(c + 1, '9');202                out << " ";203                more_digits(len - 1, less_decimals);204            }205        }206        return;207    }208 209    if (has_max) {210        if (max_value >= 0) {211            if (top_level) {212                out << "\"-\" [1-9] ";213                more_digits(0, less_decimals);214                out << " | ";215            }216            build_min_max_int(0, max_value, out, decimals_left, /* top_level= */ true);217        } else {218            out << "\"-\" (";219            build_min_max_int(-max_value, std::numeric_limits<int64_t>::max(), out, decimals_left, /* top_level= */ false);220            out << ")";221        }222        return;223    }224 225    throw std::runtime_error("At least one of min_value or max_value must be set");226}227 228const std::string SPACE_RULE = "| \" \" | \"\\n\"{1,2} [ \\t]{0,20}";229 230struct BuiltinRule {231    std::string content;232    std::vector<std::string> deps;233};234 235static std::unordered_map<std::string, BuiltinRule> PRIMITIVE_RULES = {236    {"boolean", {"(\"true\" | \"false\") space", {}}},237    {"decimal-part", {"[0-9]{1,16}", {}}},238    {"integral-part", {"[0] | [1-9] [0-9]{0,15}", {}}},239    {"number", {"(\"-\"? integral-part) (\".\" decimal-part)? ([eE] [-+]? integral-part)? space", {"integral-part", "decimal-part"}}},240    {"integer", {"(\"-\"? integral-part) space", {"integral-part"}}},241    {"value", {"object | array | string | number | boolean | null", {"object", "array", "string", "number", "boolean", "null"}}},242    {"object", {"\"{\" space ( string \":\" space value (\",\" space string \":\" space value)* )? \"}\" space", {"string", "value"}}},243    {"array", {"\"[\" space ( value (\",\" space value)* )? \"]\" space", {"value"}}},244    {"uuid", {"\"\\\"\" [0-9a-fA-F]{8} \"-\" [0-9a-fA-F]{4} \"-\" [0-9a-fA-F]{4} \"-\" [0-9a-fA-F]{4} \"-\" [0-9a-fA-F]{12} \"\\\"\" space", {}}},245    {"char",   {"[^\"\\\\\\x7F\\x00-\\x1F] | [\\\\] ([\"\\\\bfnrt] | \"u\" [0-9a-fA-F]{4})", {}}},246    {"string", {"\"\\\"\" char* \"\\\"\" space", {"char"}}},247    {"null", {"\"null\" space", {}}},248};249 250static std::unordered_map<std::string, BuiltinRule> STRING_FORMAT_RULES = {251    {"date", {"[0-9]{4} \"-\" ( \"0\" [1-9] | \"1\" [0-2] ) \"-\" ( \"0\" [1-9] | [1-2] [0-9] | \"3\" [0-1] )", {}}},252    {"time", {"([01] [0-9] | \"2\" [0-3]) \":\" [0-5] [0-9] \":\" [0-5] [0-9] ( \".\" [0-9]{3} )? ( \"Z\" | ( \"+\" | \"-\" ) ( [01] [0-9] | \"2\" [0-3] ) \":\" [0-5] [0-9] )", {}}},253    {"date-time", {"date \"T\" time", {"date", "time"}}},254    {"date-string", {"\"\\\"\" date \"\\\"\" space", {"date"}}},255    {"time-string", {"\"\\\"\" time \"\\\"\" space", {"time"}}},256    {"date-time-string", {"\"\\\"\" date-time \"\\\"\" space", {"date-time"}}}257};258 259static bool is_reserved_name(const std::string & name) {260    static const std::unordered_set<std::string> RESERVED_NAMES = [] {261        std::unordered_set<std::string> s;262        s.insert("root");263        for (const auto & p : PRIMITIVE_RULES) {264            s.insert(p.first);265        }266        for (const auto & p : STRING_FORMAT_RULES) {267            s.insert(p.first);268        }269        return s;270    }();271    return RESERVED_NAMES.find(name) != RESERVED_NAMES.end();272}273 274static std::regex INVALID_RULE_CHARS_RE("[^a-zA-Z0-9-]+");275static std::regex GRAMMAR_LITERAL_ESCAPE_RE("[\r\n\"\\\\]");276static std::regex GRAMMAR_RANGE_LITERAL_ESCAPE_RE("[\r\n\"\\]\\-\\\\]");277static std::unordered_map<char, std::string> GRAMMAR_LITERAL_ESCAPES = {278    {'\r', "\\r"}, {'\n', "\\n"}, {'"', "\\\""}, {'-', "\\-"}, {']', "\\]"}, {'\\', "\\\\"}279};280 281static std::unordered_set<char> NON_LITERAL_SET = {'|', '.', '(', ')', '[', ']', '{', '}', '*', '+', '?'};282static std::unordered_set<char> ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS = {'^', '$', '.', '[', ']', '(', ')', '|', '{', '}', '*', '+', '?'};283 284static std::string replacePattern(const std::string & input, const std::regex & regex, const std::function<std::string(const std::smatch  &)> & replacement) {285    std::smatch match;286    std::string result;287 288    std::string::const_iterator searchStart(input.cbegin());289    std::string::const_iterator searchEnd(input.cend());290 291    while (std::regex_search(searchStart, searchEnd, match, regex)) {292        result.append(searchStart, searchStart + match.position());293        result.append(replacement(match));294        searchStart = match.suffix().first;295    }296 297    result.append(searchStart, searchEnd);298 299    return result;300}301 302static std::string format_literal(const std::string & literal) {303    std::string escaped = replacePattern(literal, GRAMMAR_LITERAL_ESCAPE_RE, [&](const std::smatch & match) {304        char c = match.str()[0];305        return GRAMMAR_LITERAL_ESCAPES.at(c);306    });307    return "\"" + escaped + "\"";308}309 310std::string gbnf_format_literal(const std::string & literal) { return format_literal(literal); }311 312class common_schema_converter {313private:314    friend class common_schema_info;315    friend std::string build_grammar(const std::function<void(const common_grammar_builder &)> & cb, const common_grammar_options & options);316    std::function<json(const std::string &)> _fetch_json;317    bool _dotall;318    std::map<std::string, std::string> _rules;319    std::unordered_map<std::string, json> _refs;320    std::unordered_set<std::string> _refs_being_resolved;321    std::vector<std::string> _errors;322    std::vector<std::string> _warnings;323 324    std::string _add_rule(const std::string & name, const std::string & rule) {325        std::string esc_name = regex_replace(name, INVALID_RULE_CHARS_RE, "-");326        if (_rules.find(esc_name) == _rules.end() || _rules[esc_name] == rule) {327            _rules[esc_name] = rule;328            return esc_name;329        }330        int i = 0;331        while (_rules.find(esc_name + std::to_string(i)) != _rules.end() && _rules[esc_name + std::to_string(i)] != rule) {332            i++;333        }334        std::string key = esc_name + std::to_string(i);335        _rules[key] = rule;336        return key;337    }338 339    std::string _generate_union_rule(const std::string & name, const std::vector<json> & alt_schemas) {340        std::vector<std::string> rules;341        rules.reserve(alt_schemas.size());342        for (size_t i = 0; i < alt_schemas.size(); i++) {343            rules.push_back(visit(alt_schemas[i], name + (name.empty() ? "alternative-" : "-") + std::to_string(i)));344        }345        return string_join(rules, " | ");346    }347 348    std::string _visit_pattern(const std::string & pattern, const std::string & name) {349        if (!(pattern.front() == '^' && pattern.back() == '$')) {350            _errors.push_back("Pattern must start with '^' and end with '$'");351            return "";352        }353        std::string sub_pattern = pattern.substr(1, pattern.length() - 2);354        std::unordered_map<std::string, std::string> sub_rule_ids;355 356        size_t i = 0;357        size_t length = sub_pattern.length();358 359        using literal_or_rule = std::pair<std::string, bool>;360        auto to_rule = [&](const literal_or_rule & ls) {361            auto is_literal = ls.second;362            auto s = ls.first;363            return is_literal ? "\"" + s + "\"" : s;364        };365        std::function<literal_or_rule()> transform = [&]() -> literal_or_rule {366            size_t start = i;367            std::vector<literal_or_rule> seq;368 369            auto get_dot = [&]() {370                std::string rule;371                if (_dotall) {372                    rule = "[\\U00000000-\\U0010FFFF]";373                } else {374                    rule = "[^\\x0A\\x0D]";375                }376                return _add_rule("dot", rule);377            };378 379            // Joins the sequence, merging consecutive literals together.380            auto join_seq = [&]() {381                std::vector<literal_or_rule> ret;382 383                std::string literal;384                auto flush_literal = [&]() {385                    if (literal.empty()) {386                        return false;387                    }388                    ret.emplace_back(literal, true);389                    literal.clear();390                    return true;391                };392 393                for (const auto & item : seq) {394                    auto is_literal = item.second;395                    if (is_literal) {396                        literal += item.first;397                    } else {398                        flush_literal();399                        ret.push_back(item);400                    }401                }402                flush_literal();403 404                std::vector<std::string> results;405                results.reserve(ret.size());406                for (const auto & item : ret) {407                    results.push_back(to_rule(item));408                }409                return std::make_pair(string_join(results, " "), false);410            };411 412            while (i < length) {413                char c = sub_pattern[i];414                if (c == '.') {415                    seq.emplace_back(get_dot(), false);416                    i++;417                } else if (c == '(') {418                    i++;419                    if (i < length && sub_pattern[i] == '?') {420                        if (i + 1 < length && sub_pattern[i + 1] == ':') {421                            i += 2; // skip "?:" for non-capturing group, treat as regular group422                        } else {423                            // lookahead/lookbehind (?=, ?!, ?<=, ?<!) - not supported424                            _warnings.push_back("Unsupported pattern syntax");425                            // skip to matching ')' to avoid UB on empty seq426                            int depth = 1;427                            while (i < length && depth > 0) {428                                if (sub_pattern[i] == '\\' && i + 1 < length) {429                                    i += 2; // skip escaped character430                                } else {431                                    if (sub_pattern[i] == '(') depth++;432                                    else if (sub_pattern[i] == ')') depth--;433                                    i++;434                                }435                            }436                            continue;437                        }438                    }439                    seq.emplace_back("(" + to_rule(transform()) + ")", false);440                } else if (c == ')') {441                    i++;442                    if (start > 0 && sub_pattern[start - 1] != '(' && (start < 2 || sub_pattern[start - 2] != '?' || sub_pattern[start - 1] != ':')) {443                        _errors.push_back("Unbalanced parentheses");444                    }445                    return join_seq();446                } else if (c == '[') {447                    std::string square_brackets = std::string(1, c);448                    i++;449                    while (i < length && sub_pattern[i] != ']') {450                        if (sub_pattern[i] == '\\') {451                            square_brackets += sub_pattern.substr(i, 2);452                            i += 2;453                        } else {454                            square_brackets += sub_pattern[i];455                            i++;456                        }457                    }458                    if (i >= length) {459                        _errors.push_back("Unbalanced square brackets");460                    }461                    square_brackets += ']';462                    i++;463                    seq.emplace_back(square_brackets, false);464                } else if (c == '|') {465                    seq.emplace_back("|", false);466                    i++;467                } else if (c == '*' || c == '+' || c == '?') {468                    seq.back() = std::make_pair(to_rule(seq.back()) + c, false);469                    i++;470                } else if (c == '{') {471                    std::string curly_brackets = std::string(1, c);472                    i++;473                    while (i < length && sub_pattern[i] != '}') {474                        curly_brackets += sub_pattern[i];475                        i++;476                    }477                    if (i >= length) {478                        _errors.push_back("Unbalanced curly brackets");479                    }480                    curly_brackets += '}';481                    i++;482                    auto nums = string_split(curly_brackets.substr(1, curly_brackets.length() - 2), ",");483                    int min_times = 0;484                    int max_times = std::numeric_limits<int>::max();485                    try {486                        if (nums.size() == 1) {487                            min_times = max_times = std::stoi(nums[0]);488                        } else if (nums.size() != 2) {489                            _errors.push_back("Wrong number of values in curly brackets");490                        } else {491                            if (!nums[0].empty()) {492                                min_times = std::stoi(nums[0]);493                            }494                            if (!nums[1].empty()) {495                                max_times = std::stoi(nums[1]);496                            }497                        }498                    } catch (const std::invalid_argument & e) {499                        _errors.push_back("Invalid number in curly brackets");500                        return std::make_pair("", false);501                    }502                    auto &last = seq.back();503                    auto &sub = last.first;504                    auto sub_is_literal = last.second;505 506                    if (!sub_is_literal) {507                        std::string & sub_id = sub_rule_ids[sub];508                        if (sub_id.empty()) {509                            sub_id = _add_rule(name + "-" + std::to_string(sub_rule_ids.size()), sub);510                        }511                        sub = sub_id;512                    }513                    seq.back().first = build_repetition(514                        sub_is_literal ? "\"" + sub + "\"" : sub,515                        min_times,516                        max_times,517                        ""518                    );519                    seq.back().second = false;520                } else {521                    std::string literal;522                    auto is_non_literal = [&](char c) {523                        return NON_LITERAL_SET.find(c) != NON_LITERAL_SET.end();524                    };525                    while (i < length) {526                        if (sub_pattern[i] == '\\' && i < length - 1) {527                            char next = sub_pattern[i + 1];528                            if (ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS.find(next) != ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS.end()) {529                                i++;530                                literal += sub_pattern[i];531                                i++;532                            } else {533                                literal += sub_pattern.substr(i, 2);534                                i += 2;535                            }536                        } else if (sub_pattern[i] == '"') {537                            literal += "\\\"";538                            i++;539                        } else if (!is_non_literal(sub_pattern[i]) &&540                                (i == length - 1 || literal.empty() || sub_pattern[i + 1] == '.' || !is_non_literal(sub_pattern[i + 1]))) {541                            literal += sub_pattern[i];542                            i++;543                        } else {544                            break;545                        }546                    }547                    if (!literal.empty()) {548                        seq.emplace_back(literal, true);549                    }550                }551            }552            return join_seq();553        };554        return _add_rule(name, "\"\\\"\" (" + to_rule(transform()) + ") \"\\\"\" space");555    }556 557    /*558        Returns a rule that matches a JSON string that is none of the provided strings559 560        not_strings({"a"})561            -> ["] ( [a] char+ | [^"a] char* )? ["] space562        not_strings({"and", "also"})563            -> ["] ( [a] ([l] ([s] ([o] char+ | [^"o] char*) | [^"s] char*) | [n] ([d] char+ | [^"d] char*) | [^"ln] char*) | [^"a] char* )? ["] space564    */565    std::string _not_strings(const std::vector<std::string> & strings) {566 567        struct TrieNode {568            std::map<char, TrieNode> children;569            bool is_end_of_string;570 571            TrieNode() : is_end_of_string(false) {}572 573            void insert(const std::string & string) {574                auto *node = this;575                for (char c : string) {576                    node = &node->children[c];577                }578                node->is_end_of_string = true;579            }580        };581 582        TrieNode trie;583        for (const auto & s : strings) {584            trie.insert(s);585        }586 587        std::string char_rule = _add_primitive("char", PRIMITIVE_RULES.at("char"));588        std::ostringstream out;589        out << "[\"] ( ";590        std::function<void(const TrieNode &)> visit = [&](const TrieNode & node) {591            std::ostringstream rejects;592            auto first = true;593            for (const auto & kv : node.children) {594                rejects << kv.first;595                if (first) {596                    first = false;597                } else {598                    out << " | ";599                }600                out << "[" << kv.first << "]";601                if (!kv.second.children.empty()) {602                    out << " (";603                    visit(kv.second);604                    out << ")";605                } else if (kv.second.is_end_of_string) {606                    out << " " << char_rule << "+";607                }608            }609            if (!node.children.empty()) {610                if (!first) {611                    out << " | ";612                }613                out << "[^\"" << rejects.str() << "] " << char_rule << "*";614            }615        };616        visit(trie);617 618        out << " )";619        if (!trie.is_end_of_string) {620            out << "?";621        }622        out << " [\"] space";623        return out.str();624    }625 626    std::string _resolve_ref(const std::string & ref) {627        auto it = ref.find('#');628        std::string ref_fragment = it != std::string::npos ? ref.substr(it + 1) : ref;629        static const std::regex nonalphanumeric_regex(R"([^a-zA-Z0-9-]+)");630        std::string ref_name = "ref" + std::regex_replace(ref_fragment, nonalphanumeric_regex, "-");631        if (_rules.find(ref_name) == _rules.end() && _refs_being_resolved.find(ref) == _refs_being_resolved.end()) {632            _refs_being_resolved.insert(ref);633            json resolved = _refs[ref];634            ref_name = visit(resolved, ref_name);635            _refs_being_resolved.erase(ref);636        }637        return ref_name;638    }639 640    std::string _build_object_rule(641        const std::vector<std::pair<std::string, json>> & properties,642        const std::unordered_set<std::string> & required,643        const std::string & name,644        const json & additional_properties)645    {646        std::vector<std::string> required_props;647        std::vector<std::string> optional_props;648        std::unordered_map<std::string, std::string> prop_kv_rule_names;649        std::vector<std::string> prop_names;650        for (const auto & kv : properties) {651            const auto &prop_name = kv.first;652            const auto &prop_schema = kv.second;653 654            std::string prop_rule_name = visit(prop_schema, name + (name.empty() ? "" : "-") + prop_name);655            prop_kv_rule_names[prop_name] = _add_rule(656                name + (name.empty() ? "" : "-") + prop_name + "-kv",657                format_literal(json(prop_name).dump()) + " space \":\" space " + prop_rule_name658            );659            if (required.find(prop_name) != required.end()) {660                required_props.push_back(prop_name);661            } else {662                optional_props.push_back(prop_name);663            }664            prop_names.push_back(prop_name);665        }666        if ((additional_properties.is_boolean() && additional_properties.get<bool>()) || additional_properties.is_object()) {667            std::string sub_name = name + (name.empty() ? "" : "-") + "additional";668            std::string value_rule =669                additional_properties.is_object() ? visit(additional_properties, sub_name + "-value")670                : _add_primitive("value", PRIMITIVE_RULES.at("value"));671 672            auto key_rule =673                prop_names.empty() ? _add_primitive("string", PRIMITIVE_RULES.at("string"))674                : _add_rule(sub_name + "-k", _not_strings(prop_names));675            std::string kv_rule = _add_rule(sub_name + "-kv", key_rule + " \":\" space " + value_rule);676            prop_kv_rule_names["*"] = kv_rule;677            optional_props.push_back("*");678        }679 680        std::string rule = "\"{\" space ";681        for (size_t i = 0; i < required_props.size(); i++) {682            if (i > 0) {683                rule += " \",\" space ";684            }685            rule += prop_kv_rule_names[required_props[i]];686        }687 688        if (!optional_props.empty()) {689            rule += " (";690            if (!required_props.empty()) {691                rule += " \",\" space ( ";692            }693 694            std::function<std::string(const std::vector<std::string> &, bool)> get_recursive_refs = [&](const std::vector<std::string> & ks, bool first_is_optional) {695                std::string res;696                if (ks.empty()) {697                    return res;698                }699                const std::string& k = ks[0];700                std::string kv_rule_name = prop_kv_rule_names[k];701                std::string comma_ref = "( \",\" space " + kv_rule_name + " )";702                if (first_is_optional) {703                    res = comma_ref + (k == "*" ? "*" : "?");704                } else {705                    res = kv_rule_name + (k == "*" ? " " + comma_ref + "*" : "");706                }707                if (ks.size() > 1) {708                    res += " " + _add_rule(709                        name + (name.empty() ? "" : "-") + k + "-rest",710                        get_recursive_refs(std::vector<std::string>(ks.begin() + 1, ks.end()), true)711                    );712                }713                return res;714            };715 716            for (size_t i = 0; i < optional_props.size(); i++) {717                if (i > 0) {718                    rule += " | ";719                }720                rule += get_recursive_refs(std::vector<std::string>(optional_props.begin() + i, optional_props.end()), false);721            }722            if (!required_props.empty()) {723                rule += " )";724            }725            rule += " )?";726        }727 728        rule += " \"}\" space";729 730        return rule;731    }732 733    std::string _add_primitive(const std::string & name, const BuiltinRule & rule) {734        auto n = _add_rule(name, rule.content);735        for (const auto & dep : rule.deps) {736            BuiltinRule dep_rule;737            auto it = PRIMITIVE_RULES.find(dep);738            if (it == PRIMITIVE_RULES.end()) {739                it = STRING_FORMAT_RULES.find(dep);740                if (it == STRING_FORMAT_RULES.end()) {741                    _errors.push_back("Rule " + dep + " not known");742                    continue;743                }744            }745            if (_rules.find(dep) == _rules.end()) {746                _add_primitive(dep, it->second);747            }748        }749        return n;750    }751 752public:753    common_schema_converter(754        const std::function<json(const std::string &)> & fetch_json,755        bool dotall)756          : _fetch_json(fetch_json), _dotall(dotall)757    {758        _rules["space"] = SPACE_RULE;759    }760 761    void resolve_refs(json & schema, const std::string & url) {762        /*763        * Resolves all $ref fields in the given schema, fetching any remote schemas,764        * replacing each $ref with absolute reference URL and populates _refs with the765        * respective referenced (sub)schema dictionaries.766        */767        std::function<void(json &)> visit_refs = [&](json & n) {768            if (n.is_array()) {769                for (auto & x : n) {770                    visit_refs(x);771                }772            } else if (n.is_object()) {773                if (n.contains("$ref")) {774                    std::string ref = n["$ref"];775                    if (_refs.find(ref) == _refs.end()) {776                        json target;777                        if (ref.find("https://") == 0) {778                            std::string base_url = ref.substr(0, ref.find('#'));779                            auto it = _refs.find(base_url);780                            if (it != _refs.end()) {781                                target = it->second;782                            } else {783                                // Fetch the referenced schema and resolve its refs784                                auto referenced = _fetch_json(ref);785                                resolve_refs(referenced, base_url);786                                _refs[base_url] = referenced;787                            }788                            if (ref.find('#') == std::string::npos || ref.substr(ref.find('#') + 1).empty()) {789                                return;790                            }791                        } else if (ref.find("#/") == 0) {792                            target = schema;793                            n["$ref"] = url + ref;794                            ref = url + ref;795                        } else {796                            _errors.push_back("Unsupported ref: " + ref);797                            return;798                        }799                        std::string pointer = ref.substr(ref.find('#') + 1);800                        std::vector<std::string> tokens = string_split(pointer, "/");801                        for (size_t i = 1; i < tokens.size(); ++i) {802                            const std::string& sel = tokens[i];803                            if (target.is_object() && target.contains(sel)) {804                                target = target[sel];805                            } else if (target.is_array()) {806                                size_t sel_index;807                                try {808                                    sel_index = std::stoull(sel);809                                } catch (const std::invalid_argument & e) {810                                    sel_index = target.size();811                                }812                                if (sel_index >= target.size()) {813                                    _errors.push_back("Error resolving ref " + ref + ": " + sel + " not in " + target.dump());814                                    return;815                                }816                                target = target[sel_index];817                            } else {818                                _errors.push_back("Error resolving ref " + ref + ": " + sel + " not in " + target.dump());819                                return;820                            }821                        }822                        _refs[ref] = target;823                    }824                } else {825                    for (const auto & kv : n.items()) {826                        visit_refs(kv.value());827                    }828                }829            }830        };831 832        visit_refs(schema);833    }834 835    static std::string _generate_constant_rule(const json & value) {836        return format_literal(value.dump());837    }838 839    std::string visit(const json & schema, const std::string & name) {840        json schema_type = schema.contains("type") ? schema["type"] : json();841        std::string schema_format = schema.contains("format") ? schema["format"].get<std::string>() : "";842        std::string rule_name = is_reserved_name(name) ? name + "-" : name.empty() ? "root" : name;843 844        if (schema.contains("$ref")) {845            return _add_rule(rule_name, _resolve_ref(schema["$ref"]));846        }847        if (schema.contains("oneOf") || schema.contains("anyOf")) {848            std::vector<json> alt_schemas = schema.contains("oneOf") ? schema["oneOf"].get<std::vector<json>>() : schema["anyOf"].get<std::vector<json>>();849            return _add_rule(rule_name, _generate_union_rule(name, alt_schemas));850        }851        if (schema_type.is_array()) {852            std::vector<json> schema_types;853            for (const auto & t : schema_type) {854                json schema_copy(schema);855                schema_copy["type"] = t;856                schema_types.push_back(schema_copy);857            }858            return _add_rule(rule_name, _generate_union_rule(name, schema_types));859        }860        if (schema.contains("const")) {861            return _add_rule(rule_name, _generate_constant_rule(schema["const"]) + " space");862        }863        if (schema.contains("enum")) {864            std::vector<std::string> enum_values;865            for (const auto & v : schema["enum"]) {866                enum_values.push_back(_generate_constant_rule(v));867            }868            return _add_rule(rule_name, "(" + string_join(enum_values, " | ") + ") space");869        }870        if ((schema_type.is_null() || schema_type == "object")871                && (schema.contains("properties") ||872                    (schema.contains("additionalProperties") && schema["additionalProperties"] != true))) {873            std::unordered_set<std::string> required;874            if (schema.contains("required") && schema["required"].is_array()) {875                for (const auto & item : schema["required"]) {876                    if (item.is_string()) {877                        required.insert(item.get<std::string>());878                    }879                }880            }881            std::vector<std::pair<std::string, json>> properties;882            if (schema.contains("properties")) {883                for (const auto & prop : schema["properties"].items()) {884                    properties.emplace_back(prop.key(), prop.value());885                }886            }887            return _add_rule(rule_name,888                _build_object_rule(889                    properties, required, name,890                    schema.contains("additionalProperties") ? schema["additionalProperties"] : json()));891        }892        if ((schema_type.is_null() || schema_type == "object" || schema_type == "string") && schema.contains("allOf")) {893            std::unordered_set<std::string> required;894            std::vector<std::pair<std::string, json>> properties;895            std::map<std::string, size_t> enum_values;896            const std::string& hybrid_name = name;897            std::function<void(const json &, bool)> add_component = [&](const json & comp_schema, bool is_required) {898                if (comp_schema.contains("$ref")) {899                    add_component(_refs[comp_schema["$ref"]], is_required);900                } else if (comp_schema.contains("properties")) {901                    for (const auto & prop : comp_schema["properties"].items()) {902                        properties.emplace_back(prop.key(), prop.value());903                        if (is_required) {904                            required.insert(prop.key());905                        }906                    }907                } else if (comp_schema.contains("enum")) {908                    for (const auto & v : comp_schema["enum"]) {909                        const auto rule = _generate_constant_rule(v);910                        if (enum_values.find(rule) == enum_values.end()) {911                            enum_values[rule] = 0;912                        }913                        enum_values[rule] += 1;914                    }915                } else {916                  // todo warning917                }918            };919            for (const auto & t : schema["allOf"]) {920                if (t.contains("anyOf")) {921                    for (const auto & tt : t["anyOf"]) {922                        add_component(tt, false);923                    }924                } else {925                    add_component(t, true);926                }927            }928            if (!enum_values.empty()) {929                std::vector<std::string> enum_intersection;930                for (const auto & p : enum_values) {931                    if (p.second == schema["allOf"].size()) {932                        enum_intersection.push_back(p.first);933                    }934                }935                if (!enum_intersection.empty()) {936                    return _add_rule(rule_name, "(" + string_join(enum_intersection, " | ") + ") space");937                }938            }939            return _add_rule(rule_name, _build_object_rule(properties, required, hybrid_name, json()));940        }941        if ((schema_type.is_null() || schema_type == "array") && (schema.contains("items") || schema.contains("prefixItems"))) {942            json items = schema.contains("items") ? schema["items"] : schema["prefixItems"];943            if (items.is_array()) {944                std::string rule = "\"[\" space ";945                for (size_t i = 0; i < items.size(); i++) {946                    if (i > 0) {947                        rule += " \",\" space ";948                    }949                    rule += visit(items[i], name + (name.empty() ? "" : "-") + "tuple-" + std::to_string(i));950                }951                rule += " \"]\" space";952                return _add_rule(rule_name, rule);953            }954            std::string item_rule_name = visit(items, name + (name.empty() ? "" : "-") + "item");955            int min_items = schema.contains("minItems") ? schema["minItems"].get<int>() : 0;956            json max_items_json = schema.contains("maxItems") ? schema["maxItems"] : json();957            int max_items = max_items_json.is_number_integer() ? max_items_json.get<int>() : std::numeric_limits<int>::max();958 959            return _add_rule(rule_name, "\"[\" space " + build_repetition(item_rule_name, min_items, max_items, "\",\" space") + " \"]\" space");960        }961        if ((schema_type.is_null() || schema_type == "string") && schema.contains("pattern")) {962            return _visit_pattern(schema["pattern"], rule_name);963        }964        if ((schema_type.is_null() || schema_type == "string") && std::regex_match(schema_format, std::regex("^uuid[1-5]?$"))) {965            return _add_primitive(rule_name == "root" ? "root" : schema_format, PRIMITIVE_RULES.at("uuid"));966        }967        if ((schema_type.is_null() || schema_type == "string") && STRING_FORMAT_RULES.find(schema_format + "-string") != STRING_FORMAT_RULES.end()) {968            auto prim_name = schema_format + "-string";969            return _add_rule(rule_name, _add_primitive(prim_name, STRING_FORMAT_RULES.at(prim_name)));970        }971        if (schema_type == "string" && (schema.contains("minLength") || schema.contains("maxLength"))) {972            std::string char_rule = _add_primitive("char", PRIMITIVE_RULES.at("char"));973            int min_len = schema.contains("minLength") ? schema["minLength"].get<int>() : 0;974            int max_len = schema.contains("maxLength") ? schema["maxLength"].get<int>() : std::numeric_limits<int>::max();975            return _add_rule(rule_name, "\"\\\"\" " + build_repetition(char_rule, min_len, max_len) + " \"\\\"\" space");976        }977        if (schema_type == "integer" && (schema.contains("minimum") || schema.contains("exclusiveMinimum") || schema.contains("maximum") || schema.contains("exclusiveMaximum"))) {978            int64_t min_value = std::numeric_limits<int64_t>::min();979            int64_t max_value = std::numeric_limits<int64_t>::max();980            if (schema.contains("minimum")) {981                min_value = schema["minimum"].get<int64_t>();982            } else if (schema.contains("exclusiveMinimum")) {983                min_value = schema["exclusiveMinimum"].get<int64_t>() + 1;984            }985            if (schema.contains("maximum")) {986                max_value = schema["maximum"].get<int64_t>();987            } else if (schema.contains("exclusiveMaximum")) {988                max_value = schema["exclusiveMaximum"].get<int64_t>() - 1;989            }990            std::stringstream out;991            out << "(";992            build_min_max_int(min_value, max_value, out);993            out << ") space";994            return _add_rule(rule_name, out.str());995        }996        if (schema.empty() || schema_type == "object") {997            return _add_rule(rule_name, _add_primitive("object", PRIMITIVE_RULES.at("object")));998        }999        if (schema_type.is_null() && schema.is_object()) {1000            // No type constraint and no recognized structural keywords (e.g. {"description": "..."}).1001            // Per JSON Schema semantics this is equivalent to {} and accepts any value.1002            return _add_rule(rule_name, _add_primitive("value", PRIMITIVE_RULES.at("value")));1003        }1004        if (!schema_type.is_string() || PRIMITIVE_RULES.find(schema_type.get<std::string>()) == PRIMITIVE_RULES.end()) {1005            _errors.push_back("Unrecognized schema: " + schema.dump());1006            return "";1007        }1008        // TODO: support minimum, maximum, exclusiveMinimum, exclusiveMaximum at least for zero1009        return _add_primitive(rule_name == "root" ? "root" : schema_type.get<std::string>(), PRIMITIVE_RULES.at(schema_type.get<std::string>()));1010    }1011 1012    void check_errors() {1013        if (!_errors.empty()) {1014            throw std::invalid_argument("JSON schema conversion failed:\n" + string_join(_errors, "\n"));1015        }1016        if (!_warnings.empty()) {1017            fprintf(stderr, "WARNING: JSON schema conversion was incomplete: %s\n", string_join(_warnings, "; ").c_str());1018        }1019    }1020 1021    std::string format_grammar() {1022        std::stringstream ss;1023        for (const auto & kv : _rules) {1024            ss << kv.first << " ::= " << kv.second << '\n';1025        }1026        return ss.str();1027    }1028};1029 1030// common_schema_info implementation (pimpl)1031 1032common_schema_info::common_schema_info()1033    : impl_(std::make_unique<common_schema_converter>(1034        [](const std::string &) { return json(); },1035        false)) {}1036 1037common_schema_info::~common_schema_info() = default;1038 1039common_schema_info::common_schema_info(common_schema_info &&) noexcept = default;1040common_schema_info & common_schema_info::operator=(common_schema_info &&) noexcept = default;1041 1042void common_schema_info::resolve_refs(nlohmann::ordered_json & schema) {1043    impl_->resolve_refs(schema, "");1044}1045 1046// Determines if a JSON schema can resolve to a string type through any path.1047// Some models emit raw string values rather than JSON-encoded strings for string parameters.1048// If any branch of the schema (via oneOf, anyOf, $ref, etc.) permits a string, this returns1049// true, allowing callers to handle the value as a raw string for simplicity.1050bool common_schema_info::resolves_to_string(const nlohmann::ordered_json & schema) {1051    std::unordered_set<std::string> visited_refs;1052 1053    std::function<bool(const json &)> check = [&](const json & s) -> bool {1054        if (!s.is_object()) {1055            return false;1056        }1057 1058        // Handle $ref1059        if (s.contains("$ref")) {1060            const std::string & ref = s["$ref"];1061            if (visited_refs.find(ref) != visited_refs.end()) {1062                // Circular reference, assume not a string to be safe1063                return false;1064            }1065            visited_refs.insert(ref);1066            auto it = impl_->_refs.find(ref);1067            if (it != impl_->_refs.end()) {1068                return check(it->second);1069            }1070            return false;1071        }1072 1073        // Check type field1074        if (s.contains("type")) {1075            const json & schema_type = s["type"];1076            if (schema_type.is_string()) {1077                if (schema_type == "string") {1078                    return true;1079                }1080            } else if (schema_type.is_array()) {1081                // Type can be an array like ["string", "null"]1082                for (const auto & t : schema_type) {1083                    if (t == "string") {1084                        return true;1085                    }1086                }1087            }1088        }1089 1090        // Check oneOf/anyOf - if any alternative can be a string1091        if (s.contains("oneOf")) {1092            for (const auto & alt : s["oneOf"]) {1093                if (check(alt)) {1094                    return true;1095                }1096            }1097        }1098        if (s.contains("anyOf")) {1099            for (const auto & alt : s["anyOf"]) {1100                if (check(alt)) {1101                    return true;1102                }1103            }1104        }1105 1106        // Check allOf - all components must be compatible with string type1107        if (s.contains("allOf")) {1108            bool all_string = true;1109            for (const auto & component : s["allOf"]) {1110                if (!check(component)) {1111                    all_string = false;1112                    break;1113                }1114            }1115            if (all_string) {1116                return true;1117            }1118        }1119 1120        // Check const - if the constant value is a string1121        if (s.contains("const")) {1122            if (s["const"].is_string()) {1123                return true;1124            }1125        }1126 1127        // Check enum - if any enum value is a string1128        if (s.contains("enum")) {1129            for (const auto & val : s["enum"]) {1130                if (val.is_string()) {1131                    return true;1132                }1133            }1134        }1135 1136        // String-specific keywords imply string type1137        if (s.contains("pattern") || s.contains("minLength") || s.contains("maxLength")) {1138            return true;1139        }1140 1141        // Check format - many formats imply string1142        if (s.contains("format")) {1143            const std::string & fmt = s["format"];1144            if (fmt == "date" || fmt == "time" || fmt == "date-time" ||1145                fmt == "uri" || fmt == "email" || fmt == "hostname" ||1146                fmt == "ipv4" || fmt == "ipv6" || fmt == "uuid" ||1147                fmt.find("uuid") == 0) {1148                return true;1149            }1150        }1151 1152        return false;1153    };1154 1155    return check(schema);1156}1157 1158std::string json_schema_to_grammar(const json & schema, bool force_gbnf) {1159#ifdef LLAMA_USE_LLGUIDANCE1160    if (!force_gbnf) {1161        return "%llguidance {}\nstart: %json " + schema.dump();1162    }1163#else1164    (void)force_gbnf;1165#endif // LLAMA_USE_LLGUIDANCE1166    return build_grammar([&](const common_grammar_builder & callbacks) {1167        auto copy = schema;1168        callbacks.resolve_refs(copy);1169        callbacks.add_schema("", copy);1170    });1171}1172 1173std::string build_grammar(const std::function<void(const common_grammar_builder &)> & cb, const common_grammar_options & options) {1174    common_schema_converter converter([&](const std::string &) { return json(); }, options.dotall);1175    common_grammar_builder builder {1176        /* .add_rule = */ [&](const std::string & name, const std::string & rule) {1177            return converter._add_rule(name, rule);1178        },1179        /* .add_schema = */ [&](const std::string & name, const nlohmann::ordered_json & schema) {1180            return converter.visit(schema, name == "root" ? "" : name);1181        },1182        /* .resolve_refs = */ [&](nlohmann::ordered_json & schema) {1183            converter.resolve_refs(schema, "");1184        }1185    };1186    cb(builder);1187    converter.check_errors();1188    return converter.format_grammar();1189}1190