# HG changeset patch
# User Bram Moolenaar <bram@vim.org>
# Date 1422964518 -3600
# Node ID 38add5a3d617109be3be5e4c0d0b7a32ab2a2e00
# Parent  84171683fd6681984b88b7b70d0d3e6a317ac169
updated for version 7.4.609
Problem:    For complicated list and dict use the garbage collector can run
	    out of stack space.
Solution:   Use a stack of dicts and lists to be marked, thus making it
	    iterative instead of recursive. (Ben Fritz)

diff --git a/src/eval.c b/src/eval.c
--- a/src/eval.c
+++ b/src/eval.c
@@ -93,7 +93,6 @@ typedef struct lval_S
     char_u	*ll_newkey;	/* New key for Dict in alloc. mem or NULL. */
 } lval_T;
 
-
 static char *e_letunexp	= N_("E18: Unexpected characters in :let");
 static char *e_listidx = N_("E684: list index out of range: %ld");
 static char *e_undefvar = N_("E121: Undefined variable: %s");
@@ -6811,6 +6810,7 @@ list_join(gap, l, sep, echo_style, copyI
 garbage_collect()
 {
     int		copyID;
+    int		abort = FALSE;
     buf_T	*buf;
     win_T	*wp;
     int		i;
@@ -6841,82 +6841,95 @@ garbage_collect()
      * the item is referenced elsewhere the funccal must not be freed. */
     for (fc = previous_funccal; fc != NULL; fc = fc->caller)
     {
-	set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID + 1);
-	set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID + 1);
+	abort = abort || set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID + 1,
+									NULL);
+	abort = abort || set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID + 1,
+									NULL);
     }
 
     /* script-local variables */
     for (i = 1; i <= ga_scripts.ga_len; ++i)
-	set_ref_in_ht(&SCRIPT_VARS(i), copyID);
+	abort = abort || set_ref_in_ht(&SCRIPT_VARS(i), copyID, NULL);
 
     /* buffer-local variables */
     for (buf = firstbuf; buf != NULL; buf = buf->b_next)
-	set_ref_in_item(&buf->b_bufvar.di_tv, copyID);
+	abort = abort || set_ref_in_item(&buf->b_bufvar.di_tv, copyID,
+								  NULL, NULL);
 
     /* window-local variables */
     FOR_ALL_TAB_WINDOWS(tp, wp)
-	set_ref_in_item(&wp->w_winvar.di_tv, copyID);
+	abort = abort || set_ref_in_item(&wp->w_winvar.di_tv, copyID,
+								  NULL, NULL);
 #ifdef FEAT_AUTOCMD
     if (aucmd_win != NULL)
-	set_ref_in_item(&aucmd_win->w_winvar.di_tv, copyID);
+	abort = abort || set_ref_in_item(&aucmd_win->w_winvar.di_tv, copyID,
+								  NULL, NULL);
 #endif
 
 #ifdef FEAT_WINDOWS
     /* tabpage-local variables */
     for (tp = first_tabpage; tp != NULL; tp = tp->tp_next)
-	set_ref_in_item(&tp->tp_winvar.di_tv, copyID);
+	abort = abort || set_ref_in_item(&tp->tp_winvar.di_tv, copyID,
+								  NULL, NULL);
 #endif
 
     /* global variables */
-    set_ref_in_ht(&globvarht, copyID);
+    abort = abort || set_ref_in_ht(&globvarht, copyID, NULL);
 
     /* function-local variables */
     for (fc = current_funccal; fc != NULL; fc = fc->caller)
     {
-	set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID);
-	set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID);
+	abort = abort || set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID, NULL);
+	abort = abort || set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID, NULL);
     }
 
     /* v: vars */
-    set_ref_in_ht(&vimvarht, copyID);
+    abort = abort || set_ref_in_ht(&vimvarht, copyID, NULL);
 
 #ifdef FEAT_LUA
-    set_ref_in_lua(copyID);
+    abort = abort || set_ref_in_lua(copyID);
 #endif
 
 #ifdef FEAT_PYTHON
-    set_ref_in_python(copyID);
+    abort = abort || set_ref_in_python(copyID);
 #endif
 
 #ifdef FEAT_PYTHON3
