2 * $Id: json_tokener.c,v 1.20 2006/07/25 03:24:50 mclark Exp $
4 * Copyright (c) 2004, 2005 Metaparadigm Pte. Ltd.
5 * Michael Clark <michael@metaparadigm.com>
7 * This library is free software; you can redistribute it and/or modify
8 * it under the terms of the MIT license. See COPYING for details.
11 * Copyright (c) 2008-2009 Yahoo! Inc. All rights reserved.
12 * The copyrights to the contents of this file are licensed under the MIT License
13 * (http://www.opensource.org/licenses/mit-license.php)
28 #include "arraylist.h"
29 #include "json_inttypes.h"
30 #include "json_object.h"
31 #include "json_tokener.h"
32 #include "json_util.h"
34 #if !HAVE_STRDUP && defined(_MSC_VER)
35 /* MSC has the version as _strdup */
36 # define strdup _strdup
38 # error You do not have strdup on your system.
39 #endif /* HAVE_STRDUP */
41 #if !HAVE_STRNCASECMP && defined(_MSC_VER)
42 /* MSC has the version as _strnicmp */
43 # define strncasecmp _strnicmp
44 #elif !HAVE_STRNCASECMP
45 # error You do not have strncasecmp on your system.
46 #endif /* HAVE_STRNCASECMP */
48 static const char* json_null_str = "null";
49 static const char* json_true_str = "true";
50 static const char* json_false_str = "false";
52 // XXX after v0.10 this array will become static:
53 const char* json_tokener_errors[] = {
57 "unexpected end of data",
58 "unexpected character",
62 "array value separator ',' expected",
63 "quoted object property name expected",
64 "object property name separator ':' expected",
65 "object value separator ',' expected",
66 "invalid string sequence",
70 const char *json_tokener_error_desc(enum json_tokener_error jerr)
72 if (jerr < 0 || jerr > sizeof(json_tokener_errors))
73 return "Unknown error, invalid json_tokener_error value passed to json_tokener_error_desc()";
74 return json_tokener_errors[jerr];
77 enum json_tokener_error json_tokener_get_error(json_tokener *tok)
82 /* Stuff for decoding unicode sequences */
83 #define IS_HIGH_SURROGATE(uc) (((uc) & 0xFC00) == 0xD800)
84 #define IS_LOW_SURROGATE(uc) (((uc) & 0xFC00) == 0xDC00)
85 #define DECODE_SURROGATE_PAIR(hi,lo) ((((hi) & 0x3FF) << 10) + ((lo) & 0x3FF) + 0x10000)
86 static unsigned char utf8_replacement_char[3] = { 0xEF, 0xBF, 0xBD };
88 struct json_tokener* json_tokener_new_ex(int depth)
90 struct json_tokener *tok;
92 tok = (struct json_tokener*)calloc(1, sizeof(struct json_tokener));
93 if (!tok) return NULL;
94 tok->stack = (struct json_tokener*)calloc(depth, sizeof(struct json_tokener_srec));
99 tok->pb = printbuf_new();
100 tok->max_depth = depth;
101 json_tokener_reset(tok);
105 struct json_tokener* json_tokener_new(void)
107 return json_tokener_new_ex(JSON_TOKENER_DEFAULT_DEPTH);
110 void json_tokener_free(struct json_tokener *tok)
112 json_tokener_reset(tok);
113 if (tok->pb) printbuf_free(tok->pb);
114 if (tok->stack) free(tok->stack);
118 static void json_tokener_reset_level(struct json_tokener *tok, int depth)
120 tok->stack[depth].state = json_tokener_state_eatws;
121 tok->stack[depth].saved_state = json_tokener_state_start;
122 json_object_put(tok->stack[depth].current);
123 tok->stack[depth].current = NULL;
124 free(tok->stack[depth].obj_field_name);
125 tok->stack[depth].obj_field_name = NULL;
128 void json_tokener_reset(struct json_tokener *tok)
134 for(i = tok->depth; i >= 0; i--)
135 json_tokener_reset_level(tok, i);
137 tok->err = json_tokener_success;
140 struct json_object* json_tokener_parse(const char *str)
142 enum json_tokener_error jerr_ignored;
143 struct json_object* obj;
144 obj = json_tokener_parse_verbose(str, &jerr_ignored);
148 struct json_object* json_tokener_parse_verbose(const char *str, enum json_tokener_error *error)
150 struct json_tokener* tok;
151 struct json_object* obj;
153 tok = json_tokener_new();
156 obj = json_tokener_parse_ex(tok, str, -1);
158 if(tok->err != json_tokener_success) {
160 json_object_put(obj);
164 json_tokener_free(tok);
170 /* CAW: compliant version of strndup() */
171 char* strndup(const char* str, size_t n)
174 size_t len = strlen(str);
175 size_t nn = json_min(len,n);
176 char* s = (char*)malloc(sizeof(char) * (nn + 1));
191 #define state tok->stack[tok->depth].state
192 #define saved_state tok->stack[tok->depth].saved_state
193 #define current tok->stack[tok->depth].current
194 #define obj_field_name tok->stack[tok->depth].obj_field_name
197 * json_tokener_parse_ex() consumed a lot of CPU in its main loop,
198 * iterating character-by character. A large performance boost is
199 * achieved by using tighter loops to locally handle units such as
200 * comments and strings. Loops that handle an entire token within
201 * their scope also gather entire strings and pass them to
202 * printbuf_memappend() in a single call, rather than calling
203 * printbuf_memappend() one char at a time.
205 * POP_CHAR() and ADVANCE_CHAR() macros are used for code that is
206 * common to both the main loop and the tighter loops.
209 /* POP_CHAR(dest, tok) macro:
210 * Not really a pop()...peeks at the current char and stores it in dest.
211 * Returns 1 on success, sets tok->err and returns 0 if no more chars.
212 * Implicit inputs: str, len vars
214 #define POP_CHAR(dest, tok) \
215 (((tok)->char_offset == len) ? \
216 (((tok)->depth == 0 && state == json_tokener_state_eatws && saved_state == json_tokener_state_finish) ? \
217 (((tok)->err = json_tokener_success), 0) \
219 (((tok)->err = json_tokener_continue), 0) \
221 (((dest) = *str), 1) \
224 /* ADVANCE_CHAR() macro:
225 * Incrementes str & tok->char_offset.
226 * For convenience of existing conditionals, returns the old value of c (0 on eof)
227 * Implicit inputs: c var
229 #define ADVANCE_CHAR(str, tok) \
230 ( ++(str), ((tok)->char_offset)++, c)
233 /* End optimization macro defs */
236 struct json_object* json_tokener_parse_ex(struct json_tokener *tok,
237 const char *str, int len)
239 struct json_object *obj = NULL;
242 tok->char_offset = 0;
243 tok->err = json_tokener_success;
245 while (POP_CHAR(c, tok)) {
250 case json_tokener_state_eatws:
251 /* Advance until we change state */
252 while (isspace((int)c)) {
253 if ((!ADVANCE_CHAR(str, tok)) || (!POP_CHAR(c, tok)))
257 printbuf_reset(tok->pb);
258 printbuf_memappend_fast(tok->pb, &c, 1);
259 state = json_tokener_state_comment_start;
266 case json_tokener_state_start:
269 state = json_tokener_state_eatws;
270 saved_state = json_tokener_state_object_field_start;
271 current = json_object_new_object();
274 state = json_tokener_state_eatws;
275 saved_state = json_tokener_state_array;
276 current = json_object_new_array();
280 state = json_tokener_state_null;
281 printbuf_reset(tok->pb);
286 state = json_tokener_state_string;
287 printbuf_reset(tok->pb);
294 state = json_tokener_state_boolean;
295 printbuf_reset(tok->pb);
298 #if defined(__GNUC__)
313 state = json_tokener_state_number;
314 printbuf_reset(tok->pb);
318 tok->err = json_tokener_error_parse_unexpected;
323 case json_tokener_state_finish:
324 if(tok->depth == 0) goto out;
325 obj = json_object_get(current);
326 json_tokener_reset_level(tok, tok->depth);
330 case json_tokener_state_null:
331 printbuf_memappend_fast(tok->pb, &c, 1);
332 if(strncasecmp(json_null_str, tok->pb->buf,
333 json_min(tok->st_pos+1, strlen(json_null_str))) == 0) {
334 if(tok->st_pos == strlen(json_null_str)) {
336 saved_state = json_tokener_state_finish;
337 state = json_tokener_state_eatws;
341 tok->err = json_tokener_error_parse_null;
347 case json_tokener_state_comment_start:
349 state = json_tokener_state_comment;
350 } else if(c == '/') {
351 state = json_tokener_state_comment_eol;
353 tok->err = json_tokener_error_parse_comment;
356 printbuf_memappend_fast(tok->pb, &c, 1);
359 case json_tokener_state_comment:
361 /* Advance until we change state */
362 const char *case_start = str;
364 if (!ADVANCE_CHAR(str, tok) || !POP_CHAR(c, tok)) {
365 printbuf_memappend_fast(tok->pb, case_start, str-case_start);
369 printbuf_memappend_fast(tok->pb, case_start, 1+str-case_start);
370 state = json_tokener_state_comment_end;
374 case json_tokener_state_comment_eol:
376 /* Advance until we change state */
377 const char *case_start = str;
379 if (!ADVANCE_CHAR(str, tok) || !POP_CHAR(c, tok)) {
380 printbuf_memappend_fast(tok->pb, case_start, str-case_start);
384 printbuf_memappend_fast(tok->pb, case_start, str-case_start);
385 MC_DEBUG("json_tokener_comment: %s\n", tok->pb->buf);
386 state = json_tokener_state_eatws;
390 case json_tokener_state_comment_end:
391 printbuf_memappend_fast(tok->pb, &c, 1);
393 MC_DEBUG("json_tokener_comment: %s\n", tok->pb->buf);
394 state = json_tokener_state_eatws;
396 state = json_tokener_state_comment;
400 case json_tokener_state_string:
402 /* Advance until we change state */
403 const char *case_start = str;
405 if(c == tok->quote_char) {
406 printbuf_memappend_fast(tok->pb, case_start, str-case_start);
407 current = json_object_new_string_len(tok->pb->buf, tok->pb->bpos);
408 saved_state = json_tokener_state_finish;
409 state = json_tokener_state_eatws;
411 } else if(c == '\\') {
412 printbuf_memappend_fast(tok->pb, case_start, str-case_start);
413 saved_state = json_tokener_state_string;
414 state = json_tokener_state_string_escape;
417 if (!ADVANCE_CHAR(str, tok) || !POP_CHAR(c, tok)) {
418 printbuf_memappend_fast(tok->pb, case_start, str-case_start);
425 case json_tokener_state_string_escape:
430 printbuf_memappend_fast(tok->pb, &c, 1);
438 if(c == 'b') printbuf_memappend_fast(tok->pb, "\b", 1);
439 else if(c == 'n') printbuf_memappend_fast(tok->pb, "\n", 1);
440 else if(c == 'r') printbuf_memappend_fast(tok->pb, "\r", 1);
441 else if(c == 't') printbuf_memappend_fast(tok->pb, "\t", 1);
442 else if(c == 'f') printbuf_memappend_fast(tok->pb, "\f", 1);
448 state = json_tokener_state_escape_unicode;
451 tok->err = json_tokener_error_parse_string;
456 case json_tokener_state_escape_unicode:
458 unsigned int got_hi_surrogate = 0;
460 /* Handle a 4-byte sequence, or two sequences if a surrogate pair */
462 if(strchr(json_hex_chars, c)) {
463 tok->ucs_char += ((unsigned int)hexdigit(c) << ((3-tok->st_pos++)*4));
464 if(tok->st_pos == 4) {
465 unsigned char unescaped_utf[4];
467 if (got_hi_surrogate) {
468 if (IS_LOW_SURROGATE(tok->ucs_char)) {
469 /* Recalculate the ucs_char, then fall thru to process normally */
470 tok->ucs_char = DECODE_SURROGATE_PAIR(got_hi_surrogate, tok->ucs_char);
472 /* Hi surrogate was not followed by a low surrogate */
473 /* Replace the hi and process the rest normally */
474 printbuf_memappend_fast(tok->pb, (char*)utf8_replacement_char, 3);
476 got_hi_surrogate = 0;
479 if (tok->ucs_char < 0x80) {
480 unescaped_utf[0] = tok->ucs_char;
481 printbuf_memappend_fast(tok->pb, (char*)unescaped_utf, 1);
482 } else if (tok->ucs_char < 0x800) {
483 unescaped_utf[0] = 0xc0 | (tok->ucs_char >> 6);
484 unescaped_utf[1] = 0x80 | (tok->ucs_char & 0x3f);
485 printbuf_memappend_fast(tok->pb, (char*)unescaped_utf, 2);
486 } else if (IS_HIGH_SURROGATE(tok->ucs_char)) {
487 /* Got a high surrogate. Remember it and look for the
488 * the beginning of another sequence, which should be the
491 got_hi_surrogate = tok->ucs_char;
492 /* Not at end, and the next two chars should be "\u" */
493 if ((tok->char_offset+1 != len) &&
494 (tok->char_offset+2 != len) &&
498 ADVANCE_CHAR(str, tok);
499 ADVANCE_CHAR(str, tok);
501 /* Advance to the first char of the next sequence and
502 * continue processing with the next sequence.
504 if (!ADVANCE_CHAR(str, tok) || !POP_CHAR(c, tok)) {
505 printbuf_memappend_fast(tok->pb, (char*)utf8_replacement_char, 3);
510 continue; /* other json_tokener_state_escape_unicode */
512 /* Got a high surrogate without another sequence following
513 * it. Put a replacement char in for the hi surrogate
514 * and pretend we finished.
516 printbuf_memappend_fast(tok->pb, (char*)utf8_replacement_char, 3);
518 } else if (IS_LOW_SURROGATE(tok->ucs_char)) {
519 /* Got a low surrogate not preceded by a high */
520 printbuf_memappend_fast(tok->pb, (char*)utf8_replacement_char, 3);
521 } else if (tok->ucs_char < 0x10000) {
522 unescaped_utf[0] = 0xe0 | (tok->ucs_char >> 12);
523 unescaped_utf[1] = 0x80 | ((tok->ucs_char >> 6) & 0x3f);
524 unescaped_utf[2] = 0x80 | (tok->ucs_char & 0x3f);
525 printbuf_memappend_fast(tok->pb, (char*)unescaped_utf, 3);
526 } else if (tok->ucs_char < 0x110000) {
527 unescaped_utf[0] = 0xf0 | ((tok->ucs_char >> 18) & 0x07);
528 unescaped_utf[1] = 0x80 | ((tok->ucs_char >> 12) & 0x3f);
529 unescaped_utf[2] = 0x80 | ((tok->ucs_char >> 6) & 0x3f);
530 unescaped_utf[3] = 0x80 | (tok->ucs_char & 0x3f);
531 printbuf_memappend_fast(tok->pb, (char*)unescaped_utf, 4);
533 /* Don't know what we got--insert the replacement char */
534 printbuf_memappend_fast(tok->pb, (char*)utf8_replacement_char, 3);
540 tok->err = json_tokener_error_parse_string;
543 if (!ADVANCE_CHAR(str, tok) || !POP_CHAR(c, tok)) {
544 if (got_hi_surrogate) /* Clean up any pending chars */
545 printbuf_memappend_fast(tok->pb, (char*)utf8_replacement_char, 3);
552 case json_tokener_state_boolean:
553 printbuf_memappend_fast(tok->pb, &c, 1);
554 if(strncasecmp(json_true_str, tok->pb->buf,
555 json_min(tok->st_pos+1, strlen(json_true_str))) == 0) {
556 if(tok->st_pos == strlen(json_true_str)) {
557 current = json_object_new_boolean(1);
558 saved_state = json_tokener_state_finish;
559 state = json_tokener_state_eatws;
562 } else if(strncasecmp(json_false_str, tok->pb->buf,
563 json_min(tok->st_pos+1, strlen(json_false_str))) == 0) {
564 if(tok->st_pos == strlen(json_false_str)) {
565 current = json_object_new_boolean(0);
566 saved_state = json_tokener_state_finish;
567 state = json_tokener_state_eatws;
571 tok->err = json_tokener_error_parse_boolean;
577 case json_tokener_state_number:
579 /* Advance until we change state */
580 const char *case_start = str;
582 while(c && strchr(json_number_chars, c)) {
584 if(c == '.' || c == 'e' || c == 'E')
586 if (!ADVANCE_CHAR(str, tok) || !POP_CHAR(c, tok)) {
587 printbuf_memappend_fast(tok->pb, case_start, case_len);
592 printbuf_memappend_fast(tok->pb, case_start, case_len);
597 if (!tok->is_double && json_parse_int64(tok->pb->buf, &num64) == 0) {
598 current = json_object_new_int64(num64);
599 } else if(tok->is_double && sscanf(tok->pb->buf, "%lf", &numd) == 1) {
600 current = json_object_new_double(numd);
602 tok->err = json_tokener_error_parse_number;
605 saved_state = json_tokener_state_finish;
606 state = json_tokener_state_eatws;
611 case json_tokener_state_array:
613 saved_state = json_tokener_state_finish;
614 state = json_tokener_state_eatws;
616 if(tok->depth >= tok->max_depth-1) {
617 tok->err = json_tokener_error_depth;
620 state = json_tokener_state_array_add;
622 json_tokener_reset_level(tok, tok->depth);
627 case json_tokener_state_array_add:
628 json_object_array_add(current, obj);
629 saved_state = json_tokener_state_array_sep;
630 state = json_tokener_state_eatws;
633 case json_tokener_state_array_sep:
635 saved_state = json_tokener_state_finish;
636 state = json_tokener_state_eatws;
637 } else if(c == ',') {
638 saved_state = json_tokener_state_array;
639 state = json_tokener_state_eatws;
641 tok->err = json_tokener_error_parse_array;
646 case json_tokener_state_object_field_start:
648 saved_state = json_tokener_state_finish;
649 state = json_tokener_state_eatws;
650 } else if (c == '"' || c == '\'') {
652 printbuf_reset(tok->pb);
653 state = json_tokener_state_object_field;
655 tok->err = json_tokener_error_parse_object_key_name;
660 case json_tokener_state_object_field:
662 /* Advance until we change state */
663 const char *case_start = str;
665 if(c == tok->quote_char) {
666 printbuf_memappend_fast(tok->pb, case_start, str-case_start);
667 obj_field_name = strdup(tok->pb->buf);
668 saved_state = json_tokener_state_object_field_end;
669 state = json_tokener_state_eatws;
671 } else if(c == '\\') {
672 printbuf_memappend_fast(tok->pb, case_start, str-case_start);
673 saved_state = json_tokener_state_object_field;
674 state = json_tokener_state_string_escape;
677 if (!ADVANCE_CHAR(str, tok) || !POP_CHAR(c, tok)) {
678 printbuf_memappend_fast(tok->pb, case_start, str-case_start);
685 case json_tokener_state_object_field_end:
687 saved_state = json_tokener_state_object_value;
688 state = json_tokener_state_eatws;
690 tok->err = json_tokener_error_parse_object_key_sep;
695 case json_tokener_state_object_value:
696 if(tok->depth >= tok->max_depth-1) {
697 tok->err = json_tokener_error_depth;
700 state = json_tokener_state_object_value_add;
702 json_tokener_reset_level(tok, tok->depth);
705 case json_tokener_state_object_value_add:
706 json_object_object_add(current, obj_field_name, obj);
707 free(obj_field_name);
708 obj_field_name = NULL;
709 saved_state = json_tokener_state_object_sep;
710 state = json_tokener_state_eatws;
713 case json_tokener_state_object_sep:
715 saved_state = json_tokener_state_finish;
716 state = json_tokener_state_eatws;
717 } else if(c == ',') {
718 saved_state = json_tokener_state_object_field_start;
719 state = json_tokener_state_eatws;
721 tok->err = json_tokener_error_parse_object_value_sep;
727 if (!ADVANCE_CHAR(str, tok))
729 } /* while(POP_CHAR) */
732 if (!c) { /* We hit an eof char (0) */
733 if(state != json_tokener_state_finish &&
734 saved_state != json_tokener_state_finish)
735 tok->err = json_tokener_error_parse_eof;
738 if (tok->err == json_tokener_success)
740 json_object *ret = json_object_get(current);
743 /* Partially reset, so we parse additional objects on subsequent calls. */
744 for(ii = tok->depth; ii >= 0; ii--)
745 json_tokener_reset_level(tok, ii);
749 MC_DEBUG("json_tokener_parse_ex: error %s at offset %d\n",
750 json_tokener_errors[tok->err], tok->char_offset);