[mirror_qemu.git] / qobject / json-parser.c

/*
 * JSON Parser
 *
 * Copyright IBM, Corp. 2009
 *
 * Authors:
 *  Anthony Liguori   <aliguori@us.ibm.com>
 *
 * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
 * See the COPYING.LIB file in the top-level directory.
 *
 */

#include "qemu/osdep.h"
#include "qemu/ctype.h"
#include "qemu/cutils.h"
#include "qemu/unicode.h"
#include "qapi/error.h"
#include "qapi/qmp/qbool.h"
#include "qapi/qmp/qdict.h"
#include "qapi/qmp/qlist.h"
#include "qapi/qmp/qnull.h"
#include "qapi/qmp/qnum.h"
#include "qapi/qmp/qstring.h"
#include "json-parser-int.h"

struct JSONToken {
    JSONTokenType type;
    int x;
    int y;
    char str[];
};

typedef struct JSONParserContext {
    Error *err;
    JSONToken *current;
    GQueue *buf;
    va_list *ap;
} JSONParserContext;

#define BUG_ON(cond) assert(!(cond))

/**
 * TODO
 *
 * 0) make errors meaningful again
 * 1) add geometry information to tokens
 * 3) should we return a parsed size?
 * 4) deal with premature EOI
 */

static QObject *parse_value(JSONParserContext *ctxt);

/**
 * Error handler
 */
static void G_GNUC_PRINTF(3, 4) parse_error(JSONParserContext *ctxt,
                                           JSONToken *token, const char *msg, ...)
{
    va_list ap;
    char message[1024];

    if (ctxt->err) {
        return;
    }
    va_start(ap, msg);
    vsnprintf(message, sizeof(message), msg, ap);
    va_end(ap);
    error_setg(&ctxt->err, "JSON parse error, %s", message);
}

static int cvt4hex(const char *s)
{
    int cp, i;

    cp = 0;
    for (i = 0; i < 4; i++) {
        if (!qemu_isxdigit(s[i])) {
            return -1;
        }
        cp <<= 4;
        if (s[i] >= '0' && s[i] <= '9') {
            cp |= s[i] - '0';
        } else if (s[i] >= 'a' && s[i] <= 'f') {
            cp |= 10 + s[i] - 'a';
        } else if (s[i] >= 'A' && s[i] <= 'F') {
            cp |= 10 + s[i] - 'A';
        } else {
            return -1;
        }
    }
    return cp;
}

/**
 * parse_string(): Parse a JSON string
 *
 * From RFC 8259 "The JavaScript Object Notation (JSON) Data
 * Interchange Format":
 *
 *    char = unescaped /
 *        escape (
 *            %x22 /          ; "    quotation mark  U+0022
 *            %x5C /          ; \    reverse solidus U+005C
 *            %x2F /          ; /    solidus         U+002F
 *            %x62 /          ; b    backspace       U+0008
 *            %x66 /          ; f    form feed       U+000C
 *            %x6E /          ; n    line feed       U+000A
 *            %x72 /          ; r    carriage return U+000D
 *            %x74 /          ; t    tab             U+0009
 *            %x75 4HEXDIG )  ; uXXXX                U+XXXX
 *    escape = %x5C              ; \
 *    quotation-mark = %x22      ; "
 *    unescaped = %x20-21 / %x23-5B / %x5D-10FFFF
 *
 * Extensions over RFC 8259:
 * - Extra escape sequence in strings:
 *   0x27 (apostrophe) is recognized after escape, too
 * - Single-quoted strings:
 *   Like double-quoted strings, except they're delimited by %x27
 *   (apostrophe) instead of %x22 (quotation mark), and can't contain
 *   unescaped apostrophe, but can contain unescaped quotation mark.
 *
 * Note:
 * - Encoding is modified UTF-8.
 * - Invalid Unicode characters are rejected.
 * - Control characters \x00..\x1F are rejected by the lexer.
 */
