json-lexer.c

   1 /*
   2  * JSON lexer
   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 "qstring.h"
  15 #include "qlist.h"
  16 #include "qdict.h"
  17 #include "qint.h"
  18 #include "qemu-common.h"
  19 #include "json-lexer.h"
  20
  21 /*
  22  * \"([^\\\"]|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*\"
  23  * '([^\\']|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*'
  24  * 0|([1-9][0-9]*(.[0-9]+)?([eE]([-+])?[0-9]+))
  25  * [{}\[\],:]
  26  * [a-z]+
  27  *
  28  */
  29
  30 enum json_lexer_state {
  31     ERROR = 0,
  32     IN_DONE_STRING,
  33     IN_DQ_UCODE3,
  34     IN_DQ_UCODE2,
  35     IN_DQ_UCODE1,
  36     IN_DQ_UCODE0,
  37     IN_DQ_STRING_ESCAPE,
  38     IN_DQ_STRING,
  39     IN_SQ_UCODE3,
  40     IN_SQ_UCODE2,
  41     IN_SQ_UCODE1,
  42     IN_SQ_UCODE0,
  43     IN_SQ_STRING_ESCAPE,
  44     IN_SQ_STRING,
  45     IN_ZERO,
  46     IN_DIGITS,
  47     IN_DIGIT,
  48     IN_EXP_E,
  49     IN_MANTISSA,
  50     IN_MANTISSA_DIGITS,
  51     IN_NONZERO_NUMBER,
  52     IN_NEG_NONZERO_NUMBER,
  53     IN_KEYWORD,
  54     IN_ESCAPE,
  55     IN_ESCAPE_L,
  56     IN_ESCAPE_LL,
  57     IN_ESCAPE_I,
  58     IN_ESCAPE_I6,
  59     IN_ESCAPE_I64,
  60     IN_ESCAPE_DONE,
  61     IN_WHITESPACE,
  62     IN_OPERATOR_DONE,
  63     IN_START,
  64 };
  65
  66 #define TERMINAL(state) [0 ... 0x7F] = (state)
  67
  68 /* Return whether TERMINAL is a terminal state and the transition to it
  69    from OLD_STATE required lookahead.  This happens whenever the table
  70    below uses the TERMINAL macro.  */
  71 #define TERMINAL_NEEDED_LOOKAHEAD(old_state, terminal) \
  72             (json_lexer[(old_state)][0] == (terminal))
  73
  74 static const uint8_t json_lexer[][256] =  {
  75     [IN_DONE_STRING] = {
  76         TERMINAL(JSON_STRING),
  77     },
  78
  79     /* double quote string */
  80     [IN_DQ_UCODE3] = {
  81         ['0' ... '9'] = IN_DQ_STRING,
  82         ['a' ... 'f'] = IN_DQ_STRING,
  83         ['A' ... 'F'] = IN_DQ_STRING,
  84     },
  85     [IN_DQ_UCODE2] = {
  86         ['0' ... '9'] = IN_DQ_UCODE3,
  87         ['a' ... 'f'] = IN_DQ_UCODE3,
  88         ['A' ... 'F'] = IN_DQ_UCODE3,
  89     },
  90     [IN_DQ_UCODE1] = {
  91         ['0' ... '9'] = IN_DQ_UCODE2,
  92         ['a' ... 'f'] = IN_DQ_UCODE2,
  93         ['A' ... 'F'] = IN_DQ_UCODE2,
  94     },
  95     [IN_DQ_UCODE0] = {
  96         ['0' ... '9'] = IN_DQ_UCODE1,
  97         ['a' ... 'f'] = IN_DQ_UCODE1,
  98         ['A' ... 'F'] = IN_DQ_UCODE1,
  99     },
 100     [IN_DQ_STRING_ESCAPE] = {
 101         ['b'] = IN_DQ_STRING,
 102         ['f'] =  IN_DQ_STRING,
 103         ['n'] =  IN_DQ_STRING,
 104         ['r'] =  IN_DQ_STRING,
 105         ['t'] =  IN_DQ_STRING,
 106         ['/'] = IN_DQ_STRING,
 107         ['\\'] = IN_DQ_STRING,
 108         ['\''] = IN_DQ_STRING,
 109         ['\"'] = IN_DQ_STRING,
 110         ['u'] = IN_DQ_UCODE0,
 111     },
 112     [IN_DQ_STRING] = {
 113         [1 ... 0xFF] = IN_DQ_STRING,
 114         ['\\'] = IN_DQ_STRING_ESCAPE,
 115         ['"'] = IN_DONE_STRING,
 116     },
 117
 118     /* single quote string */
 119     [IN_SQ_UCODE3] = {
 120         ['0' ... '9'] = IN_SQ_STRING,
 121         ['a' ... 'f'] = IN_SQ_STRING,
 122         ['A' ... 'F'] = IN_SQ_STRING,
 123     },
 124     [IN_SQ_UCODE2] = {
 125         ['0' ... '9'] = IN_SQ_UCODE3,
 126         ['a' ... 'f'] = IN_SQ_UCODE3,
 127         ['A' ... 'F'] = IN_SQ_UCODE3,
 128     },
 129     [IN_SQ_UCODE1] = {
 130         ['0' ... '9'] = IN_SQ_UCODE2,
 131         ['a' ... 'f'] = IN_SQ_UCODE2,
 132         ['A' ... 'F'] = IN_SQ_UCODE2,
 133     },
 134     [IN_SQ_UCODE0] = {
 135         ['0' ... '9'] = IN_SQ_UCODE1,
 136         ['a' ... 'f'] = IN_SQ_UCODE1,
 137         ['A' ... 'F'] = IN_SQ_UCODE1,
 138     },
 139     [IN_SQ_STRING_ESCAPE] = {
 140         ['b'] = IN_SQ_STRING,
 141         ['f'] =  IN_SQ_STRING,
 142         ['n'] =  IN_SQ_STRING,
 143         ['r'] =  IN_SQ_STRING,
 144         ['t'] =  IN_SQ_STRING,
 145         ['/'] = IN_DQ_STRING,
 146         ['\\'] = IN_DQ_STRING,
 147         ['\''] = IN_SQ_STRING,
 148         ['\"'] = IN_SQ_STRING,
 149         ['u'] = IN_SQ_UCODE0,
 150     },
 151     [IN_SQ_STRING] = {
 152         [1 ... 0xFF] = IN_SQ_STRING,
 153         ['\\'] = IN_SQ_STRING_ESCAPE,
 154         ['\''] = IN_DONE_STRING,
 155     },
 156
 157     /* Zero */
 158     [IN_ZERO] = {
 159         TERMINAL(JSON_INTEGER),
 160         ['0' ... '9'] = ERROR,
 161         ['.'] = IN_MANTISSA,
 162     },
 163
 164     /* Float */
 165     [IN_DIGITS] = {
 166         TERMINAL(JSON_FLOAT),
 167         ['0' ... '9'] = IN_DIGITS,
 168     },
 169
 170     [IN_DIGIT] = {
 171         ['0' ... '9'] = IN_DIGITS,
 172     },
 173
 174     [IN_EXP_E] = {
 175         ['-'] = IN_DIGIT,
 176         ['+'] = IN_DIGIT,
 177         ['0' ... '9'] = IN_DIGITS,
 178     },
 179
 180     [IN_MANTISSA_DIGITS] = {
 181         TERMINAL(JSON_FLOAT),
 182         ['0' ... '9'] = IN_MANTISSA_DIGITS,
 183         ['e'] = IN_EXP_E,
 184         ['E'] = IN_EXP_E,
 185     },
 186
 187     [IN_MANTISSA] = {
 188         ['0' ... '9'] = IN_MANTISSA_DIGITS,
 189     },
 190
 191     /* Number */
 192     [IN_NONZERO_NUMBER] = {
 193         TERMINAL(JSON_INTEGER),
 194         ['0' ... '9'] = IN_NONZERO_NUMBER,
 195         ['e'] = IN_EXP_E,
 196         ['E'] = IN_EXP_E,
 197         ['.'] = IN_MANTISSA,
 198     },
 199
 200     [IN_NEG_NONZERO_NUMBER] = {
 201         ['0'] = IN_ZERO,
 202         ['1' ... '9'] = IN_NONZERO_NUMBER,
 203     },
 204
 205     /* keywords */
 206     [IN_KEYWORD] = {
 207         TERMINAL(JSON_KEYWORD),
 208         ['a' ... 'z'] = IN_KEYWORD,
 209     },
 210
 211     /* whitespace */
 212     [IN_WHITESPACE] = {
 213         TERMINAL(JSON_SKIP),
 214         [' '] = IN_WHITESPACE,
 215         ['\t'] = IN_WHITESPACE,
 216         ['\r'] = IN_WHITESPACE,
 217         ['\n'] = IN_WHITESPACE,
 218     },
 219
 220     /* operator */
 221     [IN_OPERATOR_DONE] = {
 222         TERMINAL(JSON_OPERATOR),
 223     },
 224
 225     /* escape */
 226     [IN_ESCAPE_DONE] = {
 227         TERMINAL(JSON_ESCAPE),
 228     },
 229
 230     [IN_ESCAPE_LL] = {
 231         ['d'] = IN_ESCAPE_DONE,
 232     },
 233
 234     [IN_ESCAPE_L] = {
 235         ['d'] = IN_ESCAPE_DONE,
 236         ['l'] = IN_ESCAPE_LL,
 237     },
 238
 239     [IN_ESCAPE_I64] = {
 240         ['d'] = IN_ESCAPE_DONE,
 241     },
 242
 243     [IN_ESCAPE_I6] = {
 244         ['4'] = IN_ESCAPE_I64,
 245     },
 246
 247     [IN_ESCAPE_I] = {
 248         ['6'] = IN_ESCAPE_I6,
 249     },
 250
 251     [IN_ESCAPE] = {
 252         ['d'] = IN_ESCAPE_DONE,
 253         ['i'] = IN_ESCAPE_DONE,
 254         ['p'] = IN_ESCAPE_DONE,
 255         ['s'] = IN_ESCAPE_DONE,
 256         ['f'] = IN_ESCAPE_DONE,
 257         ['l'] = IN_ESCAPE_L,
 258         ['I'] = IN_ESCAPE_I,
 259     },
 260
 261     /* top level rule */
 262     [IN_START] = {
 263         ['"'] = IN_DQ_STRING,
 264         ['\''] = IN_SQ_STRING,
 265         ['0'] = IN_ZERO,
 266         ['1' ... '9'] = IN_NONZERO_NUMBER,
 267         ['-'] = IN_NEG_NONZERO_NUMBER,
 268         ['{'] = IN_OPERATOR_DONE,
 269         ['}'] = IN_OPERATOR_DONE,
 270         ['['] = IN_OPERATOR_DONE,
 271         [']'] = IN_OPERATOR_DONE,
 272         [','] = IN_OPERATOR_DONE,
 273         [':'] = IN_OPERATOR_DONE,
 274         ['a' ... 'z'] = IN_KEYWORD,
 275         ['%'] = IN_ESCAPE,
 276         [' '] = IN_WHITESPACE,
 277         ['\t'] = IN_WHITESPACE,
 278         ['\r'] = IN_WHITESPACE,
 279         ['\n'] = IN_WHITESPACE,
 280     },
 281 };
 282
 283 void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func)
 284 {
 285     lexer->emit = func;
 286     lexer->state = IN_START;
 287     lexer->token = qstring_new();
 288     lexer->x = lexer->y = 0;
 289 }
 290
 291 static int json_lexer_feed_char(JSONLexer *lexer, char ch)
 292 {
 293     int char_consumed, new_state;
 294
 295     lexer->x++;
 296     if (ch == '\n') {
 297         lexer->x = 0;
 298         lexer->y++;
 299     }
 300
 301     do {
 302         new_state = json_lexer[lexer->state][(uint8_t)ch];
 303         char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state);
 304         if (char_consumed) {
 305             qstring_append_chr(lexer->token, ch);
 306         }
 307
 308         switch (new_state) {
 309         case JSON_OPERATOR:
 310         case JSON_ESCAPE:
 311         case JSON_INTEGER:
 312         case JSON_FLOAT:
 313         case JSON_KEYWORD:
 314         case JSON_STRING:
 315             lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y);
 316         case JSON_SKIP:
 317             QDECREF(lexer->token);
 318             lexer->token = qstring_new();
 319             new_state = IN_START;
 320             break;
 321         case ERROR:
 322             return -EINVAL;
 323         default:
 324             break;
 325         }
 326         lexer->state = new_state;
 327     } while (!char_consumed);
 328     return 0;
 329 }
 330
 331 int json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size)
 332 {
 333     size_t i;
 334
 335     for (i = 0; i < size; i++) {
 336         int err;
 337
 338         err = json_lexer_feed_char(lexer, buffer[i]);
 339         if (err < 0) {
 340             return err;
 341         }
 342     }
 343
 344     return 0;
 345 }
 346
 347 int json_lexer_flush(JSONLexer *lexer)
 348 {
 349     return lexer->state == IN_START ? 0 : json_lexer_feed_char(lexer, 0);
 350 }
 351
 352 void json_lexer_destroy(JSONLexer *lexer)
 353 {
 354     QDECREF(lexer->token);
 355 }