Commit: patch 9.2.0335: json_encode() uses recursive algorithm

[Christian Brabandt]

patch 9.2.0335: json_encode() uses recursive algorithm

Commit: https://github.com/vim/vim/commit/71c10dcd58612fbbcf91b8ad74d6cc9d3fffafda
Author: Yasuhiro Matsumoto <matt...@gmail.com>
Date: Fri Apr 10 21:37:44 2026 +0000

patch 9.2.0335: json_encode() uses recursive algorithm

Problem: json_encode() uses recursive algorithm
Solution: Convert from recursive to iterative algorithm to prevent
stack overflow on deep recursive levels
(Yasuhiro Matsumoto).

closes: #19839

Signed-off-by: Yasuhiro Matsumoto <matt...@gmail.com>
Signed-off-by: Christian Brabandt <c...@256bit.org>

diff --git a/src/json.c b/src/json.c
index a21ed6e77..b0d98a290 100644
--- a/src/json.c
+++ b/src/json.c
@@ -18,7 +18,7 @@

#if defined(FEAT_EVAL)

-static int json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int depth);
+static int json_encode_item(garray_T *gap, typval_T *val, int copyID, int options);

/*
* Encode "val" into a JSON format string.
@@ -28,7 +28,7 @@ static int json_encode_item(garray_T *gap, typval_T *val, int copyID, int option
static int
json_encode_gap(garray_T *gap, typval_T *val, int options)
{
- if (json_encode_item(gap, val, get_copyID(), options, 0) == FAIL)
+ if (json_encode_item(gap, val, get_copyID(), options) == FAIL)
{
ga_clear(gap);
gap->ga_data = vim_strsave((char_u *)"");
@@ -264,31 +264,61 @@ is_simple_key(char_u *key)
return TRUE;
}

+typedef enum {
+ ENC_LIST,
+ ENC_TUPLE,
+ ENC_DICT,
+} json_enc_type_T;
+
+typedef struct {
+ json_enc_type_T je_type;
+ int je_options; // options when this container was entered
+ union {
+ struct {
+ list_T *list;
+ listitem_T *li; // current item
+ } l;
+ struct {
+ tuple_T *tuple;
+ int idx; // current index
+ int len;
+ } t;
+ struct {
+ dict_T *dict;
+ hashitem_T *hi; // current entry
+ int todo; // remaining entries
+ } d;
+ } je_u;
+} json_enc_frame_T;
+
/*
* Encode "val" into "gap".
+ * Uses an explicit stack to avoid deep recursion on nested structures.
* Return FAIL or OK.
*/
static int
-json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int depth)
+json_encode_item(garray_T *gap, typval_T *val, int copyID, int options)
{
- char_u numbuf[NUMBUFLEN];
- char_u *res;
- blob_T *b;
- list_T *l;
- tuple_T *tuple;
- dict_T *d;
- int i;
+ char_u numbuf[NUMBUFLEN];
+ char_u *res;
+ blob_T *b;
+ list_T *l;
+ tuple_T *tuple;
+ dict_T *d;
+ int i;
+ garray_T stack;
+ typval_T *cur_val;
+ json_enc_frame_T *frame;
+
+ ga_init2(&stack, sizeof(json_enc_frame_T), 100);
+ cur_val = val;

- if (depth > p_mfd)
+ for (;;)
{
- emsg(_(e_function_call_depth_is_higher_than_maxfuncdepth));
- return FAIL;
- }
-
- switch (val->v_type)
+ switch (cur_val->v_type)
{
case VAR_BOOL:
- switch ((long)val->vval.v_number)
+ switch ((long)cur_val->vval.v_number)
{
case VVAL_FALSE: GA_CONCAT_LITERAL(gap, "false"); break;
case VVAL_TRUE: GA_CONCAT_LITERAL(gap, "true"); break;
@@ -296,7 +326,7 @@ json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int dept
break;

case VAR_SPECIAL:
- switch ((long)val->vval.v_number)
+ switch ((long)cur_val->vval.v_number)
{
case VVAL_NONE: if ((options & JSON_JS) != 0
&& (options & JSON_NO_NONE) == 0)
@@ -312,13 +342,13 @@ json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int dept
size_t numbuflen;

numbuflen = vim_snprintf_safelen((char *)numbuf, sizeof(numbuf),
- "%lld", (varnumber_T)val->vval.v_number);
+ "%lld", (varnumber_T)cur_val->vval.v_number);
ga_concat_len(gap, numbuf, numbuflen);
}
break;

case VAR_STRING:
- res = val->vval.v_string;
+ res = cur_val->vval.v_string;
write_string(gap, res);
break;

@@ -330,11 +360,11 @@ json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int dept
case VAR_CLASS:
case VAR_OBJECT:
case VAR_TYPEALIAS:
- semsg(_(e_cannot_json_encode_str), vartype_name(val->v_type));
- return FAIL;
+ semsg(_(e_cannot_json_encode_str), vartype_name(cur_val->v_type));
+ goto theend;

case VAR_BLOB:
- b = val->vval.v_blob;
+ b = cur_val->vval.v_blob;
if (b == NULL || b->bv_ga.ga_len == 0)
GA_CONCAT_LITERAL(gap, "[]");
else
@@ -366,7 +396,7 @@ json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int dept
break;

case VAR_LIST:
- l = val->vval.v_list;
+ l = cur_val->vval.v_list;
if (l == NULL)
GA_CONCAT_LITERAL(gap, "[]");
else
@@ -375,26 +405,28 @@ json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int dept
GA_CONCAT_LITERAL(gap, "[]");
else
{
- listitem_T *li;
-
l->lv_copyID = copyID;
ga_append(gap, '[');
CHECK_LIST_MATERIALIZE(l);
- for (li = l->lv_first; li != NULL && !got_int; )
+ if (l->lv_first != NULL)
{
- if (json_encode_item(gap, &li->li_tv, copyID,
- options & JSON_JS,
- depth + 1) == FAIL)
- return FAIL;
- if ((options & JSON_JS)
- && li->li_next == NULL
- && li->li_tv.v_type == VAR_SPECIAL
- && li->li_tv.vval.v_number == VVAL_NONE)
- // add an extra comma if the last item is v:none
- ga_append(gap, ',');
- li = li->li_next;
- if (li != NULL)
- ga_append(gap, ',');
+ if (stack.ga_len >= p_mfd)
+ {
+ emsg(_(e_function_call_depth_is_higher_than_maxfuncdepth));
+ goto theend;
+ }
+ if (ga_grow(&stack, 1) == FAIL)
+ goto theend;
+ frame = ((json_enc_frame_T *)stack.ga_data)
+ + stack.ga_len;
+ frame->je_type = ENC_LIST;
+ frame->je_options = options;
+ frame->je_u.l.list = l;
+ frame->je_u.l.li = l->lv_first;
+ ++stack.ga_len;
+ options = options & JSON_JS;
+ cur_val = &l->lv_first->li_tv;
+ continue;
}
ga_append(gap, ']');
l->lv_copyID = 0;
@@ -403,7 +435,7 @@ json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int dept
break;

case VAR_TUPLE:
- tuple = val->vval.v_tuple;
+ tuple = cur_val->vval.v_tuple;
if (tuple == NULL)
GA_CONCAT_LITERAL(gap, "[]");
else
@@ -414,33 +446,37 @@ json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int dept
{
int len = TUPLE_LEN(tuple);

- tuple->tv_copyID = copyID;
- ga_append(gap, '[');
- for (i = 0; i < len && !got_int; i++)
+ if (len > 0)
{
- typval_T *t_item = TUPLE_ITEM(tuple, i);
- if (json_encode_item(gap, t_item, copyID,
- options & JSON_JS,
- depth + 1) == FAIL)
- return FAIL;
-
- if ((options & JSON_JS)
- && i == len - 1
- && t_item->v_type == VAR_SPECIAL
- && t_item->vval.v_number == VVAL_NONE)
- // add an extra comma if the last item is v:none
- ga_append(gap, ',');
- if (i <= len - 2)
- ga_append(gap, ',');
+ tuple->tv_copyID = copyID;
+ ga_append(gap, '[');
+ if (stack.ga_len >= p_mfd)
+ {
+ emsg(_(e_function_call_depth_is_higher_than_maxfuncdepth));
+ goto theend;
+ }
+ if (ga_grow(&stack, 1) == FAIL)
+ goto theend;
+ frame = ((json_enc_frame_T *)stack.ga_data)
+ + stack.ga_len;
+ frame->je_type = ENC_TUPLE;
+ frame->je_options = options;
+ frame->je_u.t.tuple = tuple;
+ frame->je_u.t.idx = 0;
+ frame->je_u.t.len = len;
+ ++stack.ga_len;
+ options = options & JSON_JS;
+ cur_val = TUPLE_ITEM(tuple, 0);
+ continue;
}
- ga_append(gap, ']');
- tuple->tv_copyID = 0;
+ else
+ GA_CONCAT_LITERAL(gap, "[]");
}
}
break;

case VAR_DICT:
- d = val->vval.v_dict;
+ d = cur_val->vval.v_dict;
if (d == NULL)
GA_CONCAT_LITERAL(gap, "{}");
else
@@ -449,46 +485,60 @@ json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int dept
GA_CONCAT_LITERAL(gap, "{}");
else
{
- int first = TRUE;
int todo = (int)d->dv_hashtab.ht_used;
hashitem_T *hi;

- d->dv_copyID = copyID;
- ga_append(gap, '{');
+ if (todo > 0)
+ {
+ d->dv_copyID = copyID;
+ ga_append(gap, '{');

- for (hi = d->dv_hashtab.ht_array; todo > 0 && !got_int;
- ++hi)
- if (!HASHITEM_EMPTY(hi))
- {
- --todo;
- if (first)
- first = FALSE;
- else
- ga_append(gap, ',');
- if ((options & JSON_JS)
+ // Find first non-empty hash entry
+ for (hi = d->dv_hashtab.ht_array;
+ HASHITEM_EMPTY(hi); ++hi)
+ ;
+ --todo;
+
+ // Write first key
+ if ((options & JSON_JS)
&& is_simple_key(hi->hi_key))
- ga_concat(gap, hi->hi_key);
- else
- write_string(gap, hi->hi_key);
- ga_append(gap, ':');
- if (json_encode_item(gap, &dict_lookup(hi)->di_tv,
- copyID, options | JSON_NO_NONE,
- depth + 1) == FAIL)
- return FAIL;
+ ga_concat(gap, hi->hi_key);
+ else
+ write_string(gap, hi->hi_key);
+ ga_append(gap, ':');
+
+ if (stack.ga_len >= p_mfd)
+ {
+ emsg(_(e_function_call_depth_is_higher_than_maxfuncdepth));
+ goto theend;
}
- ga_append(gap, '}');
- d->dv_copyID = 0;
+ if (ga_grow(&stack, 1) == FAIL)
+ goto theend;
+ frame = ((json_enc_frame_T *)stack.ga_data)
+ + stack.ga_len;
+ frame->je_type = ENC_DICT;
+ frame->je_options = options;
+ frame->je_u.d.dict = d;
+ frame->je_u.d.hi = hi;
+ frame->je_u.d.todo = todo;
+ ++stack.ga_len;
+ options = options | JSON_NO_NONE;
+ cur_val = &dict_lookup(hi)->di_tv;
+ continue;
+ }
+ else
+ GA_CONCAT_LITERAL(gap, "{}");
}
}
break;

case VAR_FLOAT:
#if defined(HAVE_MATH_H)
- if (isnan(val->vval.v_float))
+ if (isnan(cur_val->vval.v_float))
GA_CONCAT_LITERAL(gap, "NaN");
- else if (isinf(val->vval.v_float))
+ else if (isinf(cur_val->vval.v_float))
{
- if (val->vval.v_float < 0.0)
+ if (cur_val->vval.v_float < 0.0)
GA_CONCAT_LITERAL(gap, "-Infinity");
else
GA_CONCAT_LITERAL(gap, "Infinity");
@@ -499,17 +549,151 @@ json_encode_item(garray_T *gap, typval_T *val, int copyID, int options, int dept
size_t numbuflen;

numbuflen = vim_snprintf_safelen((char *)numbuf, sizeof(numbuf),
- "%g", val->vval.v_float);
+ "%g", cur_val->vval.v_float);
ga_concat_len(gap, numbuf, numbuflen);
}
break;
+
case VAR_UNKNOWN:
case VAR_ANY:
case VAR_VOID:
internal_error_no_abort("json_encode_item()");
- return FAIL;
+ goto theend;
}
- return OK;
+
+ // Process the completed item by advancing containers or
+ // returning when the stack is empty.
+ for (;;)
+ {
+ int advance = FALSE;
+
+ if (stack.ga_len == 0)
+ {
+ ga_clear(&stack);
+ return OK;
+ }
+
+ frame = ((json_enc_frame_T *)stack.ga_data)
+ + stack.ga_len - 1;
+ switch (frame->je_type)
+ {
+ case ENC_LIST:
+ {
+ listitem_T *li = frame->je_u.l.li;
+
+ // JSON_JS: add trailing comma if last item is v:none
+ if ((frame->je_options & JSON_JS)
+ && li->li_next == NULL
+ && li->li_tv.v_type == VAR_SPECIAL
+ && li->li_tv.vval.v_number == VVAL_NONE)
+ ga_append(gap, ',');
+
+ li = li->li_next;
+ frame->je_u.l.li = li;
+ if (li != NULL && !got_int)
+ {
+ ga_append(gap, ',');
+ options = frame->je_options & JSON_JS;
+ cur_val = &li->li_tv;
+ advance = TRUE;
+ break;
+ }
+ ga_append(gap, ']');
+ frame->je_u.l.list->lv_copyID = 0;
+ --stack.ga_len;
+ break;
+ }
+
+ case ENC_TUPLE:
+ {
+ int idx = frame->je_u.t.idx;
+ int len = frame->je_u.t.len;
+
+ // JSON_JS: add trailing comma if last item is v:none
+ if ((frame->je_options & JSON_JS) && idx == len - 1)
+ {
+ typval_T *t_item =
+ TUPLE_ITEM(frame->je_u.t.tuple, idx);
+
+ if (t_item->v_type == VAR_SPECIAL
+ && t_item->vval.v_number == VVAL_NONE)
+ ga_append(gap, ',');
+ }
+
+ ++idx;
+ frame->je_u.t.idx = idx;
+ if (idx < len && !got_int)
+ {
+ ga_append(gap, ',');
+ options = frame->je_options & JSON_JS;
+ cur_val = TUPLE_ITEM(frame->je_u.t.tuple, idx);
+ advance = TRUE;
+ break;
+ }
+ ga_append(gap, ']');
+ frame->je_u.t.tuple->tv_copyID = 0;
+ --stack.ga_len;
+ break;
+ }
+
+ case ENC_DICT:
+ {
+ hashitem_T *hi = frame->je_u.d.hi;
+ int todo = frame->je_u.d.todo;
+
+ if (todo > 0 && !got_int)
+ {
+ // Advance to next non-empty entry
+ for (++hi; HASHITEM_EMPTY(hi); ++hi)
+ ;
+ --todo;
+ frame->je_u.d.hi = hi;
+ frame->je_u.d.todo = todo;
+
+ ga_append(gap, ',');
+ if ((frame->je_options & JSON_JS)
+ && is_simple_key(hi->hi_key))
+ ga_concat(gap, hi->hi_key);
+ else
+ write_string(gap, hi->hi_key);
+ ga_append(gap, ':');
+
+ options = frame->je_options | JSON_NO_NONE;
+ cur_val = &dict_lookup(hi)->di_tv;
+ advance = TRUE;
+ break;
+ }
+ ga_append(gap, '}');
+ frame->je_u.d.dict->dv_copyID = 0;
+ --stack.ga_len;
+ break;
+ }
+ }
+ if (advance)
+ break;
+ }
+ }
+
+theend:
+ // Clean up copyIDs for remaining frames on error/failure
+ for (i = 0; i < stack.ga_len; i++)
+ {
+ frame = ((json_enc_frame_T *)stack.ga_data) + i;
+ switch (frame->je_type)
+ {
+ case ENC_LIST:
+ frame->je_u.l.list->lv_copyID = 0;
+ break;
+ case ENC_TUPLE:
+ frame->je_u.t.tuple->tv_copyID = 0;
+ break;
+ case ENC_DICT:
+ frame->je_u.d.dict->dv_copyID = 0;
+ break;
+ }
+ }
+ ga_clear(&stack);
+ return FAIL;
}

/*
diff --git a/src/version.c b/src/version.c
index 83eb6ebec..0de4e4f14 100644
--- a/src/version.c
+++ b/src/version.c
@@ -734,6 +734,8 @@ static char *(features[]) =

static int included_patches[] =
{ /* Add new patch number below this line */
+/**/
+ 335,
/**/
334,
/**/