Refactor decoder input stream
[jansson.git] / src / load.c
1 /*
2  * Copyright (c) 2009-2011 Petri Lehtinen <petri@digip.org>
3  *
4  * Jansson is free software; you can redistribute it and/or modify
5  * it under the terms of the MIT license. See LICENSE for details.
6  */
7
8 #define _GNU_SOURCE
9 #include <ctype.h>
10 #include <errno.h>
11 #include <limits.h>
12 #include <stdio.h>
13 #include <stdlib.h>
14 #include <string.h>
15 #include <stdarg.h>
16 #include <assert.h>
17
18 #include <jansson.h>
19 #include "jansson_private.h"
20 #include "strbuffer.h"
21 #include "utf.h"
22
23 #define STREAM_STATE_OK        0
24 #define STREAM_STATE_EOF      -1
25 #define STREAM_STATE_ERROR    -2
26
27 #define TOKEN_INVALID         -1
28 #define TOKEN_EOF              0
29 #define TOKEN_STRING         256
30 #define TOKEN_INTEGER        257
31 #define TOKEN_REAL           258
32 #define TOKEN_TRUE           259
33 #define TOKEN_FALSE          260
34 #define TOKEN_NULL           261
35
36 /* Read one byte from stream, convert to unsigned char, then int, and
37    return. return EOF on end of file. This corresponds to the
38    behaviour of fgetc(). */
39 typedef int (*get_func)(void *data);
40
41 typedef struct {
42     get_func get;
43     void *data;
44     char buffer[5];
45     int buffer_pos;
46     int state;
47     int line;
48     int column, last_column;
49     size_t position;
50 } stream_t;
51
52 typedef struct {
53     stream_t stream;
54     strbuffer_t saved_text;
55     int token;
56     union {
57         char *string;
58         json_int_t integer;
59         double real;
60     } value;
61 } lex_t;
62
63 #define stream_to_lex(stream) container_of(stream, lex_t, stream)
64
65
66 /*** error reporting ***/
67
68 static void error_set(json_error_t *error, const lex_t *lex,
69                       const char *msg, ...)
70 {
71     va_list ap;
72     char msg_text[JSON_ERROR_TEXT_LENGTH];
73
74     int line = -1, col = -1;
75     size_t pos = 0;
76     const char *result = msg_text;
77
78     if(!error)
79         return;
80
81     va_start(ap, msg);
82     vsnprintf(msg_text, JSON_ERROR_TEXT_LENGTH, msg, ap);
83     va_end(ap);
84
85     if(lex)
86     {
87         const char *saved_text = strbuffer_value(&lex->saved_text);
88         char msg_with_context[JSON_ERROR_TEXT_LENGTH];
89
90         line = lex->stream.line;
91         col = lex->stream.column;
92         pos = lex->stream.position;
93
94         if(saved_text && saved_text[0])
95         {
96             if(lex->saved_text.length <= 20) {
97                 snprintf(msg_with_context, JSON_ERROR_TEXT_LENGTH,
98                          "%s near '%s'", msg_text, saved_text);
99                 result = msg_with_context;
100             }
101         }
102         else
103         {
104             if(lex->stream.state == STREAM_STATE_ERROR) {
105                 /* No context for UTF-8 decoding errors */
106                 result = msg_text;
107             }
108             else {
109                 snprintf(msg_with_context, JSON_ERROR_TEXT_LENGTH,
110                          "%s near end of file", msg_text);
111                 result = msg_with_context;
112             }
113         }
114     }
115
116     jsonp_error_set(error, line, col, pos, "%s", result);
117 }
118
119
120 /*** lexical analyzer ***/
121
122 static void
123 stream_init(stream_t *stream, get_func get, void *data)
124 {
125     stream->get = get;
126     stream->data = data;
127     stream->buffer[0] = '\0';
128     stream->buffer_pos = 0;
129
130     stream->state = STREAM_STATE_OK;
131     stream->line = 1;
132     stream->column = 0;
133     stream->position = 0;
134 }
135
136 static int stream_get(stream_t *stream, json_error_t *error)
137 {
138     int c;
139
140     if(stream->state != STREAM_STATE_OK)
141         return stream->state;
142
143     if(!stream->buffer[stream->buffer_pos])
144     {
145         c = stream->get(stream->data);
146         if(c == EOF) {
147             stream->state = STREAM_STATE_EOF;
148             return STREAM_STATE_EOF;
149         }
150
151         stream->buffer[0] = c;
152         stream->buffer_pos = 0;
153
154         if(0x80 <= c && c <= 0xFF)
155         {
156             /* multi-byte UTF-8 sequence */
157             int i, count;
158
159             count = utf8_check_first(c);
160             if(!count)
161                 goto out;
162
163             assert(count >= 2);
164
165             for(i = 1; i < count; i++)
166                 stream->buffer[i] = stream->get(stream->data);
167
168             if(!utf8_check_full(stream->buffer, count, NULL))
169                 goto out;
170
171             stream->buffer[count] = '\0';
172         }
173         else
174             stream->buffer[1] = '\0';
175     }
176
177     c = stream->buffer[stream->buffer_pos++];
178
179     stream->position++;
180     if(c == '\n') {
181         stream->line++;
182         stream->last_column = stream->column;
183         stream->column = 0;
184     }
185     else if(utf8_check_first(c)) {
186         /* track the Unicode character column, so increment only if
187            this is the first character of a UTF-8 sequence */
188         stream->column++;
189     }
190
191     return c;
192
193 out:
194     stream->state = STREAM_STATE_ERROR;
195     error_set(error, stream_to_lex(stream), "unable to decode byte 0x%x", c);
196     return STREAM_STATE_ERROR;
197 }
198
199 static void stream_unget(stream_t *stream, int c)
200 {
201     if(c == STREAM_STATE_EOF || c == STREAM_STATE_ERROR)
202         return;
203
204     stream->position--;
205     if(c == '\n') {
206         stream->line--;
207         stream->column = stream->last_column;
208     }
209     else if(utf8_check_first(c))
210         stream->column--;
211
212     assert(stream->buffer_pos > 0);
213     stream->buffer_pos--;
214     assert(stream->buffer[stream->buffer_pos] == c);
215 }
216
217
218 static int lex_get(lex_t *lex, json_error_t *error)
219 {
220     return stream_get(&lex->stream, error);
221 }
222
223 static void lex_save(lex_t *lex, int c)
224 {
225     strbuffer_append_byte(&lex->saved_text, c);
226 }
227
228 static int lex_get_save(lex_t *lex, json_error_t *error)
229 {
230     int c = stream_get(&lex->stream, error);
231     if(c != STREAM_STATE_EOF && c != STREAM_STATE_ERROR)
232         lex_save(lex, c);
233     return c;
234 }
235
236 static void lex_unget(lex_t *lex, int c)
237 {
238     stream_unget(&lex->stream, c);
239 }
240
241 static void lex_unget_unsave(lex_t *lex, int c)
242 {
243     if(c != STREAM_STATE_EOF && c != STREAM_STATE_ERROR) {
244         char d;
245         stream_unget(&lex->stream, c);
246         d = strbuffer_pop(&lex->saved_text);
247         assert(c == d);
248     }
249 }
250
251 static void lex_save_cached(lex_t *lex)
252 {
253     while(lex->stream.buffer[lex->stream.buffer_pos] != '\0')
254     {
255         lex_save(lex, lex->stream.buffer[lex->stream.buffer_pos]);
256         lex->stream.buffer_pos++;
257         lex->stream.position++;
258     }
259 }
260
261 /* assumes that str points to 'u' plus at least 4 valid hex digits */
262 static int32_t decode_unicode_escape(const char *str)
263 {
264     int i;
265     int32_t value = 0;
266
267     assert(str[0] == 'u');
268
269     for(i = 1; i <= 4; i++) {
270         char c = str[i];
271         value <<= 4;
272         if(isdigit(c))
273             value += c - '0';
274         else if(islower(c))
275             value += c - 'a' + 10;
276         else if(isupper(c))
277             value += c - 'A' + 10;
278         else
279             assert(0);
280     }
281
282     return value;
283 }
284
285 static void lex_scan_string(lex_t *lex, json_error_t *error)
286 {
287     int c;
288     const char *p;
289     char *t;
290     int i;
291
292     lex->value.string = NULL;
293     lex->token = TOKEN_INVALID;
294
295     c = lex_get_save(lex, error);
296
297     while(c != '"') {
298         if(c == STREAM_STATE_ERROR)
299             goto out;
300
301         else if(c == STREAM_STATE_EOF) {
302             error_set(error, lex, "premature end of input");
303             goto out;
304         }
305
306         else if(0 <= c && c <= 0x1F) {
307             /* control character */
308             lex_unget_unsave(lex, c);
309             if(c == '\n')
310                 error_set(error, lex, "unexpected newline", c);
311             else
312                 error_set(error, lex, "control character 0x%x", c);
313             goto out;
314         }
315
316         else if(c == '\\') {
317             c = lex_get_save(lex, error);
318             if(c == 'u') {
319                 c = lex_get_save(lex, error);
320                 for(i = 0; i < 4; i++) {
321                     if(!isxdigit(c)) {
322                         error_set(error, lex, "invalid escape");
323                         goto out;
324                     }
325                     c = lex_get_save(lex, error);
326                 }
327             }
328             else if(c == '"' || c == '\\' || c == '/' || c == 'b' ||
329                     c == 'f' || c == 'n' || c == 'r' || c == 't')
330                 c = lex_get_save(lex, error);
331             else {
332                 error_set(error, lex, "invalid escape");
333                 goto out;
334             }
335         }
336         else
337             c = lex_get_save(lex, error);
338     }
339
340     /* the actual value is at most of the same length as the source
341        string, because:
342          - shortcut escapes (e.g. "\t") (length 2) are converted to 1 byte
343          - a single \uXXXX escape (length 6) is converted to at most 3 bytes
344          - two \uXXXX escapes (length 12) forming an UTF-16 surrogate pair
345            are converted to 4 bytes
346     */
347     lex->value.string = jsonp_malloc(lex->saved_text.length + 1);
348     if(!lex->value.string) {
349         /* this is not very nice, since TOKEN_INVALID is returned */
350         goto out;
351     }
352
353     /* the target */
354     t = lex->value.string;
355
356     /* + 1 to skip the " */
357     p = strbuffer_value(&lex->saved_text) + 1;
358
359     while(*p != '"') {
360         if(*p == '\\') {
361             p++;
362             if(*p == 'u') {
363                 char buffer[4];
364                 int length;
365                 int32_t value;
366
367                 value = decode_unicode_escape(p);
368                 p += 5;
369
370                 if(0xD800 <= value && value <= 0xDBFF) {
371                     /* surrogate pair */
372                     if(*p == '\\' && *(p + 1) == 'u') {
373                         int32_t value2 = decode_unicode_escape(++p);
374                         p += 5;
375
376                         if(0xDC00 <= value2 && value2 <= 0xDFFF) {
377                             /* valid second surrogate */
378                             value =
379                                 ((value - 0xD800) << 10) +
380                                 (value2 - 0xDC00) +
381                                 0x10000;
382                         }
383                         else {
384                             /* invalid second surrogate */
385                             error_set(error, lex,
386                                       "invalid Unicode '\\u%04X\\u%04X'",
387                                       value, value2);
388                             goto out;
389                         }
390                     }
391                     else {
392                         /* no second surrogate */
393                         error_set(error, lex, "invalid Unicode '\\u%04X'",
394                                   value);
395                         goto out;
396                     }
397                 }
398                 else if(0xDC00 <= value && value <= 0xDFFF) {
399                     error_set(error, lex, "invalid Unicode '\\u%04X'", value);
400                     goto out;
401                 }
402                 else if(value == 0)
403                 {
404                     error_set(error, lex, "\\u0000 is not allowed");
405                     goto out;
406                 }
407
408                 if(utf8_encode(value, buffer, &length))
409                     assert(0);
410
411                 memcpy(t, buffer, length);
412                 t += length;
413             }
414             else {
415                 switch(*p) {
416                     case '"': case '\\': case '/':
417                         *t = *p; break;
418                     case 'b': *t = '\b'; break;
419                     case 'f': *t = '\f'; break;
420                     case 'n': *t = '\n'; break;
421                     case 'r': *t = '\r'; break;
422                     case 't': *t = '\t'; break;
423                     default: assert(0);
424                 }
425                 t++;
426                 p++;
427             }
428         }
429         else
430             *(t++) = *(p++);
431     }
432     *t = '\0';
433     lex->token = TOKEN_STRING;
434     return;
435
436 out:
437     jsonp_free(lex->value.string);
438 }
439
440 #if JSON_INTEGER_IS_LONG_LONG
441 #define json_strtoint     strtoll
442 #else
443 #define json_strtoint     strtol
444 #endif
445
446 static int lex_scan_number(lex_t *lex, int c, json_error_t *error)
447 {
448     const char *saved_text;
449     char *end;
450     double value;
451
452     lex->token = TOKEN_INVALID;
453
454     if(c == '-')
455         c = lex_get_save(lex, error);
456
457     if(c == '0') {
458         c = lex_get_save(lex, error);
459         if(isdigit(c)) {
460             lex_unget_unsave(lex, c);
461             goto out;
462         }
463     }
464     else if(isdigit(c)) {
465         c = lex_get_save(lex, error);
466         while(isdigit(c))
467             c = lex_get_save(lex, error);
468     }
469     else {
470         lex_unget_unsave(lex, c);
471         goto out;
472     }
473
474     if(c != '.' && c != 'E' && c != 'e') {
475         json_int_t value;
476
477         lex_unget_unsave(lex, c);
478
479         saved_text = strbuffer_value(&lex->saved_text);
480
481         errno = 0;
482         value = json_strtoint(saved_text, &end, 10);
483         if(errno == ERANGE) {
484             if(value < 0)
485                 error_set(error, lex, "too big negative integer");
486             else
487                 error_set(error, lex, "too big integer");
488             goto out;
489         }
490
491         assert(end == saved_text + lex->saved_text.length);
492
493         lex->token = TOKEN_INTEGER;
494         lex->value.integer = value;
495         return 0;
496     }
497
498     if(c == '.') {
499         c = lex_get(lex, error);
500         if(!isdigit(c)) {
501             lex_unget(lex, c);
502             goto out;
503         }
504         lex_save(lex, c);
505
506         c = lex_get_save(lex, error);
507         while(isdigit(c))
508             c = lex_get_save(lex, error);
509     }
510
511     if(c == 'E' || c == 'e') {
512         c = lex_get_save(lex, error);
513         if(c == '+' || c == '-')
514             c = lex_get_save(lex, error);
515
516         if(!isdigit(c)) {
517             lex_unget_unsave(lex, c);
518             goto out;
519         }
520
521         c = lex_get_save(lex, error);
522         while(isdigit(c))
523             c = lex_get_save(lex, error);
524     }
525
526     lex_unget_unsave(lex, c);
527
528     saved_text = strbuffer_value(&lex->saved_text);
529     value = strtod(saved_text, &end);
530     assert(end == saved_text + lex->saved_text.length);
531
532     if(errno == ERANGE && value != 0) {
533         error_set(error, lex, "real number overflow");
534         goto out;
535     }
536
537     lex->token = TOKEN_REAL;
538     lex->value.real = value;
539     return 0;
540
541 out:
542     return -1;
543 }
544
545 static int lex_scan(lex_t *lex, json_error_t *error)
546 {
547     int c;
548
549     strbuffer_clear(&lex->saved_text);
550
551     if(lex->token == TOKEN_STRING) {
552         jsonp_free(lex->value.string);
553         lex->value.string = NULL;
554     }
555
556     c = lex_get(lex, error);
557     while(c == ' ' || c == '\t' || c == '\n' || c == '\r')
558         c = lex_get(lex, error);
559
560     if(c == STREAM_STATE_EOF) {
561         lex->token = TOKEN_EOF;
562         goto out;
563     }
564
565     if(c == STREAM_STATE_ERROR) {
566         lex->token = TOKEN_INVALID;
567         goto out;
568     }
569
570     lex_save(lex, c);
571
572     if(c == '{' || c == '}' || c == '[' || c == ']' || c == ':' || c == ',')
573         lex->token = c;
574
575     else if(c == '"')
576         lex_scan_string(lex, error);
577
578     else if(isdigit(c) || c == '-') {
579         if(lex_scan_number(lex, c, error))
580             goto out;
581     }
582
583     else if(isupper(c) || islower(c)) {
584         /* eat up the whole identifier for clearer error messages */
585         const char *saved_text;
586
587         c = lex_get_save(lex, error);
588         while(isupper(c) || islower(c))
589             c = lex_get_save(lex, error);
590         lex_unget_unsave(lex, c);
591
592         saved_text = strbuffer_value(&lex->saved_text);
593
594         if(strcmp(saved_text, "true") == 0)
595             lex->token = TOKEN_TRUE;
596         else if(strcmp(saved_text, "false") == 0)
597             lex->token = TOKEN_FALSE;
598         else if(strcmp(saved_text, "null") == 0)
599             lex->token = TOKEN_NULL;
600         else
601             lex->token = TOKEN_INVALID;
602     }
603
604     else {
605         /* save the rest of the input UTF-8 sequence to get an error
606            message of valid UTF-8 */
607         lex_save_cached(lex);
608         lex->token = TOKEN_INVALID;
609     }
610
611 out:
612     return lex->token;
613 }
614
615 static char *lex_steal_string(lex_t *lex)
616 {
617     char *result = NULL;
618     if(lex->token == TOKEN_STRING)
619     {
620         result = lex->value.string;
621         lex->value.string = NULL;
622     }
623     return result;
624 }
625
626 static int lex_init(lex_t *lex, get_func get, void *data)
627 {
628     stream_init(&lex->stream, get, data);
629     if(strbuffer_init(&lex->saved_text))
630         return -1;
631
632     lex->token = TOKEN_INVALID;
633     return 0;
634 }
635
636 static void lex_close(lex_t *lex)
637 {
638     if(lex->token == TOKEN_STRING)
639         jsonp_free(lex->value.string);
640     strbuffer_close(&lex->saved_text);
641 }
642
643
644 /*** parser ***/
645
646 static json_t *parse_value(lex_t *lex, json_error_t *error);
647
648 static json_t *parse_object(lex_t *lex, json_error_t *error)
649 {
650     json_t *object = json_object();
651     if(!object)
652         return NULL;
653
654     lex_scan(lex, error);
655     if(lex->token == '}')
656         return object;
657
658     while(1) {
659         char *key;
660         json_t *value;
661
662         if(lex->token != TOKEN_STRING) {
663             error_set(error, lex, "string or '}' expected");
664             goto error;
665         }
666
667         key = lex_steal_string(lex);
668         if(!key)
669             return NULL;
670
671         lex_scan(lex, error);
672         if(lex->token != ':') {
673             jsonp_free(key);
674             error_set(error, lex, "':' expected");
675             goto error;
676         }
677
678         lex_scan(lex, error);
679         value = parse_value(lex, error);
680         if(!value) {
681             jsonp_free(key);
682             goto error;
683         }
684
685         if(json_object_set_nocheck(object, key, value)) {
686             jsonp_free(key);
687             json_decref(value);
688             goto error;
689         }
690
691         json_decref(value);
692         jsonp_free(key);
693
694         lex_scan(lex, error);
695         if(lex->token != ',')
696             break;
697
698         lex_scan(lex, error);
699     }
700
701     if(lex->token != '}') {
702         error_set(error, lex, "'}' expected");
703         goto error;
704     }
705
706     return object;
707
708 error:
709     json_decref(object);
710     return NULL;
711 }
712
713 static json_t *parse_array(lex_t *lex, json_error_t *error)
714 {
715     json_t *array = json_array();
716     if(!array)
717         return NULL;
718
719     lex_scan(lex, error);
720     if(lex->token == ']')
721         return array;
722
723     while(lex->token) {
724         json_t *elem = parse_value(lex, error);
725         if(!elem)
726             goto error;
727
728         if(json_array_append(array, elem)) {
729             json_decref(elem);
730             goto error;
731         }
732         json_decref(elem);
733
734         lex_scan(lex, error);
735         if(lex->token != ',')
736             break;
737
738         lex_scan(lex, error);
739     }
740
741     if(lex->token != ']') {
742         error_set(error, lex, "']' expected");
743         goto error;
744     }
745
746     return array;
747
748 error:
749     json_decref(array);
750     return NULL;
751 }
752
753 static json_t *parse_value(lex_t *lex, json_error_t *error)
754 {
755     json_t *json;
756
757     switch(lex->token) {
758         case TOKEN_STRING: {
759             json = json_string_nocheck(lex->value.string);
760             break;
761         }
762
763         case TOKEN_INTEGER: {
764             json = json_integer(lex->value.integer);
765             break;
766         }
767
768         case TOKEN_REAL: {
769             json = json_real(lex->value.real);
770             break;
771         }
772
773         case TOKEN_TRUE:
774             json = json_true();
775             break;
776
777         case TOKEN_FALSE:
778             json = json_false();
779             break;
780
781         case TOKEN_NULL:
782             json = json_null();
783             break;
784
785         case '{':
786             json = parse_object(lex, error);
787             break;
788
789         case '[':
790             json = parse_array(lex, error);
791             break;
792
793         case TOKEN_INVALID:
794             error_set(error, lex, "invalid token");
795             return NULL;
796
797         default:
798             error_set(error, lex, "unexpected token");
799             return NULL;
800     }
801
802     if(!json)
803         return NULL;
804
805     return json;
806 }
807
808 static json_t *parse_json(lex_t *lex, json_error_t *error)
809 {
810     lex_scan(lex, error);
811     if(lex->token != '[' && lex->token != '{') {
812         error_set(error, lex, "'[' or '{' expected");
813         return NULL;
814     }
815
816     return parse_value(lex, error);
817 }
818
819 typedef struct
820 {
821     const char *data;
822     int pos;
823 } string_data_t;
824
825 static int string_get(void *data)
826 {
827     char c;
828     string_data_t *stream = (string_data_t *)data;
829     c = stream->data[stream->pos];
830     if(c == '\0')
831         return EOF;
832     else
833     {
834         stream->pos++;
835         return (unsigned char)c;
836     }
837 }
838
839 json_t *json_loads(const char *string, size_t flags, json_error_t *error)
840 {
841     lex_t lex;
842     json_t *result;
843     string_data_t stream_data = {string, 0};
844
845     (void)flags; /* unused */
846
847     if(lex_init(&lex, string_get, (void *)&stream_data))
848         return NULL;
849
850     jsonp_error_init(error, "<string>");
851
852     result = parse_json(&lex, error);
853     if(!result)
854         goto out;
855
856     lex_scan(&lex, error);
857     if(lex.token != TOKEN_EOF) {
858         error_set(error, &lex, "end of file expected");
859         json_decref(result);
860         result = NULL;
861     }
862
863 out:
864     lex_close(&lex);
865     return result;
866 }
867
868 json_t *json_loadf(FILE *input, size_t flags, json_error_t *error)
869 {
870     lex_t lex;
871     const char *source;
872     json_t *result;
873     (void)flags; /* unused */
874
875     if(lex_init(&lex, (get_func)fgetc, input))
876         return NULL;
877
878     if(input == stdin)
879         source = "<stdin>";
880     else
881         source = "<stream>";
882
883     jsonp_error_init(error, source);
884
885     result = parse_json(&lex, error);
886     if(!result)
887         goto out;
888
889     lex_scan(&lex, error);
890     if(lex.token != TOKEN_EOF) {
891         error_set(error, &lex, "end of file expected");
892         json_decref(result);
893         result = NULL;
894     }
895
896 out:
897     lex_close(&lex);
898     return result;
899 }
900
901 json_t *json_load_file(const char *path, size_t flags, json_error_t *error)
902 {
903     json_t *result;
904     FILE *fp;
905
906     jsonp_error_init(error, path);
907
908     fp = fopen(path, "r");
909     if(!fp)
910     {
911         error_set(error, NULL, "unable to open %s: %s",
912                   path, strerror(errno));
913         return NULL;
914     }
915
916     result = json_loadf(fp, flags, error);
917
918     fclose(fp);
919     return result;
920 }