char-fork/llama.cpp

git clone https://git.t4t.associates/char-fork/llama.cpp

Aldehir Rojascommon : implement common_schema internal representation for JSON schemas (#28736)acecd5603

char/aliceai-t5-moe
brancheschar/aliceai-t5-moeall refs →
47.8 KiB1580 linesraw
1#ifdef NDEBUG
2#undef NDEBUG
3#endif
4
5#include "json-schema-to-grammar.h"
6
7#include "../src/llama-grammar.h"
8
9#include "json.h"
10
11#include <cassert>
12#include <regex>
13
14static std::string trim(const std::string & source) {
15    std::string s(source);
16    s.erase(0,s.find_first_not_of(" \n\r\t"));
17    s.erase(s.find_last_not_of(" \n\r\t")+1);
18    return std::regex_replace(s, std::regex("(^|\n)[ \t]+"), "$1");
19}
20
21enum TestCaseStatus {
22    SUCCESS,
23    FAILURE
24};
25
26struct TestCase {
27    TestCaseStatus expected_status;
28    std::string name;
29    std::string schema;
30    std::string expected_grammar;
31
32    void _print_failure_header() const {
33        fprintf(stderr, "#\n# Test '%s' failed.\n#\n%s\n", name.c_str(), schema.c_str());
34    }
35    void verify(const std::string & actual_grammar) const {
36        if (trim(actual_grammar) != trim(expected_grammar)) {
37        _print_failure_header();
38        fprintf(stderr, "# EXPECTED:\n%s\n# ACTUAL:\n%s\n", expected_grammar.c_str(), actual_grammar.c_str());
39        assert(false);
40        }
41    }
42    void verify_expectation_parseable() const {
43        try {
44            llama_grammar_parser state;
45            state.parse(expected_grammar.c_str());
46            if (state.symbol_ids.find("root") == state.symbol_ids.end()) {
47                throw std::runtime_error("Grammar failed to parse:\n" + expected_grammar);
48            }
49        } catch (const std::runtime_error & ex) {
50            _print_failure_header();
51            fprintf(stderr, "# GRAMMAR ERROR: %s\n", ex.what());
52            assert(false);
53        }
54    }
55    void verify_status(TestCaseStatus status) const {
56        if (status != expected_status) {
57            _print_failure_header();
58            fprintf(stderr, "# EXPECTED STATUS: %s\n", expected_status == SUCCESS ? "SUCCESS" : "FAILURE");
59            fprintf(stderr, "# ACTUAL STATUS: %s\n", status == SUCCESS ? "SUCCESS" : "FAILURE");
60            assert(false);
61        }
62    }
63};
64
65static void test_all(const std::string & title, std::function<void(const TestCase &)> runner) {
66    fprintf(stderr, "#\n# %s\n#\n", title.c_str());
67    auto test = [&](const TestCase & tc) {
68        fprintf(stderr, "- %s%s\n", tc.name.c_str(), tc.expected_status == FAILURE ? " (failure expected)" : "");
69        runner(tc);
70    };
71
72    test({
73        SUCCESS,
74        "min 0",
75        R"""({
76            "type": "integer",
77            "minimum": 0
78        })""",
79        R"""(
80            root ::= ([0] | [1-9] [0-9]{0,15})
81            space ::= | " " | "\n"{1,2} [ \t]{0,20}
82        )"""
83    });
84
85    test({
86        SUCCESS,
87        "min 1",
88        R"""({
89            "type": "integer",
90            "minimum": 1
91        })""",
92        R"""(
93            root ::= ([1-9] [0-9]{0,15})
94            space ::= | " " | "\n"{1,2} [ \t]{0,20}
95        )"""
96    });
97
98    test({
99        SUCCESS,
100        "min 3",
101        R"""({
102            "type": "integer",
103            "minimum": 3
104        })""",
105        R"""(
106            root ::= ([1-2] [0-9]{1,15} | [3-9] [0-9]{0,15})
107            space ::= | " " | "\n"{1,2} [ \t]{0,20}
108        )"""
109    });
110
111    test({
112        SUCCESS,
113        "min 9",
114        R"""({
115            "type": "integer",
116            "minimum": 9
117        })""",
118        R"""(
119            root ::= ([1-8] [0-9]{1,15} | [9] [0-9]{0,15})
120            space ::= | " " | "\n"{1,2} [ \t]{0,20}
121        )"""
122    });
123
124    test({
125        SUCCESS,
126        "min 10",
127        R"""({
128            "type": "integer",
129            "minimum": 10
130        })""",
131        R"""(
132            root ::= ([1] ([0-9]{1,15}) | [2-9] [0-9]{1,15})
133            space ::= | " " | "\n"{1,2} [ \t]{0,20}
134        )"""
135    });
136
137    test({
138        SUCCESS,
139        "min 25",
140        R"""({
141            "type": "integer",
142            "minimum": 25
143        })""",
144        R"""(
145            root ::= ([1] [0-9]{2,15} | [2] ([0-4] [0-9]{1,14} | [5-9] [0-9]{0,14}) | [3-9] [0-9]{1,15})
146            space ::= | " " | "\n"{1,2} [ \t]{0,20}
147        )"""
148    });
149
150    test({
151        SUCCESS,
152        "max 30",
153        R"""({
154            "type": "integer",
155            "maximum": 30
156        })""",
157        R"""(
158            root ::= ("-" [1-9] [0-9]{0,15} | [0-9] | ([1-2] [0-9] | [3] "0"))
159            space ::= | " " | "\n"{1,2} [ \t]{0,20}
160        )"""
161    });
162
163    test({
164        SUCCESS,
165        "min -5",
166        R"""({
167            "type": "integer",
168            "minimum": -5
169        })""",
170        R"""(
171            root ::= ("-" ([0-5]) | [0] | [1-9] [0-9]{0,15})
172            space ::= | " " | "\n"{1,2} [ \t]{0,20}
173        )"""
174    });
175
176    test({
177        SUCCESS,
178        "min -123",
179        R"""({
180            "type": "integer",
181            "minimum": -123
182        })""",
183        R"""(
184            root ::= ("-" ([0-9] | ([1-8] [0-9] | [9] [0-9]) | "1" ([0-1] [0-9] | [2] [0-3])) | [0] | [1-9] [0-9]{0,15})
185            space ::= | " " | "\n"{1,2} [ \t]{0,20}
186        )"""
187    });
188
189    test({
190        SUCCESS,
191        "max -5",
192        R"""({
193            "type": "integer",
194            "maximum": -5
195        })""",
196        R"""(
197            root ::= ("-" ([0-4] [0-9]{1,15} | [5-9] [0-9]{0,15}))
198            space ::= | " " | "\n"{1,2} [ \t]{0,20}
199        )"""
200    });
201
202    test({
203        SUCCESS,
204        "max 1",
205        R"""({
206            "type": "integer",
207            "maximum": 1
208        })""",
209        R"""(
210            root ::= ("-" [1-9] [0-9]{0,15} | [0-1])
211            space ::= | " " | "\n"{1,2} [ \t]{0,20}
212        )"""
213    });
214
215    test({
216        SUCCESS,
217        "max 100",
218        R"""({
219            "type": "integer",
220            "maximum": 100
221        })""",
222        R"""(
223            root ::= ("-" [1-9] [0-9]{0,15} | [0-9] | ([1-8] [0-9] | [9] [0-9]) | "100")
224            space ::= | " " | "\n"{1,2} [ \t]{0,20}
225        )"""
226    });
227
228    test({
229        SUCCESS,
230        "min 0 max 23",
231        R"""({
232            "type": "integer",
233            "minimum": 0,
234            "maximum": 23
235        })""",
236        R"""(
237            root ::= ([0-9] | ([1] [0-9] | [2] [0-3]))
238            space ::= | " " | "\n"{1,2} [ \t]{0,20}
239        )"""
240    });
241
242    test({
243        SUCCESS,
244        "min 15 max 300",
245        R"""({
246            "type": "integer",
247            "minimum": 15,
248            "maximum": 300
249        })""",
250        R"""(
251            root ::= (([1] ([5-9]) | [2-9] [0-9]) | ([1-2] [0-9]{2} | [3] "00"))
252            space ::= | " " | "\n"{1,2} [ \t]{0,20}
253        )"""
254    });
255
256    test({
257        SUCCESS,
258        "min 5 max 30",
259        R"""({
260            "type": "integer",
261            "minimum": 5,
262            "maximum": 30
263        })""",
264        R"""(
265            root ::= ([5-9] | ([1-2] [0-9] | [3] "0"))
266            space ::= | " " | "\n"{1,2} [ \t]{0,20}
267        )"""
268    });
269
270    test({
271        SUCCESS,
272        "min -123 max 42",
273        R"""({
274            "type": "integer",
275            "minimum": -123,
276            "maximum": 42
277        })""",
278        R"""(
279            root ::= ("-" ([0-9] | ([1-8] [0-9] | [9] [0-9]) | "1" ([0-1] [0-9] | [2] [0-3])) | [0-9] | ([1-3] [0-9] | [4] [0-2]))
280            space ::= | " " | "\n"{1,2} [ \t]{0,20}
281        )"""
282    });
283
284    test({
285        SUCCESS,
286        "min -10 max 10",
287        R"""({
288            "type": "integer",
289            "minimum": -10,
290            "maximum": 10
291        })""",
292        R"""(
293            root ::= ("-" ([0-9] | "10") | [0-9] | "10")
294            space ::= | " " | "\n"{1,2} [ \t]{0,20}
295        )"""
296    });
297
298    test({
299        FAILURE,
300        "unknown type",
301        R"""({
302            "type": "kaboom"
303        })""",
304        ""
305    });
306
307    test({
308        FAILURE,
309        "invalid type",
310        R"""({
311            "type": 123
312        })""",
313        ""
314    });
315
316    test({
317        SUCCESS,
318        "empty schema (any value)",
319        "{}",
320        R"""(
321            array ::= "[" space ( value ("," space value)* )? space "]"
322            boolean ::= ("true" | "false")
323            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
324            decimal-part ::= [0-9]{1,16}
325            integral-part ::= [0] | [1-9] [0-9]{0,15}
326            null ::= "null"
327            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
328            object ::= "{" space ( string ":" space value ("," space string ":" space value)* )? space "}"
329            root ::= value
330            space ::= | " " | "\n"{1,2} [ \t]{0,20}
331            string ::= "\"" char* "\""
332            value ::= object | array | string | number | boolean | null
333        )"""
334    });
335
336    test({
337        SUCCESS,
338        "exotic formats",
339        R"""({
340            "items": [
341                { "format": "date" },
342                { "format": "uuid" },
343                { "format": "time" },
344                { "format": "date-time" }
345            ]
346        })""",
347        R"""(
348            date ::= [0-9]{4} "-" ( "0" [1-9] | "1" [0-2] ) "-" ( "0" [1-9] | [1-2] [0-9] | "3" [0-1] )
349            date-string ::= "\"" date "\""
350            date-time ::= date "T" time
351            date-time-string ::= "\"" date-time "\""
352            root ::= "[" space tuple-0 "," space uuid "," space tuple-2 "," space tuple-3 space "]"
353            space ::= | " " | "\n"{1,2} [ \t]{0,20}
354            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] )
355            time-string ::= "\"" time "\""
356            tuple-0 ::= date-string
357            tuple-2 ::= time-string
358            tuple-3 ::= date-time-string
359            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} "\""
360        )"""
361    });
362
363    test({
364        SUCCESS,
365        "string",
366        R"""({
367            "type": "string"
368        })""",
369        R"""(
370            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
371            root ::= "\"" char* "\""
372            space ::= | " " | "\n"{1,2} [ \t]{0,20}
373        )"""
374    });
375
376    test({
377        SUCCESS,
378        "string w/ min length 1",
379        R"""({
380            "type": "string",
381            "minLength": 1
382        })""",
383        R"""(
384            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
385            root ::= "\"" char+ "\""
386            space ::= | " " | "\n"{1,2} [ \t]{0,20}
387        )"""
388    });
389
390    test({
391        SUCCESS,
392        "string w/ min length 3",
393        R"""({
394            "type": "string",
395            "minLength": 3
396        })""",
397        R"""(
398            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
399            root ::= "\"" char{3,} "\""
400            space ::= | " " | "\n"{1,2} [ \t]{0,20}
401        )"""
402    });
403
404    test({
405        SUCCESS,
406        "string w/ max length",
407        R"""({
408            "type": "string",
409            "maxLength": 3
410        })""",
411        R"""(
412            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
413            root ::= "\"" char{0,3} "\""
414            space ::= | " " | "\n"{1,2} [ \t]{0,20}
415        )"""
416    });
417
418    test({
419        SUCCESS,
420        "string w/ min & max length",
421        R"""({
422            "type": "string",
423            "minLength": 1,
424            "maxLength": 4
425        })""",
426        R"""(
427            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
428            root ::= "\"" char{1,4} "\""
429            space ::= | " " | "\n"{1,2} [ \t]{0,20}
430        )"""
431    });
432
433    test({
434        SUCCESS,
435        "boolean",
436        R"""({
437            "type": "boolean"
438        })""",
439        R"""(
440            root ::= ("true" | "false")
441            space ::= | " " | "\n"{1,2} [ \t]{0,20}
442        )"""
443    });
444
445    test({
446        SUCCESS,
447        "integer",
448        R"""({
449            "type": "integer"
450        })""",
451        R"""(
452            integral-part ::= [0] | [1-9] [0-9]{0,15}
453            root ::= ("-"? integral-part)
454            space ::= | " " | "\n"{1,2} [ \t]{0,20}
455        )"""
456    });
457
458    test({
459        SUCCESS,
460        "string const",
461        R"""({
462            "const": "foo"
463        })""",
464        R"""(
465            root ::= "\"foo\""
466            space ::= | " " | "\n"{1,2} [ \t]{0,20}
467        )"""
468    });
469
470    test({
471        SUCCESS,
472        "non-string const",
473        R"""({
474            "const": 123
475        })""",
476        R"""(
477            root ::= "123"
478            space ::= | " " | "\n"{1,2} [ \t]{0,20}
479        )"""
480    });
481
482    test({
483        SUCCESS,
484        "non-string enum",
485        R"""({
486            "enum": ["red", "amber", "green", null, 42, ["foo"]]
487        })""",
488        R"""(
489            root ::= ("\"red\"" | "\"amber\"" | "\"green\"" | "null" | "42" | "[\"foo\"]")
490            space ::= | " " | "\n"{1,2} [ \t]{0,20}
491        )"""
492    });
493
494    test({
495        SUCCESS,
496        "string array",
497        R"""({
498            "type": "array",
499            "prefixItems": { "type": "string" }
500        })""",
501        R"""(
502            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
503            root ::= "[" space (string ("," space string)*)? space "]"
504            space ::= | " " | "\n"{1,2} [ \t]{0,20}
505            string ::= "\"" char* "\""
506        )"""
507    });
508
509    test({
510        SUCCESS,
511        "nullable string array",
512        R"""({
513            "type": ["array", "null"],
514            "prefixItems": { "type": "string" }
515        })""",
516        R"""(
517            alternative-0 ::= "[" space (string ("," space string)*)? space "]"
518            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
519            null ::= "null"
520            root ::= alternative-0 | null
521            space ::= | " " | "\n"{1,2} [ \t]{0,20}
522            string ::= "\"" char* "\""
523        )"""
524    });
525
526    test({
527        SUCCESS,
528        "tuple1",
529        R"""({
530            "prefixItems": [{ "type": "string" }]
531        })""",
532        R"""(
533            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
534            root ::= "[" space string space "]"
535            space ::= | " " | "\n"{1,2} [ \t]{0,20}
536            string ::= "\"" char* "\""
537        )"""
538    });
539
540    test({
541        SUCCESS,
542        "tuple2",
543        R"""({
544            "prefixItems": [{ "type": "string" }, { "type": "number" }]
545        })""",
546        R"""(
547            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
548            decimal-part ::= [0-9]{1,16}
549            integral-part ::= [0] | [1-9] [0-9]{0,15}
550            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
551            root ::= "[" space string "," space number space "]"
552            space ::= | " " | "\n"{1,2} [ \t]{0,20}
553            string ::= "\"" char* "\""
554        )"""
555    });
556
557    // items {} constrains nothing, the same as no items at all
558    test({
559        SUCCESS,
560        "array with empty items",
561        R"""({
562            "type": "array",
563            "items": {}
564        })""",
565        R"""(
566            array ::= "[" space ( value ("," space value)* )? space "]"
567            boolean ::= ("true" | "false")
568            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
569            decimal-part ::= [0-9]{1,16}
570            integral-part ::= [0] | [1-9] [0-9]{0,15}
571            null ::= "null"
572            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
573            object ::= "{" space ( string ":" space value ("," space string ":" space value)* )? space "}"
574            root ::= "[" space ( value ("," space value)* )? space "]"
575            space ::= | " " | "\n"{1,2} [ \t]{0,20}
576            string ::= "\"" char* "\""
577            value ::= object | array | string | number | boolean | null
578        )"""
579    });
580
581    test({
582        SUCCESS,
583        "array with empty items and prefixItems",
584        R"""({
585            "type": "array",
586            "items": {},
587            "prefixItems": { "type": "string" }
588        })""",
589        R"""(
590            array ::= "[" space ( value ("," space value)* )? space "]"
591            boolean ::= ("true" | "false")
592            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
593            decimal-part ::= [0-9]{1,16}
594            integral-part ::= [0] | [1-9] [0-9]{0,15}
595            null ::= "null"
596            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
597            object ::= "{" space ( string ":" space value ("," space string ":" space value)* )? space "}"
598            root ::= "[" space ( value ("," space value)* )? space "]"
599            space ::= | " " | "\n"{1,2} [ \t]{0,20}
600            string ::= "\"" char* "\""
601            value ::= object | array | string | number | boolean | null
602        )"""
603    });
604
605    test({
606        SUCCESS,
607        "number",
608        R"""({
609            "type": "number"
610        })""",
611        R"""(
612            decimal-part ::= [0-9]{1,16}
613            integral-part ::= [0] | [1-9] [0-9]{0,15}
614            root ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
615            space ::= | " " | "\n"{1,2} [ \t]{0,20}
616        )"""
617    });
618
619    test({
620        SUCCESS,
621        "minItems",
622        R"""({
623            "items": {
624                "type": "boolean"
625            },
626            "minItems": 2
627        })""",
628        R"""(
629            boolean ::= ("true" | "false")
630            root ::= "[" space boolean ("," space boolean)+ space "]"
631            space ::= | " " | "\n"{1,2} [ \t]{0,20}
632        )"""
633    });
634
635    test({
636        SUCCESS,
637        "maxItems 0",
638        R"""({
639            "items": {
640                "type": "boolean"
641            },
642            "maxItems": 0
643        })""",
644        R"""(
645            boolean ::= ("true" | "false")
646            root ::= "[" space  space "]"
647            space ::= | " " | "\n"{1,2} [ \t]{0,20}
648        )"""
649    });
650
651    test({
652        SUCCESS,
653        "maxItems 1",
654        R"""({
655            "items": {
656                "type": "boolean"
657            },
658            "maxItems": 1
659        })""",
660        R"""(
661            boolean ::= ("true" | "false")
662            root ::= "[" space boolean? space "]"
663            space ::= | " " | "\n"{1,2} [ \t]{0,20}
664        )"""
665    });
666
667    test({
668        SUCCESS,
669        "maxItems 2",
670        R"""({
671            "items": {
672                "type": "boolean"
673            },
674            "maxItems": 2
675        })""",
676        R"""(
677            boolean ::= ("true" | "false")
678            root ::= "[" space (boolean ("," space boolean)?)? space "]"
679            space ::= | " " | "\n"{1,2} [ \t]{0,20}
680        )"""
681    });
682
683    test({
684        SUCCESS,
685        "min + maxItems",
686        R"""({
687            "items": {
688                "type": ["number", "integer"]
689            },
690            "minItems": 3,
691            "maxItems": 5
692        })""",
693        R"""(
694            decimal-part ::= [0-9]{1,16}
695            integer ::= ("-"? integral-part)
696            integral-part ::= [0] | [1-9] [0-9]{0,15}
697            item ::= number | integer
698            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
699            root ::= "[" space item ("," space item){2,4} space "]"
700            space ::= | " " | "\n"{1,2} [ \t]{0,20}
701        )"""
702    });
703
704    test({
705        SUCCESS,
706        "min + max items with min + max values across zero",
707        R"""({
708            "items": {
709                "type": "integer",
710                "minimum": -12,
711                "maximum": 207
712            },
713            "minItems": 3,
714            "maxItems": 5
715        })""",
716        R"""(
717            item ::= ("-" ([0-9] | "1" [0-2]) | [0-9] | ([1-8] [0-9] | [9] [0-9]) | ([1] [0-9]{2} | [2] "0" [0-7]))
718            root ::= "[" space item ("," space item){2,4} space "]"
719            space ::= | " " | "\n"{1,2} [ \t]{0,20}
720        )"""
721    });
722
723    test({
724        SUCCESS,
725        "min + max items with min + max values",
726        R"""({
727            "items": {
728                "type": "integer",
729                "minimum": 12,
730                "maximum": 207
731            },
732            "minItems": 3,
733            "maxItems": 5
734        })""",
735        R"""(
736            item ::= (([1] ([2-9]) | [2-9] [0-9]) | ([1] [0-9]{2} | [2] "0" [0-7]))
737            root ::= "[" space item ("," space item){2,4} space "]"
738            space ::= | " " | "\n"{1,2} [ \t]{0,20}
739        )"""
740    });
741
742    test({
743        SUCCESS,
744        "simple regexp",
745        R"""({
746            "type": "string",
747            "pattern": "^abc?d*efg+(hij)?kl$"
748        })""",
749        R"""(
750            root ::= "\"" ("ab" "c"? "d"* "ef" "g"+ ("hij")? "kl") "\""
751            space ::= | " " | "\n"{1,2} [ \t]{0,20}
752        )"""
753    });
754
755    test({
756        SUCCESS,
757        "regexp escapes",
758        R"""({
759            "type": "string",
760            "pattern": "^\\[\\]\\{\\}\\(\\)\\|\\+\\*\\?$"
761        })""",
762        R"""(
763            root ::= "\"" ("[]{}()|+*?") "\""
764            space ::= | " " | "\n"{1,2} [ \t]{0,20}
765        )"""
766    });
767
768    test({
769        SUCCESS,
770        "regexp quote",
771        R"""({
772            "type": "string",
773            "pattern": "^\"$"
774        })""",
775        R"""(
776            root ::= "\"" ("\"") "\""
777            space ::= | " " | "\n"{1,2} [ \t]{0,20}
778        )"""
779    });
780
781    test({
782        SUCCESS,
783        "regexp with top-level alternation",
784        R"""({
785            "type": "string",
786            "pattern": "^A|B|C|D$"
787        })""",
788        R"""(
789            root ::= "\"" ("A" | "B" | "C" | "D") "\""
790            space ::= | " " | "\n"{1,2} [ \t]{0,20}
791        )"""
792    });
793
794    test({
795        SUCCESS,
796        "regexp",
797        R"""({
798            "type": "string",
799            "pattern": "^(\\([0-9]{1,3}\\))?[0-9]{3}-[0-9]{4} a{3,5}nd...$"
800        })""",
801        R"""(
802            dot ::= [^\x0A\x0D]
803            root ::= "\"" (("(" root-1{1,3} ")")? root-1{3,3} "-" root-1{4,4} " " "a"{3,5} "nd" dot dot dot) "\""
804            root-1 ::= [0-9]
805            space ::= | " " | "\n"{1,2} [ \t]{0,20}
806        )"""
807    });
808
809    test({
810        SUCCESS,
811        "required props in original order",
812        R"""({
813            "type": "object",
814            "properties": {
815                "b": {"type": "string"},
816                "c": {"type": "string"},
817                "a": {"type": "string"}
818            },
819            "required": [
820                "a",
821                "b",
822                "c"
823            ],
824            "additionalProperties": false,
825            "definitions": {}
826        })""",
827        R"""(
828            a-kv ::= "\"a\"" space ":" space string
829            b-kv ::= "\"b\"" space ":" space string
830            c-kv ::= "\"c\"" space ":" space string
831            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
832            root ::= "{" space b-kv "," space c-kv "," space a-kv space "}"
833            space ::= | " " | "\n"{1,2} [ \t]{0,20}
834            string ::= "\"" char* "\""
835        )"""
836    });
837
838    test({
839        SUCCESS,
840        "1 optional prop",
841        R"""({
842            "properties": {
843                "a": {
844                "type": "string"
845                }
846            },
847            "additionalProperties": false
848        })""",
849        R"""(
850            a-kv ::= "\"a\"" space ":" space string
851            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
852            root ::= "{" space  (a-kv )? space "}"
853            space ::= | " " | "\n"{1,2} [ \t]{0,20}
854            string ::= "\"" char* "\""
855        )"""
856    });
857
858    test({
859        SUCCESS,
860        "N optional props",
861        R"""({
862            "properties": {
863                "a": {"type": "string"},
864                "b": {"type": "string"},
865                "c": {"type": "string"}
866            },
867            "additionalProperties": false
868        })""",
869        R"""(
870            a-kv ::= "\"a\"" space ":" space string
871            a-rest ::= ( "," space b-kv )? b-rest
872            b-kv ::= "\"b\"" space ":" space string
873            b-rest ::= ( "," space c-kv )?
874            c-kv ::= "\"c\"" space ":" space string
875            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
876            root ::= "{" space  (a-kv a-rest | b-kv b-rest | c-kv )? space "}"
877            space ::= | " " | "\n"{1,2} [ \t]{0,20}
878            string ::= "\"" char* "\""
879        )"""
880    });
881
882    test({
883        SUCCESS,
884        "required + optional props each in original order",
885        R"""({
886            "properties": {
887                "b": {"type": "string"},
888                "a": {"type": "string"},
889                "d": {"type": "string"},
890                "c": {"type": "string"}
891            },
892            "required": ["a", "b"],
893            "additionalProperties": false
894        })""",
895        R"""(
896            a-kv ::= "\"a\"" space ":" space string
897            b-kv ::= "\"b\"" space ":" space string
898            c-kv ::= "\"c\"" space ":" space string
899            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
900            d-kv ::= "\"d\"" space ":" space string
901            d-rest ::= ( "," space c-kv )?
902            root ::= "{" space b-kv "," space a-kv ( "," space ( d-kv d-rest | c-kv ) )? space "}"
903            space ::= | " " | "\n"{1,2} [ \t]{0,20}
904            string ::= "\"" char* "\""
905        )"""
906    });
907
908    test({
909        SUCCESS,
910        "additional props",
911        R"""({
912            "type": "object",
913            "additionalProperties": {"type": "array", "items": {"type": "number"}}
914        })""",
915        R"""(
916            additional-kv ::= string ":" space additional-value
917            additional-value ::= "[" space (number ("," space number)*)? space "]"
918            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
919            decimal-part ::= [0-9]{1,16}
920            integral-part ::= [0] | [1-9] [0-9]{0,15}
921            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
922            root ::= "{" space  (additional-kv ( "," space additional-kv )* )? space "}"
923            space ::= | " " | "\n"{1,2} [ \t]{0,20}
924            string ::= "\"" char* "\""
925        )"""
926    });
927
928    test({
929        SUCCESS,
930        "additional props (true)",
931        R"""({
932            "type": "object",
933            "additionalProperties": true
934        })""",
935        R"""(
936            array ::= "[" space ( value ("," space value)* )? space "]"
937            boolean ::= ("true" | "false")
938            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
939            decimal-part ::= [0-9]{1,16}
940            integral-part ::= [0] | [1-9] [0-9]{0,15}
941            null ::= "null"
942            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
943            object ::= "{" space ( string ":" space value ("," space string ":" space value)* )? space "}"
944            root ::= object
945            space ::= | " " | "\n"{1,2} [ \t]{0,20}
946            string ::= "\"" char* "\""
947            value ::= object | array | string | number | boolean | null
948        )"""
949    });
950
951    test({
952        SUCCESS,
953        "additional props (implicit)",
954        R"""({
955            "type": "object"
956        })""",
957        R"""(
958            array ::= "[" space ( value ("," space value)* )? space "]"
959            boolean ::= ("true" | "false")
960            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
961            decimal-part ::= [0-9]{1,16}
962            integral-part ::= [0] | [1-9] [0-9]{0,15}
963            null ::= "null"
964            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
965            object ::= "{" space ( string ":" space value ("," space string ":" space value)* )? space "}"
966            root ::= object
967            space ::= | " " | "\n"{1,2} [ \t]{0,20}
968            string ::= "\"" char* "\""
969            value ::= object | array | string | number | boolean | null
970        )"""
971    });
972
973    test({
974        SUCCESS,
975        "empty w/o additional props",
976        R"""({
977            "type": "object",
978            "additionalProperties": false
979        })""",
980        R"""(
981            root ::= "{" space "}"
982            space ::= | " " | "\n"{1,2} [ \t]{0,20}
983        )"""
984    });
985
986    test({
987        SUCCESS,
988        "required + additional props",
989        R"""({
990            "type": "object",
991            "properties": {
992                "a": {"type": "number"}
993            },
994            "required": ["a"],
995            "additionalProperties": {"type": "string"}
996        })""",
997        R"""(
998            a-kv ::= "\"a\"" space ":" space number
999            additional-k ::= ["] ( [a] char+ | [^"a] char* )? ["]
1000            additional-kv ::= additional-k ":" space string
1001            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1002            decimal-part ::= [0-9]{1,16}
1003            integral-part ::= [0] | [1-9] [0-9]{0,15}
1004            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
1005            root ::= "{" space a-kv ( "," space ( additional-kv ( "," space additional-kv )* ) )? space "}"
1006            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1007            string ::= "\"" char* "\""
1008        )"""
1009    });
1010
1011    test({
1012        SUCCESS,
1013        "optional + additional props",
1014        R"""({
1015            "type": "object",
1016            "properties": {
1017                "a": {"type": "number"}
1018            },
1019            "additionalProperties": {"type": "number"}
1020        })""",
1021        R"""(
1022            a-kv ::= "\"a\"" space ":" space number
1023            a-rest ::= ( "," space additional-kv )*
1024            additional-k ::= ["] ( [a] char+ | [^"a] char* )? ["]
1025            additional-kv ::= additional-k ":" space number
1026            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1027            decimal-part ::= [0-9]{1,16}
1028            integral-part ::= [0] | [1-9] [0-9]{0,15}
1029            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
1030            root ::= "{" space  (a-kv a-rest | additional-kv ( "," space additional-kv )* )? space "}"
1031            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1032        )"""
1033    });
1034
1035    test({
1036        SUCCESS,
1037        "required + optional + additional props",
1038        R"""({
1039            "type": "object",
1040            "properties": {
1041                "and": {"type": "number"},
1042                "also": {"type": "number"}
1043            },
1044            "required": ["and"],
1045            "additionalProperties": {"type": "number"}
1046        })""",
1047        R"""(
1048            additional-k ::= ["] ( [a] ([l] ([s] ([o] char+ | [^"o] char*) | [^"s] char*) | [n] ([d] char+ | [^"d] char*) | [^"ln] char*) | [^"a] char* )? ["]
1049            additional-kv ::= additional-k ":" space number
1050            also-kv ::= "\"also\"" space ":" space number
1051            also-rest ::= ( "," space additional-kv )*
1052            and-kv ::= "\"and\"" space ":" space number
1053            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1054            decimal-part ::= [0-9]{1,16}
1055            integral-part ::= [0] | [1-9] [0-9]{0,15}
1056            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
1057            root ::= "{" space and-kv ( "," space ( also-kv also-rest | additional-kv ( "," space additional-kv )* ) )? space "}"
1058            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1059        )"""
1060    });
1061
1062    test({
1063        SUCCESS,
1064        "optional props with empty name",
1065        R"""({
1066            "properties": {
1067                "": {"type": "integer"},
1068                "a": {"type": "integer"}
1069            },
1070            "additionalProperties": {"type": "integer"}
1071        })""",
1072        R"""(
1073            -kv ::= "\"\"" space ":" space root
1074            -rest ::= ( "," space a-kv )? a-rest
1075            a-kv ::= "\"a\"" space ":" space integer
1076            a-rest ::= ( "," space additional-kv )*
1077            additional-k ::= ["] ( [a] char+ | [^"a] char* ) ["]
1078            additional-kv ::= additional-k ":" space integer
1079            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1080            integer ::= ("-"? integral-part)
1081            integral-part ::= [0] | [1-9] [0-9]{0,15}
1082            root ::= ("-"? integral-part)
1083            root0 ::= "{" space  (-kv -rest | a-kv a-rest | additional-kv ( "," space additional-kv )* )? space "}"
1084            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1085        )"""
1086    });
1087
1088    test({
1089        SUCCESS,
1090        "optional props with nested names",
1091        R"""({
1092            "properties": {
1093                "a": {"type": "integer"},
1094                "aa": {"type": "integer"}
1095            },
1096            "additionalProperties": {"type": "integer"}
1097        })""",
1098        R"""(
1099            a-kv ::= "\"a\"" space ":" space integer
1100            a-rest ::= ( "," space aa-kv )? aa-rest
1101            aa-kv ::= "\"aa\"" space ":" space integer
1102            aa-rest ::= ( "," space additional-kv )*
1103            additional-k ::= ["] ( [a] ([a] char+ | [^"a] char*) | [^"a] char* )? ["]
1104            additional-kv ::= additional-k ":" space integer
1105            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1106            integer ::= ("-"? integral-part)
1107            integral-part ::= [0] | [1-9] [0-9]{0,15}
1108            root ::= "{" space  (a-kv a-rest | aa-kv aa-rest | additional-kv ( "," space additional-kv )* )? space "}"
1109            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1110        )"""
1111    });
1112
1113    test({
1114        SUCCESS,
1115        "optional props with common prefix",
1116        R"""({
1117            "properties": {
1118                "ab": {"type": "integer"},
1119                "ac": {"type": "integer"}
1120            },
1121            "additionalProperties": {"type": "integer"}
1122        })""",
1123        R"""(
1124            ab-kv ::= "\"ab\"" space ":" space integer
1125            ab-rest ::= ( "," space ac-kv )? ac-rest
1126            ac-kv ::= "\"ac\"" space ":" space integer
1127            ac-rest ::= ( "," space additional-kv )*
1128            additional-k ::= ["] ( [a] ([b] char+ | [c] char+ | [^"bc] char*) | [^"a] char* )? ["]
1129            additional-kv ::= additional-k ":" space integer
1130            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1131            integer ::= ("-"? integral-part)
1132            integral-part ::= [0] | [1-9] [0-9]{0,15}
1133            root ::= "{" space  (ab-kv ab-rest | ac-kv ac-rest | additional-kv ( "," space additional-kv )* )? space "}"
1134            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1135        )"""
1136    });
1137
1138    test({
1139        SUCCESS,
1140        "top-level $ref",
1141        R"""({
1142            "$ref": "#/definitions/foo",
1143            "definitions": {
1144                "foo": {
1145                    "type": "object",
1146                    "properties": {
1147                        "a": {
1148                            "type": "string"
1149                        }
1150                    },
1151                    "required": [
1152                        "a"
1153                    ],
1154                    "additionalProperties": false
1155                }
1156            }
1157        })""",
1158        R"""(
1159            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1160            ref-definitions-foo ::= "{" space ref-definitions-foo-a-kv space "}"
1161            ref-definitions-foo-a-kv ::= "\"a\"" space ":" space string
1162            root ::= ref-definitions-foo
1163            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1164            string ::= "\"" char* "\""
1165        )"""
1166    });
1167
1168    test({
1169        SUCCESS,
1170        "anyOf",
1171        R"""({
1172            "anyOf": [
1173                {"$ref": "#/definitions/foo"},
1174                {"$ref": "#/definitions/bar"}
1175            ],
1176            "definitions": {
1177                "foo": {
1178                    "properties": {"a": {"type": "number"}}
1179                },
1180                "bar": {
1181                    "properties": {"b": {"type": "number"}}
1182                }
1183            },
1184            "type": "object"
1185        })""",
1186        R"""(
1187            alternative-0 ::= ref-definitions-foo
1188            alternative-1 ::= ref-definitions-bar
1189            decimal-part ::= [0-9]{1,16}
1190            integral-part ::= [0] | [1-9] [0-9]{0,15}
1191            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
1192            ref-definitions-bar ::= "{" space  (ref-definitions-bar-b-kv )? space "}"
1193            ref-definitions-bar-b-kv ::= "\"b\"" space ":" space number
1194            ref-definitions-foo ::= "{" space  (ref-definitions-foo-a-kv )? space "}"
1195            ref-definitions-foo-a-kv ::= "\"a\"" space ":" space number
1196            root ::= alternative-0 | alternative-1
1197            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1198        )"""
1199    });
1200
1201    test({
1202        SUCCESS,
1203        "anyOf $ref",
1204        R"""({
1205            "properties": {
1206                "a": {
1207                    "anyOf": [
1208                        {"type": "string"},
1209                        {"type": "number"}
1210                    ]
1211                },
1212                "b": {
1213                    "anyOf": [
1214                        {"$ref": "#/properties/a/anyOf/0"},
1215                        {"type": "boolean"}
1216                    ]
1217                }
1218            },
1219            "type": "object"
1220        })""",
1221        R"""(
1222            a ::= string | number
1223            a-kv ::= "\"a\"" space ":" space a
1224            a-rest ::= ( "," space b-kv )?
1225            b ::= b-0 | boolean
1226            b-0 ::= string
1227            b-kv ::= "\"b\"" space ":" space b
1228            boolean ::= ("true" | "false")
1229            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1230            decimal-part ::= [0-9]{1,16}
1231            integral-part ::= [0] | [1-9] [0-9]{0,15}
1232            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
1233            root ::= "{" space  (a-kv a-rest | b-kv )? space "}"
1234            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1235            string ::= "\"" char* "\""
1236        )"""
1237    });
1238
1239    test({
1240        SUCCESS,
1241        "mix of allOf, anyOf and $ref (similar to https://json.schemastore.org/tsconfig.json)",
1242        R"""({
1243            "allOf": [
1244                {"$ref": "#/definitions/foo"},
1245                {"$ref": "#/definitions/bar"},
1246                {
1247                "anyOf": [
1248                    {"$ref": "#/definitions/baz"},
1249                    {"$ref": "#/definitions/bam"}
1250                ]
1251                }
1252            ],
1253            "definitions": {
1254                "foo": {
1255                    "properties": {"a": {"type": "number"}}
1256                },
1257                "bar": {
1258                    "properties": {"b": {"type": "number"}}
1259                },
1260                "bam": {
1261                    "properties": {"c": {"type": "number"}}
1262                },
1263                "baz": {
1264                    "properties": {"d": {"type": "number"}}
1265                }
1266            },
1267            "type": "object"
1268        })""",
1269        R"""(
1270            a-kv ::= "\"a\"" space ":" space number
1271            b-kv ::= "\"b\"" space ":" space number
1272            c-kv ::= "\"c\"" space ":" space number
1273            d-kv ::= "\"d\"" space ":" space number
1274            d-rest ::= ( "," space c-kv )?
1275            decimal-part ::= [0-9]{1,16}
1276            integral-part ::= [0] | [1-9] [0-9]{0,15}
1277            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
1278            root ::= "{" space a-kv "," space b-kv ( "," space ( d-kv d-rest | c-kv ) )? space "}"
1279            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1280        )"""
1281    });
1282
1283    test({
1284        SUCCESS,
1285        "allOf with enum schema",
1286        R"""({
1287            "allOf": [
1288                {"$ref": "#/definitions/foo"}
1289            ],
1290            "definitions": {
1291                "foo": {
1292                    "type": "string",
1293                    "enum": ["a", "b"]
1294                }
1295            }
1296        })""",
1297        R"""(
1298            root ::= ("\"a\"" | "\"b\"")
1299            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1300        )"""
1301    });
1302
1303    test({
1304        SUCCESS,
1305        "allOf with multiple enum schemas",
1306        R"""({
1307            "allOf": [
1308                {"$ref": "#/definitions/foo"},
1309                {"$ref": "#/definitions/bar"}
1310            ],
1311            "definitions": {
1312                "foo": {
1313                    "type": "string",
1314                    "enum": ["a", "b", "c"]
1315                },
1316                "bar": {
1317                    "type": "string",
1318                    "enum": ["b", "c", "d"]
1319                }
1320            }
1321        })""",
1322        R"""(
1323            root ::= ("\"b\"" | "\"c\"")
1324            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1325        )"""
1326    });
1327
1328    test({
1329        SUCCESS,
1330        "conflicting names",
1331        R"""({
1332            "type": "object",
1333            "properties": {
1334                "number": {
1335                "type": "object",
1336                "properties": {
1337                    "number": {
1338                    "type": "object",
1339                        "properties": {
1340                            "root": {
1341                                "type": "number"
1342                            }
1343                        },
1344                        "required": [
1345                            "root"
1346                        ],
1347                        "additionalProperties": false
1348                    }
1349                },
1350                "required": [
1351                    "number"
1352                ],
1353                "additionalProperties": false
1354                }
1355            },
1356            "required": [
1357                "number"
1358            ],
1359            "additionalProperties": false,
1360            "definitions": {}
1361        })""",
1362        R"""(
1363            decimal-part ::= [0-9]{1,16}
1364            integral-part ::= [0] | [1-9] [0-9]{0,15}
1365            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
1366            number- ::= "{" space number-number-kv space "}"
1367            number-kv ::= "\"number\"" space ":" space number-
1368            number-number ::= "{" space number-number-root-kv space "}"
1369            number-number-kv ::= "\"number\"" space ":" space number-number
1370            number-number-root-kv ::= "\"root\"" space ":" space number
1371            root ::= "{" space number-kv space "}"
1372            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1373        )"""
1374    });
1375
1376    test({
1377        SUCCESS,
1378        "description only (no type) treated as unconstrained",
1379        R"""({"description": "The 0-based index of the last line to be retrieved (inclusive). If None, read until the end of the file."})""",
1380        R"""(
1381            array ::= "[" space ( value ("," space value)* )? space "]"
1382            boolean ::= ("true" | "false")
1383            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1384            decimal-part ::= [0-9]{1,16}
1385            integral-part ::= [0] | [1-9] [0-9]{0,15}
1386            null ::= "null"
1387            number ::= ("-"? integral-part) ("." decimal-part)? ([eE] [-+]? integral-part)?
1388            object ::= "{" space ( string ":" space value ("," space string ":" space value)* )? space "}"
1389            root ::= value
1390            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1391            string ::= "\"" char* "\""
1392            value ::= object | array | string | number | boolean | null
1393        )"""
1394    });
1395
1396    test({
1397        SUCCESS,
1398        "literal string with escapes",
1399        R"""({
1400            "properties": {
1401                "code": {
1402                    "const": " \r \n \" \\ ",
1403                    "description": "Generated code",
1404                    "title": "Code",
1405                    "type": "string"
1406                }
1407            },
1408            "required": [
1409                "code"
1410            ],
1411            "title": "DecoderResponse",
1412            "type": "object"
1413        })""",
1414        R"""(
1415            code ::= "\" \\r \\n \\\" \\\\ \""
1416            code-kv ::= "\"code\"" space ":" space code
1417            root ::= "{" space code-kv space "}"
1418            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1419        )"""
1420    });
1421
1422    test({
1423        SUCCESS,
1424        "regexp with non-capturing group",
1425        R"""({
1426            "type": "string",
1427            "pattern": "^(?:foo|bar)baz$"
1428        })""",
1429        R"""(
1430            root ::= "\"" (("foo" | "bar") "baz") "\""
1431            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1432        )"""
1433    });
1434
1435    test({
1436        SUCCESS,
1437        "regexp with nested non-capturing groups",
1438        R"""({
1439            "type": "string",
1440            "pattern": "^(?:(?:ab)+c)?d$"
1441        })""",
1442        R"""(
1443            root ::= "\"" ((("ab")+ "c")? "d") "\""
1444            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1445        )"""
1446    });
1447
1448    test({
1449        SUCCESS,
1450        "unanchored regexp",
1451        R"""({
1452            "type": "string",
1453            "pattern": "[0-9]+"
1454        })""",
1455        R"""(
1456            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1457            root ::= string
1458            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1459            string ::= "\"" char* "\""
1460        )"""
1461    });
1462
1463    // the rules of the partial conversion (here "root-0") must not leak into the grammar
1464    test({
1465        SUCCESS,
1466        "regexp with unsupported shorthand",
1467        R"""({
1468            "type": "string",
1469            "pattern": "^[0-9]{3}\\w$"
1470        })""",
1471        R"""(
1472            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1473            root ::= string
1474            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1475            string ::= "\"" char* "\""
1476        )"""
1477    });
1478
1479    // a regexp that is invalid under any flavor is still an error
1480    test({
1481        FAILURE,
1482        "regexp with unbalanced parentheses",
1483        R"""({
1484            "type": "string",
1485            "pattern": "^(a$"
1486        })""",
1487        ""
1488    });
1489
1490    // only the property with the bad pattern degrades
1491    test({
1492        SUCCESS,
1493        "unsupported regexp in a property",
1494        R"""({
1495            "type": "object",
1496            "properties": {
1497                "a": { "type": "string", "pattern": "^[a-z\\-]+$" }
1498            },
1499            "required": ["a"],
1500            "additionalProperties": false
1501        })""",
1502        R"""(
1503            a ::= string
1504            a-kv ::= "\"a\"" space ":" space a
1505            char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1506            root ::= "{" space a-kv space "}"
1507            space ::= | " " | "\n"{1,2} [ \t]{0,20}
1508            string ::= "\"" char* "\""
1509        )"""
1510    });
1511}
1512
1513int main() {
1514    test_all("JSON schema conversion", [](const TestCase & tc) {
1515        try {
1516            tc.verify(json_schema_to_grammar(common_json::parse(tc.schema), true));
1517            tc.verify_status(SUCCESS);
1518        } catch (const std::invalid_argument & ex) {
1519            fprintf(stderr, "Error: %s\n", ex.what());
1520            tc.verify_status(FAILURE);
1521        }
1522    });
1523
1524    // a document parsed up front gives the same grammar as the JSON, recursion included
1525    {
1526        fprintf(stderr, "- parsed document\n");
1527        auto schema = common_json::parse(R"""({
1528            "$ref": "#/$defs/node",
1529            "$defs": {
1530                "node": {
1531                    "type": "object",
1532                    "properties": {"next": {"$ref": "#/$defs/node"}, "leaf": {}},
1533                    "additionalProperties": false
1534                }
1535            }
1536        })""");
1537        assert(json_schema_to_grammar(common_chat_schema_from_json(schema)) == json_schema_to_grammar(schema, true));
1538    }
1539
1540    // a property node carries its $ref target, so its grammar names the ref rule
1541    {
1542        fprintf(stderr, "- sub-schema $ref\n");
1543        auto parameters = common_json::parse(R"""({
1544            "type": "object",
1545            "properties": {"item": {"$ref": "#/$defs/item"}},
1546            "$defs": {
1547                "item": {
1548                    "type": "object",
1549                    "properties": {"a": {"type": "string"}},
1550                    "required": ["a"],
1551                    "additionalProperties": false
1552                }
1553            }
1554        })""");
1555        TestCase tc {
1556            SUCCESS,
1557            "sub-schema $ref",
1558            "",
1559            R"""(
1560                char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
1561                ref-defs-item ::= "{" space ref-defs-item-a-kv space "}"
1562                ref-defs-item-a-kv ::= "\"a\"" space ":" space string
1563                root ::= ref-defs-item
1564                space ::= | " " | "\n"{1,2} [ \t]{0,20}
1565                string ::= "\"" char* "\""
1566            )""",
1567        };
1568        auto doc = common_chat_schema_from_json(parameters);
1569        tc.verify(build_grammar([&](const common_grammar_builder & builder) {
1570            const auto & item = static_cast<const common_chat_schema_object &>(*doc.root).properties.at(0);
1571            builder.add_schema("root", *item.schema);
1572        }));
1573    }
1574
1575    test_all("Check the expectations parse", [](const TestCase & tc) {
1576        if (tc.expected_status == SUCCESS) {
1577            tc.verify_expectation_parseable();
1578        }
1579    });
1580}