json: Limit recursion depth
[gpgme.git] / src / cJSON.c
1 /* cJSON.c - JSON parser in C.
2  * Copyright (c) 2009 Dave Gamble
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  * SPDX-License-Identifier: MIT
23  *
24  * Note that this code has been modified from the original code taken
25  * from cjson-code-58.zip before 2014 (my first local commit was in
26  * 2014 but I may used the code even earlier).  Since 2016 the project
27  * was revived and moved to https://github.com/DaveGamble/cJSON.git.
28  * It is now a lot more complex and has substantial changes so that it
29  * is not possible to merge them directly.  In any case we only need a
30  * simple parser and not a complete library.  I have looked through
31  * the commits and fixed a few things which should apply; I also added
32  * a few references to the upstream code.  Regression test are missing!
33  */
34
35 #ifdef HAVE_CONFIG_H
36 # include <config.h>
37 #endif
38
39 #include <string.h>
40 #include <stdio.h>
41 #include <math.h>
42 #include <stdlib.h>
43 #include <float.h>
44 #include <limits.h>
45 #include <ctype.h>
46 #include <errno.h>
47
48 #include <gpg-error.h>
49
50 #include "cJSON.h"
51
52 /* Only use calloc. */
53 #define CALLOC_ONLY 1
54
55 /* Maximum recursion depth */
56 #define MAX_DEPTH 512
57
58 /* To avoid that a compiler optimizes certain memset calls away, these
59    macros may be used instead. */
60 #define wipememory2(_ptr,_set,_len) do { \
61         volatile char *_vptr=(volatile char *)(_ptr); \
62         size_t _vlen=(_len); \
63         while(_vlen) { *_vptr=(_set); _vptr++; _vlen--; } \
64     } while(0)
65 #define wipememory(_ptr,_len) wipememory2(_ptr,0,_len)
66
67 /* We use malloc function wrappers from gpgrt (aka libgpg-error).  */
68 #if GPGRT_VERSION_NUMBER >= 0x011c00 /* 1.28 */
69 # include <gpgrt.h>
70 # define xtrycalloc(a,b) gpgrt_calloc ((a), (b))
71 # define xtrystrdup(a)   gpgrt_strdup ((a))
72 # define xfree(a)        gpgrt_free ((a))
73 # if CALLOC_ONLY
74 #  define xtrymalloc(a)  gpgrt_calloc (1, (a))
75 # else
76 #  define xtrymalloc(a)  gpgrt_malloc ((a))
77 # endif
78 #else /* Without gpgrt (aka libgpg-error).  */
79 # define xtrycalloc(a,b) calloc ((a), (b))
80 # define xtrystrdup(a)   strdup ((a))
81 # define xfree(a)        free ((a))
82 # if CALLOC_ONLY
83 #  define xtrymalloc(a)  calloc (1, (a))
84 # else
85 #  define xtrymalloc(a)  malloc ((a))
86 # endif
87 #endif
88
89
90 static int
91 cJSON_strcasecmp (const char *s1, const char *s2)
92 {
93   if (!s1)
94     return (s1 == s2) ? 0 : 1;
95   if (!s2)
96     return 1;
97   for (; tolower (*(const unsigned char *)s1)
98          == tolower (*(const unsigned char *) s2); ++s1, ++s2)
99     if (*s1 == 0)
100       return 0;
101   return tolower (*(const unsigned char *) s1) -
102     tolower (*(const unsigned char *) s2);
103 }
104
105 /* Internal constructor. */
106 static cJSON *
107 cJSON_New_Item (void)
108 {
109   return xtrycalloc (1, sizeof (cJSON));
110 }
111
112 /* Delete a cJSON structure.  (Does not clobber ERRNO). */
113 void
114 cJSON_Delete (cJSON * c)
115 {
116   cJSON *next;
117   int save_errno;
118
119   if (!c)
120     return;
121
122   save_errno = errno;
123   while (c)
124     {
125       next = c->next;
126       if (!(c->type & cJSON_IsReference) && c->child)
127         cJSON_Delete (c->child);
128       if (!(c->type & cJSON_IsReference) && c->valuestring)
129         {
130           wipememory (c->valuestring, strlen (c->valuestring));
131           xfree (c->valuestring);
132         }
133       if (c->string)
134         {
135           wipememory (c->string, strlen (c->string));
136           xfree (c->string);
137         }
138       xfree (c);
139       c = next;
140     }
141   errno = save_errno;
142 }
143
144 /* Parse the input text to generate a number, and populate the result
145  * into item. */
146 static const char *
147 parse_number (cJSON * item, const char *num)
148 {
149   double n = 0, sign = 1, scale = 0;
150   int subscale = 0, signsubscale = 1;
151
152   if (*num == '-')
153     sign = -1, num++;           /* Has sign? */
154   if (*num == '0')
155     num++;                      /* is zero */
156   if (*num >= '1' && *num <= '9')
157     do
158       n = (n * 10.0) + (*num++ - '0');
159     while (*num >= '0' && *num <= '9'); /* Number? */
160   if (*num == '.' && num[1] >= '0' && num[1] <= '9')
161     {
162       num++;
163       do
164         n = (n * 10.0) + (*num++ - '0'), scale--;
165       while (*num >= '0' && *num <= '9');
166     }                           /* Fractional part? */
167   if (*num == 'e' || *num == 'E')       /* Exponent? */
168     {
169       num++;
170       if (*num == '+')
171         num++;
172       else if (*num == '-')
173         signsubscale = -1, num++;       /* With sign? */
174       while (*num >= '0' && *num <= '9')
175         subscale = (subscale * 10) + (*num++ - '0');    /* Number? */
176     }
177
178   /* number = +/- number.fraction * 10^+/- exponent */
179   n = sign * n * pow (10.0, (scale + subscale * signsubscale));
180
181   item->valuedouble = n;
182   item->valueint = (int) n;
183   item->type = cJSON_Number;
184   return num;
185 }
186
187 /* Render the number nicely from the given item into a string. */
188 static char *
189 print_number (cJSON * item)
190 {
191   char *str;
192   double d = item->valuedouble;
193   if (fabs (((double) item->valueint) - d) <= DBL_EPSILON && d <= INT_MAX
194       && d >= INT_MIN)
195     {
196       /* 2^64+1 can be represented in 21 chars. */
197       str = xtrymalloc (21);
198       if (str)
199         sprintf (str, "%d", item->valueint);
200     }
201   else
202     {
203       str = xtrymalloc (64);    /* This is a nice tradeoff. */
204       if (str)
205         {
206           if (fabs (floor (d) - d) <= DBL_EPSILON && fabs (d) < 1.0e60)
207             sprintf (str, "%.0f", d);
208           else if (fabs (d) < 1.0e-6 || fabs (d) > 1.0e9)
209             sprintf (str, "%e", d);
210           else
211             sprintf (str, "%f", d);
212         }
213     }
214   return str;
215 }
216
217 static unsigned
218 parse_hex4 (const char *str)
219 {
220   unsigned h = 0;
221   if (*str >= '0' && *str <= '9')
222     h += (*str) - '0';
223   else if (*str >= 'A' && *str <= 'F')
224     h += 10 + (*str) - 'A';
225   else if (*str >= 'a' && *str <= 'f')
226     h += 10 + (*str) - 'a';
227   else
228     return 0;
229   h = h << 4;
230   str++;
231   if (*str >= '0' && *str <= '9')
232     h += (*str) - '0';
233   else if (*str >= 'A' && *str <= 'F')
234     h += 10 + (*str) - 'A';
235   else if (*str >= 'a' && *str <= 'f')
236     h += 10 + (*str) - 'a';
237   else
238     return 0;
239   h = h << 4;
240   str++;
241   if (*str >= '0' && *str <= '9')
242     h += (*str) - '0';
243   else if (*str >= 'A' && *str <= 'F')
244     h += 10 + (*str) - 'A';
245   else if (*str >= 'a' && *str <= 'f')
246     h += 10 + (*str) - 'a';
247   else
248     return 0;
249   h = h << 4;
250   str++;
251   if (*str >= '0' && *str <= '9')
252     h += (*str) - '0';
253   else if (*str >= 'A' && *str <= 'F')
254     h += 10 + (*str) - 'A';
255   else if (*str >= 'a' && *str <= 'f')
256     h += 10 + (*str) - 'a';
257   else
258     return 0;
259   return h;
260 }
261
262 /* Parse the input text into an unescaped cstring, and populate item. */
263 static const unsigned char firstByteMark[7] =
264   { 0x00, 0x00, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC };
265 static const char *
266 parse_string (cJSON * item, const char *str, const char **ep)
267 {
268   const char *ptr = str + 1;
269   char *ptr2;
270   char *out;
271   int len = 0;
272   unsigned uc, uc2;
273
274   /* FIXME: We should consider eary failure like it is done with
275    * commit 8656386c4f4a12f1cf3d6b26158407fd05e65029 in upstream.  */
276   if (*str != '\"')
277     {
278       *ep = str;
279       return 0;
280     }                           /* not a string! */
281
282   while (*ptr != '\"' && *ptr && ++len)
283     if (*ptr++ == '\\' && *ptr)
284       ptr++;                    /* Skip escaped quotes. */
285
286   out = xtrymalloc (len + 2);   /* This is how long we need for the
287                                  * string, roughly.  We add one extra
288                                  * byte in case the last input
289                                  * character is a backslash.  */
290   if (!out)
291     return 0;
292
293   ptr = str + 1;
294   ptr2 = out;
295   while (*ptr != '\"' && *ptr)
296     {
297       if (*ptr != '\\')
298         *ptr2++ = *ptr++;
299       else
300         {
301           ptr++;
302           if (!*ptr)
303             break;
304           switch (*ptr)
305             {
306             case 'b':
307               *ptr2++ = '\b';
308               break;
309             case 'f':
310               *ptr2++ = '\f';
311               break;
312             case 'n':
313               *ptr2++ = '\n';
314               break;
315             case 'r':
316               *ptr2++ = '\r';
317               break;
318             case 't':
319               *ptr2++ = '\t';
320               break;
321             case 'u':           /* transcode utf16 to utf8. */
322               uc = parse_hex4 (ptr + 1);
323               if (!uc)
324                 break;          /* Bad hex; continue right after the 'u'. */
325               ptr += 4;         /* get the unicode char. */
326
327               if ((uc >= 0xDC00 && uc <= 0xDFFF))
328                 break;          /* check for invalid.   */
329
330               if (uc >= 0xD800 && uc <= 0xDBFF) /* UTF16 surrogate pairs. */
331                 {
332                   if (ptr[1] != '\\' || ptr[2] != 'u')
333                     break;      /* missing second-half of surrogate.    */
334                   ptr += 2;
335                   uc2 = parse_hex4 (ptr + 1);
336                   if (!uc2)
337                     break;      /* Bad hex; continue right after the 'u'. */
338                   ptr += 4;
339                   if (uc2 < 0xDC00 || uc2 > 0xDFFF)
340                     break;      /* invalid second-half of surrogate.    */
341                   uc = 0x10000 + (((uc & 0x3FF) << 10) | (uc2 & 0x3FF));
342                 }
343
344               len = 4;
345               if (uc < 0x80)
346                 len = 1;
347               else if (uc < 0x800)
348                 len = 2;
349               else if (uc < 0x10000)
350                 len = 3;
351               ptr2 += len;
352
353               switch (len)
354                 {
355                 case 4:
356                   *--ptr2 = ((uc | 0x80) & 0xBF);
357                   uc >>= 6;
358                   /*FALLTHRU*/
359                 case 3:
360                   *--ptr2 = ((uc | 0x80) & 0xBF);
361                   uc >>= 6;
362                   /*FALLTHRU*/
363                 case 2:
364                   *--ptr2 = ((uc | 0x80) & 0xBF);
365                   uc >>= 6;
366                   /*FALLTHRU*/
367                 case 1:
368                   *--ptr2 = (uc | firstByteMark[len]);
369                 }
370               ptr2 += len;
371               break;
372             default:
373               /* Fixme: Should we fail here: See
374                * https://github.com/DaveGamble/cJSON/issues/10  */
375               *ptr2++ = *ptr;
376               break;
377             }
378           ptr++;
379         }
380     }
381   *ptr2 = 0;
382   if (*ptr == '\"')
383     ptr++;
384   item->valuestring = out;
385   item->type = cJSON_String;
386   return ptr;
387 }
388
389 /* Render the cstring provided to an escaped version that can be printed. */
390 static char *
391 print_string_ptr (const char *str)
392 {
393   const char *ptr;
394   char *ptr2, *out;
395   int len = 0;
396   unsigned char token;
397
398   if (!str)
399     return xtrystrdup ("");
400   ptr = str;
401   while ((token = *ptr) && ++len)
402     {
403       if (strchr ("\"\\\b\f\n\r\t", token))
404         len++;
405       else if (token < 32)
406         len += 5;
407       ptr++;
408     }
409
410   out = xtrymalloc (len + 3);
411   if (!out)
412     return 0;
413
414   ptr2 = out;
415   ptr = str;
416   *ptr2++ = '\"';
417   while (*ptr)
418     {
419       if ((unsigned char) *ptr > 31 && *ptr != '\"' && *ptr != '\\')
420         *ptr2++ = *ptr++;
421       else
422         {
423           *ptr2++ = '\\';
424           switch (token = *ptr++)
425             {
426             case '\\':
427               *ptr2++ = '\\';
428               break;
429             case '\"':
430               *ptr2++ = '\"';
431               break;
432             case '\b':
433               *ptr2++ = 'b';
434               break;
435             case '\f':
436               *ptr2++ = 'f';
437               break;
438             case '\n':
439               *ptr2++ = 'n';
440               break;
441             case '\r':
442               *ptr2++ = 'r';
443               break;
444             case '\t':
445               *ptr2++ = 't';
446               break;
447             default:
448               sprintf (ptr2, "u%04x", token);
449               ptr2 += 5;
450               break;            /* escape and print */
451             }
452         }
453     }
454   *ptr2++ = '\"';
455   *ptr2++ = 0;
456   return out;
457 }
458
459 /* Invote print_string_ptr (which is useful) on an item. */
460 static char *
461 print_string (cJSON * item)
462 {
463   return print_string_ptr (item->valuestring);
464 }
465
466 /* Predeclare these prototypes. */
467 static const char *parse_value (cJSON * item, const char *value,
468                                 const char **ep, size_t depth);
469 static char *print_value (cJSON * item, int depth, int fmt);
470 static const char *parse_array (cJSON * item, const char *value,
471                                 const char **ep, size_t depth);
472 static char *print_array (cJSON * item, int depth, int fmt);
473 static const char *parse_object (cJSON * item, const char *value,
474                                  const char **ep, size_t depth);
475 static char *print_object (cJSON * item, int depth, int fmt);
476
477 /* Utility to jump whitespace and cr/lf */
478 static const char *
479 skip (const char *in)
480 {
481   while (in && *in && (unsigned char) *in <= 32)
482     in++;
483   return in;
484 }
485
486 /* Parse an object - create a new root, and populate. */
487 cJSON *
488 cJSON_ParseWithOpts (const char *value, const char **return_parse_end,
489                      int require_null_terminated, size_t *r_erroff)
490 {
491   const char *end = 0;
492   const char *ep = 0;
493   cJSON *c;
494
495   if (r_erroff)
496     *r_erroff = 0;
497
498   c = cJSON_New_Item ();
499   if (!c)
500     return NULL; /* memory fail */
501
502   end = parse_value (c, skip (value), &ep, 0);
503   if (!end)
504     {
505       cJSON_Delete (c);
506       errno = EINVAL;
507       if (r_erroff)
508         *r_erroff = ep - value;
509       return 0;
510     }                           /* parse failure. ep is set. */
511
512   /* if we require null-terminated JSON without appended garbage, skip
513      and then check for a null terminator */
514   if (require_null_terminated)
515     {
516       end = skip (end);
517       if (*end)
518         {
519           cJSON_Delete (c);
520           ep = end;
521           errno = EINVAL;
522           if (r_erroff)
523             *r_erroff = ep - value;
524           return 0;
525         }
526     }
527   if (return_parse_end)
528     *return_parse_end = end;
529   return c;
530 }
531
532 /* Default options for cJSON_Parse */
533 cJSON *
534 cJSON_Parse (const char *value, size_t *r_erroff)
535 {
536   return cJSON_ParseWithOpts (value, 0, 0, r_erroff);
537 }
538
539 /* Render a cJSON item/entity/structure to text. */
540 char *
541 cJSON_Print (cJSON * item)
542 {
543   return print_value (item, 0, 1);
544 }
545
546 char *
547 cJSON_PrintUnformatted (cJSON * item)
548 {
549   return print_value (item, 0, 0);
550 }
551
552 /* Parser core - when encountering text, process appropriately. */
553 static const char *
554 parse_value (cJSON * item, const char *value, const char **ep,
555              size_t depth)
556 {
557   if (depth > MAX_DEPTH)
558     {
559       *ep = value;
560       return 0;
561     }
562
563   if (!value)
564     return 0;                   /* Fail on null. */
565   if (!strncmp (value, "null", 4))
566     {
567       item->type = cJSON_NULL;
568       return value + 4;
569     }
570   if (!strncmp (value, "false", 5))
571     {
572       item->type = cJSON_False;
573       return value + 5;
574     }
575   if (!strncmp (value, "true", 4))
576     {
577       item->type = cJSON_True;
578       item->valueint = 1;
579       return value + 4;
580     }
581   if (*value == '\"')
582     {
583       return parse_string (item, value, ep);
584     }
585   if (*value == '-' || (*value >= '0' && *value <= '9'))
586     {
587       return parse_number (item, value);
588     }
589   if (*value == '[')
590     {
591       return parse_array (item, value, ep, depth + 1);
592     }
593   if (*value == '{')
594     {
595       return parse_object (item, value, ep, depth + 1);
596     }
597
598   *ep = value;
599   return 0;                     /* failure. */
600 }
601
602 /* Render a value to text. */
603 static char *
604 print_value (cJSON * item, int depth, int fmt)
605 {
606   char *out = 0;
607   if (!item)
608     return 0;
609   switch ((item->type) & 255)
610     {
611     case cJSON_NULL:
612       out = xtrystrdup ("null");
613       break;
614     case cJSON_False:
615       out = xtrystrdup ("false");
616       break;
617     case cJSON_True:
618       out = xtrystrdup ("true");
619       break;
620     case cJSON_Number:
621       out = print_number (item);
622       break;
623     case cJSON_String:
624       out = print_string (item);
625       break;
626     case cJSON_Array:
627       out = print_array (item, depth, fmt);
628       break;
629     case cJSON_Object:
630       out = print_object (item, depth, fmt);
631       break;
632     }
633   return out;
634 }
635
636 /* Build an array from input text. */
637 static const char *
638 parse_array (cJSON * item, const char *value, const char **ep,
639              size_t depth)
640 {
641   cJSON *child;
642
643   if (depth > MAX_DEPTH)
644     {
645       *ep = value;
646       return 0;
647     }
648
649   if (*value != '[')
650     {
651       *ep = value;
652       return 0;
653     }                           /* not an array! */
654
655   item->type = cJSON_Array;
656   value = skip (value + 1);
657   if (*value == ']')
658     return value + 1;           /* empty array. */
659
660   item->child = child = cJSON_New_Item ();
661   if (!item->child)
662     return 0;                   /* memory fail */
663   /* skip any spacing, get the value. */
664   value = skip (parse_value (child, skip (value), ep,
665                              depth + 1));
666   if (!value)
667     return 0;
668
669   while (*value == ',')
670     {
671       cJSON *new_item;
672       if (!(new_item = cJSON_New_Item ()))
673         return 0;               /* memory fail */
674       child->next = new_item;
675       new_item->prev = child;
676       child = new_item;
677       value = skip (parse_value (child, skip (value + 1), ep,
678                                  depth + 1));
679       if (!value)
680         return 0;               /* memory fail */
681     }
682
683   if (*value == ']')
684     return value + 1;           /* end of array */
685   *ep = value;
686   return 0;                     /* malformed. */
687 }
688
689 /* Render an array to text */
690 static char *
691 print_array (cJSON * item, int depth, int fmt)
692 {
693   char **entries;
694   char *out = 0, *ptr, *ret;
695   int len = 5;
696   cJSON *child = item->child;
697   int numentries = 0, i = 0, fail = 0;
698
699   /* How many entries in the array? */
700   while (child)
701     numentries++, child = child->next;
702   /* Explicitly handle numentries==0 */
703   if (!numentries)
704     {
705       out = xtrymalloc (3);
706       if (out)
707         strcpy (out, "[]");
708       return out;
709     }
710   /* Allocate an array to hold the values for each */
711   entries = xtrymalloc (numentries * sizeof (char *));
712   if (!entries)
713     return 0;
714   memset (entries, 0, numentries * sizeof (char *));
715   /* Retrieve all the results: */
716   child = item->child;
717   while (child && !fail)
718     {
719       ret = print_value (child, depth + 1, fmt);
720       entries[i++] = ret;
721       if (ret)
722         len += strlen (ret) + 2 + (fmt ? 1 : 0);
723       else
724         fail = 1;
725       child = child->next;
726     }
727
728   /* If we didn't fail, try to xtrymalloc the output string */
729   if (!fail)
730     out = xtrymalloc (len);
731   /* If that fails, we fail. */
732   if (!out)
733     fail = 1;
734
735   /* Handle failure. */
736   if (fail)
737     {
738       for (i = 0; i < numentries; i++)
739         if (entries[i])
740           xfree (entries[i]);
741       xfree (entries);
742       return 0;
743     }
744
745   /* Compose the output array. */
746   *out = '[';
747   ptr = out + 1;
748   *ptr = 0;
749   for (i = 0; i < numentries; i++)
750     {
751       strcpy (ptr, entries[i]);
752       ptr += strlen (entries[i]);
753       if (i != numentries - 1)
754         {
755           *ptr++ = ',';
756           if (fmt)
757             *ptr++ = ' ';
758           *ptr = 0;
759         }
760       xfree (entries[i]);
761     }
762   xfree (entries);
763   *ptr++ = ']';
764   *ptr++ = 0;
765   return out;
766 }
767
768 /* Build an object from the text. */
769 static const char *
770 parse_object (cJSON * item, const char *value, const char **ep,
771               size_t depth)
772 {
773   cJSON *child;
774   if (depth > MAX_DEPTH)
775     {
776       *ep = value;
777       return 0;
778     }
779
780   if (*value != '{')
781     {
782       *ep = value;
783       return 0;
784     }                           /* not an object! */
785
786   item->type = cJSON_Object;
787   value = skip (value + 1);
788   if (*value == '}')
789     return value + 1;           /* empty array. */
790
791   item->child = child = cJSON_New_Item ();
792   if (!item->child)
793     return 0;
794   value = skip (parse_string (child, skip (value), ep));
795   if (!value)
796     return 0;
797   child->string = child->valuestring;
798   child->valuestring = 0;
799   if (*value != ':')
800     {
801       *ep = value;
802       return 0;
803     }                           /* fail! */
804   /* skip any spacing, get the value. */
805   value = skip (parse_value (child, skip (value + 1), ep,
806                              depth + 1));
807   if (!value)
808     return 0;
809
810   while (*value == ',')
811     {
812       cJSON *new_item;
813       if (!(new_item = cJSON_New_Item ()))
814         return 0;               /* memory fail */
815       child->next = new_item;
816       new_item->prev = child;
817       child = new_item;
818       value = skip (parse_string (child, skip (value + 1), ep));
819       if (!value)
820         return 0;
821       child->string = child->valuestring;
822       child->valuestring = 0;
823       if (*value != ':')
824         {
825           *ep = value;
826           return 0;
827         }                       /* fail! */
828       /* skip any spacing, get the value. */
829       value = skip (parse_value (child, skip (value + 1), ep, depth + 1));
830       if (!value)
831         return 0;
832     }
833
834   if (*value == '}')
835     return value + 1;           /* end of array */
836   *ep = value;
837   return 0;                     /* malformed. */
838 }
839
840 /* Render an object to text. */
841 static char *
842 print_object (cJSON * item, int depth, int fmt)
843 {
844   char **entries = 0, **names = 0;
845   char *out = 0, *ptr, *ret, *str;
846   int len = 7, i = 0, j;
847   cJSON *child = item->child;
848   int numentries = 0, fail = 0;
849   /* Count the number of entries. */
850   while (child)
851     numentries++, child = child->next;
852   /* Explicitly handle empty object case */
853   if (!numentries)
854     {
855       out = xtrymalloc (fmt ? depth + 4 : 3);
856       if (!out)
857         return 0;
858       ptr = out;
859       *ptr++ = '{';
860       if (fmt)
861         {
862           *ptr++ = '\n';
863           for (i = 0; i < depth - 1; i++)
864             *ptr++ = '\t';
865         }
866       *ptr++ = '}';
867       *ptr++ = 0;
868       return out;
869     }
870   /* Allocate space for the names and the objects */
871   entries = xtrymalloc (numentries * sizeof (char *));
872   if (!entries)
873     return 0;
874   names = xtrymalloc (numentries * sizeof (char *));
875   if (!names)
876     {
877       xfree (entries);
878       return 0;
879     }
880   memset (entries, 0, sizeof (char *) * numentries);
881   memset (names, 0, sizeof (char *) * numentries);
882
883   /* Collect all the results into our arrays: */
884   child = item->child;
885   depth++;
886   if (fmt)
887     len += depth;
888   while (child)
889     {
890       names[i] = str = print_string_ptr (child->string);
891       entries[i++] = ret = print_value (child, depth, fmt);
892       if (str && ret)
893         len += strlen (ret) + strlen (str) + 2 + (fmt ? 2 + depth : 0);
894       else
895         fail = 1;
896       child = child->next;
897     }
898
899   /* Try to allocate the output string */
900   if (!fail)
901     out = xtrymalloc (len);
902   if (!out)
903     fail = 1;
904
905   /* Handle failure */
906   if (fail)
907     {
908       for (i = 0; i < numentries; i++)
909         {
910           if (names[i])
911             xfree (names[i]);
912           if (entries[i])
913             xfree (entries[i]);
914         }
915       xfree (names);
916       xfree (entries);
917       return 0;
918     }
919
920   /* Compose the output: */
921   *out = '{';
922   ptr = out + 1;
923   if (fmt)
924     *ptr++ = '\n';
925   *ptr = 0;
926   for (i = 0; i < numentries; i++)
927     {
928       if (fmt)
929         for (j = 0; j < depth; j++)
930           *ptr++ = '\t';
931       strcpy (ptr, names[i]);
932       ptr += strlen (names[i]);
933       *ptr++ = ':';
934       if (fmt)
935         *ptr++ = '\t';
936       strcpy (ptr, entries[i]);
937       ptr += strlen (entries[i]);
938       if (i != numentries - 1)
939         *ptr++ = ',';
940       if (fmt)
941         *ptr++ = '\n';
942       *ptr = 0;
943       xfree (names[i]);
944       xfree (entries[i]);
945     }
946
947   xfree (names);
948   xfree (entries);
949   if (fmt)
950     for (i = 0; i < depth - 1; i++)
951       *ptr++ = '\t';
952   *ptr++ = '}';
953   *ptr++ = 0;
954   return out;
955 }
956
957 /* Get Array size/item / object item. */
958 int
959 cJSON_GetArraySize (cJSON * array)
960 {
961   cJSON *c = array->child;
962   int i = 0;
963   while (c)
964     i++, c = c->next;
965   return i;
966 }
967
968 cJSON *
969 cJSON_GetArrayItem (cJSON * array, int item)
970 {
971   cJSON *c = array->child;
972   while (c && item > 0)
973     item--, c = c->next;
974   return c;
975 }
976
977 cJSON *
978 cJSON_GetObjectItem (cJSON * object, const char *string)
979 {
980   cJSON *c = object->child;
981   while (c && cJSON_strcasecmp (c->string, string))
982     c = c->next;
983   return c;
984 }
985
986 /* Utility for array list handling. */
987 static void
988 suffix_object (cJSON * prev, cJSON * item)
989 {
990   prev->next = item;
991   item->prev = prev;
992 }
993
994 /* Utility for handling references. */
995 static cJSON *
996 create_reference (cJSON * item)
997 {
998   cJSON *ref = cJSON_New_Item ();
999   if (!ref)
1000     return 0;
1001   memcpy (ref, item, sizeof (cJSON));
1002   ref->string = 0;
1003   ref->type |= cJSON_IsReference;
1004   ref->next = ref->prev = 0;
1005   return ref;
1006 }
1007
1008 /* Add item to array/object. */
1009 void
1010 cJSON_AddItemToArray (cJSON * array, cJSON * item)
1011 {
1012   cJSON *c;
1013
1014   if (!item || !array)
1015     return;
1016   c = array->child;
1017   if (!c)
1018     {
1019       array->child = item;
1020     }
1021   else
1022     {
1023       while (c && c->next)
1024         c = c->next;
1025       suffix_object (c, item);
1026     }
1027 }
1028
1029 cJSON *
1030 cJSON_AddItemToObject (cJSON * object, const char *string, cJSON * item)
1031 {
1032   char *tmp;
1033
1034   if (!item)
1035     return 0;
1036   tmp = xtrystrdup (string);
1037   if (!tmp)
1038     return NULL;
1039
1040   if (item->string)
1041     xfree (item->string);
1042   item->string = tmp;
1043   cJSON_AddItemToArray (object, item);
1044   return object;
1045 }
1046
1047 cJSON *
1048 cJSON_AddNullToObject (cJSON *object, const char *name)
1049 {
1050   cJSON *obj, *tmp;
1051
1052   tmp = cJSON_CreateNull ();
1053   if (!tmp)
1054     return NULL;
1055   obj = cJSON_AddItemToObject(object, name, tmp);
1056   if (!obj)
1057     cJSON_Delete (tmp);
1058   return obj;
1059 }
1060
1061 cJSON *
1062 cJSON_AddTrueToObject (cJSON *object, const char *name)
1063 {
1064   cJSON *obj, *tmp;
1065
1066   tmp = cJSON_CreateTrue ();
1067   if (!tmp)
1068     return NULL;
1069   obj = cJSON_AddItemToObject(object, name, tmp);
1070   if (!obj)
1071     cJSON_Delete (tmp);
1072   return obj;
1073 }
1074
1075 cJSON *
1076 cJSON_AddFalseToObject (cJSON *object, const char *name)
1077 {
1078   cJSON *obj, *tmp;
1079
1080   tmp = cJSON_CreateFalse ();
1081   if (!tmp)
1082     return NULL;
1083   obj = cJSON_AddItemToObject(object, name, tmp);
1084   if (!obj)
1085     cJSON_Delete (tmp);
1086   return obj;
1087 }
1088
1089 cJSON *
1090 cJSON_AddBoolToObject (cJSON *object, const char *name, int b)
1091 {
1092   cJSON *obj, *tmp;
1093
1094   tmp = cJSON_CreateBool (b);
1095   if (!tmp)
1096     return NULL;
1097   obj = cJSON_AddItemToObject(object, name, tmp);
1098   if (!obj)
1099     cJSON_Delete (tmp);
1100   return obj;
1101 }
1102
1103 cJSON *
1104 cJSON_AddNumberToObject (cJSON *object, const char *name, double num)
1105 {
1106   cJSON *obj, *tmp;
1107
1108   tmp = cJSON_CreateNumber (num);
1109   if (!tmp)
1110     return NULL;
1111   obj = cJSON_AddItemToObject(object, name, tmp);
1112   if (!obj)
1113     cJSON_Delete (tmp);
1114   return obj;
1115 }
1116
1117 cJSON *
1118 cJSON_AddStringToObject (cJSON *object, const char *name, const char *string)
1119 {
1120   cJSON *obj, *tmp;
1121
1122   tmp = cJSON_CreateString (string);
1123   if (!tmp)
1124     return NULL;
1125   obj = cJSON_AddItemToObject(object, name, tmp);
1126   if (!obj)
1127     cJSON_Delete (tmp);
1128   return obj;
1129 }
1130
1131 void
1132 cJSON_AddItemReferenceToArray (cJSON * array, cJSON * item)
1133 {
1134   cJSON_AddItemToArray (array, create_reference (item));
1135 }
1136
1137 void
1138 cJSON_AddItemReferenceToObject (cJSON * object, const char *string,
1139                                 cJSON * item)
1140 {
1141   cJSON_AddItemToObject (object, string, create_reference (item));
1142 }
1143
1144 cJSON *
1145 cJSON_DetachItemFromArray (cJSON * array, int which)
1146 {
1147   cJSON *c = array->child;
1148   while (c && which > 0)
1149     c = c->next, which--;
1150   if (!c)
1151     return 0;
1152   if (c->prev)
1153     c->prev->next = c->next;
1154   if (c->next)
1155     c->next->prev = c->prev;
1156   if (c == array->child)
1157     array->child = c->next;
1158   c->prev = c->next = 0;
1159   return c;
1160 }
1161
1162 void
1163 cJSON_DeleteItemFromArray (cJSON * array, int which)
1164 {
1165   cJSON_Delete (cJSON_DetachItemFromArray (array, which));
1166 }
1167
1168 cJSON *
1169 cJSON_DetachItemFromObject (cJSON * object, const char *string)
1170 {
1171   int i = 0;
1172   cJSON *c = object->child;
1173   while (c && cJSON_strcasecmp (c->string, string))
1174     i++, c = c->next;
1175   if (c)
1176     return cJSON_DetachItemFromArray (object, i);
1177   return 0;
1178 }
1179
1180 void
1181 cJSON_DeleteItemFromObject (cJSON * object, const char *string)
1182 {
1183   cJSON_Delete (cJSON_DetachItemFromObject (object, string));
1184 }
1185
1186 /* Replace array/object items with new ones. */
1187 void
1188 cJSON_ReplaceItemInArray (cJSON * array, int which, cJSON * newitem)
1189 {
1190   cJSON *c = array->child;
1191   while (c && which > 0)
1192     c = c->next, which--;
1193   if (!c)
1194     return;
1195   newitem->next = c->next;
1196   newitem->prev = c->prev;
1197   if (newitem->next)
1198     newitem->next->prev = newitem;
1199   if (c == array->child)
1200     array->child = newitem;
1201   else
1202     newitem->prev->next = newitem;
1203   c->next = c->prev = 0;
1204   cJSON_Delete (c);
1205 }
1206
1207 void
1208 cJSON_ReplaceItemInObject (cJSON * object, const char *string,
1209                            cJSON * newitem)
1210 {
1211   int i = 0;
1212   cJSON *c = object->child;
1213   while (c && cJSON_strcasecmp (c->string, string))
1214     i++, c = c->next;
1215   if (c)
1216     {
1217       /* FIXME: I guess we should free newitem->string here.  See
1218        * upstream commit 0d10e279c8b604f71829b5d49d092719f4ae96b6.  */
1219       newitem->string = xtrystrdup (string);
1220       cJSON_ReplaceItemInArray (object, i, newitem);
1221     }
1222 }
1223
1224 /* Create basic types: */
1225 cJSON *
1226 cJSON_CreateNull (void)
1227 {
1228   cJSON *item = cJSON_New_Item ();
1229   if (item)
1230     item->type = cJSON_NULL;
1231   return item;
1232 }
1233
1234 cJSON *
1235 cJSON_CreateTrue (void)
1236 {
1237   cJSON *item = cJSON_New_Item ();
1238   if (item)
1239     item->type = cJSON_True;
1240   return item;
1241 }
1242
1243 cJSON *
1244 cJSON_CreateFalse (void)
1245 {
1246   cJSON *item = cJSON_New_Item ();
1247   if (item)
1248     item->type = cJSON_False;
1249   return item;
1250 }
1251
1252 cJSON *
1253 cJSON_CreateBool (int b)
1254 {
1255   cJSON *item = cJSON_New_Item ();
1256   if (item)
1257     item->type = b ? cJSON_True : cJSON_False;
1258   return item;
1259 }
1260
1261 cJSON *
1262 cJSON_CreateNumber (double num)
1263 {
1264   cJSON *item = cJSON_New_Item ();
1265   if (item)
1266     {
1267       item->type = cJSON_Number;
1268       item->valuedouble = num;
1269       item->valueint = (int) num;
1270     }
1271   return item;
1272 }
1273
1274 cJSON *
1275 cJSON_CreateString (const char *string)
1276 {
1277   cJSON *item = cJSON_New_Item ();
1278   if (item)
1279     {
1280       item->type = cJSON_String;
1281       item->valuestring = xtrystrdup (string);
1282     }
1283   return item;
1284 }
1285
1286 cJSON *
1287 cJSON_CreateStringConvey (char *string)
1288 {
1289   cJSON *item = cJSON_New_Item ();
1290   if (item)
1291     {
1292       item->type = cJSON_String;
1293       item->valuestring = string;
1294     }
1295   return item;
1296 }
1297
1298 cJSON *
1299 cJSON_CreateArray (void)
1300 {
1301   cJSON *item = cJSON_New_Item ();
1302   if (item)
1303     item->type = cJSON_Array;
1304   return item;
1305 }
1306
1307 cJSON *
1308 cJSON_CreateObject (void)
1309 {
1310   cJSON *item = cJSON_New_Item ();
1311   if (item)
1312     item->type = cJSON_Object;
1313   return item;
1314 }
1315
1316 /* Create Arrays: */
1317 cJSON *
1318 cJSON_CreateIntArray (const int *numbers, int count)
1319 {
1320   int i;
1321   cJSON *n = 0, *p = 0, *a = cJSON_CreateArray ();
1322   for (i = 0; a && i < count; i++)
1323     {
1324       n = cJSON_CreateNumber (numbers[i]);
1325       if (!i)
1326         a->child = n;
1327       else
1328         suffix_object (p, n);
1329       p = n;
1330     }
1331   return a;
1332 }
1333
1334 cJSON *
1335 cJSON_CreateFloatArray (const float *numbers, int count)
1336 {
1337   int i;
1338   cJSON *n = 0, *p = 0, *a = cJSON_CreateArray ();
1339   for (i = 0; a && i < count; i++)
1340     {
1341       n = cJSON_CreateNumber (numbers[i]);
1342       if (!i)
1343         a->child = n;
1344       else
1345         suffix_object (p, n);
1346       p = n;
1347     }
1348   return a;
1349 }
1350
1351 cJSON *
1352 cJSON_CreateDoubleArray (const double *numbers, int count)
1353 {
1354   int i;
1355   cJSON *n = 0, *p = 0, *a = cJSON_CreateArray ();
1356   for (i = 0; a && i < count; i++)
1357     {
1358       n = cJSON_CreateNumber (numbers[i]);
1359       if (!i)
1360         a->child = n;
1361       else
1362         suffix_object (p, n);
1363       p = n;
1364     }
1365   return a;
1366 }
1367
1368 cJSON *
1369 cJSON_CreateStringArray (const char **strings, int count)
1370 {
1371   int i;
1372   cJSON *n = 0, *p = 0, *a = cJSON_CreateArray ();
1373   for (i = 0; a && i < count; i++)
1374     {
1375       n = cJSON_CreateString (strings[i]);
1376       if (!i)
1377         a->child = n;
1378       else
1379         suffix_object (p, n);
1380       p = n;
1381     }
1382   return a;
1383 }
1384
1385 /* Duplication */
1386 cJSON *
1387 cJSON_Duplicate (cJSON * item, int recurse)
1388 {
1389   cJSON *newitem, *cptr, *nptr = 0, *newchild;
1390   /* Bail on bad ptr */
1391   if (!item)
1392     return 0;
1393   /* Create new item */
1394   newitem = cJSON_New_Item ();
1395   if (!newitem)
1396     return 0;
1397   /* Copy over all vars */
1398   newitem->type = item->type & (~cJSON_IsReference), newitem->valueint =
1399     item->valueint, newitem->valuedouble = item->valuedouble;
1400   if (item->valuestring)
1401     {
1402       newitem->valuestring = xtrystrdup (item->valuestring);
1403       if (!newitem->valuestring)
1404         {
1405           cJSON_Delete (newitem);
1406           return 0;
1407         }
1408     }
1409   if (item->string)
1410     {
1411       newitem->string = xtrystrdup (item->string);
1412       if (!newitem->string)
1413         {
1414           cJSON_Delete (newitem);
1415           return 0;
1416         }
1417     }
1418   /* If non-recursive, then we're done! */
1419   if (!recurse)
1420     return newitem;
1421   /* Walk the ->next chain for the child. */
1422   cptr = item->child;
1423   while (cptr)
1424     {
1425       /* Duplicate (with recurse) each item in the ->next chain */
1426       newchild = cJSON_Duplicate (cptr, 1);
1427       if (!newchild)
1428         {
1429           cJSON_Delete (newitem);
1430           return 0;
1431         }
1432       if (nptr)
1433         {
1434           /* If newitem->child already set,
1435            * then crosswire ->prev and ->next and move on.  */
1436           nptr->next = newchild, newchild->prev = nptr;
1437           nptr = newchild;
1438         }
1439       else
1440         {
1441           /* Set newitem->child and move to it.  */
1442           newitem->child = newchild;
1443           nptr = newchild;
1444         }
1445       cptr = cptr->next;
1446     }
1447   return newitem;
1448 }
1449
1450 void
1451 cJSON_Minify (char *json)
1452 {
1453   char *into = json;
1454   while (*json)
1455     {
1456       if (*json == ' ')
1457         json++;
1458       else if (*json == '\t')
1459         json++;                 /* Whitespace characters.  */
1460       else if (*json == '\r')
1461         json++;
1462       else if (*json == '\n')
1463         json++;
1464       else if (*json == '/' && json[1] == '/')
1465         while (*json && *json != '\n')
1466           json++;               /* Double-slash comments, to end of line.  */
1467       else if (*json == '/' && json[1] == '*')
1468         {
1469           while (*json && !(*json == '*' && json[1] == '/'))
1470             json++;
1471           json += 2;
1472         }                       /* Multiline comments.  */
1473       else if (*json == '\"')
1474         {
1475           *into++ = *json++;
1476           while (*json && *json != '\"')
1477             {
1478               if (*json == '\\')
1479                 *into++ = *json++;
1480               if (*json)
1481                 *into++ = *json++;
1482             }
1483           if (*json)
1484             *into++ = *json++;
1485         }                       /* String literals, which are \" sensitive.  */
1486       else
1487         *into++ = *json++;      /* All other characters.  */
1488     }
1489   *into = 0;                    /* and null-terminate.  */
1490 }