Archipelago » qemu

/*

 * 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 <stdarg.h>

#include "qemu-common.h"

#include "qstring.h"

#include "qint.h"

#include "qdict.h"

#include "qlist.h"

#include "qfloat.h"

#include "qbool.h"

#include "json-parser.h"

#include "json-lexer.h"

#include "qerror.h"

typedef struct JSONParserContext

{

    Error *err;

    struct {

        QObject **buf;

        size_t pos;

        size_t count;

    } tokens;

} 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, va_list *ap);

/**

 * Token manipulators

 *

 * tokens are dictionaries that contain a type, a string value, and geometry information

 * about a token identified by the lexer.  These are routines that make working with

 * these objects a bit easier.

 */

static const char *token_get_value(QObject *obj)

{

    return qdict_get_str(qobject_to_qdict(obj), "token");

}

static JSONTokenType token_get_type(QObject *obj)

{

    return qdict_get_int(qobject_to_qdict(obj), "type");

}

static int token_is_operator(QObject *obj, char op)

{

    const char *val;

    if (token_get_type(obj) != JSON_OPERATOR) {

        return 0;

    }

    val = token_get_value(obj);

    return (val[0] == op) && (val[1] == 0);

}

static int token_is_keyword(QObject *obj, const char *value)

{

    if (token_get_type(obj) != JSON_KEYWORD) {

        return 0;

    }

    return strcmp(token_get_value(obj), value) == 0;

}

static int token_is_escape(QObject *obj, const char *value)

{

    if (token_get_type(obj) != JSON_ESCAPE) {

        return 0;

    }

    return (strcmp(token_get_value(obj), value) == 0);

}

/**

 * Error handler

 */

static void GCC_FMT_ATTR(3, 4) parse_error(JSONParserContext *ctxt,

                                           QObject *token, const char *msg, ...)

{

    va_list ap;

    char message[1024];

    va_start(ap, msg);

    vsnprintf(message, sizeof(message), msg, ap);

    va_end(ap);

    if (ctxt->err) {

        error_free(ctxt->err);

        ctxt->err = NULL;

    }

    error_set(&ctxt->err, QERR_JSON_PARSE_ERROR, message);

}

/**

 * String helpers

 *

 * These helpers are used to unescape strings.

 */

static void wchar_to_utf8(uint16_t wchar, char *buffer, size_t buffer_length)

{

    if (wchar <= 0x007F) {

        BUG_ON(buffer_length < 2);

        buffer[0] = wchar & 0x7F;

        buffer[1] = 0;

    } else if (wchar <= 0x07FF) {

        BUG_ON(buffer_length < 3);

        buffer[0] = 0xC0 | ((wchar >> 6) & 0x1F);

        buffer[1] = 0x80 | (wchar & 0x3F);

        buffer[2] = 0;

    } else {

        BUG_ON(buffer_length < 4);

        buffer[0] = 0xE0 | ((wchar >> 12) & 0x0F);

        buffer[1] = 0x80 | ((wchar >> 6) & 0x3F);

        buffer[2] = 0x80 | (wchar & 0x3F);

        buffer[3] = 0;

    }

}

static int hex2decimal(char ch)

{

    if (ch >= '0' && ch <= '9') {

        return (ch - '0');

    } else if (ch >= 'a' && ch <= 'f') {

        return 10 + (ch - 'a');

    } else if (ch >= 'A' && ch <= 'F') {

        return 10 + (ch - 'A');

    }

    return -1;

}

/**

 * parse_string(): Parse a json string and return a QObject

 *

 *  string

 *      ""

 *      " chars "

 *  chars

 *      char

 *      char chars

 *  char

 *      any-Unicode-character-

 *          except-"-or-\-or-

 *          control-character

 *      \"

 *      \\

 *      \/

 *      \b

 *      \f

 *      \n

 *      \r

 *      \t

 *      \u four-hex-digits 

 */

static QString *qstring_from_escaped_str(JSONParserContext *ctxt, QObject *token)

