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