Re: [Qemu-devel] Re: [PATCH 01/10] Introduce qmisc module

[Anthony Liguori]

Anthony Liguori wrote:
> Paolo Bonzini wrote:
> > On 10/18/2009 04:06 PM, Luiz Capitulino wrote:
> > >   Integration with QObjects is a killer feature, I think it's the
> > > stronger argument against grabbing one from the internet.
> >
> > Yeah, I'd say let's go with Anthony's stuff.  I'll rebase the encoder 
> > on top of it soonish (I still think it's best if JSON encoding lies 
> > in QObject like a kind of toString).  If we'll need the asynchronous 
> > parsing later, we can easily replace it with mine or Vincent's.
>
> One thing I want to add as a feature to the 0.12 release is a nice 
> client API.  To have this, we'll need message boundary identification 
> and a JSON encoder.  I'll focus on the message boundary identification 
> today.

Here's a first pass.  I'll clean up this afternoon and post a proper 
patch.  It turned out to work pretty well.

Regards,

Anthony Liguori

#include <stdint.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>

#define offset_of(type, member) ((unsigned long)&(((type *)0)->member))
#define container_of(obj, type, member) (type *)((void *)(obj) - 
offset_of(type, member))

/*
 * 
\"([^\\\"]|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*\"
 * 
'([^\\']|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*'
 * 0|([1-9][0-9]*(.[0-9]+)?([eE]([-+])?[0-9]+))
 * [{}\[\],:]
 * [a-z]+
 *
 */

enum json_lexer_state {
    ERROR = 0,
    IN_DONE,
    IN_DQ_UCODE3,
    IN_DQ_UCODE2,
    IN_DQ_UCODE1,
    IN_DQ_UCODE0,
    IN_DQ_STRING_ESCAPE,
    IN_DQ_STRING,
    IN_SQ_UCODE3,
    IN_SQ_UCODE2,
    IN_SQ_UCODE1,
    IN_SQ_UCODE0,
    IN_SQ_STRING_ESCAPE,
    IN_SQ_STRING,
    IN_ZERO,
    IN_DIGITS,
    IN_DIGIT,
    IN_EXP_E,
    IN_MANTISSA,
    IN_MANTISSA_DIGITS,
    IN_NONZERO_NUMBER,
    IN_NEG_NONZERO_NUMBER,
    IN_KEYWORD,
    IN_WHITESPACE,
    IN_START,
    DONE,
    SKIP,
};

