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