static QString *parse_string(JSONParserContext *ctxt, JSONToken *token)
{
    const char *ptr = token->str;
    GString *str;
    char quote;
    const char *beg;
    int cp, trailing;
    char *end;
    ssize_t len;
    char utf8_buf[5];

    assert(*ptr == '"' || *ptr == '\'');
    quote = *ptr++;
    str = g_string_new(NULL);

    while (*ptr != quote) {
        assert(*ptr);
        switch (*ptr) {
        case '\\':
            beg = ptr++;
            switch (*ptr++) {
            case '"':
                g_string_append_c(str, '"');
                break;
            case '\'':
                g_string_append_c(str, '\'');
                break;
            case '\\':
                g_string_append_c(str, '\\');
                break;
            case '/':
                g_string_append_c(str, '/');
                break;
            case 'b':
                g_string_append_c(str, '\b');
                break;
            case 'f':
                g_string_append_c(str, '\f');
                break;
            case 'n':
                g_string_append_c(str, '\n');
                break;
            case 'r':
                g_string_append_c(str, '\r');
                break;
            case 't':
                g_string_append_c(str, '\t');
                break;
            case 'u':
                cp = cvt4hex(ptr);
                ptr += 4;

                /* handle surrogate pairs */
                if (cp >= 0xD800 && cp <= 0xDBFF
                    && ptr[0] == '\\' && ptr[1] == 'u') {
                    /* leading surrogate followed by \u */
                    cp = 0x10000 + ((cp & 0x3FF) << 10);
                    trailing = cvt4hex(ptr + 2);
                    if (trailing >= 0xDC00 && trailing <= 0xDFFF) {
                        /* followed by trailing surrogate */
                        cp |= trailing & 0x3FF;
                        ptr += 6;
                    } else {
                        cp = -1; /* invalid */
                    }
                }

                if (mod_utf8_encode(utf8_buf, sizeof(utf8_buf), cp) < 0) {
                    parse_error(ctxt, token,
                                "%.*s is not a valid Unicode character",
                                (int)(ptr - beg), beg);
                    goto out;
                }
                g_string_append(str, utf8_buf);
                break;
            default:
                parse_error(ctxt, token, "invalid escape sequence in string");
                goto out;
            }
            break;
        case '%':
            if (ctxt->ap) {
                if (ptr[1] != '%') {
                    parse_error(ctxt, token, "can't interpolate into string");
                    goto out;
                }
                ptr++;
            }
            /* fall through */
        default:
            cp = mod_utf8_codepoint(ptr, 6, &end);
            if (cp < 0) {
                parse_error(ctxt, token, "invalid UTF-8 sequence in string");
                goto out;
            }
            ptr = end;
            len = mod_utf8_encode(utf8_buf, sizeof(utf8_buf), cp);
            assert(len >= 0);
            g_string_append(str, utf8_buf);
        }
    }

    return qstring_from_gstring(str);

out:
    g_string_free(str, true);
    return NULL;
}

/* Note: the token object returned by parser_context_peek_token or
 * parser_context_pop_token is deleted as soon as parser_context_pop_token
 * is called again.
 */
static JSONToken *parser_context_pop_token(JSONParserContext *ctxt)
{
    g_free(ctxt->current);
    ctxt->current = g_queue_pop_head(ctxt->buf);
    return ctxt->current;
}

static JSONToken *parser_context_peek_token(JSONParserContext *ctxt)
{
    return g_queue_peek_head(ctxt->buf);
}

/**
 * Parsing rules
 */
static int parse_pair(JSONParserContext *ctxt, QDict *dict)
{
    QObject *key_obj = NULL;
    QString *key;
    QObject *value;
    JSONToken *peek, *token;

    peek = parser_context_peek_token(ctxt);
    if (peek == NULL) {
        parse_error(ctxt, NULL, "premature EOI");
        goto out;
    }

    key_obj = parse_value(ctxt);
    key = qobject_to(QString, key_obj);
    if (!key) {
        parse_error(ctxt, peek, "key is not a string in object");
        goto out;
    }

    token = parser_context_pop_token(ctxt);
    if (token == NULL) {
        parse_error(ctxt, NULL, "premature EOI");
        goto out;
    }

    if (token->type != JSON_COLON) {
        parse_error(ctxt, token, "missing : in object pair");
        goto out;
    }

    value = parse_value(ctxt);
    if (value == NULL) {
        parse_error(ctxt, token, "Missing value in dict");
        goto out;
    }

    if (qdict_haskey(dict, qstring_get_str(key))) {
        parse_error(ctxt, token, "duplicate key");
        goto out;
    }

    qdict_put_obj(dict, qstring_get_str(key), value);

    qobject_unref(key_obj);
    return 0;

out:
    qobject_unref(key_obj);
    return -1;
}

static QObject *parse_object(JSONParserContext *ctxt)
{
    QDict *dict = NULL;
    JSONToken *token, *peek;

    token = parser_context_pop_token(ctxt);
    assert(token && token->type == JSON_LCURLY);

    dict = qdict_new();

    peek = parser_context_peek_token(ctxt);
    if (peek == NULL) {
        parse_error(ctxt, NULL, "premature EOI");
        goto out;
    }

    if (peek->type != JSON_RCURLY) {
        if (parse_pair(ctxt, dict) == -1) {
            goto out;
        }

        token = parser_context_pop_token(ctxt);
        if (token == NULL) {
            parse_error(ctxt, NULL, "premature EOI");
            goto out;
        }

        while (token->type != JSON_RCURLY) {
            if (token->type != JSON_COMMA) {
                parse_error(ctxt, token, "expected separator in dict");
                goto out;
            }

            if (parse_pair(ctxt, dict) == -1) {
                goto out;
            }

            token = parser_context_pop_token(ctxt);
            if (token == NULL) {
                parse_error(ctxt, NULL, "premature EOI");
                goto out;
            }
        }
    } else {
        (void)parser_context_pop_token(ctxt);
    }

    return QOBJECT(dict);

out:
    qobject_unref(dict);
    return NULL;
}

