]>
Commit | Line | Data |
---|---|---|
5ab8558d AL |
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 | ||
f2ad72b3 | 14 | #include "qemu/osdep.h" |
5ab8558d | 15 | #include "qemu-common.h" |
7b1b5d19 | 16 | #include "qapi/qmp/json-lexer.h" |
5ab8558d | 17 | |
325601b4 AL |
18 | #define MAX_TOKEN_SIZE (64ULL << 20) |
19 | ||
5ab8558d | 20 | /* |
eddc0a7f MA |
21 | * From RFC 8259 "The JavaScript Object Notation (JSON) Data |
22 | * Interchange Format", with [comments in brackets]: | |
ff5394ad | 23 | * |
eddc0a7f MA |
24 | * The set of tokens includes six structural characters, strings, |
25 | * numbers, and three literal names. | |
ff5394ad | 26 | * |
eddc0a7f | 27 | * These are the six structural characters: |
ff5394ad | 28 | * |
eddc0a7f MA |
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 | |
ff5394ad | 35 | * |
eddc0a7f MA |
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.] | |
ff5394ad | 41 | * |
eddc0a7f MA |
42 | * ws = *( |
43 | * %x20 / ; Space | |
44 | * %x09 / ; Horizontal tab | |
45 | * %x0A / ; Line feed or New line | |
46 | * %x0D ) ; Carriage return | |
5ab8558d | 47 | * |
eddc0a7f MA |
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 | * | |
84 | * | |
85 | * Extensions over RFC 8259: | |
86 | * - Extra escape sequence in strings: | |
87 | * 0x27 (apostrophe) is recognized after escape, too | |
88 | * - Single-quoted strings: | |
89 | * Like double-quoted strings, except they're delimited by %x27 | |
90 | * (apostrophe) instead of %x22 (quotation mark), and can't contain | |
91 | * unescaped apostrophe, but can contain unescaped quotation mark. | |
92 | * - Interpolation: | |
93 | * interpolation = %((l|ll|I64)[du]|[ipsf]) | |
94 | * | |
95 | * Note: | |
96 | * - Input must be encoded in UTF-8. | |
97 | * - Decoding and validating is left to the parser. | |
5ab8558d AL |
98 | */ |
99 | ||
100 | enum json_lexer_state { | |
b8d3b1da | 101 | IN_ERROR = 0, /* must really be 0, see json_lexer[] */ |
5ab8558d AL |
102 | IN_DQ_UCODE3, |
103 | IN_DQ_UCODE2, | |
104 | IN_DQ_UCODE1, | |
105 | IN_DQ_UCODE0, | |
106 | IN_DQ_STRING_ESCAPE, | |
107 | IN_DQ_STRING, | |
108 | IN_SQ_UCODE3, | |
109 | IN_SQ_UCODE2, | |
110 | IN_SQ_UCODE1, | |
111 | IN_SQ_UCODE0, | |
112 | IN_SQ_STRING_ESCAPE, | |
113 | IN_SQ_STRING, | |
114 | IN_ZERO, | |
115 | IN_DIGITS, | |
116 | IN_DIGIT, | |
117 | IN_EXP_E, | |
118 | IN_MANTISSA, | |
119 | IN_MANTISSA_DIGITS, | |
120 | IN_NONZERO_NUMBER, | |
121 | IN_NEG_NONZERO_NUMBER, | |
122 | IN_KEYWORD, | |
123 | IN_ESCAPE, | |
124 | IN_ESCAPE_L, | |
125 | IN_ESCAPE_LL, | |
2c0d4b36 RT |
126 | IN_ESCAPE_I, |
127 | IN_ESCAPE_I6, | |
128 | IN_ESCAPE_I64, | |
5ab8558d | 129 | IN_WHITESPACE, |
5ab8558d AL |
130 | IN_START, |
131 | }; | |
132 | ||
b8d3b1da MA |
133 | QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START); |
134 | ||
5ab8558d AL |
135 | #define TERMINAL(state) [0 ... 0x7F] = (state) |
136 | ||
f7c05274 PB |
137 | /* Return whether TERMINAL is a terminal state and the transition to it |
138 | from OLD_STATE required lookahead. This happens whenever the table | |
139 | below uses the TERMINAL macro. */ | |
140 | #define TERMINAL_NEEDED_LOOKAHEAD(old_state, terminal) \ | |
a2ec6be7 | 141 | (terminal != IN_ERROR && json_lexer[(old_state)][0] == (terminal)) |
f7c05274 | 142 | |
5ab8558d | 143 | static const uint8_t json_lexer[][256] = { |
b8d3b1da MA |
144 | /* Relies on default initialization to IN_ERROR! */ |
145 | ||
5ab8558d AL |
146 | /* double quote string */ |
147 | [IN_DQ_UCODE3] = { | |
148 | ['0' ... '9'] = IN_DQ_STRING, | |
149 | ['a' ... 'f'] = IN_DQ_STRING, | |
150 | ['A' ... 'F'] = IN_DQ_STRING, | |
151 | }, | |
152 | [IN_DQ_UCODE2] = { | |
153 | ['0' ... '9'] = IN_DQ_UCODE3, | |
154 | ['a' ... 'f'] = IN_DQ_UCODE3, | |
155 | ['A' ... 'F'] = IN_DQ_UCODE3, | |
156 | }, | |
157 | [IN_DQ_UCODE1] = { | |
158 | ['0' ... '9'] = IN_DQ_UCODE2, | |
159 | ['a' ... 'f'] = IN_DQ_UCODE2, | |
160 | ['A' ... 'F'] = IN_DQ_UCODE2, | |
161 | }, | |
162 | [IN_DQ_UCODE0] = { | |
163 | ['0' ... '9'] = IN_DQ_UCODE1, | |
164 | ['a' ... 'f'] = IN_DQ_UCODE1, | |
165 | ['A' ... 'F'] = IN_DQ_UCODE1, | |
166 | }, | |
167 | [IN_DQ_STRING_ESCAPE] = { | |
168 | ['b'] = IN_DQ_STRING, | |
169 | ['f'] = IN_DQ_STRING, | |
170 | ['n'] = IN_DQ_STRING, | |
171 | ['r'] = IN_DQ_STRING, | |
172 | ['t'] = IN_DQ_STRING, | |
1041ba7a LC |
173 | ['/'] = IN_DQ_STRING, |
174 | ['\\'] = IN_DQ_STRING, | |
5ab8558d AL |
175 | ['\''] = IN_DQ_STRING, |
176 | ['\"'] = IN_DQ_STRING, | |
177 | ['u'] = IN_DQ_UCODE0, | |
178 | }, | |
179 | [IN_DQ_STRING] = { | |
de930f45 | 180 | [0x20 ... 0xFD] = IN_DQ_STRING, |
5ab8558d | 181 | ['\\'] = IN_DQ_STRING_ESCAPE, |
28e91a68 | 182 | ['"'] = JSON_STRING, |
5ab8558d AL |
183 | }, |
184 | ||
185 | /* single quote string */ | |
186 | [IN_SQ_UCODE3] = { | |
187 | ['0' ... '9'] = IN_SQ_STRING, | |
188 | ['a' ... 'f'] = IN_SQ_STRING, | |
189 | ['A' ... 'F'] = IN_SQ_STRING, | |
190 | }, | |
191 | [IN_SQ_UCODE2] = { | |
192 | ['0' ... '9'] = IN_SQ_UCODE3, | |
193 | ['a' ... 'f'] = IN_SQ_UCODE3, | |
194 | ['A' ... 'F'] = IN_SQ_UCODE3, | |
195 | }, | |
196 | [IN_SQ_UCODE1] = { | |
197 | ['0' ... '9'] = IN_SQ_UCODE2, | |
198 | ['a' ... 'f'] = IN_SQ_UCODE2, | |
199 | ['A' ... 'F'] = IN_SQ_UCODE2, | |
200 | }, | |
201 | [IN_SQ_UCODE0] = { | |
202 | ['0' ... '9'] = IN_SQ_UCODE1, | |
203 | ['a' ... 'f'] = IN_SQ_UCODE1, | |
204 | ['A' ... 'F'] = IN_SQ_UCODE1, | |
205 | }, | |
206 | [IN_SQ_STRING_ESCAPE] = { | |
207 | ['b'] = IN_SQ_STRING, | |
208 | ['f'] = IN_SQ_STRING, | |
209 | ['n'] = IN_SQ_STRING, | |
210 | ['r'] = IN_SQ_STRING, | |
211 | ['t'] = IN_SQ_STRING, | |
d5932334 PB |
212 | ['/'] = IN_SQ_STRING, |
213 | ['\\'] = IN_SQ_STRING, | |
5ab8558d AL |
214 | ['\''] = IN_SQ_STRING, |
215 | ['\"'] = IN_SQ_STRING, | |
216 | ['u'] = IN_SQ_UCODE0, | |
217 | }, | |
218 | [IN_SQ_STRING] = { | |
de930f45 | 219 | [0x20 ... 0xFD] = IN_SQ_STRING, |
5ab8558d | 220 | ['\\'] = IN_SQ_STRING_ESCAPE, |
28e91a68 | 221 | ['\''] = JSON_STRING, |
5ab8558d AL |
222 | }, |
223 | ||
224 | /* Zero */ | |
225 | [IN_ZERO] = { | |
226 | TERMINAL(JSON_INTEGER), | |
33d05394 | 227 | ['0' ... '9'] = IN_ERROR, |
5ab8558d AL |
228 | ['.'] = IN_MANTISSA, |
229 | }, | |
230 | ||
231 | /* Float */ | |
232 | [IN_DIGITS] = { | |
233 | TERMINAL(JSON_FLOAT), | |
234 | ['0' ... '9'] = IN_DIGITS, | |
235 | }, | |
236 | ||
237 | [IN_DIGIT] = { | |
238 | ['0' ... '9'] = IN_DIGITS, | |
239 | }, | |
240 | ||
241 | [IN_EXP_E] = { | |
242 | ['-'] = IN_DIGIT, | |
243 | ['+'] = IN_DIGIT, | |
244 | ['0' ... '9'] = IN_DIGITS, | |
245 | }, | |
246 | ||
247 | [IN_MANTISSA_DIGITS] = { | |
248 | TERMINAL(JSON_FLOAT), | |
249 | ['0' ... '9'] = IN_MANTISSA_DIGITS, | |
250 | ['e'] = IN_EXP_E, | |
251 | ['E'] = IN_EXP_E, | |
252 | }, | |
253 | ||
254 | [IN_MANTISSA] = { | |
255 | ['0' ... '9'] = IN_MANTISSA_DIGITS, | |
256 | }, | |
257 | ||
258 | /* Number */ | |
259 | [IN_NONZERO_NUMBER] = { | |
260 | TERMINAL(JSON_INTEGER), | |
261 | ['0' ... '9'] = IN_NONZERO_NUMBER, | |
262 | ['e'] = IN_EXP_E, | |
263 | ['E'] = IN_EXP_E, | |
264 | ['.'] = IN_MANTISSA, | |
265 | }, | |
266 | ||
267 | [IN_NEG_NONZERO_NUMBER] = { | |
268 | ['0'] = IN_ZERO, | |
269 | ['1' ... '9'] = IN_NONZERO_NUMBER, | |
270 | }, | |
271 | ||
272 | /* keywords */ | |
273 | [IN_KEYWORD] = { | |
274 | TERMINAL(JSON_KEYWORD), | |
275 | ['a' ... 'z'] = IN_KEYWORD, | |
276 | }, | |
277 | ||
278 | /* whitespace */ | |
279 | [IN_WHITESPACE] = { | |
280 | TERMINAL(JSON_SKIP), | |
281 | [' '] = IN_WHITESPACE, | |
282 | ['\t'] = IN_WHITESPACE, | |
283 | ['\r'] = IN_WHITESPACE, | |
284 | ['\n'] = IN_WHITESPACE, | |
ff5394ad | 285 | }, |
5ab8558d | 286 | |
5ab8558d | 287 | /* escape */ |
5ab8558d | 288 | [IN_ESCAPE_LL] = { |
28e91a68 | 289 | ['d'] = JSON_ESCAPE, |
2bc7cfea | 290 | ['u'] = JSON_ESCAPE, |
5ab8558d AL |
291 | }, |
292 | ||
293 | [IN_ESCAPE_L] = { | |
28e91a68 | 294 | ['d'] = JSON_ESCAPE, |
5ab8558d | 295 | ['l'] = IN_ESCAPE_LL, |
2bc7cfea | 296 | ['u'] = JSON_ESCAPE, |
5ab8558d AL |
297 | }, |
298 | ||
2c0d4b36 | 299 | [IN_ESCAPE_I64] = { |
28e91a68 | 300 | ['d'] = JSON_ESCAPE, |
2bc7cfea | 301 | ['u'] = JSON_ESCAPE, |
2c0d4b36 RT |
302 | }, |
303 | ||
304 | [IN_ESCAPE_I6] = { | |
305 | ['4'] = IN_ESCAPE_I64, | |
306 | }, | |
307 | ||
308 | [IN_ESCAPE_I] = { | |
309 | ['6'] = IN_ESCAPE_I6, | |
310 | }, | |
311 | ||
5ab8558d | 312 | [IN_ESCAPE] = { |
28e91a68 PB |
313 | ['d'] = JSON_ESCAPE, |
314 | ['i'] = JSON_ESCAPE, | |
315 | ['p'] = JSON_ESCAPE, | |
316 | ['s'] = JSON_ESCAPE, | |
2bc7cfea | 317 | ['u'] = JSON_ESCAPE, |
28e91a68 | 318 | ['f'] = JSON_ESCAPE, |
5ab8558d | 319 | ['l'] = IN_ESCAPE_L, |
2c0d4b36 | 320 | ['I'] = IN_ESCAPE_I, |
5ab8558d AL |
321 | }, |
322 | ||
323 | /* top level rule */ | |
324 | [IN_START] = { | |
325 | ['"'] = IN_DQ_STRING, | |
326 | ['\''] = IN_SQ_STRING, | |
327 | ['0'] = IN_ZERO, | |
328 | ['1' ... '9'] = IN_NONZERO_NUMBER, | |
329 | ['-'] = IN_NEG_NONZERO_NUMBER, | |
c5461660 MA |
330 | ['{'] = JSON_LCURLY, |
331 | ['}'] = JSON_RCURLY, | |
332 | ['['] = JSON_LSQUARE, | |
333 | [']'] = JSON_RSQUARE, | |
334 | [','] = JSON_COMMA, | |
335 | [':'] = JSON_COLON, | |
5ab8558d AL |
336 | ['a' ... 'z'] = IN_KEYWORD, |
337 | ['%'] = IN_ESCAPE, | |
338 | [' '] = IN_WHITESPACE, | |
339 | ['\t'] = IN_WHITESPACE, | |
340 | ['\r'] = IN_WHITESPACE, | |
341 | ['\n'] = IN_WHITESPACE, | |
342 | }, | |
343 | }; | |
344 | ||
345 | void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func) | |
346 | { | |
347 | lexer->emit = func; | |
348 | lexer->state = IN_START; | |
d2ca7c0b | 349 | lexer->token = g_string_sized_new(3); |
03308f6c | 350 | lexer->x = lexer->y = 0; |
5ab8558d AL |
351 | } |
352 | ||
bd3924a3 | 353 | static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush) |
5ab8558d | 354 | { |
f7c05274 PB |
355 | int char_consumed, new_state; |
356 | ||
5ab8558d AL |
357 | lexer->x++; |
358 | if (ch == '\n') { | |
359 | lexer->x = 0; | |
360 | lexer->y++; | |
361 | } | |
362 | ||
f7c05274 | 363 | do { |
b8d3b1da | 364 | assert(lexer->state <= ARRAY_SIZE(json_lexer)); |
f7c05274 PB |
365 | new_state = json_lexer[lexer->state][(uint8_t)ch]; |
366 | char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state); | |
a2ec6be7 | 367 | if (char_consumed && !flush) { |
d2ca7c0b | 368 | g_string_append_c(lexer->token, ch); |
f7c05274 | 369 | } |
5ab8558d | 370 | |
f7c05274 | 371 | switch (new_state) { |
c5461660 MA |
372 | case JSON_LCURLY: |
373 | case JSON_RCURLY: | |
374 | case JSON_LSQUARE: | |
375 | case JSON_RSQUARE: | |
376 | case JSON_COLON: | |
377 | case JSON_COMMA: | |
f7c05274 PB |
378 | case JSON_ESCAPE: |
379 | case JSON_INTEGER: | |
380 | case JSON_FLOAT: | |
381 | case JSON_KEYWORD: | |
382 | case JSON_STRING: | |
383 | lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y); | |
0b0404bf | 384 | /* fall through */ |
f7c05274 | 385 | case JSON_SKIP: |
d2ca7c0b | 386 | g_string_truncate(lexer->token, 0); |
f7c05274 PB |
387 | new_state = IN_START; |
388 | break; | |
33d05394 | 389 | case IN_ERROR: |
b011f619 MR |
390 | /* XXX: To avoid having previous bad input leaving the parser in an |
391 | * unresponsive state where we consume unpredictable amounts of | |
392 | * subsequent "good" input, percolate this error state up to the | |
393 | * tokenizer/parser by forcing a NULL object to be emitted, then | |
394 | * reset state. | |
395 | * | |
396 | * Also note that this handling is required for reliable channel | |
397 | * negotiation between QMP and the guest agent, since chr(0xFF) | |
398 | * is placed at the beginning of certain events to ensure proper | |
399 | * delivery when the channel is in an unknown state. chr(0xFF) is | |
400 | * never a valid ASCII/UTF-8 sequence, so this should reliably | |
401 | * induce an error/flush state. | |
402 | */ | |
403 | lexer->emit(lexer, lexer->token, JSON_ERROR, lexer->x, lexer->y); | |
d2ca7c0b | 404 | g_string_truncate(lexer->token, 0); |
529a0ef5 | 405 | new_state = IN_START; |
b011f619 MR |
406 | lexer->state = new_state; |
407 | return 0; | |
f7c05274 PB |
408 | default: |
409 | break; | |
410 | } | |
411 | lexer->state = new_state; | |
bd3924a3 | 412 | } while (!char_consumed && !flush); |
325601b4 AL |
413 | |
414 | /* Do not let a single token grow to an arbitrarily large size, | |
415 | * this is a security consideration. | |
416 | */ | |
d2ca7c0b | 417 | if (lexer->token->len > MAX_TOKEN_SIZE) { |
325601b4 | 418 | lexer->emit(lexer, lexer->token, lexer->state, lexer->x, lexer->y); |
d2ca7c0b | 419 | g_string_truncate(lexer->token, 0); |
325601b4 AL |
420 | lexer->state = IN_START; |
421 | } | |
422 | ||
5ab8558d AL |
423 | return 0; |
424 | } | |
425 | ||
426 | int json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size) | |
427 | { | |
428 | size_t i; | |
429 | ||
430 | for (i = 0; i < size; i++) { | |
431 | int err; | |
432 | ||
bd3924a3 | 433 | err = json_lexer_feed_char(lexer, buffer[i], false); |
5ab8558d AL |
434 | if (err < 0) { |
435 | return err; | |
436 | } | |
437 | } | |
438 | ||
439 | return 0; | |
440 | } | |
441 | ||
442 | int json_lexer_flush(JSONLexer *lexer) | |
443 | { | |
b011f619 | 444 | return lexer->state == IN_START ? 0 : json_lexer_feed_char(lexer, 0, true); |
5ab8558d AL |
445 | } |
446 | ||
447 | void json_lexer_destroy(JSONLexer *lexer) | |
448 | { | |
d2ca7c0b | 449 | g_string_free(lexer->token, true); |
5ab8558d | 450 | } |