1 To: vim_dev@googlegroups.com
4 From: Bram Moolenaar <Bram@moolenaar.net>
6 Content-Type: text/plain; charset=UTF-8
7 Content-Transfer-Encoding: 8bit
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
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
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));
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));
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)
53 /* Compare two Lists for being equal or unequal. */
54 ! n1 = list_equal(rettv->vval.v_list, var2.vval.v_list,
56 if (type == TYPE_NEQUAL)
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)
71 /* Compare two Dictionaries for being equal or unequal. */
72 ! n1 = dict_equal(rettv->vval.v_dict, var2.vval.v_dict,
74 if (type == TYPE_NEQUAL)
79 * Return TRUE when two lists have exactly the same values.
82 ! list_equal(l1, l2, ic)
85 int ic; /* ignore case for strings */
87 listitem_T *item1, *item2;
90 * Return TRUE when two lists have exactly the same values.
93 ! list_equal(l1, l2, ic, recursive)
96 int ic; /* ignore case for strings */
97 + int recursive; /* TRUE when used recursively */
99 listitem_T *item1, *item2;
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))
108 return item1 == NULL && item2 == NULL;
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))
116 return item1 == NULL && item2 == NULL;
120 * Return TRUE when two dictionaries have exactly the same key/values.
123 ! dict_equal(d1, d2, ic)
126 int ic; /* ignore case for strings */
131 * Return TRUE when two dictionaries have exactly the same key/values.
134 ! dict_equal(d1, d2, ic, recursive)
137 int ic; /* ignore case for strings */
138 + int recursive; /* TRUE when used recursively */
144 item2 = dict_find(d2, hi->hi_key, -1);
147 ! if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic))
152 item2 = dict_find(d2, hi->hi_key, -1);
155 ! if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic, recursive))
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.
170 ! tv_equal(tv1, tv2, ic)
173 ! int ic; /* ignore case */
175 char_u buf1[NUMBUFLEN], buf2[NUMBUFLEN];
177 ! static int recursive = 0; /* cach recursive loops */
180 if (tv1->v_type != tv2->v_type)
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)
191 ! r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic);
197 ! r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic);
206 + static int tv_equal_recurse_limit;
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.
214 ! tv_equal(tv1, tv2, ic, recursive)
217 ! int ic; /* ignore case */
218 ! int recursive; /* TRUE when used recursively */
220 char_u buf1[NUMBUFLEN], buf2[NUMBUFLEN];
222 ! static int recursive_cnt = 0; /* catch recursive loops */
225 if (tv1->v_type != tv2->v_type)
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. */
235 ! tv_equal_recurse_limit = 1000;
236 ! if (recursive_cnt >= tv_equal_recurse_limit)
238 ! --tv_equal_recurse_limit;
246 ! r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic, TRUE);
252 ! r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic, TRUE);
261 for ( ; li != NULL; li = li->li_next)
262 ! if (tv_equal(&li->li_tv, &argvars[1], ic))
269 for ( ; li != NULL; li = li->li_next)
270 ! if (tv_equal(&li->li_tv, &argvars[1], ic, FALSE))
276 if (!HASHITEM_EMPTY(hi))
279 ! if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic))
284 if (!HASHITEM_EMPTY(hi))
287 ! if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic, FALSE))
295 for ( ; item != NULL; item = item->li_next, ++idx)
296 ! if (tv_equal(&item->li_tv, &argvars[1], ic))
298 rettv->vval.v_number = idx;
303 for ( ; item != NULL; item = item->li_next, ++idx)
304 ! if (tv_equal(&item->li_tv, &argvars[1], ic, FALSE))
306 rettv->vval.v_number = idx;
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
314 :$put =(l != deepcopy(l))
315 :$put =(d != deepcopy(d))
317 + :" compare complex recursively linked list and dict
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)
328 :call Test(1, 2, [3, 4], {5: 6}) " This may take a while
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
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
346 { /* Add new patch number below this line */
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]
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 ///