static QObject *parse_array(JSONParserContext *ctxt)
{
    QList *list = NULL;
    JSONToken *token, *peek;

    token = parser_context_pop_token(ctxt);
    assert(token && token->type == JSON_LSQUARE);

    list = qlist_new();

    peek = parser_context_peek_token(ctxt);
    if (peek == NULL) {
        parse_error(ctxt, NULL, "premature EOI");
        goto out;
    }

    if (peek->type != JSON_RSQUARE) {
        QObject *obj;

        obj = parse_value(ctxt);
        if (obj == NULL) {
            parse_error(ctxt, token, "expecting value");
            goto out;
        }

        qlist_append_obj(list, obj);

        token = parser_context_pop_token(ctxt);
        if (token == NULL) {
            parse_error(ctxt, NULL, "premature EOI");
            goto out;
        }

        while (token->type != JSON_RSQUARE) {
            if (token->type != JSON_COMMA) {
                parse_error(ctxt, token, "expected separator in list");
                goto out;
            }

            obj = parse_value(ctxt);
            if (obj == NULL) {
                parse_error(ctxt, token, "expecting value");
                goto out;
            }

            qlist_append_obj(list, obj);

            token = parser_context_pop_token(ctxt);
            if (token == NULL) {
                parse_error(ctxt, NULL, "premature EOI");
                goto out;
            }
        }
    } else {
        (void)parser_context_pop_token(ctxt);
    }

    return QOBJECT(list);

out:
    qobject_unref(list);
    return NULL;
}

static QObject *parse_keyword(JSONParserContext *ctxt)
{
    JSONToken *token;

    token = parser_context_pop_token(ctxt);
    assert(token && token->type == JSON_KEYWORD);

    if (!strcmp(token->str, "true")) {
        return QOBJECT(qbool_from_bool(true));
    } else if (!strcmp(token->str, "false")) {
        return QOBJECT(qbool_from_bool(false));
    } else if (!strcmp(token->str, "null")) {
        return QOBJECT(qnull());
    }
    parse_error(ctxt, token, "invalid keyword '%s'", token->str);
    return NULL;
}

static QObject *parse_interpolation(JSONParserContext *ctxt)
{
    JSONToken *token;

    token = parser_context_pop_token(ctxt);
    assert(token && token->type == JSON_INTERP);

    if (!strcmp(token->str, "%p")) {
        return va_arg(*ctxt->ap, QObject *);
    } else if (!strcmp(token->str, "%i")) {
        return QOBJECT(qbool_from_bool(va_arg(*ctxt->ap, int)));
    } else if (!strcmp(token->str, "%d")) {
        return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, int)));
    } else if (!strcmp(token->str, "%ld")) {
        return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, long)));
    } else if (!strcmp(token->str, "%lld")) {
        return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, long long)));
    } else if (!strcmp(token->str, "%" PRId64)) {
        return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, int64_t)));
    } else if (!strcmp(token->str, "%u")) {
        return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, unsigned int)));
    } else if (!strcmp(token->str, "%lu")) {
        return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, unsigned long)));
    } else if (!strcmp(token->str, "%llu")) {
        return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, unsigned long long)));
    } else if (!strcmp(token->str, "%" PRIu64)) {
        return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, uint64_t)));
    } else if (!strcmp(token->str, "%s")) {
        return QOBJECT(qstring_from_str(va_arg(*ctxt->ap, const char *)));
    } else if (!strcmp(token->str, "%f")) {
        return QOBJECT(qnum_from_double(va_arg(*ctxt->ap, double)));
    }
    parse_error(ctxt, token, "invalid interpolation '%s'", token->str);
    return NULL;
}

