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