{

    const char *ptr = token_get_value(token);

    QString *str;

    int double_quote = 1;

    if (*ptr == '"') {

        double_quote = 1;

    } else {

        double_quote = 0;

    }

    ptr++;

    str = qstring_new();

    while (*ptr && 

           ((double_quote && *ptr != '"') || (!double_quote && *ptr != '\''))) {

        if (*ptr == '\\') {

            ptr++;

            switch (*ptr) {

            case '"':

                qstring_append(str, "\"");

                ptr++;

                break;

            case '\'':

                qstring_append(str, "'");

                ptr++;

                break;

            case '\\':

                qstring_append(str, "\\");

                ptr++;

                break;

            case '/':

                qstring_append(str, "/");

                ptr++;

                break;

            case 'b':

                qstring_append(str, "\b");

                ptr++;

                break;

            case 'f':

                qstring_append(str, "\f");

                ptr++;

                break;

            case 'n':

                qstring_append(str, "\n");

                ptr++;

                break;

            case 'r':

                qstring_append(str, "\r");

                ptr++;

                break;

            case 't':

                qstring_append(str, "\t");

                ptr++;

                break;

            case 'u': {

                uint16_t unicode_char = 0;

                char utf8_char[4];

                int i = 0;

                ptr++;

                for (i = 0; i < 4; i++) {

                    if (qemu_isxdigit(*ptr)) {

                        unicode_char |= hex2decimal(*ptr) << ((3 - i) * 4);

                    } else {

                        parse_error(ctxt, token,

                                    "invalid hex escape sequence in string");

                        goto out;

                    }

                    ptr++;

                }

                wchar_to_utf8(unicode_char, utf8_char, sizeof(utf8_char));

                qstring_append(str, utf8_char);

            }   break;

            default:

                parse_error(ctxt, token, "invalid escape sequence in string");

                goto out;

            }

        } else {

            char dummy[2];

            dummy[0] = *ptr++;

            dummy[1] = 0;

            qstring_append(str, dummy);

        }

    }

    return str;

out:

    QDECREF(str);

    return NULL;

}

static QObject *parser_context_pop_token(JSONParserContext *ctxt)

{

    QObject *token;

    g_assert(ctxt->tokens.pos < ctxt->tokens.count);

    token = ctxt->tokens.buf[ctxt->tokens.pos];

    ctxt->tokens.pos++;

    return token;

}

/* Note: parser_context_{peek|pop}_token do not increment the

 * token object's refcount. In both cases the references will continue

 * to be tracked and cleaned up in parser_context_free(), so do not

 * attempt to free the token object.

 */

static QObject *parser_context_peek_token(JSONParserContext *ctxt)

{

    QObject *token;

    g_assert(ctxt->tokens.pos < ctxt->tokens.count);

    token = ctxt->tokens.buf[ctxt->tokens.pos];

    return token;

}

static JSONParserContext parser_context_save(JSONParserContext *ctxt)

{

    JSONParserContext saved_ctxt = {0};

    saved_ctxt.tokens.pos = ctxt->tokens.pos;

    saved_ctxt.tokens.count = ctxt->tokens.count;

    saved_ctxt.tokens.buf = ctxt->tokens.buf;

    return saved_ctxt;

}

static void parser_context_restore(JSONParserContext *ctxt,

                                   JSONParserContext saved_ctxt)

{

    ctxt->tokens.pos = saved_ctxt.tokens.pos;

    ctxt->tokens.count = saved_ctxt.tokens.count;

    ctxt->tokens.buf = saved_ctxt.tokens.buf;

}

static void tokens_append_from_iter(QObject *obj, void *opaque)

{

    JSONParserContext *ctxt = opaque;

    g_assert(ctxt->tokens.pos < ctxt->tokens.count);

    ctxt->tokens.buf[ctxt->tokens.pos++] = obj;

    qobject_incref(obj);

}

static JSONParserContext *parser_context_new(QList *tokens)

{

    JSONParserContext *ctxt;

    size_t count;

    if (!tokens) {

        return NULL;

    }

    count = qlist_size(tokens);

    if (count == 0) {

        return NULL;

    }

    ctxt = g_malloc0(sizeof(JSONParserContext));

    ctxt->tokens.pos = 0;

    ctxt->tokens.count = count;

    ctxt->tokens.buf = g_malloc(count * sizeof(QObject *));

    qlist_iter(tokens, tokens_append_from_iter, ctxt);

    ctxt->tokens.pos = 0;

    return ctxt;

}

