qobject/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 "qemu/osdep.h"
  15 #include "qemu-common.h"
  16 #include "qapi/qmp/json-lexer.h"
  17
  18 #define MAX_TOKEN_SIZE (64ULL << 20)
  19
  20 /*
  21  * From RFC 8259 "The JavaScript Object Notation (JSON) Data
  22  * Interchange Format", with [comments in brackets]:
  23  *
  24  * The set of tokens includes six structural characters, strings,
  25  * numbers, and three literal names.
  26  *
  27  * These are the six structural characters:
  28  *
  29  *    begin-array     = ws %x5B ws  ; [ left square bracket
  30  *    begin-object    = ws %x7B ws  ; { left curly bracket
  31  *    end-array       = ws %x5D ws  ; ] right square bracket
  32  *    end-object      = ws %x7D ws  ; } right curly bracket
  33  *    name-separator  = ws %x3A ws  ; : colon
  34  *    value-separator = ws %x2C ws  ; , comma
  35  *
  36  * Insignificant whitespace is allowed before or after any of the six
  37  * structural characters.
  38  * [This lexer accepts it before or after any token, which is actually
  39  * the same, as the grammar always has structural characters between
  40  * other tokens.]
  41  *
  42  *    ws = *(
  43  *           %x20 /              ; Space
  44  *           %x09 /              ; Horizontal tab
  45  *           %x0A /              ; Line feed or New line
  46  *           %x0D )              ; Carriage return
  47  *
  48  * [...] three literal names:
  49  *    false null true
  50  *  [This lexer accepts [a-z]+, and leaves rejecting unknown literal
  51  *  names to the parser.]
  52  *
  53  * [Numbers:]
  54  *
  55  *    number = [ minus ] int [ frac ] [ exp ]
  56  *    decimal-point = %x2E       ; .
  57  *    digit1-9 = %x31-39         ; 1-9
  58  *    e = %x65 / %x45            ; e E
  59  *    exp = e [ minus / plus ] 1*DIGIT
  60  *    frac = decimal-point 1*DIGIT
  61  *    int = zero / ( digit1-9 *DIGIT )
  62  *    minus = %x2D               ; -
  63  *    plus = %x2B                ; +
  64  *    zero = %x30                ; 0
  65  *
  66  * [Strings:]
  67  *    string = quotation-mark *char quotation-mark
  68  *
  69  *    char = unescaped /
  70  *        escape (
  71  *            %x22 /          ; "    quotation mark  U+0022
  72  *            %x5C /          ; \    reverse solidus U+005C
  73  *            %x2F /          ; /    solidus         U+002F
  74  *            %x62 /          ; b    backspace       U+0008
  75  *            %x66 /          ; f    form feed       U+000C
  76  *            %x6E /          ; n    line feed       U+000A
  77  *            %x72 /          ; r    carriage return U+000D
  78  *            %x74 /          ; t    tab             U+0009
  79  *            %x75 4HEXDIG )  ; uXXXX                U+XXXX
  80  *    escape = %x5C              ; \
  81  *    quotation-mark = %x22      ; "
  82  *    unescaped = %x20-21 / %x23-5B / %x5D-10FFFF
  83  *
  84  *
  85  * Extensions over RFC 8259:
  86  * - Extra escape sequence in strings:
  87  *   0x27 (apostrophe) is recognized after escape, too
  88  * - Single-quoted strings:
  89  *   Like double-quoted strings, except they're delimited by %x27
  90  *   (apostrophe) instead of %x22 (quotation mark), and can't contain
  91  *   unescaped apostrophe, but can contain unescaped quotation mark.
  92  * - Interpolation:
  93  *   interpolation = %((l|ll|I64)[du]|[ipsf])
  94  *
  95  * Note:
  96  * - Input must be encoded in UTF-8.
  97  * - Decoding and validating is left to the parser.
  98  */
  99
 100 enum json_lexer_state {
 101     IN_ERROR = 0,               /* must really be 0, see json_lexer[] */
 102     IN_DQ_UCODE3,
 103     IN_DQ_UCODE2,
 104     IN_DQ_UCODE1,
 105     IN_DQ_UCODE0,
 106     IN_DQ_STRING_ESCAPE,
 107     IN_DQ_STRING,
 108     IN_SQ_UCODE3,
 109     IN_SQ_UCODE2,
 110     IN_SQ_UCODE1,
 111     IN_SQ_UCODE0,
 112     IN_SQ_STRING_ESCAPE,
 113     IN_SQ_STRING,
 114     IN_ZERO,
 115     IN_DIGITS,
 116     IN_DIGIT,
 117     IN_EXP_E,
 118     IN_MANTISSA,
 119     IN_MANTISSA_DIGITS,
 120     IN_NONZERO_NUMBER,
 121     IN_NEG_NONZERO_NUMBER,
 122     IN_KEYWORD,
 123     IN_ESCAPE,
 124     IN_ESCAPE_L,
 125     IN_ESCAPE_LL,
 126     IN_ESCAPE_I,
 127     IN_ESCAPE_I6,
 128     IN_ESCAPE_I64,
 129     IN_WHITESPACE,
 130     IN_START,
 131 };
 132
 133 QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START);
 134
 135 #define TERMINAL(state) [0 ... 0x7F] = (state)
 136
 137 /* Return whether TERMINAL is a terminal state and the transition to it
 138    from OLD_STATE required lookahead.  This happens whenever the table
 139    below uses the TERMINAL macro.  */
 140 #define TERMINAL_NEEDED_LOOKAHEAD(old_state, terminal) \
 141     (terminal != IN_ERROR && json_lexer[(old_state)][0] == (terminal))
 142
 143 static const uint8_t json_lexer[][256] =  {
 144     /* Relies on default initialization to IN_ERROR! */
 145
 146     /* double quote string */
 147     [IN_DQ_UCODE3] = {
 148         ['0' ... '9'] = IN_DQ_STRING,
 149         ['a' ... 'f'] = IN_DQ_STRING,
 150         ['A' ... 'F'] = IN_DQ_STRING,
 151     },
 152     [IN_DQ_UCODE2] = {
 153         ['0' ... '9'] = IN_DQ_UCODE3,
 154         ['a' ... 'f'] = IN_DQ_UCODE3,
 155         ['A' ... 'F'] = IN_DQ_UCODE3,
 156     },
 157     [IN_DQ_UCODE1] = {
 158         ['0' ... '9'] = IN_DQ_UCODE2,
 159         ['a' ... 'f'] = IN_DQ_UCODE2,
 160         ['A' ... 'F'] = IN_DQ_UCODE2,
 161     },
 162     [IN_DQ_UCODE0] = {
 163         ['0' ... '9'] = IN_DQ_UCODE1,
 164         ['a' ... 'f'] = IN_DQ_UCODE1,
 165         ['A' ... 'F'] = IN_DQ_UCODE1,
 166     },
 167     [IN_DQ_STRING_ESCAPE] = {
 168         ['b'] = IN_DQ_STRING,
 169         ['f'] =  IN_DQ_STRING,
 170         ['n'] =  IN_DQ_STRING,
 171         ['r'] =  IN_DQ_STRING,
 172         ['t'] =  IN_DQ_STRING,
 173         ['/'] = IN_DQ_STRING,
 174         ['\\'] = IN_DQ_STRING,
 175         ['\''] = IN_DQ_STRING,
 176         ['\"'] = IN_DQ_STRING,
 177         ['u'] = IN_DQ_UCODE0,
 178     },
 179     [IN_DQ_STRING] = {
 180         [0x20 ... 0xFD] = IN_DQ_STRING,
 181         ['\\'] = IN_DQ_STRING_ESCAPE,
 182         ['"'] = JSON_STRING,
 183     },
 184
 185     /* single quote string */
 186     [IN_SQ_UCODE3] = {
 187         ['0' ... '9'] = IN_SQ_STRING,
 188         ['a' ... 'f'] = IN_SQ_STRING,
 189         ['A' ... 'F'] = IN_SQ_STRING,
 190     },
 191     [IN_SQ_UCODE2] = {
 192         ['0' ... '9'] = IN_SQ_UCODE3,
 193         ['a' ... 'f'] = IN_SQ_UCODE3,
 194         ['A' ... 'F'] = IN_SQ_UCODE3,
 195     },
 196     [IN_SQ_UCODE1] = {
 197         ['0' ... '9'] = IN_SQ_UCODE2,
 198         ['a' ... 'f'] = IN_SQ_UCODE2,
 199         ['A' ... 'F'] = IN_SQ_UCODE2,
 200     },
 201     [IN_SQ_UCODE0] = {
 202         ['0' ... '9'] = IN_SQ_UCODE1,
 203         ['a' ... 'f'] = IN_SQ_UCODE1,
 204         ['A' ... 'F'] = IN_SQ_UCODE1,
 205     },
 206     [IN_SQ_STRING_ESCAPE] = {
 207         ['b'] = IN_SQ_STRING,
 208         ['f'] =  IN_SQ_STRING,
 209         ['n'] =  IN_SQ_STRING,
 210         ['r'] =  IN_SQ_STRING,
 211         ['t'] =  IN_SQ_STRING,
 212         ['/'] = IN_SQ_STRING,
 213         ['\\'] = IN_SQ_STRING,
 214         ['\''] = IN_SQ_STRING,
 215         ['\"'] = IN_SQ_STRING,
 216         ['u'] = IN_SQ_UCODE0,
 217     },
 218     [IN_SQ_STRING] = {
 219         [0x20 ... 0xFD] = IN_SQ_STRING,
 220         ['\\'] = IN_SQ_STRING_ESCAPE,
 221         ['\''] = JSON_STRING,
 222     },
 223
 224     /* Zero */
 225     [IN_ZERO] = {
 226         TERMINAL(JSON_INTEGER),
 227         ['0' ... '9'] = IN_ERROR,
 228         ['.'] = IN_MANTISSA,
 229     },
 230
 231     /* Float */
 232     [IN_DIGITS] = {
 233         TERMINAL(JSON_FLOAT),
 234         ['0' ... '9'] = IN_DIGITS,
 235     },
 236
 237     [IN_DIGIT] = {
 238         ['0' ... '9'] = IN_DIGITS,
 239     },
 240
 241     [IN_EXP_E] = {
 242         ['-'] = IN_DIGIT,
 243         ['+'] = IN_DIGIT,
 244         ['0' ... '9'] = IN_DIGITS,
 245     },
 246
 247     [IN_MANTISSA_DIGITS] = {
 248         TERMINAL(JSON_FLOAT),
 249         ['0' ... '9'] = IN_MANTISSA_DIGITS,
 250         ['e'] = IN_EXP_E,
 251         ['E'] = IN_EXP_E,
 252     },
 253
 254     [IN_MANTISSA] = {
 255         ['0' ... '9'] = IN_MANTISSA_DIGITS,
 256     },
 257
 258     /* Number */
 259     [IN_NONZERO_NUMBER] = {
 260         TERMINAL(JSON_INTEGER),
 261         ['0' ... '9'] = IN_NONZERO_NUMBER,
 262         ['e'] = IN_EXP_E,
 263         ['E'] = IN_EXP_E,
 264         ['.'] = IN_MANTISSA,
 265     },
 266
 267     [IN_NEG_NONZERO_NUMBER] = {
 268         ['0'] = IN_ZERO,
 269         ['1' ... '9'] = IN_NONZERO_NUMBER,
 270     },
 271
 272     /* keywords */
 273     [IN_KEYWORD] = {
 274         TERMINAL(JSON_KEYWORD),
 275         ['a' ... 'z'] = IN_KEYWORD,
 276     },
 277
 278     /* whitespace */
 279     [IN_WHITESPACE] = {
 280         TERMINAL(JSON_SKIP),
 281         [' '] = IN_WHITESPACE,
 282         ['\t'] = IN_WHITESPACE,
 283         ['\r'] = IN_WHITESPACE,
 284         ['\n'] = IN_WHITESPACE,
 285     },
 286
 287     /* escape */
 288     [IN_ESCAPE_LL] = {
 289         ['d'] = JSON_ESCAPE,
 290         ['u'] = JSON_ESCAPE,
 291     },
 292
 293     [IN_ESCAPE_L] = {
 294         ['d'] = JSON_ESCAPE,
 295         ['l'] = IN_ESCAPE_LL,
 296         ['u'] = JSON_ESCAPE,
 297     },
 298
 299     [IN_ESCAPE_I64] = {
 300         ['d'] = JSON_ESCAPE,
 301         ['u'] = JSON_ESCAPE,
 302     },
 303
 304     [IN_ESCAPE_I6] = {
 305         ['4'] = IN_ESCAPE_I64,
 306     },
 307
 308     [IN_ESCAPE_I] = {
 309         ['6'] = IN_ESCAPE_I6,
 310     },
 311
 312     [IN_ESCAPE] = {
 313         ['d'] = JSON_ESCAPE,
 314         ['i'] = JSON_ESCAPE,
 315         ['p'] = JSON_ESCAPE,
 316         ['s'] = JSON_ESCAPE,
 317         ['u'] = JSON_ESCAPE,
 318         ['f'] = JSON_ESCAPE,
 319         ['l'] = IN_ESCAPE_L,
 320         ['I'] = IN_ESCAPE_I,
 321     },
 322
 323     /* top level rule */
 324     [IN_START] = {
 325         ['"'] = IN_DQ_STRING,
 326         ['\''] = IN_SQ_STRING,
 327         ['0'] = IN_ZERO,
 328         ['1' ... '9'] = IN_NONZERO_NUMBER,
 329         ['-'] = IN_NEG_NONZERO_NUMBER,
 330         ['{'] = JSON_LCURLY,
 331         ['}'] = JSON_RCURLY,
 332         ['['] = JSON_LSQUARE,
 333         [']'] = JSON_RSQUARE,
 334         [','] = JSON_COMMA,
 335         [':'] = JSON_COLON,
 336         ['a' ... 'z'] = IN_KEYWORD,
 337         ['%'] = IN_ESCAPE,
 338         [' '] = IN_WHITESPACE,
 339         ['\t'] = IN_WHITESPACE,
 340         ['\r'] = IN_WHITESPACE,
 341         ['\n'] = IN_WHITESPACE,
 342     },
 343 };
 344
 345 void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func)
 346 {
 347     lexer->emit = func;
 348     lexer->state = IN_START;
 349     lexer->token = g_string_sized_new(3);
 350     lexer->x = lexer->y = 0;
 351 }
 352
 353 static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
 354 {
 355     int char_consumed, new_state;
 356
 357     lexer->x++;
 358     if (ch == '\n') {
 359         lexer->x = 0;
 360         lexer->y++;
 361     }
 362
 363     do {
 364         assert(lexer->state <= ARRAY_SIZE(json_lexer));
 365         new_state = json_lexer[lexer->state][(uint8_t)ch];
 366         char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state);
 367         if (char_consumed && !flush) {
 368             g_string_append_c(lexer->token, ch);
 369         }
 370
 371         switch (new_state) {
 372         case JSON_LCURLY:
 373         case JSON_RCURLY:
 374         case JSON_LSQUARE:
 375         case JSON_RSQUARE:
 376         case JSON_COLON:
 377         case JSON_COMMA:
 378         case JSON_ESCAPE:
 379         case JSON_INTEGER:
 380         case JSON_FLOAT:
 381         case JSON_KEYWORD:
 382         case JSON_STRING:
 383             lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y);
 384             /* fall through */
 385         case JSON_SKIP:
 386             g_string_truncate(lexer->token, 0);
 387             new_state = IN_START;
 388             break;
 389         case IN_ERROR:
 390             /* XXX: To avoid having previous bad input leaving the parser in an
 391              * unresponsive state where we consume unpredictable amounts of
 392              * subsequent "good" input, percolate this error state up to the
 393              * tokenizer/parser by forcing a NULL object to be emitted, then
 394              * reset state.
 395              *
 396              * Also note that this handling is required for reliable channel
 397              * negotiation between QMP and the guest agent, since chr(0xFF)
 398              * is placed at the beginning of certain events to ensure proper
 399              * delivery when the channel is in an unknown state. chr(0xFF) is
 400              * never a valid ASCII/UTF-8 sequence, so this should reliably
 401              * induce an error/flush state.
 402              */
 403             lexer->emit(lexer, lexer->token, JSON_ERROR, lexer->x, lexer->y);
 404             g_string_truncate(lexer->token, 0);
 405             new_state = IN_START;
 406             lexer->state = new_state;
 407             return 0;
 408         default:
 409             break;
 410         }
 411         lexer->state = new_state;
 412     } while (!char_consumed && !flush);
 413
 414     /* Do not let a single token grow to an arbitrarily large size,
 415      * this is a security consideration.
 416      */
 417     if (lexer->token->len > MAX_TOKEN_SIZE) {
 418         lexer->emit(lexer, lexer->token, lexer->state, lexer->x, lexer->y);
 419         g_string_truncate(lexer->token, 0);
 420         lexer->state = IN_START;
 421     }
 422
 423     return 0;
 424 }
 425
 426 int json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size)
 427 {
 428     size_t i;
 429
 430     for (i = 0; i < size; i++) {
 431         int err;
 432
 433         err = json_lexer_feed_char(lexer, buffer[i], false);
 434         if (err < 0) {
 435             return err;
 436         }
 437     }
 438
 439     return 0;
 440 }
 441
 442 int json_lexer_flush(JSONLexer *lexer)
 443 {
 444     return lexer->state == IN_START ? 0 : json_lexer_feed_char(lexer, 0, true);
 445 }
 446
 447 void json_lexer_destroy(JSONLexer *lexer)
 448 {
 449     g_string_free(lexer->token, true);
 450 }