]>
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" |
86cdf9ec | 15 | #include "json-parser-int.h" |
5ab8558d | 16 | |
325601b4 AL |
17 | #define MAX_TOKEN_SIZE (64ULL << 20) |
18 | ||
5ab8558d | 19 | /* |
eddc0a7f MA |
20 | * From RFC 8259 "The JavaScript Object Notation (JSON) Data |
21 | * Interchange Format", with [comments in brackets]: | |
ff5394ad | 22 | * |
eddc0a7f MA |
23 | * The set of tokens includes six structural characters, strings, |
24 | * numbers, and three literal names. | |
ff5394ad | 25 | * |
eddc0a7f | 26 | * These are the six structural characters: |
ff5394ad | 27 | * |
eddc0a7f MA |
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 | |
ff5394ad | 34 | * |
eddc0a7f MA |
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.] | |
ff5394ad | 40 | * |
eddc0a7f MA |
41 | * ws = *( |
42 | * %x20 / ; Space | |
43 | * %x09 / ; Horizontal tab | |
44 | * %x0A / ; Line feed or New line | |
45 | * %x0D ) ; Carriage return | |
5ab8558d | 46 | * |
eddc0a7f MA |
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 | |
b2da4a4d MA |
82 | * [This lexer accepts any non-control character after escape, and |
83 | * leaves rejecting invalid ones to the parser.] | |
eddc0a7f MA |
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. | |
2cbd15aa | 93 | * - Interpolation, if enabled: |
f7617d45 MA |
94 | * The lexer accepts %[A-Za-z0-9]*, and leaves rejecting invalid |
95 | * ones to the parser. | |
eddc0a7f MA |
96 | * |
97 | * Note: | |
4b1c0cd7 | 98 | * - Input must be encoded in modified UTF-8. |
eddc0a7f | 99 | * - Decoding and validating is left to the parser. |
5ab8558d AL |
100 | */ |
101 | ||
102 | enum json_lexer_state { | |
b8d3b1da | 103 | IN_ERROR = 0, /* must really be 0, see json_lexer[] */ |
5ab8558d AL |
104 | IN_DQ_STRING_ESCAPE, |
105 | IN_DQ_STRING, | |
5ab8558d AL |
106 | IN_SQ_STRING_ESCAPE, |
107 | IN_SQ_STRING, | |
108 | IN_ZERO, | |
4d400661 MA |
109 | IN_EXP_DIGITS, |
110 | IN_EXP_SIGN, | |
5ab8558d AL |
111 | IN_EXP_E, |
112 | IN_MANTISSA, | |
113 | IN_MANTISSA_DIGITS, | |
4d400661 MA |
114 | IN_DIGITS, |
115 | IN_SIGN, | |
5ab8558d | 116 | IN_KEYWORD, |
61030280 | 117 | IN_INTERP, |
5ab8558d | 118 | IN_WHITESPACE, |
5ab8558d | 119 | IN_START, |
2cbd15aa | 120 | IN_START_INTERP, /* must be IN_START + 1 */ |
5ab8558d AL |
121 | }; |
122 | ||
2cbd15aa MA |
123 | QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START_INTERP); |
124 | QEMU_BUILD_BUG_ON(IN_START_INTERP != IN_START + 1); | |
b8d3b1da | 125 | |
5ab8558d AL |
126 | #define TERMINAL(state) [0 ... 0x7F] = (state) |
127 | ||
f7c05274 PB |
128 | /* Return whether TERMINAL is a terminal state and the transition to it |
129 | from OLD_STATE required lookahead. This happens whenever the table | |
130 | below uses the TERMINAL macro. */ | |
131 | #define TERMINAL_NEEDED_LOOKAHEAD(old_state, terminal) \ | |
a2ec6be7 | 132 | (terminal != IN_ERROR && json_lexer[(old_state)][0] == (terminal)) |
f7c05274 | 133 | |
5ab8558d | 134 | static const uint8_t json_lexer[][256] = { |
b8d3b1da MA |
135 | /* Relies on default initialization to IN_ERROR! */ |
136 | ||
5ab8558d | 137 | /* double quote string */ |
5ab8558d | 138 | [IN_DQ_STRING_ESCAPE] = { |
b2da4a4d | 139 | [0x20 ... 0xFD] = IN_DQ_STRING, |
5ab8558d AL |
140 | }, |
141 | [IN_DQ_STRING] = { | |
de930f45 | 142 | [0x20 ... 0xFD] = IN_DQ_STRING, |
5ab8558d | 143 | ['\\'] = IN_DQ_STRING_ESCAPE, |
28e91a68 | 144 | ['"'] = JSON_STRING, |
5ab8558d AL |
145 | }, |
146 | ||
147 | /* single quote string */ | |
5ab8558d | 148 | [IN_SQ_STRING_ESCAPE] = { |
b2da4a4d | 149 | [0x20 ... 0xFD] = IN_SQ_STRING, |
5ab8558d AL |
150 | }, |
151 | [IN_SQ_STRING] = { | |
de930f45 | 152 | [0x20 ... 0xFD] = IN_SQ_STRING, |
5ab8558d | 153 | ['\\'] = IN_SQ_STRING_ESCAPE, |
28e91a68 | 154 | ['\''] = JSON_STRING, |
5ab8558d AL |
155 | }, |
156 | ||
157 | /* Zero */ | |
158 | [IN_ZERO] = { | |
159 | TERMINAL(JSON_INTEGER), | |
33d05394 | 160 | ['0' ... '9'] = IN_ERROR, |
5ab8558d AL |
161 | ['.'] = IN_MANTISSA, |
162 | }, | |
163 | ||
164 | /* Float */ | |
4d400661 | 165 | [IN_EXP_DIGITS] = { |
5ab8558d | 166 | TERMINAL(JSON_FLOAT), |
4d400661 | 167 | ['0' ... '9'] = IN_EXP_DIGITS, |
5ab8558d AL |
168 | }, |
169 | ||
4d400661 MA |
170 | [IN_EXP_SIGN] = { |
171 | ['0' ... '9'] = IN_EXP_DIGITS, | |
5ab8558d AL |
172 | }, |
173 | ||
174 | [IN_EXP_E] = { | |
4d400661 MA |
175 | ['-'] = IN_EXP_SIGN, |
176 | ['+'] = IN_EXP_SIGN, | |
177 | ['0' ... '9'] = IN_EXP_DIGITS, | |
5ab8558d AL |
178 | }, |
179 | ||
180 | [IN_MANTISSA_DIGITS] = { | |
181 | TERMINAL(JSON_FLOAT), | |
182 | ['0' ... '9'] = IN_MANTISSA_DIGITS, | |
183 | ['e'] = IN_EXP_E, | |
184 | ['E'] = IN_EXP_E, | |
185 | }, | |
186 | ||
187 | [IN_MANTISSA] = { | |
188 | ['0' ... '9'] = IN_MANTISSA_DIGITS, | |
189 | }, | |
190 | ||
191 | /* Number */ | |
4d400661 | 192 | [IN_DIGITS] = { |
5ab8558d | 193 | TERMINAL(JSON_INTEGER), |
4d400661 | 194 | ['0' ... '9'] = IN_DIGITS, |
5ab8558d AL |
195 | ['e'] = IN_EXP_E, |
196 | ['E'] = IN_EXP_E, | |
197 | ['.'] = IN_MANTISSA, | |
198 | }, | |
199 | ||
4d400661 | 200 | [IN_SIGN] = { |
5ab8558d | 201 | ['0'] = IN_ZERO, |
4d400661 | 202 | ['1' ... '9'] = IN_DIGITS, |
5ab8558d AL |
203 | }, |
204 | ||
205 | /* keywords */ | |
206 | [IN_KEYWORD] = { | |
207 | TERMINAL(JSON_KEYWORD), | |
208 | ['a' ... 'z'] = IN_KEYWORD, | |
209 | }, | |
210 | ||
211 | /* whitespace */ | |
212 | [IN_WHITESPACE] = { | |
213 | TERMINAL(JSON_SKIP), | |
214 | [' '] = IN_WHITESPACE, | |
215 | ['\t'] = IN_WHITESPACE, | |
216 | ['\r'] = IN_WHITESPACE, | |
217 | ['\n'] = IN_WHITESPACE, | |
ff5394ad | 218 | }, |
5ab8558d | 219 | |
61030280 | 220 | /* interpolation */ |
61030280 | 221 | [IN_INTERP] = { |
f7617d45 MA |
222 | TERMINAL(JSON_INTERP), |
223 | ['A' ... 'Z'] = IN_INTERP, | |
224 | ['a' ... 'z'] = IN_INTERP, | |
225 | ['0' ... '9'] = IN_INTERP, | |
5ab8558d AL |
226 | }, |
227 | ||
2cbd15aa MA |
228 | /* |
229 | * Two start states: | |
230 | * - IN_START recognizes JSON tokens with our string extensions | |
231 | * - IN_START_INTERP additionally recognizes interpolation. | |
232 | */ | |
233 | [IN_START ... IN_START_INTERP] = { | |
5ab8558d AL |
234 | ['"'] = IN_DQ_STRING, |
235 | ['\''] = IN_SQ_STRING, | |
236 | ['0'] = IN_ZERO, | |
4d400661 MA |
237 | ['1' ... '9'] = IN_DIGITS, |
238 | ['-'] = IN_SIGN, | |
c5461660 MA |
239 | ['{'] = JSON_LCURLY, |
240 | ['}'] = JSON_RCURLY, | |
241 | ['['] = JSON_LSQUARE, | |
242 | [']'] = JSON_RSQUARE, | |
243 | [','] = JSON_COMMA, | |
244 | [':'] = JSON_COLON, | |
5ab8558d | 245 | ['a' ... 'z'] = IN_KEYWORD, |
5ab8558d AL |
246 | [' '] = IN_WHITESPACE, |
247 | ['\t'] = IN_WHITESPACE, | |
248 | ['\r'] = IN_WHITESPACE, | |
249 | ['\n'] = IN_WHITESPACE, | |
250 | }, | |
2cbd15aa | 251 | [IN_START_INTERP]['%'] = IN_INTERP, |
5ab8558d AL |
252 | }; |
253 | ||
2cbd15aa | 254 | void json_lexer_init(JSONLexer *lexer, bool enable_interpolation) |
5ab8558d | 255 | { |
2cbd15aa MA |
256 | lexer->start_state = lexer->state = enable_interpolation |
257 | ? IN_START_INTERP : IN_START; | |
d2ca7c0b | 258 | lexer->token = g_string_sized_new(3); |
03308f6c | 259 | lexer->x = lexer->y = 0; |
5ab8558d AL |
260 | } |
261 | ||
7c1e1d54 | 262 | static void json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush) |
5ab8558d | 263 | { |
f7c05274 PB |
264 | int char_consumed, new_state; |
265 | ||
5ab8558d AL |
266 | lexer->x++; |
267 | if (ch == '\n') { | |
268 | lexer->x = 0; | |
269 | lexer->y++; | |
270 | } | |
271 | ||
f7c05274 | 272 | do { |
b8d3b1da | 273 | assert(lexer->state <= ARRAY_SIZE(json_lexer)); |
f7c05274 PB |
274 | new_state = json_lexer[lexer->state][(uint8_t)ch]; |
275 | char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state); | |
a2ec6be7 | 276 | if (char_consumed && !flush) { |
d2ca7c0b | 277 | g_string_append_c(lexer->token, ch); |
f7c05274 | 278 | } |
5ab8558d | 279 | |
f7c05274 | 280 | switch (new_state) { |
c5461660 MA |
281 | case JSON_LCURLY: |
282 | case JSON_RCURLY: | |
283 | case JSON_LSQUARE: | |
284 | case JSON_RSQUARE: | |
285 | case JSON_COLON: | |
286 | case JSON_COMMA: | |
61030280 | 287 | case JSON_INTERP: |
f7c05274 PB |
288 | case JSON_INTEGER: |
289 | case JSON_FLOAT: | |
290 | case JSON_KEYWORD: | |
291 | case JSON_STRING: | |
037f2440 MA |
292 | json_message_process_token(lexer, lexer->token, new_state, |
293 | lexer->x, lexer->y); | |
0b0404bf | 294 | /* fall through */ |
f7c05274 | 295 | case JSON_SKIP: |
d2ca7c0b | 296 | g_string_truncate(lexer->token, 0); |
2cbd15aa | 297 | new_state = lexer->start_state; |
f7c05274 | 298 | break; |
33d05394 | 299 | case IN_ERROR: |
b011f619 MR |
300 | /* XXX: To avoid having previous bad input leaving the parser in an |
301 | * unresponsive state where we consume unpredictable amounts of | |
302 | * subsequent "good" input, percolate this error state up to the | |
84a56f38 | 303 | * parser by emitting a JSON_ERROR token, then reset lexer state. |
b011f619 MR |
304 | * |
305 | * Also note that this handling is required for reliable channel | |
306 | * negotiation between QMP and the guest agent, since chr(0xFF) | |
307 | * is placed at the beginning of certain events to ensure proper | |
308 | * delivery when the channel is in an unknown state. chr(0xFF) is | |
309 | * never a valid ASCII/UTF-8 sequence, so this should reliably | |
310 | * induce an error/flush state. | |
311 | */ | |
037f2440 MA |
312 | json_message_process_token(lexer, lexer->token, JSON_ERROR, |
313 | lexer->x, lexer->y); | |
d2ca7c0b | 314 | g_string_truncate(lexer->token, 0); |
2cbd15aa | 315 | lexer->state = lexer->start_state; |
7c1e1d54 | 316 | return; |
f7c05274 PB |
317 | default: |
318 | break; | |
319 | } | |
320 | lexer->state = new_state; | |
bd3924a3 | 321 | } while (!char_consumed && !flush); |
325601b4 AL |
322 | |
323 | /* Do not let a single token grow to an arbitrarily large size, | |
324 | * this is a security consideration. | |
325 | */ | |
d2ca7c0b | 326 | if (lexer->token->len > MAX_TOKEN_SIZE) { |
037f2440 MA |
327 | json_message_process_token(lexer, lexer->token, lexer->state, |
328 | lexer->x, lexer->y); | |
d2ca7c0b | 329 | g_string_truncate(lexer->token, 0); |
2cbd15aa | 330 | lexer->state = lexer->start_state; |
325601b4 | 331 | } |
5ab8558d AL |
332 | } |
333 | ||
7c1e1d54 | 334 | void json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size) |
5ab8558d AL |
335 | { |
336 | size_t i; | |
337 | ||
338 | for (i = 0; i < size; i++) { | |
7c1e1d54 | 339 | json_lexer_feed_char(lexer, buffer[i], false); |
5ab8558d | 340 | } |
5ab8558d AL |
341 | } |
342 | ||
7c1e1d54 | 343 | void json_lexer_flush(JSONLexer *lexer) |
5ab8558d | 344 | { |
2cbd15aa | 345 | if (lexer->state != lexer->start_state) { |
7c1e1d54 MAL |
346 | json_lexer_feed_char(lexer, 0, true); |
347 | } | |
f9277915 MA |
348 | json_message_process_token(lexer, lexer->token, JSON_END_OF_INPUT, |
349 | lexer->x, lexer->y); | |
5ab8558d AL |
350 | } |
351 | ||
352 | void json_lexer_destroy(JSONLexer *lexer) | |
353 | { | |
d2ca7c0b | 354 | g_string_free(lexer->token, true); |
5ab8558d | 355 | } |