-    set_ref_in_python3(copyID);
-#endif
-
-    /*
-     * 2. Free lists and dictionaries that are not referenced.
-     */
-    did_free = free_unref_items(copyID);
-
-    /*
-     * 3. Check if any funccal can be freed now.
-     */
-    for (pfc = &previous_funccal; *pfc != NULL; )
-    {
-	if (can_free_funccal(*pfc, copyID))
-	{
-	    fc = *pfc;
-	    *pfc = fc->caller;
-	    free_funccal(fc, TRUE);
-	    did_free = TRUE;
-	    did_free_funccal = TRUE;
-	}
-	else
-	    pfc = &(*pfc)->caller;
-    }
-    if (did_free_funccal)
-	/* When a funccal was freed some more items might be garbage
-	 * collected, so run again. */
-	(void)garbage_collect();
+    abort = abort || set_ref_in_python3(copyID);
+#endif
+
+    if (!abort)
+    {
+	/*
+	 * 2. Free lists and dictionaries that are not referenced.
+	 */
+	did_free = free_unref_items(copyID);
+
+	/*
+	 * 3. Check if any funccal can be freed now.
+	 */
+	for (pfc = &previous_funccal; *pfc != NULL; )
+	{
+	    if (can_free_funccal(*pfc, copyID))
+	    {
+		fc = *pfc;
+		*pfc = fc->caller;
+		free_funccal(fc, TRUE);
+		did_free = TRUE;
+		did_free_funccal = TRUE;
+	    }
+	    else
+		pfc = &(*pfc)->caller;
+	}
+	if (did_free_funccal)
+	    /* When a funccal was freed some more items might be garbage
+	     * collected, so run again. */
+	    (void)garbage_collect();
+    }
+    else if (p_verbose > 0)
+    {
+	verb_msg((char_u *)_("Not enough memory to set references, garbage collection aborted!"));
+    }
 
     return did_free;
 }
@@ -6976,48 +6989,112 @@ free_unref_items(copyID)
 
 /*
  * Mark all lists and dicts referenced through hashtab "ht" with "copyID".
- */
-    void
-set_ref_in_ht(ht, copyID)
-    hashtab_T	*ht;
-    int		copyID;
+ * "list_stack" is used to add lists to be marked.  Can be NULL.
+ *
+ * Returns TRUE if setting references failed somehow.
+ */
+    int
+set_ref_in_ht(ht, copyID, list_stack)
+    hashtab_T	    *ht;
+    int		    copyID;
+    list_stack_T    **list_stack;
 {
     int		todo;
+    int		abort = FALSE;
     hashitem_T	*hi;
-
-    todo = (int)ht->ht_used;
-    for (hi = ht->ht_array; todo > 0; ++hi)
-	if (!HASHITEM_EMPTY(hi))
-	{
-	    --todo;
-	    set_ref_in_item(&HI2DI(hi)->di_tv, copyID);
-	}
+    hashtab_T	*cur_ht;
+    ht_stack_T	*ht_stack = NULL;
+    ht_stack_T	*tempitem;
+
+    cur_ht = ht;
+    for (;;)
+    {
+	if (!abort)
+	{
+	    /* Mark each item in the hashtab.  If the item contains a hashtab
+	     * it is added to ht_stack, if it contains a list it is added to
+	     * list_stack. */
+	    todo = (int)cur_ht->ht_used;
+	    for (hi = cur_ht->ht_array; todo > 0; ++hi)
+		if (!HASHITEM_EMPTY(hi))
+		{
+		    --todo;
+		    abort = abort || set_ref_in_item(&HI2DI(hi)->di_tv, copyID,
+						       &ht_stack, list_stack);
+		}
+	}
+
+	if (ht_stack == NULL)
+	    break;
+
+	/* take an item from the stack */
+	cur_ht = ht_stack->ht;
+	tempitem = ht_stack;
+	ht_stack = ht_stack->prev;
+	free(tempitem);
+    }
+
+    return abort;
 }
 
 /*
  * Mark all lists and dicts referenced through list "l" with "copyID".
- */
-    void
-set_ref_in_list(l, copyID)
+ * "ht_stack" is used to add hashtabs to be marked.  Can be NULL.
+ *
+ * Returns TRUE if setting references failed somehow.
+ */
+    int
+set_ref_in_list(l, copyID, ht_stack)
     list_T	*l;
     int		copyID;
