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