source: lib/json.c @ 9e8c945

Last change on this file since 9e8c945 was 696dc9e, checked in by Wilmer van der Gaast <wilmer@…>, at 2012-10-28T23:05:02Z

Add json.[ch], update debian/copyright with license info.

  • Property mode set to 100644
File size: 19.3 KB
Line 
1
2/* vim: set et ts=3 sw=3 ft=c:
3 *
4 * Copyright (C) 2012 James McLaughlin et al.  All rights reserved.
5 * https://github.com/udp/json-parser
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 *   notice, this list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *   notice, this list of conditions and the following disclaimer in the
16 *   documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31#include "json.h"
32
33#ifdef _MSC_VER
34   #ifndef _CRT_SECURE_NO_WARNINGS
35      #define _CRT_SECURE_NO_WARNINGS
36   #endif
37#endif
38
39#ifdef __cplusplus
40   const struct _json_value json_value_none; /* zero-d by ctor */
41#else
42   const struct _json_value json_value_none = { 0 };
43#endif
44
45#include <stdlib.h>
46#include <stdio.h>
47#include <string.h>
48#include <ctype.h>
49
50typedef unsigned short json_uchar;
51
52static unsigned char hex_value (json_char c)
53{
54   if (c >= 'A' && c <= 'F')
55      return (c - 'A') + 10;
56
57   if (c >= 'a' && c <= 'f')
58      return (c - 'a') + 10;
59
60   if (c >= '0' && c <= '9')
61      return c - '0';
62
63   return 0xFF;
64}
65
66typedef struct
67{
68   json_settings settings;
69   int first_pass;
70
71   unsigned long used_memory;
72
73   unsigned int uint_max;
74   unsigned long ulong_max;
75
76} json_state;
77
78static void * json_alloc (json_state * state, unsigned long size, int zero)
79{
80   void * mem;
81
82   if ((state->ulong_max - state->used_memory) < size)
83      return 0;
84
85   if (state->settings.max_memory
86         && (state->used_memory += size) > state->settings.max_memory)
87   {
88      return 0;
89   }
90
91   if (! (mem = zero ? calloc (size, 1) : malloc (size)))
92      return 0;
93
94   return mem;
95}
96
97static int new_value
98   (json_state * state, json_value ** top, json_value ** root, json_value ** alloc, json_type type)
99{
100   json_value * value;
101   int values_size;
102
103   if (!state->first_pass)
104   {
105      value = *top = *alloc;
106      *alloc = (*alloc)->_reserved.next_alloc;
107
108      if (!*root)
109         *root = value;
110
111      switch (value->type)
112      {
113         case json_array:
114
115            if (! (value->u.array.values = (json_value **) json_alloc
116               (state, value->u.array.length * sizeof (json_value *), 0)) )
117            {
118               return 0;
119            }
120
121            break;
122
123         case json_object:
124
125            values_size = sizeof (*value->u.object.values) * value->u.object.length;
126
127            if (! ((*(void **) &value->u.object.values) = json_alloc
128                  (state, values_size + ((unsigned long) value->u.object.values), 0)) )
129            {
130               return 0;
131            }
132
133            value->_reserved.object_mem = (*(char **) &value->u.object.values) + values_size;
134
135            break;
136
137         case json_string:
138
139            if (! (value->u.string.ptr = (json_char *) json_alloc
140               (state, (value->u.string.length + 1) * sizeof (json_char), 0)) )
141            {
142               return 0;
143            }
144
145            break;
146
147         default:
148            break;
149      };
150
151      value->u.array.length = 0;
152
153      return 1;
154   }
155
156   value = (json_value *) json_alloc (state, sizeof (json_value), 1);
157
158   if (!value)
159      return 0;
160
161   if (!*root)
162      *root = value;
163
164   value->type = type;
165   value->parent = *top;
166
167   if (*alloc)
168      (*alloc)->_reserved.next_alloc = value;
169
170   *alloc = *top = value;
171
172   return 1;
173}
174
175#define e_off \
176   ((int) (i - cur_line_begin))
177
178#define whitespace \
179   case '\n': ++ cur_line;  cur_line_begin = i; \
180   case ' ': case '\t': case '\r'
181
182#define string_add(b)  \
183   do { if (!state.first_pass) string [string_length] = b;  ++ string_length; } while (0);
184
185const static int
186   flag_next = 1, flag_reproc = 2, flag_need_comma = 4, flag_seek_value = 8, flag_exponent = 16,
187   flag_got_exponent_sign = 32, flag_escaped = 64, flag_string = 128, flag_need_colon = 256,
188   flag_done = 512;
189
190json_value * json_parse_ex (json_settings * settings, const json_char * json, char * error_buf)
191{
192   json_char error [128];
193   unsigned int cur_line;
194   const json_char * cur_line_begin, * i;
195   json_value * top, * root, * alloc = 0;
196   json_state state;
197   int flags;
198
199   error[0] = '\0';
200
201   memset (&state, 0, sizeof (json_state));
202   memcpy (&state.settings, settings, sizeof (json_settings));
203
204   memset (&state.uint_max, 0xFF, sizeof (state.uint_max));
205   memset (&state.ulong_max, 0xFF, sizeof (state.ulong_max));
206
207   state.uint_max -= 8; /* limit of how much can be added before next check */
208   state.ulong_max -= 8;
209
210   for (state.first_pass = 1; state.first_pass >= 0; -- state.first_pass)
211   {
212      json_uchar uchar;
213      unsigned char uc_b1, uc_b2, uc_b3, uc_b4;
214      json_char * string;
215      unsigned int string_length;
216
217      top = root = 0;
218      flags = flag_seek_value;
219
220      cur_line = 1;
221      cur_line_begin = json;
222
223      for (i = json ;; ++ i)
224      {
225         json_char b = *i;
226
227         if (flags & flag_done)
228         {
229            if (!b)
230               break;
231
232            switch (b)
233            {
234               whitespace:
235                  continue;
236
237               default:
238                  sprintf (error, "%d:%d: Trailing garbage: `%c`", cur_line, e_off, b);
239                  goto e_failed;
240            };
241         }
242
243         if (flags & flag_string)
244         {
245            if (!b)
246            {  sprintf (error, "Unexpected EOF in string (at %d:%d)", cur_line, e_off);
247               goto e_failed;
248            }
249
250            if (string_length > state.uint_max)
251               goto e_overflow;
252
253            if (flags & flag_escaped)
254            {
255               flags &= ~ flag_escaped;
256
257               switch (b)
258               {
259                  case 'b':  string_add ('\b');  break;
260                  case 'f':  string_add ('\f');  break;
261                  case 'n':  string_add ('\n');  break;
262                  case 'r':  string_add ('\r');  break;
263                  case 't':  string_add ('\t');  break;
264                  case 'u':
265
266                    if ((uc_b1 = hex_value (*++ i)) == 0xFF || (uc_b2 = hex_value (*++ i)) == 0xFF
267                          || (uc_b3 = hex_value (*++ i)) == 0xFF || (uc_b4 = hex_value (*++ i)) == 0xFF)
268                    {
269                        sprintf (error, "Invalid character value `%c` (at %d:%d)", b, cur_line, e_off);
270                        goto e_failed;
271                    }
272
273                    uc_b1 = uc_b1 * 16 + uc_b2;
274                    uc_b2 = uc_b3 * 16 + uc_b4;
275
276                    uchar = ((json_char) uc_b1) * 256 + uc_b2;
277
278                    if (sizeof (json_char) >= sizeof (json_uchar) || (uc_b1 == 0 && uc_b2 <= 0x7F))
279                    {
280                       string_add ((json_char) uchar);
281                       break;
282                    }
283
284                    if (uchar <= 0x7FF)
285                    {
286                        if (state.first_pass)
287                           string_length += 2;
288                        else
289                        {  string [string_length ++] = 0xC0 | ((uc_b2 & 0xC0) >> 6) | ((uc_b1 & 0x3) << 3);
290                           string [string_length ++] = 0x80 | (uc_b2 & 0x3F);
291                        }
292
293                        break;
294                    }
295
296                    if (state.first_pass)
297                       string_length += 3;
298                    else
299                    {  string [string_length ++] = 0xE0 | ((uc_b1 & 0xF0) >> 4);
300                       string [string_length ++] = 0x80 | ((uc_b1 & 0xF) << 2) | ((uc_b2 & 0xC0) >> 6);
301                       string [string_length ++] = 0x80 | (uc_b2 & 0x3F);
302                    }
303
304                    break;
305
306                  default:
307                     string_add (b);
308               };
309
310               continue;
311            }
312
313            if (b == '\\')
314            {
315               flags |= flag_escaped;
316               continue;
317            }
318
319            if (b == '"')
320            {
321               if (!state.first_pass)
322                  string [string_length] = 0;
323
324               flags &= ~ flag_string;
325               string = 0;
326
327               switch (top->type)
328               {
329                  case json_string:
330
331                     top->u.string.length = string_length;
332                     flags |= flag_next;
333
334                     break;
335
336                  case json_object:
337
338                     if (state.first_pass)
339                        (*(json_char **) &top->u.object.values) += string_length + 1;
340                     else
341                     { 
342                        top->u.object.values [top->u.object.length].name
343                           = (json_char *) top->_reserved.object_mem;
344
345                        (*(json_char **) &top->_reserved.object_mem) += string_length + 1;
346                     }
347
348                     flags |= flag_seek_value | flag_need_colon;
349                     continue;
350
351                  default:
352                     break;
353               };
354            }
355            else
356            {
357               string_add (b);
358               continue;
359            }
360         }
361
362         if (flags & flag_seek_value)
363         {
364            switch (b)
365            {
366               whitespace:
367                  continue;
368
369               case ']':
370
371                  if (top->type == json_array)
372                     flags = (flags & ~ (flag_need_comma | flag_seek_value)) | flag_next;
373                  else if (!state.settings.settings & json_relaxed_commas)
374                  {  sprintf (error, "%d:%d: Unexpected ]", cur_line, e_off);
375                     goto e_failed;
376                  }
377
378                  break;
379
380               default:
381
382                  if (flags & flag_need_comma)
383                  {
384                     if (b == ',')
385                     {  flags &= ~ flag_need_comma;
386                        continue;
387                     }
388                     else
389                     {  sprintf (error, "%d:%d: Expected , before %c", cur_line, e_off, b);
390                        goto e_failed;
391                     }
392                  }
393
394                  if (flags & flag_need_colon)
395                  {
396                     if (b == ':')
397                     {  flags &= ~ flag_need_colon;
398                        continue;
399                     }
400                     else
401                     {  sprintf (error, "%d:%d: Expected : before %c", cur_line, e_off, b);
402                        goto e_failed;
403                     }
404                  }
405
406                  flags &= ~ flag_seek_value;
407
408                  switch (b)
409                  {
410                     case '{':
411
412                        if (!new_value (&state, &top, &root, &alloc, json_object))
413                           goto e_alloc_failure;
414
415                        continue;
416
417                     case '[':
418
419                        if (!new_value (&state, &top, &root, &alloc, json_array))
420                           goto e_alloc_failure;
421
422                        flags |= flag_seek_value;
423                        continue;
424
425                     case '"':
426
427                        if (!new_value (&state, &top, &root, &alloc, json_string))
428                           goto e_alloc_failure;
429
430                        flags |= flag_string;
431
432                        string = top->u.string.ptr;
433                        string_length = 0;
434
435                        continue;
436
437                     case 't':
438
439                        if (*(++ i) != 'r' || *(++ i) != 'u' || *(++ i) != 'e')
440                           goto e_unknown_value;
441
442                        if (!new_value (&state, &top, &root, &alloc, json_boolean))
443                           goto e_alloc_failure;
444
445                        top->u.boolean = 1;
446
447                        flags |= flag_next;
448                        break;
449
450                     case 'f':
451
452                        if (*(++ i) != 'a' || *(++ i) != 'l' || *(++ i) != 's' || *(++ i) != 'e')
453                           goto e_unknown_value;
454
455                        if (!new_value (&state, &top, &root, &alloc, json_boolean))
456                           goto e_alloc_failure;
457
458                        flags |= flag_next;
459                        break;
460
461                     case 'n':
462
463                        if (*(++ i) != 'u' || *(++ i) != 'l' || *(++ i) != 'l')
464                           goto e_unknown_value;
465
466                        if (!new_value (&state, &top, &root, &alloc, json_null))
467                           goto e_alloc_failure;
468
469                        flags |= flag_next;
470                        break;
471
472                     default:
473
474                        if (isdigit (b) || b == '-')
475                        {
476                           if (!new_value (&state, &top, &root, &alloc, json_integer))
477                              goto e_alloc_failure;
478
479                           flags &= ~ (flag_exponent | flag_got_exponent_sign);
480
481                           if (state.first_pass)
482                              continue;
483
484                           if (top->type == json_double)
485                              top->u.dbl = strtod (i, (json_char **) &i);
486                           else
487                              top->u.integer = strtol (i, (json_char **) &i, 10);
488
489                           flags |= flag_next | flag_reproc;
490                        }
491                        else
492                        {  sprintf (error, "%d:%d: Unexpected %c when seeking value", cur_line, e_off, b);
493                           goto e_failed;
494                        }
495                  };
496            };
497         }
498         else
499         {
500            switch (top->type)
501            {
502            case json_object:
503               
504               switch (b)
505               {
506                  whitespace:
507                     continue;
508
509                  case '"':
510
511                     if (flags & flag_need_comma && (!state.settings.settings & json_relaxed_commas))
512                     {
513                        sprintf (error, "%d:%d: Expected , before \"", cur_line, e_off);
514                        goto e_failed;
515                     }
516
517                     flags |= flag_string;
518
519                     string = (json_char *) top->_reserved.object_mem;
520                     string_length = 0;
521
522                     break;
523                 
524                  case '}':
525
526                     flags = (flags & ~ flag_need_comma) | flag_next;
527                     break;
528
529                  case ',':
530
531                     if (flags & flag_need_comma)
532                     {
533                        flags &= ~ flag_need_comma;
534                        break;
535                     }
536
537                  default:
538
539                     sprintf (error, "%d:%d: Unexpected `%c` in object", cur_line, e_off, b);
540                     goto e_failed;
541               };
542
543               break;
544
545            case json_integer:
546            case json_double:
547
548               if (isdigit (b))
549                  continue;
550
551               if (b == 'e' || b == 'E')
552               {
553                  if (!(flags & flag_exponent))
554                  {
555                     flags |= flag_exponent;
556                     top->type = json_double;
557
558                     continue;
559                  }
560               }
561               else if (b == '+' || b == '-')
562               {
563                  if (flags & flag_exponent && !(flags & flag_got_exponent_sign))
564                  {
565                     flags |= flag_got_exponent_sign;
566                     continue;
567                  }
568               }
569               else if (b == '.' && top->type == json_integer)
570               {
571                  top->type = json_double;
572                  continue;
573               }
574
575               flags |= flag_next | flag_reproc;
576               break;
577
578            default:
579               break;
580            };
581         }
582
583         if (flags & flag_reproc)
584         {
585            flags &= ~ flag_reproc;
586            -- i;
587         }
588
589         if (flags & flag_next)
590         {
591            flags = (flags & ~ flag_next) | flag_need_comma;
592
593            if (!top->parent)
594            {
595               /* root value done */
596
597               flags |= flag_done;
598               continue;
599            }
600
601            if (top->parent->type == json_array)
602               flags |= flag_seek_value;
603               
604            if (!state.first_pass)
605            {
606               json_value * parent = top->parent;
607
608               switch (parent->type)
609               {
610                  case json_object:
611
612                     parent->u.object.values
613                        [parent->u.object.length].value = top;
614
615                     break;
616
617                  case json_array:
618
619                     parent->u.array.values
620                           [parent->u.array.length] = top;
621
622                     break;
623
624                  default:
625                     break;
626               };
627            }
628
629            if ( (++ top->parent->u.array.length) > state.uint_max)
630               goto e_overflow;
631
632            top = top->parent;
633
634            continue;
635         }
636      }
637
638      alloc = root;
639   }
640
641   return root;
642
643e_unknown_value:
644
645   sprintf (error, "%d:%d: Unknown value", cur_line, e_off);
646   goto e_failed;
647
648e_alloc_failure:
649
650   strcpy (error, "Memory allocation failure");
651   goto e_failed;
652
653e_overflow:
654
655   sprintf (error, "%d:%d: Too long (caught overflow)", cur_line, e_off);
656   goto e_failed;
657
658e_failed:
659
660   if (error_buf)
661   {
662      if (*error)
663         strcpy (error_buf, error);
664      else
665         strcpy (error_buf, "Unknown error");
666   }
667
668   if (state.first_pass)
669      alloc = root;
670
671   while (alloc)
672   {
673      top = alloc->_reserved.next_alloc;
674      free (alloc);
675      alloc = top;
676   }
677
678   if (!state.first_pass)
679      json_value_free (root);
680
681   return 0;
682}
683
684json_value * json_parse (const json_char * json)
685{
686   json_settings settings;
687   memset (&settings, 0, sizeof (json_settings));
688
689   return json_parse_ex (&settings, json, 0);
690}
691
692void json_value_free (json_value * value)
693{
694   json_value * cur_value;
695
696   if (!value)
697      return;
698
699   value->parent = 0;
700
701   while (value)
702   {
703      switch (value->type)
704      {
705         case json_array:
706
707            if (!value->u.array.length)
708            {
709               free (value->u.array.values);
710               break;
711            }
712
713            value = value->u.array.values [-- value->u.array.length];
714            continue;
715
716         case json_object:
717
718            if (!value->u.object.length)
719            {
720               free (value->u.object.values);
721               break;
722            }
723
724            value = value->u.object.values [-- value->u.object.length].value;
725            continue;
726
727         case json_string:
728
729            free (value->u.string.ptr);
730            break;
731
732         default:
733            break;
734      };
735
736      cur_value = value;
737      value = value->parent;
738      free (cur_value);
739   }
740}
741
742
Note: See TracBrowser for help on using the repository browser.