static const uint8_t json_lexer[][256] =  {
    [IN_DONE] = {
        [1 ... 0x7F] = DONE,
    },

    /* double quote string */
    [IN_DQ_UCODE3] = {
        ['0' ... '9'] = IN_DQ_STRING,
        ['a' ... 'f'] = IN_DQ_STRING,
        ['A' ... 'F'] = IN_DQ_STRING,
    },
    [IN_DQ_UCODE2] = {
        ['0' ... '9'] = IN_DQ_UCODE3,
        ['a' ... 'f'] = IN_DQ_UCODE3,
        ['A' ... 'F'] = IN_DQ_UCODE3,
    },
    [IN_DQ_UCODE1] = {
        ['0' ... '9'] = IN_DQ_UCODE2,
        ['a' ... 'f'] = IN_DQ_UCODE2,
        ['A' ... 'F'] = IN_DQ_UCODE2,
    },
    [IN_DQ_UCODE0] = {
        ['0' ... '9'] = IN_DQ_UCODE1,
        ['a' ... 'f'] = IN_DQ_UCODE1,
        ['A' ... 'F'] = IN_DQ_UCODE1,
    },
    [IN_DQ_STRING_ESCAPE] = {
        ['b'] = IN_DQ_STRING,
        ['f'] =  IN_DQ_STRING,
        ['n'] =  IN_DQ_STRING,
        ['r'] =  IN_DQ_STRING,
        ['t'] =  IN_DQ_STRING,
        ['\''] = IN_DQ_STRING,
        ['\"'] = IN_DQ_STRING,
        ['u'] = IN_DQ_UCODE0,
    },
    [IN_DQ_STRING] = {
        [1 ... 0xFF] = IN_DQ_STRING,
        ['\\'] = IN_DQ_STRING_ESCAPE,
        ['"'] = IN_DONE,
    },

    /* single quote string */
    [IN_SQ_UCODE3] = {
        ['0' ... '9'] = IN_SQ_STRING,
        ['a' ... 'f'] = IN_SQ_STRING,
        ['A' ... 'F'] = IN_SQ_STRING,
    },
    [IN_SQ_UCODE2] = {
        ['0' ... '9'] = IN_SQ_UCODE3,
        ['a' ... 'f'] = IN_SQ_UCODE3,
        ['A' ... 'F'] = IN_SQ_UCODE3,
    },
    [IN_SQ_UCODE1] = {
        ['0' ... '9'] = IN_SQ_UCODE2,
        ['a' ... 'f'] = IN_SQ_UCODE2,
        ['A' ... 'F'] = IN_SQ_UCODE2,
    },
    [IN_SQ_UCODE0] = {
        ['0' ... '9'] = IN_SQ_UCODE1,
        ['a' ... 'f'] = IN_SQ_UCODE1,
        ['A' ... 'F'] = IN_SQ_UCODE1,
    },
    [IN_SQ_STRING_ESCAPE] = {
        ['b'] = IN_SQ_STRING,
        ['f'] =  IN_SQ_STRING,
        ['n'] =  IN_SQ_STRING,
        ['r'] =  IN_SQ_STRING,
        ['t'] =  IN_SQ_STRING,
        ['\''] = IN_SQ_STRING,
        ['\"'] = IN_SQ_STRING,
        ['u'] = IN_SQ_UCODE0,
    },
    [IN_SQ_STRING] = {
        [1 ... 0xFF] = IN_SQ_STRING,
        ['\\'] = IN_SQ_STRING_ESCAPE,
        ['\''] = IN_DONE,
    },

    /* Zero */
    [IN_ZERO] = {
        [1 ... 0x7F] = DONE,
        ['0' ... '9'] = ERROR,
    },

    /* Non-zero numbers */
    [IN_DIGITS] = {
        [1 ... 0x7F] = DONE,
        ['0' ... '9'] = IN_DIGITS,
    },

    [IN_DIGIT] = {
        ['0' ... '9'] = IN_DIGITS,
    },

    [IN_EXP_E] = {
        ['-'] = IN_DIGIT,
        ['+'] = IN_DIGIT,
        ['0' ... '9'] = IN_DIGITS,
    },

    [IN_MANTISSA_DIGITS] = {
        [1 ... 0x7F] = DONE,
        ['0' ... '9'] = IN_MANTISSA_DIGITS,
        ['e'] = IN_EXP_E,
        ['E'] = IN_EXP_E,
    },

    [IN_MANTISSA] = {
        ['0' ... '9'] = IN_MANTISSA_DIGITS,
    },

    [IN_NONZERO_NUMBER] = {
        [1 ... 0x7F] = DONE,
        ['0' ... '9'] = IN_NONZERO_NUMBER,
        ['e'] = IN_EXP_E,
        ['E'] = IN_EXP_E,
        ['.'] = IN_MANTISSA,
    },

    [IN_NEG_NONZERO_NUMBER] = {
        ['1' ... '9'] = IN_NONZERO_NUMBER,
    },

    /* keywords */
    [IN_KEYWORD] = {
        [1 ... 0x7F] = DONE,
        ['a' ... 'z'] = IN_KEYWORD,
    },

    /* whitespace */
    [IN_WHITESPACE] = {
        [1 ... 0x7F] = SKIP,
        [' '] = IN_WHITESPACE,
        ['\t'] = IN_WHITESPACE,
        ['\r'] = IN_WHITESPACE,
        ['\n'] = IN_WHITESPACE,
    },        

    /* top level rule */
    [IN_START] = {
        ['"'] = IN_DQ_STRING,
        ['\''] = IN_SQ_STRING,
        ['0'] = IN_ZERO,
        ['1' ... '9'] = IN_NONZERO_NUMBER,
        ['-'] = IN_NEG_NONZERO_NUMBER,
        ['{'] = IN_DONE,
        ['}'] = IN_DONE,
        ['['] = IN_DONE,
        [']'] = IN_DONE,
        [','] = IN_DONE,
        [':'] = IN_DONE,
        ['a' ... 'z'] = IN_KEYWORD,
        [' '] = IN_WHITESPACE,
        ['\t'] = IN_WHITESPACE,
        ['\r'] = IN_WHITESPACE,
        ['\n'] = IN_WHITESPACE,
    },
};