static QObject *parse_literal(JSONParserContext *ctxt)
{
    JSONToken *token;

    token = parser_context_pop_token(ctxt);
    assert(token);

    switch (token->type) {
    case JSON_STRING:
        return QOBJECT(parse_string(ctxt, token));
    case JSON_INTEGER: {
        /*
         * Represent JSON_INTEGER as QNUM_I64 if possible, else as
         * QNUM_U64, else as QNUM_DOUBLE.  Note that qemu_strtoi64()
         * and qemu_strtou64() fail with ERANGE when it's not
         * possible.
         *
         * qnum_get_int() will then work for any signed 64-bit
         * JSON_INTEGER, qnum_get_uint() for any unsigned 64-bit
         * integer, and qnum_get_double() both for any JSON_INTEGER
         * and any JSON_FLOAT (with precision loss for integers beyond
         * 53 bits)
         */
        int ret;
        int64_t value;
        uint64_t uvalue;

        ret = qemu_strtoi64(token->str, NULL, 10, &value);
        if (!ret) {
            return QOBJECT(qnum_from_int(value));
        }
        assert(ret == -ERANGE);

        if (token->str[0] != '-') {
            ret = qemu_strtou64(token->str, NULL, 10, &uvalue);
            if (!ret) {
                return QOBJECT(qnum_from_uint(uvalue));
            }
            assert(ret == -ERANGE);
        }
    }
    /* fall through to JSON_FLOAT */
    case JSON_FLOAT:
        /* FIXME dependent on locale; a pervasive issue in QEMU */
        /* FIXME our lexer matches RFC 8259 in forbidding Inf or NaN,
         * but those might be useful extensions beyond JSON */
        return QOBJECT(qnum_from_double(strtod(token->str, NULL)));
    default:
        abort();
    }
}

static QObject *parse_value(JSONParserContext *ctxt)
{
    JSONToken *token;

    token = parser_context_peek_token(ctxt);
    if (token == NULL) {
        parse_error(ctxt, NULL, "premature EOI");
        return NULL;
    }

    switch (token->type) {
    case JSON_LCURLY:
        return parse_object(ctxt);
    case JSON_LSQUARE:
        return parse_array(ctxt);
    case JSON_INTERP:
        return parse_interpolation(ctxt);
    case JSON_INTEGER:
    case JSON_FLOAT:
    case JSON_STRING:
        return parse_literal(ctxt);
    case JSON_KEYWORD:
        return parse_keyword(ctxt);
    default:
        parse_error(ctxt, token, "expecting value");
        return NULL;
    }
}

JSONToken *json_token(JSONTokenType type, int x, int y, GString *tokstr)
{
    JSONToken *token = g_malloc(sizeof(JSONToken) + tokstr->len + 1);

    token->type = type;
    memcpy(token->str, tokstr->str, tokstr->len);
    token->str[tokstr->len] = 0;
    token->x = x;
    token->y = y;
    return token;
}

QObject *json_parser_parse(GQueue *tokens, va_list *ap, Error **errp)
{
    JSONParserContext ctxt = { .buf = tokens, .ap = ap };
    QObject *result;

    result = parse_value(&ctxt);
    assert(ctxt.err || g_queue_is_empty(ctxt.buf));

    error_propagate(errp, ctxt.err);

    while (!g_queue_is_empty(ctxt.buf)) {
        parser_context_pop_token(&ctxt);
    }
    g_free(ctxt.current);

    return result;
}
Commit	Line	Data
4a5fcab7	1	/*
6e8e5cb9	2	* JSON Parser
4a5fcab7 AL	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
f2ad72b3	14	#include "qemu/osdep.h"
856dfd8a	15	#include "qemu/ctype.h"
2bc7cfea	16	#include "qemu/cutils.h"
e59f39d4	17	#include "qemu/unicode.h"
da34e65c	18	#include "qapi/error.h"
6b673957	19	#include "qapi/qmp/qbool.h"
452fcdbc	20	#include "qapi/qmp/qdict.h"
47e6b297	21	#include "qapi/qmp/qlist.h"
15280c36 MA	22	#include "qapi/qmp/qnull.h"
15280c36 MA	23	#include "qapi/qmp/qnum.h"
6b673957	24	#include "qapi/qmp/qstring.h"
86cdf9ec	25	#include "json-parser-int.h"
4a5fcab7	26
abe7c206 MA	27	struct JSONToken {
	28	JSONTokenType type;
	29	int x;
	30	int y;
	31	char str[];
	32	};
	33
5086c997	34	typedef struct JSONParserContext {
ef749d07	35	Error *err;
9bada897	36	JSONToken *current;
95385fe9	37	GQueue *buf;
ada74c3b	38	va_list *ap;
4a5fcab7 AL	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
ada74c3b	52	static QObject parse_value(JSONParserContext ctxt);
4a5fcab7	53
4a5fcab7 AL	54	/**
	55	* Error handler
	56	*/