-{
-    listitem_T *li;
-
-    for (li = l->lv_first; li != NULL; li = li->li_next)
-	set_ref_in_item(&li->li_tv, copyID);
+    ht_stack_T	**ht_stack;
+{
+    listitem_T	 *li;
+    int		 abort = FALSE;
+    list_T	 *cur_l;
+    list_stack_T *list_stack = NULL;
+    list_stack_T *tempitem;
+
+    cur_l = l;
+    for (;;)
+    {
+	if (!abort)
+	    /* Mark each item in the list.  If the item contains a hashtab
+	     * it is added to ht_stack, if it contains a list it is added to
+	     * list_stack. */
+	    for (li = cur_l->lv_first; !abort && li != NULL; li = li->li_next)
+		abort = abort || set_ref_in_item(&li->li_tv, copyID,
+						       ht_stack, &list_stack);
+	if (list_stack == NULL)
+	    break;
+
+	/* take an item from the stack */
+	cur_l = list_stack->list;
+	tempitem = list_stack;
+	list_stack = list_stack->prev;
+	free(tempitem);
+    }
+
+    return abort;
 }
 
 /*
  * Mark all lists and dicts referenced through typval "tv" with "copyID".
- */
-    void
-set_ref_in_item(tv, copyID)
-    typval_T	*tv;
-    int		copyID;
+ * "list_stack" is used to add lists to be marked.  Can be NULL.
+ * "ht_stack" is used to add hashtabs to be marked.  Can be NULL.
+ *
+ * Returns TRUE if setting references failed somehow.
+ */
+    int
+set_ref_in_item(tv, copyID, ht_stack, list_stack)
+    typval_T	    *tv;
+    int		    copyID;
+    ht_stack_T	    **ht_stack;
+    list_stack_T    **list_stack;
 {
     dict_T	*dd;
     list_T	*ll;
+    int		abort = FALSE;
 
     switch (tv->v_type)
     {
@@ -7027,7 +7104,23 @@ set_ref_in_item(tv, copyID)
 	    {
 		/* Didn't see this dict yet. */
 		dd->dv_copyID = copyID;
-		set_ref_in_ht(&dd->dv_hashtab, copyID);
+		if (ht_stack == NULL)
+		{
+		    abort = set_ref_in_ht(&dd->dv_hashtab, copyID, list_stack);
+		}
+		else
+		{
+		    ht_stack_T *newitem = (ht_stack_T*)malloc(
+							  sizeof(ht_stack_T));
+		    if (newitem == NULL)
+			abort = TRUE;
+		    else
+		    {
+			newitem->ht = &dd->dv_hashtab;
+			newitem->prev = *ht_stack;
+			*ht_stack = newitem;
+		    }
+		}
 	    }
 	    break;
 
@@ -7037,11 +7130,27 @@ set_ref_in_item(tv, copyID)
 	    {
 		/* Didn't see this list yet. */
 		ll->lv_copyID = copyID;
-		set_ref_in_list(ll, copyID);
-	    }
-	    break;
-    }
-    return;
+		if (list_stack == NULL)
+		{
+		    abort = set_ref_in_list(ll, copyID, ht_stack);
+		}
+		else
+		{
+		    list_stack_T *newitem = (list_stack_T*)malloc(
+							sizeof(list_stack_T));
+		    if (newitem == NULL)
+			abort = TRUE;
+		    else
+		    {
+			newitem->list = ll;
+			newitem->prev = *list_stack;
+			*list_stack = newitem;
+		    }
+		}
+	    }
+	    break;
+    }
+    return abort;
 }
 
 /*
diff --git a/src/if_lua.c b/src/if_lua.c
--- a/src/if_lua.c
+++ b/src/if_lua.c
@@ -1523,12 +1523,14 @@ luaV_luaeval (lua_State *L)
     static int
 luaV_setref (lua_State *L)
 {
-    int copyID = lua_tointeger(L, 1);
-    typval_T tv;
+    int		copyID = lua_tointeger(L, 1);
+    int		abort = FALSE;
+    typval_T	tv;
+
     luaV_getfield(L, LUAVIM_LIST);
     luaV_getfield(L, LUAVIM_DICT);
     lua_pushnil(L);
-    while (lua_next(L, lua_upvalueindex(1)) != 0) /* traverse cache table */
+    while (!abort && lua_next(L, lua_upvalueindex(1)) != 0) /* traverse cache table */
     {
 	lua_getmetatable(L, -1);
 	if (lua_rawequal(L, -1, 2)) /* list? */
@@ -1542,9 +1544,9 @@ luaV_setref (lua_State *L)
 	    tv.vval.v_dict = (dict_T *) lua_touserdata(L, 4); /* key */
 	}
 	lua_pop(L, 2); /* metatable and value */
