To: vim_dev@googlegroups.com
Subject: Patch 7.3.055
Fcc: outbox
From: Bram Moolenaar <Bram@moolenaar.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
------------
Patch 7.3.055
Problem: Recursively nested lists and dictionaries cause a near-endless
loop when comparing them with a copy. (ZyX)
Solution: Limit recursiveness in a way that non-recursive structures can
still be nested very deep.
Files: src/eval.c, src/testdir/test55.in, src/testdir/test55.ok
*** ../vim-7.3.054/src/eval.c 2010-10-20 21:22:17.000000000 +0200
--- src/eval.c 2010-11-10 20:02:57.000000000 +0100
***************
*** 434,442 ****
static void listitem_free __ARGS((listitem_T *item));
static void listitem_remove __ARGS((list_T *l, listitem_T *item));
static long list_len __ARGS((list_T *l));
! static int list_equal __ARGS((list_T *l1, list_T *l2, int ic));
! static int dict_equal __ARGS((dict_T *d1, dict_T *d2, int ic));
! static int tv_equal __ARGS((typval_T *tv1, typval_T *tv2, int ic));
static listitem_T *list_find __ARGS((list_T *l, long n));
static long list_find_nr __ARGS((list_T *l, long idx, int *errorp));
static long list_idx_of_item __ARGS((list_T *l, listitem_T *item));
--- 434,442 ----
static void listitem_free __ARGS((listitem_T *item));
static void listitem_remove __ARGS((list_T *l, listitem_T *item));
static long list_len __ARGS((list_T *l));
! static int list_equal __ARGS((list_T *l1, list_T *l2, int ic, int recursive));
! static int dict_equal __ARGS((dict_T *d1, dict_T *d2, int ic, int recursive));
! static int tv_equal __ARGS((typval_T *tv1, typval_T *tv2, int ic, int recursive));
static listitem_T *list_find __ARGS((list_T *l, long n));
static long list_find_nr __ARGS((list_T *l, long idx, int *errorp));
static long list_idx_of_item __ARGS((list_T *l, listitem_T *item));
***************
*** 4350,4356 ****
else
{
/* Compare two Lists for being equal or unequal. */
! n1 = list_equal(rettv->vval.v_list, var2.vval.v_list, ic);
if (type == TYPE_NEQUAL)
n1 = !n1;
}
--- 4350,4357 ----
else
{
/* Compare two Lists for being equal or unequal. */
! n1 = list_equal(rettv->vval.v_list, var2.vval.v_list,
! ic, FALSE);
if (type == TYPE_NEQUAL)
n1 = !n1;
}
***************
*** 4379,4385 ****
else
{
/* Compare two Dictionaries for being equal or unequal. */
! n1 = dict_equal(rettv->vval.v_dict, var2.vval.v_dict, ic);
if (type == TYPE_NEQUAL)
n1 = !n1;
}
--- 4380,4387 ----
else
{
/* Compare two Dictionaries for being equal or unequal. */
! n1 = dict_equal(rettv->vval.v_dict, var2.vval.v_dict,
! ic, FALSE);
if (type == TYPE_NEQUAL)
n1 = !n1;
}
***************
*** 5914,5923 ****
* Return TRUE when two lists have exactly the same values.
*/
static int
! list_equal(l1, l2, ic)
list_T *l1;
list_T *l2;
int ic; /* ignore case for strings */
{
listitem_T *item1, *item2;
--- 5916,5926 ----
* Return TRUE when two lists have exactly the same values.
*/
static int
! list_equal(l1, l2, ic, recursive)
list_T *l1;
list_T *l2;
int ic; /* ignore case for strings */
+ int recursive; /* TRUE when used recursively */
{
listitem_T *item1, *item2;
***************
*** 5931,5937 ****
for (item1 = l1->lv_first, item2 = l2->lv_first;
item1 != NULL && item2 != NULL;
item1 = item1->li_next, item2 = item2->li_next)
! if (!tv_equal(&item1->li_tv, &item2->li_tv, ic))
return FALSE;
return item1 == NULL && item2 == NULL;
}
--- 5934,5940 ----
for (item1 = l1->lv_first, item2 = l2->lv_first;
item1 != NULL && item2 != NULL;
item1 = item1->li_next, item2 = item2->li_next)
! if (!tv_equal(&item1->li_tv, &item2->li_tv, ic, recursive))
return FALSE;
return item1 == NULL && item2 == NULL;
}
***************
*** 5953,5962 ****
* Return TRUE when two dictionaries have exactly the same key/values.
*/
static int
! dict_equal(d1, d2, ic)
dict_T *d1;
dict_T *d2;
int ic; /* ignore case for strings */
{
hashitem_T *hi;
dictitem_T *item2;
--- 5956,5966 ----
* Return TRUE when two dictionaries have exactly the same key/values.
*/
static int
! dict_equal(d1, d2, ic, recursive)
dict_T *d1;
dict_T *d2;
int ic; /* ignore case for strings */
+ int recursive; /* TRUE when used recursively */
{
hashitem_T *hi;
dictitem_T *item2;
***************
*** 5977,5983 ****
item2 = dict_find(d2, hi->hi_key, -1);
if (item2 == NULL)
return FALSE;
! if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic))
return FALSE;
--todo;
}
--- 5981,5987 ----
item2 = dict_find(d2, hi->hi_key, -1);
if (item2 == NULL)
return FALSE;
! if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic, recursive))
return FALSE;
--todo;
}
***************
*** 5985,6025 ****
return TRUE;
}
/*
* Return TRUE if "tv1" and "tv2" have the same value.
* Compares the items just like "==" would compare them, but strings and
* numbers are different. Floats and numbers are also different.
*/
static int
! tv_equal(tv1, tv2, ic)
typval_T *tv1;
typval_T *tv2;
! int ic; /* ignore case */
{
char_u buf1[NUMBUFLEN], buf2[NUMBUFLEN];
char_u *s1, *s2;
! static int recursive = 0; /* cach recursive loops */
int r;
if (tv1->v_type != tv2->v_type)
return FALSE;
/* Catch lists and dicts that have an endless loop by limiting
! * recursiveness to 1000. We guess they are equal then. */
! if (recursive >= 1000)
return TRUE;
switch (tv1->v_type)
{
case VAR_LIST:
! ++recursive;
! r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic);
! --recursive;
return r;
case VAR_DICT:
! ++recursive;
! r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic);
! --recursive;
return r;
case VAR_FUNC:
--- 5989,6042 ----
return TRUE;
}
+ static int tv_equal_recurse_limit;
+
/*
* Return TRUE if "tv1" and "tv2" have the same value.
* Compares the items just like "==" would compare them, but strings and
* numbers are different. Floats and numbers are also different.
*/
static int
! tv_equal(tv1, tv2, ic, recursive)
typval_T *tv1;
typval_T *tv2;
! int ic; /* ignore case */
! int recursive; /* TRUE when used recursively */
{
char_u buf1[NUMBUFLEN], buf2[NUMBUFLEN];
char_u *s1, *s2;
! static int recursive_cnt = 0; /* catch recursive loops */
int r;
if (tv1->v_type != tv2->v_type)
return FALSE;
+
/* Catch lists and dicts that have an endless loop by limiting
! * recursiveness to a limit. We guess they are equal then.
! * A fixed limit has the problem of still taking an awful long time.
! * Reduce the limit every time running into it. That should work fine for
! * deeply linked structures that are not recursively linked and catch
! * recursiveness quickly. */
! if (!recursive)
! tv_equal_recurse_limit = 1000;
! if (recursive_cnt >= tv_equal_recurse_limit)
! {
! --tv_equal_recurse_limit;
return TRUE;
+ }
switch (tv1->v_type)
{
case VAR_LIST:
! ++recursive_cnt;
! r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic, TRUE);
! --recursive_cnt;
return r;
case VAR_DICT:
! ++recursive_cnt;
! r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic, TRUE);
! --recursive_cnt;
return r;
case VAR_FUNC:
***************
*** 9391,9397 ****
}
for ( ; li != NULL; li = li->li_next)
! if (tv_equal(&li->li_tv, &argvars[1], ic))
++n;
}
}
--- 9408,9414 ----
}
for ( ; li != NULL; li = li->li_next)
! if (tv_equal(&li->li_tv, &argvars[1], ic, FALSE))
++n;
}
}
***************
*** 9418,9424 ****
if (!HASHITEM_EMPTY(hi))
{
--todo;
! if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic))
++n;
}
}
--- 9435,9441 ----
if (!HASHITEM_EMPTY(hi))
{
--todo;
! if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic, FALSE))
++n;
}
}
***************
*** 12574,12580 ****
}
for ( ; item != NULL; item = item->li_next, ++idx)
! if (tv_equal(&item->li_tv, &argvars[1], ic))
{
rettv->vval.v_number = idx;
break;
--- 12591,12597 ----
}
for ( ; item != NULL; item = item->li_next, ++idx)
! if (tv_equal(&item->li_tv, &argvars[1], ic, FALSE))
{
rettv->vval.v_number = idx;
break;
*** ../vim-7.3.054/src/testdir/test55.in 2010-08-15 21:57:29.000000000 +0200
--- src/testdir/test55.in 2010-11-10 20:15:27.000000000 +0100
***************
*** 342,348 ****
--- 342,359 ----
:$put =(d == d)
:$put =(l != deepcopy(l))
:$put =(d != deepcopy(d))
+ :"
+ :" compare complex recursively linked list and dict
+ :let l = []
+ :call add(l, l)
+ :let dict4 = {"l": l}
+ :call add(dict4.l, dict4)
+ :let lcopy = deepcopy(l)
+ :let dict4copy = deepcopy(dict4)
+ :$put =(l == lcopy)
+ :$put =(dict4 == dict4copy)
:endfun
+ :"
:call Test(1, 2, [3, 4], {5: 6}) " This may take a while
:"
:delfunc Test
*** ../vim-7.3.054/src/testdir/test55.ok 2010-08-15 21:57:29.000000000 +0200
--- src/testdir/test55.ok 2010-11-10 20:16:37.000000000 +0100
***************
*** 109,111 ****
--- 109,113 ----
1
0
0
+ 1
+ 1
*** ../vim-7.3.054/src/version.c 2010-11-10 18:59:50.000000000 +0100
--- src/version.c 2010-11-10 20:10:51.000000000 +0100
***************
*** 716,717 ****
--- 716,719 ----
{ /* Add new patch number below this line */
+ /**/
+ 55,
/**/
--
A special law prohibits unmarried women from parachuting on Sunday or she
shall risk arrest, fine, and/or jailing.
[real standing law in Florida, United States of America]
/// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\
/// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
\\\ download, build and distribute -- http://www.A-A-P.org ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///