Mercurial > vim

comparison src/eval.c @ 2634:fcb916bed51a v7.3.055

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
updated for version 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
author Bram Moolenaar <bram@vim.org>
date Wed, 10 Nov 2010 20:41:57 +0100
parents 6c05b5e5c1be
children ef3a3ec8940c
comparison
equal deleted inserted replaced
2633:7002404b17b1 2634:fcb916bed51a
432 static int rettv_list_alloc __ARGS((typval_T *rettv)); 432 static int rettv_list_alloc __ARGS((typval_T *rettv));
433 static listitem_T *listitem_alloc __ARGS((void)); 433 static listitem_T *listitem_alloc __ARGS((void));
434 static void listitem_free __ARGS((listitem_T *item)); 434 static void listitem_free __ARGS((listitem_T *item));
435 static void listitem_remove __ARGS((list_T *l, listitem_T *item)); 435 static void listitem_remove __ARGS((list_T *l, listitem_T *item));
436 static long list_len __ARGS((list_T *l)); 436 static long list_len __ARGS((list_T *l));
437 static int list_equal __ARGS((list_T *l1, list_T *l2, int ic)); 437 static int list_equal __ARGS((list_T *l1, list_T *l2, int ic, int recursive));
438 static int dict_equal __ARGS((dict_T *d1, dict_T *d2, int ic)); 438 static int dict_equal __ARGS((dict_T *d1, dict_T *d2, int ic, int recursive));
439 static int tv_equal __ARGS((typval_T *tv1, typval_T *tv2, int ic)); 439 static int tv_equal __ARGS((typval_T *tv1, typval_T *tv2, int ic, int recursive));
440 static listitem_T *list_find __ARGS((list_T *l, long n)); 440 static listitem_T *list_find __ARGS((list_T *l, long n));
441 static long list_find_nr __ARGS((list_T *l, long idx, int *errorp)); 441 static long list_find_nr __ARGS((list_T *l, long idx, int *errorp));
442 static long list_idx_of_item __ARGS((list_T *l, listitem_T *item)); 442 static long list_idx_of_item __ARGS((list_T *l, listitem_T *item));
443 static void list_append __ARGS((list_T *l, listitem_T *item)); 443 static void list_append __ARGS((list_T *l, listitem_T *item));
444 static int list_append_number __ARGS((list_T *l, varnumber_T n)); 444 static int list_append_number __ARGS((list_T *l, varnumber_T n));
4348 return FAIL; 4348 return FAIL;
4349 } 4349 }
4350 else 4350 else
4351 { 4351 {
4352 /* Compare two Lists for being equal or unequal. */ 4352 /* Compare two Lists for being equal or unequal. */
4353 n1 = list_equal(rettv->vval.v_list, var2.vval.v_list, ic); 4353 n1 = list_equal(rettv->vval.v_list, var2.vval.v_list,
4354 ic, FALSE);
4354 if (type == TYPE_NEQUAL) 4355 if (type == TYPE_NEQUAL)
4355 n1 = !n1; 4356 n1 = !n1;
4356 } 4357 }
4357 } 4358 }
4358 4359
4377 return FAIL; 4378 return FAIL;
4378 } 4379 }
4379 else 4380 else
4380 { 4381 {
4381 /* Compare two Dictionaries for being equal or unequal. */ 4382 /* Compare two Dictionaries for being equal or unequal. */
4382 n1 = dict_equal(rettv->vval.v_dict, var2.vval.v_dict, ic); 4383 n1 = dict_equal(rettv->vval.v_dict, var2.vval.v_dict,
4384 ic, FALSE);
4383 if (type == TYPE_NEQUAL) 4385 if (type == TYPE_NEQUAL)
4384 n1 = !n1; 4386 n1 = !n1;
4385 } 4387 }
4386 } 4388 }
4387 4389
5912 5914
5913 /* 5915 /*
5914 * Return TRUE when two lists have exactly the same values. 5916 * Return TRUE when two lists have exactly the same values.
5915 */ 5917 */
5916 static int 5918 static int
5917 list_equal(l1, l2, ic) 5919 list_equal(l1, l2, ic, recursive)
5918 list_T *l1; 5920 list_T *l1;
5919 list_T *l2; 5921 list_T *l2;
5920 int ic; /* ignore case for strings */ 5922 int ic; /* ignore case for strings */
5923 int recursive; /* TRUE when used recursively */
5921 { 5924 {
5922 listitem_T *item1, *item2; 5925 listitem_T *item1, *item2;
5923 5926
5924 if (l1 == NULL || l2 == NULL) 5927 if (l1 == NULL || l2 == NULL)
5925 return FALSE; 5928 return FALSE;
5929 return FALSE; 5932 return FALSE;
5930 5933
5931 for (item1 = l1->lv_first, item2 = l2->lv_first; 5934 for (item1 = l1->lv_first, item2 = l2->lv_first;
5932 item1 != NULL && item2 != NULL; 5935 item1 != NULL && item2 != NULL;
5933 item1 = item1->li_next, item2 = item2->li_next) 5936 item1 = item1->li_next, item2 = item2->li_next)
5934 if (!tv_equal(&item1->li_tv, &item2->li_tv, ic)) 5937 if (!tv_equal(&item1->li_tv, &item2->li_tv, ic, recursive))
5935 return FALSE; 5938 return FALSE;
5936 return item1 == NULL && item2 == NULL; 5939 return item1 == NULL && item2 == NULL;
5937 } 5940 }
5938 5941
5939 #if defined(FEAT_RUBY) || defined(FEAT_PYTHON) || defined(FEAT_PYTHON3) \ 5942 #if defined(FEAT_RUBY) || defined(FEAT_PYTHON) || defined(FEAT_PYTHON3) \
5951 5954
5952 /* 5955 /*
5953 * Return TRUE when two dictionaries have exactly the same key/values. 5956 * Return TRUE when two dictionaries have exactly the same key/values.
5954 */ 5957 */
5955 static int 5958 static int
5956 dict_equal(d1, d2, ic) 5959 dict_equal(d1, d2, ic, recursive)
5957 dict_T *d1; 5960 dict_T *d1;
5958 dict_T *d2; 5961 dict_T *d2;
5959 int ic; /* ignore case for strings */ 5962 int ic; /* ignore case for strings */
5963 int recursive; /* TRUE when used recursively */
5960 { 5964 {
5961 hashitem_T *hi; 5965 hashitem_T *hi;
5962 dictitem_T *item2; 5966 dictitem_T *item2;
5963 int todo; 5967 int todo;
5964 5968
5975 if (!HASHITEM_EMPTY(hi)) 5979 if (!HASHITEM_EMPTY(hi))
5976 { 5980 {
5977 item2 = dict_find(d2, hi->hi_key, -1); 5981 item2 = dict_find(d2, hi->hi_key, -1);
5978 if (item2 == NULL) 5982 if (item2 == NULL)
5979 return FALSE; 5983 return FALSE;
5980 if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic)) 5984 if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic, recursive))
5981 return FALSE; 5985 return FALSE;
5982 --todo; 5986 --todo;
5983 } 5987 }
5984 } 5988 }
5985 return TRUE; 5989 return TRUE;
5986 } 5990 }
5991
5992 static int tv_equal_recurse_limit;
5987 5993
5988 /* 5994 /*
5989 * Return TRUE if "tv1" and "tv2" have the same value. 5995 * Return TRUE if "tv1" and "tv2" have the same value.
5990 * Compares the items just like "==" would compare them, but strings and 5996 * Compares the items just like "==" would compare them, but strings and
5991 * numbers are different. Floats and numbers are also different. 5997 * numbers are different. Floats and numbers are also different.
5992 */ 5998 */
5993 static int 5999 static int
5994 tv_equal(tv1, tv2, ic) 6000 tv_equal(tv1, tv2, ic, recursive)
5995 typval_T *tv1; 6001 typval_T *tv1;
5996 typval_T *tv2; 6002 typval_T *tv2;
5997 int ic; /* ignore case */ 6003 int ic; /* ignore case */
6004 int recursive; /* TRUE when used recursively */
5998 { 6005 {
5999 char_u buf1[NUMBUFLEN], buf2[NUMBUFLEN]; 6006 char_u buf1[NUMBUFLEN], buf2[NUMBUFLEN];
6000 char_u *s1, *s2; 6007 char_u *s1, *s2;
6001 static int recursive = 0; /* cach recursive loops */ 6008 static int recursive_cnt = 0; /* catch recursive loops */
6002 int r; 6009 int r;
6003 6010
6004 if (tv1->v_type != tv2->v_type) 6011 if (tv1->v_type != tv2->v_type)
6005 return FALSE; 6012 return FALSE;
6013
6006 /* Catch lists and dicts that have an endless loop by limiting 6014 /* Catch lists and dicts that have an endless loop by limiting
6007 * recursiveness to 1000. We guess they are equal then. */ 6015 * recursiveness to a limit. We guess they are equal then.
6008 if (recursive >= 1000) 6016 * A fixed limit has the problem of still taking an awful long time.
6017 * Reduce the limit every time running into it. That should work fine for
6018 * deeply linked structures that are not recursively linked and catch
6019 * recursiveness quickly. */
6020 if (!recursive)
6021 tv_equal_recurse_limit = 1000;
6022 if (recursive_cnt >= tv_equal_recurse_limit)
6023 {
6024 --tv_equal_recurse_limit;
6009 return TRUE; 6025 return TRUE;
6026 }
6010 6027
6011 switch (tv1->v_type) 6028 switch (tv1->v_type)
6012 { 6029 {
6013 case VAR_LIST: 6030 case VAR_LIST:
6014 ++recursive; 6031 ++recursive_cnt;
6015 r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic); 6032 r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic, TRUE);
6016 --recursive; 6033 --recursive_cnt;
6017 return r; 6034 return r;
6018 6035
6019 case VAR_DICT: 6036 case VAR_DICT:
6020 ++recursive; 6037 ++recursive_cnt;
6021 r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic); 6038 r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic, TRUE);
6022 --recursive; 6039 --recursive_cnt;
6023 return r; 6040 return r;
6024 6041
6025 case VAR_FUNC: 6042 case VAR_FUNC:
6026 return (tv1->vval.v_string != NULL 6043 return (tv1->vval.v_string != NULL
6027 && tv2->vval.v_string != NULL 6044 && tv2->vval.v_string != NULL
9389 if (error) 9406 if (error)
9390 li = NULL; 9407 li = NULL;
9391 } 9408 }
9392 9409
9393 for ( ; li != NULL; li = li->li_next) 9410 for ( ; li != NULL; li = li->li_next)
9394 if (tv_equal(&li->li_tv, &argvars[1], ic)) 9411 if (tv_equal(&li->li_tv, &argvars[1], ic, FALSE))
9395 ++n; 9412 ++n;
9396 } 9413 }
9397 } 9414 }
9398 else if (argvars[0].v_type == VAR_DICT) 9415 else if (argvars[0].v_type == VAR_DICT)
9399 { 9416 {
9416 for (hi = d->dv_hashtab.ht_array; todo > 0; ++hi) 9433 for (hi = d->dv_hashtab.ht_array; todo > 0; ++hi)
9417 { 9434 {
9418 if (!HASHITEM_EMPTY(hi)) 9435 if (!HASHITEM_EMPTY(hi))
9419 { 9436 {
9420 --todo; 9437 --todo;
9421 if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic)) 9438 if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic, FALSE))
9422 ++n; 9439 ++n;
9423 } 9440 }
9424 } 9441 }
9425 } 9442 }
9426 } 9443 }
12572 if (error) 12589 if (error)
12573 item = NULL; 12590 item = NULL;
12574 } 12591 }
12575 12592
12576 for ( ; item != NULL; item = item->li_next, ++idx) 12593 for ( ; item != NULL; item = item->li_next, ++idx)
12577 if (tv_equal(&item->li_tv, &argvars[1], ic)) 12594 if (tv_equal(&item->li_tv, &argvars[1], ic, FALSE))
12578 { 12595 {
12579 rettv->vval.v_number = idx; 12596 rettv->vval.v_number = idx;
12580 break; 12597 break;
12581 } 12598 }
12582 } 12599 }