9edc6313	57	static void G_GNUC_PRINTF(3, 4) parse_error(JSONParserContext *ctxt,
9bada897	58	JSONToken token, const char msg, ...)
4a5fcab7	59	{
c96c84a9	60	va_list ap;
ef749d07	61	char message[1024];
574bf16f MA	62
	63	if (ctxt->err) {
	64	return;
	65	}
c96c84a9	66	va_start(ap, msg);
ef749d07	67	vsnprintf(message, sizeof(message), msg, ap);
c96c84a9	68	va_end(ap);
f231b88d	69	error_setg(&ctxt->err, "JSON parse error, %s", message);
4a5fcab7 AL	70	}
4a5fcab7 AL	71
dc45a07c	72	static int cvt4hex(const char *s)
4a5fcab7	73	{
dc45a07c MA	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	}
4a5fcab7	91	}
dc45a07c	92	return cp;
4a5fcab7 AL	93	}
	94
	95	/**
b2da4a4d	96	* parse_string(): Parse a JSON string
4a5fcab7	97	*
b2da4a4d MA	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.
4a5fcab7	128	*/
b2da4a4d	129	static QString parse_string(JSONParserContext ctxt, JSONToken *token)
4a5fcab7	130	{
9bada897	131	const char *ptr = token->str;
68af4cc1	132	GString *str;
00ea57fa	133	char quote;
dc45a07c MA	134	const char *beg;
dc45a07c MA	135	int cp, trailing;
e59f39d4 MA	136	char *end;
	137	ssize_t len;
	138	char utf8_buf[5];
4a5fcab7	139
00ea57fa MA	140	assert(ptr == '"' \|\| ptr == '\'');
00ea57fa MA	141	quote = *ptr++;
68af4cc1	142	str = g_string_new(NULL);
00ea57fa MA	143
	144	while (*ptr != quote) {
	145	assert(*ptr);
16a48599 MA	146	switch (*ptr) {
16a48599 MA	147	case '\\':
dc45a07c	148	beg = ptr++;
00ea57fa	149	switch (*ptr++) {
4a5fcab7	150	case '"':
68af4cc1	151	g_string_append_c(str, '"');
4a5fcab7 AL	152	break;
4a5fcab7 AL	153	case '\'':
68af4cc1	154	g_string_append_c(str, '\'');
4a5fcab7 AL	155	break;
4a5fcab7 AL	156	case '\\':
68af4cc1	157	g_string_append_c(str, '\\');
4a5fcab7 AL	158	break;
4a5fcab7 AL	159	case '/':
68af4cc1	160	g_string_append_c(str, '/');
4a5fcab7 AL	161	break;
4a5fcab7 AL	162	case 'b':
68af4cc1	163	g_string_append_c(str, '\b');
4a5fcab7	164	break;
bd032695	165	case 'f':
68af4cc1	166	g_string_append_c(str, '\f');
bd032695	167	break;
4a5fcab7	168	case 'n':
68af4cc1	169	g_string_append_c(str, '\n');
4a5fcab7 AL	170	break;
4a5fcab7 AL	171	case 'r':
68af4cc1	172	g_string_append_c(str, '\r');
4a5fcab7 AL	173	break;
4a5fcab7 AL	174	case 't':
68af4cc1	175	g_string_append_c(str, '\t');
4a5fcab7	176	break;
de6decfe	177	case 'u':
dc45a07c MA	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 */
4a5fcab7	193	}
4a5fcab7 AL	194	}
4a5fcab7 AL	195
46a628b1 MA	196	if (mod_utf8_encode(utf8_buf, sizeof(utf8_buf), cp) < 0) {
46a628b1 MA	197	parse_error(ctxt, token,
dc45a07c MA	198	"%.*s is not a valid Unicode character",
dc45a07c MA	199	(int)(ptr - beg), beg);
46a628b1 MA	200	goto out;
46a628b1 MA	201	}
68af4cc1	202	g_string_append(str, utf8_buf);
de6decfe	203	break;
4a5fcab7 AL	204	default:
	205	parse_error(ctxt, token, "invalid escape sequence in string");
	206	goto out;
	207	}
16a48599 MA	208	break;
16a48599 MA	209	case '%':
bbc0586c CF	210	if (ctxt->ap) {
	211	if (ptr[1] != '%') {
	212	parse_error(ctxt, token, "can't interpolate into string");
	213	goto out;
	214	}
	215	ptr++;
16a48599 MA	216	}
	217	/* fall through */
	218	default:
e59f39d4	219	cp = mod_utf8_codepoint(ptr, 6, &end);
4b1c0cd7	220	if (cp < 0) {
e59f39d4 MA	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);
68af4cc1	227	g_string_append(str, utf8_buf);
4a5fcab7 AL	228	}
	229	}
	230
68af4cc1	231	return qstring_from_gstring(str);
4a5fcab7 AL	232
4a5fcab7 AL	233	out:
68af4cc1	234	g_string_free(str, true);
4a5fcab7 AL	235	return NULL;
	236	}
	237
