1/*
2 * JavaScript Object Notation (JSON) parser (RFC7159)
3 * Copyright (c) 2017, Qualcomm Atheros, Inc.
4 *
5 * This software may be distributed under the terms of the BSD license.
6 * See README for more details.
7 */
8
9#include "includes.h"
10
11#include "common.h"
12#include "base64.h"
13#include "json.h"
14
15#define JSON_MAX_DEPTH 10
16#define JSON_MAX_TOKENS 500
17
18
19void json_escape_string(char *txt, size_t maxlen, const char *data, size_t len)
20{
21	char *end = txt + maxlen;
22	size_t i;
23
24	for (i = 0; i < len; i++) {
25		if (txt + 4 >= end)
26			break;
27
28		switch (data[i]) {
29		case '\"':
30			*txt++ = '\\';
31			*txt++ = '\"';
32			break;
33		case '\\':
34			*txt++ = '\\';
35			*txt++ = '\\';
36			break;
37		case '\n':
38			*txt++ = '\\';
39			*txt++ = 'n';
40			break;
41		case '\r':
42			*txt++ = '\\';
43			*txt++ = 'r';
44			break;
45		case '\t':
46			*txt++ = '\\';
47			*txt++ = 't';
48			break;
49		default:
50			if (data[i] >= 32 && data[i] <= 126) {
51				*txt++ = data[i];
52			} else {
53				txt += os_snprintf(txt, end - txt, "\\u%04x",
54						   data[i]);
55			}
56			break;
57		}
58	}
59
60	*txt = '\0';
61}
62
63
64static char * json_parse_string(const char **json_pos, const char *end)
65{
66	const char *pos = *json_pos;
67	char *str, *spos, *s_end;
68	size_t max_len, buf_len;
69	u8 bin[2];
70
71	pos++; /* skip starting quote */
72
73	max_len = end - pos + 1;
74	buf_len = max_len > 10 ? 10 : max_len;
75	str = os_malloc(buf_len);
76	if (!str)
77		return NULL;
78	spos = str;
79	s_end = str + buf_len;
80
81	for (; pos < end; pos++) {
82		if (buf_len < max_len && s_end - spos < 3) {
83			char *tmp;
84			int idx;
85
86			idx = spos - str;
87			buf_len *= 2;
88			if (buf_len > max_len)
89				buf_len = max_len;
90			tmp = os_realloc(str, buf_len);
91			if (!tmp)
92				goto fail;
93			str = tmp;
94			spos = str + idx;
95			s_end = str + buf_len;
96		}
97
98		switch (*pos) {
99		case '\"': /* end string */
100			*spos = '\0';
101			/* caller will move to the next position */
102			*json_pos = pos;
103			return str;
104		case '\\':
105			pos++;
106			if (pos >= end) {
107				wpa_printf(MSG_DEBUG,
108					   "JSON: Truncated \\ escape");
109				goto fail;
110			}
111			switch (*pos) {
112			case '"':
113			case '\\':
114			case '/':
115				*spos++ = *pos;
116				break;
117			case 'n':
118				*spos++ = '\n';
119				break;
120			case 'r':
121				*spos++ = '\r';
122				break;
123			case 't':
124				*spos++ = '\t';
125				break;
126			case 'u':
127				if (end - pos < 5 ||
128				    hexstr2bin(pos + 1, bin, 2) < 0 ||
129				    bin[1] == 0x00) {
130					wpa_printf(MSG_DEBUG,
131						   "JSON: Invalid \\u escape");
132					goto fail;
133				}
134				if (bin[0] == 0x00) {
135					*spos++ = bin[1];
136				} else {
137					*spos++ = bin[0];
138					*spos++ = bin[1];
139				}
140				pos += 4;
141				break;
142			default:
143				wpa_printf(MSG_DEBUG,
144					   "JSON: Unknown escape '%c'", *pos);
145				goto fail;
146			}
147			break;
148		default:
149			*spos++ = *pos;
150			break;
151		}
152	}
153
154fail:
155	os_free(str);
156	return NULL;
157}
158
159
160static int json_parse_number(const char **json_pos, const char *end,
161			     int *ret_val)
162{
163	const char *pos = *json_pos;
164	size_t len;
165	char *str;
166
167	for (; pos < end; pos++) {
168		if (*pos != '-' && (*pos < '0' || *pos > '9')) {
169			pos--;
170			break;
171		}
172	}
173	if (pos == end)
174		pos--;
175	if (pos < *json_pos)
176		return -1;
177	len = pos - *json_pos + 1;
178	str = os_malloc(len + 1);
179	if (!str)
180		return -1;
181	os_memcpy(str, *json_pos, len);
182	str[len] = '\0';
183
184	*ret_val = atoi(str);
185	os_free(str);
186	*json_pos = pos;
187	return 0;
188}
189
190
191static int json_check_tree_state(struct json_token *token)
192{
193	if (!token)
194		return 0;
195	if (json_check_tree_state(token->child) < 0 ||
196	    json_check_tree_state(token->sibling) < 0)
197		return -1;
198	if (token->state != JSON_COMPLETED) {
199		wpa_printf(MSG_DEBUG,
200			   "JSON: Unexpected token state %d (name=%s type=%d)",
201			   token->state, token->name ? token->name : "N/A",
202			   token->type);
203		return -1;
204	}
205	return 0;
206}
207
208
209static struct json_token * json_alloc_token(unsigned int *tokens)
210{
211	(*tokens)++;
212	if (*tokens > JSON_MAX_TOKENS) {
213		wpa_printf(MSG_DEBUG, "JSON: Maximum token limit exceeded");
214		return NULL;
215	}
216	return os_zalloc(sizeof(struct json_token));
217}
218
219
220struct json_token * json_parse(const char *data, size_t data_len)
221{
222	struct json_token *root = NULL, *curr_token = NULL, *token = NULL;
223	const char *pos, *end;
224	char *str;
225	int num;
226	unsigned int depth = 0;
227	unsigned int tokens = 0;
228
229	pos = data;
230	end = data + data_len;
231
232	for (; pos < end; pos++) {
233		switch (*pos) {
234		case '[': /* start array */
235		case '{': /* start object */
236			if (!curr_token) {
237				token = json_alloc_token(&tokens);
238				if (!token)
239					goto fail;
240				if (!root)
241					root = token;
242			} else if (curr_token->state == JSON_WAITING_VALUE) {
243				token = curr_token;
244			} else if (curr_token->parent &&
245				   curr_token->parent->type == JSON_ARRAY &&
246				   curr_token->parent->state == JSON_STARTED &&
247				   curr_token->state == JSON_EMPTY) {
248				token = curr_token;
249			} else {
250				wpa_printf(MSG_DEBUG,
251					   "JSON: Invalid state for start array/object");
252				goto fail;
253			}
254			depth++;
255			if (depth > JSON_MAX_DEPTH) {
256				wpa_printf(MSG_DEBUG,
257					   "JSON: Max depth exceeded");
258				goto fail;
259			}
260			token->type = *pos == '[' ? JSON_ARRAY : JSON_OBJECT;
261			token->state = JSON_STARTED;
262			token->child = json_alloc_token(&tokens);
263			if (!token->child)
264				goto fail;
265			curr_token = token->child;
266			curr_token->parent = token;
267			curr_token->state = JSON_EMPTY;
268			break;
269		case ']': /* end array */
270		case '}': /* end object */
271			if (!curr_token || !curr_token->parent ||
272			    curr_token->parent->state != JSON_STARTED) {
273				wpa_printf(MSG_DEBUG,
274					   "JSON: Invalid state for end array/object");
275				goto fail;
276			}
277			depth--;
278			curr_token = curr_token->parent;
279			if ((*pos == ']' &&
280			     curr_token->type != JSON_ARRAY) ||
281			    (*pos == '}' &&
282			     curr_token->type != JSON_OBJECT)) {
283				wpa_printf(MSG_DEBUG,
284					   "JSON: Array/Object mismatch");
285				goto fail;
286			}
287			if (curr_token->child->state == JSON_EMPTY &&
288			    !curr_token->child->child &&
289			    !curr_token->child->sibling) {
290				/* Remove pending child token since the
291				 * array/object was empty. */
292				json_free(curr_token->child);
293				curr_token->child = NULL;
294			}
295			curr_token->state = JSON_COMPLETED;
296			break;
297		case '\"': /* string */
298			str = json_parse_string(&pos, end);
299			if (!str)
300				goto fail;
301			if (!curr_token) {
302				token = json_alloc_token(&tokens);
303				if (!token)
304					goto fail;
305				token->type = JSON_STRING;
306				token->string = str;
307				token->state = JSON_COMPLETED;
308			} else if (curr_token->parent &&
309				   curr_token->parent->type == JSON_ARRAY &&
310				   curr_token->parent->state == JSON_STARTED &&
311				   curr_token->state == JSON_EMPTY) {
312				curr_token->string = str;
313				curr_token->state = JSON_COMPLETED;
314				curr_token->type = JSON_STRING;
315				wpa_printf(MSG_MSGDUMP,
316					   "JSON: String value: '%s'",
317					   curr_token->string);
318			} else if (curr_token->state == JSON_EMPTY) {
319				curr_token->type = JSON_VALUE;
320				curr_token->name = str;
321				curr_token->state = JSON_STARTED;
322			} else if (curr_token->state == JSON_WAITING_VALUE) {
323				curr_token->string = str;
324				curr_token->state = JSON_COMPLETED;
325				curr_token->type = JSON_STRING;
326				wpa_printf(MSG_MSGDUMP,
327					   "JSON: String value: '%s' = '%s'",
328					   curr_token->name,
329					   curr_token->string);
330			} else {
331				wpa_printf(MSG_DEBUG,
332					   "JSON: Invalid state for a string");
333				os_free(str);
334				goto fail;
335			}
336			break;
337		case ' ':
338		case '\t':
339		case '\r':
340		case '\n':
341			/* ignore whitespace */
342			break;
343		case ':': /* name/value separator */
344			if (!curr_token || curr_token->state != JSON_STARTED)
345				goto fail;
346			curr_token->state = JSON_WAITING_VALUE;
347			break;
348		case ',': /* member separator */
349			if (!curr_token)
350				goto fail;
351			curr_token->sibling = json_alloc_token(&tokens);
352			if (!curr_token->sibling)
353				goto fail;
354			curr_token->sibling->parent = curr_token->parent;
355			curr_token = curr_token->sibling;
356			curr_token->state = JSON_EMPTY;
357			break;
358		case 't': /* true */
359		case 'f': /* false */
360		case 'n': /* null */
361			if (!((end - pos >= 4 &&
362			       os_strncmp(pos, "true", 4) == 0) ||
363			      (end - pos >= 5 &&
364			       os_strncmp(pos, "false", 5) == 0) ||
365			      (end - pos >= 4 &&
366			       os_strncmp(pos, "null", 4) == 0))) {
367				wpa_printf(MSG_DEBUG,
368					   "JSON: Invalid literal name");
369				goto fail;
370			}
371			if (!curr_token) {
372				token = json_alloc_token(&tokens);
373				if (!token)
374					goto fail;
375				curr_token = token;
376			} else if (curr_token->state == JSON_WAITING_VALUE) {
377				wpa_printf(MSG_MSGDUMP,
378					   "JSON: Literal name: '%s' = %c",
379					   curr_token->name, *pos);
380			} else if (curr_token->parent &&
381				   curr_token->parent->type == JSON_ARRAY &&
382				   curr_token->parent->state == JSON_STARTED &&
383				   curr_token->state == JSON_EMPTY) {
384				wpa_printf(MSG_MSGDUMP,
385					   "JSON: Literal name: %c", *pos);
386			} else {
387				wpa_printf(MSG_DEBUG,
388					   "JSON: Invalid state for a literal name");
389				goto fail;
390			}
391			switch (*pos) {
392			case 't':
393				curr_token->type = JSON_BOOLEAN;
394				curr_token->number = 1;
395				pos += 3;
396				break;
397			case 'f':
398				curr_token->type = JSON_BOOLEAN;
399				curr_token->number = 0;
400				pos += 4;
401				break;
402			case 'n':
403				curr_token->type = JSON_NULL;
404				pos += 3;
405				break;
406			}
407			curr_token->state = JSON_COMPLETED;
408			break;
409		case '-':
410		case '0':
411		case '1':
412		case '2':
413		case '3':
414		case '4':
415		case '5':
416		case '6':
417		case '7':
418		case '8':
419		case '9':
420			/* number */
421			if (json_parse_number(&pos, end, &num) < 0)
422				goto fail;
423			if (!curr_token) {
424				token = json_alloc_token(&tokens);
425				if (!token)
426					goto fail;
427				token->type = JSON_NUMBER;
428				token->number = num;
429				token->state = JSON_COMPLETED;
430			} else if (curr_token->state == JSON_WAITING_VALUE) {
431				curr_token->number = num;
432				curr_token->state = JSON_COMPLETED;
433				curr_token->type = JSON_NUMBER;
434				wpa_printf(MSG_MSGDUMP,
435					   "JSON: Number value: '%s' = '%d'",
436					   curr_token->name,
437					   curr_token->number);
438			} else if (curr_token->parent &&
439				   curr_token->parent->type == JSON_ARRAY &&
440				   curr_token->parent->state == JSON_STARTED &&
441				   curr_token->state == JSON_EMPTY) {
442				curr_token->number = num;
443				curr_token->state = JSON_COMPLETED;
444				curr_token->type = JSON_NUMBER;
445				wpa_printf(MSG_MSGDUMP,
446					   "JSON: Number value: %d",
447					   curr_token->number);
448			} else {
449				wpa_printf(MSG_DEBUG,
450					   "JSON: Invalid state for a number");
451				goto fail;
452			}
453			break;
454		default:
455			wpa_printf(MSG_DEBUG,
456				   "JSON: Unexpected JSON character: %c", *pos);
457			goto fail;
458		}
459
460		if (!root)
461			root = token;
462		if (!curr_token)
463			curr_token = token;
464	}
465
466	if (json_check_tree_state(root) < 0) {
467		wpa_printf(MSG_DEBUG, "JSON: Incomplete token in the tree");
468		goto fail;
469	}
470
471	return root;
472fail:
473	wpa_printf(MSG_DEBUG, "JSON: Parsing failed");
474	json_free(root);
475	return NULL;
476}
477
478
479void json_free(struct json_token *json)
480{
481	if (!json)
482		return;
483	json_free(json->child);
484	json_free(json->sibling);
485	os_free(json->name);
486	os_free(json->string);
487	os_free(json);
488}
489
490
491struct json_token * json_get_member(struct json_token *json, const char *name)
492{
493	struct json_token *token, *ret = NULL;
494
495	if (!json || json->type != JSON_OBJECT)
496		return NULL;
497	/* Return last matching entry */
498	for (token = json->child; token; token = token->sibling) {
499		if (token->name && os_strcmp(token->name, name) == 0)
500			ret = token;
501	}
502	return ret;
503}
504
505
506struct wpabuf * json_get_member_base64url(struct json_token *json,
507					  const char *name)
508{
509	struct json_token *token;
510	unsigned char *buf;
511	size_t buflen;
512	struct wpabuf *ret;
513
514	token = json_get_member(json, name);
515	if (!token || token->type != JSON_STRING)
516		return NULL;
517	buf = base64_url_decode((const unsigned char *) token->string,
518				os_strlen(token->string), &buflen);
519	if (!buf)
520		return NULL;
521	ret = wpabuf_alloc_ext_data(buf, buflen);
522	if (!ret)
523		os_free(buf);
524
525	return ret;
526}
527
528
529static const char * json_type_str(enum json_type type)
530{
531	switch (type) {
532	case JSON_VALUE:
533		return "VALUE";
534	case JSON_OBJECT:
535		return "OBJECT";
536	case JSON_ARRAY:
537		return "ARRAY";
538	case JSON_STRING:
539		return "STRING";
540	case JSON_NUMBER:
541		return "NUMBER";
542	case JSON_BOOLEAN:
543		return "BOOLEAN";
544	case JSON_NULL:
545		return "NULL";
546	}
547	return "??";
548}
549
550
551static void json_print_token(struct json_token *token, int depth,
552			     char *buf, size_t buflen)
553{
554	size_t len;
555	int ret;
556
557	if (!token)
558		return;
559	len = os_strlen(buf);
560	ret = os_snprintf(buf + len, buflen - len, "[%d:%s:%s]",
561			  depth, json_type_str(token->type),
562			  token->name ? token->name : "");
563	if (os_snprintf_error(buflen - len, ret)) {
564		buf[len] = '\0';
565		return;
566	}
567	json_print_token(token->child, depth + 1, buf, buflen);
568	json_print_token(token->sibling, depth, buf, buflen);
569}
570
571
572void json_print_tree(struct json_token *root, char *buf, size_t buflen)
573{
574	buf[0] = '\0';
575	json_print_token(root, 1, buf, buflen);
576}
577