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    ///