typedef struct JSONLexer
{
    void (*emit)(struct JSONLexer *lexer, const char *token);
    enum json_lexer_state state;
    char token[1024];
    size_t len;
} JSONLexer;

void json_lexer_init(JSONLexer *lexer,
                     void (*func)(JSONLexer *, const char *))
{
    lexer->emit = func;
    lexer->state = IN_START;
    lexer->len = 0;
    lexer->token[lexer->len] = 0;
}

int json_lexer_feed(JSONLexer *lexer, char ch)
{
    lexer->state = json_lexer[lexer->state][(uint8_t)ch];

    if (lexer->state == DONE || lexer->state == SKIP) {
        if (lexer->state == DONE) {
            lexer->emit(lexer, lexer->token);
        }
        lexer->state = json_lexer[IN_START][(uint8_t)ch];
        lexer->len = 0;
    }

    if (lexer->state == ERROR) {
        return -EINVAL;
    }

    if (lexer->len < (sizeof(lexer->token) - 1)) {
        lexer->token[lexer->len++] = ch;
    }
    lexer->token[lexer->len] = 0;

    return 0;
}

typedef struct JSONMessageParser
{
    void (*emit)(struct JSONMessageParser *parser, const char *message);
    JSONLexer lexer;
    int brace_count;
    int bracket_count;
    char buffer[1024];
    size_t len;
} JSONMessageParser;

static void json_message_process_token(JSONLexer *lexer, const char *token)
{
    JSONMessageParser *parser = container_of(lexer, JSONMessageParser, lexer);

    if (strcmp(token, "{") == 0) {
        parser->brace_count++;
    } else if (strcmp(token, "}") == 0) {
        parser->brace_count--;
    } else if (strcmp(token, "[") == 0) {
        parser->bracket_count++;
    } else if (strcmp(token, "]") == 0) {
        parser->bracket_count--;
    }

    if (parser->brace_count == 0 &&
        parser->bracket_count == 0) {
        parser->emit(parser, parser->buffer);
        parser->len = 0;
    }
}

void json_message_parser_init(JSONMessageParser *parser,
                              void (*func)(JSONMessageParser *, const char *))
{
    parser->emit = func;
    parser->brace_count = 0;
    parser->bracket_count = 0;
    parser->len = 0;
    parser->buffer[parser->len] = 0;

    json_lexer_init(&parser->lexer, json_message_process_token);
}

int json_message_parser_feed(JSONMessageParser *parser,
                             const char *buffer, size_t size)
{
    size_t i;

    for (i = 0; i < size; i++) {
        int ret;

        parser->buffer[parser->len++] = buffer[i];
        parser->buffer[parser->len] = 0; /* FIXME overflow */

        ret = json_lexer_feed(&parser->lexer, buffer[i]);
        if (ret < 0) {
            return ret;
        }
    }

    return 0;
}

static void got_message(JSONMessageParser *parser, const char *message)
{
    printf("got message `%s'\n", message);
}

int main(int argc, char **argv)
{
    JSONMessageParser parser = {};
    char buf[2];
    int ch;

    json_message_parser_init(&parser, got_message);

    while ((ch = getchar()) != EOF) {
        buf[0] = ch;
        buf[1] = 0;

        if (json_message_parser_feed(&parser, buf, 1) < 0) {
            fprintf(stderr, "Invalid character `%c'\n", ch);
            return 1;
        }
    }

    return 0;
}