qobject/json-lexer.c

   1 /*
   2  * JSON lexer
   3  *
   4  * Copyright IBM, Corp. 2009
   5  *
   6  * Authors:
   7  *  Anthony Liguori   <[email protected]>
   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  *    [This lexer accepts any non-control character after escape, and
  84  *    leaves rejecting invalid ones to the parser.]
  85  *
  86  *
  87  * Extensions over RFC 8259:
  88  * - Extra escape sequence in strings:
  89  *   0x27 (apostrophe) is recognized after escape, too
  90  * - Single-quoted strings:
  91  *   Like double-quoted strings, except they're delimited by %x27
  92  *   (apostrophe) instead of %x22 (quotation mark), and can't contain
  93  *   unescaped apostrophe, but can contain unescaped quotation mark.
  94  * - Interpolation:
  95  *   interpolation = %((l|ll|I64)[du]|[ipsf])
  96  *
  97  * Note:
  98  * - Input must be encoded in modified UTF-8.
  99  * - Decoding and validating is left to the parser.
 100  */
 101
 102 enum json_lexer_state {
 103     IN_ERROR = 0,               /* must really be 0, see json_lexer[] */
 104     IN_DQ_STRING_ESCAPE,
 105     IN_DQ_STRING,
 106     IN_SQ_STRING_ESCAPE,
 107     IN_SQ_STRING,
 108     IN_ZERO,
 109     IN_DIGITS,
 110     IN_DIGIT,
 111     IN_EXP_E,
 112     IN_MANTISSA,
 113     IN_MANTISSA_DIGITS,
 114     IN_NONZERO_NUMBER,
 115     IN_NEG_NONZERO_NUMBER,
 116     IN_KEYWORD,
 117     IN_ESCAPE,
 118     IN_ESCAPE_L,
 119     IN_ESCAPE_LL,
 120     IN_ESCAPE_I,
 121     IN_ESCAPE_I6,
 122     IN_ESCAPE_I64,
 123     IN_WHITESPACE,
 124     IN_START,
 125 };
 126
 127 QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START);
 128
 129 #define TERMINAL(state) [0 ... 0x7F] = (state)
 130
 131 /* Return whether TERMINAL is a terminal state and the transition to it
 132    from OLD_STATE required lookahead.  This happens whenever the table
 133    below uses the TERMINAL macro.  */
 134 #define TERMINAL_NEEDED_LOOKAHEAD(old_state, terminal) \
 135     (terminal != IN_ERROR && json_lexer[(old_state)][0] == (terminal))
 136
 137 static const uint8_t json_lexer[][256] =  {
 138     /* Relies on default initialization to IN_ERROR! */
 139
 140     /* double quote string */
 141     [IN_DQ_STRING_ESCAPE] = {
 142         [0x20 ... 0xFD] = IN_DQ_STRING,
 143     },
 144     [IN_DQ_STRING] = {
 145         [0x20 ... 0xFD] = IN_DQ_STRING,
 146         ['\\'] = IN_DQ_STRING_ESCAPE,
 147         ['"'] = JSON_STRING,
 148     },
 149
 150     /* single quote string */
 151     [IN_SQ_STRING_ESCAPE] = {
 152         [0x20 ... 0xFD] = IN_SQ_STRING,
 153     },
 154     [IN_SQ_STRING] = {
 155         [0x20 ... 0xFD] = IN_SQ_STRING,
 156         ['\\'] = IN_SQ_STRING_ESCAPE,
 157         ['\''] = JSON_STRING,
 158     },
 159
 160     /* Zero */
 161     [IN_ZERO] = {
 162         TERMINAL(JSON_INTEGER),
 163         ['0' ... '9'] = IN_ERROR,
 164         ['.'] = IN_MANTISSA,
 165     },
 166
 167     /* Float */
 168     [IN_DIGITS] = {
 169         TERMINAL(JSON_FLOAT),
 170         ['0' ... '9'] = IN_DIGITS,
 171     },
 172
 173     [IN_DIGIT] = {
 174         ['0' ... '9'] = IN_DIGITS,
 175     },
 176
 177     [IN_EXP_E] = {
 178         ['-'] = IN_DIGIT,
 179         ['+'] = IN_DIGIT,
 180         ['0' ... '9'] = IN_DIGITS,
 181     },
 182
 183     [IN_MANTISSA_DIGITS] = {
 184         TERMINAL(JSON_FLOAT),
 185         ['0' ... '9'] = IN_MANTISSA_DIGITS,
 186         ['e'] = IN_EXP_E,
 187         ['E'] = IN_EXP_E,
 188     },
 189
 190     [IN_MANTISSA] = {
 191         ['0' ... '9'] = IN_MANTISSA_DIGITS,
 192     },
 193
 194     /* Number */
 195     [IN_NONZERO_NUMBER] = {
 196         TERMINAL(JSON_INTEGER),
 197         ['0' ... '9'] = IN_NONZERO_NUMBER,
 198         ['e'] = IN_EXP_E,
 199         ['E'] = IN_EXP_E,
 200         ['.'] = IN_MANTISSA,
 201     },
 202
 203     [IN_NEG_NONZERO_NUMBER] = {
 204         ['0'] = IN_ZERO,
 205         ['1' ... '9'] = IN_NONZERO_NUMBER,
 206     },
 207
 208     /* keywords */
 209     [IN_KEYWORD] = {
 210         TERMINAL(JSON_KEYWORD),
 211         ['a' ... 'z'] = IN_KEYWORD,
 212     },
 213
 214     /* whitespace */
 215     [IN_WHITESPACE] = {
 216         TERMINAL(JSON_SKIP),
 217         [' '] = IN_WHITESPACE,
 218         ['\t'] = IN_WHITESPACE,
 219         ['\r'] = IN_WHITESPACE,
 220         ['\n'] = IN_WHITESPACE,
 221     },
 222
 223     /* escape */
 224     [IN_ESCAPE_LL] = {
 225         ['d'] = JSON_ESCAPE,
 226         ['u'] = JSON_ESCAPE,
 227     },
 228
 229     [IN_ESCAPE_L] = {
 230         ['d'] = JSON_ESCAPE,
 231         ['l'] = IN_ESCAPE_LL,
 232         ['u'] = JSON_ESCAPE,
 233     },
 234
 235     [IN_ESCAPE_I64] = {
 236         ['d'] = JSON_ESCAPE,
 237         ['u'] = JSON_ESCAPE,
 238     },
 239
 240     [IN_ESCAPE_I6] = {
 241         ['4'] = IN_ESCAPE_I64,
 242     },
 243
 244     [IN_ESCAPE_I] = {
 245         ['6'] = IN_ESCAPE_I6,
 246     },
 247
 248     [IN_ESCAPE] = {
 249         ['d'] = JSON_ESCAPE,
 250         ['i'] = JSON_ESCAPE,
 251         ['p'] = JSON_ESCAPE,
 252         ['s'] = JSON_ESCAPE,
 253         ['u'] = JSON_ESCAPE,
 254         ['f'] = JSON_ESCAPE,
 255         ['l'] = IN_ESCAPE_L,
 256         ['I'] = IN_ESCAPE_I,
 257     },
 258
 259     /* top level rule */
 260     [IN_START] = {
 261         ['"'] = IN_DQ_STRING,
 262         ['\''] = IN_SQ_STRING,
 263         ['0'] = IN_ZERO,
 264         ['1' ... '9'] = IN_NONZERO_NUMBER,
 265         ['-'] = IN_NEG_NONZERO_NUMBER,
 266         ['{'] = JSON_LCURLY,
 267         ['}'] = JSON_RCURLY,
 268         ['['] = JSON_LSQUARE,
 269         [']'] = JSON_RSQUARE,
 270         [','] = JSON_COMMA,
 271         [':'] = JSON_COLON,
 272         ['a' ... 'z'] = IN_KEYWORD,
 273         ['%'] = IN_ESCAPE,
 274         [' '] = IN_WHITESPACE,
 275         ['\t'] = IN_WHITESPACE,
 276         ['\r'] = IN_WHITESPACE,
 277         ['\n'] = IN_WHITESPACE,
 278     },
 279 };
 280
 281 void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func)
 282 {
 283     lexer->emit = func;
 284     lexer->state = IN_START;
 285     lexer->token = g_string_sized_new(3);
 286     lexer->x = lexer->y = 0;
 287 }
 288
 289 static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
 290 {
 291     int char_consumed, new_state;
 292
 293     lexer->x++;
 294     if (ch == '\n') {
 295         lexer->x = 0;
 296         lexer->y++;
 297     }
 298
 299     do {
 300         assert(lexer->state <= ARRAY_SIZE(json_lexer));
 301         new_state = json_lexer[lexer->state][(uint8_t)ch];
 302         char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state);
 303         if (char_consumed && !flush) {
 304             g_string_append_c(lexer->token, ch);
 305         }
 306
 307         switch (new_state) {
 308         case JSON_LCURLY:
 309         case JSON_RCURLY:
 310         case JSON_LSQUARE:
 311         case JSON_RSQUARE:
 312         case JSON_COLON:
 313         case JSON_COMMA:
 314         case JSON_ESCAPE:
 315         case JSON_INTEGER:
 316         case JSON_FLOAT:
 317         case JSON_KEYWORD:
 318         case JSON_STRING:
 319             lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y);
 320             /* fall through */
 321         case JSON_SKIP:
 322             g_string_truncate(lexer->token, 0);
 323             new_state = IN_START;
 324             break;
 325         case IN_ERROR:
 326             /* XXX: To avoid having previous bad input leaving the parser in an
 327              * unresponsive state where we consume unpredictable amounts of
 328              * subsequent "good" input, percolate this error state up to the
 329              * tokenizer/parser by forcing a NULL object to be emitted, then
 330              * reset state.
 331              *
 332              * Also note that this handling is required for reliable channel
 333              * negotiation between QMP and the guest agent, since chr(0xFF)
 334              * is placed at the beginning of certain events to ensure proper
 335              * delivery when the channel is in an unknown state. chr(0xFF) is
 336              * never a valid ASCII/UTF-8 sequence, so this should reliably
 337              * induce an error/flush state.
 338              */
 339             lexer->emit(lexer, lexer->token, JSON_ERROR, lexer->x, lexer->y);
 340             g_string_truncate(lexer->token, 0);
 341             new_state = IN_START;
 342             lexer->state = new_state;
 343             return 0;
 344         default:
 345             break;
 346         }
 347         lexer->state = new_state;
 348     } while (!char_consumed && !flush);
 349
 350     /* Do not let a single token grow to an arbitrarily large size,
 351      * this is a security consideration.
 352      */
 353     if (lexer->token->len > MAX_TOKEN_SIZE) {
 354         lexer->emit(lexer, lexer->token, lexer->state, lexer->x, lexer->y);
 355         g_string_truncate(lexer->token, 0);
 356         lexer->state = IN_START;
 357     }
 358
 359     return 0;
 360 }
 361
 362 int json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size)
 363 {
 364     size_t i;
 365
 366     for (i = 0; i < size; i++) {
 367         int err;
 368
 369         err = json_lexer_feed_char(lexer, buffer[i], false);
 370         if (err < 0) {
 371             return err;
 372         }
 373     }
 374
 375     return 0;
 376 }
 377
 378 int json_lexer_flush(JSONLexer *lexer)
 379 {
 380     return lexer->state == IN_START ? 0 : json_lexer_feed_char(lexer, 0, true);
 381 }
 382
 383 void json_lexer_destroy(JSONLexer *lexer)
 384 {
 385     g_string_free(lexer->token, true);
 386 }