]>
Commit | Line | Data |
---|---|---|
17e7d110 SS |
1 | To: vim_dev@googlegroups.com |
2 | Subject: Patch 7.3.055 | |
3 | Fcc: outbox | |
4 | From: Bram Moolenaar <Bram@moolenaar.net> | |
5 | Mime-Version: 1.0 | |
6 | Content-Type: text/plain; charset=UTF-8 | |
7 | Content-Transfer-Encoding: 8bit | |
8 | ------------ | |
9 | ||
10 | Patch 7.3.055 | |
11 | Problem: Recursively nested lists and dictionaries cause a near-endless | |
12 | loop when comparing them with a copy. (ZyX) | |
13 | Solution: Limit recursiveness in a way that non-recursive structures can | |
14 | still be nested very deep. | |
15 | Files: src/eval.c, src/testdir/test55.in, src/testdir/test55.ok | |
16 | ||
17 | ||
18 | *** ../vim-7.3.054/src/eval.c 2010-10-20 21:22:17.000000000 +0200 | |
19 | --- src/eval.c 2010-11-10 20:02:57.000000000 +0100 | |
20 | *************** | |
21 | *** 434,442 **** | |
22 | static void listitem_free __ARGS((listitem_T *item)); | |
23 | static void listitem_remove __ARGS((list_T *l, listitem_T *item)); | |
24 | static long list_len __ARGS((list_T *l)); | |
25 | ! static int list_equal __ARGS((list_T *l1, list_T *l2, int ic)); | |
26 | ! static int dict_equal __ARGS((dict_T *d1, dict_T *d2, int ic)); | |
27 | ! static int tv_equal __ARGS((typval_T *tv1, typval_T *tv2, int ic)); | |
28 | static listitem_T *list_find __ARGS((list_T *l, long n)); | |
29 | static long list_find_nr __ARGS((list_T *l, long idx, int *errorp)); | |
30 | static long list_idx_of_item __ARGS((list_T *l, listitem_T *item)); | |
31 | --- 434,442 ---- | |
32 | static void listitem_free __ARGS((listitem_T *item)); | |
33 | static void listitem_remove __ARGS((list_T *l, listitem_T *item)); | |
34 | static long list_len __ARGS((list_T *l)); | |
35 | ! static int list_equal __ARGS((list_T *l1, list_T *l2, int ic, int recursive)); | |
36 | ! static int dict_equal __ARGS((dict_T *d1, dict_T *d2, int ic, int recursive)); | |
37 | ! static int tv_equal __ARGS((typval_T *tv1, typval_T *tv2, int ic, int recursive)); | |
38 | static listitem_T *list_find __ARGS((list_T *l, long n)); | |
39 | static long list_find_nr __ARGS((list_T *l, long idx, int *errorp)); | |
40 | static long list_idx_of_item __ARGS((list_T *l, listitem_T *item)); | |
41 | *************** | |
42 | *** 4350,4356 **** | |
43 | else | |
44 | { | |
45 | /* Compare two Lists for being equal or unequal. */ | |
46 | ! n1 = list_equal(rettv->vval.v_list, var2.vval.v_list, ic); | |
47 | if (type == TYPE_NEQUAL) | |
48 | n1 = !n1; | |
49 | } | |
50 | --- 4350,4357 ---- | |
51 | else | |
52 | { | |
53 | /* Compare two Lists for being equal or unequal. */ | |
54 | ! n1 = list_equal(rettv->vval.v_list, var2.vval.v_list, | |
55 | ! ic, FALSE); | |
56 | if (type == TYPE_NEQUAL) | |
57 | n1 = !n1; | |
58 | } | |
59 | *************** | |
60 | *** 4379,4385 **** | |
61 | else | |
62 | { | |
63 | /* Compare two Dictionaries for being equal or unequal. */ | |
64 | ! n1 = dict_equal(rettv->vval.v_dict, var2.vval.v_dict, ic); | |
65 | if (type == TYPE_NEQUAL) | |
66 | n1 = !n1; | |
67 | } | |
68 | --- 4380,4387 ---- | |
69 | else | |
70 | { | |
71 | /* Compare two Dictionaries for being equal or unequal. */ | |
72 | ! n1 = dict_equal(rettv->vval.v_dict, var2.vval.v_dict, | |
73 | ! ic, FALSE); | |
74 | if (type == TYPE_NEQUAL) | |
75 | n1 = !n1; | |
76 | } | |
77 | *************** | |
78 | *** 5914,5923 **** | |
79 | * Return TRUE when two lists have exactly the same values. | |
80 | */ | |
81 | static int | |
82 | ! list_equal(l1, l2, ic) | |
83 | list_T *l1; | |
84 | list_T *l2; | |
85 | int ic; /* ignore case for strings */ | |
86 | { | |
87 | listitem_T *item1, *item2; | |
88 | ||
89 | --- 5916,5926 ---- | |
90 | * Return TRUE when two lists have exactly the same values. | |
91 | */ | |
92 | static int | |
93 | ! list_equal(l1, l2, ic, recursive) | |
94 | list_T *l1; | |
95 | list_T *l2; | |
96 | int ic; /* ignore case for strings */ | |
97 | + int recursive; /* TRUE when used recursively */ | |
98 | { | |
99 | listitem_T *item1, *item2; | |
100 | ||
101 | *************** | |
102 | *** 5931,5937 **** | |
103 | for (item1 = l1->lv_first, item2 = l2->lv_first; | |
104 | item1 != NULL && item2 != NULL; | |
105 | item1 = item1->li_next, item2 = item2->li_next) | |
106 | ! if (!tv_equal(&item1->li_tv, &item2->li_tv, ic)) | |
107 | return FALSE; | |
108 | return item1 == NULL && item2 == NULL; | |
109 | } | |
110 | --- 5934,5940 ---- | |
111 | for (item1 = l1->lv_first, item2 = l2->lv_first; | |
112 | item1 != NULL && item2 != NULL; | |
113 | item1 = item1->li_next, item2 = item2->li_next) | |
114 | ! if (!tv_equal(&item1->li_tv, &item2->li_tv, ic, recursive)) | |
115 | return FALSE; | |
116 | return item1 == NULL && item2 == NULL; | |
117 | } | |
118 | *************** | |
119 | *** 5953,5962 **** | |
120 | * Return TRUE when two dictionaries have exactly the same key/values. | |
121 | */ | |
122 | static int | |
123 | ! dict_equal(d1, d2, ic) | |
124 | dict_T *d1; | |
125 | dict_T *d2; | |
126 | int ic; /* ignore case for strings */ | |
127 | { | |
128 | hashitem_T *hi; | |
129 | dictitem_T *item2; | |
130 | --- 5956,5966 ---- | |
131 | * Return TRUE when two dictionaries have exactly the same key/values. | |
132 | */ | |
133 | static int | |
134 | ! dict_equal(d1, d2, ic, recursive) | |
135 | dict_T *d1; | |
136 | dict_T *d2; | |
137 | int ic; /* ignore case for strings */ | |
138 | + int recursive; /* TRUE when used recursively */ | |
139 | { | |
140 | hashitem_T *hi; | |
141 | dictitem_T *item2; | |
142 | *************** | |
143 | *** 5977,5983 **** | |
144 | item2 = dict_find(d2, hi->hi_key, -1); | |
145 | if (item2 == NULL) | |
146 | return FALSE; | |
147 | ! if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic)) | |
148 | return FALSE; | |
149 | --todo; | |
150 | } | |
151 | --- 5981,5987 ---- | |
152 | item2 = dict_find(d2, hi->hi_key, -1); | |
153 | if (item2 == NULL) | |
154 | return FALSE; | |
155 | ! if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic, recursive)) | |
156 | return FALSE; | |
157 | --todo; | |
158 | } | |
159 | *************** | |
160 | *** 5985,6025 **** | |
161 | return TRUE; | |
162 | } | |
163 | ||
164 | /* | |
165 | * Return TRUE if "tv1" and "tv2" have the same value. | |
166 | * Compares the items just like "==" would compare them, but strings and | |
167 | * numbers are different. Floats and numbers are also different. | |
168 | */ | |
169 | static int | |
170 | ! tv_equal(tv1, tv2, ic) | |
171 | typval_T *tv1; | |
172 | typval_T *tv2; | |
173 | ! int ic; /* ignore case */ | |
174 | { | |
175 | char_u buf1[NUMBUFLEN], buf2[NUMBUFLEN]; | |
176 | char_u *s1, *s2; | |
177 | ! static int recursive = 0; /* cach recursive loops */ | |
178 | int r; | |
179 | ||
180 | if (tv1->v_type != tv2->v_type) | |
181 | return FALSE; | |
182 | /* Catch lists and dicts that have an endless loop by limiting | |
183 | ! * recursiveness to 1000. We guess they are equal then. */ | |
184 | ! if (recursive >= 1000) | |
185 | return TRUE; | |
186 | ||
187 | switch (tv1->v_type) | |
188 | { | |
189 | case VAR_LIST: | |
190 | ! ++recursive; | |
191 | ! r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic); | |
192 | ! --recursive; | |
193 | return r; | |
194 | ||
195 | case VAR_DICT: | |
196 | ! ++recursive; | |
197 | ! r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic); | |
198 | ! --recursive; | |
199 | return r; | |
200 | ||
201 | case VAR_FUNC: | |
202 | --- 5989,6042 ---- | |
203 | return TRUE; | |
204 | } | |
205 | ||
206 | + static int tv_equal_recurse_limit; | |
207 | + | |
208 | /* | |
209 | * Return TRUE if "tv1" and "tv2" have the same value. | |
210 | * Compares the items just like "==" would compare them, but strings and | |
211 | * numbers are different. Floats and numbers are also different. | |
212 | */ | |
213 | static int | |
214 | ! tv_equal(tv1, tv2, ic, recursive) | |
215 | typval_T *tv1; | |
216 | typval_T *tv2; | |
217 | ! int ic; /* ignore case */ | |
218 | ! int recursive; /* TRUE when used recursively */ | |
219 | { | |
220 | char_u buf1[NUMBUFLEN], buf2[NUMBUFLEN]; | |
221 | char_u *s1, *s2; | |
222 | ! static int recursive_cnt = 0; /* catch recursive loops */ | |
223 | int r; | |
224 | ||
225 | if (tv1->v_type != tv2->v_type) | |
226 | return FALSE; | |
227 | + | |
228 | /* Catch lists and dicts that have an endless loop by limiting | |
229 | ! * recursiveness to a limit. We guess they are equal then. | |
230 | ! * A fixed limit has the problem of still taking an awful long time. | |
231 | ! * Reduce the limit every time running into it. That should work fine for | |
232 | ! * deeply linked structures that are not recursively linked and catch | |
233 | ! * recursiveness quickly. */ | |
234 | ! if (!recursive) | |
235 | ! tv_equal_recurse_limit = 1000; | |
236 | ! if (recursive_cnt >= tv_equal_recurse_limit) | |
237 | ! { | |
238 | ! --tv_equal_recurse_limit; | |
239 | return TRUE; | |
240 | + } | |
241 | ||
242 | switch (tv1->v_type) | |
243 | { | |
244 | case VAR_LIST: | |
245 | ! ++recursive_cnt; | |
246 | ! r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic, TRUE); | |
247 | ! --recursive_cnt; | |
248 | return r; | |
249 | ||
250 | case VAR_DICT: | |
251 | ! ++recursive_cnt; | |
252 | ! r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic, TRUE); | |
253 | ! --recursive_cnt; | |
254 | return r; | |
255 | ||
256 | case VAR_FUNC: | |
257 | *************** | |
258 | *** 9391,9397 **** | |
259 | } | |
260 | ||
261 | for ( ; li != NULL; li = li->li_next) | |
262 | ! if (tv_equal(&li->li_tv, &argvars[1], ic)) | |
263 | ++n; | |
264 | } | |
265 | } | |
266 | --- 9408,9414 ---- | |
267 | } | |
268 | ||
269 | for ( ; li != NULL; li = li->li_next) | |
270 | ! if (tv_equal(&li->li_tv, &argvars[1], ic, FALSE)) | |
271 | ++n; | |
272 | } | |
273 | } | |
274 | *************** | |
275 | *** 9418,9424 **** | |
276 | if (!HASHITEM_EMPTY(hi)) | |
277 | { | |
278 | --todo; | |
279 | ! if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic)) | |
280 | ++n; | |
281 | } | |
282 | } | |
283 | --- 9435,9441 ---- | |
284 | if (!HASHITEM_EMPTY(hi)) | |
285 | { | |
286 | --todo; | |
287 | ! if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic, FALSE)) | |
288 | ++n; | |
289 | } | |
290 | } | |
291 | *************** | |
292 | *** 12574,12580 **** | |
293 | } | |
294 | ||
295 | for ( ; item != NULL; item = item->li_next, ++idx) | |
296 | ! if (tv_equal(&item->li_tv, &argvars[1], ic)) | |
297 | { | |
298 | rettv->vval.v_number = idx; | |
299 | break; | |
300 | --- 12591,12597 ---- | |
301 | } | |
302 | ||
303 | for ( ; item != NULL; item = item->li_next, ++idx) | |
304 | ! if (tv_equal(&item->li_tv, &argvars[1], ic, FALSE)) | |
305 | { | |
306 | rettv->vval.v_number = idx; | |
307 | break; | |
308 | *** ../vim-7.3.054/src/testdir/test55.in 2010-08-15 21:57:29.000000000 +0200 | |
309 | --- src/testdir/test55.in 2010-11-10 20:15:27.000000000 +0100 | |
310 | *************** | |
311 | *** 342,348 **** | |
312 | --- 342,359 ---- | |
313 | :$put =(d == d) | |
314 | :$put =(l != deepcopy(l)) | |
315 | :$put =(d != deepcopy(d)) | |
316 | + :" | |
317 | + :" compare complex recursively linked list and dict | |
318 | + :let l = [] | |
319 | + :call add(l, l) | |
320 | + :let dict4 = {"l": l} | |
321 | + :call add(dict4.l, dict4) | |
322 | + :let lcopy = deepcopy(l) | |
323 | + :let dict4copy = deepcopy(dict4) | |
324 | + :$put =(l == lcopy) | |
325 | + :$put =(dict4 == dict4copy) | |
326 | :endfun | |
327 | + :" | |
328 | :call Test(1, 2, [3, 4], {5: 6}) " This may take a while | |
329 | :" | |
330 | :delfunc Test | |
331 | *** ../vim-7.3.054/src/testdir/test55.ok 2010-08-15 21:57:29.000000000 +0200 | |
332 | --- src/testdir/test55.ok 2010-11-10 20:16:37.000000000 +0100 | |
333 | *************** | |
334 | *** 109,111 **** | |
335 | --- 109,113 ---- | |
336 | 1 | |
337 | 0 | |
338 | 0 | |
339 | + 1 | |
340 | + 1 | |
341 | *** ../vim-7.3.054/src/version.c 2010-11-10 18:59:50.000000000 +0100 | |
342 | --- src/version.c 2010-11-10 20:10:51.000000000 +0100 | |
343 | *************** | |
344 | *** 716,717 **** | |
345 | --- 716,719 ---- | |
346 | { /* Add new patch number below this line */ | |
347 | + /**/ | |
348 | + 55, | |
349 | /**/ | |
350 | ||
351 | -- | |
352 | A special law prohibits unmarried women from parachuting on Sunday or she | |
353 | shall risk arrest, fine, and/or jailing. | |
354 | [real standing law in Florida, United States of America] | |
355 | ||
356 | /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\ | |
357 | /// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\ | |
358 | \\\ download, build and distribute -- http://www.A-A-P.org /// | |
359 | \\\ help me help AIDS victims -- http://ICCF-Holland.org /// |