9bada897 PB	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.
95385fe9	241	*/
9bada897	242	static JSONToken parser_context_pop_token(JSONParserContext ctxt)
65c0f1e9	243	{
9bada897	244	g_free(ctxt->current);
95385fe9 PB	245	ctxt->current = g_queue_pop_head(ctxt->buf);
95385fe9 PB	246	return ctxt->current;
65c0f1e9 MR	247	}
65c0f1e9 MR	248
9bada897	249	static JSONToken parser_context_peek_token(JSONParserContext ctxt)
65c0f1e9	250	{
95385fe9	251	return g_queue_peek_head(ctxt->buf);
65c0f1e9 MR	252	}
65c0f1e9 MR	253
4a5fcab7 AL	254	/**
	255	* Parsing rules
	256	*/
ada74c3b	257	static int parse_pair(JSONParserContext ctxt, QDict dict)
4a5fcab7	258	{
922d42bb AC	259	QObject *key_obj = NULL;
922d42bb AC	260	QString *key;
532fb532	261	QObject *value;
9bada897	262	JSONToken peek, token;
4a5fcab7	263
65c0f1e9	264	peek = parser_context_peek_token(ctxt);
11e8a46c AL	265	if (peek == NULL) {
	266	parse_error(ctxt, NULL, "premature EOI");
	267	goto out;
	268	}
	269
922d42bb AC	270	key_obj = parse_value(ctxt);
922d42bb AC	271	key = qobject_to(QString, key_obj);
532fb532	272	if (!key) {
4a5fcab7 AL	273	parse_error(ctxt, peek, "key is not a string in object");
	274	goto out;
	275	}
	276
65c0f1e9	277	token = parser_context_pop_token(ctxt);
11e8a46c AL	278	if (token == NULL) {
	279	parse_error(ctxt, NULL, "premature EOI");
	280	goto out;
	281	}
	282
9bada897	283	if (token->type != JSON_COLON) {
4a5fcab7 AL	284	parse_error(ctxt, token, "missing : in object pair");
	285	goto out;
	286	}
	287
ada74c3b	288	value = parse_value(ctxt);
4a5fcab7 AL	289	if (value == NULL) {
	290	parse_error(ctxt, token, "Missing value in dict");
	291	goto out;
	292	}
00382fa8 MA	293
	294	if (qdict_haskey(dict, qstring_get_str(key))) {
	295	parse_error(ctxt, token, "duplicate key");
	296	goto out;
	297	}
4a5fcab7	298
532fb532	299	qdict_put_obj(dict, qstring_get_str(key), value);
4a5fcab7	300
922d42bb	301	qobject_unref(key_obj);
4a5fcab7 AL	302	return 0;
	303
	304	out:
922d42bb	305	qobject_unref(key_obj);
4a5fcab7 AL	306	return -1;
	307	}
	308
ada74c3b	309	static QObject parse_object(JSONParserContext ctxt)
4a5fcab7 AL	310	{
4a5fcab7 AL	311	QDict *dict = NULL;
9bada897	312	JSONToken token, peek;
4a5fcab7	313
65c0f1e9	314	token = parser_context_pop_token(ctxt);
9bada897	315	assert(token && token->type == JSON_LCURLY);
4a5fcab7 AL	316
	317	dict = qdict_new();
	318
65c0f1e9	319	peek = parser_context_peek_token(ctxt);
11e8a46c AL	320	if (peek == NULL) {
	321	parse_error(ctxt, NULL, "premature EOI");
	322	goto out;
	323	}
	324
9bada897	325	if (peek->type != JSON_RCURLY) {
ada74c3b	326	if (parse_pair(ctxt, dict) == -1) {
4a5fcab7 AL	327	goto out;
	328	}
	329
65c0f1e9	330	token = parser_context_pop_token(ctxt);
11e8a46c AL	331	if (token == NULL) {
	332	parse_error(ctxt, NULL, "premature EOI");
	333	goto out;
	334	}
	335
9bada897 PB	336	while (token->type != JSON_RCURLY) {
9bada897 PB	337	if (token->type != JSON_COMMA) {
4a5fcab7 AL	338	parse_error(ctxt, token, "expected separator in dict");
	339	goto out;
	340	}
4a5fcab7	341
ada74c3b	342	if (parse_pair(ctxt, dict) == -1) {
4a5fcab7 AL	343	goto out;
	344	}
	345
65c0f1e9	346	token = parser_context_pop_token(ctxt);
11e8a46c AL	347	if (token == NULL) {
	348	parse_error(ctxt, NULL, "premature EOI");
	349	goto out;
	350	}
4a5fcab7	351	}
4a5fcab7	352	} else {
a491af47	353	(void)parser_context_pop_token(ctxt);
4a5fcab7 AL	354	}
4a5fcab7 AL	355
4a5fcab7 AL	356	return QOBJECT(dict);
	357
	358	out:
cb3e7f08	359	qobject_unref(dict);
4a5fcab7 AL	360	return NULL;
	361	}
	362
