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