-	set_ref_in_item(&tv, copyID);
+	abort = set_ref_in_item(&tv, copyID, NULL, NULL);
     }
-    return 0;
+    lua_pushinteger(L, abort);
 }
 
     static int
@@ -1770,13 +1772,23 @@ do_luaeval (char_u *str, typval_T *arg, 
     lua_call(L, 3, 0);
 }
 
-    void
+    int
 set_ref_in_lua (int copyID)
 {
-    if (!lua_isopen()) return;
-    luaV_getfield(L, LUAVIM_SETREF);
-    lua_pushinteger(L, copyID);
-    lua_call(L, 1, 0);
+    int aborted = 0;
+
+    if (lua_isopen())
+    {
+	luaV_getfield(L, LUAVIM_SETREF);
+	/* call the function with 1 arg, getting 1 result back */
+	lua_pushinteger(L, copyID);
+	lua_call(L, 1, 1);
+	/* get the result */
+	aborted = lua_tointeger(L, -1);
+	/* pop result off the stack */
+	lua_pop(L, 1);
+    }
+    return aborted;
 }
 
 #endif
diff --git a/src/if_py_both.h b/src/if_py_both.h
--- a/src/if_py_both.h
+++ b/src/if_py_both.h
@@ -5502,34 +5502,41 @@ run_eval(const char *cmd, typval_T *rett
     PyErr_Clear();
 }
 
-    static void
+    static int
 set_ref_in_py(const int copyID)
 {
     pylinkedlist_T	*cur;
     dict_T	*dd;
     list_T	*ll;
+    int		abort = FALSE;
 
     if (lastdict != NULL)
-	for(cur = lastdict ; cur != NULL ; cur = cur->pll_prev)
+    {
+	for(cur = lastdict ; !abort && cur != NULL ; cur = cur->pll_prev)
 	{
 	    dd = ((DictionaryObject *) (cur->pll_obj))->dict;
 	    if (dd->dv_copyID != copyID)
 	    {
 		dd->dv_copyID = copyID;
-		set_ref_in_ht(&dd->dv_hashtab, copyID);
+		abort = abort || set_ref_in_ht(&dd->dv_hashtab, copyID, NULL);
 	    }
 	}
+    }
 
     if (lastlist != NULL)
-	for(cur = lastlist ; cur != NULL ; cur = cur->pll_prev)
+    {
+	for(cur = lastlist ; !abort && cur != NULL ; cur = cur->pll_prev)
 	{
 	    ll = ((ListObject *) (cur->pll_obj))->list;
 	    if (ll->lv_copyID != copyID)
 	    {
 		ll->lv_copyID = copyID;
-		set_ref_in_list(ll, copyID);
+		abort = abort || set_ref_in_list(ll, copyID, NULL);
 	    }
 	}
+    }
+
+    return abort;
 }
 
     static int
diff --git a/src/if_python.c b/src/if_python.c
--- a/src/if_python.c
+++ b/src/if_python.c
@@ -1567,8 +1567,8 @@ Py_GetProgramName(void)
 }
 #endif /* Python 1.4 */
 
-    void
+    int
 set_ref_in_python (int copyID)
 {
-    set_ref_in_py(copyID);
+    return set_ref_in_py(copyID);
 }
diff --git a/src/if_python3.c b/src/if_python3.c
--- a/src/if_python3.c
+++ b/src/if_python3.c
@@ -1649,8 +1649,8 @@ do_py3eval (char_u *str, typval_T *rettv
     }
 }
 
-    void
+    int
 set_ref_in_python3 (int copyID)
 {
-    set_ref_in_py(copyID);
+    int set_ref_in_py(copyID);
 }
