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 "qemu/osdep.h"
  15 #include "qemu/ctype.h"
  16 #include "qemu/cutils.h"
  17 #include "qemu/unicode.h"
  18 #include "qapi/error.h"
  19 #include "qapi/qmp/qbool.h"
  20 #include "qapi/qmp/qdict.h"
  21 #include "qapi/qmp/qlist.h"
  22 #include "qapi/qmp/qnull.h"
  23 #include "qapi/qmp/qnum.h"
  24 #include "qapi/qmp/qstring.h"
  25 #include "json-parser-int.h"
  26
  27 struct JSONToken {
  28     JSONTokenType type;
  29     int x;
  30     int y;
  31     char str[];
  32 };
  33
  34 typedef struct JSONParserContext {
  35     Error *err;
  36     JSONToken *current;
  37     GQueue *buf;
  38     va_list *ap;
  39 } JSONParserContext;
  40
  41 #define BUG_ON(cond) assert(!(cond))
  42
  43 /**
  44  * TODO
  45  *
  46  * 0) make errors meaningful again
  47  * 1) add geometry information to tokens
  48  * 3) should we return a parsed size?
  49  * 4) deal with premature EOI
  50  */
  51
  52 static QObject *parse_value(JSONParserContext *ctxt);
  53
  54 /**
  55  * Error handler
  56  */
  57 static void GCC_FMT_ATTR(3, 4) parse_error(JSONParserContext *ctxt,
  58                                            JSONToken *token, const char *msg, ...)
  59 {
  60     va_list ap;
  61     char message[1024];
  62
  63     if (ctxt->err) {
  64         return;
  65     }
  66     va_start(ap, msg);
  67     vsnprintf(message, sizeof(message), msg, ap);
  68     va_end(ap);
  69     error_setg(&ctxt->err, "JSON parse error, %s", message);
  70 }
  71
  72 static int cvt4hex(const char *s)
  73 {
  74     int cp, i;
  75
  76     cp = 0;
  77     for (i = 0; i < 4; i++) {
  78         if (!qemu_isxdigit(s[i])) {
  79             return -1;
  80         }
  81         cp <<= 4;
  82         if (s[i] >= '0' && s[i] <= '9') {
  83             cp |= s[i] - '0';
  84         } else if (s[i] >= 'a' && s[i] <= 'f') {
  85             cp |= 10 + s[i] - 'a';
  86         } else if (s[i] >= 'A' && s[i] <= 'F') {
  87             cp |= 10 + s[i] - 'A';
  88         } else {
  89             return -1;
  90         }
  91     }
  92     return cp;
  93 }
  94
  95 /**
  96  * parse_string(): Parse a JSON string
  97  *
  98  * From RFC 8259 "The JavaScript Object Notation (JSON) Data
  99  * Interchange Format":
 100  *
 101  *    char = unescaped /
 102  *        escape (
 103  *            %x22 /          ; "    quotation mark  U+0022
 104  *            %x5C /          ; \    reverse solidus U+005C
 105  *            %x2F /          ; /    solidus         U+002F
 106  *            %x62 /          ; b    backspace       U+0008
 107  *            %x66 /          ; f    form feed       U+000C
 108  *            %x6E /          ; n    line feed       U+000A
 109  *            %x72 /          ; r    carriage return U+000D
 110  *            %x74 /          ; t    tab             U+0009
 111  *            %x75 4HEXDIG )  ; uXXXX                U+XXXX
 112  *    escape = %x5C              ; \
 113  *    quotation-mark = %x22      ; "
 114  *    unescaped = %x20-21 / %x23-5B / %x5D-10FFFF
 115  *
 116  * Extensions over RFC 8259:
 117  * - Extra escape sequence in strings:
 118  *   0x27 (apostrophe) is recognized after escape, too
 119  * - Single-quoted strings:
 120  *   Like double-quoted strings, except they're delimited by %x27
 121  *   (apostrophe) instead of %x22 (quotation mark), and can't contain
 122  *   unescaped apostrophe, but can contain unescaped quotation mark.
 123  *
 124  * Note:
 125  * - Encoding is modified UTF-8.
 126  * - Invalid Unicode characters are rejected.
 127  * - Control characters \x00..\x1F are rejected by the lexer.
 128  */
 129 static QString *parse_string(JSONParserContext *ctxt, JSONToken *token)
 130 {
 131     const char *ptr = token->str;
 132     GString *str;
 133     char quote;
 134     const char *beg;
 135     int cp, trailing;
 136     char *end;
 137     ssize_t len;
 138     char utf8_buf[5];
 139
 140     assert(*ptr == '"' || *ptr == '\'');
 141     quote = *ptr++;
 142     str = g_string_new(NULL);
 143
 144     while (*ptr != quote) {
 145         assert(*ptr);
 146         switch (*ptr) {
 147         case '\\':
 148             beg = ptr++;
 149             switch (*ptr++) {
 150             case '"':
 151                 g_string_append_c(str, '"');
 152                 break;
 153             case '\'':
 154                 g_string_append_c(str, '\'');
 155                 break;
 156             case '\\':
 157                 g_string_append_c(str, '\\');
 158                 break;
 159             case '/':
 160                 g_string_append_c(str, '/');
 161                 break;
 162             case 'b':
 163                 g_string_append_c(str, '\b');
 164                 break;
 165             case 'f':
 166                 g_string_append_c(str, '\f');
 167                 break;
 168             case 'n':
 169                 g_string_append_c(str, '\n');
 170                 break;
 171             case 'r':
 172                 g_string_append_c(str, '\r');
 173                 break;
 174             case 't':
 175                 g_string_append_c(str, '\t');
 176                 break;
 177             case 'u':
 178                 cp = cvt4hex(ptr);
 179                 ptr += 4;
 180
 181                 /* handle surrogate pairs */
 182                 if (cp >= 0xD800 && cp <= 0xDBFF
 183                     && ptr[0] == '\\' && ptr[1] == 'u') {
 184                     /* leading surrogate followed by \u */
 185                     cp = 0x10000 + ((cp & 0x3FF) << 10);
 186                     trailing = cvt4hex(ptr + 2);
 187                     if (trailing >= 0xDC00 && trailing <= 0xDFFF) {
 188                         /* followed by trailing surrogate */
 189                         cp |= trailing & 0x3FF;
 190                         ptr += 6;
 191                     } else {
 192                         cp = -1; /* invalid */
 193                     }
 194                 }
 195
 196                 if (mod_utf8_encode(utf8_buf, sizeof(utf8_buf), cp) < 0) {
 197                     parse_error(ctxt, token,
 198                                 "%.*s is not a valid Unicode character",
 199                                 (int)(ptr - beg), beg);
 200                     goto out;
 201                 }
 202                 g_string_append(str, utf8_buf);
 203                 break;
 204             default:
 205                 parse_error(ctxt, token, "invalid escape sequence in string");
 206                 goto out;
 207             }
 208             break;
 209         case '%':
 210             if (ctxt->ap) {
 211                 if (ptr[1] != '%') {
 212                     parse_error(ctxt, token, "can't interpolate into string");
 213                     goto out;
 214                 }
 215                 ptr++;
 216             }
 217             /* fall through */
 218         default:
 219             cp = mod_utf8_codepoint(ptr, 6, &end);
 220             if (cp < 0) {
 221                 parse_error(ctxt, token, "invalid UTF-8 sequence in string");
 222                 goto out;
 223             }
 224             ptr = end;
 225             len = mod_utf8_encode(utf8_buf, sizeof(utf8_buf), cp);
 226             assert(len >= 0);
 227             g_string_append(str, utf8_buf);
 228         }
 229     }
 230
 231     return qstring_from_gstring(str);
 232
 233 out:
 234     g_string_free(str, true);
 235     return NULL;
 236 }
 237
 238 /* Note: the token object returned by parser_context_peek_token or
 239  * parser_context_pop_token is deleted as soon as parser_context_pop_token
 240  * is called again.
 241  */
 242 static JSONToken *parser_context_pop_token(JSONParserContext *ctxt)
 243 {
 244     g_free(ctxt->current);
 245     ctxt->current = g_queue_pop_head(ctxt->buf);
 246     return ctxt->current;
 247 }
 248
 249 static JSONToken *parser_context_peek_token(JSONParserContext *ctxt)
 250 {
 251     return g_queue_peek_head(ctxt->buf);
 252 }
 253
 254 /**
 255  * Parsing rules
 256  */
 257 static int parse_pair(JSONParserContext *ctxt, QDict *dict)
 258 {
 259     QObject *key_obj = NULL;
 260     QString *key;
 261     QObject *value;
 262     JSONToken *peek, *token;
 263
 264     peek = parser_context_peek_token(ctxt);
 265     if (peek == NULL) {
 266         parse_error(ctxt, NULL, "premature EOI");
 267         goto out;
 268     }
 269
 270     key_obj = parse_value(ctxt);
 271     key = qobject_to(QString, key_obj);
 272     if (!key) {
 273         parse_error(ctxt, peek, "key is not a string in object");
 274         goto out;
 275     }
 276
 277     token = parser_context_pop_token(ctxt);
 278     if (token == NULL) {
 279         parse_error(ctxt, NULL, "premature EOI");
 280         goto out;
 281     }
 282
 283     if (token->type != JSON_COLON) {
 284         parse_error(ctxt, token, "missing : in object pair");
 285         goto out;
 286     }
 287
 288     value = parse_value(ctxt);
 289     if (value == NULL) {
 290         parse_error(ctxt, token, "Missing value in dict");
 291         goto out;
 292     }
 293
 294     if (qdict_haskey(dict, qstring_get_str(key))) {
 295         parse_error(ctxt, token, "duplicate key");
 296         goto out;
 297     }
 298
 299     qdict_put_obj(dict, qstring_get_str(key), value);
 300
 301     qobject_unref(key_obj);
 302     return 0;
 303
 304 out:
 305     qobject_unref(key_obj);
 306     return -1;
 307 }
 308
 309 static QObject *parse_object(JSONParserContext *ctxt)
 310 {
 311     QDict *dict = NULL;
 312     JSONToken *token, *peek;
 313
 314     token = parser_context_pop_token(ctxt);
 315     assert(token && token->type == JSON_LCURLY);
 316
 317     dict = qdict_new();
 318
 319     peek = parser_context_peek_token(ctxt);
 320     if (peek == NULL) {
 321         parse_error(ctxt, NULL, "premature EOI");
 322         goto out;
 323     }
 324
 325     if (peek->type != JSON_RCURLY) {
 326         if (parse_pair(ctxt, dict) == -1) {
 327             goto out;
 328         }
 329
 330         token = parser_context_pop_token(ctxt);
 331         if (token == NULL) {
 332             parse_error(ctxt, NULL, "premature EOI");
 333             goto out;
 334         }
 335
 336         while (token->type != JSON_RCURLY) {
 337             if (token->type != JSON_COMMA) {
 338                 parse_error(ctxt, token, "expected separator in dict");
 339                 goto out;
 340             }
 341
 342             if (parse_pair(ctxt, dict) == -1) {
 343                 goto out;
 344             }
 345
 346             token = parser_context_pop_token(ctxt);
 347             if (token == NULL) {
 348                 parse_error(ctxt, NULL, "premature EOI");
 349                 goto out;
 350             }
 351         }
 352     } else {
 353         (void)parser_context_pop_token(ctxt);
 354     }
 355
 356     return QOBJECT(dict);
 357
 358 out:
 359     qobject_unref(dict);
 360     return NULL;
 361 }
 362
 363 static QObject *parse_array(JSONParserContext *ctxt)
 364 {
 365     QList *list = NULL;
 366     JSONToken *token, *peek;
 367
 368     token = parser_context_pop_token(ctxt);
 369     assert(token && token->type == JSON_LSQUARE);
 370
 371     list = qlist_new();
 372
 373     peek = parser_context_peek_token(ctxt);
 374     if (peek == NULL) {
 375         parse_error(ctxt, NULL, "premature EOI");
 376         goto out;
 377     }
 378
 379     if (peek->type != JSON_RSQUARE) {
 380         QObject *obj;
 381
 382         obj = parse_value(ctxt);
 383         if (obj == NULL) {
 384             parse_error(ctxt, token, "expecting value");
 385             goto out;
 386         }
 387
 388         qlist_append_obj(list, obj);
 389
 390         token = parser_context_pop_token(ctxt);
 391         if (token == NULL) {
 392             parse_error(ctxt, NULL, "premature EOI");
 393             goto out;
 394         }
 395
 396         while (token->type != JSON_RSQUARE) {
 397             if (token->type != JSON_COMMA) {
 398                 parse_error(ctxt, token, "expected separator in list");
 399                 goto out;
 400             }
 401
 402             obj = parse_value(ctxt);
 403             if (obj == NULL) {
 404                 parse_error(ctxt, token, "expecting value");
 405                 goto out;
 406             }
 407
 408             qlist_append_obj(list, obj);
 409
 410             token = parser_context_pop_token(ctxt);
 411             if (token == NULL) {
 412                 parse_error(ctxt, NULL, "premature EOI");
 413                 goto out;
 414             }
 415         }
 416     } else {
 417         (void)parser_context_pop_token(ctxt);
 418     }
 419
 420     return QOBJECT(list);
 421
 422 out:
 423     qobject_unref(list);
 424     return NULL;
 425 }
 426
 427 static QObject *parse_keyword(JSONParserContext *ctxt)
 428 {
 429     JSONToken *token;
 430
 431     token = parser_context_pop_token(ctxt);
 432     assert(token && token->type == JSON_KEYWORD);
 433
 434     if (!strcmp(token->str, "true")) {
 435         return QOBJECT(qbool_from_bool(true));
 436     } else if (!strcmp(token->str, "false")) {
 437         return QOBJECT(qbool_from_bool(false));
 438     } else if (!strcmp(token->str, "null")) {
 439         return QOBJECT(qnull());
 440     }
 441     parse_error(ctxt, token, "invalid keyword '%s'", token->str);
 442     return NULL;
 443 }
 444
 445 static QObject *parse_interpolation(JSONParserContext *ctxt)
 446 {
 447     JSONToken *token;
 448
 449     token = parser_context_pop_token(ctxt);
 450     assert(token && token->type == JSON_INTERP);
 451
 452     if (!strcmp(token->str, "%p")) {
 453         return va_arg(*ctxt->ap, QObject *);
 454     } else if (!strcmp(token->str, "%i")) {
 455         return QOBJECT(qbool_from_bool(va_arg(*ctxt->ap, int)));
 456     } else if (!strcmp(token->str, "%d")) {
 457         return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, int)));
 458     } else if (!strcmp(token->str, "%ld")) {
 459         return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, long)));
 460     } else if (!strcmp(token->str, "%lld")) {
 461         return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, long long)));
 462     } else if (!strcmp(token->str, "%" PRId64)) {
 463         return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, int64_t)));
 464     } else if (!strcmp(token->str, "%u")) {
 465         return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, unsigned int)));
 466     } else if (!strcmp(token->str, "%lu")) {
 467         return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, unsigned long)));
 468     } else if (!strcmp(token->str, "%llu")) {
 469         return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, unsigned long long)));
 470     } else if (!strcmp(token->str, "%" PRIu64)) {
 471         return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, uint64_t)));
 472     } else if (!strcmp(token->str, "%s")) {
 473         return QOBJECT(qstring_from_str(va_arg(*ctxt->ap, const char *)));
 474     } else if (!strcmp(token->str, "%f")) {
 475         return QOBJECT(qnum_from_double(va_arg(*ctxt->ap, double)));
 476     }
 477     parse_error(ctxt, token, "invalid interpolation '%s'", token->str);
 478     return NULL;
 479 }
 480
 481 static QObject *parse_literal(JSONParserContext *ctxt)
 482 {
 483     JSONToken *token;
 484
 485     token = parser_context_pop_token(ctxt);
 486     assert(token);
 487
 488     switch (token->type) {
 489     case JSON_STRING:
 490         return QOBJECT(parse_string(ctxt, token));
 491     case JSON_INTEGER: {
 492         /*
 493          * Represent JSON_INTEGER as QNUM_I64 if possible, else as
 494          * QNUM_U64, else as QNUM_DOUBLE.  Note that qemu_strtoi64()
 495          * and qemu_strtou64() fail with ERANGE when it's not
 496          * possible.
 497          *
 498          * qnum_get_int() will then work for any signed 64-bit
 499          * JSON_INTEGER, qnum_get_uint() for any unsigned 64-bit
 500          * integer, and qnum_get_double() both for any JSON_INTEGER
 501          * and any JSON_FLOAT (with precision loss for integers beyond
 502          * 53 bits)
 503          */
 504         int ret;
 505         int64_t value;
 506         uint64_t uvalue;
 507
 508         ret = qemu_strtoi64(token->str, NULL, 10, &value);
 509         if (!ret) {
 510             return QOBJECT(qnum_from_int(value));
 511         }
 512         assert(ret == -ERANGE);
 513
 514         if (token->str[0] != '-') {
 515             ret = qemu_strtou64(token->str, NULL, 10, &uvalue);
 516             if (!ret) {
 517                 return QOBJECT(qnum_from_uint(uvalue));
 518             }
 519             assert(ret == -ERANGE);
 520         }
 521     }
 522     /* fall through to JSON_FLOAT */
 523     case JSON_FLOAT:
 524         /* FIXME dependent on locale; a pervasive issue in QEMU */
 525         /* FIXME our lexer matches RFC 8259 in forbidding Inf or NaN,
 526          * but those might be useful extensions beyond JSON */
 527         return QOBJECT(qnum_from_double(strtod(token->str, NULL)));
 528     default:
 529         abort();
 530     }
 531 }
 532
 533 static QObject *parse_value(JSONParserContext *ctxt)
 534 {
 535     JSONToken *token;
 536
 537     token = parser_context_peek_token(ctxt);
 538     if (token == NULL) {
 539         parse_error(ctxt, NULL, "premature EOI");
 540         return NULL;
 541     }
 542
 543     switch (token->type) {
 544     case JSON_LCURLY:
 545         return parse_object(ctxt);
 546     case JSON_LSQUARE:
 547         return parse_array(ctxt);
 548     case JSON_INTERP:
 549         return parse_interpolation(ctxt);
 550     case JSON_INTEGER:
 551     case JSON_FLOAT:
 552     case JSON_STRING:
 553         return parse_literal(ctxt);
 554     case JSON_KEYWORD:
 555         return parse_keyword(ctxt);
 556     default:
 557         parse_error(ctxt, token, "expecting value");
 558         return NULL;
 559     }
 560 }
 561
 562 JSONToken *json_token(JSONTokenType type, int x, int y, GString *tokstr)
 563 {
 564     JSONToken *token = g_malloc(sizeof(JSONToken) + tokstr->len + 1);
 565
 566     token->type = type;
 567     memcpy(token->str, tokstr->str, tokstr->len);
 568     token->str[tokstr->len] = 0;
 569     token->x = x;
 570     token->y = y;
 571     return token;
 572 }
 573
 574 QObject *json_parser_parse(GQueue *tokens, va_list *ap, Error **errp)
 575 {
 576     JSONParserContext ctxt = { .buf = tokens, .ap = ap };
 577     QObject *result;
 578
 579     result = parse_value(&ctxt);
 580     assert(ctxt.err || g_queue_is_empty(ctxt.buf));
 581
 582     error_propagate(errp, ctxt.err);
 583
 584     while (!g_queue_is_empty(ctxt.buf)) {
 585         parser_context_pop_token(&ctxt);
 586     }
 587     g_free(ctxt.current);
 588
 589     return result;
 590 }