]>
Commit | Line | Data |
---|---|---|
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 ... 0xFF] = IN_DQ_STRING, | |
109 | ['\\'] = IN_DQ_STRING_ESCAPE, | |
110 | ['"'] = JSON_STRING, | |
111 | }, | |
112 | ||
113 | /* single quote string */ | |
114 | [IN_SQ_UCODE3] = { | |
115 | ['0' ... '9'] = IN_SQ_STRING, | |
116 | ['a' ... 'f'] = IN_SQ_STRING, | |
117 | ['A' ... 'F'] = IN_SQ_STRING, | |
118 | }, | |
119 | [IN_SQ_UCODE2] = { | |
120 | ['0' ... '9'] = IN_SQ_UCODE3, | |
121 | ['a' ... 'f'] = IN_SQ_UCODE3, | |
122 | ['A' ... 'F'] = IN_SQ_UCODE3, | |
123 | }, | |
124 | [IN_SQ_UCODE1] = { | |
125 | ['0' ... '9'] = IN_SQ_UCODE2, | |
126 | ['a' ... 'f'] = IN_SQ_UCODE2, | |
127 | ['A' ... 'F'] = IN_SQ_UCODE2, | |
128 | }, | |
129 | [IN_SQ_UCODE0] = { | |
130 | ['0' ... '9'] = IN_SQ_UCODE1, | |
131 | ['a' ... 'f'] = IN_SQ_UCODE1, | |
132 | ['A' ... 'F'] = IN_SQ_UCODE1, | |
133 | }, | |
134 | [IN_SQ_STRING_ESCAPE] = { | |
135 | ['b'] = IN_SQ_STRING, | |
136 | ['f'] = IN_SQ_STRING, | |
137 | ['n'] = IN_SQ_STRING, | |
138 | ['r'] = IN_SQ_STRING, | |
139 | ['t'] = IN_SQ_STRING, | |
140 | ['/'] = IN_DQ_STRING, | |
141 | ['\\'] = IN_DQ_STRING, | |
142 | ['\''] = IN_SQ_STRING, | |
143 | ['\"'] = IN_SQ_STRING, | |
144 | ['u'] = IN_SQ_UCODE0, | |
145 | }, | |
146 | [IN_SQ_STRING] = { | |
147 | [1 ... 0xFF] = IN_SQ_STRING, | |
148 | ['\\'] = IN_SQ_STRING_ESCAPE, | |
149 | ['\''] = JSON_STRING, | |
150 | }, | |
151 | ||
152 | /* Zero */ | |
153 | [IN_ZERO] = { | |
154 | TERMINAL(JSON_INTEGER), | |
155 | ['0' ... '9'] = IN_ERROR, | |
156 | ['.'] = IN_MANTISSA, | |
157 | }, | |
158 | ||
159 | /* Float */ | |
160 | [IN_DIGITS] = { | |
161 | TERMINAL(JSON_FLOAT), | |
162 | ['0' ... '9'] = IN_DIGITS, | |
163 | }, | |
164 | ||
165 | [IN_DIGIT] = { | |
166 | ['0' ... '9'] = IN_DIGITS, | |
167 | }, | |
168 | ||
169 | [IN_EXP_E] = { | |
170 | ['-'] = IN_DIGIT, | |
171 | ['+'] = IN_DIGIT, | |
172 | ['0' ... '9'] = IN_DIGITS, | |
173 | }, | |
174 | ||
175 | [IN_MANTISSA_DIGITS] = { | |
176 | TERMINAL(JSON_FLOAT), | |
177 | ['0' ... '9'] = IN_MANTISSA_DIGITS, | |
178 | ['e'] = IN_EXP_E, | |
179 | ['E'] = IN_EXP_E, | |
180 | }, | |
181 | ||
182 | [IN_MANTISSA] = { | |
183 | ['0' ... '9'] = IN_MANTISSA_DIGITS, | |
184 | }, | |
185 | ||
186 | /* Number */ | |
187 | [IN_NONZERO_NUMBER] = { | |
188 | TERMINAL(JSON_INTEGER), | |
189 | ['0' ... '9'] = IN_NONZERO_NUMBER, | |
190 | ['e'] = IN_EXP_E, | |
191 | ['E'] = IN_EXP_E, | |
192 | ['.'] = IN_MANTISSA, | |
193 | }, | |
194 | ||
195 | [IN_NEG_NONZERO_NUMBER] = { | |
196 | ['0'] = IN_ZERO, | |
197 | ['1' ... '9'] = IN_NONZERO_NUMBER, | |
198 | }, | |
199 | ||
200 | /* keywords */ | |
201 | [IN_KEYWORD] = { | |
202 | TERMINAL(JSON_KEYWORD), | |
203 | ['a' ... 'z'] = IN_KEYWORD, | |
204 | }, | |
205 | ||
206 | /* whitespace */ | |
207 | [IN_WHITESPACE] = { | |
208 | TERMINAL(JSON_SKIP), | |
209 | [' '] = IN_WHITESPACE, | |
210 | ['\t'] = IN_WHITESPACE, | |
211 | ['\r'] = IN_WHITESPACE, | |
212 | ['\n'] = IN_WHITESPACE, | |
213 | }, | |
214 | ||
215 | /* escape */ | |
216 | [IN_ESCAPE_LL] = { | |
217 | ['d'] = JSON_ESCAPE, | |
218 | }, | |
219 | ||
220 | [IN_ESCAPE_L] = { | |
221 | ['d'] = JSON_ESCAPE, | |
222 | ['l'] = IN_ESCAPE_LL, | |
223 | }, | |
224 | ||
225 | [IN_ESCAPE_I64] = { | |
226 | ['d'] = JSON_ESCAPE, | |
227 | }, | |
228 | ||
229 | [IN_ESCAPE_I6] = { | |
230 | ['4'] = IN_ESCAPE_I64, | |
231 | }, | |
232 | ||
233 | [IN_ESCAPE_I] = { | |
234 | ['6'] = IN_ESCAPE_I6, | |
235 | }, | |
236 | ||
237 | [IN_ESCAPE] = { | |
238 | ['d'] = JSON_ESCAPE, | |
239 | ['i'] = JSON_ESCAPE, | |
240 | ['p'] = JSON_ESCAPE, | |
241 | ['s'] = JSON_ESCAPE, | |
242 | ['f'] = JSON_ESCAPE, | |
243 | ['l'] = IN_ESCAPE_L, | |
244 | ['I'] = IN_ESCAPE_I, | |
245 | }, | |
246 | ||
247 | /* top level rule */ | |
248 | [IN_START] = { | |
249 | ['"'] = IN_DQ_STRING, | |
250 | ['\''] = IN_SQ_STRING, | |
251 | ['0'] = IN_ZERO, | |
252 | ['1' ... '9'] = IN_NONZERO_NUMBER, | |
253 | ['-'] = IN_NEG_NONZERO_NUMBER, | |
254 | ['{'] = JSON_OPERATOR, | |
255 | ['}'] = JSON_OPERATOR, | |
256 | ['['] = JSON_OPERATOR, | |
257 | [']'] = JSON_OPERATOR, | |
258 | [','] = JSON_OPERATOR, | |
259 | [':'] = JSON_OPERATOR, | |
260 | ['a' ... 'z'] = IN_KEYWORD, | |
261 | ['%'] = IN_ESCAPE, | |
262 | [' '] = IN_WHITESPACE, | |
263 | ['\t'] = IN_WHITESPACE, | |
264 | ['\r'] = IN_WHITESPACE, | |
265 | ['\n'] = IN_WHITESPACE, | |
266 | }, | |
267 | }; | |
268 | ||
269 | void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func) | |
270 | { | |
271 | lexer->emit = func; | |
272 | lexer->state = IN_START; | |
273 | lexer->token = qstring_new(); | |
274 | lexer->x = lexer->y = 0; | |
275 | } | |
276 | ||
277 | static int json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush) | |
278 | { | |
279 | int char_consumed, new_state; | |
280 | ||
281 | lexer->x++; | |
282 | if (ch == '\n') { | |
283 | lexer->x = 0; | |
284 | lexer->y++; | |
285 | } | |
286 | ||
287 | do { | |
288 | new_state = json_lexer[lexer->state][(uint8_t)ch]; | |
289 | char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state); | |
290 | if (char_consumed) { | |
291 | qstring_append_chr(lexer->token, ch); | |
292 | } | |
293 | ||
294 | switch (new_state) { | |
295 | case JSON_OPERATOR: | |
296 | case JSON_ESCAPE: | |
297 | case JSON_INTEGER: | |
298 | case JSON_FLOAT: | |
299 | case JSON_KEYWORD: | |
300 | case JSON_STRING: | |
301 | lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y); | |
302 | case JSON_SKIP: | |
303 | QDECREF(lexer->token); | |
304 | lexer->token = qstring_new(); | |
305 | new_state = IN_START; | |
306 | break; | |
307 | case IN_ERROR: | |
308 | QDECREF(lexer->token); | |
309 | lexer->token = qstring_new(); | |
310 | new_state = IN_START; | |
311 | return -EINVAL; | |
312 | default: | |
313 | break; | |
314 | } | |
315 | lexer->state = new_state; | |
316 | } while (!char_consumed && !flush); | |
317 | ||
318 | /* Do not let a single token grow to an arbitrarily large size, | |
319 | * this is a security consideration. | |
320 | */ | |
321 | if (lexer->token->length > MAX_TOKEN_SIZE) { | |
322 | lexer->emit(lexer, lexer->token, lexer->state, lexer->x, lexer->y); | |
323 | QDECREF(lexer->token); | |
324 | lexer->token = qstring_new(); | |
325 | lexer->state = IN_START; | |
326 | } | |
327 | ||
328 | return 0; | |
329 | } | |
330 | ||
331 | int json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size) | |
332 | { | |
333 | size_t i; | |
334 | ||
335 | for (i = 0; i < size; i++) { | |
336 | int err; | |
337 | ||
338 | err = json_lexer_feed_char(lexer, buffer[i], false); | |
339 | if (err < 0) { | |
340 | return err; | |
341 | } | |
342 | } | |
343 | ||
344 | return 0; | |
345 | } | |
346 | ||
347 | int json_lexer_flush(JSONLexer *lexer) | |
348 | { | |
349 | return lexer->state == IN_START ? 0 : json_lexer_feed_char(lexer, 0); | |
350 | } | |
351 | ||
352 | void json_lexer_destroy(JSONLexer *lexer) | |
353 | { | |
354 | QDECREF(lexer->token); | |
355 | } |