7.3.055

   1 To: vim_dev@googlegroups.com
   2 Subject: Patch 7.3.055
   3 Fcc: outbox
   4 From: Bram Moolenaar <Bram@moolenaar.net>
   5 Mime-Version: 1.0
   6 Content-Type: text/plain; charset=UTF-8
   7 Content-Transfer-Encoding: 8bit
   8 ------------
   9
  10 Patch 7.3.055
  11 Problem:    Recursively nested lists and dictionaries cause a near-endless
  12             loop when comparing them with a copy. (ZyX)
  13 Solution:   Limit recursiveness in a way that non-recursive structures can
  14             still be nested very deep.
  15 Files:      src/eval.c, src/testdir/test55.in, src/testdir/test55.ok
  16
  17
  18 *** ../vim-7.3.054/src/eval.c   2010-10-20 21:22:17.000000000 +0200
  19 --- src/eval.c  2010-11-10 20:02:57.000000000 +0100
  20 ***************
  21 *** 434,442 ****
  22   static void listitem_free __ARGS((listitem_T *item));
  23   static void listitem_remove __ARGS((list_T *l, listitem_T *item));
  24   static long list_len __ARGS((list_T *l));
  25 ! static int list_equal __ARGS((list_T *l1, list_T *l2, int ic));
  26 ! static int dict_equal __ARGS((dict_T *d1, dict_T *d2, int ic));
  27 ! static int tv_equal __ARGS((typval_T *tv1, typval_T *tv2, int ic));
  28   static listitem_T *list_find __ARGS((list_T *l, long n));
  29   static long list_find_nr __ARGS((list_T *l, long idx, int *errorp));
  30   static long list_idx_of_item __ARGS((list_T *l, listitem_T *item));
  31 --- 434,442 ----
  32   static void listitem_free __ARGS((listitem_T *item));
  33   static void listitem_remove __ARGS((list_T *l, listitem_T *item));
  34   static long list_len __ARGS((list_T *l));
  35 ! static int list_equal __ARGS((list_T *l1, list_T *l2, int ic, int recursive));
  36 ! static int dict_equal __ARGS((dict_T *d1, dict_T *d2, int ic, int recursive));
  37 ! static int tv_equal __ARGS((typval_T *tv1, typval_T *tv2, int ic, int recursive));
  38   static listitem_T *list_find __ARGS((list_T *l, long n));
  39   static long list_find_nr __ARGS((list_T *l, long idx, int *errorp));
  40   static long list_idx_of_item __ARGS((list_T *l, listitem_T *item));
  41 ***************
  42 *** 4350,4356 ****
  43                 else
  44                 {
  45                     /* Compare two Lists for being equal or unequal. */
  46 !                   n1 = list_equal(rettv->vval.v_list, var2.vval.v_list, ic);
  47                     if (type == TYPE_NEQUAL)
  48                         n1 = !n1;
  49                 }
  50 --- 4350,4357 ----
  51                 else
  52                 {
  53                     /* Compare two Lists for being equal or unequal. */
  54 !                   n1 = list_equal(rettv->vval.v_list, var2.vval.v_list,
  55 !                                                                  ic, FALSE);
  56                     if (type == TYPE_NEQUAL)
  57                         n1 = !n1;
  58                 }
  59 ***************
  60 *** 4379,4385 ****
  61                 else
  62                 {
  63                     /* Compare two Dictionaries for being equal or unequal. */
  64 !                   n1 = dict_equal(rettv->vval.v_dict, var2.vval.v_dict, ic);
  65                     if (type == TYPE_NEQUAL)
  66                         n1 = !n1;
  67                 }
  68 --- 4380,4387 ----
  69                 else
  70                 {
  71                     /* Compare two Dictionaries for being equal or unequal. */
  72 !                   n1 = dict_equal(rettv->vval.v_dict, var2.vval.v_dict,
  73 !                                                                  ic, FALSE);
  74                     if (type == TYPE_NEQUAL)
  75                         n1 = !n1;
  76                 }
  77 ***************
  78 *** 5914,5923 ****
  79    * Return TRUE when two lists have exactly the same values.
  80    */
  81       static int
  82 ! list_equal(l1, l2, ic)
  83       list_T    *l1;
  84       list_T    *l2;
  85       int               ic;     /* ignore case for strings */
  86   {
  87       listitem_T        *item1, *item2;
  88
  89 --- 5916,5926 ----
  90    * Return TRUE when two lists have exactly the same values.
  91    */
  92       static int
  93 ! list_equal(l1, l2, ic, recursive)
  94       list_T    *l1;
  95       list_T    *l2;
  96       int               ic;     /* ignore case for strings */
  97 +     int               recursive;  /* TRUE when used recursively */
  98   {
  99       listitem_T        *item1, *item2;
 100
 101 ***************
 102 *** 5931,5937 ****
 103       for (item1 = l1->lv_first, item2 = l2->lv_first;
 104             item1 != NULL && item2 != NULL;
 105                                item1 = item1->li_next, item2 = item2->li_next)
 106 !       if (!tv_equal(&item1->li_tv, &item2->li_tv, ic))
 107             return FALSE;
 108       return item1 == NULL && item2 == NULL;
 109   }
 110 --- 5934,5940 ----
 111       for (item1 = l1->lv_first, item2 = l2->lv_first;
 112             item1 != NULL && item2 != NULL;
 113                                item1 = item1->li_next, item2 = item2->li_next)
 114 !       if (!tv_equal(&item1->li_tv, &item2->li_tv, ic, recursive))
 115             return FALSE;
 116       return item1 == NULL && item2 == NULL;
 117   }
 118 ***************
 119 *** 5953,5962 ****
 120    * Return TRUE when two dictionaries have exactly the same key/values.
 121    */
 122       static int
 123 ! dict_equal(d1, d2, ic)
 124       dict_T    *d1;
 125       dict_T    *d2;
 126       int               ic;     /* ignore case for strings */
 127   {
 128       hashitem_T        *hi;
 129       dictitem_T        *item2;
 130 --- 5956,5966 ----
 131    * Return TRUE when two dictionaries have exactly the same key/values.
 132    */
 133       static int
 134 ! dict_equal(d1, d2, ic, recursive)
 135       dict_T    *d1;
 136       dict_T    *d2;
 137       int               ic;     /* ignore case for strings */
 138 +     int               recursive; /* TRUE when used recursively */
 139   {
 140       hashitem_T        *hi;
 141       dictitem_T        *item2;
 142 ***************
 143 *** 5977,5983 ****
 144             item2 = dict_find(d2, hi->hi_key, -1);
 145             if (item2 == NULL)
 146                 return FALSE;
 147 !           if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic))
 148                 return FALSE;
 149             --todo;
 150         }
 151 --- 5981,5987 ----
 152             item2 = dict_find(d2, hi->hi_key, -1);
 153             if (item2 == NULL)
 154                 return FALSE;
 155 !           if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic, recursive))
 156                 return FALSE;
 157             --todo;
 158         }
 159 ***************
 160 *** 5985,6025 ****
 161       return TRUE;
 162   }
 163
 164   /*
 165    * Return TRUE if "tv1" and "tv2" have the same value.
 166    * Compares the items just like "==" would compare them, but strings and
 167    * numbers are different.  Floats and numbers are also different.
 168    */
 169       static int
 170 ! tv_equal(tv1, tv2, ic)
 171       typval_T *tv1;
 172       typval_T *tv2;
 173 !     int           ic;     /* ignore case */
 174   {
 175       char_u    buf1[NUMBUFLEN], buf2[NUMBUFLEN];
 176       char_u    *s1, *s2;
 177 !     static int  recursive = 0;            /* cach recursive loops */
 178       int               r;
 179
 180       if (tv1->v_type != tv2->v_type)
 181         return FALSE;
 182       /* Catch lists and dicts that have an endless loop by limiting
 183 !      * recursiveness to 1000.  We guess they are equal then. */
 184 !     if (recursive >= 1000)
 185         return TRUE;
 186
 187       switch (tv1->v_type)
 188       {
 189         case VAR_LIST:
 190 !           ++recursive;
 191 !           r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic);
 192 !           --recursive;
 193             return r;
 194
 195         case VAR_DICT:
 196 !           ++recursive;
 197 !           r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic);
 198 !           --recursive;
 199             return r;
 200
 201         case VAR_FUNC:
 202 --- 5989,6042 ----
 203       return TRUE;
 204   }
 205
 206 + static int tv_equal_recurse_limit;
 207 +
 208   /*
 209    * Return TRUE if "tv1" and "tv2" have the same value.
 210    * Compares the items just like "==" would compare them, but strings and
 211    * numbers are different.  Floats and numbers are also different.
 212    */
 213       static int
 214 ! tv_equal(tv1, tv2, ic, recursive)
 215       typval_T *tv1;
 216       typval_T *tv2;
 217 !     int            ic;            /* ignore case */
 218 !     int            recursive;     /* TRUE when used recursively */
 219   {
 220       char_u    buf1[NUMBUFLEN], buf2[NUMBUFLEN];
 221       char_u    *s1, *s2;
 222 !     static int  recursive_cnt = 0;        /* catch recursive loops */
 223       int               r;
 224
 225       if (tv1->v_type != tv2->v_type)
 226         return FALSE;
 227 +
 228       /* Catch lists and dicts that have an endless loop by limiting
 229 !      * recursiveness to a limit.  We guess they are equal then.
 230 !      * A fixed limit has the problem of still taking an awful long time.
 231 !      * Reduce the limit every time running into it. That should work fine for
 232 !      * deeply linked structures that are not recursively linked and catch
 233 !      * recursiveness quickly. */
 234 !     if (!recursive)
 235 !       tv_equal_recurse_limit = 1000;
 236 !     if (recursive_cnt >= tv_equal_recurse_limit)
 237 !     {
 238 !       --tv_equal_recurse_limit;
 239         return TRUE;
 240 +     }
 241
 242       switch (tv1->v_type)
 243       {
 244         case VAR_LIST:
 245 !           ++recursive_cnt;
 246 !           r = list_equal(tv1->vval.v_list, tv2->vval.v_list, ic, TRUE);
 247 !           --recursive_cnt;
 248             return r;
 249
 250         case VAR_DICT:
 251 !           ++recursive_cnt;
 252 !           r = dict_equal(tv1->vval.v_dict, tv2->vval.v_dict, ic, TRUE);
 253 !           --recursive_cnt;
 254             return r;
 255
 256         case VAR_FUNC:
 257 ***************
 258 *** 9391,9397 ****
 259             }
 260
 261             for ( ; li != NULL; li = li->li_next)
 262 !               if (tv_equal(&li->li_tv, &argvars[1], ic))
 263                     ++n;
 264         }
 265       }
 266 --- 9408,9414 ----
 267             }
 268
 269             for ( ; li != NULL; li = li->li_next)
 270 !               if (tv_equal(&li->li_tv, &argvars[1], ic, FALSE))
 271                     ++n;
 272         }
 273       }
 274 ***************
 275 *** 9418,9424 ****
 276                 if (!HASHITEM_EMPTY(hi))
 277                 {
 278                     --todo;
 279 !                   if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic))
 280                         ++n;
 281                 }
 282             }
 283 --- 9435,9441 ----
 284                 if (!HASHITEM_EMPTY(hi))
 285                 {
 286                     --todo;
 287 !                   if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic, FALSE))
 288                         ++n;
 289                 }
 290             }
 291 ***************
 292 *** 12574,12580 ****
 293         }
 294
 295         for ( ; item != NULL; item = item->li_next, ++idx)
 296 !           if (tv_equal(&item->li_tv, &argvars[1], ic))
 297             {
 298                 rettv->vval.v_number = idx;
 299                 break;
 300 --- 12591,12597 ----
 301         }
 302
 303         for ( ; item != NULL; item = item->li_next, ++idx)
 304 !           if (tv_equal(&item->li_tv, &argvars[1], ic, FALSE))
 305             {
 306                 rettv->vval.v_number = idx;
 307                 break;
 308 *** ../vim-7.3.054/src/testdir/test55.in        2010-08-15 21:57:29.000000000 +0200
 309 --- src/testdir/test55.in       2010-11-10 20:15:27.000000000 +0100
 310 ***************
 311 *** 342,348 ****
 312 --- 342,359 ----
 313   :$put =(d == d)
 314   :$put =(l != deepcopy(l))
 315   :$put =(d != deepcopy(d))
 316 + :"
 317 + :" compare complex recursively linked list and dict
 318 + :let l = []
 319 + :call add(l, l)
 320 + :let dict4 = {"l": l}
 321 + :call add(dict4.l, dict4)
 322 + :let lcopy = deepcopy(l)
 323 + :let dict4copy = deepcopy(dict4)
 324 + :$put =(l == lcopy)
 325 + :$put =(dict4 == dict4copy)
 326   :endfun
 327 + :"
 328   :call Test(1, 2, [3, 4], {5: 6})  " This may take a while
 329   :"
 330   :delfunc Test
 331 *** ../vim-7.3.054/src/testdir/test55.ok        2010-08-15 21:57:29.000000000 +0200
 332 --- src/testdir/test55.ok       2010-11-10 20:16:37.000000000 +0100
 333 ***************
 334 *** 109,111 ****
 335 --- 109,113 ----
 336   1
 337   0
 338   0
 339 + 1
 340 + 1
 341 *** ../vim-7.3.054/src/version.c        2010-11-10 18:59:50.000000000 +0100
 342 --- src/version.c       2010-11-10 20:10:51.000000000 +0100
 343 ***************
 344 *** 716,717 ****
 345 --- 716,719 ----
 346   {   /* Add new patch number below this line */
 347 + /**/
 348 +     55,
 349   /**/
 350
 351 --
 352 A special law prohibits unmarried women from parachuting on Sunday or she
 353 shall risk arrest, fine, and/or jailing.
 354                 [real standing law in Florida, United States of America]
 355
 356  /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net   \\\
 357 ///        sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
 358 \\\        download, build and distribute -- http://www.A-A-P.org        ///
 359  \\\            help me help AIDS victims -- http://ICCF-Holland.org    ///