xref: /openbmc/qemu/qobject/json-lexer.c (revision d5657258)
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 "qemu/osdep.h"
15 #include "json-parser-int.h"
16 
17 #define MAX_TOKEN_SIZE (64ULL << 20)
18 
19 /*
20  * From RFC 8259 "The JavaScript Object Notation (JSON) Data
21  * Interchange Format", with [comments in brackets]:
22  *
23  * The set of tokens includes six structural characters, strings,
24  * numbers, and three literal names.
25  *
26  * These are the six structural characters:
27  *
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
34  *
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.]
40  *
41  *    ws = *(
42  *           %x20 /              ; Space
43  *           %x09 /              ; Horizontal tab
44  *           %x0A /              ; Line feed or New line
45  *           %x0D )              ; Carriage return
46  *
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
82  *    [This lexer accepts any non-control character after escape, and
83  *    leaves rejecting invalid ones to the parser.]
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.
93  * - Interpolation, if enabled:
94  *   The lexer accepts %[A-Za-z0-9]*, and leaves rejecting invalid
95  *   ones to the parser.
96  *
97  * Note:
98  * - Input must be encoded in modified UTF-8.
99  * - Decoding and validating is left to the parser.
100  */
101 
102 enum json_lexer_state {
103     IN_RECOVERY = 1,
104     IN_DQ_STRING_ESCAPE,
105     IN_DQ_STRING,
106     IN_SQ_STRING_ESCAPE,
107     IN_SQ_STRING,
108     IN_ZERO,
109     IN_EXP_DIGITS,
110     IN_EXP_SIGN,
111     IN_EXP_E,
112     IN_MANTISSA,
113     IN_MANTISSA_DIGITS,
114     IN_DIGITS,
115     IN_SIGN,
116     IN_KEYWORD,
117     IN_INTERP,
118     IN_START,
119     IN_START_INTERP,            /* must be IN_START + 1 */
120 };
121 
122 QEMU_BUILD_BUG_ON(JSON_ERROR != 0);
123 QEMU_BUILD_BUG_ON(IN_RECOVERY != JSON_ERROR + 1);
124 QEMU_BUILD_BUG_ON((int)JSON_MIN <= (int)IN_START_INTERP);
125 QEMU_BUILD_BUG_ON(JSON_MAX >= 0x80);
126 QEMU_BUILD_BUG_ON(IN_START_INTERP != IN_START + 1);
127 
128 #define LOOKAHEAD 0x80
129 #define TERMINAL(state) [0 ... 0xFF] = ((state) | LOOKAHEAD)
130 
131 static const uint8_t json_lexer[][256] =  {
132     /* Relies on default initialization to IN_ERROR! */
133 
134     /* 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
142          * state; see docs/interop/qmp-spec.rst.
143          */
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 
156     /* double quote string */
157     [IN_DQ_STRING_ESCAPE] = {
158         [0x20 ... 0xFD] = IN_DQ_STRING,
159     },
160     [IN_DQ_STRING] = {
161         [0x20 ... 0xFD] = IN_DQ_STRING,
162         ['\\'] = IN_DQ_STRING_ESCAPE,
163         ['"'] = JSON_STRING,
164     },
165 
166     /* single quote string */
167     [IN_SQ_STRING_ESCAPE] = {
168         [0x20 ... 0xFD] = IN_SQ_STRING,
169     },
170     [IN_SQ_STRING] = {
171         [0x20 ... 0xFD] = IN_SQ_STRING,
172         ['\\'] = IN_SQ_STRING_ESCAPE,
173         ['\''] = JSON_STRING,
174     },
175 
176     /* Zero */
177     [IN_ZERO] = {
178         TERMINAL(JSON_INTEGER),
179         ['0' ... '9'] = JSON_ERROR,
180         ['.'] = IN_MANTISSA,
181     },
182 
183     /* Float */
184     [IN_EXP_DIGITS] = {
185         TERMINAL(JSON_FLOAT),
186         ['0' ... '9'] = IN_EXP_DIGITS,
187     },
188 
189     [IN_EXP_SIGN] = {
190         ['0' ... '9'] = IN_EXP_DIGITS,
191     },
192 
193     [IN_EXP_E] = {
194         ['-'] = IN_EXP_SIGN,
195         ['+'] = IN_EXP_SIGN,
196         ['0' ... '9'] = IN_EXP_DIGITS,
197     },
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 */
211     [IN_DIGITS] = {
212         TERMINAL(JSON_INTEGER),
213         ['0' ... '9'] = IN_DIGITS,
214         ['e'] = IN_EXP_E,
215         ['E'] = IN_EXP_E,
216         ['.'] = IN_MANTISSA,
217     },
218 
219     [IN_SIGN] = {
220         ['0'] = IN_ZERO,
221         ['1' ... '9'] = IN_DIGITS,
222     },
223 
224     /* keywords */
225     [IN_KEYWORD] = {
226         TERMINAL(JSON_KEYWORD),
227         ['a' ... 'z'] = IN_KEYWORD,
228     },
229 
230     /* interpolation */
231     [IN_INTERP] = {
232         TERMINAL(JSON_INTERP),
233         ['A' ... 'Z'] = IN_INTERP,
234         ['a' ... 'z'] = IN_INTERP,
235         ['0' ... '9'] = IN_INTERP,
236     },
237 
238     /*
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] = {
244         ['"'] = IN_DQ_STRING,
245         ['\''] = IN_SQ_STRING,
246         ['0'] = IN_ZERO,
247         ['1' ... '9'] = IN_DIGITS,
248         ['-'] = IN_SIGN,
249         ['{'] = JSON_LCURLY,
250         ['}'] = JSON_RCURLY,
251         ['['] = JSON_LSQUARE,
252         [']'] = JSON_RSQUARE,
253         [','] = JSON_COMMA,
254         [':'] = JSON_COLON,
255         ['a' ... 'z'] = IN_KEYWORD,
256         [' '] = IN_START,
257         ['\t'] = IN_START,
258         ['\r'] = IN_START,
259         ['\n'] = IN_START,
260     },
261     [IN_START_INTERP]['%'] = IN_INTERP,
262 };
263 
next_state(JSONLexer * lexer,char ch,bool flush,bool * char_consumed)264 static inline uint8_t next_state(JSONLexer *lexer, char ch, bool flush,
265                                  bool *char_consumed)
266 {
267     uint8_t next;
268 
269     assert(lexer->state < ARRAY_SIZE(json_lexer));
270     next = json_lexer[lexer->state][(uint8_t)ch];
271     *char_consumed = !flush && !(next & LOOKAHEAD);
272     return next & ~LOOKAHEAD;
273 }
274 
json_lexer_init(JSONLexer * lexer,bool enable_interpolation)275 void json_lexer_init(JSONLexer *lexer, bool enable_interpolation)
276 {
277     lexer->start_state = lexer->state = enable_interpolation
278         ? IN_START_INTERP : IN_START;
279     lexer->token = g_string_sized_new(3);
280     lexer->x = lexer->y = 0;
281 }
282 
json_lexer_feed_char(JSONLexer * lexer,char ch,bool flush)283 static void json_lexer_feed_char(JSONLexer *lexer, char ch, bool flush)
284 {
285     int new_state;
286     bool char_consumed = false;
287 
288     lexer->x++;
289     if (ch == '\n') {
290         lexer->x = 0;
291         lexer->y++;
292     }
293 
294     while (flush ? lexer->state != lexer->start_state : !char_consumed) {
295         new_state = next_state(lexer, ch, flush, &char_consumed);
296         if (char_consumed) {
297             assert(!flush);
298             g_string_append_c(lexer->token, ch);
299         }
300 
301         switch (new_state) {
302         case JSON_LCURLY:
303         case JSON_RCURLY:
304         case JSON_LSQUARE:
305         case JSON_RSQUARE:
306         case JSON_COLON:
307         case JSON_COMMA:
308         case JSON_INTERP:
309         case JSON_INTEGER:
310         case JSON_FLOAT:
311         case JSON_KEYWORD:
312         case JSON_STRING:
313             json_message_process_token(lexer, lexer->token, new_state,
314                                        lexer->x, lexer->y);
315             /* fall through */
316         case IN_START:
317             g_string_truncate(lexer->token, 0);
318             new_state = lexer->start_state;
319             break;
320         case JSON_ERROR:
321             json_message_process_token(lexer, lexer->token, JSON_ERROR,
322                                        lexer->x, lexer->y);
323             new_state = IN_RECOVERY;
324             /* fall through */
325         case IN_RECOVERY:
326             g_string_truncate(lexer->token, 0);
327             break;
328         default:
329             break;
330         }
331         lexer->state = new_state;
332     }
333 
334     /* Do not let a single token grow to an arbitrarily large size,
335      * this is a security consideration.
336      */
337     if (lexer->token->len > MAX_TOKEN_SIZE) {
338         json_message_process_token(lexer, lexer->token, lexer->state,
339                                    lexer->x, lexer->y);
340         g_string_truncate(lexer->token, 0);
341         lexer->state = lexer->start_state;
342     }
343 }
344 
json_lexer_feed(JSONLexer * lexer,const char * buffer,size_t size)345 void json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size)
346 {
347     size_t i;
348 
349     for (i = 0; i < size; i++) {
350         json_lexer_feed_char(lexer, buffer[i], false);
351     }
352 }
353 
json_lexer_flush(JSONLexer * lexer)354 void json_lexer_flush(JSONLexer *lexer)
355 {
356     json_lexer_feed_char(lexer, 0, true);
357     assert(lexer->state == lexer->start_state);
358     json_message_process_token(lexer, lexer->token, JSON_END_OF_INPUT,
359                                lexer->x, lexer->y);
360 }
361 
json_lexer_destroy(JSONLexer * lexer)362 void json_lexer_destroy(JSONLexer *lexer)
363 {
364     g_string_free(lexer->token, true);
365 }
366