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 "qapi/qmp/qstring.h" 15 #include "qapi/qmp/qlist.h" 16 #include "qapi/qmp/qdict.h" 17 #include "qapi/qmp/qint.h" 18 #include "qemu-common.h" 19 #include "qapi/qmp/json-lexer.h" 20 21 #define MAX_TOKEN_SIZE (64ULL << 20) 22 23 /* 24 * \"([^\\\"]|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*\" 25 * '([^\\']|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*' 26 * 0|([1-9][0-9]*(.[0-9]+)?([eE]([-+])?[0-9]+)) 27 * [{}\[\],:] 28 * [a-z]+ 29 * 30 */ 31 32 enum json_lexer_state { 33 IN_ERROR = 0, /* must really be 0, see json_lexer[] */ 34 IN_DQ_UCODE3, 35 IN_DQ_UCODE2, 36 IN_DQ_UCODE1, 37 IN_DQ_UCODE0, 38 IN_DQ_STRING_ESCAPE, 39 IN_DQ_STRING, 40 IN_SQ_UCODE3, 41 IN_SQ_UCODE2, 42 IN_SQ_UCODE1, 43 IN_SQ_UCODE0, 44 IN_SQ_STRING_ESCAPE, 45 IN_SQ_STRING, 46 IN_ZERO, 47 IN_DIGITS, 48 IN_DIGIT, 49 IN_EXP_E, 50 IN_MANTISSA, 51 IN_MANTISSA_DIGITS, 52 IN_NONZERO_NUMBER, 53 IN_NEG_NONZERO_NUMBER, 54 IN_KEYWORD, 55 IN_ESCAPE, 56 IN_ESCAPE_L, 57 IN_ESCAPE_LL, 58 IN_ESCAPE_I, 59 IN_ESCAPE_I6, 60 IN_ESCAPE_I64, 61 IN_WHITESPACE, 62 IN_START, 63 }; 64 65 QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START); 66 67 #define TERMINAL(state) [0 ... 0x7F] = (state) 68 69 /* Return whether TERMINAL is a terminal state and the transition to it 70 from OLD_STATE required lookahead. This happens whenever the table 71 below uses the TERMINAL macro. */ 72 #define TERMINAL_NEEDED_LOOKAHEAD(old_state, terminal) \ 73 (json_lexer[(old_state)][0] == (terminal)) 74 75 static const uint8_t json_lexer[][256] = { 76 /* Relies on default initialization to IN_ERROR! */ 77 78 /* double quote string */ 79 [IN_DQ_UCODE3] = { 80 ['0' ... '9'] = IN_DQ_STRING, 81 ['a' ... 'f'] = IN_DQ_STRING, 82 ['A' ... 'F'] = IN_DQ_STRING, 83 }, 84 [IN_DQ_UCODE2] = { 85 ['0' ... '9'] = IN_DQ_UCODE3, 86 ['a' ... 'f'] = IN_DQ_UCODE3, 87 ['A' ... 'F'] = IN_DQ_UCODE3, 88 }, 89 [IN_DQ_UCODE1] = { 90 ['0' ... '9'] = IN_DQ_UCODE2, 91 ['a' ... 'f'] = IN_DQ_UCODE2, 92 ['A' ... 'F'] = IN_DQ_UCODE2, 93 }, 94 [IN_DQ_UCODE0] = { 95 ['0' ... '9'] = IN_DQ_UCODE1, 96 ['a' ... 'f'] = IN_DQ_UCODE1, 97 ['A' ... 'F'] = IN_DQ_UCODE1, 98 }, 99 [IN_DQ_STRING_ESCAPE] = { 100 ['b'] = IN_DQ_STRING, 101 ['f'] = IN_DQ_STRING, 102 ['n'] = IN_DQ_STRING, 103 ['r'] = IN_DQ_STRING, 104 ['t'] = IN_DQ_STRING, 105 ['/'] = IN_DQ_STRING, 106 ['\\'] = IN_DQ_STRING, 107 ['\''] = IN_DQ_STRING, 108 ['\"'] = IN_DQ_STRING, 109 ['u'] = IN_DQ_UCODE0, 110 }, 111 [IN_DQ_STRING] = { 112 [1 ... 0xBF] = IN_DQ_STRING, 113 [0xC2 ... 0xF4] = IN_DQ_STRING, 114 ['\\'] = IN_DQ_STRING_ESCAPE, 115 ['"'] = JSON_STRING, 116 }, 117 118 /* single quote string */ 119 [IN_SQ_UCODE3] = { 120 ['0' ... '9'] = IN_SQ_STRING, 121 ['a' ... 'f'] = IN_SQ_STRING, 122 ['A' ... 'F'] = IN_SQ_STRING, 123 }, 124 [IN_SQ_UCODE2] = { 125 ['0' ... '9'] = IN_SQ_UCODE3, 126 ['a' ... 'f'] = IN_SQ_UCODE3, 127 ['A' ... 'F'] = IN_SQ_UCODE3, 128 }, 129 [IN_SQ_UCODE1] = { 130 ['0' ... '9'] = IN_SQ_UCODE2, 131 ['a' ... 'f'] = IN_SQ_UCODE2, 132 ['A' ... 'F'] = IN_SQ_UCODE2, 133 }, 134 [IN_SQ_UCODE0] = { 135 ['0' ... '9'] = IN_SQ_UCODE1, 136 ['a' ... 'f'] = IN_SQ_UCODE1, 137 ['A' ... 'F'] = IN_SQ_UCODE1, 138 }, 139 [IN_SQ_STRING_ESCAPE] = { 140 ['b'] = IN_SQ_STRING, 141 ['f'] = IN_SQ_STRING, 142 ['n'] = IN_SQ_STRING, 143 ['r'] = IN_SQ_STRING, 144 ['t'] = IN_SQ_STRING, 145 ['/'] = IN_SQ_STRING, 146 ['\\'] = IN_SQ_STRING, 147 ['\''] = IN_SQ_STRING, 148 ['\"'] = IN_SQ_STRING, 149 ['u'] = IN_SQ_UCODE0, 150 }, 151 [IN_SQ_STRING] = { 152 [1 ... 0xBF] = IN_SQ_STRING, 153 [0xC2 ... 0xF4] = IN_SQ_STRING, 154 ['\\'] = IN_SQ_STRING_ESCAPE, 155 ['\''] = JSON_STRING, 156 }, 157 158 /* Zero */ 159 [IN_ZERO] = { 160 TERMINAL(JSON_INTEGER), 161 ['0' ... '9'] = IN_ERROR, 162 ['.'] = IN_MANTISSA, 163 }, 164 165 /* Float */ 166 [IN_DIGITS] = { 167 TERMINAL(JSON_FLOAT), 168 ['0' ... '9'] = IN_DIGITS, 169 }, 170 171 [IN_DIGIT] = { 172 ['0' ... '9'] = IN_DIGITS, 173 }, 174 175 [IN_EXP_E] = { 176 ['-'] = IN_DIGIT, 177 ['+'] = IN_DIGIT, 178 ['0' ... '9'] = IN_DIGITS, 179 }, 180 181 [IN_MANTISSA_DIGITS] = { 182 TERMINAL(JSON_FLOAT), 183 ['0' ... '9'] = IN_MANTISSA_DIGITS, 184 ['e'] = IN_EXP_E, 185 ['E'] = IN_EXP_E, 186 }, 187 188 [IN_MANTISSA] = { 189 ['0' ... '9'] = IN_MANTISSA_DIGITS, 190 }, 191 192 /* Number */ 193 [IN_NONZERO_NUMBER] = { 194 TERMINAL(JSON_INTEGER), 195 ['0' ... '9'] = IN_NONZERO_NUMBER, 196 ['e'] = IN_EXP_E, 197 ['E'] = IN_EXP_E, 198 ['.'] = IN_MANTISSA, 199 }, 200 201 [IN_NEG_NONZERO_NUMBER] = { 202 ['0'] = IN_ZERO, 203 ['1' ... '9'] = IN_NONZERO_NUMBER, 204 }, 205 206 /* keywords */ 207 [IN_KEYWORD] = { 208 TERMINAL(JSON_KEYWORD), 209 ['a' ... 'z'] = IN_KEYWORD, 210 }, 211 212 /* whitespace */ 213 [IN_WHITESPACE] = { 214 TERMINAL(JSON_SKIP), 215 [' '] = IN_WHITESPACE, 216 ['\t'] = IN_WHITESPACE, 217 ['\r'] = IN_WHITESPACE, 218 ['\n'] = IN_WHITESPACE, 219 }, 220 221 /* escape */ 222 [IN_ESCAPE_LL] = { 223 ['d'] = JSON_ESCAPE, 224 }, 225 226 [IN_ESCAPE_L] = { 227 ['d'] = JSON_ESCAPE, 228 ['l'] = IN_ESCAPE_LL, 229 }, 230 231 [IN_ESCAPE_I64] = { 232 ['d'] = JSON_ESCAPE, 233 }, 234 235 [IN_ESCAPE_I6] = { 236 ['4'] = IN_ESCAPE_I64, 237 }, 238 239 [IN_ESCAPE_I] = { 240 ['6'] = IN_ESCAPE_I6, 241 }, 242 243 [IN_ESCAPE] = { 244 ['d'] = JSON_ESCAPE, 245 ['i'] = JSON_ESCAPE, 246 ['p'] = JSON_ESCAPE, 247 ['s'] = JSON_ESCAPE, 248 ['f'] = JSON_ESCAPE, 249 ['l'] = IN_ESCAPE_L, 250 ['I'] = IN_ESCAPE_I, 251 }, 252 253 /* top level rule */ 254 [IN_START] = { 255 ['"'] = IN_DQ_STRING, 256 ['\''] = IN_SQ_STRING, 257 ['0'] = IN_ZERO, 258 ['1' ... '9'] = IN_NONZERO_NUMBER, 259 ['-'] = IN_NEG_NONZERO_NUMBER, 260 ['{'] = JSON_OPERATOR, 261 ['}'] = JSON_OPERATOR, 262 ['['] = JSON_OPERATOR, 263 [']'] = JSON_OPERATOR, 264 [','] = JSON_OPERATOR, 265 [':'] = JSON_OPERATOR, 266 ['a' ... 'z'] = IN_KEYWORD, 267 ['%'] = IN_ESCAPE, 268 [' '] = IN_WHITESPACE, 269 ['\t'] = IN_WHITESPACE, 270 ['\r'] = IN_WHITESPACE, 271 ['\n'] = IN_WHITESPACE, 272 }, 273 }; 274 275 void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func) 276 { 277 lexer->emit = func; 278 lexer->state = IN_START; 279 lexer->token = qstring_new(); 280 lexer->x = lexer->y = 0; 281 } 282 283 static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush) 284 { 285 int char_consumed, new_state; 286 287 lexer->x++; 288 if (ch == '\n') { 289 lexer->x = 0; 290 lexer->y++; 291 } 292 293 do { 294 assert(lexer->state <= ARRAY_SIZE(json_lexer)); 295 new_state = json_lexer[lexer->state][(uint8_t)ch]; 296 char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state); 297 if (char_consumed) { 298 qstring_append_chr(lexer->token, ch); 299 } 300 301 switch (new_state) { 302 case JSON_OPERATOR: 303 case JSON_ESCAPE: 304 case JSON_INTEGER: 305 case JSON_FLOAT: 306 case JSON_KEYWORD: 307 case JSON_STRING: 308 lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y); 309 /* fall through */ 310 case JSON_SKIP: 311 QDECREF(lexer->token); 312 lexer->token = qstring_new(); 313 new_state = IN_START; 314 break; 315 case IN_ERROR: 316 /* XXX: To avoid having previous bad input leaving the parser in an 317 * unresponsive state where we consume unpredictable amounts of 318 * subsequent "good" input, percolate this error state up to the 319 * tokenizer/parser by forcing a NULL object to be emitted, then 320 * reset state. 321 * 322 * Also note that this handling is required for reliable channel 323 * negotiation between QMP and the guest agent, since chr(0xFF) 324 * is placed at the beginning of certain events to ensure proper 325 * delivery when the channel is in an unknown state. chr(0xFF) is 326 * never a valid ASCII/UTF-8 sequence, so this should reliably 327 * induce an error/flush state. 328 */ 329 lexer->emit(lexer, lexer->token, JSON_ERROR, lexer->x, lexer->y); 330 QDECREF(lexer->token); 331 lexer->token = qstring_new(); 332 new_state = IN_START; 333 lexer->state = new_state; 334 return 0; 335 default: 336 break; 337 } 338 lexer->state = new_state; 339 } while (!char_consumed && !flush); 340 341 /* Do not let a single token grow to an arbitrarily large size, 342 * this is a security consideration. 343 */ 344 if (lexer->token->length > MAX_TOKEN_SIZE) { 345 lexer->emit(lexer, lexer->token, lexer->state, lexer->x, lexer->y); 346 QDECREF(lexer->token); 347 lexer->token = qstring_new(); 348 lexer->state = IN_START; 349 } 350 351 return 0; 352 } 353 354 int json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size) 355 { 356 size_t i; 357 358 for (i = 0; i < size; i++) { 359 int err; 360 361 err = json_lexer_feed_char(lexer, buffer[i], false); 362 if (err < 0) { 363 return err; 364 } 365 } 366 367 return 0; 368 } 369 370 int json_lexer_flush(JSONLexer *lexer) 371 { 372 return lexer->state == IN_START ? 0 : json_lexer_feed_char(lexer, 0, true); 373 } 374 375 void json_lexer_destroy(JSONLexer *lexer) 376 { 377 QDECREF(lexer->token); 378 } 379