These changes are a raw update to a vanilla kernel 4.1.10, with the
[kvmfornfv.git] / qemu / qobject / json-parser.c
1 /*
2  * JSON Parser 
3  *
4  * Copyright IBM, Corp. 2009
5  *
6  * Authors:
7  *  Anthony Liguori   <aliguori@us.ibm.com>
8  *
9  * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
10  * See the COPYING.LIB file in the top-level directory.
11  *
12  */
13
14 #include <stdarg.h>
15
16 #include "qemu-common.h"
17 #include "qapi/qmp/qstring.h"
18 #include "qapi/qmp/qint.h"
19 #include "qapi/qmp/qdict.h"
20 #include "qapi/qmp/qlist.h"
21 #include "qapi/qmp/qfloat.h"
22 #include "qapi/qmp/qbool.h"
23 #include "qapi/qmp/json-parser.h"
24 #include "qapi/qmp/json-lexer.h"
25
26 typedef struct JSONParserContext
27 {
28     Error *err;
29     struct {
30         QObject **buf;
31         size_t pos;
32         size_t count;
33     } tokens;
34 } JSONParserContext;
35
36 #define BUG_ON(cond) assert(!(cond))
37
38 /**
39  * TODO
40  *
41  * 0) make errors meaningful again
42  * 1) add geometry information to tokens
43  * 3) should we return a parsed size?
44  * 4) deal with premature EOI
45  */
46
47 static QObject *parse_value(JSONParserContext *ctxt, va_list *ap);
48
49 /**
50  * Token manipulators
51  *
52  * tokens are dictionaries that contain a type, a string value, and geometry information
53  * about a token identified by the lexer.  These are routines that make working with
54  * these objects a bit easier.
55  */
56 static const char *token_get_value(QObject *obj)
57 {
58     return qdict_get_str(qobject_to_qdict(obj), "token");
59 }
60
61 static JSONTokenType token_get_type(QObject *obj)
62 {
63     return qdict_get_int(qobject_to_qdict(obj), "type");
64 }
65
66 static int token_is_operator(QObject *obj, char op)
67 {
68     const char *val;
69
70     if (token_get_type(obj) != JSON_OPERATOR) {
71         return 0;
72     }
73
74     val = token_get_value(obj);
75
76     return (val[0] == op) && (val[1] == 0);
77 }
78
79 static int token_is_keyword(QObject *obj, const char *value)
80 {
81     if (token_get_type(obj) != JSON_KEYWORD) {
82         return 0;
83     }
84
85     return strcmp(token_get_value(obj), value) == 0;
86 }
87
88 static int token_is_escape(QObject *obj, const char *value)
89 {
90     if (token_get_type(obj) != JSON_ESCAPE) {
91         return 0;
92     }
93
94     return (strcmp(token_get_value(obj), value) == 0);
95 }
96
97 /**
98  * Error handler
99  */
100 static void GCC_FMT_ATTR(3, 4) parse_error(JSONParserContext *ctxt,
101                                            QObject *token, const char *msg, ...)
102 {
103     va_list ap;
104     char message[1024];
105     va_start(ap, msg);
106     vsnprintf(message, sizeof(message), msg, ap);
107     va_end(ap);
108     if (ctxt->err) {
109         error_free(ctxt->err);
110         ctxt->err = NULL;
111     }
112     error_setg(&ctxt->err, "JSON parse error, %s", message);
113 }
114
115 /**
116  * String helpers
117  *
118  * These helpers are used to unescape strings.
119  */
120 static void wchar_to_utf8(uint16_t wchar, char *buffer, size_t buffer_length)
121 {
122     if (wchar <= 0x007F) {
123         BUG_ON(buffer_length < 2);
124
125         buffer[0] = wchar & 0x7F;
126         buffer[1] = 0;
127     } else if (wchar <= 0x07FF) {
128         BUG_ON(buffer_length < 3);
129
130         buffer[0] = 0xC0 | ((wchar >> 6) & 0x1F);
131         buffer[1] = 0x80 | (wchar & 0x3F);
132         buffer[2] = 0;
133     } else {
134         BUG_ON(buffer_length < 4);
135
136         buffer[0] = 0xE0 | ((wchar >> 12) & 0x0F);
137         buffer[1] = 0x80 | ((wchar >> 6) & 0x3F);
138         buffer[2] = 0x80 | (wchar & 0x3F);
139         buffer[3] = 0;
140     }
141 }
142
143 static int hex2decimal(char ch)
144 {
145     if (ch >= '0' && ch <= '9') {
146         return (ch - '0');
147     } else if (ch >= 'a' && ch <= 'f') {
148         return 10 + (ch - 'a');
149     } else if (ch >= 'A' && ch <= 'F') {
150         return 10 + (ch - 'A');
151     }
152
153     return -1;
154 }
155
156 /**
157  * parse_string(): Parse a json string and return a QObject
158  *
159  *  string
160  *      ""
161  *      " chars "
162  *  chars
163  *      char
164  *      char chars
165  *  char
166  *      any-Unicode-character-
167  *          except-"-or-\-or-
168  *          control-character
169  *      \"
170  *      \\
171  *      \/
172  *      \b
173  *      \f
174  *      \n
175  *      \r
176  *      \t
177  *      \u four-hex-digits 
178  */
179 static QString *qstring_from_escaped_str(JSONParserContext *ctxt, QObject *token)
180 {
181     const char *ptr = token_get_value(token);
182     QString *str;
183     int double_quote = 1;
184
185     if (*ptr == '"') {
186         double_quote = 1;
187     } else {
188         double_quote = 0;
189     }
190     ptr++;
191
192     str = qstring_new();
193     while (*ptr && 
194            ((double_quote && *ptr != '"') || (!double_quote && *ptr != '\''))) {
195         if (*ptr == '\\') {
196             ptr++;
197
198             switch (*ptr) {
199             case '"':
200                 qstring_append(str, "\"");
201                 ptr++;
202                 break;
203             case '\'':
204                 qstring_append(str, "'");
205                 ptr++;
206                 break;
207             case '\\':
208                 qstring_append(str, "\\");
209                 ptr++;
210                 break;
211             case '/':
212                 qstring_append(str, "/");
213                 ptr++;
214                 break;
215             case 'b':
216                 qstring_append(str, "\b");
217                 ptr++;
218                 break;
219             case 'f':
220                 qstring_append(str, "\f");
221                 ptr++;
222                 break;
223             case 'n':
224                 qstring_append(str, "\n");
225                 ptr++;
226                 break;
227             case 'r':
228                 qstring_append(str, "\r");
229                 ptr++;
230                 break;
231             case 't':
232                 qstring_append(str, "\t");
233                 ptr++;
234                 break;
235             case 'u': {
236                 uint16_t unicode_char = 0;
237                 char utf8_char[4];
238                 int i = 0;
239
240                 ptr++;
241
242                 for (i = 0; i < 4; i++) {
243                     if (qemu_isxdigit(*ptr)) {
244                         unicode_char |= hex2decimal(*ptr) << ((3 - i) * 4);
245                     } else {
246                         parse_error(ctxt, token,
247                                     "invalid hex escape sequence in string");
248                         goto out;
249                     }
250                     ptr++;
251                 }
252
253                 wchar_to_utf8(unicode_char, utf8_char, sizeof(utf8_char));
254                 qstring_append(str, utf8_char);
255             }   break;
256             default:
257                 parse_error(ctxt, token, "invalid escape sequence in string");
258                 goto out;
259             }
260         } else {
261             char dummy[2];
262
263             dummy[0] = *ptr++;
264             dummy[1] = 0;
265
266             qstring_append(str, dummy);
267         }
268     }
269
270     return str;
271
272 out:
273     QDECREF(str);
274     return NULL;
275 }
276
277 static QObject *parser_context_pop_token(JSONParserContext *ctxt)
278 {
279     QObject *token;
280     g_assert(ctxt->tokens.pos < ctxt->tokens.count);
281     token = ctxt->tokens.buf[ctxt->tokens.pos];
282     ctxt->tokens.pos++;
283     return token;
284 }
285
286 /* Note: parser_context_{peek|pop}_token do not increment the
287  * token object's refcount. In both cases the references will continue
288  * to be tracked and cleaned up in parser_context_free(), so do not
289  * attempt to free the token object.
290  */
291 static QObject *parser_context_peek_token(JSONParserContext *ctxt)
292 {
293     QObject *token;
294     g_assert(ctxt->tokens.pos < ctxt->tokens.count);
295     token = ctxt->tokens.buf[ctxt->tokens.pos];
296     return token;
297 }
298
299 static JSONParserContext parser_context_save(JSONParserContext *ctxt)
300 {
301     JSONParserContext saved_ctxt = {0};
302     saved_ctxt.tokens.pos = ctxt->tokens.pos;
303     saved_ctxt.tokens.count = ctxt->tokens.count;
304     saved_ctxt.tokens.buf = ctxt->tokens.buf;
305     return saved_ctxt;
306 }
307
308 static void parser_context_restore(JSONParserContext *ctxt,
309                                    JSONParserContext saved_ctxt)
310 {
311     ctxt->tokens.pos = saved_ctxt.tokens.pos;
312     ctxt->tokens.count = saved_ctxt.tokens.count;
313     ctxt->tokens.buf = saved_ctxt.tokens.buf;
314 }
315
316 static void tokens_append_from_iter(QObject *obj, void *opaque)
317 {
318     JSONParserContext *ctxt = opaque;
319     g_assert(ctxt->tokens.pos < ctxt->tokens.count);
320     ctxt->tokens.buf[ctxt->tokens.pos++] = obj;
321     qobject_incref(obj);
322 }
323
324 static JSONParserContext *parser_context_new(QList *tokens)
325 {
326     JSONParserContext *ctxt;
327     size_t count;
328
329     if (!tokens) {
330         return NULL;
331     }
332
333     count = qlist_size(tokens);
334     if (count == 0) {
335         return NULL;
336     }
337
338     ctxt = g_malloc0(sizeof(JSONParserContext));
339     ctxt->tokens.pos = 0;
340     ctxt->tokens.count = count;
341     ctxt->tokens.buf = g_malloc(count * sizeof(QObject *));
342     qlist_iter(tokens, tokens_append_from_iter, ctxt);
343     ctxt->tokens.pos = 0;
344
345     return ctxt;
346 }
347
348 /* to support error propagation, ctxt->err must be freed separately */
349 static void parser_context_free(JSONParserContext *ctxt)
350 {
351     int i;
352     if (ctxt) {
353         for (i = 0; i < ctxt->tokens.count; i++) {
354             qobject_decref(ctxt->tokens.buf[i]);
355         }
356         g_free(ctxt->tokens.buf);
357         g_free(ctxt);
358     }
359 }
360
361 /**
362  * Parsing rules
363  */
364 static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
365 {
366     QObject *key = NULL, *token = NULL, *value, *peek;
367     JSONParserContext saved_ctxt = parser_context_save(ctxt);
368
369     peek = parser_context_peek_token(ctxt);
370     if (peek == NULL) {
371         parse_error(ctxt, NULL, "premature EOI");
372         goto out;
373     }
374
375     key = parse_value(ctxt, ap);
376     if (!key || qobject_type(key) != QTYPE_QSTRING) {
377         parse_error(ctxt, peek, "key is not a string in object");
378         goto out;
379     }
380
381     token = parser_context_pop_token(ctxt);
382     if (token == NULL) {
383         parse_error(ctxt, NULL, "premature EOI");
384         goto out;
385     }
386
387     if (!token_is_operator(token, ':')) {
388         parse_error(ctxt, token, "missing : in object pair");
389         goto out;
390     }
391
392     value = parse_value(ctxt, ap);
393     if (value == NULL) {
394         parse_error(ctxt, token, "Missing value in dict");
395         goto out;
396     }
397
398     qdict_put_obj(dict, qstring_get_str(qobject_to_qstring(key)), value);
399
400     qobject_decref(key);
401
402     return 0;
403
404 out:
405     parser_context_restore(ctxt, saved_ctxt);
406     qobject_decref(key);
407
408     return -1;
409 }
410
411 static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
412 {
413     QDict *dict = NULL;
414     QObject *token, *peek;
415     JSONParserContext saved_ctxt = parser_context_save(ctxt);
416
417     token = parser_context_pop_token(ctxt);
418     if (token == NULL) {
419         goto out;
420     }
421
422     if (!token_is_operator(token, '{')) {
423         goto out;
424     }
425
426     dict = qdict_new();
427
428     peek = parser_context_peek_token(ctxt);
429     if (peek == NULL) {
430         parse_error(ctxt, NULL, "premature EOI");
431         goto out;
432     }
433
434     if (!token_is_operator(peek, '}')) {
435         if (parse_pair(ctxt, dict, ap) == -1) {
436             goto out;
437         }
438
439         token = parser_context_pop_token(ctxt);
440         if (token == NULL) {
441             parse_error(ctxt, NULL, "premature EOI");
442             goto out;
443         }
444
445         while (!token_is_operator(token, '}')) {
446             if (!token_is_operator(token, ',')) {
447                 parse_error(ctxt, token, "expected separator in dict");
448                 goto out;
449             }
450
451             if (parse_pair(ctxt, dict, ap) == -1) {
452                 goto out;
453             }
454
455             token = parser_context_pop_token(ctxt);
456             if (token == NULL) {
457                 parse_error(ctxt, NULL, "premature EOI");
458                 goto out;
459             }
460         }
461     } else {
462         (void)parser_context_pop_token(ctxt);
463     }
464
465     return QOBJECT(dict);
466
467 out:
468     parser_context_restore(ctxt, saved_ctxt);
469     QDECREF(dict);
470     return NULL;
471 }
472
473 static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
474 {
475     QList *list = NULL;
476     QObject *token, *peek;
477     JSONParserContext saved_ctxt = parser_context_save(ctxt);
478
479     token = parser_context_pop_token(ctxt);
480     if (token == NULL) {
481         goto out;
482     }
483
484     if (!token_is_operator(token, '[')) {
485         goto out;
486     }
487
488     list = qlist_new();
489
490     peek = parser_context_peek_token(ctxt);
491     if (peek == NULL) {
492         parse_error(ctxt, NULL, "premature EOI");
493         goto out;
494     }
495
496     if (!token_is_operator(peek, ']')) {
497         QObject *obj;
498
499         obj = parse_value(ctxt, ap);
500         if (obj == NULL) {
501             parse_error(ctxt, token, "expecting value");
502             goto out;
503         }
504
505         qlist_append_obj(list, obj);
506
507         token = parser_context_pop_token(ctxt);
508         if (token == NULL) {
509             parse_error(ctxt, NULL, "premature EOI");
510             goto out;
511         }
512
513         while (!token_is_operator(token, ']')) {
514             if (!token_is_operator(token, ',')) {
515                 parse_error(ctxt, token, "expected separator in list");
516                 goto out;
517             }
518
519             obj = parse_value(ctxt, ap);
520             if (obj == NULL) {
521                 parse_error(ctxt, token, "expecting value");
522                 goto out;
523             }
524
525             qlist_append_obj(list, obj);
526
527             token = parser_context_pop_token(ctxt);
528             if (token == NULL) {
529                 parse_error(ctxt, NULL, "premature EOI");
530                 goto out;
531             }
532         }
533     } else {
534         (void)parser_context_pop_token(ctxt);
535     }
536
537     return QOBJECT(list);
538
539 out:
540     parser_context_restore(ctxt, saved_ctxt);
541     QDECREF(list);
542     return NULL;
543 }
544
545 static QObject *parse_keyword(JSONParserContext *ctxt)
546 {
547     QObject *token, *ret;
548     JSONParserContext saved_ctxt = parser_context_save(ctxt);
549
550     token = parser_context_pop_token(ctxt);
551     if (token == NULL) {
552         goto out;
553     }
554
555     if (token_get_type(token) != JSON_KEYWORD) {
556         goto out;
557     }
558
559     if (token_is_keyword(token, "true")) {
560         ret = QOBJECT(qbool_from_bool(true));
561     } else if (token_is_keyword(token, "false")) {
562         ret = QOBJECT(qbool_from_bool(false));
563     } else if (token_is_keyword(token, "null")) {
564         ret = qnull();
565     } else {
566         parse_error(ctxt, token, "invalid keyword `%s'", token_get_value(token));
567         goto out;
568     }
569
570     return ret;
571
572 out: 
573     parser_context_restore(ctxt, saved_ctxt);
574
575     return NULL;
576 }
577
578 static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
579 {
580     QObject *token = NULL, *obj;
581     JSONParserContext saved_ctxt = parser_context_save(ctxt);
582
583     if (ap == NULL) {
584         goto out;
585     }
586
587     token = parser_context_pop_token(ctxt);
588     if (token == NULL) {
589         goto out;
590     }
591
592     if (token_is_escape(token, "%p")) {
593         obj = va_arg(*ap, QObject *);
594     } else if (token_is_escape(token, "%i")) {
595         obj = QOBJECT(qbool_from_bool(va_arg(*ap, int)));
596     } else if (token_is_escape(token, "%d")) {
597         obj = QOBJECT(qint_from_int(va_arg(*ap, int)));
598     } else if (token_is_escape(token, "%ld")) {
599         obj = QOBJECT(qint_from_int(va_arg(*ap, long)));
600     } else if (token_is_escape(token, "%lld") ||
601                token_is_escape(token, "%I64d")) {
602         obj = QOBJECT(qint_from_int(va_arg(*ap, long long)));
603     } else if (token_is_escape(token, "%s")) {
604         obj = QOBJECT(qstring_from_str(va_arg(*ap, const char *)));
605     } else if (token_is_escape(token, "%f")) {
606         obj = QOBJECT(qfloat_from_double(va_arg(*ap, double)));
607     } else {
608         goto out;
609     }
610
611     return obj;
612
613 out:
614     parser_context_restore(ctxt, saved_ctxt);
615
616     return NULL;
617 }
618
619 static QObject *parse_literal(JSONParserContext *ctxt)
620 {
621     QObject *token, *obj;
622     JSONParserContext saved_ctxt = parser_context_save(ctxt);
623
624     token = parser_context_pop_token(ctxt);
625     if (token == NULL) {
626         goto out;
627     }
628
629     switch (token_get_type(token)) {
630     case JSON_STRING:
631         obj = QOBJECT(qstring_from_escaped_str(ctxt, token));
632         break;
633     case JSON_INTEGER: {
634         /* A possibility exists that this is a whole-valued float where the
635          * fractional part was left out due to being 0 (.0). It's not a big
636          * deal to treat these as ints in the parser, so long as users of the
637          * resulting QObject know to expect a QInt in place of a QFloat in
638          * cases like these.
639          *
640          * However, in some cases these values will overflow/underflow a
641          * QInt/int64 container, thus we should assume these are to be handled
642          * as QFloats/doubles rather than silently changing their values.
643          *
644          * strtoll() indicates these instances by setting errno to ERANGE
645          */
646         int64_t value;
647
648         errno = 0; /* strtoll doesn't set errno on success */
649         value = strtoll(token_get_value(token), NULL, 10);
650         if (errno != ERANGE) {
651             obj = QOBJECT(qint_from_int(value));
652             break;
653         }
654         /* fall through to JSON_FLOAT */
655     }
656     case JSON_FLOAT:
657         /* FIXME dependent on locale */
658         obj = QOBJECT(qfloat_from_double(strtod(token_get_value(token), NULL)));
659         break;
660     default:
661         goto out;
662     }
663
664     return obj;
665
666 out:
667     parser_context_restore(ctxt, saved_ctxt);
668
669     return NULL;
670 }
671
672 static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
673 {
674     QObject *obj;
675
676     obj = parse_object(ctxt, ap);
677     if (obj == NULL) {
678         obj = parse_array(ctxt, ap);
679     }
680     if (obj == NULL) {
681         obj = parse_escape(ctxt, ap);
682     }
683     if (obj == NULL) {
684         obj = parse_keyword(ctxt);
685     } 
686     if (obj == NULL) {
687         obj = parse_literal(ctxt);
688     }
689
690     return obj;
691 }
692
693 QObject *json_parser_parse(QList *tokens, va_list *ap)
694 {
695     return json_parser_parse_err(tokens, ap, NULL);
696 }
697
698 QObject *json_parser_parse_err(QList *tokens, va_list *ap, Error **errp)
699 {
700     JSONParserContext *ctxt = parser_context_new(tokens);
701     QObject *result;
702
703     if (!ctxt) {
704         return NULL;
705     }
706
707     result = parse_value(ctxt, ap);
708
709     error_propagate(errp, ctxt->err);
710
711     parser_context_free(ctxt);
712
713     return result;
714 }