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