| 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 |
| |
| |
| |
| |
| |
| *** 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; |
| |
| |
| |
| *** 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 |
| |
| |
| |
| *** 109,111 **** |
| --- 109,113 ---- |
| 1 |
| 0 |
| 0 |
| + 1 |
| + 1 |
| |
| |
| |
| *** 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 /// |