patch 8.0.0169: json_decode() may run out of stack spacev8.0.0169

Problem:    For complicated string json_decode() may run out of stack space.
Solution:   Change the recursive solution into an iterative solution.

2 files changed, 392 insertions, 289 deletions

diff --git a/src/json.c b/src/json.c
index 2d0e706913..091d98f592 100644
--- a/src/json.c
+++ b/src/json.c
@@ -378,187 +378,6 @@ json_skip_white(js_read_T *reader)
 }
 
     static int
-json_decode_array(js_read_T *reader, typval_T *res, int options)
-{
-    char_u	*p;
-    typval_T	item;
-    listitem_T	*li;
-    int		ret;
-
-    if (res != NULL && rettv_list_alloc(res) == FAIL)
-    {
-	res->v_type = VAR_SPECIAL;
-	res->vval.v_number = VVAL_NONE;
-	return FAIL;
-    }
-    ++reader->js_used; /* consume the '[' */
-
-    while (TRUE)
-    {
-	json_skip_white(reader);
-	p = reader->js_buf + reader->js_used;
-	if (*p == NUL)
-	    return MAYBE;
-	if (*p == ']')
-	{
-	    ++reader->js_used; /* consume the ']' */
-	    break;
-	}
-
-	ret = json_decode_item(reader, res == NULL ? NULL : &item, options);
-	if (ret != OK)
-	    return ret;
-	if (res != NULL)
-	{
-	    li = listitem_alloc();
-	    if (li == NULL)
-	    {
-		clear_tv(&item);
-		return FAIL;
-	    }
-	    li->li_tv = item;
-	    list_append(res->vval.v_list, li);
-	}
-
-	json_skip_white(reader);
-	p = reader->js_buf + reader->js_used;
-	if (*p == ',')
-	    ++reader->js_used;
-	else if (*p != ']')
-	{
-	    if (*p == NUL)
-		return MAYBE;
-	    EMSG(_(e_invarg));
-	    return FAIL;
-	}
-    }
-    return OK;
-}
-
-    static int
-json_decode_object(js_read_T *reader, typval_T *res, int options)
-{
-    char_u	*p;
-    typval_T	tvkey;
-    typval_T	item;
-    dictitem_T	*di;
-    char_u	buf[NUMBUFLEN];
-    char_u	*key = NULL;
-    int		ret;
-
-    if (res != NULL && rettv_dict_alloc(res) == FAIL)
-    {
-	res->v_type = VAR_SPECIAL;
-	res->vval.v_number = VVAL_NONE;
-	return FAIL;
-    }
-    ++reader->js_used; /* consume the '{' */
-
-    while (TRUE)
-    {
-	json_skip_white(reader);
-	p = reader->js_buf + reader->js_used;
-	if (*p == NUL)
-	    return MAYBE;
-	if (*p == '}')
-	{
-	    ++reader->js_used; /* consume the '}' */
-	    break;
-	}
-
-	if ((options & JSON_JS) && reader->js_buf[reader->js_used] != '"')
-	{
-	    /* accept a key that is not in quotes */
-	    key = p = reader->js_buf + reader->js_used;
-	    while (*p != NUL && *p != ':' && *p > ' ')
-		++p;
-	    tvkey.v_type = VAR_STRING;
-	    tvkey.vval.v_string = vim_strnsave(key, (int)(p - key));
-	    reader->js_used += (int)(p - key);
-	    key = tvkey.vval.v_string;
-	}
-	else
-	{
-	    ret = json_decode_item(reader, res == NULL ? NULL : &tvkey,
-								     options);
-	    if (ret != OK)
-		return ret;
-	    if (res != NULL)
-	    {
-		key = get_tv_string_buf_chk(&tvkey, buf);
-		if (key == NULL || *key == NUL)
-		{
-		    clear_tv(&tvkey);
-		    EMSG(_(e_invarg));
-		    return FAIL;
-		}
-	    }
-	}
-
-	json_skip_white(reader);
-	p = reader->js_buf + reader->js_used;
-	if (*p != ':')
-	{
-	    if (res != NULL)
-		clear_tv(&tvkey);
-	    if (*p == NUL)
-		return MAYBE;
-	    EMSG(_(e_invarg));
-	    return FAIL;
-	}
-	++reader->js_used;
-	json_skip_white(reader);
-
-	ret = json_decode_item(reader, res == NULL ? NULL : &item, options);
-	if (ret != OK)
-	{
-	    if (res != NULL)
-		clear_tv(&tvkey);
-	    return ret;
-	}
-
-	if (res != NULL && dict_find(res->vval.v_dict, key, -1) != NULL)
-	{
-	    EMSG2(_("E937: Duplicate key in JSON: \"%s\""), key);
-	    clear_tv(&tvkey);
-	    clear_tv(&item);
-	    return FAIL;
-	}
-
-	if (res != NULL)
-	{
-	    di = dictitem_alloc(key);
-	    clear_tv(&tvkey);
-	    if (di == NULL)
-	    {
-		clear_tv(&item);
-		return FAIL;
-	    }
-	    di->di_tv = item;
-	    di->di_tv.v_lock = 0;
-	    if (dict_add(res->vval.v_dict, di) == FAIL)
-	    {
-		dictitem_free(di);
-		return FAIL;
-	    }
-	}
-
-	json_skip_white(reader);
-	p = reader->js_buf + reader->js_used;
-	if (*p == ',')
-	    ++reader->js_used;
-	else if (*p != '}')
-	{
-	    if (*p == NUL)
-		return MAYBE;
-	    EMSG(_(e_invarg));
-	    return FAIL;
-	}
-    }
-    return OK;
-}
-
-    static int
 json_decode_string(js_read_T *reader, typval_T *res)
 {
     garray_T    ga;
@@ -723,6 +542,19 @@ json_decode_string(js_read_T *reader, typval_T *res)
     return MAYBE;
 }
 
