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/cutils.h"
  16 #include "qemu/unicode.h"
  17 #include "qapi/error.h"
  18 #include "qemu-common.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 } 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, va_list *ap);
  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     QString *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 = qstring_new();
 143
 144     while (*ptr != quote) {
 145         assert(*ptr);
 146         if (*ptr == '\\') {
 147             beg = ptr++;
 148             switch (*ptr++) {
 149             case '"':
 150                 qstring_append_chr(str, '"');
 151                 break;
 152             case '\'':
 153                 qstring_append_chr(str, '\'');
 154                 break;
 155             case '\\':
 156                 qstring_append_chr(str, '\\');
 157                 break;
 158             case '/':
 159                 qstring_append_chr(str, '/');
 160                 break;
 161             case 'b':
 162                 qstring_append_chr(str, '\b');
 163                 break;
 164             case 'f':
 165                 qstring_append_chr(str, '\f');
 166                 break;
 167             case 'n':
 168                 qstring_append_chr(str, '\n');
 169                 break;
 170             case 'r':
 171                 qstring_append_chr(str, '\r');
 172                 break;
 173             case 't':
 174                 qstring_append_chr(str, '\t');
 175                 break;
 176             case 'u':
 177                 cp = cvt4hex(ptr);
 178                 ptr += 4;
 179
 180                 /* handle surrogate pairs */
 181                 if (cp >= 0xD800 && cp <= 0xDBFF
 182                     && ptr[0] == '\\' && ptr[1] == 'u') {
 183                     /* leading surrogate followed by \u */
 184                     cp = 0x10000 + ((cp & 0x3FF) << 10);
 185                     trailing = cvt4hex(ptr + 2);
 186                     if (trailing >= 0xDC00 && trailing <= 0xDFFF) {
 187                         /* followed by trailing surrogate */
 188                         cp |= trailing & 0x3FF;
 189                         ptr += 6;
 190                     } else {
 191                         cp = -1; /* invalid */
 192                     }
 193                 }
 194
 195                 if (mod_utf8_encode(utf8_buf, sizeof(utf8_buf), cp) < 0) {
 196                     parse_error(ctxt, token,
 197                                 "%.*s is not a valid Unicode character",
 198                                 (int)(ptr - beg), beg);
 199                     goto out;
 200                 }
 201                 qstring_append(str, utf8_buf);
 202                 break;
 203             default:
 204                 parse_error(ctxt, token, "invalid escape sequence in string");
 205                 goto out;
 206             }
 207         } else {
 208             cp = mod_utf8_codepoint(ptr, 6, &end);
 209             if (cp < 0) {
 210                 parse_error(ctxt, token, "invalid UTF-8 sequence in string");
 211                 goto out;
 212             }
 213             ptr = end;
 214             len = mod_utf8_encode(utf8_buf, sizeof(utf8_buf), cp);
 215             assert(len >= 0);
 216             qstring_append(str, utf8_buf);
 217         }
 218     }
 219
 220     return str;
 221
 222 out:
 223     qobject_unref(str);
 224     return NULL;
 225 }
 226
 227 /* Note: the token object returned by parser_context_peek_token or
 228  * parser_context_pop_token is deleted as soon as parser_context_pop_token
 229  * is called again.
 230  */
 231 static JSONToken *parser_context_pop_token(JSONParserContext *ctxt)
 232 {
 233     g_free(ctxt->current);
 234     ctxt->current = g_queue_pop_head(ctxt->buf);
 235     return ctxt->current;
 236 }
 237
 238 static JSONToken *parser_context_peek_token(JSONParserContext *ctxt)
 239 {
 240     return g_queue_peek_head(ctxt->buf);
 241 }
 242
 243 /**
 244  * Parsing rules
 245  */
 246 static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
 247 {
 248     QObject *value;
 249     QString *key = NULL;
 250     JSONToken *peek, *token;
 251
 252     peek = parser_context_peek_token(ctxt);
 253     if (peek == NULL) {
 254         parse_error(ctxt, NULL, "premature EOI");
 255         goto out;
 256     }
 257
 258     key = qobject_to(QString, parse_value(ctxt, ap));
 259     if (!key) {
 260         parse_error(ctxt, peek, "key is not a string in object");
 261         goto out;
 262     }
 263
 264     token = parser_context_pop_token(ctxt);
 265     if (token == NULL) {
 266         parse_error(ctxt, NULL, "premature EOI");
 267         goto out;
 268     }
 269
 270     if (token->type != JSON_COLON) {
 271         parse_error(ctxt, token, "missing : in object pair");
 272         goto out;
 273     }
 274
 275     value = parse_value(ctxt, ap);
 276     if (value == NULL) {
 277         parse_error(ctxt, token, "Missing value in dict");
 278         goto out;
 279     }
 280
 281     qdict_put_obj(dict, qstring_get_str(key), value);
 282
 283     qobject_unref(key);
 284
 285     return 0;
 286
 287 out:
 288     qobject_unref(key);
 289
 290     return -1;
 291 }
 292
 293 static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
 294 {
 295     QDict *dict = NULL;
 296     JSONToken *token, *peek;
 297
 298     token = parser_context_pop_token(ctxt);
 299     assert(token && token->type == JSON_LCURLY);
 300
 301     dict = qdict_new();
 302
 303     peek = parser_context_peek_token(ctxt);
 304     if (peek == NULL) {
 305         parse_error(ctxt, NULL, "premature EOI");
 306         goto out;
 307     }
 308
 309     if (peek->type != JSON_RCURLY) {
 310         if (parse_pair(ctxt, dict, ap) == -1) {
 311             goto out;
 312         }
 313
 314         token = parser_context_pop_token(ctxt);
 315         if (token == NULL) {
 316             parse_error(ctxt, NULL, "premature EOI");
 317             goto out;
 318         }
 319
 320         while (token->type != JSON_RCURLY) {
 321             if (token->type != JSON_COMMA) {
 322                 parse_error(ctxt, token, "expected separator in dict");
 323                 goto out;
 324             }
 325
 326             if (parse_pair(ctxt, dict, ap) == -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     } else {
 337         (void)parser_context_pop_token(ctxt);
 338     }
 339
 340     return QOBJECT(dict);
 341
 342 out:
 343     qobject_unref(dict);
 344     return NULL;
 345 }
 346
 347 static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
 348 {
 349     QList *list = NULL;
 350     JSONToken *token, *peek;
 351
 352     token = parser_context_pop_token(ctxt);
 353     assert(token && token->type == JSON_LSQUARE);
 354
 355     list = qlist_new();
 356
 357     peek = parser_context_peek_token(ctxt);
 358     if (peek == NULL) {
 359         parse_error(ctxt, NULL, "premature EOI");
 360         goto out;
 361     }
 362
 363     if (peek->type != JSON_RSQUARE) {
 364         QObject *obj;
 365
 366         obj = parse_value(ctxt, ap);
 367         if (obj == NULL) {
 368             parse_error(ctxt, token, "expecting value");
 369             goto out;
 370         }
 371
 372         qlist_append_obj(list, obj);
 373
 374         token = parser_context_pop_token(ctxt);
 375         if (token == NULL) {
 376             parse_error(ctxt, NULL, "premature EOI");
 377             goto out;
 378         }
 379
 380         while (token->type != JSON_RSQUARE) {
 381             if (token->type != JSON_COMMA) {
 382                 parse_error(ctxt, token, "expected separator in list");
 383                 goto out;
 384             }
 385
 386             obj = parse_value(ctxt, ap);
 387             if (obj == NULL) {
 388                 parse_error(ctxt, token, "expecting value");
 389                 goto out;
 390             }
 391
 392             qlist_append_obj(list, obj);
 393
 394             token = parser_context_pop_token(ctxt);
 395             if (token == NULL) {
 396                 parse_error(ctxt, NULL, "premature EOI");
 397                 goto out;
 398             }
 399         }
 400     } else {
 401         (void)parser_context_pop_token(ctxt);
 402     }
 403
 404     return QOBJECT(list);
 405
 406 out:
 407     qobject_unref(list);
 408     return NULL;
 409 }
 410
 411 static QObject *parse_keyword(JSONParserContext *ctxt)
 412 {
 413     JSONToken *token;
 414
 415     token = parser_context_pop_token(ctxt);
 416     assert(token && token->type == JSON_KEYWORD);
 417
 418     if (!strcmp(token->str, "true")) {
 419         return QOBJECT(qbool_from_bool(true));
 420     } else if (!strcmp(token->str, "false")) {
 421         return QOBJECT(qbool_from_bool(false));
 422     } else if (!strcmp(token->str, "null")) {
 423         return QOBJECT(qnull());
 424     }
 425     parse_error(ctxt, token, "invalid keyword '%s'", token->str);
 426     return NULL;
 427 }
 428
 429 static QObject *parse_interpolation(JSONParserContext *ctxt, va_list *ap)
 430 {
 431     JSONToken *token;
 432
 433     token = parser_context_pop_token(ctxt);
 434     assert(token && token->type == JSON_INTERP);
 435
 436     if (!strcmp(token->str, "%p")) {
 437         return va_arg(*ap, QObject *);
 438     } else if (!strcmp(token->str, "%i")) {
 439         return QOBJECT(qbool_from_bool(va_arg(*ap, int)));
 440     } else if (!strcmp(token->str, "%d")) {
 441         return QOBJECT(qnum_from_int(va_arg(*ap, int)));
 442     } else if (!strcmp(token->str, "%ld")) {
 443         return QOBJECT(qnum_from_int(va_arg(*ap, long)));
 444     } else if (!strcmp(token->str, "%lld")) {
 445         return QOBJECT(qnum_from_int(va_arg(*ap, long long)));
 446     } else if (!strcmp(token->str, "%" PRId64)) {
 447         return QOBJECT(qnum_from_int(va_arg(*ap, int64_t)));
 448     } else if (!strcmp(token->str, "%u")) {
 449         return QOBJECT(qnum_from_uint(va_arg(*ap, unsigned int)));
 450     } else if (!strcmp(token->str, "%lu")) {
 451         return QOBJECT(qnum_from_uint(va_arg(*ap, unsigned long)));
 452     } else if (!strcmp(token->str, "%llu")) {
 453         return QOBJECT(qnum_from_uint(va_arg(*ap, unsigned long long)));
 454     } else if (!strcmp(token->str, "%" PRIu64)) {
 455         return QOBJECT(qnum_from_uint(va_arg(*ap, uint64_t)));
 456     } else if (!strcmp(token->str, "%s")) {
 457         return QOBJECT(qstring_from_str(va_arg(*ap, const char *)));
 458     } else if (!strcmp(token->str, "%f")) {
 459         return QOBJECT(qnum_from_double(va_arg(*ap, double)));
 460     }
 461     parse_error(ctxt, token, "invalid interpolation '%s'", token->str);
 462     return NULL;
 463 }
 464
 465 static QObject *parse_literal(JSONParserContext *ctxt)
 466 {
 467     JSONToken *token;
 468
 469     token = parser_context_pop_token(ctxt);
 470     assert(token);
 471
 472     switch (token->type) {
 473     case JSON_STRING:
 474         return QOBJECT(parse_string(ctxt, token));
 475     case JSON_INTEGER: {
 476         /*
 477          * Represent JSON_INTEGER as QNUM_I64 if possible, else as
 478          * QNUM_U64, else as QNUM_DOUBLE.  Note that qemu_strtoi64()
 479          * and qemu_strtou64() fail with ERANGE when it's not
 480          * possible.
 481          *
 482          * qnum_get_int() will then work for any signed 64-bit
 483          * JSON_INTEGER, qnum_get_uint() for any unsigned 64-bit
 484          * integer, and qnum_get_double() both for any JSON_INTEGER
 485          * and any JSON_FLOAT (with precision loss for integers beyond
 486          * 53 bits)
 487          */
 488         int ret;
 489         int64_t value;
 490         uint64_t uvalue;
 491
 492         ret = qemu_strtoi64(token->str, NULL, 10, &value);
 493         if (!ret) {
 494             return QOBJECT(qnum_from_int(value));
 495         }
 496         assert(ret == -ERANGE);
 497
 498         if (token->str[0] != '-') {
 499             ret = qemu_strtou64(token->str, NULL, 10, &uvalue);
 500             if (!ret) {
 501                 return QOBJECT(qnum_from_uint(uvalue));
 502             }
 503             assert(ret == -ERANGE);
 504         }
 505         /* fall through to JSON_FLOAT */
 506     }
 507     case JSON_FLOAT:
 508         /* FIXME dependent on locale; a pervasive issue in QEMU */
 509         /* FIXME our lexer matches RFC 7159 in forbidding Inf or NaN,
 510          * but those might be useful extensions beyond JSON */
 511         return QOBJECT(qnum_from_double(strtod(token->str, NULL)));
 512     default:
 513         abort();
 514     }
 515 }
 516
 517 static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
 518 {
 519     JSONToken *token;
 520
 521     token = parser_context_peek_token(ctxt);
 522     if (token == NULL) {
 523         parse_error(ctxt, NULL, "premature EOI");
 524         return NULL;
 525     }
 526
 527     switch (token->type) {
 528     case JSON_LCURLY:
 529         return parse_object(ctxt, ap);
 530     case JSON_LSQUARE:
 531         return parse_array(ctxt, ap);
 532     case JSON_INTERP:
 533         return parse_interpolation(ctxt, ap);
 534     case JSON_INTEGER:
 535     case JSON_FLOAT:
 536     case JSON_STRING:
 537         return parse_literal(ctxt);
 538     case JSON_KEYWORD:
 539         return parse_keyword(ctxt);
 540     default:
 541         parse_error(ctxt, token, "expecting value");
 542         return NULL;
 543     }
 544 }
 545
 546 JSONToken *json_token(JSONTokenType type, int x, int y, GString *tokstr)
 547 {
 548     JSONToken *token = g_malloc(sizeof(JSONToken) + tokstr->len + 1);
 549
 550     token->type = type;
 551     memcpy(token->str, tokstr->str, tokstr->len);
 552     token->str[tokstr->len] = 0;
 553     token->x = x;
 554     token->y = y;
 555     return token;
 556 }
 557
 558 QObject *json_parser_parse(GQueue *tokens, va_list *ap, Error **errp)
 559 {
 560     JSONParserContext ctxt = { .buf = tokens };
 561     QObject *result;
 562
 563     result = parse_value(&ctxt, ap);
 564     assert(ctxt.err || g_queue_is_empty(ctxt.buf));
 565
 566     error_propagate(errp, ctxt.err);
 567
 568     while (!g_queue_is_empty(ctxt.buf)) {
 569         parser_context_pop_token(&ctxt);
 570     }
 571     g_free(ctxt.current);
 572
 573     return result;
 574 }