Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 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 | /* |
| 22 | * \"([^\\\"]|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*\" |
| 23 | * '([^\\']|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*' |
| 24 | * 0|([1-9][0-9]*(.[0-9]+)?([eE]([-+])?[0-9]+)) |
| 25 | * [{}\[\],:] |
| 26 | * [a-z]+ |
| 27 | * |
| 28 | */ |
| 29 | |
| 30 | enum json_lexer_state { |
| 31 | ERROR = 0, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 32 | IN_DQ_UCODE3, |
| 33 | IN_DQ_UCODE2, |
| 34 | IN_DQ_UCODE1, |
| 35 | IN_DQ_UCODE0, |
| 36 | IN_DQ_STRING_ESCAPE, |
| 37 | IN_DQ_STRING, |
| 38 | IN_SQ_UCODE3, |
| 39 | IN_SQ_UCODE2, |
| 40 | IN_SQ_UCODE1, |
| 41 | IN_SQ_UCODE0, |
| 42 | IN_SQ_STRING_ESCAPE, |
| 43 | IN_SQ_STRING, |
| 44 | IN_ZERO, |
| 45 | IN_DIGITS, |
| 46 | IN_DIGIT, |
| 47 | IN_EXP_E, |
| 48 | IN_MANTISSA, |
| 49 | IN_MANTISSA_DIGITS, |
| 50 | IN_NONZERO_NUMBER, |
| 51 | IN_NEG_NONZERO_NUMBER, |
| 52 | IN_KEYWORD, |
| 53 | IN_ESCAPE, |
| 54 | IN_ESCAPE_L, |
| 55 | IN_ESCAPE_LL, |
Roy Tam | 2c0d4b3 | 2010-02-04 10:30:30 +0800 | [diff] [blame] | 56 | IN_ESCAPE_I, |
| 57 | IN_ESCAPE_I6, |
| 58 | IN_ESCAPE_I64, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 59 | IN_WHITESPACE, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 60 | IN_START, |
| 61 | }; |
| 62 | |
| 63 | #define TERMINAL(state) [0 ... 0x7F] = (state) |
| 64 | |
Paolo Bonzini | f7c0527 | 2010-05-24 09:39:52 +0200 | [diff] [blame] | 65 | /* Return whether TERMINAL is a terminal state and the transition to it |
| 66 | from OLD_STATE required lookahead. This happens whenever the table |
| 67 | below uses the TERMINAL macro. */ |
| 68 | #define TERMINAL_NEEDED_LOOKAHEAD(old_state, terminal) \ |
| 69 | (json_lexer[(old_state)][0] == (terminal)) |
| 70 | |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 71 | static const uint8_t json_lexer[][256] = { |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 72 | /* double quote string */ |
| 73 | [IN_DQ_UCODE3] = { |
| 74 | ['0' ... '9'] = IN_DQ_STRING, |
| 75 | ['a' ... 'f'] = IN_DQ_STRING, |
| 76 | ['A' ... 'F'] = IN_DQ_STRING, |
| 77 | }, |
| 78 | [IN_DQ_UCODE2] = { |
| 79 | ['0' ... '9'] = IN_DQ_UCODE3, |
| 80 | ['a' ... 'f'] = IN_DQ_UCODE3, |
| 81 | ['A' ... 'F'] = IN_DQ_UCODE3, |
| 82 | }, |
| 83 | [IN_DQ_UCODE1] = { |
| 84 | ['0' ... '9'] = IN_DQ_UCODE2, |
| 85 | ['a' ... 'f'] = IN_DQ_UCODE2, |
| 86 | ['A' ... 'F'] = IN_DQ_UCODE2, |
| 87 | }, |
| 88 | [IN_DQ_UCODE0] = { |
| 89 | ['0' ... '9'] = IN_DQ_UCODE1, |
| 90 | ['a' ... 'f'] = IN_DQ_UCODE1, |
| 91 | ['A' ... 'F'] = IN_DQ_UCODE1, |
| 92 | }, |
| 93 | [IN_DQ_STRING_ESCAPE] = { |
| 94 | ['b'] = IN_DQ_STRING, |
| 95 | ['f'] = IN_DQ_STRING, |
| 96 | ['n'] = IN_DQ_STRING, |
| 97 | ['r'] = IN_DQ_STRING, |
| 98 | ['t'] = IN_DQ_STRING, |
Luiz Capitulino | 1041ba7 | 2010-05-19 16:57:28 -0300 | [diff] [blame] | 99 | ['/'] = IN_DQ_STRING, |
| 100 | ['\\'] = IN_DQ_STRING, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 101 | ['\''] = IN_DQ_STRING, |
| 102 | ['\"'] = IN_DQ_STRING, |
| 103 | ['u'] = IN_DQ_UCODE0, |
| 104 | }, |
| 105 | [IN_DQ_STRING] = { |
| 106 | [1 ... 0xFF] = IN_DQ_STRING, |
| 107 | ['\\'] = IN_DQ_STRING_ESCAPE, |
Paolo Bonzini | 28e91a6 | 2010-05-24 09:39:53 +0200 | [diff] [blame] | 108 | ['"'] = JSON_STRING, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 109 | }, |
| 110 | |
| 111 | /* single quote string */ |
| 112 | [IN_SQ_UCODE3] = { |
| 113 | ['0' ... '9'] = IN_SQ_STRING, |
| 114 | ['a' ... 'f'] = IN_SQ_STRING, |
| 115 | ['A' ... 'F'] = IN_SQ_STRING, |
| 116 | }, |
| 117 | [IN_SQ_UCODE2] = { |
| 118 | ['0' ... '9'] = IN_SQ_UCODE3, |
| 119 | ['a' ... 'f'] = IN_SQ_UCODE3, |
| 120 | ['A' ... 'F'] = IN_SQ_UCODE3, |
| 121 | }, |
| 122 | [IN_SQ_UCODE1] = { |
| 123 | ['0' ... '9'] = IN_SQ_UCODE2, |
| 124 | ['a' ... 'f'] = IN_SQ_UCODE2, |
| 125 | ['A' ... 'F'] = IN_SQ_UCODE2, |
| 126 | }, |
| 127 | [IN_SQ_UCODE0] = { |
| 128 | ['0' ... '9'] = IN_SQ_UCODE1, |
| 129 | ['a' ... 'f'] = IN_SQ_UCODE1, |
| 130 | ['A' ... 'F'] = IN_SQ_UCODE1, |
| 131 | }, |
| 132 | [IN_SQ_STRING_ESCAPE] = { |
| 133 | ['b'] = IN_SQ_STRING, |
| 134 | ['f'] = IN_SQ_STRING, |
| 135 | ['n'] = IN_SQ_STRING, |
| 136 | ['r'] = IN_SQ_STRING, |
| 137 | ['t'] = IN_SQ_STRING, |
Luiz Capitulino | 1041ba7 | 2010-05-19 16:57:28 -0300 | [diff] [blame] | 138 | ['/'] = IN_DQ_STRING, |
| 139 | ['\\'] = IN_DQ_STRING, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 140 | ['\''] = IN_SQ_STRING, |
| 141 | ['\"'] = IN_SQ_STRING, |
| 142 | ['u'] = IN_SQ_UCODE0, |
| 143 | }, |
| 144 | [IN_SQ_STRING] = { |
| 145 | [1 ... 0xFF] = IN_SQ_STRING, |
| 146 | ['\\'] = IN_SQ_STRING_ESCAPE, |
Paolo Bonzini | 28e91a6 | 2010-05-24 09:39:53 +0200 | [diff] [blame] | 147 | ['\''] = JSON_STRING, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 148 | }, |
| 149 | |
| 150 | /* Zero */ |
| 151 | [IN_ZERO] = { |
| 152 | TERMINAL(JSON_INTEGER), |
| 153 | ['0' ... '9'] = ERROR, |
| 154 | ['.'] = IN_MANTISSA, |
| 155 | }, |
| 156 | |
| 157 | /* Float */ |
| 158 | [IN_DIGITS] = { |
| 159 | TERMINAL(JSON_FLOAT), |
| 160 | ['0' ... '9'] = IN_DIGITS, |
| 161 | }, |
| 162 | |
| 163 | [IN_DIGIT] = { |
| 164 | ['0' ... '9'] = IN_DIGITS, |
| 165 | }, |
| 166 | |
| 167 | [IN_EXP_E] = { |
| 168 | ['-'] = IN_DIGIT, |
| 169 | ['+'] = IN_DIGIT, |
| 170 | ['0' ... '9'] = IN_DIGITS, |
| 171 | }, |
| 172 | |
| 173 | [IN_MANTISSA_DIGITS] = { |
| 174 | TERMINAL(JSON_FLOAT), |
| 175 | ['0' ... '9'] = IN_MANTISSA_DIGITS, |
| 176 | ['e'] = IN_EXP_E, |
| 177 | ['E'] = IN_EXP_E, |
| 178 | }, |
| 179 | |
| 180 | [IN_MANTISSA] = { |
| 181 | ['0' ... '9'] = IN_MANTISSA_DIGITS, |
| 182 | }, |
| 183 | |
| 184 | /* Number */ |
| 185 | [IN_NONZERO_NUMBER] = { |
| 186 | TERMINAL(JSON_INTEGER), |
| 187 | ['0' ... '9'] = IN_NONZERO_NUMBER, |
| 188 | ['e'] = IN_EXP_E, |
| 189 | ['E'] = IN_EXP_E, |
| 190 | ['.'] = IN_MANTISSA, |
| 191 | }, |
| 192 | |
| 193 | [IN_NEG_NONZERO_NUMBER] = { |
| 194 | ['0'] = IN_ZERO, |
| 195 | ['1' ... '9'] = IN_NONZERO_NUMBER, |
| 196 | }, |
| 197 | |
| 198 | /* keywords */ |
| 199 | [IN_KEYWORD] = { |
| 200 | TERMINAL(JSON_KEYWORD), |
| 201 | ['a' ... 'z'] = IN_KEYWORD, |
| 202 | }, |
| 203 | |
| 204 | /* whitespace */ |
| 205 | [IN_WHITESPACE] = { |
| 206 | TERMINAL(JSON_SKIP), |
| 207 | [' '] = IN_WHITESPACE, |
| 208 | ['\t'] = IN_WHITESPACE, |
| 209 | ['\r'] = IN_WHITESPACE, |
| 210 | ['\n'] = IN_WHITESPACE, |
| 211 | }, |
| 212 | |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 213 | /* escape */ |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 214 | [IN_ESCAPE_LL] = { |
Paolo Bonzini | 28e91a6 | 2010-05-24 09:39:53 +0200 | [diff] [blame] | 215 | ['d'] = JSON_ESCAPE, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 216 | }, |
| 217 | |
| 218 | [IN_ESCAPE_L] = { |
Paolo Bonzini | 28e91a6 | 2010-05-24 09:39:53 +0200 | [diff] [blame] | 219 | ['d'] = JSON_ESCAPE, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 220 | ['l'] = IN_ESCAPE_LL, |
| 221 | }, |
| 222 | |
Roy Tam | 2c0d4b3 | 2010-02-04 10:30:30 +0800 | [diff] [blame] | 223 | [IN_ESCAPE_I64] = { |
Paolo Bonzini | 28e91a6 | 2010-05-24 09:39:53 +0200 | [diff] [blame] | 224 | ['d'] = JSON_ESCAPE, |
Roy Tam | 2c0d4b3 | 2010-02-04 10:30:30 +0800 | [diff] [blame] | 225 | }, |
| 226 | |
| 227 | [IN_ESCAPE_I6] = { |
| 228 | ['4'] = IN_ESCAPE_I64, |
| 229 | }, |
| 230 | |
| 231 | [IN_ESCAPE_I] = { |
| 232 | ['6'] = IN_ESCAPE_I6, |
| 233 | }, |
| 234 | |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 235 | [IN_ESCAPE] = { |
Paolo Bonzini | 28e91a6 | 2010-05-24 09:39:53 +0200 | [diff] [blame] | 236 | ['d'] = JSON_ESCAPE, |
| 237 | ['i'] = JSON_ESCAPE, |
| 238 | ['p'] = JSON_ESCAPE, |
| 239 | ['s'] = JSON_ESCAPE, |
| 240 | ['f'] = JSON_ESCAPE, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 241 | ['l'] = IN_ESCAPE_L, |
Roy Tam | 2c0d4b3 | 2010-02-04 10:30:30 +0800 | [diff] [blame] | 242 | ['I'] = IN_ESCAPE_I, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 243 | }, |
| 244 | |
| 245 | /* top level rule */ |
| 246 | [IN_START] = { |
| 247 | ['"'] = IN_DQ_STRING, |
| 248 | ['\''] = IN_SQ_STRING, |
| 249 | ['0'] = IN_ZERO, |
| 250 | ['1' ... '9'] = IN_NONZERO_NUMBER, |
| 251 | ['-'] = IN_NEG_NONZERO_NUMBER, |
Paolo Bonzini | 28e91a6 | 2010-05-24 09:39:53 +0200 | [diff] [blame] | 252 | ['{'] = JSON_OPERATOR, |
| 253 | ['}'] = JSON_OPERATOR, |
| 254 | ['['] = JSON_OPERATOR, |
| 255 | [']'] = JSON_OPERATOR, |
| 256 | [','] = JSON_OPERATOR, |
| 257 | [':'] = JSON_OPERATOR, |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 258 | ['a' ... 'z'] = IN_KEYWORD, |
| 259 | ['%'] = IN_ESCAPE, |
| 260 | [' '] = IN_WHITESPACE, |
| 261 | ['\t'] = IN_WHITESPACE, |
| 262 | ['\r'] = IN_WHITESPACE, |
| 263 | ['\n'] = IN_WHITESPACE, |
| 264 | }, |
| 265 | }; |
| 266 | |
| 267 | void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func) |
| 268 | { |
| 269 | lexer->emit = func; |
| 270 | lexer->state = IN_START; |
| 271 | lexer->token = qstring_new(); |
Luiz Capitulino | 03308f6 | 2010-05-17 17:50:01 -0300 | [diff] [blame] | 272 | lexer->x = lexer->y = 0; |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 273 | } |
| 274 | |
| 275 | static int json_lexer_feed_char(JSONLexer *lexer, char ch) |
| 276 | { |
Paolo Bonzini | f7c0527 | 2010-05-24 09:39:52 +0200 | [diff] [blame] | 277 | int char_consumed, new_state; |
| 278 | |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 279 | lexer->x++; |
| 280 | if (ch == '\n') { |
| 281 | lexer->x = 0; |
| 282 | lexer->y++; |
| 283 | } |
| 284 | |
Paolo Bonzini | f7c0527 | 2010-05-24 09:39:52 +0200 | [diff] [blame] | 285 | do { |
| 286 | new_state = json_lexer[lexer->state][(uint8_t)ch]; |
| 287 | char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state); |
| 288 | if (char_consumed) { |
| 289 | qstring_append_chr(lexer->token, ch); |
| 290 | } |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 291 | |
Paolo Bonzini | f7c0527 | 2010-05-24 09:39:52 +0200 | [diff] [blame] | 292 | switch (new_state) { |
| 293 | case JSON_OPERATOR: |
| 294 | case JSON_ESCAPE: |
| 295 | case JSON_INTEGER: |
| 296 | case JSON_FLOAT: |
| 297 | case JSON_KEYWORD: |
| 298 | case JSON_STRING: |
| 299 | lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y); |
| 300 | case JSON_SKIP: |
| 301 | QDECREF(lexer->token); |
| 302 | lexer->token = qstring_new(); |
| 303 | new_state = IN_START; |
| 304 | break; |
| 305 | case ERROR: |
| 306 | return -EINVAL; |
| 307 | default: |
| 308 | break; |
| 309 | } |
| 310 | lexer->state = new_state; |
| 311 | } while (!char_consumed); |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 312 | return 0; |
| 313 | } |
| 314 | |
| 315 | int json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size) |
| 316 | { |
| 317 | size_t i; |
| 318 | |
| 319 | for (i = 0; i < size; i++) { |
| 320 | int err; |
| 321 | |
| 322 | err = json_lexer_feed_char(lexer, buffer[i]); |
| 323 | if (err < 0) { |
| 324 | return err; |
| 325 | } |
| 326 | } |
| 327 | |
| 328 | return 0; |
| 329 | } |
| 330 | |
| 331 | int json_lexer_flush(JSONLexer *lexer) |
| 332 | { |
Paolo Bonzini | f7c0527 | 2010-05-24 09:39:52 +0200 | [diff] [blame] | 333 | return lexer->state == IN_START ? 0 : json_lexer_feed_char(lexer, 0); |
Anthony Liguori | 5ab8558 | 2009-11-11 10:39:14 -0600 | [diff] [blame] | 334 | } |
| 335 | |
| 336 | void json_lexer_destroy(JSONLexer *lexer) |
| 337 | { |
| 338 | QDECREF(lexer->token); |
| 339 | } |