]> git.pld-linux.org Git - packages/vim.git/blame - 7.3.055
- new
[packages/vim.git] / 7.3.055
CommitLineData
5634d1d6
ER
1To: vim_dev@googlegroups.com
2Subject: Patch 7.3.055
3Fcc: outbox
4From: Bram Moolenaar <Bram@moolenaar.net>
5Mime-Version: 1.0
6Content-Type: text/plain; charset=UTF-8
7Content-Transfer-Encoding: 8bit
8------------
9
10Patch 7.3.055
11Problem: Recursively nested lists and dictionaries cause a near-endless
12 loop when comparing them with a copy. (ZyX)
13Solution: Limit recursiveness in a way that non-recursive structures can
14 still be nested very deep.
15Files: 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--
352A special law prohibits unmarried women from parachuting on Sunday or she
353shall 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 ///
This page took 0.056438 seconds and 4 git commands to generate.