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