diff --git a/src/proto/eval.pro b/src/proto/eval.pro
--- a/src/proto/eval.pro
+++ b/src/proto/eval.pro
@@ -62,9 +62,9 @@ int list_insert_tv __ARGS((list_T *l, ty
 void list_insert __ARGS((list_T *l, listitem_T *ni, listitem_T *item));
 void vimlist_remove __ARGS((list_T *l, listitem_T *item, listitem_T *item2));
 int garbage_collect __ARGS((void));
-void set_ref_in_ht __ARGS((hashtab_T *ht, int copyID));
-void set_ref_in_list __ARGS((list_T *l, int copyID));
-void set_ref_in_item __ARGS((typval_T *tv, int copyID));
+int set_ref_in_ht __ARGS((hashtab_T *ht, int copyID, list_stack_T **list_stack));
+int set_ref_in_list __ARGS((list_T *l, int copyID, ht_stack_T **ht_stack));
+int set_ref_in_item __ARGS((typval_T *tv, int copyID, ht_stack_T **ht_stack, list_stack_T **list_stack));
 dict_T *dict_alloc __ARGS((void));
 void dict_unref __ARGS((dict_T *d));
 void dict_free __ARGS((dict_T *d, int recurse));
diff --git a/src/proto/if_lua.pro b/src/proto/if_lua.pro
--- a/src/proto/if_lua.pro
+++ b/src/proto/if_lua.pro
@@ -7,5 +7,5 @@ void ex_luafile __ARGS((exarg_T *eap));
 void lua_buffer_free __ARGS((buf_T *buf));
 void lua_window_free __ARGS((win_T *win));
 void do_luaeval __ARGS((char_u *str, typval_T *arg, typval_T *rettv));
-void set_ref_in_lua __ARGS((int copyID));
+int set_ref_in_lua __ARGS((int copyID));
 /* vim: set ft=c : */
diff --git a/src/proto/if_python.pro b/src/proto/if_python.pro
--- a/src/proto/if_python.pro
+++ b/src/proto/if_python.pro
@@ -9,5 +9,5 @@ void python_buffer_free __ARGS((buf_T *b
 void python_window_free __ARGS((win_T *win));
 void python_tabpage_free __ARGS((tabpage_T *tab));
 void do_pyeval __ARGS((char_u *str, typval_T *rettv));
-void set_ref_in_python __ARGS((int copyID));
+int set_ref_in_python __ARGS((int copyID));
 /* vim: set ft=c : */
diff --git a/src/proto/if_python3.pro b/src/proto/if_python3.pro
--- a/src/proto/if_python3.pro
+++ b/src/proto/if_python3.pro
@@ -9,5 +9,5 @@ void python3_buffer_free __ARGS((buf_T *
 void python3_window_free __ARGS((win_T *win));
 void python3_tabpage_free __ARGS((tabpage_T *tab));
 void do_py3eval __ARGS((char_u *str, typval_T *rettv));
-void set_ref_in_python3 __ARGS((int copyID));
+int set_ref_in_python3 __ARGS((int copyID));
 /* vim: set ft=c : */
diff --git a/src/structs.h b/src/structs.h
--- a/src/structs.h
+++ b/src/structs.h
@@ -1223,6 +1223,20 @@ struct dictvar_S
     dict_T	*dv_used_prev;	/* previous dict in used dicts list */
 };
 
+/* structure used for explicit stack while garbage collecting hash tables */
+typedef struct ht_stack_S
+{
+    hashtab_T		*ht;
+    struct ht_stack_S	*prev;
+} ht_stack_T;
+
+/* structure used for explicit stack while garbage collecting lists */
+typedef struct list_stack_S
+{
+    list_T		*list;
+    struct list_stack_S	*prev;
+} list_stack_T;
+
 /* values for b_syn_spell: what to do with toplevel text */
 #define SYNSPL_DEFAULT	0	/* spell check if @Spell not defined */
 #define SYNSPL_TOP	1	/* spell check toplevel text */
diff --git a/src/version.c b/src/version.c
--- a/src/version.c
+++ b/src/version.c
@@ -742,6 +742,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    609,
+/**/
     608,
 /**/
     607,