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 "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_RECOVERY = 1,
 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_START,
 119     IN_START_INTERP,            /* must be IN_START + 1 */
 120 };
 121
 122 QEMU_BUILD_BUG_ON(JSON_ERROR != 0);
 123 QEMU_BUILD_BUG_ON(IN_RECOVERY != JSON_ERROR + 1);
 124 QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START_INTERP);
 125 QEMU_BUILD_BUG_ON(JSON_MAX >= 0x80);
 126 QEMU_BUILD_BUG_ON(IN_START_INTERP != IN_START + 1);
 127
 128 #define LOOKAHEAD 0x80
 129 #define TERMINAL(state) [0 ... 0xFF] = ((state) | LOOKAHEAD)
 130
 131 static const uint8_t json_lexer[][256] =  {
 132     /* Relies on default initialization to IN_ERROR! */
 133
 134     /* error recovery */
 135     [IN_RECOVERY] = {
 136         /*
 137          * Skip characters until a structural character, an ASCII
 138          * control character other than '\t', or impossible UTF-8
 139          * bytes '\xFE', '\xFF'.  Structural characters and line
 140          * endings are promising resynchronization points.  Clients
 141          * may use the others to force the JSON parser into known-good
 142          * state; see docs/interop/qmp-spec.rst.
 143          */
 144         [0 ... 0x1F] = IN_START | LOOKAHEAD,
 145         [0x20 ... 0xFD] = IN_RECOVERY,
 146         [0xFE ... 0xFF] = IN_START | LOOKAHEAD,
 147         ['\t'] = IN_RECOVERY,
 148         ['['] = IN_START | LOOKAHEAD,
 149         [']'] = IN_START | LOOKAHEAD,
 150         ['{'] = IN_START | LOOKAHEAD,
 151         ['}'] = IN_START | LOOKAHEAD,
 152         [':'] = IN_START | LOOKAHEAD,
 153         [','] = IN_START | LOOKAHEAD,
 154     },
 155
 156     /* double quote string */
 157     [IN_DQ_STRING_ESCAPE] = {
 158         [0x20 ... 0xFD] = IN_DQ_STRING,
 159     },
 160     [IN_DQ_STRING] = {
 161         [0x20 ... 0xFD] = IN_DQ_STRING,
 162         ['\\'] = IN_DQ_STRING_ESCAPE,
 163         ['"'] = JSON_STRING,
 164     },
 165
 166     /* single quote string */
 167     [IN_SQ_STRING_ESCAPE] = {
 168         [0x20 ... 0xFD] = IN_SQ_STRING,
 169     },
 170     [IN_SQ_STRING] = {
 171         [0x20 ... 0xFD] = IN_SQ_STRING,
 172         ['\\'] = IN_SQ_STRING_ESCAPE,
 173         ['\''] = JSON_STRING,
 174     },
 175
 176     /* Zero */
 177     [IN_ZERO] = {
 178         TERMINAL(JSON_INTEGER),
 179         ['0' ... '9'] = JSON_ERROR,
 180         ['.'] = IN_MANTISSA,
 181     },
 182
 183     /* Float */
 184     [IN_EXP_DIGITS] = {
 185         TERMINAL(JSON_FLOAT),
 186         ['0' ... '9'] = IN_EXP_DIGITS,
 187     },
 188
 189     [IN_EXP_SIGN] = {
 190         ['0' ... '9'] = IN_EXP_DIGITS,
 191     },
 192
 193     [IN_EXP_E] = {
 194         ['-'] = IN_EXP_SIGN,
 195         ['+'] = IN_EXP_SIGN,
 196         ['0' ... '9'] = IN_EXP_DIGITS,
 197     },
 198
 199     [IN_MANTISSA_DIGITS] = {
 200         TERMINAL(JSON_FLOAT),
 201         ['0' ... '9'] = IN_MANTISSA_DIGITS,
 202         ['e'] = IN_EXP_E,
 203         ['E'] = IN_EXP_E,
 204     },
 205
 206     [IN_MANTISSA] = {
 207         ['0' ... '9'] = IN_MANTISSA_DIGITS,
 208     },
 209
 210     /* Number */
 211     [IN_DIGITS] = {
 212         TERMINAL(JSON_INTEGER),
 213         ['0' ... '9'] = IN_DIGITS,
 214         ['e'] = IN_EXP_E,
 215         ['E'] = IN_EXP_E,
 216         ['.'] = IN_MANTISSA,
 217     },
 218
 219     [IN_SIGN] = {
 220         ['0'] = IN_ZERO,
 221         ['1' ... '9'] = IN_DIGITS,
 222     },
 223
 224     /* keywords */
 225     [IN_KEYWORD] = {
 226         TERMINAL(JSON_KEYWORD),
 227         ['a' ... 'z'] = IN_KEYWORD,
 228     },
 229
 230     /* interpolation */
 231     [IN_INTERP] = {
 232         TERMINAL(JSON_INTERP),
 233         ['A' ... 'Z'] = IN_INTERP,
 234         ['a' ... 'z'] = IN_INTERP,
 235         ['0' ... '9'] = IN_INTERP,
 236     },
 237
 238     /*
 239      * Two start states:
 240      * - IN_START recognizes JSON tokens with our string extensions
 241      * - IN_START_INTERP additionally recognizes interpolation.
 242      */
 243     [IN_START ... IN_START_INTERP] = {
 244         ['"'] = IN_DQ_STRING,
 245         ['\''] = IN_SQ_STRING,
 246         ['0'] = IN_ZERO,
 247         ['1' ... '9'] = IN_DIGITS,
 248         ['-'] = IN_SIGN,
 249         ['{'] = JSON_LCURLY,
 250         ['}'] = JSON_RCURLY,
 251         ['['] = JSON_LSQUARE,
 252         [']'] = JSON_RSQUARE,
 253         [','] = JSON_COMMA,
 254         [':'] = JSON_COLON,
 255         ['a' ... 'z'] = IN_KEYWORD,
 256         [' '] = IN_START,
 257         ['\t'] = IN_START,
 258         ['\r'] = IN_START,
 259         ['\n'] = IN_START,
 260     },
 261     [IN_START_INTERP]['%'] = IN_INTERP,
 262 };
 263
 264 static inline uint8_t next_state(JSONLexer *lexer, char ch, bool flush,
 265                                  bool *char_consumed)
 266 {
 267     uint8_t next;
 268
 269     assert(lexer->state < ARRAY_SIZE(json_lexer));
 270     next = json_lexer[lexer->state][(uint8_t)ch];
 271     *char_consumed = !flush && !(next & LOOKAHEAD);
 272     return next & ~LOOKAHEAD;
 273 }
 274
 275 void json_lexer_init(JSONLexer *lexer, bool enable_interpolation)
 276 {
 277     lexer->start_state = lexer->state = enable_interpolation
 278         ? IN_START_INTERP : IN_START;
 279     lexer->token = g_string_sized_new(3);
 280     lexer->x = lexer->y = 0;
 281 }
 282
 283 static void json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
 284 {
 285     int new_state;
 286     bool char_consumed = false;
 287
 288     lexer->x++;
 289     if (ch == '\n') {
 290         lexer->x = 0;
 291         lexer->y++;
 292     }
 293
 294     while (flush ? lexer->state != lexer->start_state : !char_consumed) {
 295         new_state = next_state(lexer, ch, flush, &char_consumed);
 296         if (char_consumed) {
 297             assert(!flush);
 298             g_string_append_c(lexer->token, ch);
 299         }
 300
 301         switch (new_state) {
 302         case JSON_LCURLY:
 303         case JSON_RCURLY:
 304         case JSON_LSQUARE:
 305         case JSON_RSQUARE:
 306         case JSON_COLON:
 307         case JSON_COMMA:
 308         case JSON_INTERP:
 309         case JSON_INTEGER:
 310         case JSON_FLOAT:
 311         case JSON_KEYWORD:
 312         case JSON_STRING:
 313             json_message_process_token(lexer, lexer->token, new_state,
 314                                        lexer->x, lexer->y);
 315             /* fall through */
 316         case IN_START:
 317             g_string_truncate(lexer->token, 0);
 318             new_state = lexer->start_state;
 319             break;
 320         case JSON_ERROR:
 321             json_message_process_token(lexer, lexer->token, JSON_ERROR,
 322                                        lexer->x, lexer->y);
 323             new_state = IN_RECOVERY;
 324             /* fall through */
 325         case IN_RECOVERY:
 326             g_string_truncate(lexer->token, 0);
 327             break;
 328         default:
 329             break;
 330         }
 331         lexer->state = new_state;
 332     }
 333
 334     /* Do not let a single token grow to an arbitrarily large size,
 335      * this is a security consideration.
 336      */
 337     if (lexer->token->len > MAX_TOKEN_SIZE) {
 338         json_message_process_token(lexer, lexer->token, lexer->state,
 339                                    lexer->x, lexer->y);
 340         g_string_truncate(lexer->token, 0);
 341         lexer->state = lexer->start_state;
 342     }
 343 }
 344
 345 void json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size)
 346 {
 347     size_t i;
 348
 349     for (i = 0; i < size; i++) {
 350         json_lexer_feed_char(lexer, buffer[i], false);
 351     }
 352 }
 353
 354 void json_lexer_flush(JSONLexer *lexer)
 355 {
 356     json_lexer_feed_char(lexer, 0, true);
 357     assert(lexer->state == lexer->start_state);
 358     json_message_process_token(lexer, lexer->token, JSON_END_OF_INPUT,
 359                                lexer->x, lexer->y);
 360 }
 361
 362 void json_lexer_destroy(JSONLexer *lexer)
 363 {
 364     g_string_free(lexer->token, true);
 365 }