wsutil/jsmn.c

   1 /*
   2 Copyright (c) 2010 Serge A. Zaitsev
   3
   4 Permission is hereby granted, free of charge, to any person obtaining a copy
   5 of this software and associated documentation files (the "Software"), to deal
   6 in the Software without restriction, including without limitation the rights
   7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8 copies of the Software, and to permit persons to whom the Software is
   9 furnished to do so, subject to the following conditions:
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20 THE SOFTWARE.
  21 */
  22
  23 #include "jsmn.h"
  24
  25 /**
  26  * Allocates a fresh unused token from the token pull.
  27  */
  28 static jsmntok_t *jsmn_alloc_token(jsmn_parser *parser,
  29                 jsmntok_t *tokens, size_t num_tokens) {
  30         jsmntok_t *tok;
  31         if (parser->toknext >= num_tokens) {
  32                 return NULL;
  33         }
  34         tok = &tokens[parser->toknext++];
  35         tok->start = tok->end = -1;
  36         tok->size = 0;
  37 #ifdef JSMN_PARENT_LINKS
  38         tok->parent = -1;
  39 #endif
  40         return tok;
  41 }
  42
  43 /**
  44  * Fills token type and boundaries.
  45  */
  46 static void jsmn_fill_token(jsmntok_t *token, jsmntype_t type,
  47                             int start, int end) {
  48         token->type = type;
  49         token->start = start;
  50         token->end = end;
  51         token->size = 0;
  52 }
  53
  54 /**
  55  * Fills next available token with JSON primitive.
  56  */
  57 static int jsmn_parse_primitive(jsmn_parser *parser, const char *js,
  58                 size_t len, jsmntok_t *tokens, size_t num_tokens) {
  59         jsmntok_t *token;
  60         int start;
  61
  62         start = parser->pos;
  63
  64         for (; parser->pos < len && js[parser->pos] != '\0'; parser->pos++) {
  65                 switch (js[parser->pos]) {
  66 #ifndef JSMN_STRICT
  67                         /* In strict mode primitive must be followed by "," or "}" or "]" */
  68                         case ':':
  69 #endif
  70                         case '\t' : case '\r' : case '\n' : case ' ' :
  71                         case ','  : case ']'  : case '}' :
  72                                 goto found;
  73                 }
  74                 if (js[parser->pos] < 32 || js[parser->pos] >= 127) {
  75                         parser->pos = start;
  76                         return JSMN_ERROR_INVAL;
  77                 }
  78         }
  79 #ifdef JSMN_STRICT
  80         /* In strict mode primitive must be followed by a comma/object/array */
  81         parser->pos = start;
  82         return JSMN_ERROR_PART;
  83 #endif
  84
  85 found:
  86         if (tokens == NULL) {
  87                 parser->pos--;
  88                 return 0;
  89         }
  90         token = jsmn_alloc_token(parser, tokens, num_tokens);
  91         if (token == NULL) {
  92                 parser->pos = start;
  93                 return JSMN_ERROR_NOMEM;
  94         }
  95         jsmn_fill_token(token, JSMN_PRIMITIVE, start, parser->pos);
  96 #ifdef JSMN_PARENT_LINKS
  97         token->parent = parser->toksuper;
  98 #endif
  99         parser->pos--;
 100         return 0;
 101 }
 102
 103 /**
 104  * Fills next token with JSON string.
 105  */
 106 static int jsmn_parse_string(jsmn_parser *parser, const char *js,
 107                 size_t len, jsmntok_t *tokens, size_t num_tokens) {
 108         jsmntok_t *token;
 109
 110         int start = parser->pos;
 111
 112         parser->pos++;
 113
 114         /* Skip starting quote */
 115         for (; parser->pos < len && js[parser->pos] != '\0'; parser->pos++) {
 116                 char c = js[parser->pos];
 117
 118                 /* Quote: end of string */
 119                 if (c == '\"') {
 120                         if (tokens == NULL) {
 121                                 return 0;
 122                         }
 123                         token = jsmn_alloc_token(parser, tokens, num_tokens);
 124                         if (token == NULL) {
 125                                 parser->pos = start;
 126                                 return JSMN_ERROR_NOMEM;
 127                         }
 128                         jsmn_fill_token(token, JSMN_STRING, start+1, parser->pos);
 129 #ifdef JSMN_PARENT_LINKS
 130                         token->parent = parser->toksuper;
 131 #endif
 132                         return 0;
 133                 }
 134
 135                 /* Backslash: Quoted symbol expected */
 136                 if (c == '\\' && parser->pos + 1 < len) {
 137                         int i;
 138                         parser->pos++;
 139                         switch (js[parser->pos]) {
 140                                 /* Allowed escaped symbols */
 141                                 case '\"': case '/' : case '\\' : case 'b' :
 142                                 case 'f' : case 'r' : case 'n'  : case 't' :
 143                                         break;
 144                                 /* Allows escaped symbol \uXXXX */
 145                                 case 'u':
 146                                         parser->pos++;
 147                                         for(i = 0; i < 4 && parser->pos < len && js[parser->pos] != '\0'; i++) {
 148                                                 /* If it isn't a hex character we have an error */
 149                                                 if(!((js[parser->pos] >= 48 && js[parser->pos] <= 57) || /* 0-9 */
 150                                                                         (js[parser->pos] >= 65 && js[parser->pos] <= 70) || /* A-F */
 151                                                                         (js[parser->pos] >= 97 && js[parser->pos] <= 102))) { /* a-f */
 152                                                         parser->pos = start;
 153                                                         return JSMN_ERROR_INVAL;
 154                                                 }
 155                                                 parser->pos++;
 156                                         }
 157                                         parser->pos--;
 158                                         break;
 159                                 /* Unexpected symbol */
 160                                 default:
 161                                         parser->pos = start;
 162                                         return JSMN_ERROR_INVAL;
 163                         }
 164                 }
 165         }
 166         parser->pos = start;
 167         return JSMN_ERROR_PART;
 168 }
 169
 170 /**
 171  * Parse JSON string and fill tokens.
 172  */
 173 int jsmn_parse(jsmn_parser *parser, const char *js, size_t len,
 174                 jsmntok_t *tokens, unsigned int num_tokens) {
 175         int r;
 176         int i;
 177         jsmntok_t *token;
 178         int count = parser->toknext;
 179
 180         for (; parser->pos < len && js[parser->pos] != '\0'; parser->pos++) {
 181                 char c;
 182                 jsmntype_t type;
 183
 184                 c = js[parser->pos];
 185                 switch (c) {
 186                         case '{': case '[':
 187                                 count++;
 188                                 if (tokens == NULL) {
 189                                         break;
 190                                 }
 191                                 token = jsmn_alloc_token(parser, tokens, num_tokens);
 192                                 if (token == NULL)
 193                                         return JSMN_ERROR_NOMEM;
 194                                 if (parser->toksuper != -1) {
 195                                         tokens[parser->toksuper].size++;
 196 #ifdef JSMN_PARENT_LINKS
 197                                         token->parent = parser->toksuper;
 198 #endif
 199                                 }
 200                                 token->type = (c == '{' ? JSMN_OBJECT : JSMN_ARRAY);
 201                                 token->start = parser->pos;
 202                                 parser->toksuper = parser->toknext - 1;
 203                                 break;
 204                         case '}': case ']':
 205                                 if (tokens == NULL)
 206                                         break;
 207                                 type = (c == '}' ? JSMN_OBJECT : JSMN_ARRAY);
 208 #ifdef JSMN_PARENT_LINKS
 209                                 if (parser->toknext < 1) {
 210                                         return JSMN_ERROR_INVAL;
 211                                 }
 212                                 token = &tokens[parser->toknext - 1];
 213                                 for (;;) {
 214                                         if (token->start != -1 && token->end == -1) {
 215                                                 if (token->type != type) {
 216                                                         return JSMN_ERROR_INVAL;
 217                                                 }
 218                                                 token->end = parser->pos + 1;
 219                                                 parser->toksuper = token->parent;
 220                                                 break;
 221                                         }
 222                                         if (token->parent == -1) {
 223                                                 break;
 224                                         }
 225                                         token = &tokens[token->parent];
 226                                 }
 227 #else
 228                                 for (i = parser->toknext - 1; i >= 0; i--) {
 229                                         token = &tokens[i];
 230                                         if (token->start != -1 && token->end == -1) {
 231                                                 if (token->type != type) {
 232                                                         return JSMN_ERROR_INVAL;
 233                                                 }
 234                                                 parser->toksuper = -1;
 235                                                 token->end = parser->pos + 1;
 236                                                 break;
 237                                         }
 238                                 }
 239                                 /* Error if unmatched closing bracket */
 240                                 if (i == -1) return JSMN_ERROR_INVAL;
 241                                 for (; i >= 0; i--) {
 242                                         token = &tokens[i];
 243                                         if (token->start != -1 && token->end == -1) {
 244                                                 parser->toksuper = i;
 245                                                 break;
 246                                         }
 247                                 }
 248 #endif
 249                                 break;
 250                         case '\"':
 251                                 r = jsmn_parse_string(parser, js, len, tokens, num_tokens);
 252                                 if (r < 0) return r;
 253                                 count++;
 254                                 if (parser->toksuper != -1 && tokens != NULL)
 255                                         tokens[parser->toksuper].size++;
 256                                 break;
 257                         case '\t' : case '\r' : case '\n' : case ' ':
 258                                 break;
 259                         case ':':
 260                                 parser->toksuper = parser->toknext - 1;
 261                                 break;
 262                         case ',':
 263                                 if (tokens != NULL && parser->toksuper != -1 &&
 264                                                 tokens[parser->toksuper].type != JSMN_ARRAY &&
 265                                                 tokens[parser->toksuper].type != JSMN_OBJECT) {
 266 #ifdef JSMN_PARENT_LINKS
 267                                         parser->toksuper = tokens[parser->toksuper].parent;
 268 #else
 269                                         for (i = parser->toknext - 1; i >= 0; i--) {
 270                                                 if (tokens[i].type == JSMN_ARRAY || tokens[i].type == JSMN_OBJECT) {
 271                                                         if (tokens[i].start != -1 && tokens[i].end == -1) {
 272                                                                 parser->toksuper = i;
 273                                                                 break;
 274                                                         }
 275                                                 }
 276                                         }
 277 #endif
 278                                 }
 279                                 break;
 280 #ifdef JSMN_STRICT
 281                         /* In strict mode primitives are: numbers and booleans */
 282                         case '-': case '0': case '1' : case '2': case '3' : case '4':
 283                         case '5': case '6': case '7' : case '8': case '9':
 284                         case 't': case 'f': case 'n' :
 285                                 /* And they must not be keys of the object */
 286                                 if (tokens != NULL && parser->toksuper != -1) {
 287                                         jsmntok_t *t = &tokens[parser->toksuper];
 288                                         if (t->type == JSMN_OBJECT ||
 289                                                         (t->type == JSMN_STRING && t->size != 0)) {
 290                                                 return JSMN_ERROR_INVAL;
 291                                         }
 292                                 }
 293 #else
 294                         /* In non-strict mode every unquoted value is a primitive */
 295                         default:
 296 #endif
 297                                 r = jsmn_parse_primitive(parser, js, len, tokens, num_tokens);
 298                                 if (r < 0) return r;
 299                                 count++;
 300                                 if (parser->toksuper != -1 && tokens != NULL)
 301                                         tokens[parser->toksuper].size++;
 302                                 break;
 303
 304 #ifdef JSMN_STRICT
 305                         /* Unexpected char in strict mode */
 306                         default:
 307                                 return JSMN_ERROR_INVAL;
 308 #endif
 309                 }
 310         }
 311
 312         if (tokens != NULL) {
 313                 for (i = parser->toknext - 1; i >= 0; i--) {
 314                         /* Unmatched opened object or array */
 315                         if (tokens[i].start != -1 && tokens[i].end == -1) {
 316                                 return JSMN_ERROR_PART;
 317                         }
 318                 }
 319         }
 320
 321         return count;
 322 }
 323
 324 /**
 325  * Creates a new parser based over a given  buffer with an array of tokens
 326  * available.
 327  */
 328 void jsmn_init(jsmn_parser *parser) {
 329         parser->pos = 0;
 330         parser->toknext = 0;
 331         parser->toksuper = -1;
 332 }