/* to support error propagation, ctxt->err must be freed separately */

static void parser_context_free(JSONParserContext *ctxt)

{

    int i;

    if (ctxt) {

        for (i = 0; i < ctxt->tokens.count; i++) {

            qobject_decref(ctxt->tokens.buf[i]);

        }

        g_free(ctxt->tokens.buf);

        g_free(ctxt);

    }

}

/**

 * Parsing rules

 */

static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)

{

    QObject *key = NULL, *token = NULL, *value, *peek;

    JSONParserContext saved_ctxt = parser_context_save(ctxt);

    peek = parser_context_peek_token(ctxt);

    if (peek == NULL) {

        parse_error(ctxt, NULL, "premature EOI");

        goto out;

    }

    key = parse_value(ctxt, ap);

    if (!key || qobject_type(key) != QTYPE_QSTRING) {

        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_is_operator(token, ':')) {

        parse_error(ctxt, token, "missing : in object pair");

        goto out;

    }

    value = parse_value(ctxt, ap);

    if (value == NULL) {

        parse_error(ctxt, token, "Missing value in dict");

        goto out;

    }

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

    qobject_decref(key);

    return 0;

out:

    parser_context_restore(ctxt, saved_ctxt);

    qobject_decref(key);

    return -1;

}

static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)

{

    QDict *dict = NULL;

    QObject *token, *peek;

    JSONParserContext saved_ctxt = parser_context_save(ctxt);

    token = parser_context_pop_token(ctxt);

    if (token == NULL) {

        goto out;

    }

    if (!token_is_operator(token, '{')) {

        goto out;

    }

    token = NULL;

    dict = qdict_new();

    peek = parser_context_peek_token(ctxt);

    if (peek == NULL) {

        parse_error(ctxt, NULL, "premature EOI");

        goto out;

    }

    if (!token_is_operator(peek, '}')) {

        if (parse_pair(ctxt, dict, ap) == -1) {

            goto out;

        }

        token = parser_context_pop_token(ctxt);

        if (token == NULL) {

            parse_error(ctxt, NULL, "premature EOI");

            goto out;

        }

        while (!token_is_operator(token, '}')) {

            if (!token_is_operator(token, ',')) {

                parse_error(ctxt, token, "expected separator in dict");

                goto out;

            }

            token = NULL;

            if (parse_pair(ctxt, dict, ap) == -1) {

                goto out;

            }

            token = parser_context_pop_token(ctxt);

            if (token == NULL) {

                parse_error(ctxt, NULL, "premature EOI");

                goto out;

            }

        }

        token = NULL;

    } else {

        token = parser_context_pop_token(ctxt);

        token = NULL;

    }

    return QOBJECT(dict);

out:

    parser_context_restore(ctxt, saved_ctxt);

    QDECREF(dict);

    return NULL;

}

static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)

{

    QList *list = NULL;

    QObject *token, *peek;

    JSONParserContext saved_ctxt = parser_context_save(ctxt);

    token = parser_context_pop_token(ctxt);

    if (token == NULL) {

        goto out;

    }

    if (!token_is_operator(token, '[')) {

        token = NULL;

        goto out;

    }

    token = NULL;

    list = qlist_new();

    peek = parser_context_peek_token(ctxt);

    if (peek == NULL) {

        parse_error(ctxt, NULL, "premature EOI");

        goto out;

    }

    if (!token_is_operator(peek, ']')) {

        QObject *obj;

        obj = parse_value(ctxt, ap);

        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_is_operator(token, ']')) {

            if (!token_is_operator(token, ',')) {

                parse_error(ctxt, token, "expected separator in list");

                goto out;

            }

            token = NULL;

            obj = parse_value(ctxt, ap);

            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;

            }

        }

        token = NULL;

    } else {

        token = parser_context_pop_token(ctxt);

        token = NULL;

    }

    return QOBJECT(list);

