datapath: Fix default value of skb transport_header.
[sliver-openvswitch.git] / lib / json.c
1 /*
2  * Copyright (c) 2009, 2010 Nicira Networks.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 #include <config.h>
18
19 #include "json.h"
20
21 #include <assert.h>
22 #include <ctype.h>
23 #include <errno.h>
24 #include <float.h>
25 #include <limits.h>
26 #include <math.h>
27 #include <string.h>
28
29 #include "dynamic-string.h"
30 #include "hash.h"
31 #include "shash.h"
32 #include "unicode.h"
33 #include "util.h"
34
35 /* The type of a JSON token. */
36 enum json_token_type {
37     T_EOF = 0,
38     T_BEGIN_ARRAY = '[',
39     T_END_ARRAY = ']',
40     T_BEGIN_OBJECT = '{',
41     T_END_OBJECT = '}',
42     T_NAME_SEPARATOR = ':',
43     T_VALUE_SEPARATOR = ',',
44     T_FALSE = UCHAR_MAX + 1,
45     T_NULL,
46     T_TRUE,
47     T_INTEGER,
48     T_REAL,
49     T_STRING
50 };
51
52 /* A JSON token.
53  *
54  * RFC 4627 doesn't define a lexical structure for JSON but I believe this to
55  * be compliant with the standard.
56  */
57 struct json_token {
58     enum json_token_type type;
59     union {
60         double real;
61         long long int integer;
62         const char *string;
63     } u;
64 };
65
66 enum json_lex_state {
67     JSON_LEX_START,             /* Not inside a token. */
68     JSON_LEX_NUMBER,            /* Reading a number. */
69     JSON_LEX_KEYWORD,           /* Reading a keyword. */
70     JSON_LEX_STRING,            /* Reading a quoted string. */
71     JSON_LEX_ESCAPE             /* In a quoted string just after a "\". */
72 };
73
74 enum json_parse_state {
75     JSON_PARSE_START,           /* Beginning of input. */
76     JSON_PARSE_END,             /* End of input. */
77
78     /* Objects. */
79     JSON_PARSE_OBJECT_INIT,     /* Expecting '}' or an object name. */
80     JSON_PARSE_OBJECT_NAME,     /* Expecting an object name. */
81     JSON_PARSE_OBJECT_COLON,    /* Expecting ':'. */
82     JSON_PARSE_OBJECT_VALUE,    /* Expecting an object value. */
83     JSON_PARSE_OBJECT_NEXT,     /* Expecting ',' or '}'. */
84
85     /* Arrays. */
86     JSON_PARSE_ARRAY_INIT,      /* Expecting ']' or a value. */
87     JSON_PARSE_ARRAY_VALUE,     /* Expecting a value. */
88     JSON_PARSE_ARRAY_NEXT       /* Expecting ',' or ']'. */
89 };
90
91 struct json_parser_node {
92     struct json *json;
93 };
94
95 /* A JSON parser. */
96 struct json_parser {
97     int flags;
98
99     /* Lexical analysis. */
100     enum json_lex_state lex_state;
101     struct ds buffer;           /* Buffer for accumulating token text. */
102     int line_number;
103     int column_number;
104     int byte_number;
105
106     /* Parsing. */
107     enum json_parse_state parse_state;
108 #define JSON_MAX_HEIGHT 1000
109     struct json_parser_node *stack;
110     size_t height, allocated_height;
111     char *member_name;
112
113     /* Parse status. */
114     bool done;
115     char *error;                /* Error message, if any, null if none yet. */
116 };
117
118 static struct json *json_create(enum json_type type);
119 static void json_parser_input(struct json_parser *, struct json_token *);
120
121 static void json_error(struct json_parser *p, const char *format, ...)
122     PRINTF_FORMAT(2, 3);
123 \f
124 const char *
125 json_type_to_string(enum json_type type)
126 {
127     switch (type) {
128     case JSON_NULL:
129         return "null";
130
131     case JSON_FALSE:
132         return "false";
133
134     case JSON_TRUE:
135         return "true";
136
137     case JSON_OBJECT:
138         return "object";
139
140     case JSON_ARRAY:
141         return "array";
142
143     case JSON_INTEGER:
144     case JSON_REAL:
145         return "number";
146
147     case JSON_STRING:
148         return "string";
149
150     case JSON_N_TYPES:
151     default:
152         return "<invalid>";
153     }
154 }
155 \f
156 /* Functions for manipulating struct json. */
157
158 struct json *
159 json_null_create(void)
160 {
161     return json_create(JSON_NULL);
162 }
163
164 struct json *
165 json_boolean_create(bool b)
166 {
167     return json_create(b ? JSON_TRUE : JSON_FALSE);
168 }
169
170 struct json *
171 json_string_create_nocopy(char *s)
172 {
173     struct json *json = json_create(JSON_STRING);
174     json->u.string = s;
175     return json;
176 }
177
178 struct json *
179 json_string_create(const char *s)
180 {
181     return json_string_create_nocopy(xstrdup(s));
182 }
183
184 struct json *
185 json_array_create_empty(void)
186 {
187     struct json *json = json_create(JSON_ARRAY);
188     json->u.array.elems = NULL;
189     json->u.array.n = 0;
190     json->u.array.n_allocated = 0;
191     return json;
192 }
193
194 void
195 json_array_add(struct json *array_, struct json *element)
196 {
197     struct json_array *array = json_array(array_);
198     if (array->n >= array->n_allocated) {
199         array->elems = x2nrealloc(array->elems, &array->n_allocated,
200                                   sizeof *array->elems);
201     }
202     array->elems[array->n++] = element;
203 }
204
205 void
206 json_array_trim(struct json *array_)
207 {
208     struct json_array *array = json_array(array_);
209     if (array->n < array->n_allocated){
210         array->n_allocated = array->n;
211         array->elems = xrealloc(array->elems, array->n * sizeof *array->elems);
212     }
213 }
214
215 struct json *
216 json_array_create(struct json **elements, size_t n)
217 {
218     struct json *json = json_create(JSON_ARRAY);
219     json->u.array.elems = elements;
220     json->u.array.n = n;
221     json->u.array.n_allocated = n;
222     return json;
223 }
224
225 struct json *
226 json_array_create_1(struct json *elem0)
227 {
228     struct json **elems = xmalloc(sizeof *elems);
229     elems[0] = elem0;
230     return json_array_create(elems, 1);
231 }
232
233 struct json *
234 json_array_create_2(struct json *elem0, struct json *elem1)
235 {
236     struct json **elems = xmalloc(2 * sizeof *elems);
237     elems[0] = elem0;
238     elems[1] = elem1;
239     return json_array_create(elems, 2);
240 }
241
242 struct json *
243 json_array_create_3(struct json *elem0, struct json *elem1, struct json *elem2)
244 {
245     struct json **elems = xmalloc(3 * sizeof *elems);
246     elems[0] = elem0;
247     elems[1] = elem1;
248     elems[2] = elem2;
249     return json_array_create(elems, 3);
250 }
251
252 struct json *
253 json_object_create(void)
254 {
255     struct json *json = json_create(JSON_OBJECT);
256     json->u.object = xmalloc(sizeof *json->u.object);
257     shash_init(json->u.object);
258     return json;
259 }
260
261 struct json *
262 json_integer_create(long long int integer)
263 {
264     struct json *json = json_create(JSON_INTEGER);
265     json->u.integer = integer;
266     return json;
267 }
268
269 struct json *
270 json_real_create(double real)
271 {
272     struct json *json = json_create(JSON_REAL);
273     json->u.real = real;
274     return json;
275 }
276
277 void
278 json_object_put(struct json *json, const char *name, struct json *value)
279 {
280     json_destroy(shash_replace(json->u.object, name, value));
281 }
282
283 void
284 json_object_put_string(struct json *json, const char *name, const char *value)
285 {
286     json_object_put(json, name, json_string_create(value));
287 }
288
289 const char *
290 json_string(const struct json *json)
291 {
292     assert(json->type == JSON_STRING);
293     return json->u.string;
294 }
295
296 struct json_array *
297 json_array(const struct json *json)
298 {
299     assert(json->type == JSON_ARRAY);
300     return (struct json_array *) &json->u.array;
301 }
302
303 struct shash *
304 json_object(const struct json *json)
305 {
306     assert(json->type == JSON_OBJECT);
307     return (struct shash *) json->u.object;
308 }
309
310 bool
311 json_boolean(const struct json *json)
312 {
313     assert(json->type == JSON_TRUE || json->type == JSON_FALSE);
314     return json->type == JSON_TRUE;
315 }
316
317 double
318 json_real(const struct json *json)
319 {
320     assert(json->type == JSON_REAL || json->type == JSON_INTEGER);
321     return json->type == JSON_REAL ? json->u.real : json->u.integer;
322 }
323
324 int64_t
325 json_integer(const struct json *json)
326 {
327     assert(json->type == JSON_INTEGER);
328     return json->u.integer;
329 }
330 \f
331 static void json_destroy_object(struct shash *object);
332 static void json_destroy_array(struct json_array *array);
333
334 /* Frees 'json' and everything it points to, recursively. */
335 void
336 json_destroy(struct json *json)
337 {
338     if (json) {
339         switch (json->type) {
340         case JSON_OBJECT:
341             json_destroy_object(json->u.object);
342             break;
343
344         case JSON_ARRAY:
345             json_destroy_array(&json->u.array);
346             break;
347
348         case JSON_STRING:
349             free(json->u.string);
350             break;
351
352         case JSON_NULL:
353         case JSON_FALSE:
354         case JSON_TRUE:
355         case JSON_INTEGER:
356         case JSON_REAL:
357             break;
358
359         case JSON_N_TYPES:
360             NOT_REACHED();
361         }
362         free(json);
363     }
364 }
365
366 static void
367 json_destroy_object(struct shash *object)
368 {
369     struct shash_node *node, *next;
370
371     SHASH_FOR_EACH_SAFE (node, next, object) {
372         struct json *value = node->data;
373
374         json_destroy(value);
375         shash_delete(object, node);
376     }
377     shash_destroy(object);
378     free(object);
379 }
380
381 static void
382 json_destroy_array(struct json_array *array)
383 {
384     size_t i;
385
386     for (i = 0; i < array->n; i++) {
387         json_destroy(array->elems[i]);
388     }
389     free(array->elems);
390 }
391 \f
392 static struct json *json_clone_object(const struct shash *object);
393 static struct json *json_clone_array(const struct json_array *array);
394
395 /* Returns a deep copy of 'json'. */
396 struct json *
397 json_clone(const struct json *json)
398 {
399     switch (json->type) {
400     case JSON_OBJECT:
401         return json_clone_object(json->u.object);
402
403     case JSON_ARRAY:
404         return json_clone_array(&json->u.array);
405
406     case JSON_STRING:
407         return json_string_create(json->u.string);
408
409     case JSON_NULL:
410     case JSON_FALSE:
411     case JSON_TRUE:
412         return json_create(json->type);
413
414     case JSON_INTEGER:
415         return json_integer_create(json->u.integer);
416
417     case JSON_REAL:
418         return json_real_create(json->u.real);
419
420     case JSON_N_TYPES:
421     default:
422         NOT_REACHED();
423     }
424 }
425
426 static struct json *
427 json_clone_object(const struct shash *object)
428 {
429     struct shash_node *node;
430     struct json *json;
431
432     json = json_object_create();
433     SHASH_FOR_EACH (node, object) {
434         struct json *value = node->data;
435         json_object_put(json, node->name, json_clone(value));
436     }
437     return json;
438 }
439
440 static struct json *
441 json_clone_array(const struct json_array *array)
442 {
443     struct json **elems;
444     size_t i;
445
446     elems = xmalloc(array->n * sizeof *elems);
447     for (i = 0; i < array->n; i++) {
448         elems[i] = json_clone(array->elems[i]);
449     }
450     return json_array_create(elems, array->n);
451 }
452 \f
453 static size_t
454 json_hash_object(const struct shash *object, size_t basis)
455 {
456     const struct shash_node **nodes;
457     size_t n, i;
458
459     nodes = shash_sort(object);
460     n = shash_count(object);
461     for (i = 0; i < n; i++) {
462         const struct shash_node *node = nodes[i];
463         basis = hash_string(node->name, basis);
464         basis = json_hash(node->data, basis);
465     }
466     return basis;
467 }
468
469 static size_t
470 json_hash_array(const struct json_array *array, size_t basis)
471 {
472     size_t i;
473
474     basis = hash_int(array->n, basis);
475     for (i = 0; i < array->n; i++) {
476         basis = json_hash(array->elems[i], basis);
477     }
478     return basis;
479 }
480
481 size_t
482 json_hash(const struct json *json, size_t basis)
483 {
484     switch (json->type) {
485     case JSON_OBJECT:
486         return json_hash_object(json->u.object, basis);
487
488     case JSON_ARRAY:
489         return json_hash_array(&json->u.array, basis);
490
491     case JSON_STRING:
492         return hash_string(json->u.string, basis);
493
494     case JSON_NULL:
495     case JSON_FALSE:
496     case JSON_TRUE:
497         return hash_int(json->type << 8, basis);
498
499     case JSON_INTEGER:
500         return hash_int(json->u.integer, basis);
501
502     case JSON_REAL:
503         return hash_double(json->u.real, basis);
504
505     case JSON_N_TYPES:
506     default:
507         NOT_REACHED();
508     }
509 }
510
511 static bool
512 json_equal_object(const struct shash *a, const struct shash *b)
513 {
514     struct shash_node *a_node;
515
516     if (shash_count(a) != shash_count(b)) {
517         return false;
518     }
519
520     SHASH_FOR_EACH (a_node, a) {
521         struct shash_node *b_node = shash_find(b, a_node->name);
522         if (!b_node || !json_equal(a_node->data, b_node->data)) {
523             return false;
524         }
525     }
526
527     return true;
528 }
529
530 static bool
531 json_equal_array(const struct json_array *a, const struct json_array *b)
532 {
533     size_t i;
534
535     if (a->n != b->n) {
536         return false;
537     }
538
539     for (i = 0; i < a->n; i++) {
540         if (!json_equal(a->elems[i], b->elems[i])) {
541             return false;
542         }
543     }
544
545     return true;
546 }
547
548 bool
549 json_equal(const struct json *a, const struct json *b)
550 {
551     if (a->type != b->type) {
552         return false;
553     }
554
555     switch (a->type) {
556     case JSON_OBJECT:
557         return json_equal_object(a->u.object, b->u.object);
558
559     case JSON_ARRAY:
560         return json_equal_array(&a->u.array, &b->u.array);
561
562     case JSON_STRING:
563         return !strcmp(a->u.string, b->u.string);
564
565     case JSON_NULL:
566     case JSON_FALSE:
567     case JSON_TRUE:
568         return true;
569
570     case JSON_INTEGER:
571         return a->u.integer == b->u.integer;
572
573     case JSON_REAL:
574         return a->u.real == b->u.real;
575
576     case JSON_N_TYPES:
577     default:
578         NOT_REACHED();
579     }
580 }
581 \f
582 /* Lexical analysis. */
583
584 static void
585 json_lex_keyword(struct json_parser *p)
586 {
587     struct json_token token;
588     const char *s;
589
590     s = ds_cstr(&p->buffer);
591     if (!strcmp(s, "false")) {
592         token.type = T_FALSE;
593     } else if (!strcmp(s, "true")) {
594         token.type = T_TRUE;
595     } else if (!strcmp(s, "null")) {
596         token.type = T_NULL;
597     } else {
598         json_error(p, "invalid keyword '%s'", s);
599         return;
600     }
601     json_parser_input(p, &token);
602 }
603
604 static void
605 json_lex_number(struct json_parser *p)
606 {
607     const char *cp = ds_cstr(&p->buffer);
608     unsigned long long int significand = 0;
609     struct json_token token;
610     bool imprecise = false;
611     bool negative = false;
612     int pow10 = 0;
613
614     /* Leading minus sign. */
615     if (*cp == '-') {
616         negative = true;
617         cp++;
618     }
619
620     /* At least one integer digit, but 0 may not be used as a leading digit for
621      * a longer number. */
622     significand = 0;
623     if (*cp == '0') {
624         cp++;
625         if (isdigit(*cp)) {
626             json_error(p, "leading zeros not allowed");
627             return;
628         }
629     } else if (isdigit(*cp)) {
630         do {
631             if (significand <= ULLONG_MAX / 10) {
632                 significand = significand * 10 + (*cp - '0');
633             } else {
634                 pow10++;
635                 if (*cp != '0') {
636                     imprecise = true;
637                 }
638             }
639             cp++;
640         } while (isdigit(*cp));
641     } else {
642         json_error(p, "'-' must be followed by digit");
643         return;
644     }
645
646     /* Optional fraction. */
647     if (*cp == '.') {
648         cp++;
649         if (!isdigit(*cp)) {
650             json_error(p, "decimal point must be followed by digit");
651             return;
652         }
653         do {
654             if (significand <= ULLONG_MAX / 10) {
655                 significand = significand * 10 + (*cp - '0');
656                 pow10--;
657             } else if (*cp != '0') {
658                 imprecise = true;
659             }
660             cp++;
661         } while (isdigit(*cp));
662     }
663
664     /* Optional exponent. */
665     if (*cp == 'e' || *cp == 'E') {
666         bool negative_exponent = false;
667         int exponent;
668
669         cp++;
670         if (*cp == '+') {
671             cp++;
672         } else if (*cp == '-') {
673             negative_exponent = true;
674             cp++;
675         }
676
677         if (!isdigit(*cp)) {
678             json_error(p, "exponent must contain at least one digit");
679             return;
680         }
681
682         exponent = 0;
683         do {
684             if (exponent >= INT_MAX / 10) {
685                 json_error(p, "exponent outside valid range");
686                 return;
687             }
688             exponent = exponent * 10 + (*cp - '0');
689             cp++;
690         } while (isdigit(*cp));
691
692         if (negative_exponent) {
693             pow10 -= exponent;
694         } else {
695             pow10 += exponent;
696         }
697     }
698
699     if (*cp != '\0') {
700         json_error(p, "syntax error in number");
701         return;
702     }
703
704     /* Figure out number.
705      *
706      * We suppress negative zeros as a matter of policy. */
707     if (!significand) {
708         struct json_token token;
709         token.type = T_INTEGER;
710         token.u.integer = 0;
711         json_parser_input(p, &token);
712         return;
713     }
714
715     if (!imprecise) {
716         while (pow10 > 0 && significand < ULLONG_MAX / 10) {
717             significand *= 10;
718             pow10--;
719         }
720         while (pow10 < 0 && significand % 10 == 0) {
721             significand /= 10;
722             pow10++;
723         }
724         if (pow10 == 0
725             && significand <= (negative
726                                ? (unsigned long long int) LLONG_MAX + 1
727                                : LLONG_MAX)) {
728             token.type = T_INTEGER;
729             token.u.integer = negative ? -significand : significand;
730             json_parser_input(p, &token);
731             return;
732         }
733     }
734
735     token.type = T_REAL;
736     if (!str_to_double(ds_cstr(&p->buffer), &token.u.real)) {
737         json_error(p, "number outside valid range");
738         return;
739     }
740     /* Suppress negative zero. */
741     if (token.u.real == 0) {
742         token.u.real = 0;
743     }
744     json_parser_input(p, &token);
745 }
746
747 static const char *
748 json_lex_4hex(const char *cp, const char *end, int *valuep)
749 {
750     int value, i;
751
752     if (cp + 4 > end) {
753         return "quoted string ends within \\u escape";
754     }
755
756     value = 0;
757     for (i = 0; i < 4; i++) {
758         unsigned char c = *cp++;
759         if (!isxdigit(c)) {
760             return "malformed \\u escape";
761         }
762         value = (value << 4) | hexit_value(c);
763     }
764     if (!value) {
765         return "null bytes not supported in quoted strings";
766     }
767     *valuep = value;
768     return NULL;
769 }
770
771 static const char *
772 json_lex_unicode(const char *cp, const char *end, struct ds *out)
773 {
774     const char *error;
775     int c0, c1;
776
777     error = json_lex_4hex(cp, end, &c0);
778     if (error) {
779         ds_clear(out);
780         ds_put_cstr(out, error);
781         return NULL;
782     }
783     cp += 4;
784     if (!uc_is_leading_surrogate(c0)) {
785         ds_put_utf8(out, c0);
786         return cp;
787     }
788
789     if (cp + 2 > end || *cp++ != '\\' || *cp++ != 'u') {
790         ds_clear(out);
791         ds_put_cstr(out, "malformed escaped surrogate pair");
792         return NULL;
793     }
794
795     error = json_lex_4hex(cp, end, &c1);
796     if (error) {
797         ds_clear(out);
798         ds_put_cstr(out, error);
799         return NULL;
800     }
801     cp += 4;
802     if (!uc_is_trailing_surrogate(c1)) {
803         ds_clear(out);
804         ds_put_cstr(out, "second half of escaped surrogate pair is not "
805                     "trailing surrogate");
806         return NULL;
807     }
808
809     ds_put_utf8(out, utf16_decode_surrogate_pair(c0, c1));
810     return cp;
811 }
812
813 bool
814 json_string_unescape(const char *in, size_t in_len, char **outp)
815 {
816     const char *end = in + in_len;
817     bool ok = false;
818     struct ds out;
819
820     ds_init(&out);
821     ds_reserve(&out, in_len);
822     if (in_len > 0 && in[in_len - 1] == '\\') {
823         ds_put_cstr(&out, "quoted string may not end with backslash");
824         goto exit;
825     }
826     while (in < end) {
827         if (*in == '"') {
828             ds_clear(&out);
829             ds_put_cstr(&out, "quoted string may not include unescaped \"");
830             goto exit;
831         }
832         if (*in != '\\') {
833             ds_put_char(&out, *in++);
834             continue;
835         }
836
837         in++;
838         switch (*in++) {
839         case '"': case '\\': case '/':
840             ds_put_char(&out, in[-1]);
841             break;
842
843         case 'b':
844             ds_put_char(&out, '\b');
845             break;
846
847         case 'f':
848             ds_put_char(&out, '\f');
849             break;
850
851         case 'n':
852             ds_put_char(&out, '\n');
853             break;
854
855         case 'r':
856             ds_put_char(&out, '\r');
857             break;
858
859         case 't':
860             ds_put_char(&out, '\t');
861             break;
862
863         case 'u':
864             in = json_lex_unicode(in, end, &out);
865             if (!in) {
866                 goto exit;
867             }
868             break;
869
870         default:
871             ds_clear(&out);
872             ds_put_format(&out, "bad escape \\%c", in[-1]);
873             goto exit;
874         }
875     }
876     ok = true;
877
878 exit:
879     *outp = ds_cstr(&out);
880     return ok;
881 }
882
883 static void
884 json_parser_input_string(struct json_parser *p, const char *s)
885 {
886     struct json_token token;
887
888     token.type = T_STRING;
889     token.u.string = s;
890     json_parser_input(p, &token);
891 }
892
893 static void
894 json_lex_string(struct json_parser *p)
895 {
896     const char *raw = ds_cstr(&p->buffer);
897     if (!strchr(raw, '\\')) {
898         json_parser_input_string(p, raw);
899     } else {
900         char *cooked;
901
902         if (json_string_unescape(raw, strlen(raw), &cooked)) {
903             json_parser_input_string(p, cooked);
904         } else {
905             json_error(p, "%s", cooked);
906         }
907
908         free(cooked);
909     }
910 }
911
912 static bool
913 json_lex_input(struct json_parser *p, unsigned char c)
914 {
915     struct json_token token;
916
917     p->byte_number++;
918     if (c == '\n') {
919         p->column_number = 0;
920         p->line_number++;
921     } else {
922         p->column_number++;
923     }
924
925     switch (p->lex_state) {
926     case JSON_LEX_START:
927         switch (c) {
928         case ' ': case '\t': case '\n': case '\r':
929             /* Nothing to do. */
930             return true;
931
932         case 'a': case 'b': case 'c': case 'd': case 'e':
933         case 'f': case 'g': case 'h': case 'i': case 'j':
934         case 'k': case 'l': case 'm': case 'n': case 'o':
935         case 'p': case 'q': case 'r': case 's': case 't':
936         case 'u': case 'v': case 'w': case 'x': case 'y':
937         case 'z':
938             p->lex_state = JSON_LEX_KEYWORD;
939             break;
940
941         case '[': case '{': case ']': case '}': case ':': case ',':
942             token.type = c;
943             json_parser_input(p, &token);
944             return true;
945
946         case '-':
947         case '0': case '1': case '2': case '3': case '4':
948         case '5': case '6': case '7': case '8': case '9':
949             p->lex_state = JSON_LEX_NUMBER;
950             break;
951
952         case '"':
953             p->lex_state = JSON_LEX_STRING;
954             return true;
955
956         default:
957             if (isprint(c)) {
958                 json_error(p, "invalid character '%c'", c);
959             } else {
960                 json_error(p, "invalid character U+%04x", c);
961             }
962             return true;
963         }
964         break;
965
966     case JSON_LEX_KEYWORD:
967         if (!isalpha((unsigned char) c)) {
968             json_lex_keyword(p);
969             return false;
970         }
971         break;
972
973     case JSON_LEX_NUMBER:
974         if (!strchr(".0123456789eE-+", c)) {
975             json_lex_number(p);
976             return false;
977         }
978         break;
979
980     case JSON_LEX_STRING:
981         if (c == '\\') {
982             p->lex_state = JSON_LEX_ESCAPE;
983         } else if (c == '"') {
984             json_lex_string(p);
985             return true;
986         } else if (c < 0x20) {
987             json_error(p, "U+%04X must be escaped in quoted string", c);
988             return true;
989         }
990         break;
991
992     case JSON_LEX_ESCAPE:
993         p->lex_state = JSON_LEX_STRING;
994         break;
995
996     default:
997         abort();
998     }
999     ds_put_char(&p->buffer, c);
1000     return true;
1001 }
1002 \f
1003 /* Parsing. */
1004
1005 /* Parses 'string' as a JSON object or array and returns a newly allocated
1006  * 'struct json'.  The caller must free the returned structure with
1007  * json_destroy() when it is no longer needed.
1008  *
1009  * 'string' must be encoded in UTF-8.
1010  *
1011  * If 'string' is valid JSON, then the returned 'struct json' will be either an
1012  * object (JSON_OBJECT) or an array (JSON_ARRAY).
1013  *
1014  * If 'string' is not valid JSON, then the returned 'struct json' will be a
1015  * string (JSON_STRING) that describes the particular error encountered during
1016  * parsing.  (This is an acceptable means of error reporting because at its top
1017  * level JSON must be either an object or an array; a bare string is not
1018  * valid.) */
1019 struct json *
1020 json_from_string(const char *string)
1021 {
1022     struct json_parser *p = json_parser_create(JSPF_TRAILER);
1023     json_parser_feed(p, string, strlen(string));
1024     return json_parser_finish(p);
1025 }
1026
1027 /* Reads the file named 'file_name', parses its contents as a JSON object or
1028  * array, and returns a newly allocated 'struct json'.  The caller must free
1029  * the returned structure with json_destroy() when it is no longer needed.
1030  *
1031  * The file must be encoded in UTF-8.
1032  *
1033  * See json_from_string() for return value semantics.
1034  */
1035 struct json *
1036 json_from_file(const char *file_name)
1037 {
1038     struct json *json;
1039     FILE *stream;
1040
1041     stream = fopen(file_name, "r");
1042     if (!stream) {
1043         return json_string_create_nocopy(
1044             xasprintf("error opening \"%s\": %s", file_name, strerror(errno)));
1045     }
1046     json = json_from_stream(stream);
1047     fclose(stream);
1048
1049     return json;
1050 }
1051
1052 /* Parses the contents of 'stream' as a JSON object or array, and returns a
1053  * newly allocated 'struct json'.  The caller must free the returned structure
1054  * with json_destroy() when it is no longer needed.
1055  *
1056  * The file must be encoded in UTF-8.
1057  *
1058  * See json_from_string() for return value semantics.
1059  */
1060 struct json *
1061 json_from_stream(FILE *stream)
1062 {
1063     struct json_parser *p;
1064     struct json *json;
1065
1066     p = json_parser_create(JSPF_TRAILER);
1067     for (;;) {
1068         char buffer[BUFSIZ];
1069         size_t n;
1070
1071         n = fread(buffer, 1, sizeof buffer, stream);
1072         if (!n || json_parser_feed(p, buffer, n) != n) {
1073             break;
1074         }
1075     }
1076     json = json_parser_finish(p);
1077
1078     if (ferror(stream)) {
1079         json_destroy(json);
1080         json = json_string_create_nocopy(
1081             xasprintf("error reading JSON stream: %s", strerror(errno)));
1082     }
1083
1084     return json;
1085 }
1086
1087 struct json_parser *
1088 json_parser_create(int flags)
1089 {
1090     struct json_parser *p = xzalloc(sizeof *p);
1091     p->flags = flags;
1092     return p;
1093 }
1094
1095 size_t
1096 json_parser_feed(struct json_parser *p, const char *input, size_t n)
1097 {
1098     size_t i;
1099     for (i = 0; !p->done && i < n; ) {
1100         if (json_lex_input(p, input[i])) {
1101             i++;
1102         }
1103     }
1104     return i;
1105 }
1106
1107 bool
1108 json_parser_is_done(const struct json_parser *p)
1109 {
1110     return p->done;
1111 }
1112
1113 struct json *
1114 json_parser_finish(struct json_parser *p)
1115 {
1116     struct json *json;
1117
1118     switch (p->lex_state) {
1119     case JSON_LEX_START:
1120         break;
1121
1122     case JSON_LEX_STRING:
1123     case JSON_LEX_ESCAPE:
1124         json_error(p, "unexpected end of input in quoted string");
1125         break;
1126
1127     case JSON_LEX_NUMBER:
1128     case JSON_LEX_KEYWORD:
1129         json_lex_input(p, ' ');
1130         break;
1131     }
1132
1133     if (p->parse_state == JSON_PARSE_START) {
1134         json_error(p, "empty input stream");
1135     } else if (p->parse_state != JSON_PARSE_END) {
1136         json_error(p, "unexpected end of input");
1137     }
1138
1139     if (!p->error) {
1140         assert(p->height == 1);
1141         assert(p->stack[0].json != NULL);
1142         json = p->stack[--p->height].json;
1143     } else {
1144         json = json_string_create_nocopy(p->error);
1145         p->error = NULL;
1146     }
1147
1148     json_parser_abort(p);
1149
1150     return json;
1151 }
1152
1153 void
1154 json_parser_abort(struct json_parser *p)
1155 {
1156     if (p) {
1157         ds_destroy(&p->buffer);
1158         if (p->height) {
1159             json_destroy(p->stack[0].json);
1160         }
1161         free(p->stack);
1162         free(p->member_name);
1163         free(p->error);
1164         free(p);
1165     }
1166 }
1167
1168 static struct json_parser_node *
1169 json_parser_top(struct json_parser *p)
1170 {
1171     return &p->stack[p->height - 1];
1172 }
1173
1174 static void
1175 json_parser_put_value(struct json_parser *p, struct json *value)
1176 {
1177     struct json_parser_node *node = json_parser_top(p);
1178     if (node->json->type == JSON_OBJECT) {
1179         json_object_put(node->json, p->member_name, value);
1180         free(p->member_name);
1181         p->member_name = NULL;
1182     } else if (node->json->type == JSON_ARRAY) {
1183         json_array_add(node->json, value);
1184     } else {
1185         NOT_REACHED();
1186     }
1187 }
1188
1189 static void
1190 json_parser_push(struct json_parser *p,
1191                  struct json *new_json, enum json_parse_state new_state)
1192 {
1193     if (p->height < JSON_MAX_HEIGHT) {
1194         struct json_parser_node *node;
1195
1196         if (p->height >= p->allocated_height) {
1197             p->stack = x2nrealloc(p->stack, &p->allocated_height,
1198                                   sizeof *p->stack);
1199         }
1200
1201         if (p->height > 0) {
1202             json_parser_put_value(p, new_json);
1203         }
1204
1205         node = &p->stack[p->height++];
1206         node->json = new_json;
1207         p->parse_state = new_state;
1208     } else {
1209         json_destroy(new_json);
1210         json_error(p, "input exceeds maximum nesting depth %d",
1211                    JSON_MAX_HEIGHT);
1212     }
1213 }
1214
1215 static void
1216 json_parser_push_object(struct json_parser *p)
1217 {
1218     json_parser_push(p, json_object_create(), JSON_PARSE_OBJECT_INIT);
1219 }
1220
1221 static void
1222 json_parser_push_array(struct json_parser *p)
1223 {
1224     json_parser_push(p, json_array_create_empty(), JSON_PARSE_ARRAY_INIT);
1225 }
1226
1227 static void
1228 json_parse_value(struct json_parser *p, struct json_token *token,
1229                  enum json_parse_state next_state)
1230 {
1231     struct json *value;
1232
1233     switch (token->type) {
1234     case T_FALSE:
1235         value = json_boolean_create(false);
1236         break;
1237
1238     case T_NULL:
1239         value = json_null_create();
1240         break;
1241
1242     case T_TRUE:
1243         value = json_boolean_create(true);
1244         break;
1245
1246     case '{':
1247         json_parser_push_object(p);
1248         return;
1249
1250     case '[':
1251         json_parser_push_array(p);
1252         return;
1253
1254     case T_INTEGER:
1255         value = json_integer_create(token->u.integer);
1256         break;
1257
1258     case T_REAL:
1259         value = json_real_create(token->u.real);
1260         break;
1261
1262     case T_STRING:
1263         value = json_string_create(token->u.string);
1264         break;
1265
1266     case T_EOF:
1267     case '}':
1268     case ']':
1269     case ':':
1270     case ',':
1271     default:
1272         json_error(p, "syntax error expecting value");
1273         return;
1274     }
1275
1276     json_parser_put_value(p, value);
1277     p->parse_state = next_state;
1278 }
1279
1280 static void
1281 json_parser_pop(struct json_parser *p)
1282 {
1283     struct json_parser_node *node;
1284
1285     /* Conserve memory. */
1286     node = json_parser_top(p);
1287     if (node->json->type == JSON_ARRAY) {
1288         json_array_trim(node->json);
1289     }
1290
1291     /* Pop off the top-of-stack. */
1292     if (p->height == 1) {
1293         p->parse_state = JSON_PARSE_END;
1294         if (!(p->flags & JSPF_TRAILER)) {
1295             p->done = true;
1296         }
1297     } else {
1298         p->height--;
1299         node = json_parser_top(p);
1300         if (node->json->type == JSON_ARRAY) {
1301             p->parse_state = JSON_PARSE_ARRAY_NEXT;
1302         } else if (node->json->type == JSON_OBJECT) {
1303             p->parse_state = JSON_PARSE_OBJECT_NEXT;
1304         } else {
1305             NOT_REACHED();
1306         }
1307     }
1308 }
1309
1310 static void
1311 json_parser_input(struct json_parser *p, struct json_token *token)
1312 {
1313     switch (p->parse_state) {
1314     case JSON_PARSE_START:
1315         if (token->type == '{') {
1316             json_parser_push_object(p);
1317         } else if (token->type == '[') {
1318             json_parser_push_array(p);
1319         } else {
1320             json_error(p, "syntax error at beginning of input");
1321         }
1322         break;
1323
1324     case JSON_PARSE_END:
1325         json_error(p, "trailing garbage at end of input");
1326         break;
1327
1328     case JSON_PARSE_OBJECT_INIT:
1329         if (token->type == '}') {
1330             json_parser_pop(p);
1331             break;
1332         }
1333         /* Fall through. */
1334     case JSON_PARSE_OBJECT_NAME:
1335         if (token->type == T_STRING) {
1336             p->member_name = xstrdup(token->u.string);
1337             p->parse_state = JSON_PARSE_OBJECT_COLON;
1338         } else {
1339             json_error(p, "syntax error parsing object expecting string");
1340         }
1341         break;
1342
1343     case JSON_PARSE_OBJECT_COLON:
1344         if (token->type == ':') {
1345             p->parse_state = JSON_PARSE_OBJECT_VALUE;
1346         } else {
1347             json_error(p, "syntax error parsing object expecting ':'");
1348         }
1349         break;
1350
1351     case JSON_PARSE_OBJECT_VALUE:
1352         json_parse_value(p, token, JSON_PARSE_OBJECT_NEXT);
1353         break;
1354
1355     case JSON_PARSE_OBJECT_NEXT:
1356         if (token->type == ',') {
1357             p->parse_state = JSON_PARSE_OBJECT_NAME;
1358         } else if (token->type == '}') {
1359             json_parser_pop(p);
1360         } else {
1361             json_error(p, "syntax error expecting '}' or ','");
1362         }
1363         break;
1364
1365     case JSON_PARSE_ARRAY_INIT:
1366         if (token->type == ']') {
1367             json_parser_pop(p);
1368             break;
1369         }
1370         /* Fall through. */
1371     case JSON_PARSE_ARRAY_VALUE:
1372         json_parse_value(p, token, JSON_PARSE_ARRAY_NEXT);
1373         break;
1374
1375     case JSON_PARSE_ARRAY_NEXT:
1376         if (token->type == ',') {
1377             p->parse_state = JSON_PARSE_ARRAY_VALUE;
1378         } else if (token->type == ']') {
1379             json_parser_pop(p);
1380         } else {
1381             json_error(p, "syntax error expecting ']' or ','");
1382         }
1383         break;
1384
1385     default:
1386         abort();
1387     }
1388
1389     p->lex_state = JSON_LEX_START;
1390     ds_clear(&p->buffer);
1391 }
1392
1393 static struct json *
1394 json_create(enum json_type type)
1395 {
1396     struct json *json = xmalloc(sizeof *json);
1397     json->type = type;
1398     return json;
1399 }
1400
1401 static void
1402 json_error(struct json_parser *p, const char *format, ...)
1403 {
1404     if (!p->error) {
1405         struct ds msg;
1406         va_list args;
1407
1408         ds_init(&msg);
1409         ds_put_format(&msg, "line %d, column %d, byte %d: ",
1410                       p->line_number, p->column_number, p->byte_number);
1411         va_start(args, format);
1412         ds_put_format_valist(&msg, format, args);
1413         va_end(args);
1414
1415         p->error = ds_steal_cstr(&msg);
1416
1417         p->done = true;
1418     }
1419 }
1420 \f
1421 #define SPACES_PER_LEVEL 2
1422
1423 struct json_serializer {
1424     struct ds *ds;
1425     int depth;
1426     int flags;
1427 };
1428
1429 static void json_serialize(const struct json *, struct json_serializer *);
1430 static void json_serialize_object(const struct shash *object,
1431                                   struct json_serializer *);
1432 static void json_serialize_array(const struct json_array *,
1433                                  struct json_serializer *);
1434 static void json_serialize_string(const char *, struct ds *);
1435
1436 /* Converts 'json' to a string in JSON format, encoded in UTF-8, and returns
1437  * that string.  The caller is responsible for freeing the returned string,
1438  * with free(), when it is no longer needed.
1439  *
1440  * If 'flags' contains JSSF_PRETTY, the output is pretty-printed with each
1441  * nesting level introducing an additional indentation.  Otherwise, the
1442  * returned string does not contain any new-line characters.
1443  *
1444  * If 'flags' contains JSSF_SORT, members of objects in the output are sorted
1445  * in bytewise lexicographic order for reproducibility.  Otherwise, members of
1446  * objects are output in an indeterminate order.
1447  *
1448  * The returned string is valid JSON only if 'json' represents an array or an
1449  * object, since a bare literal does not satisfy the JSON grammar. */
1450 char *
1451 json_to_string(const struct json *json, int flags)
1452 {
1453     struct ds ds;
1454
1455     ds_init(&ds);
1456     json_to_ds(json, flags, &ds);
1457     return ds_steal_cstr(&ds);
1458 }
1459
1460 /* Same as json_to_string(), but the output is appended to 'ds'. */
1461 void
1462 json_to_ds(const struct json *json, int flags, struct ds *ds)
1463 {
1464     struct json_serializer s;
1465
1466     s.ds = ds;
1467     s.depth = 0;
1468     s.flags = flags;
1469     json_serialize(json, &s);
1470 }
1471
1472 static void
1473 json_serialize(const struct json *json, struct json_serializer *s)
1474 {
1475     struct ds *ds = s->ds;
1476
1477     switch (json->type) {
1478     case JSON_NULL:
1479         ds_put_cstr(ds, "null");
1480         break;
1481
1482     case JSON_FALSE:
1483         ds_put_cstr(ds, "false");
1484         break;
1485
1486     case JSON_TRUE:
1487         ds_put_cstr(ds, "true");
1488         break;
1489
1490     case JSON_OBJECT:
1491         json_serialize_object(json->u.object, s);
1492         break;
1493
1494     case JSON_ARRAY:
1495         json_serialize_array(&json->u.array, s);
1496         break;
1497
1498     case JSON_INTEGER:
1499         ds_put_format(ds, "%lld", json->u.integer);
1500         break;
1501
1502     case JSON_REAL:
1503         ds_put_format(ds, "%.*g", DBL_DIG, json->u.real);
1504         break;
1505
1506     case JSON_STRING:
1507         json_serialize_string(json->u.string, ds);
1508         break;
1509
1510     case JSON_N_TYPES:
1511     default:
1512         NOT_REACHED();
1513     }
1514 }
1515
1516 static void
1517 indent_line(struct json_serializer *s)
1518 {
1519     if (s->flags & JSSF_PRETTY) {
1520         ds_put_char(s->ds, '\n');
1521         ds_put_char_multiple(s->ds, ' ', SPACES_PER_LEVEL * s->depth);
1522     }
1523 }
1524
1525 static void
1526 json_serialize_object_member(size_t i, const struct shash_node *node,
1527                              struct json_serializer *s)
1528 {
1529     struct ds *ds = s->ds;
1530
1531     if (i) {
1532         ds_put_char(ds, ',');
1533         indent_line(s);
1534     }
1535
1536     json_serialize_string(node->name, ds);
1537     ds_put_char(ds, ':');
1538     if (s->flags & JSSF_PRETTY) {
1539         ds_put_char(ds, ' ');
1540     }
1541     json_serialize(node->data, s);
1542 }
1543
1544 static void
1545 json_serialize_object(const struct shash *object, struct json_serializer *s)
1546 {
1547     struct ds *ds = s->ds;
1548
1549     ds_put_char(ds, '{');
1550
1551     s->depth++;
1552     indent_line(s);
1553
1554     if (s->flags & JSSF_SORT) {
1555         const struct shash_node **nodes;
1556         size_t n, i;
1557
1558         nodes = shash_sort(object);
1559         n = shash_count(object);
1560         for (i = 0; i < n; i++) {
1561             json_serialize_object_member(i, nodes[i], s);
1562         }
1563         free(nodes);
1564     } else {
1565         struct shash_node *node;
1566         size_t i;
1567
1568         i = 0;
1569         SHASH_FOR_EACH (node, object) {
1570             json_serialize_object_member(i++, node, s);
1571         }
1572     }
1573
1574     ds_put_char(ds, '}');
1575     s->depth--;
1576 }
1577
1578 static void
1579 json_serialize_array(const struct json_array *array, struct json_serializer *s)
1580 {
1581     struct ds *ds = s->ds;
1582     size_t i;
1583
1584     ds_put_char(ds, '[');
1585     s->depth++;
1586
1587     if (array->n > 0) {
1588         indent_line(s);
1589
1590         for (i = 0; i < array->n; i++) {
1591             if (i) {
1592                 ds_put_char(ds, ',');
1593                 indent_line(s);
1594             }
1595             json_serialize(array->elems[i], s);
1596         }
1597     }
1598
1599     s->depth--;
1600     ds_put_char(ds, ']');
1601 }
1602
1603 static void
1604 json_serialize_string(const char *string, struct ds *ds)
1605 {
1606     uint8_t c;
1607
1608     ds_put_char(ds, '"');
1609     while ((c = *string++) != '\0') {
1610         switch (c) {
1611         case '"':
1612             ds_put_cstr(ds, "\\\"");
1613             break;
1614
1615         case '\\':
1616             ds_put_cstr(ds, "\\\\");
1617             break;
1618
1619         case '\b':
1620             ds_put_cstr(ds, "\\b");
1621             break;
1622
1623         case '\f':
1624             ds_put_cstr(ds, "\\f");
1625             break;
1626
1627         case '\n':
1628             ds_put_cstr(ds, "\\n");
1629             break;
1630
1631         case '\r':
1632             ds_put_cstr(ds, "\\r");
1633             break;
1634
1635         case '\t':
1636             ds_put_cstr(ds, "\\t");
1637             break;
1638
1639         default:
1640             if (c >= 32) {
1641                 ds_put_char(ds, c);
1642             } else {
1643                 ds_put_format(ds, "\\u%04x", c);
1644             }
1645             break;
1646         }
1647     }
1648     ds_put_char(ds, '"');
1649 }