Felipe97/llama-cpp-compiled
01.1k
1#include "json-schema-to-grammar.h"2#include "common.h"3#include "trie.h"4#include "unicode.h"5 6#include <algorithm>7#include <limits>8#include <map>9#include <regex>10#include <sstream>11#include <string>12#include <unordered_map>13#include <unordered_set>14#include <vector>15 16using json = common_json;17 18static std::string build_repetition(const std::string & item_rule, int min_items, int max_items, const std::string & separator_rule = "") {19 auto has_max = max_items != std::numeric_limits<int>::max();20 21 if (max_items == 0) {22 return "";23 }24 if (min_items == 0 && max_items == 1) {25 return item_rule + "?";26 }27 28 if (separator_rule.empty()) {29 if (min_items == 1 && !has_max) {30 return item_rule + "+";31 }32 if (min_items == 0 && !has_max) {33 return item_rule + "*";34 }35 return item_rule + "{" + std::to_string(min_items) + "," + (has_max ? std::to_string(max_items) : "") + "}";36 }37 38 auto result = item_rule + " " + build_repetition("(" + separator_rule + " " + item_rule + ")", min_items == 0 ? 0 : min_items - 1, has_max ? max_items - 1 : max_items);39 if (min_items == 0) {40 result = "(" + result + ")?";41 }42 return result;43}44 45static void build_min_max_int(int64_t min_value, int64_t max_value, std::stringstream & out, int decimals_left = 16, bool top_level = true) {46 auto has_min = min_value != std::numeric_limits<int64_t>::min();47 auto has_max = max_value != std::numeric_limits<int64_t>::max();48 49 auto digit_range = [&](char from, char to) {50 out << "[";51 if (from == to) {52 out << from;53 } else {54 out << from << "-" << to;55 }56 out << "]";57 };58 auto more_digits = [&](int min_digits, int max_digits) {59 out << "[0-9]";60 if (min_digits == max_digits && min_digits == 1) {61 return;62 }63 out << "{";64 out << min_digits;65 if (max_digits != min_digits) {66 out << ",";67 if (max_digits != std::numeric_limits<int>::max()) {68 out << max_digits;69 }70 }71 out << "}";72 };73 std::function<void(const std::string_view &, const std::string_view &)> uniform_range =74 [&](const std::string_view & from, const std::string_view & to) {75 size_t i = 0;76 while (i < from.length() && i < to.length() && from[i] == to[i]) {77 i++;78 }79 if (i > 0) {80 out << "\"" << from.substr(0, i) << "\"";81 }82 if (i < from.length() && i < to.length()) {83 if (i > 0) {84 out << " ";85 }86 auto sub_len = from.length() - i - 1;87 if (sub_len > 0) {88 auto from_sub = from.substr(i + 1);89 auto to_sub = to.substr(i + 1);90 auto sub_zeros = string_repeat("0", sub_len);91 auto sub_nines = string_repeat("9", sub_len);92 93 auto to_reached = false;94 out << "(";95 if (from_sub == sub_zeros) {96 digit_range(from[i], to[i] - 1);97 out << " ";98 more_digits(sub_len, sub_len);99 } else {100 out << "[" << from[i] << "] ";101 out << "(";102 uniform_range(from_sub, sub_nines);103 out << ")";104 if (from[i] < to[i] - 1) {105 out << " | ";106 if (to_sub == sub_nines) {107 digit_range(from[i] + 1, to[i]);108 to_reached = true;109 } else {110 digit_range(from[i] + 1, to[i] - 1);111 }112 out << " ";113 more_digits(sub_len, sub_len);114 }115 }116 if (!to_reached) {117 out << " | ";118 digit_range(to[i], to[i]);119 out << " ";120 uniform_range(sub_zeros, to_sub);121 }122 out << ")";123 } else {124 out << "[" << from[i] << "-" << to[i] << "]";125 }126 }127 };128 129 if (has_min && has_max) {130 if (min_value < 0 && max_value < 0) {131 out << "\"-\" (";132 build_min_max_int(-max_value, -min_value, out, decimals_left, /* top_level= */ true);133 out << ")";134 return;135 }136 137 if (min_value < 0) {138 out << "\"-\" (";139 build_min_max_int(0, -min_value, out, decimals_left, /* top_level= */ true);140 out << ") | ";141 min_value = 0;142 }143 144 auto min_s = std::to_string(min_value);145 auto max_s = std::to_string(max_value);146 auto min_digits = min_s.length();147 auto max_digits = max_s.length();148 149 for (auto digits = min_digits; digits < max_digits; digits++) {150 uniform_range(min_s, string_repeat("9", digits));151 min_s = "1" + string_repeat("0", digits);152 out << " | ";153 }154 uniform_range(min_s, max_s);155 return;156 }157 158 auto less_decimals = std::max(decimals_left - 1, 1);159 160 if (has_min) {161 if (min_value < 0) {162 out << "\"-\" (";163 build_min_max_int(std::numeric_limits<int64_t>::min(), -min_value, out, decimals_left, /* top_level= */ false);164 out << ") | [0] | [1-9] ";165 more_digits(0, decimals_left - 1);166 } else if (min_value == 0) {167 if (top_level) {168 out << "[0] | [1-9] ";169 more_digits(0, less_decimals);170 } else {171 more_digits(1, decimals_left);172 }173 } else if (min_value <= 9) {174 char c = '0' + min_value;175 auto range_start = top_level ? '1' : '0';176 if (c > range_start) {177 digit_range(range_start, c - 1);178 out << " ";179 more_digits(1, less_decimals);180 out << " | ";181 }182 digit_range(c, '9');183 out << " ";184 more_digits(0, less_decimals);185 } else {186 auto min_s = std::to_string(min_value);187 auto len = min_s.length();188 auto c = min_s[0];189 190 if (c > '1') {191 digit_range(top_level ? '1' : '0', c - 1);192 out << " ";193 more_digits(len, less_decimals);194 out << " | ";195 }196 digit_range(c, c);197 out << " (";198 build_min_max_int(std::stoll(min_s.substr(1)), std::numeric_limits<int64_t>::max(), out, less_decimals, /* top_level= */ false);199 out << ")";200 if (c < '9') {201 out << " | ";202 digit_range(c + 1, '9');203 out << " ";204 more_digits(len - 1, less_decimals);205 }206 }207 return;208 }209 210 if (has_max) {211 if (max_value >= 0) {212 if (top_level) {213 out << "\"-\" [1-9] ";214 more_digits(0, less_decimals);215 out << " | ";216 }217 build_min_max_int(0, max_value, out, decimals_left, /* top_level= */ true);218 } else {219 out << "\"-\" (";220 build_min_max_int(-max_value, std::numeric_limits<int64_t>::max(), out, decimals_left, /* top_level= */ false);221 out << ")";222 }223 return;224 }225 226 throw std::runtime_error("At least one of min_value or max_value must be set");227}228 229const std::string SPACE_RULE = "| \" \" | \"\\n\"{1,2} [ \\t]{0,20}";230 231struct BuiltinRule {232 std::string content;233 std::vector<std::string> deps;234};235 236static std::unordered_map<std::string, BuiltinRule> PRIMITIVE_RULES = {237 {"boolean", {"(\"true\" | \"false\")", {}}},238 {"decimal-part", {"[0-9]{1,16}", {}}},239 {"integral-part", {"[0] | [1-9] [0-9]{0,15}", {}}},240 {"number", {"(\"-\"? integral-part) (\".\" decimal-part)? ([eE] [-+]? integral-part)?", {"integral-part", "decimal-part"}}},241 {"integer", {"(\"-\"? integral-part)", {"integral-part"}}},242 {"value", {"object | array | string | number | boolean | null", {"object", "array", "string", "number", "boolean", "null"}}},243 {"object", {"\"{\" space ( string \":\" space value (\",\" space string \":\" space value)* )? space \"}\"", {"string", "value"}}},244 {"array", {"\"[\" space ( value (\",\" space value)* )? space \"]\"", {"value"}}},245 {"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} \"\\\"\"", {}}},246 {"char", {"[^\"\\\\\\x7F\\x00-\\x1F] | [\\\\] ([\"\\\\bfnrt] | \"u\" [0-9a-fA-F]{4})", {}}},247 {"string", {"\"\\\"\" char* \"\\\"\"", {"char"}}},248 {"null", {"\"null\"", {}}},249};250 251static std::unordered_map<std::string, BuiltinRule> STRING_FORMAT_RULES = {252 {"date", {"[0-9]{4} \"-\" ( \"0\" [1-9] | \"1\" [0-2] ) \"-\" ( \"0\" [1-9] | [1-2] [0-9] | \"3\" [0-1] )", {}}},253 {"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] )", {}}},254 {"date-time", {"date \"T\" time", {"date", "time"}}},255 {"date-string", {"\"\\\"\" date \"\\\"\"", {"date"}}},256 {"time-string", {"\"\\\"\" time \"\\\"\"", {"time"}}},257 {"date-time-string", {"\"\\\"\" date-time \"\\\"\"", {"date-time"}}}258};259 260static bool is_reserved_name(const std::string & name) {261 static const std::unordered_set<std::string> RESERVED_NAMES = [] {262 std::unordered_set<std::string> s;263 s.insert("root");264 for (const auto & p : PRIMITIVE_RULES) {265 s.insert(p.first);266 }267 for (const auto & p : STRING_FORMAT_RULES) {268 s.insert(p.first);269 }270 return s;271 }();272 return RESERVED_NAMES.find(name) != RESERVED_NAMES.end();273}274 275static std::regex INVALID_RULE_CHARS_RE("[^a-zA-Z0-9-]+");276static std::regex GRAMMAR_LITERAL_ESCAPE_RE("[\r\n\"\\\\]");277static std::regex GRAMMAR_RANGE_LITERAL_ESCAPE_RE("[\r\n\"\\]\\-\\\\]");278static std::unordered_map<char, std::string> GRAMMAR_LITERAL_ESCAPES = {279 {'\r', "\\r"}, {'\n', "\\n"}, {'"', "\\\""}, {'-', "\\-"}, {']', "\\]"}, {'\\', "\\\\"}280};281 282static const int MAX_PATTERN_DEPTH = 100;283 284static std::unordered_set<char> NON_LITERAL_SET = {'|', '.', '(', ')', '[', ']', '{', '}', '*', '+', '?', '^', '$'};285static std::unordered_set<char> ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS = {'^', '$', '.', '[', ']', '(', ')', '|', '{', '}', '*', '+', '?'};286 287static std::string replacePattern(const std::string & input, const std::regex & regex, const std::function<std::string(const std::smatch &)> & replacement) {288 std::smatch match;289 std::string result;290 291 std::string::const_iterator searchStart(input.cbegin());292 std::string::const_iterator searchEnd(input.cend());293 294 while (std::regex_search(searchStart, searchEnd, match, regex)) {295 result.append(searchStart, searchStart + match.position());296 result.append(replacement(match));297 searchStart = match.suffix().first;298 }299 300 result.append(searchStart, searchEnd);301 302 return result;303}304 305static std::string format_literal(const std::string & literal) {306 std::string escaped = replacePattern(literal, GRAMMAR_LITERAL_ESCAPE_RE, [&](const std::smatch & match) {307 char c = match.str()[0];308 return GRAMMAR_LITERAL_ESCAPES.at(c);309 });310 return "\"" + escaped + "\"";311}312 313std::string gbnf_format_literal(const std::string & literal) { return format_literal(literal); }314 315static size_t gbnf_escape_length(const std::string & pattern, size_t pos) {316 if (pos + 1 >= pattern.length() || pattern[pos] != '\\') {317 return 0;318 }319 size_t n_hex = 0;320 switch (pattern[pos + 1]) {321 case 'x': n_hex = 2; break;322 case 'u': n_hex = 4; break;323 case 'U': n_hex = 8; break;324 // keep in sync with parse_char() in src/llama-grammar.cpp325 case 't': case 'r': case 'n': case '\\': case '"': case '[': case ']': case '-':326 return 2;327 default:328 return 0;329 }330 if (pos + 2 + n_hex > pattern.length()) {331 return 0;332 }333 for (size_t i = pos + 2; i < pos + 2 + n_hex; i++) {334 char h = pattern[i];335 if (!((h >= '0' && h <= '9') || (h >= 'a' && h <= 'f') || (h >= 'A' && h <= 'F'))) {336 return 0;337 }338 }339 return 2 + n_hex;340}341 342class common_chat_schema_converter {343private:344 friend std::string build_grammar(const std::function<void(const common_grammar_builder &)> & cb, const common_grammar_options & options);345 bool _dotall;346 std::map<std::string, std::string> _rules;347 std::unordered_set<std::string> _refs_being_resolved;348 std::vector<std::string> _errors;349 std::vector<std::string> _warnings;350 351 template <typename T>352 static const T & as(const common_chat_schema & node) {353 return static_cast<const T &>(node);354 }355 356 std::string _add_rule(const std::string & name, const std::string & rule) {357 std::string esc_name = regex_replace(name, INVALID_RULE_CHARS_RE, "-");358 if (_rules.find(esc_name) == _rules.end() || _rules[esc_name] == rule) {359 _rules[esc_name] = rule;360 return esc_name;361 }362 int i = 0;363 while (_rules.find(esc_name + std::to_string(i)) != _rules.end() && _rules[esc_name + std::to_string(i)] != rule) {364 i++;365 }366 std::string key = esc_name + std::to_string(i);367 _rules[key] = rule;368 return key;369 }370 371 std::string _generate_union_rule(const std::string & name, const std::vector<common_chat_schema_ptr> & alt_schemas) {372 std::vector<std::string> rules;373 rules.reserve(alt_schemas.size());374 for (size_t i = 0; i < alt_schemas.size(); i++) {375 rules.push_back(visit(*alt_schemas[i], name + (name.empty() ? "alternative-" : "-") + std::to_string(i)));376 }377 return string_join(rules, " | ");378 }379 380 // thrown when the pattern is a valid regex with no grammar equivalent381 struct unsupported_pattern : public std::runtime_error {382 using std::runtime_error::runtime_error;383 };384 385 // thrown when the pattern is not a valid regex386 struct invalid_pattern : public std::runtime_error {387 using std::runtime_error::runtime_error;388 };389 390 std::string _visit_pattern(const std::string & pattern, const std::string & name) {391 auto rules_snapshot = _rules;392 try {393 return _pattern_to_rule(pattern, name);394 } catch (const unsupported_pattern & err) {395 // revert rules396 _rules = std::move(rules_snapshot);397 _warnings.push_back("pattern " + pattern + " is not supported (" + err.what() + "), accepting any string");398 return _add_rule(name, _add_primitive("string", PRIMITIVE_RULES.at("string")));399 } catch (const invalid_pattern & err) {400 _rules = std::move(rules_snapshot);401 _errors.push_back("Invalid pattern " + pattern + ": " + err.what());402 return "";403 }404 }405 406 std::string _pattern_to_rule(const std::string & pattern, const std::string & name) {407 if (pattern.length() < 2 || pattern.front() != '^' || pattern.back() != '$') {408 throw unsupported_pattern("not anchored with '^' and '$'");409 }410 std::string sub_pattern = pattern.substr(1, pattern.length() - 2);411 std::unordered_map<std::string, std::string> sub_rule_ids;412 413 size_t i = 0;414 size_t length = sub_pattern.length();415 int paren_depth = 0;416 417 using literal_or_rule = std::pair<std::string, bool>;418 auto to_rule = [&](const literal_or_rule & ls) {419 auto is_literal = ls.second;420 auto s = ls.first;421 return is_literal ? "\"" + s + "\"" : s;422 };423 std::function<literal_or_rule()> transform = [&]() -> literal_or_rule {424 std::vector<literal_or_rule> seq;425 426 auto get_dot = [&]() {427 std::string rule;428 if (_dotall) {429 rule = "[\\U00000000-\\U0010FFFF]";430 } else {431 rule = "[^\\x0A\\x0D]";432 }433 return _add_rule("dot", rule);434 };435 436 // Joins the sequence, merging consecutive literals together.437 auto join_seq = [&]() {438 std::vector<literal_or_rule> ret;439 440 std::string literal;441 auto flush_literal = [&]() {442 if (literal.empty()) {443 return false;444 }445 ret.emplace_back(literal, true);446 literal.clear();447 return true;448 };449 450 for (const auto & item : seq) {451 auto is_literal = item.second;452 if (is_literal) {453 literal += item.first;454 } else {455 flush_literal();456 ret.push_back(item);457 }458 }459 flush_literal();460 461 std::vector<std::string> results;462 results.reserve(ret.size());463 for (const auto & item : ret) {464 results.push_back(to_rule(item));465 }466 return std::make_pair(string_join(results, " "), false);467 };468 469 while (i < length) {470 char c = sub_pattern[i];471 if (c == '.') {472 seq.emplace_back(get_dot(), false);473 i++;474 } else if (c == '(') {475 i++;476 if (i < length && sub_pattern[i] == '?') {477 if (i + 1 < length && sub_pattern[i + 1] == ':') {478 i += 2; // skip "?:" for non-capturing group, treat as regular group479 } else {480 // lookaround, named group, inline flags, ...481 throw unsupported_pattern("unsupported group syntax");482 }483 }484 paren_depth++;485 if (paren_depth > MAX_PATTERN_DEPTH) {486 throw unsupported_pattern("pattern nesting too deep");487 }488 seq.emplace_back("(" + to_rule(transform()) + ")", false);489 } else if (c == ')') {490 i++;491 if (paren_depth == 0) {492 throw invalid_pattern("unbalanced parentheses");493 }494 paren_depth--;495 return join_seq();496 } else if (c == '^' || c == '$') {497 throw unsupported_pattern("anchor inside the pattern");498 } else if (c == '[') {499 std::string square_brackets = std::string(1, c);500 i++;501 while (i < length && sub_pattern[i] != ']') {502 if (sub_pattern[i] == '\\') {503 auto escape_length = gbnf_escape_length(sub_pattern, i);504 if (escape_length == 0) {505 throw unsupported_pattern("unsupported escape in character class: " + sub_pattern.substr(i, 2));506 }507 square_brackets += sub_pattern.substr(i, escape_length);508 i += escape_length;509 } else {510 square_brackets += sub_pattern[i];511 i++;512 }513 }514 if (i >= length) {515 throw invalid_pattern("unterminated character class");516 }517 square_brackets += ']';518 i++;519 seq.emplace_back(square_brackets, false);520 } else if (c == '|') {521 seq.emplace_back("|", false);522 i++;523 } else if (c == '*' || c == '+' || c == '?') {524 if (seq.empty()) {525 throw invalid_pattern("nothing to repeat");526 }527 seq.back() = std::make_pair(to_rule(seq.back()) + c, false);528 i++;529 } else if (c == '{') {530 std::string curly_brackets = std::string(1, c);531 i++;532 while (i < length && sub_pattern[i] != '}') {533 curly_brackets += sub_pattern[i];534 i++;535 }536 if (i >= length) {537 throw unsupported_pattern("unterminated curly brackets");538 }539 curly_brackets += '}';540 i++;541 auto nums = string_split(curly_brackets.substr(1, curly_brackets.length() - 2), ",");542 int min_times = 0;543 int max_times = std::numeric_limits<int>::max();544 if (nums.size() != 1 && nums.size() != 2) {545 throw unsupported_pattern("wrong number of values in curly brackets");546 }547 try {548 if (nums.size() == 1) {549 min_times = max_times = std::stoi(nums[0]);550 } else {551 if (!nums[0].empty()) {552 min_times = std::stoi(nums[0]);553 }554 if (!nums[1].empty()) {555 max_times = std::stoi(nums[1]);556 }557 }558 } catch (const std::logic_error &) {559 throw unsupported_pattern("invalid number in curly brackets");560 }561 if (seq.empty()) {562 throw invalid_pattern("nothing to repeat");563 }564 auto &last = seq.back();565 auto &sub = last.first;566 auto sub_is_literal = last.second;567 568 if (!sub_is_literal) {569 std::string & sub_id = sub_rule_ids[sub];570 if (sub_id.empty()) {571 sub_id = _add_rule(name + "-" + std::to_string(sub_rule_ids.size()), sub);572 }573 sub = sub_id;574 }575 seq.back().first = build_repetition(576 sub_is_literal ? "\"" + sub + "\"" : sub,577 min_times,578 max_times,579 ""580 );581 seq.back().second = false;582 } else {583 std::string literal;584 auto is_non_literal = [&](char c) {585 return NON_LITERAL_SET.find(c) != NON_LITERAL_SET.end();586 };587 while (i < length) {588 if (sub_pattern[i] == '\\') {589 if (i == length - 1) {590 throw invalid_pattern("trailing backslash");591 }592 char next = sub_pattern[i + 1];593 if (ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS.find(next) != ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS.end()) {594 i++;595 literal += sub_pattern[i];596 i++;597 } else {598 auto escape_length = gbnf_escape_length(sub_pattern, i);599 if (escape_length == 0) {600 throw unsupported_pattern("unsupported escape: " + sub_pattern.substr(i, 2));601 }602 literal += sub_pattern.substr(i, escape_length);603 i += escape_length;604 }605 } else if (sub_pattern[i] == '"') {606 literal += "\\\"";607 i++;608 } else if (!is_non_literal(sub_pattern[i]) &&609 (i == length - 1 || literal.empty() || sub_pattern[i + 1] == '.' || !is_non_literal(sub_pattern[i + 1]))) {610 literal += sub_pattern[i];611 i++;612 } else {613 break;614 }615 }616 if (literal.empty()) { // nothing was consumed, ex. a stray ']' or '}'617 throw unsupported_pattern(std::string("unsupported character: ") + c);618 }619 seq.emplace_back(literal, true);620 }621 }622 return join_seq();623 };624 625 auto rule = to_rule(transform());626 if (paren_depth != 0) {627 throw invalid_pattern("unbalanced parentheses");628 }629 630 return _add_rule(name, "\"\\\"\" (" + rule + ") \"\\\"\"");631 }632 633 /*634 Returns a rule that matches a JSON string that is none of the provided strings635 636 not_strings({"a"})637 -> ["] ( [a] char+ | [^"a] char* )? ["]638 not_strings({"and", "also"})639 -> ["] ( [a] ([l] ([s] ([o] char+ | [^"o] char*) | [^"s] char*) | [n] ([d] char+ | [^"d] char*) | [^"ln] char*) | [^"a] char* )? ["]640 */641 std::string _not_strings(const std::vector<std::string> & strings) {642 common_trie trie(strings);643 644 std::string char_rule = _add_primitive("char", PRIMITIVE_RULES.at("char"));645 std::ostringstream out;646 out << "[\"] ( ";647 std::function<void(size_t)> visit = [&](size_t idx) {648 const auto & node = trie.nodes[idx];649 std::string rejects;650 auto first = true;651 for (const auto & [cpt, child] : node.children) {652 std::string c = common_unicode_cpt_to_utf8(cpt);653 rejects += c;654 if (first) {655 first = false;656 } else {657 out << " | ";658 }659 out << "[" << c << "]";660 if (!trie.nodes[child].children.empty()) {661 out << " (";662 visit(child);663 out << ")";664 } else {665 out << " " << char_rule << "+";666 }667 }668 if (!node.children.empty()) {669 out << " | [^\"" << rejects << "] " << char_rule << "*";670 }671 };672 visit(0);673 674 out << " )";675 if (trie.nodes[0].pattern < 0) {676 out << "?";677 }678 out << " [\"]";679 return out.str();680 }681 682 std::string _resolve_ref(const common_chat_schema_ref & schema) {683 auto it = schema.ref.find('#');684 std::string ref_fragment = it != std::string::npos ? schema.ref.substr(it + 1) : schema.ref;685 static const std::regex nonalphanumeric_regex(R"([^a-zA-Z0-9-]+)");686 std::string ref_name = "ref" + std::regex_replace(ref_fragment, nonalphanumeric_regex, "-");687 if (_rules.find(ref_name) == _rules.end() && _refs_being_resolved.find(schema.ref) == _refs_being_resolved.end()) {688 if (!schema.target) {689 _errors.push_back("Unresolved $ref " + schema.ref);690 return "";691 }692 _refs_being_resolved.insert(schema.ref);693 ref_name = visit(*schema.target, ref_name);694 _refs_being_resolved.erase(schema.ref);695 }696 return ref_name;697 }698 699 std::string _build_object_rule(700 const std::vector<std::pair<std::string, const common_chat_schema *>> & properties,701 const std::unordered_set<std::string> & required,702 const std::string & name,703 const common_chat_schema * additional_properties)704 {705 std::vector<std::string> required_props;706 std::vector<std::string> optional_props;707 std::unordered_map<std::string, std::string> prop_kv_rule_names;708 std::vector<std::string> prop_names;709 for (const auto & kv : properties) {710 const auto &prop_name = kv.first;711 const auto &prop_schema = kv.second;712 713 std::string prop_rule_name = visit(*prop_schema, name + (name.empty() ? "" : "-") + prop_name);714 prop_kv_rule_names[prop_name] = _add_rule(715 name + (name.empty() ? "" : "-") + prop_name + "-kv",716 format_literal(json(prop_name).dump()) + " space \":\" space " + prop_rule_name717 );718 if (required.find(prop_name) != required.end()) {719 required_props.push_back(prop_name);720 } else {721 optional_props.push_back(prop_name);722 }723 prop_names.push_back(prop_name);724 }725 if (additional_properties) {726 std::string sub_name = name + (name.empty() ? "" : "-") + "additional";727 std::string value_rule =728 additional_properties->kind() != common_chat_schema::KIND_ANY ? visit(*additional_properties, sub_name + "-value")729 : _add_primitive("value", PRIMITIVE_RULES.at("value"));730 731 auto key_rule =732 prop_names.empty() ? _add_primitive("string", PRIMITIVE_RULES.at("string"))733 : _add_rule(sub_name + "-k", _not_strings(prop_names));734 std::string kv_rule = _add_rule(sub_name + "-kv", key_rule + " \":\" space " + value_rule);735 prop_kv_rule_names["*"] = kv_rule;736 optional_props.push_back("*");737 }738 739 if (required_props.empty() && optional_props.empty()) {740 return "\"{\" space \"}\"";741 }742 743 std::string rule = "\"{\" space ";744 for (size_t i = 0; i < required_props.size(); i++) {745 if (i > 0) {746 rule += " \",\" space ";747 }748 rule += prop_kv_rule_names[required_props[i]];749 }750 751 if (!optional_props.empty()) {752 rule += " (";753 if (!required_props.empty()) {754 rule += " \",\" space ( ";755 }756 757 std::function<std::string(const std::vector<std::string> &, bool)> get_recursive_refs = [&](const std::vector<std::string> & ks, bool first_is_optional) {758 std::string res;759 if (ks.empty()) {760 return res;761 }762 const std::string& k = ks[0];763 std::string kv_rule_name = prop_kv_rule_names[k];764 std::string comma_ref = "( \",\" space " + kv_rule_name + " )";765 if (first_is_optional) {766 res = comma_ref + (k == "*" ? "*" : "?");767 } else {768 res = kv_rule_name + (k == "*" ? " " + comma_ref + "*" : "");769 }770 if (ks.size() > 1) {771 res += " " + _add_rule(772 name + (name.empty() ? "" : "-") + k + "-rest",773 get_recursive_refs(std::vector<std::string>(ks.begin() + 1, ks.end()), true)774 );775 }776 return res;777 };778 779 for (size_t i = 0; i < optional_props.size(); i++) {780 if (i > 0) {781 rule += " | ";782 }783 rule += get_recursive_refs(std::vector<std::string>(optional_props.begin() + i, optional_props.end()), false);784 }785 if (!required_props.empty()) {786 rule += " )";787 }788 rule += " )?";789 }790 791 rule += " space \"}\"";792 793 return rule;794 }795 796 std::string _add_primitive(const std::string & name, const BuiltinRule & rule) {797 auto n = _add_rule(name, rule.content);798 for (const auto & dep : rule.deps) {799 BuiltinRule dep_rule;800 auto it = PRIMITIVE_RULES.find(dep);801 if (it == PRIMITIVE_RULES.end()) {802 it = STRING_FORMAT_RULES.find(dep);803 if (it == STRING_FORMAT_RULES.end()) {804 _errors.push_back("Rule " + dep + " not known");805 continue;806 }807 }808 if (_rules.find(dep) == _rules.end()) {809 _add_primitive(dep, it->second);810 }811 }812 return n;813 }814 815public:816 explicit common_chat_schema_converter(bool dotall) : _dotall(dotall) {817 _rules["space"] = SPACE_RULE;818 }819 820 std::string add_schema(const std::string & name, const common_chat_schema & schema) {821 return visit(schema, name);822 }823 824 static std::string _generate_constant_rule(const json & value) {825 return format_literal(value.dump());826 }827 828 std::string _visit_primitive(const std::string & rule_name, const std::string & type) {829 return _add_primitive(rule_name == "root" ? "root" : type, PRIMITIVE_RULES.at(type));830 }831 832 std::string _visit_all_of(const common_chat_schema_all_of & schema, const std::string & name, const std::string & rule_name) {833 std::unordered_set<std::string> required;834 std::vector<std::pair<std::string, const common_chat_schema *>> properties;835 std::map<std::string, size_t> enum_values;836 std::function<void(const common_chat_schema &, bool)> add_component = [&](const common_chat_schema & comp, bool is_required) {837 if (comp.kind() == common_chat_schema::KIND_REF) {838 if (const auto * target = as<common_chat_schema_ref>(comp).target) {839 add_component(*target, is_required);840 }841 } else if (comp.kind() == common_chat_schema::KIND_OBJECT) {842 for (const auto & prop : as<common_chat_schema_object>(comp).properties) {843 properties.emplace_back(prop.name, prop.schema.get());844 if (is_required) {845 required.insert(prop.name);846 }847 }848 } else if (comp.kind() == common_chat_schema::KIND_ENUM) {849 for (const auto & v : as<common_chat_schema_enum>(comp).values) {850 enum_values[_generate_constant_rule(v)] += 1;851 }852 }853 };854 for (const auto & child : schema.children) {855 if (child->kind() == common_chat_schema::KIND_ANY_OF) {856 for (const auto & alt : as<common_chat_schema_any_of>(*child).children) {857 add_component(*alt, false);858 }859 } else {860 add_component(*child, true);861 }862 }863 if (!enum_values.empty()) {864 std::vector<std::string> enum_intersection;865 for (const auto & p : enum_values) {866 if (p.second == schema.children.size()) {867 enum_intersection.push_back(p.first);868 }869 }870 if (!enum_intersection.empty()) {871 return _add_rule(rule_name, "(" + string_join(enum_intersection, " | ") + ")");872 }873 }874 return _add_rule(rule_name, _build_object_rule(properties, required, name, nullptr));875 }876 877 std::string visit(const common_chat_schema & schema, const std::string & name) {878 std::string rule_name = is_reserved_name(name) ? name + "-" : name.empty() ? "root" : name;879 std::string sub_name = name + (name.empty() ? "" : "-");880 881 switch (schema.kind()) {882 case common_chat_schema::KIND_REF:883 return _add_rule(rule_name, _resolve_ref(as<common_chat_schema_ref>(schema)));884 case common_chat_schema::KIND_ANY_OF:885 return _add_rule(rule_name, _generate_union_rule(name, as<common_chat_schema_any_of>(schema).children));886 case common_chat_schema::KIND_ALL_OF:887 return _visit_all_of(as<common_chat_schema_all_of>(schema), name, rule_name);888 case common_chat_schema::KIND_CONST:889 return _add_rule(rule_name, _generate_constant_rule(as<common_chat_schema_const>(schema).value));890 case common_chat_schema::KIND_ENUM: {891 std::vector<std::string> enum_values;892 for (const auto & v : as<common_chat_schema_enum>(schema).values) {893 enum_values.push_back(_generate_constant_rule(v));894 }895 return _add_rule(rule_name, "(" + string_join(enum_values, " | ") + ")");896 }897 case common_chat_schema::KIND_OBJECT: {898 const auto & obj = as<common_chat_schema_object>(schema);899 if (obj.properties.empty() && obj.additional_properties && obj.additional_properties->kind() == common_chat_schema::KIND_ANY) {900 return _add_rule(rule_name, _add_primitive("object", PRIMITIVE_RULES.at("object")));901 }902 std::vector<std::pair<std::string, const common_chat_schema *>> properties;903 std::unordered_set<std::string> required;904 for (const auto & prop : obj.properties) {905 properties.emplace_back(prop.name, prop.schema.get());906 if (prop.required) {907 required.insert(prop.name);908 }909 }910 return _add_rule(rule_name, _build_object_rule(properties, required, name, obj.additional_properties.get()));911 }912 case common_chat_schema::KIND_TUPLE: {913 const auto & items = as<common_chat_schema_tuple>(schema).items;914 std::string rule = "\"[\" space ";915 for (size_t i = 0; i < items.size(); i++) {916 if (i > 0) {917 rule += " \",\" space ";918 }919 rule += visit(*items[i], sub_name + "tuple-" + std::to_string(i));920 }921 rule += " space \"]\"";922 return _add_rule(rule_name, rule);923 }924 case common_chat_schema::KIND_ARRAY: {925 const auto & arr = as<common_chat_schema_array>(schema);926 if (arr.items->kind() == common_chat_schema::KIND_ANY && arr.min_items == 0 && arr.max_items < 0) {927 return _visit_primitive(rule_name, "array");928 }929 std::string item_rule_name = visit(*arr.items, sub_name + "item");930 int max_items = arr.max_items < 0 ? std::numeric_limits<int>::max() : arr.max_items;931 return _add_rule(rule_name, "\"[\" space " + build_repetition(item_rule_name, arr.min_items, max_items, "\",\" space") + " space \"]\"");932 }933 case common_chat_schema::KIND_STRING: {934 const auto & str = as<common_chat_schema_string>(schema);935 if (!str.pattern.empty()) {936 return _visit_pattern(str.pattern, rule_name);937 }938 if (str.format == common_chat_schema::FORMAT_UUID) {939 return _visit_primitive(rule_name, "uuid");940 }941 if (str.format != common_chat_schema::FORMAT_NONE) {942 std::string prim_name = std::string(str.format == common_chat_schema::FORMAT_DATE ? "date" : str.format == common_chat_schema::FORMAT_TIME ? "time" : "date-time") + "-string";943 return _add_rule(rule_name, _add_primitive(prim_name, STRING_FORMAT_RULES.at(prim_name)));944 }945 if (str.min_length > 0 || str.max_length >= 0) {946 std::string char_rule = _add_primitive("char", PRIMITIVE_RULES.at("char"));947 int max_len = str.max_length < 0 ? std::numeric_limits<int>::max() : str.max_length;948 return _add_rule(rule_name, "\"\\\"\" " + build_repetition(char_rule, str.min_length, max_len) + " \"\\\"\"");949 }950 return _visit_primitive(rule_name, "string");951 }952 case common_chat_schema::KIND_INTEGER: {953 const auto & i = as<common_chat_schema_integer>(schema);954 if (i.minimum == std::numeric_limits<int64_t>::min() && i.maximum == std::numeric_limits<int64_t>::max()) {955 return _visit_primitive(rule_name, "integer");956 }957 std::stringstream out;958 out << "(";959 build_min_max_int(i.minimum, i.maximum, out);960 out << ")";961 return _add_rule(rule_name, out.str());962 }963 case common_chat_schema::KIND_NUMBER:964 return _visit_primitive(rule_name, "number");965 case common_chat_schema::KIND_BOOLEAN:966 return _visit_primitive(rule_name, "boolean");967 case common_chat_schema::KIND_NULL:968 return _visit_primitive(rule_name, "null");969 case common_chat_schema::KIND_ANY:970 return _add_rule(rule_name, _add_primitive("value", PRIMITIVE_RULES.at("value")));971 }972 return "";973 }974 975 void check_errors() {976 if (!_errors.empty()) {977 throw std::invalid_argument("JSON schema conversion failed:\n" + string_join(_errors, "\n"));978 }979 if (!_warnings.empty()) {980 fprintf(stderr, "WARNING: JSON schema conversion was incomplete: %s\n", string_join(_warnings, "; ").c_str());981 }982 }983 984 std::string format_grammar() {985 std::stringstream ss;986 for (const auto & kv : _rules) {987 ss << kv.first << " ::= " << kv.second << '\n';988 }989 return ss.str();990 }991};992 993std::string json_schema_to_grammar(const common_json & schema, bool force_gbnf) {994#ifdef LLAMA_USE_LLGUIDANCE995 if (!force_gbnf) {996 return "%llguidance {}\nstart: %json " + schema.dump();997 }998#else999 (void)force_gbnf;1000#endif // LLAMA_USE_LLGUIDANCE1001 try {1002 return json_schema_to_grammar(common_chat_schema_from_json(schema));1003 } catch (const std::runtime_error & e) {1004 throw std::invalid_argument(std::string("JSON schema conversion failed:\n") + e.what());1005 }1006}1007 1008std::string json_schema_to_grammar(const common_chat_schema_document & schema) {1009 common_chat_schema_converter converter(false);1010 converter.visit(*schema.root, "");1011 converter.check_errors();1012 return converter.format_grammar();1013}1014 1015std::string build_grammar(const std::function<void(const common_grammar_builder &)> & cb, const common_grammar_options & options) {1016 common_chat_schema_converter converter(options.dotall);1017 common_grammar_builder builder {1018 /* .add_rule = */ [&](const std::string & name, const std::string & rule) {1019 return converter._add_rule(name, rule);1020 },1021 /* .add_schema = */ [&](const std::string & name, const common_chat_schema & schema) {1022 return converter.add_schema(name == "root" ? "" : name, schema);1023 },1024 };1025 cb(builder);1026 converter.check_errors();1027 return converter.format_grammar();1028}1029