out:

    parser_context_restore(ctxt, saved_ctxt);

    QDECREF(list);

    return NULL;

}

static QObject *parse_keyword(JSONParserContext *ctxt)

{

    QObject *token, *ret;

    JSONParserContext saved_ctxt = parser_context_save(ctxt);

    token = parser_context_pop_token(ctxt);

    if (token == NULL) {

        goto out;

    }

    if (token_get_type(token) != JSON_KEYWORD) {

        goto out;

    }

    if (token_is_keyword(token, "true")) {

        ret = QOBJECT(qbool_from_int(true));

    } else if (token_is_keyword(token, "false")) {

        ret = QOBJECT(qbool_from_int(false));

    } else {

        parse_error(ctxt, token, "invalid keyword `%s'", token_get_value(token));

        goto out;

    }

    return ret;

out: 

    parser_context_restore(ctxt, saved_ctxt);

    return NULL;

}

static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)

{

    QObject *token = NULL, *obj;

    JSONParserContext saved_ctxt = parser_context_save(ctxt);

    if (ap == NULL) {

        goto out;

    }

    token = parser_context_pop_token(ctxt);

    if (token == NULL) {

        goto out;

    }

    if (token_is_escape(token, "%p")) {

        obj = va_arg(*ap, QObject *);

    } else if (token_is_escape(token, "%i")) {

        obj = QOBJECT(qbool_from_int(va_arg(*ap, int)));

    } else if (token_is_escape(token, "%d")) {

        obj = QOBJECT(qint_from_int(va_arg(*ap, int)));

    } else if (token_is_escape(token, "%ld")) {

        obj = QOBJECT(qint_from_int(va_arg(*ap, long)));

    } else if (token_is_escape(token, "%lld") ||

               token_is_escape(token, "%I64d")) {

        obj = QOBJECT(qint_from_int(va_arg(*ap, long long)));

    } else if (token_is_escape(token, "%s")) {

        obj = QOBJECT(qstring_from_str(va_arg(*ap, const char *)));

    } else if (token_is_escape(token, "%f")) {

        obj = QOBJECT(qfloat_from_double(va_arg(*ap, double)));

    } else {

        goto out;

    }

    return obj;

out:

    parser_context_restore(ctxt, saved_ctxt);

    return NULL;

}

static QObject *parse_literal(JSONParserContext *ctxt)

{

    QObject *token, *obj;

    JSONParserContext saved_ctxt = parser_context_save(ctxt);

    token = parser_context_pop_token(ctxt);

    if (token == NULL) {

        goto out;

    }

    switch (token_get_type(token)) {

    case JSON_STRING:

        obj = QOBJECT(qstring_from_escaped_str(ctxt, token));

        break;

    case JSON_INTEGER:

        obj = QOBJECT(qint_from_int(strtoll(token_get_value(token), NULL, 10)));

        break;

    case JSON_FLOAT:

        /* FIXME dependent on locale */

        obj = QOBJECT(qfloat_from_double(strtod(token_get_value(token), NULL)));

        break;

    default:

        goto out;

    }

    return obj;

out:

    parser_context_restore(ctxt, saved_ctxt);

    return NULL;

}

static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)

{

    QObject *obj;

    obj = parse_object(ctxt, ap);

    if (obj == NULL) {

        obj = parse_array(ctxt, ap);

    }

    if (obj == NULL) {

        obj = parse_escape(ctxt, ap);

    }

    if (obj == NULL) {

        obj = parse_keyword(ctxt);

    } 

    if (obj == NULL) {

        obj = parse_literal(ctxt);

    }

    return obj;

}

QObject *json_parser_parse(QList *tokens, va_list *ap)

{

    return json_parser_parse_err(tokens, ap, NULL);

}

QObject *json_parser_parse_err(QList *tokens, va_list *ap, Error **errp)

{

    JSONParserContext *ctxt = parser_context_new(tokens);

    QObject *result;

    if (!ctxt) {

        return NULL;

    }

    result = parse_value(ctxt, ap);

    error_propagate(errp, ctxt->err);

    parser_context_free(ctxt);

    return result;

}