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