blob: 51341d96e49e99b504db97b3507ff15ed98b8597 [file] [log] [blame]
Anthony Liguori5ab85582009-11-11 10:39:14 -06001/*
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
Peter Maydellf2ad72b2016-01-29 17:50:01 +000014#include "qemu/osdep.h"
Markus Armbruster86cdf9e2018-08-23 18:40:20 +020015#include "json-parser-int.h"
Anthony Liguori5ab85582009-11-11 10:39:14 -060016
Anthony Liguori325601b2011-06-01 12:14:52 -050017#define MAX_TOKEN_SIZE (64ULL << 20)
18
Anthony Liguori5ab85582009-11-11 10:39:14 -060019/*
Markus Armbrustereddc0a72018-08-23 18:39:46 +020020 * From RFC 8259 "The JavaScript Object Notation (JSON) Data
21 * Interchange Format", with [comments in brackets]:
Eric Blakeff5394a2016-06-09 20:48:06 -060022 *
Markus Armbrustereddc0a72018-08-23 18:39:46 +020023 * The set of tokens includes six structural characters, strings,
24 * numbers, and three literal names.
Eric Blakeff5394a2016-06-09 20:48:06 -060025 *
Markus Armbrustereddc0a72018-08-23 18:39:46 +020026 * These are the six structural characters:
Eric Blakeff5394a2016-06-09 20:48:06 -060027 *
Markus Armbrustereddc0a72018-08-23 18:39:46 +020028 * 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
Eric Blakeff5394a2016-06-09 20:48:06 -060034 *
Markus Armbrustereddc0a72018-08-23 18:39:46 +020035 * 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.]
Eric Blakeff5394a2016-06-09 20:48:06 -060040 *
Markus Armbrustereddc0a72018-08-23 18:39:46 +020041 * ws = *(
42 * %x20 / ; Space
43 * %x09 / ; Horizontal tab
44 * %x0A / ; Line feed or New line
45 * %x0D ) ; Carriage return
Anthony Liguori5ab85582009-11-11 10:39:14 -060046 *
Markus Armbrustereddc0a72018-08-23 18:39:46 +020047 * [...] 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
Markus Armbrusterb2da4a42018-08-23 18:39:53 +020082 * [This lexer accepts any non-control character after escape, and
83 * leaves rejecting invalid ones to the parser.]
Markus Armbrustereddc0a72018-08-23 18:39:46 +020084 *
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.
Markus Armbruster2cbd15a2018-08-23 18:40:05 +020093 * - Interpolation, if enabled:
Markus Armbrusterf7617d42018-08-23 18:40:07 +020094 * The lexer accepts %[A-Za-z0-9]*, and leaves rejecting invalid
95 * ones to the parser.
Markus Armbrustereddc0a72018-08-23 18:39:46 +020096 *
97 * Note:
Markus Armbruster4b1c0cd2018-08-23 18:39:52 +020098 * - Input must be encoded in modified UTF-8.
Markus Armbrustereddc0a72018-08-23 18:39:46 +020099 * - Decoding and validating is left to the parser.
Anthony Liguori5ab85582009-11-11 10:39:14 -0600100 */
101
102enum json_lexer_state {
Markus Armbruster2ce4ee62018-08-31 09:58:40 +0200103 IN_RECOVERY = 1,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600104 IN_DQ_STRING_ESCAPE,
105 IN_DQ_STRING,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600106 IN_SQ_STRING_ESCAPE,
107 IN_SQ_STRING,
108 IN_ZERO,
Markus Armbruster4d400662018-08-23 18:40:09 +0200109 IN_EXP_DIGITS,
110 IN_EXP_SIGN,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600111 IN_EXP_E,
112 IN_MANTISSA,
113 IN_MANTISSA_DIGITS,
Markus Armbruster4d400662018-08-23 18:40:09 +0200114 IN_DIGITS,
115 IN_SIGN,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600116 IN_KEYWORD,
Markus Armbruster61030282018-08-23 18:40:04 +0200117 IN_INTERP,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600118 IN_START,
Markus Armbruster2cbd15a2018-08-23 18:40:05 +0200119 IN_START_INTERP, /* must be IN_START + 1 */
Anthony Liguori5ab85582009-11-11 10:39:14 -0600120};
121
Markus Armbruster2ce4ee62018-08-31 09:58:40 +0200122QEMU_BUILD_BUG_ON(JSON_ERROR != 0);
123QEMU_BUILD_BUG_ON(IN_RECOVERY != JSON_ERROR + 1);
Markus Armbruster2cbd15a2018-08-23 18:40:05 +0200124QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START_INTERP);
Markus Armbrusterc0ee3af2018-08-31 09:58:38 +0200125QEMU_BUILD_BUG_ON(JSON_MAX >= 0x80);
Markus Armbruster2cbd15a2018-08-23 18:40:05 +0200126QEMU_BUILD_BUG_ON(IN_START_INTERP != IN_START + 1);
Markus Armbrusterb8d3b1d2015-11-25 22:23:25 +0100127
Markus Armbrusterc0ee3af2018-08-31 09:58:38 +0200128#define LOOKAHEAD 0x80
129#define TERMINAL(state) [0 ... 0xFF] = ((state) | LOOKAHEAD)
Paolo Bonzinif7c05272010-05-24 09:39:52 +0200130
Anthony Liguori5ab85582009-11-11 10:39:14 -0600131static const uint8_t json_lexer[][256] = {
Markus Armbrusterb8d3b1d2015-11-25 22:23:25 +0100132 /* Relies on default initialization to IN_ERROR! */
133
Markus Armbruster0f07a5d2018-08-31 09:58:39 +0200134 /* error recovery */
135 [IN_RECOVERY] = {
136 /*
137 * Skip characters until a structural character, an ASCII
138 * control character other than '\t', or impossible UTF-8
139 * bytes '\xFE', '\xFF'. Structural characters and line
140 * endings are promising resynchronization points. Clients
141 * may use the others to force the JSON parser into known-good
Peter Maydelld5657252023-05-15 17:22:43 +0100142 * state; see docs/interop/qmp-spec.rst.
Markus Armbruster0f07a5d2018-08-31 09:58:39 +0200143 */
144 [0 ... 0x1F] = IN_START | LOOKAHEAD,
145 [0x20 ... 0xFD] = IN_RECOVERY,
146 [0xFE ... 0xFF] = IN_START | LOOKAHEAD,
147 ['\t'] = IN_RECOVERY,
148 ['['] = IN_START | LOOKAHEAD,
149 [']'] = IN_START | LOOKAHEAD,
150 ['{'] = IN_START | LOOKAHEAD,
151 ['}'] = IN_START | LOOKAHEAD,
152 [':'] = IN_START | LOOKAHEAD,
153 [','] = IN_START | LOOKAHEAD,
154 },
155
Anthony Liguori5ab85582009-11-11 10:39:14 -0600156 /* double quote string */
Anthony Liguori5ab85582009-11-11 10:39:14 -0600157 [IN_DQ_STRING_ESCAPE] = {
Markus Armbrusterb2da4a42018-08-23 18:39:53 +0200158 [0x20 ... 0xFD] = IN_DQ_STRING,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600159 },
160 [IN_DQ_STRING] = {
Markus Armbrusterde930f42018-08-23 18:39:51 +0200161 [0x20 ... 0xFD] = IN_DQ_STRING,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600162 ['\\'] = IN_DQ_STRING_ESCAPE,
Paolo Bonzini28e91a62010-05-24 09:39:53 +0200163 ['"'] = JSON_STRING,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600164 },
165
166 /* single quote string */
Anthony Liguori5ab85582009-11-11 10:39:14 -0600167 [IN_SQ_STRING_ESCAPE] = {
Markus Armbrusterb2da4a42018-08-23 18:39:53 +0200168 [0x20 ... 0xFD] = IN_SQ_STRING,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600169 },
170 [IN_SQ_STRING] = {
Markus Armbrusterde930f42018-08-23 18:39:51 +0200171 [0x20 ... 0xFD] = IN_SQ_STRING,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600172 ['\\'] = IN_SQ_STRING_ESCAPE,
Paolo Bonzini28e91a62010-05-24 09:39:53 +0200173 ['\''] = JSON_STRING,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600174 },
175
176 /* Zero */
177 [IN_ZERO] = {
178 TERMINAL(JSON_INTEGER),
Markus Armbruster2ce4ee62018-08-31 09:58:40 +0200179 ['0' ... '9'] = JSON_ERROR,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600180 ['.'] = IN_MANTISSA,
181 },
182
183 /* Float */
Markus Armbruster4d400662018-08-23 18:40:09 +0200184 [IN_EXP_DIGITS] = {
Anthony Liguori5ab85582009-11-11 10:39:14 -0600185 TERMINAL(JSON_FLOAT),
Markus Armbruster4d400662018-08-23 18:40:09 +0200186 ['0' ... '9'] = IN_EXP_DIGITS,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600187 },
188
Markus Armbruster4d400662018-08-23 18:40:09 +0200189 [IN_EXP_SIGN] = {
190 ['0' ... '9'] = IN_EXP_DIGITS,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600191 },
192
193 [IN_EXP_E] = {
Markus Armbruster4d400662018-08-23 18:40:09 +0200194 ['-'] = IN_EXP_SIGN,
195 ['+'] = IN_EXP_SIGN,
196 ['0' ... '9'] = IN_EXP_DIGITS,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600197 },
198
199 [IN_MANTISSA_DIGITS] = {
200 TERMINAL(JSON_FLOAT),
201 ['0' ... '9'] = IN_MANTISSA_DIGITS,
202 ['e'] = IN_EXP_E,
203 ['E'] = IN_EXP_E,
204 },
205
206 [IN_MANTISSA] = {
207 ['0' ... '9'] = IN_MANTISSA_DIGITS,
208 },
209
210 /* Number */
Markus Armbruster4d400662018-08-23 18:40:09 +0200211 [IN_DIGITS] = {
Anthony Liguori5ab85582009-11-11 10:39:14 -0600212 TERMINAL(JSON_INTEGER),
Markus Armbruster4d400662018-08-23 18:40:09 +0200213 ['0' ... '9'] = IN_DIGITS,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600214 ['e'] = IN_EXP_E,
215 ['E'] = IN_EXP_E,
216 ['.'] = IN_MANTISSA,
217 },
218
Markus Armbruster4d400662018-08-23 18:40:09 +0200219 [IN_SIGN] = {
Anthony Liguori5ab85582009-11-11 10:39:14 -0600220 ['0'] = IN_ZERO,
Markus Armbruster4d400662018-08-23 18:40:09 +0200221 ['1' ... '9'] = IN_DIGITS,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600222 },
223
224 /* keywords */
225 [IN_KEYWORD] = {
226 TERMINAL(JSON_KEYWORD),
227 ['a' ... 'z'] = IN_KEYWORD,
228 },
229
Markus Armbruster61030282018-08-23 18:40:04 +0200230 /* interpolation */
Markus Armbruster61030282018-08-23 18:40:04 +0200231 [IN_INTERP] = {
Markus Armbrusterf7617d42018-08-23 18:40:07 +0200232 TERMINAL(JSON_INTERP),
233 ['A' ... 'Z'] = IN_INTERP,
234 ['a' ... 'z'] = IN_INTERP,
235 ['0' ... '9'] = IN_INTERP,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600236 },
237
Markus Armbruster2cbd15a2018-08-23 18:40:05 +0200238 /*
239 * Two start states:
240 * - IN_START recognizes JSON tokens with our string extensions
241 * - IN_START_INTERP additionally recognizes interpolation.
242 */
243 [IN_START ... IN_START_INTERP] = {
Anthony Liguori5ab85582009-11-11 10:39:14 -0600244 ['"'] = IN_DQ_STRING,
245 ['\''] = IN_SQ_STRING,
246 ['0'] = IN_ZERO,
Markus Armbruster4d400662018-08-23 18:40:09 +0200247 ['1' ... '9'] = IN_DIGITS,
248 ['-'] = IN_SIGN,
Markus Armbrusterc5461662015-11-25 22:23:26 +0100249 ['{'] = JSON_LCURLY,
250 ['}'] = JSON_RCURLY,
251 ['['] = JSON_LSQUARE,
252 [']'] = JSON_RSQUARE,
253 [','] = JSON_COMMA,
254 [':'] = JSON_COLON,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600255 ['a' ... 'z'] = IN_KEYWORD,
Markus Armbruster1e960b42018-08-31 09:58:41 +0200256 [' '] = IN_START,
257 ['\t'] = IN_START,
258 ['\r'] = IN_START,
259 ['\n'] = IN_START,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600260 },
Markus Armbruster2cbd15a2018-08-23 18:40:05 +0200261 [IN_START_INTERP]['%'] = IN_INTERP,
Anthony Liguori5ab85582009-11-11 10:39:14 -0600262};
263
Markus Armbrusterc0ee3af2018-08-31 09:58:38 +0200264static inline uint8_t next_state(JSONLexer *lexer, char ch, bool flush,
265 bool *char_consumed)
266{
267 uint8_t next;
268
Liam Merwick19e8ff42019-03-21 11:57:52 +0000269 assert(lexer->state < ARRAY_SIZE(json_lexer));
Markus Armbrusterc0ee3af2018-08-31 09:58:38 +0200270 next = json_lexer[lexer->state][(uint8_t)ch];
271 *char_consumed = !flush && !(next & LOOKAHEAD);
272 return next & ~LOOKAHEAD;
273}
274
Markus Armbruster2cbd15a2018-08-23 18:40:05 +0200275void json_lexer_init(JSONLexer *lexer, bool enable_interpolation)
Anthony Liguori5ab85582009-11-11 10:39:14 -0600276{
Markus Armbruster2cbd15a2018-08-23 18:40:05 +0200277 lexer->start_state = lexer->state = enable_interpolation
278 ? IN_START_INTERP : IN_START;
Paolo Bonzinid2ca7c02015-11-25 22:23:29 +0100279 lexer->token = g_string_sized_new(3);
Luiz Capitulino03308f62010-05-17 17:50:01 -0300280 lexer->x = lexer->y = 0;
Anthony Liguori5ab85582009-11-11 10:39:14 -0600281}
282
Marc-André Lureau7c1e1d52018-08-23 18:39:58 +0200283static void json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
Anthony Liguori5ab85582009-11-11 10:39:14 -0600284{
Markus Armbruster852dfa72018-08-31 09:58:37 +0200285 int new_state;
286 bool char_consumed = false;
Paolo Bonzinif7c05272010-05-24 09:39:52 +0200287
Anthony Liguori5ab85582009-11-11 10:39:14 -0600288 lexer->x++;
289 if (ch == '\n') {
290 lexer->x = 0;
291 lexer->y++;
292 }
293
Markus Armbruster852dfa72018-08-31 09:58:37 +0200294 while (flush ? lexer->state != lexer->start_state : !char_consumed) {
Markus Armbrusterc0ee3af2018-08-31 09:58:38 +0200295 new_state = next_state(lexer, ch, flush, &char_consumed);
Markus Armbruster852dfa72018-08-31 09:58:37 +0200296 if (char_consumed) {
Markus Armbrusterc0ee3af2018-08-31 09:58:38 +0200297 assert(!flush);
Paolo Bonzinid2ca7c02015-11-25 22:23:29 +0100298 g_string_append_c(lexer->token, ch);
Paolo Bonzinif7c05272010-05-24 09:39:52 +0200299 }
Anthony Liguori5ab85582009-11-11 10:39:14 -0600300
Paolo Bonzinif7c05272010-05-24 09:39:52 +0200301 switch (new_state) {
Markus Armbrusterc5461662015-11-25 22:23:26 +0100302 case JSON_LCURLY:
303 case JSON_RCURLY:
304 case JSON_LSQUARE:
305 case JSON_RSQUARE:
306 case JSON_COLON:
307 case JSON_COMMA:
Markus Armbruster61030282018-08-23 18:40:04 +0200308 case JSON_INTERP:
Paolo Bonzinif7c05272010-05-24 09:39:52 +0200309 case JSON_INTEGER:
310 case JSON_FLOAT:
311 case JSON_KEYWORD:
312 case JSON_STRING:
Markus Armbruster037f2442018-08-23 18:40:00 +0200313 json_message_process_token(lexer, lexer->token, new_state,
314 lexer->x, lexer->y);
Stefan Weil0b0404b2012-01-09 18:29:51 +0100315 /* fall through */
Markus Armbruster0f07a5d2018-08-31 09:58:39 +0200316 case IN_START:
Markus Armbruster1e960b42018-08-31 09:58:41 +0200317 g_string_truncate(lexer->token, 0);
Markus Armbruster2cbd15a2018-08-23 18:40:05 +0200318 new_state = lexer->start_state;
Paolo Bonzinif7c05272010-05-24 09:39:52 +0200319 break;
Markus Armbruster2ce4ee62018-08-31 09:58:40 +0200320 case JSON_ERROR:
Markus Armbruster037f2442018-08-23 18:40:00 +0200321 json_message_process_token(lexer, lexer->token, JSON_ERROR,
322 lexer->x, lexer->y);
Markus Armbruster0f07a5d2018-08-31 09:58:39 +0200323 new_state = IN_RECOVERY;
324 /* fall through */
325 case IN_RECOVERY:
Paolo Bonzinid2ca7c02015-11-25 22:23:29 +0100326 g_string_truncate(lexer->token, 0);
Markus Armbruster0f07a5d2018-08-31 09:58:39 +0200327 break;
Paolo Bonzinif7c05272010-05-24 09:39:52 +0200328 default:
329 break;
330 }
331 lexer->state = new_state;
Markus Armbruster852dfa72018-08-31 09:58:37 +0200332 }
Anthony Liguori325601b2011-06-01 12:14:52 -0500333
334 /* Do not let a single token grow to an arbitrarily large size,
335 * this is a security consideration.
336 */
Paolo Bonzinid2ca7c02015-11-25 22:23:29 +0100337 if (lexer->token->len > MAX_TOKEN_SIZE) {
Markus Armbruster037f2442018-08-23 18:40:00 +0200338 json_message_process_token(lexer, lexer->token, lexer->state,
339 lexer->x, lexer->y);
Paolo Bonzinid2ca7c02015-11-25 22:23:29 +0100340 g_string_truncate(lexer->token, 0);
Markus Armbruster2cbd15a2018-08-23 18:40:05 +0200341 lexer->state = lexer->start_state;
Anthony Liguori325601b2011-06-01 12:14:52 -0500342 }
Anthony Liguori5ab85582009-11-11 10:39:14 -0600343}
344
Marc-André Lureau7c1e1d52018-08-23 18:39:58 +0200345void json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size)
Anthony Liguori5ab85582009-11-11 10:39:14 -0600346{
347 size_t i;
348
349 for (i = 0; i < size; i++) {
Marc-André Lureau7c1e1d52018-08-23 18:39:58 +0200350 json_lexer_feed_char(lexer, buffer[i], false);
Anthony Liguori5ab85582009-11-11 10:39:14 -0600351 }
Anthony Liguori5ab85582009-11-11 10:39:14 -0600352}
353
Marc-André Lureau7c1e1d52018-08-23 18:39:58 +0200354void json_lexer_flush(JSONLexer *lexer)
Anthony Liguori5ab85582009-11-11 10:39:14 -0600355{
Markus Armbruster852dfa72018-08-31 09:58:37 +0200356 json_lexer_feed_char(lexer, 0, true);
357 assert(lexer->state == lexer->start_state);
Markus Armbrusterf9277912018-08-23 18:40:12 +0200358 json_message_process_token(lexer, lexer->token, JSON_END_OF_INPUT,
359 lexer->x, lexer->y);
Anthony Liguori5ab85582009-11-11 10:39:14 -0600360}
361
362void json_lexer_destroy(JSONLexer *lexer)
363{
Paolo Bonzinid2ca7c02015-11-25 22:23:29 +0100364 g_string_free(lexer->token, true);
Anthony Liguori5ab85582009-11-11 10:39:14 -0600365}