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 } else if (min_items == 0 && !has_max) {
31 return item_rule + "*";
32 } else {
33 return item_rule + "{" + std::to_string(min_items) + "," + (has_max ? std::to_string(max_items) : "") + "}";
34 }
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
235std::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
250std::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) s.insert(p.first);
264 for (const auto & p : STRING_FORMAT_RULES) s.insert(p.first);
265 return s;
266 }();
267 return RESERVED_NAMES.find(name) != RESERVED_NAMES.end();
268}
269
270std::regex INVALID_RULE_CHARS_RE("[^a-zA-Z0-9-]+");
271std::regex GRAMMAR_LITERAL_ESCAPE_RE("[\r\n\"\\\\]");
272std::regex GRAMMAR_RANGE_LITERAL_ESCAPE_RE("[\r\n\"\\]\\-\\\\]");
273std::unordered_map<char, std::string> GRAMMAR_LITERAL_ESCAPES = {
274 {'\r', "\\r"}, {'\n', "\\n"}, {'"', "\\\""}, {'-', "\\-"}, {']', "\\]"}, {'\\', "\\\\"}
275};
276
277std::unordered_set<char> NON_LITERAL_SET = {'|', '.', '(', ')', '[', ']', '{', '}', '*', '+', '?'};
278std::unordered_set<char> ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS = {'^', '$', '.', '[', ']', '(', ')', '|', '{', '}', '*', '+', '?'};
279
280static std::string replacePattern(const std::string & input, const std::regex & regex, const std::function<std::string(const std::smatch &)> & replacement) {
281 std::smatch match;
282 std::string result;
283
284 std::string::const_iterator searchStart(input.cbegin());
285 std::string::const_iterator searchEnd(input.cend());
286
287 while (std::regex_search(searchStart, searchEnd, match, regex)) {
288 result.append(searchStart, searchStart + match.position());
289 result.append(replacement(match));
290 searchStart = match.suffix().first;
291 }
292
293 result.append(searchStart, searchEnd);
294
295 return result;
296}
297
298static std::string format_literal(const std::string & literal) {
299 std::string escaped = replacePattern(literal, GRAMMAR_LITERAL_ESCAPE_RE, [&](const std::smatch & match) {
300 char c = match.str()[0];
301 return GRAMMAR_LITERAL_ESCAPES.at(c);
302 });
303 return "\"" + escaped + "\"";
304}
305
306std::string gbnf_format_literal(const std::string & literal) { return format_literal(literal); }
307
308class common_schema_converter {
309private:
310 friend class common_schema_info;
311 friend std::string build_grammar(const std::function<void(const common_grammar_builder &)> & cb, const common_grammar_options & options);
312 std::function<json(const std::string &)> _fetch_json;
313 bool _dotall;
314 std::map<std::string, std::string> _rules;
315 std::unordered_map<std::string, json> _refs;
316 std::unordered_set<std::string> _refs_being_resolved;
317 std::vector<std::string> _errors;
318 std::vector<std::string> _warnings;
319
320 std::string _add_rule(const std::string & name, const std::string & rule) {
321 std::string esc_name = regex_replace(name, INVALID_RULE_CHARS_RE, "-");
322 if (_rules.find(esc_name) == _rules.end() || _rules[esc_name] == rule) {
323 _rules[esc_name] = rule;
324 return esc_name;
325 } else {
326 int i = 0;
327 while (_rules.find(esc_name + std::to_string(i)) != _rules.end() && _rules[esc_name + std::to_string(i)] != rule) {
328 i++;
329 }
330 std::string key = esc_name + std::to_string(i);
331 _rules[key] = rule;
332 return key;
333 }
334 }
335
336 std::string _generate_union_rule(const std::string & name, const std::vector<json> & alt_schemas) {
337 std::vector<std::string> rules;
338 for (size_t i = 0; i < alt_schemas.size(); i++) {
339 rules.push_back(visit(alt_schemas[i], name + (name.empty() ? "alternative-" : "-") + std::to_string(i)));
340 }
341 return string_join(rules, " | ");
342 }
343
344 std::string _visit_pattern(const std::string & pattern, const std::string & name) {
345 if (!(pattern.front() == '^' && pattern.back() == '$')) {
346 _errors.push_back("Pattern must start with '^' and end with '$'");
347 return "";
348 }
349 std::string sub_pattern = pattern.substr(1, pattern.length() - 2);
350 std::unordered_map<std::string, std::string> sub_rule_ids;
351
352 size_t i = 0;
353 size_t length = sub_pattern.length();
354
355 using literal_or_rule = std::pair<std::string, bool>;
356 auto to_rule = [&](const literal_or_rule & ls) {
357 auto is_literal = ls.second;
358 auto s = ls.first;
359 return is_literal ? "\"" + s + "\"" : s;
360 };
361 std::function<literal_or_rule()> transform = [&]() -> literal_or_rule {
362 size_t start = i;
363 std::vector<literal_or_rule> seq;
364
365 auto get_dot = [&]() {
366 std::string rule;
367 if (_dotall) {
368 rule = "[\\U00000000-\\U0010FFFF]";
369 } else {
370 rule = "[^\\x0A\\x0D]";
371 }
372 return _add_rule("dot", rule);
373 };
374
375 // Joins the sequence, merging consecutive literals together.
376 auto join_seq = [&]() {
377 std::vector<literal_or_rule> ret;
378
379 std::string literal;
380 auto flush_literal = [&]() {
381 if (literal.empty()) {
382 return false;
383 }
384 ret.emplace_back(literal, true);
385 literal.clear();
386 return true;
387 };
388
389 for (const auto & item : seq) {
390 auto is_literal = item.second;
391 if (is_literal) {
392 literal += item.first;
393 } else {
394 flush_literal();
395 ret.push_back(item);
396 }
397 }
398 flush_literal();
399
400 std::vector<std::string> results;
401 for (const auto & item : ret) {
402 results.push_back(to_rule(item));
403 }
404 return std::make_pair(string_join(results, " "), false);
405 };
406
407 while (i < length) {
408 char c = sub_pattern[i];
409 if (c == '.') {
410 seq.emplace_back(get_dot(), false);
411 i++;
412 } else if (c == '(') {
413 i++;
414 if (i < length) {
415 if (sub_pattern[i] == '?') {
416 _warnings.push_back("Unsupported pattern syntax");
417 }
418 }
419 seq.emplace_back("(" + to_rule(transform()) + ")", false);
420 } else if (c == ')') {
421 i++;
422 if (start > 0 && sub_pattern[start - 1] != '(') {
423 _errors.push_back("Unbalanced parentheses");
424 }
425 return join_seq();
426 } else if (c == '[') {
427 std::string square_brackets = std::string(1, c);
428 i++;
429 while (i < length && sub_pattern[i] != ']') {
430 if (sub_pattern[i] == '\\') {
431 square_brackets += sub_pattern.substr(i, 2);
432 i += 2;
433 } else {
434 square_brackets += sub_pattern[i];
435 i++;
436 }
437 }
438 if (i >= length) {
439 _errors.push_back("Unbalanced square brackets");
440 }
441 square_brackets += ']';
442 i++;
443 seq.emplace_back(square_brackets, false);
444 } else if (c == '|') {
445 seq.emplace_back("|", false);
446 i++;
447 } else if (c == '*' || c == '+' || c == '?') {
448 seq.back() = std::make_pair(to_rule(seq.back()) + c, false);
449 i++;
450 } else if (c == '{') {
451 std::string curly_brackets = std::string(1, c);
452 i++;
453 while (i < length && sub_pattern[i] != '}') {
454 curly_brackets += sub_pattern[i];
455 i++;
456 }
457 if (i >= length) {
458 _errors.push_back("Unbalanced curly brackets");
459 }
460 curly_brackets += '}';
461 i++;
462 auto nums = string_split(curly_brackets.substr(1, curly_brackets.length() - 2), ",");
463 int min_times = 0;
464 int max_times = std::numeric_limits<int>::max();
465 try {
466 if (nums.size() == 1) {
467 min_times = max_times = std::stoi(nums[0]);
468 } else if (nums.size() != 2) {
469 _errors.push_back("Wrong number of values in curly brackets");
470 } else {
471 if (!nums[0].empty()) {
472 min_times = std::stoi(nums[0]);
473 }
474 if (!nums[1].empty()) {
475 max_times = std::stoi(nums[1]);
476 }
477 }
478 } catch (const std::invalid_argument & e) {
479 _errors.push_back("Invalid number in curly brackets");
480 return std::make_pair("", false);
481 }
482 auto &last = seq.back();
483 auto &sub = last.first;
484 auto sub_is_literal = last.second;
485
486 if (!sub_is_literal) {
487 std::string & sub_id = sub_rule_ids[sub];
488 if (sub_id.empty()) {
489 sub_id = _add_rule(name + "-" + std::to_string(sub_rule_ids.size()), sub);
490 }
491 sub = sub_id;
492 }
493 seq.back().first = build_repetition(
494 sub_is_literal ? "\"" + sub + "\"" : sub,
495 min_times,
496 max_times,
497 ""
498 );
499 seq.back().second = false;
500 } else {
501 std::string literal;
502 auto is_non_literal = [&](char c) {
503 return NON_LITERAL_SET.find(c) != NON_LITERAL_SET.end();
504 };
505 while (i < length) {
506 if (sub_pattern[i] == '\\' && i < length - 1) {
507 char next = sub_pattern[i + 1];
508 if (ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS.find(next) != ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS.end()) {
509 i++;
510 literal += sub_pattern[i];
511 i++;
512 } else {
513 literal += sub_pattern.substr(i, 2);
514 i += 2;
515 }
516 } else if (sub_pattern[i] == '"') {
517 literal += "\\\"";
518 i++;
519 } else if (!is_non_literal(sub_pattern[i]) &&
520 (i == length - 1 || literal.empty() || sub_pattern[i + 1] == '.' || !is_non_literal(sub_pattern[i + 1]))) {
521 literal += sub_pattern[i];
522 i++;
523 } else {
524 break;
525 }
526 }
527 if (!literal.empty()) {
528 seq.emplace_back(literal, true);
529 }
530 }
531 }
532 return join_seq();
533 };
534 return _add_rule(name, "\"\\\"\" (" + to_rule(transform()) + ") \"\\\"\" space");
535 }
536
537 /*
538 Returns a rule that matches a JSON string that is none of the provided strings
539
540 not_strings({"a"})
541 -> ["] ( [a] char+ | [^"a] char* )? ["] space
542 not_strings({"and", "also"})
543 -> ["] ( [a] ([l] ([s] ([o] char+ | [^"o] char*) | [^"s] char*) | [n] ([d] char+ | [^"d] char*) | [^"ln] char*) | [^"a] char* )? ["] space
544 */
545 std::string _not_strings(const std::vector<std::string> & strings) {
546
547 struct TrieNode {
548 std::map<char, TrieNode> children;
549 bool is_end_of_string;
550
551 TrieNode() : is_end_of_string(false) {}
552
553 void insert(const std::string & string) {
554 auto node = this;
555 for (char c : string) {
556 node = &node->children[c];
557 }
558 node->is_end_of_string = true;
559 }
560 };
561
562 TrieNode trie;
563 for (const auto & s : strings) {
564 trie.insert(s);
565 }
566
567 std::string char_rule = _add_primitive("char", PRIMITIVE_RULES.at("char"));
568 std::ostringstream out;
569 out << "[\"] ( ";
570 std::function<void(const TrieNode &)> visit = [&](const TrieNode & node) {
571 std::ostringstream rejects;
572 auto first = true;
573 for (const auto & kv : node.children) {
574 rejects << kv.first;
575 if (first) {
576 first = false;
577 } else {
578 out << " | ";
579 }
580 out << "[" << kv.first << "]";
581 if (!kv.second.children.empty()) {
582 out << " (";
583 visit(kv.second);
584 out << ")";
585 } else if (kv.second.is_end_of_string) {
586 out << " " << char_rule << "+";
587 }
588 }
589 if (!node.children.empty()) {
590 if (!first) {
591 out << " | ";
592 }
593 out << "[^\"" << rejects.str() << "] " << char_rule << "*";
594 }
595 };
596 visit(trie);
597
598 out << " )";
599 if (!trie.is_end_of_string) {
600 out << "?";
601 }
602 out << " [\"] space";
603 return out.str();
604 }
605
606 std::string _resolve_ref(const std::string & ref) {
607 auto it = ref.find('#');
608 std::string ref_fragment = it != std::string::npos ? ref.substr(it + 1) : ref;
609 static const std::regex nonalphanumeric_regex(R"([^a-zA-Z0-9-]+)");
610 std::string ref_name = "ref" + std::regex_replace(ref_fragment, nonalphanumeric_regex, "-");
611 if (_rules.find(ref_name) == _rules.end() && _refs_being_resolved.find(ref) == _refs_being_resolved.end()) {
612 _refs_being_resolved.insert(ref);
613 json resolved = _refs[ref];
614 ref_name = visit(resolved, ref_name);
615 _refs_being_resolved.erase(ref);
616 }
617 return ref_name;
618 }
619
620 std::string _build_object_rule(
621 const std::vector<std::pair<std::string, json>> & properties,
622 const std::unordered_set<std::string> & required,
623 const std::string & name,
624 const json & additional_properties)
625 {
626 std::vector<std::string> required_props;
627 std::vector<std::string> optional_props;
628 std::unordered_map<std::string, std::string> prop_kv_rule_names;
629 std::vector<std::string> prop_names;
630 for (const auto & kv : properties) {
631 const auto &prop_name = kv.first;
632 const auto &prop_schema = kv.second;
633
634 std::string prop_rule_name = visit(prop_schema, name + (name.empty() ? "" : "-") + prop_name);
635 prop_kv_rule_names[prop_name] = _add_rule(
636 name + (name.empty() ? "" : "-") + prop_name + "-kv",
637 format_literal(json(prop_name).dump()) + " space \":\" space " + prop_rule_name
638 );
639 if (required.find(prop_name) != required.end()) {
640 required_props.push_back(prop_name);
641 } else {
642 optional_props.push_back(prop_name);
643 }
644 prop_names.push_back(prop_name);
645 }
646 if ((additional_properties.is_boolean() && additional_properties.get<bool>()) || additional_properties.is_object()) {
647 std::string sub_name = name + (name.empty() ? "" : "-") + "additional";
648 std::string value_rule =
649 additional_properties.is_object() ? visit(additional_properties, sub_name + "-value")
650 : _add_primitive("value", PRIMITIVE_RULES.at("value"));
651
652 auto key_rule =
653 prop_names.empty() ? _add_primitive("string", PRIMITIVE_RULES.at("string"))
654 : _add_rule(sub_name + "-k", _not_strings(prop_names));
655 std::string kv_rule = _add_rule(sub_name + "-kv", key_rule + " \":\" space " + value_rule);
656 prop_kv_rule_names["*"] = kv_rule;
657 optional_props.push_back("*");
658 }
659
660 std::string rule = "\"{\" space ";
661 for (size_t i = 0; i < required_props.size(); i++) {
662 if (i > 0) {
663 rule += " \",\" space ";
664 }
665 rule += prop_kv_rule_names[required_props[i]];
666 }
667
668 if (!optional_props.empty()) {
669 rule += " (";
670 if (!required_props.empty()) {
671 rule += " \",\" space ( ";
672 }
673
674 std::function<std::string(const std::vector<std::string> &, bool)> get_recursive_refs = [&](const std::vector<std::string> & ks, bool first_is_optional) {
675 std::string res;
676 if (ks.empty()) {
677 return res;
678 }
679 std::string k = ks[0];
680 std::string kv_rule_name = prop_kv_rule_names[k];
681 std::string comma_ref = "( \",\" space " + kv_rule_name + " )";
682 if (first_is_optional) {
683 res = comma_ref + (k == "*" ? "*" : "?");
684 } else {
685 res = kv_rule_name + (k == "*" ? " " + comma_ref + "*" : "");
686 }
687 if (ks.size() > 1) {
688 res += " " + _add_rule(
689 name + (name.empty() ? "" : "-") + k + "-rest",
690 get_recursive_refs(std::vector<std::string>(ks.begin() + 1, ks.end()), true)
691 );
692 }
693 return res;
694 };
695
696 for (size_t i = 0; i < optional_props.size(); i++) {
697 if (i > 0) {
698 rule += " | ";
699 }
700 rule += get_recursive_refs(std::vector<std::string>(optional_props.begin() + i, optional_props.end()), false);
701 }
702 if (!required_props.empty()) {
703 rule += " )";
704 }
705 rule += " )?";
706 }
707
708 rule += " \"}\" space";
709
710 return rule;
711 }
712
713 std::string _add_primitive(const std::string & name, const BuiltinRule & rule) {
714 auto n = _add_rule(name, rule.content);
715 for (const auto & dep : rule.deps) {
716 BuiltinRule dep_rule;
717 auto it = PRIMITIVE_RULES.find(dep);
718 if (it == PRIMITIVE_RULES.end()) {
719 it = STRING_FORMAT_RULES.find(dep);
720 if (it == STRING_FORMAT_RULES.end()) {
721 _errors.push_back("Rule " + dep + " not known");
722 continue;
723 }
724 }
725 if (_rules.find(dep) == _rules.end()) {
726 _add_primitive(dep, it->second);
727 }
728 }
729 return n;
730 }
731
732public:
733 common_schema_converter(
734 const std::function<json(const std::string &)> & fetch_json,
735 bool dotall)
736 : _fetch_json(fetch_json), _dotall(dotall)
737 {
738 _rules["space"] = SPACE_RULE;
739 }
740
741 void resolve_refs(json & schema, const std::string & url) {
742 /*
743 * Resolves all $ref fields in the given schema, fetching any remote schemas,
744 * replacing each $ref with absolute reference URL and populates _refs with the
745 * respective referenced (sub)schema dictionaries.
746 */
747 std::function<void(json &)> visit_refs = [&](json & n) {
748 if (n.is_array()) {
749 for (auto & x : n) {
750 visit_refs(x);
751 }
752 } else if (n.is_object()) {
753 if (n.contains("$ref")) {
754 std::string ref = n["$ref"];
755 if (_refs.find(ref) == _refs.end()) {
756 json target;
757 if (ref.find("https://") == 0) {
758 std::string base_url = ref.substr(0, ref.find('#'));
759 auto it = _refs.find(base_url);
760 if (it != _refs.end()) {
761 target = it->second;
762 } else {
763 // Fetch the referenced schema and resolve its refs
764 auto referenced = _fetch_json(ref);
765 resolve_refs(referenced, base_url);
766 _refs[base_url] = referenced;
767 }
768 if (ref.find('#') == std::string::npos || ref.substr(ref.find('#') + 1).empty()) {
769 return;
770 }
771 } else if (ref.find("#/") == 0) {
772 target = schema;
773 n["$ref"] = url + ref;
774 ref = url + ref;
775 } else {
776 _errors.push_back("Unsupported ref: " + ref);
777 return;
778 }
779 std::string pointer = ref.substr(ref.find('#') + 1);
780 std::vector<std::string> tokens = string_split(pointer, "/");
781 for (size_t i = 1; i < tokens.size(); ++i) {
782 std::string sel = tokens[i];
783 if (target.is_object() && target.contains(sel)) {
784 target = target[sel];
785 } else if (target.is_array()) {
786 size_t sel_index;
787 try {
788 sel_index = std::stoul(sel);
789 } catch (const std::invalid_argument & e) {
790 sel_index = target.size();
791 }
792 if (sel_index >= target.size()) {
793 _errors.push_back("Error resolving ref " + ref + ": " + sel + " not in " + target.dump());
794 return;
795 }
796 target = target[sel_index];
797 } else {
798 _errors.push_back("Error resolving ref " + ref + ": " + sel + " not in " + target.dump());
799 return;
800 }
801 }
802 _refs[ref] = target;
803 }
804 } else {
805 for (auto & kv : n.items()) {
806 visit_refs(kv.value());
807 }
808 }
809 }
810 };
811
812 visit_refs(schema);
813 }
814
815 std::string _generate_constant_rule(const json & value) {
816 return format_literal(value.dump());
817 }
818
819 std::string visit(const json & schema, const std::string & name) {
820 json schema_type = schema.contains("type") ? schema["type"] : json();
821 std::string schema_format = schema.contains("format") ? schema["format"].get<std::string>() : "";
822 std::string rule_name = is_reserved_name(name) ? name + "-" : name.empty() ? "root" : name;
823
824 if (schema.contains("$ref")) {
825 return _add_rule(rule_name, _resolve_ref(schema["$ref"]));
826 } else if (schema.contains("oneOf") || schema.contains("anyOf")) {
827 std::vector<json> alt_schemas = schema.contains("oneOf") ? schema["oneOf"].get<std::vector<json>>() : schema["anyOf"].get<std::vector<json>>();
828 return _add_rule(rule_name, _generate_union_rule(name, alt_schemas));
829 } else if (schema_type.is_array()) {
830 std::vector<json> schema_types;
831 for (const auto & t : schema_type) {
832 json schema_copy(schema);
833 schema_copy["type"] = t;
834 schema_types.push_back(schema_copy);
835 }
836 return _add_rule(rule_name, _generate_union_rule(name, schema_types));
837 } else if (schema.contains("const")) {
838 return _add_rule(rule_name, _generate_constant_rule(schema["const"]) + " space");
839 } else if (schema.contains("enum")) {
840 std::vector<std::string> enum_values;
841 for (const auto & v : schema["enum"]) {
842 enum_values.push_back(_generate_constant_rule(v));
843 }
844 return _add_rule(rule_name, "(" + string_join(enum_values, " | ") + ") space");
845 } else if ((schema_type.is_null() || schema_type == "object")
846 && (schema.contains("properties") ||
847 (schema.contains("additionalProperties") && schema["additionalProperties"] != true))) {
848 std::unordered_set<std::string> required;
849 if (schema.contains("required") && schema["required"].is_array()) {
850 for (const auto & item : schema["required"]) {
851 if (item.is_string()) {
852 required.insert(item.get<std::string>());
853 }
854 }
855 }
856 std::vector<std::pair<std::string, json>> properties;
857 if (schema.contains("properties")) {
858 for (const auto & prop : schema["properties"].items()) {
859 properties.emplace_back(prop.key(), prop.value());
860 }
861 }
862 return _add_rule(rule_name,
863 _build_object_rule(
864 properties, required, name,
865 schema.contains("additionalProperties") ? schema["additionalProperties"] : json()));
866 } else if ((schema_type.is_null() || schema_type == "object" || schema_type == "string") && schema.contains("allOf")) {
867 std::unordered_set<std::string> required;
868 std::vector<std::pair<std::string, json>> properties;
869 std::map<std::string, size_t> enum_values;
870 std::string hybrid_name = name;
871 std::function<void(const json &, bool)> add_component = [&](const json & comp_schema, bool is_required) {
872 if (comp_schema.contains("$ref")) {
873 add_component(_refs[comp_schema["$ref"]], is_required);
874 } else if (comp_schema.contains("properties")) {
875 for (const auto & prop : comp_schema["properties"].items()) {
876 properties.emplace_back(prop.key(), prop.value());
877 if (is_required) {
878 required.insert(prop.key());
879 }
880 }
881 } else if (comp_schema.contains("enum")) {
882 for (const auto & v : comp_schema["enum"]) {
883 const auto rule = _generate_constant_rule(v);
884 if (enum_values.find(rule) == enum_values.end()) {
885 enum_values[rule] = 0;
886 }
887 enum_values[rule] += 1;
888 }
889 } else {
890 // todo warning
891 }
892 };
893 for (auto & t : schema["allOf"]) {
894 if (t.contains("anyOf")) {
895 for (auto & tt : t["anyOf"]) {
896 add_component(tt, false);
897 }
898 } else {
899 add_component(t, true);
900 }
901 }
902 if (!enum_values.empty()) {
903 std::vector<std::string> enum_intersection;
904 for (const auto & p : enum_values) {
905 if (p.second == schema["allOf"].size()) {
906 enum_intersection.push_back(p.first);
907 }
908 }
909 if (!enum_intersection.empty()) {
910 return _add_rule(rule_name, "(" + string_join(enum_intersection, " | ") + ") space");
911 }
912 }
913 return _add_rule(rule_name, _build_object_rule(properties, required, hybrid_name, json()));
914 } else if ((schema_type.is_null() || schema_type == "array") && (schema.contains("items") || schema.contains("prefixItems"))) {
915 json items = schema.contains("items") ? schema["items"] : schema["prefixItems"];
916 if (items.is_array()) {
917 std::string rule = "\"[\" space ";
918 for (size_t i = 0; i < items.size(); i++) {
919 if (i > 0) {
920 rule += " \",\" space ";
921 }
922 rule += visit(items[i], name + (name.empty() ? "" : "-") + "tuple-" + std::to_string(i));
923 }
924 rule += " \"]\" space";
925 return _add_rule(rule_name, rule);
926 } else {
927 std::string item_rule_name = visit(items, name + (name.empty() ? "" : "-") + "item");
928 int min_items = schema.contains("minItems") ? schema["minItems"].get<int>() : 0;
929 json max_items_json = schema.contains("maxItems") ? schema["maxItems"] : json();
930 int max_items = max_items_json.is_number_integer() ? max_items_json.get<int>() : std::numeric_limits<int>::max();
931
932 return _add_rule(rule_name, "\"[\" space " + build_repetition(item_rule_name, min_items, max_items, "\",\" space") + " \"]\" space");
933 }
934 } else if ((schema_type.is_null() || schema_type == "string") && schema.contains("pattern")) {
935 return _visit_pattern(schema["pattern"], rule_name);
936 } else if ((schema_type.is_null() || schema_type == "string") && std::regex_match(schema_format, std::regex("^uuid[1-5]?$"))) {
937 return _add_primitive(rule_name == "root" ? "root" : schema_format, PRIMITIVE_RULES.at("uuid"));
938 } else if ((schema_type.is_null() || schema_type == "string") && STRING_FORMAT_RULES.find(schema_format + "-string") != STRING_FORMAT_RULES.end()) {
939 auto prim_name = schema_format + "-string";
940 return _add_rule(rule_name, _add_primitive(prim_name, STRING_FORMAT_RULES.at(prim_name)));
941 } else if (schema_type == "string" && (schema.contains("minLength") || schema.contains("maxLength"))) {
942 std::string char_rule = _add_primitive("char", PRIMITIVE_RULES.at("char"));
943 int min_len = schema.contains("minLength") ? schema["minLength"].get<int>() : 0;
944 int max_len = schema.contains("maxLength") ? schema["maxLength"].get<int>() : std::numeric_limits<int>::max();
945 return _add_rule(rule_name, "\"\\\"\" " + build_repetition(char_rule, min_len, max_len) + " \"\\\"\" space");
946 } else if (schema_type == "integer" && (schema.contains("minimum") || schema.contains("exclusiveMinimum") || schema.contains("maximum") || schema.contains("exclusiveMaximum"))) {
947 int64_t min_value = std::numeric_limits<int64_t>::min();
948 int64_t max_value = std::numeric_limits<int64_t>::max();
949 if (schema.contains("minimum")) {
950 min_value = schema["minimum"].get<int64_t>();
951 } else if (schema.contains("exclusiveMinimum")) {
952 min_value = schema["exclusiveMinimum"].get<int64_t>() + 1;
953 }
954 if (schema.contains("maximum")) {
955 max_value = schema["maximum"].get<int64_t>();
956 } else if (schema.contains("exclusiveMaximum")) {
957 max_value = schema["exclusiveMaximum"].get<int64_t>() - 1;
958 }
959 std::stringstream out;
960 out << "(";
961 _build_min_max_int(min_value, max_value, out);
962 out << ") space";
963 return _add_rule(rule_name, out.str());
964 } else if (schema.empty() || schema_type == "object") {
965 return _add_rule(rule_name, _add_primitive("object", PRIMITIVE_RULES.at("object")));
966 } else {
967 if (!schema_type.is_string() || PRIMITIVE_RULES.find(schema_type.get<std::string>()) == PRIMITIVE_RULES.end()) {
968 _errors.push_back("Unrecognized schema: " + schema.dump());
969 return "";
970 }
971 // TODO: support minimum, maximum, exclusiveMinimum, exclusiveMaximum at least for zero
972 return _add_primitive(rule_name == "root" ? "root" : schema_type.get<std::string>(), PRIMITIVE_RULES.at(schema_type.get<std::string>()));
973 }
974 }
975
976 void check_errors() {
977 if (!_errors.empty()) {
978 throw std::invalid_argument("JSON schema conversion failed:\n" + string_join(_errors, "\n"));
979 }
980 if (!_warnings.empty()) {
981 fprintf(stderr, "WARNING: JSON schema conversion was incomplete: %s\n", string_join(_warnings, "; ").c_str());
982 }
983 }
984
985 std::string format_grammar() {
986 std::stringstream ss;
987 for (const auto & kv : _rules) {
988 ss << kv.first << " ::= " << kv.second << std::endl;
989 }
990 return ss.str();
991 }
992};
993
994// common_schema_info implementation (pimpl)
995
996common_schema_info::common_schema_info()
997 : impl_(std::make_unique<common_schema_converter>(
998 [](const std::string &) { return json(); },
999 false)) {}
1000
1001common_schema_info::~common_schema_info() = default;
1002
1003common_schema_info::common_schema_info(common_schema_info &&) noexcept = default;
1004common_schema_info & common_schema_info::operator=(common_schema_info &&) noexcept = default;
1005
1006void common_schema_info::resolve_refs(nlohmann::ordered_json & schema) {
1007 impl_->resolve_refs(schema, "");
1008}
1009
1010// Determines if a JSON schema can resolve to a string type through any path.
1011// Some models emit raw string values rather than JSON-encoded strings for string parameters.
1012// If any branch of the schema (via oneOf, anyOf, $ref, etc.) permits a string, this returns
1013// true, allowing callers to handle the value as a raw string for simplicity.
1014bool common_schema_info::resolves_to_string(const nlohmann::ordered_json & schema) {
1015 std::unordered_set<std::string> visited_refs;
1016
1017 std::function<bool(const json &)> check = [&](const json & s) -> bool {
1018 if (!s.is_object()) {
1019 return false;
1020 }
1021
1022 // Handle $ref
1023 if (s.contains("$ref")) {
1024 const std::string & ref = s["$ref"];
1025 if (visited_refs.find(ref) != visited_refs.end()) {
1026 // Circular reference, assume not a string to be safe
1027 return false;
1028 }
1029 visited_refs.insert(ref);
1030 auto it = impl_->_refs.find(ref);
1031 if (it != impl_->_refs.end()) {
1032 return check(it->second);
1033 }
1034 return false;
1035 }
1036
1037 // Check type field
1038 if (s.contains("type")) {
1039 const json & schema_type = s["type"];
1040 if (schema_type.is_string()) {
1041 if (schema_type == "string") {
1042 return true;
1043 }
1044 } else if (schema_type.is_array()) {
1045 // Type can be an array like ["string", "null"]
1046 for (const auto & t : schema_type) {
1047 if (t == "string") {
1048 return true;
1049 }
1050 }
1051 }
1052 }
1053
1054 // Check oneOf/anyOf - if any alternative can be a string
1055 if (s.contains("oneOf")) {
1056 for (const auto & alt : s["oneOf"]) {
1057 if (check(alt)) {
1058 return true;
1059 }
1060 }
1061 }
1062 if (s.contains("anyOf")) {
1063 for (const auto & alt : s["anyOf"]) {
1064 if (check(alt)) {
1065 return true;
1066 }
1067 }
1068 }
1069
1070 // Check allOf - all components must be compatible with string type
1071 if (s.contains("allOf")) {
1072 bool all_string = true;
1073 for (const auto & component : s["allOf"]) {
1074 if (!check(component)) {
1075 all_string = false;
1076 break;
1077 }
1078 }
1079 if (all_string) {
1080 return true;
1081 }
1082 }
1083
1084 // Check const - if the constant value is a string
1085 if (s.contains("const")) {
1086 if (s["const"].is_string()) {
1087 return true;
1088 }
1089 }
1090
1091 // Check enum - if any enum value is a string
1092 if (s.contains("enum")) {
1093 for (const auto & val : s["enum"]) {
1094 if (val.is_string()) {
1095 return true;
1096 }
1097 }
1098 }
1099
1100 // String-specific keywords imply string type
1101 if (s.contains("pattern") || s.contains("minLength") || s.contains("maxLength")) {
1102 return true;
1103 }
1104
1105 // Check format - many formats imply string
1106 if (s.contains("format")) {
1107 const std::string & fmt = s["format"];
1108 if (fmt == "date" || fmt == "time" || fmt == "date-time" ||
1109 fmt == "uri" || fmt == "email" || fmt == "hostname" ||
1110 fmt == "ipv4" || fmt == "ipv6" || fmt == "uuid" ||
1111 fmt.find("uuid") == 0) {
1112 return true;
1113 }
1114 }
1115
1116 return false;
1117 };
1118
1119 return check(schema);
1120}
1121
1122std::string json_schema_to_grammar(const json & schema, bool force_gbnf) {
1123#ifdef LLAMA_USE_LLGUIDANCE
1124 if (!force_gbnf) {
1125 return "%llguidance {}\nstart: %json " + schema.dump();
1126 }
1127#else
1128 (void)force_gbnf;
1129#endif // LLAMA_USE_LLGUIDANCE
1130 return build_grammar([&](const common_grammar_builder & callbacks) {
1131 auto copy = schema;
1132 callbacks.resolve_refs(copy);
1133 callbacks.add_schema("", copy);
1134 });
1135}
1136
1137std::string build_grammar(const std::function<void(const common_grammar_builder &)> & cb, const common_grammar_options & options) {
1138 common_schema_converter converter([&](const std::string &) { return json(); }, options.dotall);
1139 common_grammar_builder builder {
1140 /* .add_rule = */ [&](const std::string & name, const std::string & rule) {
1141 return converter._add_rule(name, rule);
1142 },
1143 /* .add_schema = */ [&](const std::string & name, const nlohmann::ordered_json & schema) {
1144 return converter.visit(schema, name == "root" ? "" : name);
1145 },
1146 /* .resolve_refs = */ [&](nlohmann::ordered_json & schema) {
1147 converter.resolve_refs(schema, "");
1148 }
1149 };
1150 cb(builder);
1151 converter.check_errors();
1152 return converter.format_grammar();
1153}