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