+typedef enum {
+    JSON_ARRAY,		/* parsing items in an array */
+    JSON_OBJECT_KEY,	/* parsing key of an object */
+    JSON_OBJECT		/* parsing item in an object, after the key */
+} json_decode_T;
+
+typedef struct {
+    json_decode_T jd_type;
+    typval_T	  jd_tv;	/* the list or dict */
+    typval_T	  jd_key_tv;
+    char_u	  *jd_key;
+} json_dec_item_T;
+
 /*
  * Decode one item and put it in "res".  If "res" is NULL only advance.
  * Must already have skipped white space.
@@ -735,157 +567,426 @@ json_decode_item(js_read_T *reader, typval_T *res, int options)
 {
     char_u	*p;
     int		len;
+    int		retval;
+    garray_T	stack;
+    typval_T	item;
+    typval_T	*cur_item;
+    json_dec_item_T *top_item;
+    char_u	key_buf[NUMBUFLEN];
+
+    ga_init2(&stack, sizeof(json_dec_item_T), 100);
+    cur_item = res;
+    init_tv(&item);
 
     fill_numbuflen(reader);
     p = reader->js_buf + reader->js_used;
-    switch (*p)
+    for (;;)
     {
-	case '[': /* array */
-	    return json_decode_array(reader, res, options);
-
-	case '{': /* object */
-	    return json_decode_object(reader, res, options);
-
-	case '"': /* string */
-	    return json_decode_string(reader, res);
-
-	case ',': /* comma: empty item */
-	    if ((options & JSON_JS) == 0)
+	top_item = NULL;
+	if (stack.ga_len > 0)
+	{
+	    top_item = ((json_dec_item_T *)stack.ga_data) + stack.ga_len - 1;
+	    json_skip_white(reader);
+	    p = reader->js_buf + reader->js_used;
+	    if (*p == NUL)
 	    {
-		EMSG(_(e_invarg));
-		return FAIL;
+		retval = MAYBE;
+		if (top_item->jd_type == JSON_OBJECT)
+		    /* did get the key, clear it */
+		    clear_tv(&top_item->jd_key_tv);
+		goto theend;
 	    }
-	    /* FALLTHROUGH */
-	case NUL: /* empty */
-	    if (res != NULL)
+	    if (top_item->jd_type == JSON_OBJECT_KEY
+					    || top_item->jd_type == JSON_ARRAY)
 	    {
-		res->v_type = VAR_SPECIAL;
-		res->vval.v_number = VVAL_NONE;
+		/* Check for end of object or array. */
+		if (*p == (top_item->jd_type == JSON_ARRAY ? ']' : '}'))
+		{
+		    ++reader->js_used; /* consume the ']' or '}' */
+		    --stack.ga_len;
+		    if (stack.ga_len == 0)
+		    {
+			retval = OK;
+			goto theend;
+		    }
+		    if (cur_item != NULL)
+			cur_item = &top_item->jd_tv;
+		    goto item_end;
+		}
 	    }
-	    return OK;
+	}
 
