1  #include "json-schema-to-grammar.h"
  2  #include <algorithm>
  3  #include <fstream>
  4  #include <map>
  5  #include <regex>
  6  #include <sstream>
  7  #include <string>
  8  #include <unordered_map>
  9  #include <unordered_set>
 10  #include <vector>
 11  
 12  using json = nlohmann::ordered_json;
 13  
 14  template <typename Iterator>
 15  static std::string join(Iterator begin, Iterator end, const std::string & separator);
 16  
 17  static std::string repeat(const std::string & str, size_t n);
 18  
 19  static std::string build_repetition(const std::string & item_rule, int min_items, int max_items, const std::string & separator_rule = "") {
 20      auto has_max = max_items != std::numeric_limits<int>::max();
 21  
 22      if (min_items == 0 && max_items == 1) {
 23          return item_rule + "?";
 24      }
 25  
 26      if (separator_rule.empty()) {
 27          if (min_items == 1 && !has_max) {
 28              return item_rule + "+";
 29          } else if (min_items == 0 && !has_max) {
 30              return item_rule + "*";
 31          } else {
 32              return item_rule + "{" + std::to_string(min_items) + "," + (has_max ? std::to_string(max_items) : "") + "}";
 33          }
 34      }
 35  
 36      auto result = item_rule + " " + build_repetition("(" + separator_rule + " " + item_rule + ")", min_items == 0 ? 0 : min_items - 1, has_max ? max_items - 1 : max_items);
 37      if (min_items == 0) {
 38          result = "(" + result + ")?";
 39      }
 40      return result;
 41  }
 42  
 43  const std::string SPACE_RULE = "| \" \" | \"\\n\" [ \\t]{0,20}";
 44  
 45  struct BuiltinRule {
 46      std::string content;
 47      std::vector<std::string> deps;
 48  };
 49  
 50  std::unordered_map<std::string, BuiltinRule> PRIMITIVE_RULES = {
 51      {"boolean", {"(\"true\" | \"false\") space", {}}},
 52      {"decimal-part", {"[0-9]{1,16}", {}}},
 53      {"integral-part", {"[0] | [1-9] [0-9]{0,15}", {}}},
 54      {"number", {"(\"-\"? integral-part) (\".\" decimal-part)? ([eE] [-+]? integral-part)? space", {"integral-part", "decimal-part"}}},
 55      {"integer", {"(\"-\"? integral-part) space", {"integral-part"}}},
 56      {"value", {"object | array | string | number | boolean | null", {"object", "array", "string", "number", "boolean", "null"}}},
 57      {"object", {"\"{\" space ( string \":\" space value (\",\" space string \":\" space value)* )? \"}\" space", {"string", "value"}}},
 58      {"array", {"\"[\" space ( value (\",\" space value)* )? \"]\" space", {"value"}}},
 59      {"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", {}}},
 60      {"char",   {"[^\"\\\\\\x7F\\x00-\\x1F] | [\\\\] ([\"\\\\bfnrt] | \"u\" [0-9a-fA-F]{4})", {}}},
 61      {"string", {"\"\\\"\" char* \"\\\"\" space", {"char"}}},
 62      {"null", {"\"null\" space", {}}},
 63  };
 64  
 65  std::unordered_map<std::string, BuiltinRule> STRING_FORMAT_RULES = {
 66      {"date", {"[0-9]{4} \"-\" ( \"0\" [1-9] | \"1\" [0-2] ) \"-\" ( \"0\" [1-9] | [1-2] [0-9] | \"3\" [0-1] )", {}}},
 67      {"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] )", {}}},
 68      {"date-time", {"date \"T\" time", {"date", "time"}}},
 69      {"date-string", {"\"\\\"\" date \"\\\"\" space", {"date"}}},
 70      {"time-string", {"\"\\\"\" time \"\\\"\" space", {"time"}}},
 71      {"date-time-string", {"\"\\\"\" date-time \"\\\"\" space", {"date-time"}}}
 72  };
 73  
 74  static bool is_reserved_name(const std::string & name) {
 75      static std::unordered_set<std::string> RESERVED_NAMES;
 76      if (RESERVED_NAMES.empty()) {
 77          RESERVED_NAMES.insert("root");
 78          for (const auto &p : PRIMITIVE_RULES) RESERVED_NAMES.insert(p.first);
 79          for (const auto &p : STRING_FORMAT_RULES) RESERVED_NAMES.insert(p.first);
 80      }
 81      return RESERVED_NAMES.find(name) != RESERVED_NAMES.end();
 82  }
 83  
 84  std::regex INVALID_RULE_CHARS_RE("[^a-zA-Z0-9-]+");
 85  std::regex GRAMMAR_LITERAL_ESCAPE_RE("[\r\n\"]");
 86  std::regex GRAMMAR_RANGE_LITERAL_ESCAPE_RE("[\r\n\"\\]\\-\\\\]");
 87  std::unordered_map<char, std::string> GRAMMAR_LITERAL_ESCAPES = {
 88      {'\r', "\\r"}, {'\n', "\\n"}, {'"', "\\\""}, {'-', "\\-"}, {']', "\\]"}
 89  };
 90  
 91  std::unordered_set<char> NON_LITERAL_SET = {'|', '.', '(', ')', '[', ']', '{', '}', '*', '+', '?'};
 92  std::unordered_set<char> ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS = {'[', ']', '(', ')', '|', '{', '}', '*', '+', '?'};
 93  
 94  template <typename Iterator>
 95  std::string join(Iterator begin, Iterator end, const std::string & separator) {
 96      std::ostringstream result;
 97      if (begin != end) {
 98          result << *begin;
 99          for (Iterator it = begin + 1; it != end; ++it) {
100              result << separator << *it;
101          }
102      }
103      return result.str();
104  }
105  
106  static std::vector<std::string> split(const std::string & str, const std::string & delimiter) {
107      std::vector<std::string> tokens;
108      size_t start = 0;
109      size_t end = str.find(delimiter);
110  
111      while (end != std::string::npos) {
112          tokens.push_back(str.substr(start, end - start));
113          start = end + delimiter.length();
114          end = str.find(delimiter, start);
115      }
116  
117      tokens.push_back(str.substr(start));
118  
119      return tokens;
120  }
121  
122  static std::string repeat(const std::string & str, size_t n) {
123      if (n == 0) {
124          return "";
125      }
126  
127      std::string result;
128      result.reserve(str.length() * n);
129  
130      for (size_t i = 0; i < n; ++i) {
131          result += str;
132      }
133  
134      return result;
135  }
136  
137  static std::string replacePattern(const std::string & input, const std::regex & regex, const std::function<std::string(const std::smatch  &)> & replacement) {
138      std::smatch match;
139      std::string result;
140  
141      std::string::const_iterator searchStart(input.cbegin());
142      std::string::const_iterator searchEnd(input.cend());
143  
144      while (std::regex_search(searchStart, searchEnd, match, regex)) {
145          result.append(searchStart, searchStart + match.position());
146          result.append(replacement(match));
147          searchStart = match.suffix().first;
148      }
149  
150      result.append(searchStart, searchEnd);
151  
152      return result;
153  }
154  
155  static std::string format_literal(const std::string & literal) {
156      std::string escaped = replacePattern(literal, GRAMMAR_LITERAL_ESCAPE_RE, [&](const std::smatch & match) {
157          char c = match.str()[0];
158          return GRAMMAR_LITERAL_ESCAPES.at(c);
159      });
160      return "\"" + escaped + "\"";
161  }
162  
163  
164  class SchemaConverter {
165  private:
166      std::function<json(const std::string &)> _fetch_json;
167      bool _dotall;
168      std::map<std::string, std::string> _rules;
169      std::unordered_map<std::string, json> _refs;
170      std::unordered_set<std::string> _refs_being_resolved;
171      std::vector<std::string> _errors;
172      std::vector<std::string> _warnings;
173  
174      std::string _add_rule(const std::string & name, const std::string & rule) {
175          std::string esc_name = regex_replace(name, INVALID_RULE_CHARS_RE, "-");
176          if (_rules.find(esc_name) == _rules.end() || _rules[esc_name] == rule) {
177              _rules[esc_name] = rule;
178              return esc_name;
179          } else {
180              int i = 0;
181              while (_rules.find(esc_name + std::to_string(i)) != _rules.end() && _rules[esc_name + std::to_string(i)] != rule) {
182                  i++;
183              }
184              std::string key = esc_name + std::to_string(i);
185              _rules[key] = rule;
186              return key;
187          }
188      }
189  
190      std::string _generate_union_rule(const std::string & name, const std::vector<json> & alt_schemas) {
191          std::vector<std::string> rules;
192          for (size_t i = 0; i < alt_schemas.size(); i++) {
193              rules.push_back(visit(alt_schemas[i], name + (name.empty() ? "alternative-" : "-") + std::to_string(i)));
194          }
195          return join(rules.begin(), rules.end(), " | ");
196      }
197  
198      std::string _visit_pattern(const std::string & pattern, const std::string & name) {
199          if (!(pattern.front() == '^' && pattern.back() == '$')) {
200              _errors.push_back("Pattern must start with '^' and end with '$'");
201              return "";
202          }
203          std::string sub_pattern = pattern.substr(1, pattern.length() - 2);
204          std::unordered_map<std::string, std::string> sub_rule_ids;
205  
206          size_t i = 0;
207          size_t length = sub_pattern.length();
208  
209          using literal_or_rule = std::pair<std::string, bool>;
210          auto to_rule = [&](const literal_or_rule & ls) {
211              auto is_literal = ls.second;
212              auto s = ls.first;
213              return is_literal ? "\"" + s + "\"" : s;
214          };
215          std::function<literal_or_rule()> transform = [&]() -> literal_or_rule {
216              size_t start = i;
217              std::vector<literal_or_rule> seq;
218  
219              auto get_dot = [&]() {
220                  std::string rule;
221                  if (_dotall) {
222                      rule = "[\\U00000000-\\U0010FFFF]";
223                  } else {
224                      rule = "[^\\x0A\\x0D]";
225                  }
226                  return _add_rule("dot", rule);
227              };
228  
229              // Joins the sequence, merging consecutive literals together.
230              auto join_seq = [&]() {
231                  std::vector<literal_or_rule> ret;
232  
233                  std::string literal;
234                  auto flush_literal = [&]() {
235                      if (literal.empty()) {
236                          return false;
237                      }
238                      ret.emplace_back(literal, true);
239                      literal.clear();
240                      return true;
241                  };
242  
243                  for (const auto & item : seq) {
244                      auto is_literal = item.second;
245                      if (is_literal) {
246                          literal += item.first;
247                      } else {
248                          flush_literal();
249                          ret.push_back(item);
250                      }
251                  }
252                  flush_literal();
253  
254                  std::vector<std::string> results;
255                  for (const auto & item : ret) {
256                      results.push_back(to_rule(item));
257                  }
258                  return std::make_pair(join(results.begin(), results.end(), " "), false);
259              };
260  
261              while (i < length) {
262                  char c = sub_pattern[i];
263                  if (c == '.') {
264                      seq.emplace_back(get_dot(), false);
265                      i++;
266                  } else if (c == '(') {
267                      i++;
268                      if (i < length) {
269                          if (sub_pattern[i] == '?') {
270                              _warnings.push_back("Unsupported pattern syntax");
271                          }
272                      }
273                      seq.emplace_back("(" + to_rule(transform()) + ")", false);
274                  } else if (c == ')') {
275                      i++;
276                      if (start > 0 && sub_pattern[start - 1] != '(') {
277                          _errors.push_back("Unbalanced parentheses");
278                      }
279                      return join_seq();
280                  } else if (c == '[') {
281                      std::string square_brackets = std::string(1, c);
282                      i++;
283                      while (i < length && sub_pattern[i] != ']') {
284                          if (sub_pattern[i] == '\\') {
285                              square_brackets += sub_pattern.substr(i, 2);
286                              i += 2;
287                          } else {
288                              square_brackets += sub_pattern[i];
289                              i++;
290                          }
291                      }
292                      if (i >= length) {
293                          _errors.push_back("Unbalanced square brackets");
294                      }
295                      square_brackets += ']';
296                      i++;
297                      seq.emplace_back(square_brackets, false);
298                  } else if (c == '|') {
299                      seq.emplace_back("|", false);
300                      i++;
301                  } else if (c == '*' || c == '+' || c == '?') {
302                      seq.back() = std::make_pair(to_rule(seq.back()) + c, false);
303                      i++;
304                  } else if (c == '{') {
305                      std::string curly_brackets = std::string(1, c);
306                      i++;
307                      while (i < length && sub_pattern[i] != '}') {
308                          curly_brackets += sub_pattern[i];
309                          i++;
310                      }
311                      if (i >= length) {
312                          _errors.push_back("Unbalanced curly brackets");
313                      }
314                      curly_brackets += '}';
315                      i++;
316                      auto nums = split(curly_brackets.substr(1, curly_brackets.length() - 2), ",");
317                      int min_times = 0;
318                      int max_times = std::numeric_limits<int>::max();
319                      try {
320                          if (nums.size() == 1) {
321                              min_times = max_times = std::stoi(nums[0]);
322                          } else if (nums.size() != 2) {
323                              _errors.push_back("Wrong number of values in curly brackets");
324                          } else {
325                              if (!nums[0].empty()) {
326                                  min_times = std::stoi(nums[0]);
327                              }
328                              if (!nums[1].empty()) {
329                                  max_times = std::stoi(nums[1]);
330                              }
331                          }
332                      } catch (const std::invalid_argument & e) {
333                          _errors.push_back("Invalid number in curly brackets");
334                          return std::make_pair("", false);
335                      }
336                      auto &last = seq.back();
337                      auto &sub = last.first;
338                      auto sub_is_literal = last.second;
339  
340                      if (!sub_is_literal) {
341                          std::string & sub_id = sub_rule_ids[sub];
342                          if (sub_id.empty()) {
343                              sub_id = _add_rule(name + "-" + std::to_string(sub_rule_ids.size()), sub);
344                          }
345                          sub = sub_id;
346                      }
347                      seq.back().first = build_repetition(
348                          sub_is_literal ? "\"" + sub + "\"" : sub,
349                          min_times,
350                          max_times,
351                          ""
352                      );
353                      seq.back().second = false;
354                  } else {
355                      std::string literal;
356                      auto is_non_literal = [&](char c) {
357                          return NON_LITERAL_SET.find(c) != NON_LITERAL_SET.end();
358                      };
359                      while (i < length) {
360                          if (sub_pattern[i] == '\\' && i < length - 1) {
361                              char next = sub_pattern[i + 1];
362                              if (ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS.find(next) != ESCAPED_IN_REGEXPS_BUT_NOT_IN_LITERALS.end()) {
363                                  i++;
364                                  literal += sub_pattern[i];
365                                  i++;
366                              } else {
367                                  literal += sub_pattern.substr(i, 2);
368                                  i += 2;
369                              }
370                          } else if (sub_pattern[i] == '"') {
371                              literal += "\\\"";
372                              i++;
373                          } else if (!is_non_literal(sub_pattern[i]) &&
374                                  (i == length - 1 || literal.empty() || sub_pattern[i + 1] == '.' || !is_non_literal(sub_pattern[i + 1]))) {
375                              literal += sub_pattern[i];
376                              i++;
377                          } else {
378                              break;
379                          }
380                      }
381                      if (!literal.empty()) {
382                          seq.emplace_back(literal, true);
383                      }
384                  }
385              }
386              return join_seq();
387          };
388          return _add_rule(name, "\"\\\"\" " + to_rule(transform()) + " \"\\\"\" space");
389      }
390  
391      std::string _resolve_ref(const std::string & ref) {
392          std::string ref_name = ref.substr(ref.find_last_of('/') + 1);
393          if (_rules.find(ref_name) == _rules.end() && _refs_being_resolved.find(ref) == _refs_being_resolved.end()) {
394              _refs_being_resolved.insert(ref);
395              json resolved = _refs[ref];
396              ref_name = visit(resolved, ref_name);
397              _refs_being_resolved.erase(ref);
398          }
399          return ref_name;
400      }
401  
402      std::string _build_object_rule(
403          const std::vector<std::pair<std::string, json>> & properties,
404          const std::unordered_set<std::string> & required,
405          const std::string & name,
406          const json & additional_properties)
407      {
408          std::vector<std::string> required_props;
409          std::vector<std::string> optional_props;
410          std::unordered_map<std::string, std::string> prop_kv_rule_names;
411          for (const auto & kv : properties) {
412              const auto &prop_name = kv.first;
413              const auto &prop_schema = kv.second;
414  
415              std::string prop_rule_name = visit(prop_schema, name + (name.empty() ? "" : "-") + prop_name);
416              prop_kv_rule_names[prop_name] = _add_rule(
417                  name + (name.empty() ? "" : "-") + prop_name + "-kv",
418                  format_literal(json(prop_name).dump()) + " space \":\" space " + prop_rule_name
419              );
420              if (required.find(prop_name) != required.end()) {
421                  required_props.push_back(prop_name);
422              } else {
423                  optional_props.push_back(prop_name);
424              }
425          }
426          if (additional_properties.is_object() || (additional_properties.is_boolean() && additional_properties.get<bool>())) {
427              std::string sub_name = name + (name.empty() ? "" : "-") + "additional";
428              std::string value_rule = visit(additional_properties.is_object() ? additional_properties : json::object(), sub_name + "-value");
429              std::string kv_rule = _add_rule(sub_name + "-kv", _add_primitive("string", PRIMITIVE_RULES.at("string")) + " \":\" space " + value_rule);
430              prop_kv_rule_names["*"] = kv_rule;
431              optional_props.push_back("*");
432          }
433  
434          std::string rule = "\"{\" space ";
435          for (size_t i = 0; i < required_props.size(); i++) {
436              if (i > 0) {
437                  rule += " \",\" space ";
438              }
439              rule += prop_kv_rule_names[required_props[i]];
440          }
441  
442          if (!optional_props.empty()) {
443              rule += " (";
444              if (!required_props.empty()) {
445                  rule += " \",\" space ( ";
446              }
447  
448              std::function<std::string(const std::vector<std::string> &, bool)> get_recursive_refs = [&](const std::vector<std::string> & ks, bool first_is_optional) {
449                  std::string res;
450                  if (ks.empty()) {
451                      return res;
452                  }
453                  std::string k = ks[0];
454                  std::string kv_rule_name = prop_kv_rule_names[k];
455                  if (k == "*") {
456                      res = _add_rule(
457                          name + (name.empty() ? "" : "-") + "additional-kvs",
458                          kv_rule_name + " ( \",\" space " + kv_rule_name + " )*"
459                      );
460                  } else if (first_is_optional) {
461                      res = "( \",\" space " + kv_rule_name + " )?";
462                  } else {
463                      res = kv_rule_name;
464                  }
465                  if (ks.size() > 1) {
466                      res += " " + _add_rule(
467                          name + (name.empty() ? "" : "-") + k + "-rest",
468                          get_recursive_refs(std::vector<std::string>(ks.begin() + 1, ks.end()), true)
469                      );
470                  }
471                  return res;
472              };
473  
474              for (size_t i = 0; i < optional_props.size(); i++) {
475                  if (i > 0) {
476                      rule += " | ";
477                  }
478                  rule += get_recursive_refs(std::vector<std::string>(optional_props.begin() + i, optional_props.end()), false);
479              }
480              if (!required_props.empty()) {
481                  rule += " )";
482              }
483              rule += " )?";
484          }
485  
486          rule += " \"}\" space";
487  
488          return rule;
489      }
490  
491      std::string _add_primitive(const std::string & name, const BuiltinRule & rule) {
492          auto n = _add_rule(name, rule.content);
493          for (const auto & dep : rule.deps) {
494              BuiltinRule dep_rule;
495              auto it = PRIMITIVE_RULES.find(dep);
496              if (it == PRIMITIVE_RULES.end()) {
497                  it = STRING_FORMAT_RULES.find(dep);
498                  if (it == STRING_FORMAT_RULES.end()) {
499                      _errors.push_back("Rule " + dep + " not known");
500                      continue;
501                  }
502              }
503              if (_rules.find(dep) == _rules.end()) {
504                  _add_primitive(dep, it->second);
505              }
506          }
507          return n;
508      }
509  
510  public:
511      SchemaConverter(
512          const std::function<json(const std::string &)> & fetch_json,
513          bool dotall)
514            : _fetch_json(fetch_json), _dotall(dotall)
515      {
516          _rules["space"] = SPACE_RULE;
517      }
518  
519      void resolve_refs(json & schema, const std::string & url) {
520          /*
521          * Resolves all $ref fields in the given schema, fetching any remote schemas,
522          * replacing each $ref with absolute reference URL and populates _refs with the
523          * respective referenced (sub)schema dictionaries.
524          */
525          std::function<void(json &)> visit_refs = [&](json & n) {
526              if (n.is_array()) {
527                  for (auto & x : n) {
528                      visit_refs(x);
529                  }
530              } else if (n.is_object()) {
531                  if (n.contains("$ref")) {
532                      std::string ref = n["$ref"];
533                      if (_refs.find(ref) == _refs.end()) {
534                          json target;
535                          if (ref.find("https://") == 0) {
536                              std::string base_url = ref.substr(0, ref.find('#'));
537                              auto it = _refs.find(base_url);
538                              if (it != _refs.end()) {
539                                  target = it->second;
540                              } else {
541                                  // Fetch the referenced schema and resolve its refs
542                                  auto referenced = _fetch_json(ref);
543                                  resolve_refs(referenced, base_url);
544                                  _refs[base_url] = referenced;
545                              }
546                              if (ref.find('#') == std::string::npos || ref.substr(ref.find('#') + 1).empty()) {
547                                  return;
548                              }
549                          } else if (ref.find("#/") == 0) {
550                              target = schema;
551                              n["$ref"] = url + ref;
552                              ref = url + ref;
553                          } else {
554                              _errors.push_back("Unsupported ref: " + ref);
555                              return;
556                          }
557                          std::string pointer = ref.substr(ref.find('#') + 1);
558                          std::vector<std::string> tokens = split(pointer, "/");
559                          for (size_t i = 1; i < tokens.size(); ++i) {
560                              std::string sel = tokens[i];
561                              if (target.is_null() || !target.contains(sel)) {
562                                  _errors.push_back("Error resolving ref " + ref + ": " + sel + " not in " + target.dump());
563                                  return;
564                              }
565                              target = target[sel];
566                          }
567                          _refs[ref] = target;
568                      }
569                  } else {
570                      for (auto & kv : n.items()) {
571                          visit_refs(kv.value());
572                      }
573                  }
574              }
575          };
576  
577          visit_refs(schema);
578      }
579  
580      std::string _generate_constant_rule(const json & value) {
581          return format_literal(value.dump());
582      }
583  
584      std::string visit(const json & schema, const std::string & name) {
585          json schema_type = schema.contains("type") ? schema["type"] : json();
586          std::string schema_format = schema.contains("format") ? schema["format"].get<std::string>() : "";
587          std::string rule_name = is_reserved_name(name) ? name + "-" : name.empty() ? "root" : name;
588  
589          if (schema.contains("$ref")) {
590              return _add_rule(rule_name, _resolve_ref(schema["$ref"]));
591          } else if (schema.contains("oneOf") || schema.contains("anyOf")) {
592              std::vector<json> alt_schemas = schema.contains("oneOf") ? schema["oneOf"].get<std::vector<json>>() : schema["anyOf"].get<std::vector<json>>();
593              return _add_rule(rule_name, _generate_union_rule(name, alt_schemas));
594          } else if (schema_type.is_array()) {
595              std::vector<json> schema_types;
596              for (const auto & t : schema_type) {
597                  schema_types.push_back({{"type", t}});
598              }
599              return _add_rule(rule_name, _generate_union_rule(name, schema_types));
600          } else if (schema.contains("const")) {
601              return _add_rule(rule_name, _generate_constant_rule(schema["const"]));
602          } else if (schema.contains("enum")) {
603              std::vector<std::string> enum_values;
604              for (const auto & v : schema["enum"]) {
605                  enum_values.push_back(_generate_constant_rule(v));
606              }
607              return _add_rule(rule_name, join(enum_values.begin(), enum_values.end(), " | "));
608          } else if ((schema_type.is_null() || schema_type == "object")
609                  && (schema.contains("properties") ||
610                      (schema.contains("additionalProperties") && schema["additionalProperties"] != true))) {
611              std::unordered_set<std::string> required;
612              if (schema.contains("required") && schema["required"].is_array()) {
613                  for (const auto & item : schema["required"]) {
614                      if (item.is_string()) {
615                          required.insert(item.get<std::string>());
616                      }
617                  }
618              }
619              std::vector<std::pair<std::string, json>> properties;
620              if (schema.contains("properties")) {
621                  for (const auto & prop : schema["properties"].items()) {
622                      properties.emplace_back(prop.key(), prop.value());
623                  }
624              }
625              return _add_rule(rule_name,
626                  _build_object_rule(
627                      properties, required, name,
628                      schema.contains("additionalProperties") ? schema["additionalProperties"] : json()));
629          } else if ((schema_type.is_null() || schema_type == "object") && schema.contains("allOf")) {
630              std::unordered_set<std::string> required;
631              std::vector<std::pair<std::string, json>> properties;
632              std::string hybrid_name = name;
633              std::function<void(const json &, bool)> add_component = [&](const json & comp_schema, bool is_required) {
634                  if (comp_schema.contains("$ref")) {
635                      add_component(_refs[comp_schema["$ref"]], is_required);
636                  } else if (comp_schema.contains("properties")) {
637                      for (const auto & prop : comp_schema["properties"].items()) {
638                          properties.emplace_back(prop.key(), prop.value());
639                          if (is_required) {
640                              required.insert(prop.key());
641                          }
642                      }
643                  } else {
644                    // todo warning
645                  }
646              };
647              for (auto & t : schema["allOf"]) {
648                  if (t.contains("anyOf")) {
649                      for (auto & tt : t["anyOf"]) {
650                          add_component(tt, false);
651                      }
652                  } else {
653                      add_component(t, true);
654                  }
655              }
656              return _add_rule(rule_name, _build_object_rule(properties, required, hybrid_name, json()));
657          } else if ((schema_type.is_null() || schema_type == "array") && (schema.contains("items") || schema.contains("prefixItems"))) {
658              json items = schema.contains("items") ? schema["items"] : schema["prefixItems"];
659              if (items.is_array()) {
660                  std::string rule = "\"[\" space ";
661                  for (size_t i = 0; i < items.size(); i++) {
662                      if (i > 0) {
663                          rule += " \",\" space ";
664                      }
665                      rule += visit(items[i], name + (name.empty() ? "" : "-") + "tuple-" + std::to_string(i));
666                  }
667                  rule += " \"]\" space";
668                  return _add_rule(rule_name, rule);
669              } else {
670                  std::string item_rule_name = visit(items, name + (name.empty() ? "" : "-") + "item");
671                  int min_items = schema.contains("minItems") ? schema["minItems"].get<int>() : 0;
672                  json max_items_json = schema.contains("maxItems") ? schema["maxItems"] : json();
673                  int max_items = max_items_json.is_number_integer() ? max_items_json.get<int>() : std::numeric_limits<int>::max();
674  
675                  return _add_rule(rule_name, "\"[\" space " + build_repetition(item_rule_name, min_items, max_items, "\",\" space") + " \"]\" space");
676              }
677          } else if ((schema_type.is_null() || schema_type == "string") && schema.contains("pattern")) {
678              return _visit_pattern(schema["pattern"], rule_name);
679          } else if ((schema_type.is_null() || schema_type == "string") && std::regex_match(schema_format, std::regex("^uuid[1-5]?$"))) {
680              return _add_primitive(rule_name == "root" ? "root" : schema_format, PRIMITIVE_RULES.at("uuid"));
681          } else if ((schema_type.is_null() || schema_type == "string") && STRING_FORMAT_RULES.find(schema_format + "-string") != STRING_FORMAT_RULES.end()) {
682              auto prim_name = schema_format + "-string";
683              return _add_rule(rule_name, _add_primitive(prim_name, STRING_FORMAT_RULES.at(prim_name)));
684          } else if (schema_type == "string" && (schema.contains("minLength") || schema.contains("maxLength"))) {
685              std::string char_rule = _add_primitive("char", PRIMITIVE_RULES.at("char"));
686              int min_len = schema.contains("minLength") ? schema["minLength"].get<int>() : 0;
687              int max_len = schema.contains("maxLength") ? schema["maxLength"].get<int>() : std::numeric_limits<int>::max();
688              return _add_rule(rule_name, "\"\\\"\" " + build_repetition(char_rule, min_len, max_len) + " \"\\\"\" space");
689          } else if (schema.empty() || schema_type == "object") {
690              return _add_rule(rule_name, _add_primitive("object", PRIMITIVE_RULES.at("object")));
691          } else {
692              if (!schema_type.is_string() || PRIMITIVE_RULES.find(schema_type.get<std::string>()) == PRIMITIVE_RULES.end()) {
693                  _errors.push_back("Unrecognized schema: " + schema.dump());
694                  return "";
695              }
696              // TODO: support minimum, maximum, exclusiveMinimum, exclusiveMaximum at least for zero
697              return _add_primitive(rule_name == "root" ? "root" : schema_type.get<std::string>(), PRIMITIVE_RULES.at(schema_type.get<std::string>()));
698          }
699      }
700  
701      void check_errors() {
702          if (!_errors.empty()) {
703              throw std::runtime_error("JSON schema conversion failed:\n" + join(_errors.begin(), _errors.end(), "\n"));
704          }
705          if (!_warnings.empty()) {
706              fprintf(stderr, "WARNING: JSON schema conversion was incomplete: %s\n", join(_warnings.begin(), _warnings.end(), "; ").c_str());
707          }
708      }
709  
710      std::string format_grammar() {
711          std::stringstream ss;
712          for (const auto & kv : _rules) {
713              ss << kv.first << " ::= " << kv.second << std::endl;
714          }
715          return ss.str();
716      }
717  };
718  
719  std::string json_schema_to_grammar(const json & schema) {
720      SchemaConverter converter([](const std::string &) { return json::object(); }, /* dotall= */ false);
721      auto copy = schema;
722      converter.resolve_refs(copy, "input");
723      converter.visit(copy, "");
724      converter.check_errors();
725      return converter.format_grammar();
726  }