ada74c3b	363	static QObject parse_array(JSONParserContext ctxt)
4a5fcab7 AL	364	{
4a5fcab7 AL	365	QList *list = NULL;
9bada897	366	JSONToken token, peek;
4a5fcab7	367
65c0f1e9	368	token = parser_context_pop_token(ctxt);
9bada897	369	assert(token && token->type == JSON_LSQUARE);
4a5fcab7 AL	370
	371	list = qlist_new();
	372
65c0f1e9	373	peek = parser_context_peek_token(ctxt);
11e8a46c AL	374	if (peek == NULL) {
	375	parse_error(ctxt, NULL, "premature EOI");
	376	goto out;
	377	}
	378
9bada897	379	if (peek->type != JSON_RSQUARE) {
4a5fcab7 AL	380	QObject *obj;
4a5fcab7 AL	381
ada74c3b	382	obj = parse_value(ctxt);
4a5fcab7 AL	383	if (obj == NULL) {
	384	parse_error(ctxt, token, "expecting value");
	385	goto out;
	386	}
	387
	388	qlist_append_obj(list, obj);
	389
65c0f1e9	390	token = parser_context_pop_token(ctxt);
11e8a46c AL	391	if (token == NULL) {
	392	parse_error(ctxt, NULL, "premature EOI");
	393	goto out;
	394	}
	395
9bada897 PB	396	while (token->type != JSON_RSQUARE) {
9bada897 PB	397	if (token->type != JSON_COMMA) {
4a5fcab7 AL	398	parse_error(ctxt, token, "expected separator in list");
	399	goto out;
	400	}
	401
ada74c3b	402	obj = parse_value(ctxt);
4a5fcab7 AL	403	if (obj == NULL) {
	404	parse_error(ctxt, token, "expecting value");
	405	goto out;
	406	}
	407
	408	qlist_append_obj(list, obj);
	409
65c0f1e9	410	token = parser_context_pop_token(ctxt);
11e8a46c AL	411	if (token == NULL) {
	412	parse_error(ctxt, NULL, "premature EOI");
	413	goto out;
	414	}
4a5fcab7	415	}
4a5fcab7	416	} else {
a491af47	417	(void)parser_context_pop_token(ctxt);
4a5fcab7 AL	418	}
4a5fcab7 AL	419
4a5fcab7 AL	420	return QOBJECT(list);
	421
	422	out:
cb3e7f08	423	qobject_unref(list);
4a5fcab7 AL	424	return NULL;
	425	}
	426
65c0f1e9	427	static QObject parse_keyword(JSONParserContext ctxt)
4a5fcab7	428	{
9bada897	429	JSONToken *token;
4a5fcab7	430
65c0f1e9	431	token = parser_context_pop_token(ctxt);
9bada897	432	assert(token && token->type == JSON_KEYWORD);
50e2a467	433
9bada897	434	if (!strcmp(token->str, "true")) {
d538b255	435	return QOBJECT(qbool_from_bool(true));
9bada897	436	} else if (!strcmp(token->str, "false")) {
d538b255	437	return QOBJECT(qbool_from_bool(false));
9bada897	438	} else if (!strcmp(token->str, "null")) {
006ca09f	439	return QOBJECT(qnull());
4a5fcab7	440	}
9bada897	441	parse_error(ctxt, token, "invalid keyword '%s'", token->str);
4a5fcab7 AL	442	return NULL;
	443	}
	444
ada74c3b	445	static QObject parse_interpolation(JSONParserContext ctxt)
4a5fcab7	446	{
9bada897	447	JSONToken *token;
4a5fcab7	448
65c0f1e9	449	token = parser_context_pop_token(ctxt);
61030280	450	assert(token && token->type == JSON_INTERP);
6b9606f6	451
9bada897	452	if (!strcmp(token->str, "%p")) {
ada74c3b	453	return va_arg(ctxt->ap, QObject );
9bada897	454	} else if (!strcmp(token->str, "%i")) {
ada74c3b	455	return QOBJECT(qbool_from_bool(va_arg(*ctxt->ap, int)));
9bada897	456	} else if (!strcmp(token->str, "%d")) {
ada74c3b	457	return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, int)));
9bada897	458	} else if (!strcmp(token->str, "%ld")) {
ada74c3b	459	return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, long)));
53a0d616	460	} else if (!strcmp(token->str, "%lld")) {
ada74c3b	461	return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, long long)));
53a0d616	462	} else if (!strcmp(token->str, "%" PRId64)) {
ada74c3b	463	return QOBJECT(qnum_from_int(va_arg(*ctxt->ap, int64_t)));
2bc7cfea	464	} else if (!strcmp(token->str, "%u")) {
ada74c3b	465	return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, unsigned int)));
2bc7cfea	466	} else if (!strcmp(token->str, "%lu")) {
ada74c3b	467	return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, unsigned long)));
53a0d616	468	} else if (!strcmp(token->str, "%llu")) {
ada74c3b	469	return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, unsigned long long)));
53a0d616	470	} else if (!strcmp(token->str, "%" PRIu64)) {
ada74c3b	471	return QOBJECT(qnum_from_uint(va_arg(*ctxt->ap, uint64_t)));
9bada897	472	} else if (!strcmp(token->str, "%s")) {
ada74c3b	473	return QOBJECT(qstring_from_str(va_arg(ctxt->ap, const char )));
9bada897	474	} else if (!strcmp(token->str, "%f")) {
ada74c3b	475	return QOBJECT(qnum_from_double(va_arg(*ctxt->ap, double)));
4a5fcab7	476	}
f7617d45	477	parse_error(ctxt, token, "invalid interpolation '%s'", token->str);
4a5fcab7 AL	478	return NULL;
	479	}
	480