-	default:
-	    if (VIM_ISDIGIT(*p) || *p == '-')
+	if (top_item != NULL && top_item->jd_type == JSON_OBJECT_KEY
+		&& (options & JSON_JS)
+		&& reader->js_buf[reader->js_used] != '"')
+	{
+	    char_u *key;
+
+	    /* accept an object key that is not in quotes */
+	    key = p = reader->js_buf + reader->js_used;
+	    while (*p != NUL && *p != ':' && *p > ' ')
+		++p;
+	    cur_item->v_type = VAR_STRING;
+	    cur_item->vval.v_string = vim_strnsave(key, (int)(p - key));
+	    reader->js_used += (int)(p - key);
+	    top_item->jd_key = cur_item->vval.v_string;
+	}
+	else
+	{
+	    switch (*p)
 	    {
-#ifdef FEAT_FLOAT
-		char_u  *sp = p;
+		case '[': /* start of array */
+		    if (ga_grow(&stack, 1) == FAIL)
+		    {
+			retval = FAIL;
+			break;
+		    }
+		    if (cur_item != NULL && rettv_list_alloc(cur_item) == FAIL)
+		    {
+			cur_item->v_type = VAR_SPECIAL;
+			cur_item->vval.v_number = VVAL_NONE;
+			retval = FAIL;
+			break;
+		    }
 
-		if (*sp == '-')
-		{
-		    ++sp;
-		    if (*sp == NUL)
-			return MAYBE;
-		    if (!VIM_ISDIGIT(*sp))
+		    ++reader->js_used; /* consume the '[' */
+		    top_item = ((json_dec_item_T *)stack.ga_data)
+								+ stack.ga_len;
+		    top_item->jd_type = JSON_ARRAY;
+		    ++stack.ga_len;
+		    if (cur_item != NULL)
 		    {
-			EMSG(_(e_invarg));
-			return FAIL;
+			top_item->jd_tv = *cur_item;
+			cur_item = &item;
 		    }
-		}
-		sp = skipdigits(sp);
-		if (*sp == '.' || *sp == 'e' || *sp == 'E')
-		{
-		    if (res == NULL)
+		    continue;
+
+		case '{': /* start of object */
+		    if (ga_grow(&stack, 1) == FAIL)
+		    {
+			retval = FAIL;
+			break;
+		    }
+		    if (cur_item != NULL && rettv_dict_alloc(cur_item) == FAIL)
 		    {
-			float_T f;
+			cur_item->v_type = VAR_SPECIAL;
+			cur_item->vval.v_number = VVAL_NONE;
+			retval = FAIL;
+			break;
+		    }
 
-			len = string2float(p, &f);
+		    ++reader->js_used; /* consume the '{' */
+		    top_item = ((json_dec_item_T *)stack.ga_data)
+								+ stack.ga_len;
+		    top_item->jd_type = JSON_OBJECT_KEY;
+		    ++stack.ga_len;
+		    if (cur_item != NULL)
+		    {
+			top_item->jd_tv = *cur_item;
+			cur_item = &top_item->jd_key_tv;
 		    }
-		    else
+		    continue;
+
+		case '"': /* string */
+		    retval = json_decode_string(reader, cur_item);
+		    break;
+
+		case ',': /* comma: empty item */
+		    if ((options & JSON_JS) == 0)
 		    {
-			res->v_type = VAR_FLOAT;
-			len = string2float(p, &res->vval.v_float);
+			EMSG(_(e_invarg));
+			retval = FAIL;
+			break;
 		    }
-		}
-		else
-#endif
-		{
-		    varnumber_T nr;
+		    /* FALLTHROUGH */
+		case NUL: /* empty */
+		    if (cur_item != NULL)
+		    {
+			cur_item->v_type = VAR_SPECIAL;
+			cur_item->vval.v_number = VVAL_NONE;
+		    }
+		    retval = OK;
+		    break;
 
-		    vim_str2nr(reader->js_buf + reader->js_used,
-			    NULL, &len, 0, /* what */
-			    &nr, NULL, 0);
-		    if (res != NULL)
+		default:
+		    if (VIM_ISDIGIT(*p) || *p == '-')
+		    {
+#ifdef FEAT_FLOAT
+			char_u  *sp = p;
+
+			if (*sp == '-')
+			{
+			    ++sp;
+			    if (*sp == NUL)
+			    {
+				retval = MAYBE;
+				break;
+			    }
+			    if (!VIM_ISDIGIT(*sp))
+			    {
+				EMSG(_(e_invarg));
+				retval = FAIL;
+				break;
+			    }
+			}
+			sp = skipdigits(sp);
+			if (*sp == '.' || *sp == 'e' || *sp == 'E')
+			{
+			    if (cur_item == NULL)
+			    {
+				float_T f;
+
+				len = string2float(p, &f);
+			    }
+			    else
+			    {
+				cur_item->v_type = VAR_FLOAT;
+				len = string2float(p, &cur_item->vval.v_float);
+			    }
+			}
+			else
+#endif
+			{
+			    varnumber_T nr;
+
+			    vim_str2nr(reader->js_buf + reader->js_used,
+				    NULL, &len, 0, /* what */
+				    &nr, NULL, 0);
+			    if (cur_item != NULL)
+			    {
+				cur_item->v_type = VAR_NUMBER;
+				cur_item->vval.v_number = nr;
+			    }
+			}
+			reader->js_used += len;
+			retval = OK;
+			break;
+		    }
+		    if (STRNICMP((char *)p, "false", 5) == 0)
 		    {
-			res->v_type = VAR_NUMBER;
-			res->vval.v_number = nr;
+			reader->js_used += 5;
+			if (cur_item != NULL)
+			{
+			    cur_item->v_type = VAR_SPECIAL;
+			    cur_item->vval.v_number = VVAL_FALSE;
+			}
+			retval = OK;
+			break;
 		    }
-		}
-		reader->js_used += len;
-		return OK;
+		    if (STRNICMP((char *)p, "true", 4) == 0)
+		    {
+			reader->js_used += 4;
+			if (cur_item != NULL)
+			{
+			    cur_item->v_type = VAR_SPECIAL;
+			    cur_item->vval.v_number = VVAL_TRUE;
+			}
+			retval = OK;
+			break;
+		    }
+		    if (STRNICMP((char *)p, "null", 4) == 0)
+		    {
+			reader->js_used += 4;
+			if (cur_item != NULL)
+			{
+			    cur_item->v_type = VAR_SPECIAL;
+			    cur_item->vval.v_number = VVAL_NULL;
+			}
+			retval = OK;
+			break;
+		    }
+#ifdef FEAT_FLOAT
+		    if (STRNICMP((char *)p, "NaN", 3) == 0)
+		    {
+			reader->js_used += 3;
+			if (cur_item != NULL)
+			{
+			    cur_item->v_type = VAR_FLOAT;
+			    cur_item->vval.v_float = NAN;
+			}
+			retval = OK;
+			break;
+		    }
+		    if (STRNICMP((char *)p, "Infinity", 8) == 0)
+		    {
+			reader->js_used += 8;
+			if (cur_item != NULL)
+			{
+			    cur_item->v_type = VAR_FLOAT;
+			    cur_item->vval.v_float = INFINITY;
+			}
+			retval = OK;
+			break;
+		    }
+#endif
+		    /* check for truncated name */
+		    len = (int)(reader->js_end - (reader->js_buf + reader->js_used));
+		    if (
+			    (len < 5 && STRNICMP((char *)p, "false", len) == 0)
+#ifdef FEAT_FLOAT
+			    || (len < 8 && STRNICMP((char *)p, "Infinity", len) == 0)
+			    || (len < 3 && STRNICMP((char *)p, "NaN", len) == 0)
+#endif
+			    || (len < 4 && (STRNICMP((char *)p, "true", len) == 0
+				       ||  STRNICMP((char *)p, "null", len) == 0)))
+
+			retval = MAYBE;
+		    else
+			retval = FAIL;
+		    break;
 	    }
-	    if (STRNICMP((char *)p, "false", 5) == 0)
+
+	    /* We are finished when retval is FAIL or MAYBE and when at the
+	     * toplevel. */
+	    if (retval == FAIL)
+		break;
+	    if (retval == MAYBE || stack.ga_len == 0)
+		goto theend;
+
+	    if (top_item != NULL && top_item->jd_type == JSON_OBJECT_KEY
+		    && cur_item != NULL)
 	    {
-		reader->js_used += 5;
-		if (res != NULL)
+		top_item->jd_key = get_tv_string_buf_chk(cur_item, key_buf);
+		if (top_item->jd_key == NULL || *top_item->jd_key == NUL)
 		{
-		    res->v_type = VAR_SPECIAL;
-		    res->vval.v_number = VVAL_FALSE;
+		    clear_tv(cur_item);
+		    EMSG(_(e_invarg));
+		    retval = FAIL;
+		    goto theend;
 		}
-		return OK;
 	    }
-	    if (STRNICMP((char *)p, "true", 4) == 0)
-	    {
-		reader->js_used += 4;
+	}
+
+item_end:
+	top_item = ((json_dec_item_T *)stack.ga_data) + stack.ga_len - 1;
+	switch (top_item->jd_type)
+	{
+	    case JSON_ARRAY:
 		if (res != NULL)
 		{
-		    res->v_type = VAR_SPECIAL;
-		    res->vval.v_number = VVAL_TRUE;
+		    listitem_T	*li = listitem_alloc();
+
+		    if (li == NULL)
+		    {
+			clear_tv(cur_item);
+			retval = FAIL;
+			goto theend;
+		    }
+		    li->li_tv = *cur_item;
+		    list_append(top_item->jd_tv.vval.v_list, li);
 		}
-		return OK;
-	    }
-	    if (STRNICMP((char *)p, "null", 4) == 0)
-	    {
-		reader->js_used += 4;
-		if (res != NULL)
+		if (cur_item != NULL)
+		    cur_item = &item;
+
+		json_skip_white(reader);
+		p = reader->js_buf + reader->js_used;
+		if (*p == ',')
+		    ++reader->js_used;
+		else if (*p != ']')
 		{
-		    res->v_type = VAR_SPECIAL;
-		    res->vval.v_number = VVAL_NULL;
+		    if (*p == NUL)
+			retval = MAYBE;
+		    else
+		    {
+			EMSG(_(e_invarg));
+			retval = FAIL;
+		    }
+		    goto theend;
 		}
-		return OK;
-	    }
-#ifdef FEAT_FLOAT
-	    if (STRNICMP((char *)p, "NaN", 3) == 0)
-	    {
-		reader->js_used += 3;
-		if (res != NULL)
+		break;
+
+	    case JSON_OBJECT_KEY:
+		json_skip_white(reader);
+		p = reader->js_buf + reader->js_used;
+		if (*p != ':')
+		{
+		    if (cur_item != NULL)
+			clear_tv(cur_item);
+		    if (*p == NUL)
+			retval = MAYBE;
+		    else
+		    {
+			EMSG(_(e_invarg));
+			retval = FAIL;
+		    }
+		    goto theend;
+		}
+		++reader->js_used;
+		json_skip_white(reader);
+		top_item->jd_type = JSON_OBJECT;
+		if (cur_item != NULL)
+		    cur_item = &item;
+		break;
+
+	    case JSON_OBJECT:
+		if (cur_item != NULL
+			&& dict_find(top_item->jd_tv.vval.v_dict,
+						 top_item->jd_key, -1) != NULL)
 		{
-		    res->v_type = VAR_FLOAT;
-		    res->vval.v_float = NAN;
+		    EMSG2(_("E937: Duplicate key in JSON: \"%s\""),
+							     top_item->jd_key);
+		    clear_tv(&top_item->jd_key_tv);
+		    clear_tv(cur_item);
+		    retval = FAIL;
+		    goto theend;
 		}
-		return OK;
-	    }
-	    if (STRNICMP((char *)p, "Infinity", 8) == 0)
-	    {
-		reader->js_used += 8;
-		if (res != NULL)
+
+		if (cur_item != NULL)
 		{
-		    res->v_type = VAR_FLOAT;
-		    res->vval.v_float = INFINITY;
+		    dictitem_T *di = dictitem_alloc(top_item->jd_key);
+
+		    clear_tv(&top_item->jd_key_tv);
+		    if (di == NULL)
+		    {
+			clear_tv(cur_item);
+			retval = FAIL;
+			goto theend;
+		    }
+		    di->di_tv = *cur_item;
+		    di->di_tv.v_lock = 0;
+		    if (dict_add(top_item->jd_tv.vval.v_dict, di) == FAIL)
+		    {
+			dictitem_free(di);
+			retval = FAIL;
+			goto theend;
+		    }
 		}
-		return OK;
-	    }
-#endif
-	    /* check for truncated name */
-	    len = (int)(reader->js_end - (reader->js_buf + reader->js_used));
-	    if (
-		    (len < 5 && STRNICMP((char *)p, "false", len) == 0)
-#ifdef FEAT_FLOAT
-		    || (len < 8 && STRNICMP((char *)p, "Infinity", len) == 0)
-		    || (len < 3 && STRNICMP((char *)p, "NaN", len) == 0)
-#endif
-		    || (len < 4 && (STRNICMP((char *)p, "true", len) == 0
-			       ||  STRNICMP((char *)p, "null", len) == 0)))
-		return MAYBE;
-	    break;
+
+		json_skip_white(reader);
+		p = reader->js_buf + reader->js_used;
+		if (*p == ',')
+		    ++reader->js_used;
+		else if (*p != '}')
+		{
+		    if (*p == NUL)
+			retval = MAYBE;
+		    else
+		    {
+			EMSG(_(e_invarg));
+			retval = FAIL;
+		    }
+		    goto theend;
+		}
+		top_item->jd_type = JSON_OBJECT_KEY;
+		if (cur_item != NULL)
+		    cur_item = &top_item->jd_key_tv;
+		break;
+	}
     }
 
+    /* Get here when parsing failed. */
     if (res != NULL)
     {
+	clear_tv(res);
 	res->v_type = VAR_SPECIAL;
 	res->vval.v_number = VVAL_NONE;
     }
     EMSG(_(e_invarg));
-    return FAIL;
+
+theend:
+    ga_clear(&stack);
+    clear_tv(&item);
+    return retval;
 }
 
 /*
diff --git a/src/version.c b/src/version.c
index 6294188277..23dd5aeb6d 100644
--- a/src/version.c
+++ b/src/version.c
@@ -765,6 +765,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    169,
+/**/
     168,
 /**/
     167,