To: vim_dev@googlegroups.com Subject: Patch 7.3.055 Fcc: outbox From: Bram Moolenaar 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 ///