65c0f1e9	481	static QObject parse_literal(JSONParserContext ctxt)
4a5fcab7	482	{
9bada897	483	JSONToken *token;
4a5fcab7	484
65c0f1e9	485	token = parser_context_pop_token(ctxt);
d538b255	486	assert(token);
11e8a46c	487
9bada897	488	switch (token->type) {
4a5fcab7	489	case JSON_STRING:
b2da4a4d	490	return QOBJECT(parse_string(ctxt, token));
3d5b3ec6	491	case JSON_INTEGER: {
01b2ffce MAL	492	/*
01b2ffce MAL	493	* Represent JSON_INTEGER as QNUM_I64 if possible, else as
2bc7cfea MAL	494	* QNUM_U64, else as QNUM_DOUBLE. Note that qemu_strtoi64()
	495	* and qemu_strtou64() fail with ERANGE when it's not
	496	* possible.
3d5b3ec6	497	*
01b2ffce	498	* qnum_get_int() will then work for any signed 64-bit
2bc7cfea MAL	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)
3d5b3ec6	503	*/
2bc7cfea	504	int ret;
3d5b3ec6	505	int64_t value;
2bc7cfea	506	uint64_t uvalue;
3d5b3ec6	507
2bc7cfea MAL	508	ret = qemu_strtoi64(token->str, NULL, 10, &value);
2bc7cfea MAL	509	if (!ret) {
01b2ffce	510	return QOBJECT(qnum_from_int(value));
3d5b3ec6	511	}
2bc7cfea MAL	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	}
3d5b3ec6	521	}
6f0dd6c5	522	/* fall through to JSON_FLOAT */
4a5fcab7	523	case JSON_FLOAT:
6e8e5cb9	524	/* FIXME dependent on locale; a pervasive issue in QEMU */
37aded92	525	/* FIXME our lexer matches RFC 8259 in forbidding Inf or NaN,
6e8e5cb9	526	* but those might be useful extensions beyond JSON */
01b2ffce	527	return QOBJECT(qnum_from_double(strtod(token->str, NULL)));
4a5fcab7	528	default:
d538b255	529	abort();
4a5fcab7	530	}
4a5fcab7 AL	531	}
4a5fcab7 AL	532
ada74c3b	533	static QObject parse_value(JSONParserContext ctxt)
4a5fcab7	534	{
9bada897	535	JSONToken *token;
4a5fcab7	536
d538b255 MA	537	token = parser_context_peek_token(ctxt);
	538	if (token == NULL) {
	539	parse_error(ctxt, NULL, "premature EOI");
	540	return NULL;
4a5fcab7 AL	541	}
4a5fcab7 AL	542
9bada897	543	switch (token->type) {
d538b255	544	case JSON_LCURLY:
ada74c3b	545	return parse_object(ctxt);
d538b255	546	case JSON_LSQUARE:
ada74c3b	547	return parse_array(ctxt);
61030280	548	case JSON_INTERP:
ada74c3b	549	return parse_interpolation(ctxt);
d538b255 MA	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	}
4a5fcab7 AL	560	}
4a5fcab7 AL	561
abe7c206 MA	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
62815d85	574	QObject json_parser_parse(GQueue tokens, va_list ap, Error *errp)
4a5fcab7	575	{
ada74c3b	576	JSONParserContext ctxt = { .buf = tokens, .ap = ap };
4a5fcab7 AL	577	QObject *result;
4a5fcab7 AL	578
ada74c3b	579	result = parse_value(&ctxt);
5d50113c	580	assert(ctxt.err \|\| g_queue_is_empty(ctxt.buf));
65c0f1e9	581
e8b19d7d	582	error_propagate(errp, ctxt.err);
4a5fcab7	583
e8b19d7d MAL	584	while (!g_queue_is_empty(ctxt.buf)) {
	585	parser_context_pop_token(&ctxt);
	586	}
	587	g_free(ctxt.current);
ef749d07	588
4a5fcab7 AL	589	return result;
4a5fcab7 AL	590	}