vim: src/eval.c comparison

comparison src/eval.c @ 6565:38add5a3d617 v7.4.609

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)

author	Bram Moolenaar <bram@vim.org>
date	Tue, 03 Feb 2015 12:55:18 +0100
parents	2561531decf1
children	7092ec5d5ef1

comparison

equal deleted inserted replaced

-:84171683fd66
+:38add5a3d617
 int		ll_empty2;	/* Second index is empty: [i:] */
 dict_T	*ll_dict;	/* The Dictionary or NULL */
 dictitem_T	*ll_di;		/* The dictitem or NULL */
 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");
 static char *e_missbrac = N_("E111: Missing ']'");
 */
 int
 garbage_collect()
 {
 int		copyID;
+int		abort = FALSE;
 buf_T	*buf;
 win_T	*wp;
 int		i;
 funccall_T	*fc, **pfc;
 int		did_free;
 /* Don't free variables in the previous_funccal list unless they are only
 * referenced through previous_funccal.  This must be first, because if
 * 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);
+	abort = abort || set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID + 1,
-	set_ref_in_ht(&fc->l_avars.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);
+	abort = abort || set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID, NULL);
-	set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID);
+	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);
+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);
+	 * 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; )
+	 * 3. Check if any funccal can be freed now.
-{
+	 */
-	if (can_free_funccal(*pfc, copyID))
+	for (pfc = &previous_funccal; *pfc != NULL; )
 	{
-	    fc = *pfc;
+	    if (can_free_funccal(*pfc, copyID))
-	    *pfc = fc->caller;
+	    {
-	    free_funccal(fc, TRUE);
+		fc = *pfc;
-	    did_free = TRUE;
+		*pfc = fc->caller;
-	    did_free_funccal = TRUE;
+		free_funccal(fc, TRUE);
-	}
+		did_free = TRUE;
-	else
+		did_free_funccal = TRUE;
-	    pfc = &(*pfc)->caller;
+	    }
-}
+	    else
-if (did_free_funccal)
+		pfc = &(*pfc)->caller;
-	/* When a funccal was freed some more items might be garbage
+	}
-	 * collected, so run again. */
+	if (did_free_funccal)
-	(void)garbage_collect();
+	    /* 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;
 }
 /*
 return did_free;
 }
 /*
 * Mark all lists and dicts referenced through hashtab "ht" with "copyID".
-*/
+* "list_stack" is used to add lists to be marked.  Can be NULL.
-void
+*
-set_ref_in_ht(ht, copyID)
+* Returns TRUE if setting references failed somehow.
-hashtab_T	*ht;
+*/
-int		copyID;
+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;
+hashtab_T	*cur_ht;
-todo = (int)ht->ht_used;
+ht_stack_T	*ht_stack = NULL;
-for (hi = ht->ht_array; todo > 0; ++hi)
+ht_stack_T	*tempitem;
-	if (!HASHITEM_EMPTY(hi))
-	{
+cur_ht = ht;
-	    --todo;
+for (;;)
-	    set_ref_in_item(&HI2DI(hi)->di_tv, copyID);
+{
-	}
+	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".
-*/
+* "ht_stack" is used to add hashtabs to be marked.  Can be NULL.
-void
+*
-set_ref_in_list(l, copyID)
+* Returns TRUE if setting references failed somehow.
+*/
+int
+set_ref_in_list(l, copyID, ht_stack)
 list_T	*l;
 int		copyID;
-{
+ht_stack_T	**ht_stack;
-listitem_T *li;
+{
+listitem_T	 *li;
-for (li = l->lv_first; li != NULL; li = li->li_next)
+int		 abort = FALSE;
-	set_ref_in_item(&li->li_tv, copyID);
+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".
-*/
+* "list_stack" is used to add lists to be marked.  Can be NULL.
-void
+* "ht_stack" is used to add hashtabs to be marked.  Can be NULL.
-set_ref_in_item(tv, copyID)
+*
-typval_T	*tv;
+* Returns TRUE if setting references failed somehow.
-int		copyID;
+*/
+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)
 {
 	case VAR_DICT:
 	    dd = tv->vval.v_dict;
 	    if (dd != NULL && dd->dv_copyID != 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;
 	case VAR_LIST:
 	    ll = tv->vval.v_list;
 	    if (ll != NULL && ll->lv_copyID != copyID)
 	    {
 		/* Didn't see this list yet. */
 		ll->lv_copyID = copyID;
-		set_ref_in_list(ll, copyID);
+		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;
+return abort;
 }
 /*
 * Allocate an empty header for a dictionary.
 */

Mercurial > vim

comparison src/eval.c @ 6565:38add5a3d617 v7.4.609