Mercurial > vim
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
6564:84171683fd66 | 6565:38add5a3d617 |
---|---|
90 int ll_empty2; /* Second index is empty: [i:] */ | 90 int ll_empty2; /* Second index is empty: [i:] */ |
91 dict_T *ll_dict; /* The Dictionary or NULL */ | 91 dict_T *ll_dict; /* The Dictionary or NULL */ |
92 dictitem_T *ll_di; /* The dictitem or NULL */ | 92 dictitem_T *ll_di; /* The dictitem or NULL */ |
93 char_u *ll_newkey; /* New key for Dict in alloc. mem or NULL. */ | 93 char_u *ll_newkey; /* New key for Dict in alloc. mem or NULL. */ |
94 } lval_T; | 94 } lval_T; |
95 | |
96 | 95 |
97 static char *e_letunexp = N_("E18: Unexpected characters in :let"); | 96 static char *e_letunexp = N_("E18: Unexpected characters in :let"); |
98 static char *e_listidx = N_("E684: list index out of range: %ld"); | 97 static char *e_listidx = N_("E684: list index out of range: %ld"); |
99 static char *e_undefvar = N_("E121: Undefined variable: %s"); | 98 static char *e_undefvar = N_("E121: Undefined variable: %s"); |
100 static char *e_missbrac = N_("E111: Missing ']'"); | 99 static char *e_missbrac = N_("E111: Missing ']'"); |
6809 */ | 6808 */ |
6810 int | 6809 int |
6811 garbage_collect() | 6810 garbage_collect() |
6812 { | 6811 { |
6813 int copyID; | 6812 int copyID; |
6813 int abort = FALSE; | |
6814 buf_T *buf; | 6814 buf_T *buf; |
6815 win_T *wp; | 6815 win_T *wp; |
6816 int i; | 6816 int i; |
6817 funccall_T *fc, **pfc; | 6817 funccall_T *fc, **pfc; |
6818 int did_free; | 6818 int did_free; |
6839 /* Don't free variables in the previous_funccal list unless they are only | 6839 /* Don't free variables in the previous_funccal list unless they are only |
6840 * referenced through previous_funccal. This must be first, because if | 6840 * referenced through previous_funccal. This must be first, because if |
6841 * the item is referenced elsewhere the funccal must not be freed. */ | 6841 * the item is referenced elsewhere the funccal must not be freed. */ |
6842 for (fc = previous_funccal; fc != NULL; fc = fc->caller) | 6842 for (fc = previous_funccal; fc != NULL; fc = fc->caller) |
6843 { | 6843 { |
6844 set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID + 1); | 6844 abort = abort || set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID + 1, |
6845 set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID + 1); | 6845 NULL); |
6846 abort = abort || set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID + 1, | |
6847 NULL); | |
6846 } | 6848 } |
6847 | 6849 |
6848 /* script-local variables */ | 6850 /* script-local variables */ |
6849 for (i = 1; i <= ga_scripts.ga_len; ++i) | 6851 for (i = 1; i <= ga_scripts.ga_len; ++i) |
6850 set_ref_in_ht(&SCRIPT_VARS(i), copyID); | 6852 abort = abort || set_ref_in_ht(&SCRIPT_VARS(i), copyID, NULL); |
6851 | 6853 |
6852 /* buffer-local variables */ | 6854 /* buffer-local variables */ |
6853 for (buf = firstbuf; buf != NULL; buf = buf->b_next) | 6855 for (buf = firstbuf; buf != NULL; buf = buf->b_next) |
6854 set_ref_in_item(&buf->b_bufvar.di_tv, copyID); | 6856 abort = abort || set_ref_in_item(&buf->b_bufvar.di_tv, copyID, |
6857 NULL, NULL); | |
6855 | 6858 |
6856 /* window-local variables */ | 6859 /* window-local variables */ |
6857 FOR_ALL_TAB_WINDOWS(tp, wp) | 6860 FOR_ALL_TAB_WINDOWS(tp, wp) |
6858 set_ref_in_item(&wp->w_winvar.di_tv, copyID); | 6861 abort = abort || set_ref_in_item(&wp->w_winvar.di_tv, copyID, |
6862 NULL, NULL); | |
6859 #ifdef FEAT_AUTOCMD | 6863 #ifdef FEAT_AUTOCMD |
6860 if (aucmd_win != NULL) | 6864 if (aucmd_win != NULL) |
6861 set_ref_in_item(&aucmd_win->w_winvar.di_tv, copyID); | 6865 abort = abort || set_ref_in_item(&aucmd_win->w_winvar.di_tv, copyID, |
6866 NULL, NULL); | |
6862 #endif | 6867 #endif |
6863 | 6868 |
6864 #ifdef FEAT_WINDOWS | 6869 #ifdef FEAT_WINDOWS |
6865 /* tabpage-local variables */ | 6870 /* tabpage-local variables */ |
6866 for (tp = first_tabpage; tp != NULL; tp = tp->tp_next) | 6871 for (tp = first_tabpage; tp != NULL; tp = tp->tp_next) |
6867 set_ref_in_item(&tp->tp_winvar.di_tv, copyID); | 6872 abort = abort || set_ref_in_item(&tp->tp_winvar.di_tv, copyID, |
6873 NULL, NULL); | |
6868 #endif | 6874 #endif |
6869 | 6875 |
6870 /* global variables */ | 6876 /* global variables */ |
6871 set_ref_in_ht(&globvarht, copyID); | 6877 abort = abort || set_ref_in_ht(&globvarht, copyID, NULL); |
6872 | 6878 |
6873 /* function-local variables */ | 6879 /* function-local variables */ |
6874 for (fc = current_funccal; fc != NULL; fc = fc->caller) | 6880 for (fc = current_funccal; fc != NULL; fc = fc->caller) |
6875 { | 6881 { |
6876 set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID); | 6882 abort = abort || set_ref_in_ht(&fc->l_vars.dv_hashtab, copyID, NULL); |
6877 set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID); | 6883 abort = abort || set_ref_in_ht(&fc->l_avars.dv_hashtab, copyID, NULL); |
6878 } | 6884 } |
6879 | 6885 |
6880 /* v: vars */ | 6886 /* v: vars */ |
6881 set_ref_in_ht(&vimvarht, copyID); | 6887 abort = abort || set_ref_in_ht(&vimvarht, copyID, NULL); |
6882 | 6888 |
6883 #ifdef FEAT_LUA | 6889 #ifdef FEAT_LUA |
6884 set_ref_in_lua(copyID); | 6890 abort = abort || set_ref_in_lua(copyID); |
6885 #endif | 6891 #endif |
6886 | 6892 |
6887 #ifdef FEAT_PYTHON | 6893 #ifdef FEAT_PYTHON |
6888 set_ref_in_python(copyID); | 6894 abort = abort || set_ref_in_python(copyID); |
6889 #endif | 6895 #endif |
6890 | 6896 |
6891 #ifdef FEAT_PYTHON3 | 6897 #ifdef FEAT_PYTHON3 |
6892 set_ref_in_python3(copyID); | 6898 abort = abort || set_ref_in_python3(copyID); |
6893 #endif | 6899 #endif |
6894 | 6900 |
6895 /* | 6901 if (!abort) |
6896 * 2. Free lists and dictionaries that are not referenced. | 6902 { |
6897 */ | 6903 /* |
6898 did_free = free_unref_items(copyID); | 6904 * 2. Free lists and dictionaries that are not referenced. |
6899 | 6905 */ |
6900 /* | 6906 did_free = free_unref_items(copyID); |
6901 * 3. Check if any funccal can be freed now. | 6907 |
6902 */ | 6908 /* |
6903 for (pfc = &previous_funccal; *pfc != NULL; ) | 6909 * 3. Check if any funccal can be freed now. |
6904 { | 6910 */ |
6905 if (can_free_funccal(*pfc, copyID)) | 6911 for (pfc = &previous_funccal; *pfc != NULL; ) |
6906 { | 6912 { |
6907 fc = *pfc; | 6913 if (can_free_funccal(*pfc, copyID)) |
6908 *pfc = fc->caller; | 6914 { |
6909 free_funccal(fc, TRUE); | 6915 fc = *pfc; |
6910 did_free = TRUE; | 6916 *pfc = fc->caller; |
6911 did_free_funccal = TRUE; | 6917 free_funccal(fc, TRUE); |
6912 } | 6918 did_free = TRUE; |
6913 else | 6919 did_free_funccal = TRUE; |
6914 pfc = &(*pfc)->caller; | 6920 } |
6915 } | 6921 else |
6916 if (did_free_funccal) | 6922 pfc = &(*pfc)->caller; |
6917 /* When a funccal was freed some more items might be garbage | 6923 } |
6918 * collected, so run again. */ | 6924 if (did_free_funccal) |
6919 (void)garbage_collect(); | 6925 /* When a funccal was freed some more items might be garbage |
6926 * collected, so run again. */ | |
6927 (void)garbage_collect(); | |
6928 } | |
6929 else if (p_verbose > 0) | |
6930 { | |
6931 verb_msg((char_u *)_("Not enough memory to set references, garbage collection aborted!")); | |
6932 } | |
6920 | 6933 |
6921 return did_free; | 6934 return did_free; |
6922 } | 6935 } |
6923 | 6936 |
6924 /* | 6937 /* |
6974 return did_free; | 6987 return did_free; |
6975 } | 6988 } |
6976 | 6989 |
6977 /* | 6990 /* |
6978 * Mark all lists and dicts referenced through hashtab "ht" with "copyID". | 6991 * Mark all lists and dicts referenced through hashtab "ht" with "copyID". |
6979 */ | 6992 * "list_stack" is used to add lists to be marked. Can be NULL. |
6980 void | 6993 * |
6981 set_ref_in_ht(ht, copyID) | 6994 * Returns TRUE if setting references failed somehow. |
6982 hashtab_T *ht; | 6995 */ |
6983 int copyID; | 6996 int |
6997 set_ref_in_ht(ht, copyID, list_stack) | |
6998 hashtab_T *ht; | |
6999 int copyID; | |
7000 list_stack_T **list_stack; | |
6984 { | 7001 { |
6985 int todo; | 7002 int todo; |
7003 int abort = FALSE; | |
6986 hashitem_T *hi; | 7004 hashitem_T *hi; |
6987 | 7005 hashtab_T *cur_ht; |
6988 todo = (int)ht->ht_used; | 7006 ht_stack_T *ht_stack = NULL; |
6989 for (hi = ht->ht_array; todo > 0; ++hi) | 7007 ht_stack_T *tempitem; |
6990 if (!HASHITEM_EMPTY(hi)) | 7008 |
6991 { | 7009 cur_ht = ht; |
6992 --todo; | 7010 for (;;) |
6993 set_ref_in_item(&HI2DI(hi)->di_tv, copyID); | 7011 { |
6994 } | 7012 if (!abort) |
7013 { | |
7014 /* Mark each item in the hashtab. If the item contains a hashtab | |
7015 * it is added to ht_stack, if it contains a list it is added to | |
7016 * list_stack. */ | |
7017 todo = (int)cur_ht->ht_used; | |
7018 for (hi = cur_ht->ht_array; todo > 0; ++hi) | |
7019 if (!HASHITEM_EMPTY(hi)) | |
7020 { | |
7021 --todo; | |
7022 abort = abort || set_ref_in_item(&HI2DI(hi)->di_tv, copyID, | |
7023 &ht_stack, list_stack); | |
7024 } | |
7025 } | |
7026 | |
7027 if (ht_stack == NULL) | |
7028 break; | |
7029 | |
7030 /* take an item from the stack */ | |
7031 cur_ht = ht_stack->ht; | |
7032 tempitem = ht_stack; | |
7033 ht_stack = ht_stack->prev; | |
7034 free(tempitem); | |
7035 } | |
7036 | |
7037 return abort; | |
6995 } | 7038 } |
6996 | 7039 |
6997 /* | 7040 /* |
6998 * Mark all lists and dicts referenced through list "l" with "copyID". | 7041 * Mark all lists and dicts referenced through list "l" with "copyID". |
6999 */ | 7042 * "ht_stack" is used to add hashtabs to be marked. Can be NULL. |
7000 void | 7043 * |
7001 set_ref_in_list(l, copyID) | 7044 * Returns TRUE if setting references failed somehow. |
7045 */ | |
7046 int | |
7047 set_ref_in_list(l, copyID, ht_stack) | |
7002 list_T *l; | 7048 list_T *l; |
7003 int copyID; | 7049 int copyID; |
7004 { | 7050 ht_stack_T **ht_stack; |
7005 listitem_T *li; | 7051 { |
7006 | 7052 listitem_T *li; |
7007 for (li = l->lv_first; li != NULL; li = li->li_next) | 7053 int abort = FALSE; |
7008 set_ref_in_item(&li->li_tv, copyID); | 7054 list_T *cur_l; |
7055 list_stack_T *list_stack = NULL; | |
7056 list_stack_T *tempitem; | |
7057 | |
7058 cur_l = l; | |
7059 for (;;) | |
7060 { | |
7061 if (!abort) | |
7062 /* Mark each item in the list. If the item contains a hashtab | |
7063 * it is added to ht_stack, if it contains a list it is added to | |
7064 * list_stack. */ | |
7065 for (li = cur_l->lv_first; !abort && li != NULL; li = li->li_next) | |
7066 abort = abort || set_ref_in_item(&li->li_tv, copyID, | |
7067 ht_stack, &list_stack); | |
7068 if (list_stack == NULL) | |
7069 break; | |
7070 | |
7071 /* take an item from the stack */ | |
7072 cur_l = list_stack->list; | |
7073 tempitem = list_stack; | |
7074 list_stack = list_stack->prev; | |
7075 free(tempitem); | |
7076 } | |
7077 | |
7078 return abort; | |
7009 } | 7079 } |
7010 | 7080 |
7011 /* | 7081 /* |
7012 * Mark all lists and dicts referenced through typval "tv" with "copyID". | 7082 * Mark all lists and dicts referenced through typval "tv" with "copyID". |
7013 */ | 7083 * "list_stack" is used to add lists to be marked. Can be NULL. |
7014 void | 7084 * "ht_stack" is used to add hashtabs to be marked. Can be NULL. |
7015 set_ref_in_item(tv, copyID) | 7085 * |
7016 typval_T *tv; | 7086 * Returns TRUE if setting references failed somehow. |
7017 int copyID; | 7087 */ |
7088 int | |
7089 set_ref_in_item(tv, copyID, ht_stack, list_stack) | |
7090 typval_T *tv; | |
7091 int copyID; | |
7092 ht_stack_T **ht_stack; | |
7093 list_stack_T **list_stack; | |
7018 { | 7094 { |
7019 dict_T *dd; | 7095 dict_T *dd; |
7020 list_T *ll; | 7096 list_T *ll; |
7097 int abort = FALSE; | |
7021 | 7098 |
7022 switch (tv->v_type) | 7099 switch (tv->v_type) |
7023 { | 7100 { |
7024 case VAR_DICT: | 7101 case VAR_DICT: |
7025 dd = tv->vval.v_dict; | 7102 dd = tv->vval.v_dict; |
7026 if (dd != NULL && dd->dv_copyID != copyID) | 7103 if (dd != NULL && dd->dv_copyID != copyID) |
7027 { | 7104 { |
7028 /* Didn't see this dict yet. */ | 7105 /* Didn't see this dict yet. */ |
7029 dd->dv_copyID = copyID; | 7106 dd->dv_copyID = copyID; |
7030 set_ref_in_ht(&dd->dv_hashtab, copyID); | 7107 if (ht_stack == NULL) |
7108 { | |
7109 abort = set_ref_in_ht(&dd->dv_hashtab, copyID, list_stack); | |
7110 } | |
7111 else | |
7112 { | |
7113 ht_stack_T *newitem = (ht_stack_T*)malloc( | |
7114 sizeof(ht_stack_T)); | |
7115 if (newitem == NULL) | |
7116 abort = TRUE; | |
7117 else | |
7118 { | |
7119 newitem->ht = &dd->dv_hashtab; | |
7120 newitem->prev = *ht_stack; | |
7121 *ht_stack = newitem; | |
7122 } | |
7123 } | |
7031 } | 7124 } |
7032 break; | 7125 break; |
7033 | 7126 |
7034 case VAR_LIST: | 7127 case VAR_LIST: |
7035 ll = tv->vval.v_list; | 7128 ll = tv->vval.v_list; |
7036 if (ll != NULL && ll->lv_copyID != copyID) | 7129 if (ll != NULL && ll->lv_copyID != copyID) |
7037 { | 7130 { |
7038 /* Didn't see this list yet. */ | 7131 /* Didn't see this list yet. */ |
7039 ll->lv_copyID = copyID; | 7132 ll->lv_copyID = copyID; |
7040 set_ref_in_list(ll, copyID); | 7133 if (list_stack == NULL) |
7134 { | |
7135 abort = set_ref_in_list(ll, copyID, ht_stack); | |
7136 } | |
7137 else | |
7138 { | |
7139 list_stack_T *newitem = (list_stack_T*)malloc( | |
7140 sizeof(list_stack_T)); | |
7141 if (newitem == NULL) | |
7142 abort = TRUE; | |
7143 else | |
7144 { | |
7145 newitem->list = ll; | |
7146 newitem->prev = *list_stack; | |
7147 *list_stack = newitem; | |
7148 } | |
7149 } | |
7041 } | 7150 } |
7042 break; | 7151 break; |
7043 } | 7152 } |
7044 return; | 7153 return abort; |
7045 } | 7154 } |
7046 | 7155 |
7047 /* | 7156 /* |
7048 * Allocate an empty header for a dictionary. | 7157 * Allocate an empty header for a dictionary. |
7049 */ | 7158 */ |