jsmn.c

00001 /*
00002  * Copyright (c) 2010 Serge A. Zaitsev
00003  *
00004  * Permission is hereby granted, free of charge, to any person obtaining a copy
00005  * of this software and associated documentation files (the "Software"), to deal
00006  * in the Software without restriction, including without limitation the rights
00007  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
00008  * copies of the Software, and to permit persons to whom the Software is
00009  * furnished to do so, subject to the following conditions:
00010  *
00011  * The above copyright notice and this permission notice shall be included in
00012  * all copies or substantial portions of the Software.
00013  *
00014  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00015  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00016  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
00017  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00018  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00019  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
00020  * THE SOFTWARE.
00021  */
00022 
00023 /**
00024  * @file jsmn.c
00025  * @brief Implementation of the JSMN (Jasmine) JSON parser.
00026  *
00027  * For more information on JSMN:
00028  * @see http://zserge.com/jsmn.html
00029  */
00030 
00031 #include "jsmn.h"
00032 
00033 /**
00034  * Allocates a fresh unused token from the token pull.
00035  */
00036 static jsmntok_t *jsmn_alloc_token(jsmn_parser *parser,
00037         jsmntok_t *tokens, size_t num_tokens) {
00038     jsmntok_t *tok;
00039     if (parser->toknext >= num_tokens) {
00040         return NULL;
00041     }
00042     tok = &tokens[parser->toknext++];
00043     tok->start = tok->end = -1;
00044     tok->size = 0;
00045 #ifdef JSMN_PARENT_LINKS
00046     tok->parent = -1;
00047 #endif
00048     return tok;
00049 }
00050 
00051 /**
00052  * Fills token type and boundaries.
00053  */
00054 static void jsmn_fill_token(jsmntok_t *token, jsmntype_t type,
00055                             int start, int end) {
00056     token->type = type;
00057     token->start = start;
00058     token->end = end;
00059     token->size = 0;
00060 }
00061 
00062 /**
00063  * Fills next available token with JSON primitive.
00064  */
00065 static int jsmn_parse_primitive(jsmn_parser *parser, const char *js,
00066         size_t len, jsmntok_t *tokens, size_t num_tokens) {
00067     jsmntok_t *token;
00068     int start;
00069 
00070     start = parser->pos;
00071 
00072     for (; parser->pos < len && js[parser->pos] != '\0'; parser->pos++) {
00073         switch (js[parser->pos]) {
00074 #ifndef JSMN_STRICT
00075             /* In strict mode primitive must be followed by "," or "}" or "]" */
00076             case ':':
00077 #endif
00078             case '\t' : case '\r' : case '\n' : case ' ' :
00079             case ','  : case ']'  : case '}' :
00080                 goto found;
00081         }
00082         if (js[parser->pos] < 32 || js[parser->pos] >= 127) {
00083             parser->pos = start;
00084             return JSMN_ERROR_INVAL;
00085         }
00086     }
00087 #ifdef JSMN_STRICT
00088     /* In strict mode primitive must be followed by a comma/object/array */
00089     parser->pos = start;
00090     return JSMN_ERROR_PART;
00091 #endif
00092 
00093 found:
00094     if (tokens == NULL) {
00095         parser->pos--;
00096         return 0;
00097     }
00098     token = jsmn_alloc_token(parser, tokens, num_tokens);
00099     if (token == NULL) {
00100         parser->pos = start;
00101         return JSMN_ERROR_NOMEM;
00102     }
00103     jsmn_fill_token(token, JSMN_PRIMITIVE, start, parser->pos);
00104 #ifdef JSMN_PARENT_LINKS
00105     token->parent = parser->toksuper;
00106 #endif
00107     parser->pos--;
00108     return 0;
00109 }
00110 
00111 /**
00112  * Fills next token with JSON string.
00113  */
00114 static int jsmn_parse_string(jsmn_parser *parser, const char *js,
00115         size_t len, jsmntok_t *tokens, size_t num_tokens) {
00116     jsmntok_t *token;
00117 
00118     int start = parser->pos;
00119 
00120     parser->pos++;
00121 
00122     /* Skip starting quote */
00123     for (; parser->pos < len && js[parser->pos] != '\0'; parser->pos++) {
00124         char c = js[parser->pos];
00125 
00126         /* Quote: end of string */
00127         if (c == '\"') {
00128             if (tokens == NULL) {
00129                 return 0;
00130             }
00131             token = jsmn_alloc_token(parser, tokens, num_tokens);
00132             if (token == NULL) {
00133                 parser->pos = start;
00134                 return JSMN_ERROR_NOMEM;
00135             }
00136             jsmn_fill_token(token, JSMN_STRING, start+1, parser->pos);
00137 #ifdef JSMN_PARENT_LINKS
00138             token->parent = parser->toksuper;
00139 #endif
00140             return 0;
00141         }
00142 
00143         /* Backslash: Quoted symbol expected */
00144         if (c == '\\' && parser->pos + 1 < len) {
00145             int i;
00146             parser->pos++;
00147             switch (js[parser->pos]) {
00148                 /* Allowed escaped symbols */
00149                 case '\"': case '/' : case '\\' : case 'b' :
00150                 case 'f' : case 'r' : case 'n'  : case 't' :
00151                     break;
00152                 /* Allows escaped symbol \uXXXX */
00153                 case 'u':
00154                     parser->pos++;
00155                     for(i = 0; i < 4 && parser->pos < len && js[parser->pos] != '\0'; i++) {
00156                         /* If it isn't a hex character we have an error */
00157                         if(!((js[parser->pos] >= 48 && js[parser->pos] <= 57) || /* 0-9 */
00158                                     (js[parser->pos] >= 65 && js[parser->pos] <= 70) || /* A-F */
00159                                     (js[parser->pos] >= 97 && js[parser->pos] <= 102))) { /* a-f */
00160                             parser->pos = start;
00161                             return JSMN_ERROR_INVAL;
00162                         }
00163                         parser->pos++;
00164                     }
00165                     parser->pos--;
00166                     break;
00167                 /* Unexpected symbol */
00168                 default:
00169                     parser->pos = start;
00170                     return JSMN_ERROR_INVAL;
00171             }
00172         }
00173     }
00174     parser->pos = start;
00175     return JSMN_ERROR_PART;
00176 }
00177 
00178 /**
00179  * Parse JSON string and fill tokens.
00180  */
00181 int jsmn_parse(jsmn_parser *parser, const char *js, size_t len,
00182         jsmntok_t *tokens, unsigned int num_tokens) {
00183     int r;
00184     int i;
00185     jsmntok_t *token;
00186     int count = parser->toknext;
00187 
00188     for (; parser->pos < len && js[parser->pos] != '\0'; parser->pos++) {
00189         char c;
00190         jsmntype_t type;
00191 
00192         c = js[parser->pos];
00193         switch (c) {
00194             case '{': case '[':
00195                 count++;
00196                 if (tokens == NULL) {
00197                     break;
00198                 }
00199                 token = jsmn_alloc_token(parser, tokens, num_tokens);
00200                 if (token == NULL)
00201                     return JSMN_ERROR_NOMEM;
00202                 if (parser->toksuper != -1) {
00203                     tokens[parser->toksuper].size++;
00204 #ifdef JSMN_PARENT_LINKS
00205                     token->parent = parser->toksuper;
00206 #endif
00207                 }
00208                 token->type = (c == '{' ? JSMN_OBJECT : JSMN_ARRAY);
00209                 token->start = parser->pos;
00210                 parser->toksuper = parser->toknext - 1;
00211                 break;
00212             case '}': case ']':
00213                 if (tokens == NULL)
00214                     break;
00215                 type = (c == '}' ? JSMN_OBJECT : JSMN_ARRAY);
00216 #ifdef JSMN_PARENT_LINKS
00217                 if (parser->toknext < 1) {
00218                     return JSMN_ERROR_INVAL;
00219                 }
00220                 token = &tokens[parser->toknext - 1];
00221                 for (;;) {
00222                     if (token->start != -1 && token->end == -1) {
00223                         if (token->type != type) {
00224                             return JSMN_ERROR_INVAL;
00225                         }
00226                         token->end = parser->pos + 1;
00227                         parser->toksuper = token->parent;
00228                         break;
00229                     }
00230                     if (token->parent == -1) {
00231                         if(token->type != type || parser->toksuper == -1) {
00232                             return JSMN_ERROR_INVAL;
00233                         }
00234                         break;
00235                     }
00236                     token = &tokens[token->parent];
00237                 }
00238 #else
00239                 for (i = parser->toknext - 1; i >= 0; i--) {
00240                     token = &tokens[i];
00241                     if (token->start != -1 && token->end == -1) {
00242                         if (token->type != type) {
00243                             return JSMN_ERROR_INVAL;
00244                         }
00245                         parser->toksuper = -1;
00246                         token->end = parser->pos + 1;
00247                         break;
00248                     }
00249                 }
00250                 /* Error if unmatched closing bracket */
00251                 if (i == -1) return JSMN_ERROR_INVAL;
00252                 for (; i >= 0; i--) {
00253                     token = &tokens[i];
00254                     if (token->start != -1 && token->end == -1) {
00255                         parser->toksuper = i;
00256                         break;
00257                     }
00258                 }
00259 #endif
00260                 break;
00261             case '\"':
00262                 r = jsmn_parse_string(parser, js, len, tokens, num_tokens);
00263                 if (r < 0) return r;
00264                 count++;
00265                 if (parser->toksuper != -1 && tokens != NULL)
00266                     tokens[parser->toksuper].size++;
00267                 break;
00268             case '\t' : case '\r' : case '\n' : case ' ':
00269                 break;
00270             case ':':
00271                 parser->toksuper = parser->toknext - 1;
00272                 break;
00273             case ',':
00274                 if (tokens != NULL && parser->toksuper != -1 &&
00275                         tokens[parser->toksuper].type != JSMN_ARRAY &&
00276                         tokens[parser->toksuper].type != JSMN_OBJECT) {
00277 #ifdef JSMN_PARENT_LINKS
00278                     parser->toksuper = tokens[parser->toksuper].parent;
00279 #else
00280                     for (i = parser->toknext - 1; i >= 0; i--) {
00281                         if (tokens[i].type == JSMN_ARRAY || tokens[i].type == JSMN_OBJECT) {
00282                             if (tokens[i].start != -1 && tokens[i].end == -1) {
00283                                 parser->toksuper = i;
00284                                 break;
00285                             }
00286                         }
00287                     }
00288 #endif
00289                 }
00290                 break;
00291 #ifdef JSMN_STRICT
00292             /* In strict mode primitives are: numbers and booleans */
00293             case '-': case '0': case '1' : case '2': case '3' : case '4':
00294             case '5': case '6': case '7' : case '8': case '9':
00295             case 't': case 'f': case 'n' :
00296                 /* And they must not be keys of the object */
00297                 if (tokens != NULL && parser->toksuper != -1) {
00298                     jsmntok_t *t = &tokens[parser->toksuper];
00299                     if (t->type == JSMN_OBJECT ||
00300                             (t->type == JSMN_STRING && t->size != 0)) {
00301                         return JSMN_ERROR_INVAL;
00302                     }
00303                 }
00304 #else
00305             /* In non-strict mode every unquoted value is a primitive */
00306             default:
00307 #endif
00308                 r = jsmn_parse_primitive(parser, js, len, tokens, num_tokens);
00309                 if (r < 0) return r;
00310                 count++;
00311                 if (parser->toksuper != -1 && tokens != NULL)
00312                     tokens[parser->toksuper].size++;
00313                 break;
00314 
00315 #ifdef JSMN_STRICT
00316             /* Unexpected char in strict mode */
00317             default:
00318                 return JSMN_ERROR_INVAL;
00319 #endif
00320         }
00321     }
00322 
00323     if (tokens != NULL) {
00324         for (i = parser->toknext - 1; i >= 0; i--) {
00325             /* Unmatched opened object or array */
00326             if (tokens[i].start != -1 && tokens[i].end == -1) {
00327                 return JSMN_ERROR_PART;
00328             }
00329         }
00330     }
00331 
00332     return count;
00333 }
00334 
00335 /**
00336  * Creates a new parser based over a given  buffer with an array of tokens
00337  * available.
00338  */
00339 void jsmn_init(jsmn_parser *parser) {
00340     parser->pos = 0;
00341     parser->toknext = 0;
00342     parser->toksuper = -1;
00343 }
00344