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