src/uentryList.c

   1 /*
   2 ** LCLint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2000 University of Virginia,
   4 **         Massachusetts Institute of Technology
   5 **
   6 ** This program is free software; you can redistribute it and/or modify it
   7 ** under the terms of the GNU General Public License as published by the
   8 ** Free Software Foundation; either version 2 of the License, or (at your
   9 ** option) any later version.
  10 **
  11 ** This program is distributed in the hope that it will be useful, but
  12 ** WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 ** General Public License for more details.
  15 **
  16 ** The GNU General Public License is available from http://www.gnu.org/ or
  17 ** the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  18 ** MA 02111-1307, USA.
  19 **
  20 ** For information on lclint: lclint-request@cs.virginia.edu
  21 ** To report a bug: lclint-bug@cs.virginia.edu
  22 ** For more information: http://lclint.cs.virginia.edu
  23 */
  24 /*
  25 ** uentryList.c (from slist_template.c)
  26 */
  27
  28 # include "lclintMacros.nf"
  29 # include "basic.h"
  30
  31 /*@only@*/ /*@notnull@*/ uentryList
  32 uentryList_new ()
  33 {
  34   uentryList s = (uentryList) dmalloc (sizeof (*s));
  35
  36   s->nelements = 0;
  37   s->nspace = uentryListBASESIZE;
  38   s->elements = (uentry *)
  39     dmalloc (sizeof (*s->elements) * uentryListBASESIZE);
  40   s->current = 0;
  41
  42   return (s);
  43 }
  44
  45 /*@only@*/ uentryList
  46 uentryList_single (/*@keep@*/ uentry el)
  47 {
  48   uentryList s = (uentryList) dmalloc (sizeof (*s));
  49
  50   s->nelements = 1;
  51   s->nspace = uentryListBASESIZE - 1;
  52   s->elements = (uentry *) dmalloc (sizeof (*s->elements) * uentryListBASESIZE);
  53
  54   s->elements[0] = el;
  55   s->current = 0;
  56
  57   return (s);
  58 }
  59
  60 static void
  61 uentryList_grow (uentryList s)
  62 {
  63   int i;
  64   uentry *newelements;
  65
  66   llassert (!uentryList_isUndefined (s));
  67
  68   s->nspace += uentryListBASESIZE;
  69
  70   newelements = (uentry *) dmalloc (sizeof (*newelements)
  71                                     * (s->nelements + s->nspace));
  72
  73   for (i = 0; i < s->nelements; i++)
  74     {
  75       newelements[i] = s->elements[i];
  76     }
  77
  78   sfree (s->elements);
  79   s->elements = newelements;
  80 }
  81
  82 void uentryList_clear (uentryList s)
  83 {
  84   if (uentryList_isUndefined (s))
  85     {
  86       ;
  87     }
  88   else
  89     {
  90       s->nspace += s->nelements;
  91       s->nelements = 0;
  92     }
  93 }
  94
  95 uentryList uentryList_add (uentryList s, /*@keep@*/ uentry el)
  96 {
  97   if (uentryList_isUndefined (s))
  98     {
  99       s = uentryList_new ();
 100     }
 101
 102   if (s->nspace <= 0)
 103     uentryList_grow (s);
 104
 105   s->nspace--;
 106   s->elements[s->nelements] = el;
 107   s->nelements++;
 108
 109   return s;
 110 }
 111
 112 /*@only@*/ cstring
 113   uentryList_unparse (uentryList s)
 114 {
 115   cstring st = cstring_undefined;
 116   int i;
 117
 118   if (uentryList_isDefined (s))
 119     {
 120       for (i = 0; i < uentryList_size (s); i++)
 121         {
 122           if (i == 0)
 123             {
 124               st = message ("%q;", uentry_unparse (s->elements[i]));
 125             }
 126           else
 127             st = message ("%q %q;", st, uentry_unparse (s->elements[i]));
 128         }
 129     }
 130
 131   return (st);
 132 }
 133
 134 /*@unused@*/ /*@only@*/ cstring
 135   uentryList_unparseFull (uentryList s)
 136 {
 137   cstring st = cstring_undefined;
 138   int i;
 139
 140   if (uentryList_isDefined (s))
 141     {
 142       for (i = 0; i < uentryList_size (s); i++)
 143         {
 144           if (i == 0)
 145             {
 146               st = message ("%q;", uentry_unparseFull (s->elements[i]));
 147             }
 148           else
 149             {
 150               st = message ("%q %q;", st, uentry_unparseFull (s->elements[i]));
 151             }
 152         }
 153     }
 154
 155   return (st);
 156 }
 157
 158 cstring uentryList_unparseParams (uentryList s)
 159 {
 160   int i;
 161   cstring st = cstring_undefined;
 162
 163
 164   if (uentryList_isUndefined (s))
 165     {
 166       return st;
 167     }
 168   else if (uentryList_isVoid (s))
 169     {
 170       return (cstring_makeLiteral ("void"));
 171     }
 172   else
 173     {
 174       for (i = 0; i < uentryList_size (s); i++)
 175         {
 176           if (i == 0)
 177             {
 178               st = message ("%s", ctype_unparse (uentry_getType (s->elements[i])));
 179             }
 180           else
 181             {
 182               st = message ("%q, %s", st, ctype_unparse (uentry_getType (s->elements[i])));
 183             }
 184         }
 185
 186       return st;
 187     }
 188 }
 189
 190 bool uentryList_matchParams (uentryList p1, uentryList p2, bool force, bool arg)
 191 {
 192   int sz1 = uentryList_size (p1);
 193   int sz2 = uentryList_size (p2);
 194   int i;
 195
 196   if (p1 == p2) return TRUE;
 197
 198   if (uentryList_isMissingParams (p1) || uentryList_isMissingParams (p2))
 199     {
 200       return TRUE;
 201     }
 202
 203   if (sz1 != sz2)
 204     return FALSE;
 205
 206   for (i = 0; i < sz1; i++)
 207     {
 208       if (!ctype_genMatch (uentry_getType (p1->elements[i]),
 209                            uentry_getType (p2->elements[i]),
 210                            force, arg, FALSE))
 211         {
 212           return FALSE;
 213         }
 214     }
 215
 216   return TRUE;
 217 }
 218
 219 /*@only@*/ cstring
 220 uentryList_unparseAbbrev (uentryList p)
 221 {
 222   bool first = TRUE;
 223   cstring s = cstring_undefined;
 224   int i = 0;
 225
 226   if (uentryList_isUndefined (p))
 227     return s;
 228
 229   if (uentryList_size (p) == 0)
 230     return cstring_makeLiteral ("void");
 231
 232   for (i = 0; i < p->nelements && i < PRINTBREADTH; i++)
 233     {
 234       if (first)
 235         {
 236           s = message ("%q;", uentry_unparseAbbrev (p->elements[i]));
 237           first = FALSE;
 238         }
 239       else
 240         {
 241           s = message ("%q %q;", s, uentry_unparseAbbrev (p->elements[i]));
 242         }
 243     }
 244
 245   if (i != uentryList_size (p))
 246     s = message ("%q, ...", s);
 247
 248   return (s);
 249 }
 250
 251 static int
 252 uentryList_lookupDirectName (uentryList s, cstring name)
 253 {
 254   if (uentryList_isDefined (s))
 255     {
 256       int i;
 257
 258       for (i = 0; i < uentryList_size (s); i++)
 259         {
 260           if (cstring_equal (name, uentry_rawName (s->elements[i])))
 261             {
 262               return i;
 263             }
 264         }
 265     }
 266
 267    return -1;
 268 }
 269
 270 int
 271 uentryList_lookupRealName (uentryList s, cstring name)
 272 {
 273   if (uentryList_isDefined (s))
 274     {
 275       int i;
 276
 277       for (i = 0; i < uentryList_size (s); i++)
 278         {
 279           cstring uname = uentry_getName (s->elements[i]);
 280
 281           if (cstring_equal (name, uname))
 282             {
 283               cstring_free (uname);
 284               return i;
 285             }
 286
 287           cstring_free (uname);
 288         }
 289     }
 290
 291    return -1;
 292 }
 293
 294 uentryList uentryList_copy (uentryList s)
 295 {
 296
 297   if (uentryList_isDefined (s))
 298     {
 299       uentryList t = (uentryList) dmalloc (sizeof (*t));
 300       int i;
 301
 302       t->nelements = s->nelements;
 303       t->nspace = 0;
 304       t->current = s->current;
 305
 306       if (s->nelements > 0)
 307         {
 308           t->elements = (uentry *) dmalloc (sizeof (*t->elements) * t->nelements);
 309
 310           for (i = 0; i < s->nelements; i++)
 311             {
 312                       t->elements[i] = uentry_copy (s->elements[i]);
 313                     }
 314         }
 315       else
 316         {
 317           t->elements = NULL;
 318         }
 319
 320       return t;
 321     }
 322   else
 323     {
 324       return uentryList_undefined;
 325     }
 326 }
 327
 328 void
 329 uentryList_free (uentryList s)
 330 {
 331
 332   if (!uentryList_isUndefined (s))
 333     {
 334       int i;
 335
 336       for (i = 0; i < s->nelements; i++)
 337         {
 338           uentry_free (s->elements[i]);
 339         }
 340
 341       sfree (s->elements);
 342       sfree (s);
 343     }
 344 }
 345
 346 bool
 347 uentryList_isVoid (uentryList cl)
 348 {
 349   if (cl != NULL && cl->nelements == 1)
 350     {
 351       return (ctype_isVoid (uentry_getType (cl->elements[0])));
 352     }
 353   return FALSE;
 354 }
 355
 356 /*@exposed@*/ uentry
 357 uentryList_getN (uentryList p, int n)
 358 {
 359   llassert (uentryList_isDefined (p));
 360
 361   if (n < 0 || (n >= uentryList_size (p)))
 362     {
 363       llcontbug (message ("uentryList_getN: out of range: %d (size %d)",
 364                           n, uentryList_size (p)));
 365       return uentry_undefined;
 366     }
 367
 368   return (p->elements[n]);
 369 }
 370
 371 void uentryList_fixMissingNames (uentryList cl)
 372 {
 373   uentryList_elements (cl, ce)
 374     {
 375       if (!uentry_hasRealName (ce))
 376         {
 377           ctype ct = uentry_getType (ce);
 378
 379           if (ctype_isUA (ct))
 380             {
 381               uentry_setName (ce, usymtab_getTypeEntryName (ctype_typeId (ct)));
 382             }
 383           else
 384             {
 385               llbug (message ("uentryList_fixMissingNames: not UA: %s",
 386                               ctype_unparse (ct)));
 387             }
 388
 389           uentry_setType (ce, ctype_int);
 390         }
 391     } end_uentryList_elements;
 392 }
 393
 394 void uentryList_fixImpParams (uentryList cl)
 395 {
 396
 397   if (context_getFlag (FLG_PARAMIMPTEMP))
 398     {
 399       uentryList_elements (cl, ce)
 400         {
 401           sRef s = uentry_getSref (ce);
 402           alkind ak = sRef_getAliasKind (s);
 403
 404           if (alkind_isUnknown (ak) || alkind_isImplicit (ak))
 405             {
 406               exkind ek = sRef_getExKind (s);
 407
 408               if (exkind_isKnown (ek))
 409                 {
 410                   sRef_setAliasKind (s, AK_IMPDEPENDENT, fileloc_undefined);
 411                 }
 412               else
 413                 {
 414                   sRef_setAliasKind (s, AK_IMPTEMP, fileloc_undefined);
 415                 }
 416                     }
 417           else
 418             {
 419                     }
 420         } end_uentryList_elements;
 421     }
 422 }
 423
 424 int
 425 uentryList_compareParams (uentryList s, uentryList t)
 426 {
 427   int i, sz;
 428
 429   if (s == t) return 0;
 430
 431   if (uentryList_isUndefined (s)) return 1;
 432   if (uentryList_isUndefined (t)) return -1;
 433
 434   sz = uentryList_size (s);
 435
 436   INTCOMPARERETURN (uentryList_size (t), sz);
 437
 438   for (i = 0; i < sz; i++)
 439     {
 440       COMPARERETURN (uentry_compare (s->elements[i], t->elements[i]));
 441     }
 442
 443   return 0;
 444 }
 445
 446 int
 447 uentryList_compareStrict (uentryList s, uentryList t)
 448 {
 449   int i, sz;
 450
 451   if (s == t)
 452     {
 453       return 0;
 454     }
 455
 456   if (uentryList_isMissingParams (s))
 457     {
 458       if (uentryList_isMissingParams (t))
 459         {
 460           return 0;
 461         }
 462       else
 463         {
 464           return 1;
 465         }
 466     }
 467   else
 468     {
 469       if (uentryList_isMissingParams (t))
 470         {
 471           return -1;
 472         }
 473       else
 474         {
 475           sz = uentryList_size (s);
 476
 477           INTCOMPARERETURN (uentryList_size (t), sz);
 478
 479           for (i = 0; i < sz; i++)
 480             {
 481               COMPARERETURN (uentry_compareStrict (s->elements[i], t->elements[i]));
 482             }
 483
 484           return 0;
 485         }
 486     }
 487 }
 488
 489 int
 490 uentryList_compareFields (uentryList s, uentryList t)
 491 {
 492   int i, sz;
 493
 494   if (s == t) return 0;
 495
 496   if (uentryList_isUndefined (s))
 497     return 1;
 498   if (uentryList_isUndefined (t))
 499     return -1;
 500
 501   sz = uentryList_size (s);
 502
 503   if (uentryList_size (t) != sz)
 504     {
 505       return (int_compare (sz, uentryList_size (t)));
 506     }
 507
 508   for (i = 0; i < sz; i++)
 509     {
 510       uentry se = s->elements[i];
 511       uentry te = t->elements[i];
 512       int namecmp = cstring_compare (uentry_rawName (se), uentry_rawName (te));
 513
 514       if (namecmp == 0)
 515         {
 516           int uc = uentry_compare (s->elements[i], t->elements[i]);
 517
 518           if (uc != 0)
 519             {
 520               return uc;
 521             }
 522         }
 523       else
 524         {
 525           return (namecmp);
 526         }
 527     }
 528
 529   return 0;
 530 }
 531
 532 /*@exposed@*/ uentry
 533 uentryList_current (uentryList s)
 534 {
 535   llassert (uentryList_isDefined (s));
 536   llassert (!(s->current < 0 || (s->current >= s->nelements)));
 537   return (s->elements[s->current]);
 538 }
 539
 540 cstring
 541 uentryList_dumpParams (uentryList s)
 542 {
 543   cstring st = cstring_undefined;
 544
 545   if (uentryList_isUndefined (s)) return st;
 546
 547   uentryList_elements (s, current)
 548     {
 549       st = message ("%q%q,", st, uentry_dumpParam (current));
 550   } end_uentryList_elements;
 551
 552   return st;
 553 }
 554
 555 /*@only@*/ cstring
 556 uentryList_dumpFields (uentryList s)
 557 {
 558   cstring st = cstring_undefined;
 559
 560   if (uentryList_isUndefined (s)) return st;
 561
 562   uentryList_elements (s, current)
 563   {
 564     if (!uentry_isVariable (current))
 565       {
 566         llassert (uentry_isFunction (current));
 567         st = message ("%q!%q,", st, uentry_dump (current));
 568       }
 569     else
 570       {
 571         st = message ("%q%q,", st, uentry_dump (current));
 572       }
 573   } end_uentryList_elements;
 574
 575   return st;
 576 }
 577
 578 /*@only@*/ uentryList
 579 uentryList_undumpFields (char **s, fileloc loc)
 580 {
 581   uentryList ul = uentryList_new ();
 582
 583   while (**s != '\0' && **s != '}')
 584     {
 585       if (**s == '!')
 586         {
 587           checkChar (s, '!');
 588           ul = uentryList_add (ul, uentry_undump (ekind_function, loc, s));
 589         }
 590       else
 591         {
 592           ul = uentryList_add (ul, uentry_undump (ekind_variable, loc, s));
 593         }
 594       checkChar (s, ',');
 595     }
 596
 597   checkChar (s, '}');
 598   return ul;
 599 }
 600
 601 /*@only@*/ uentryList
 602 uentryList_undump (char **s)
 603 {
 604   char c;
 605   uentryList pn = uentryList_new ();
 606   int paramno = 0;
 607
 608   c = **s;
 609
 610   while (c != '#' && c != '@' && c != ')')
 611     {
 612       uentry ue = uentry_undump (ekind_variable, g_currentloc, s);
 613
 614
 615       if (!uentry_isUndefined (ue))
 616         {
 617           pn = uentryList_add (pn, ue);
 618         }
 619       else
 620         {
 621           uentry_free (ue);
 622         }
 623
 624       checkChar (s, ',');
 625       c = **s;
 626       paramno++;
 627     }
 628
 629   checkChar (s, ')');
 630   return pn;
 631 }
 632
 633 void
 634 uentryList_reset (uentryList s)
 635 {
 636   if (uentryList_isUndefined (s)) return;
 637   s->current = 0;
 638 }
 639
 640 bool
 641 uentryList_isFinished (uentryList s)
 642 {
 643   if (uentryList_isUndefined (s)) return TRUE;
 644   return (s->current > s->nelements - 1);
 645 }
 646
 647 void
 648 uentryList_advanceSafe (uentryList s)
 649 {
 650   if (uentryList_isUndefined (s)) return;
 651
 652   s->current++;
 653
 654   if (s->current > s->nelements)
 655     {
 656       s->current = s->nelements;
 657     }
 658 }
 659
 660 int
 661 uentryList_size (uentryList s)
 662 {
 663   if (uentryList_isUndefined (s)) return 0;
 664
 665   if (s->nelements == 1 && ctype_isVoid (uentry_getType (s->elements[0])))
 666     return 0;
 667
 668   return s->nelements;
 669 }
 670
 671 bool
 672 uentryList_isMissingParams (uentryList s)
 673 {
 674   return (uentryList_isUndefined (s) || s->nelements == 0);
 675 }
 676
 677 bool uentryList_hasReturned (uentryList ul)
 678 {
 679   uentryList_elements (ul, current)
 680     {
 681       if (uentry_isReturned (current)) return TRUE;
 682     } end_uentryList_elements;
 683
 684   return FALSE;
 685 }
 686
 687 /*@exposed@*/ uentry
 688 uentryList_lookupField (uentryList f, cstring name)
 689 {
 690   int i = uentryList_lookupDirectName (f, name);
 691
 692   if (i >= 0)
 693     {
 694       return (uentryList_getN (f, i));
 695     }
 696   else
 697     {
 698       return uentry_undefined;
 699     }
 700 }
 701
 702 /*@only@*/ uentryList
 703   uentryList_mergeFields (/*@only@*/ uentryList f1, /*@only@*/ uentryList f2)
 704 {
 705   if (uentryList_isUndefined (f1))
 706     {
 707       return  (f2);
 708     }
 709
 710   if (uentryList_isDefined (f2))
 711     {
 712       uentryList_elements (f2, current)
 713         {
 714           uentry old = uentryList_lookupField (f1, uentry_rawName (current));
 715
 716           if (uentry_isValid (old))
 717             {
 718               voptgenerror
 719                 (FLG_SYNTAX,
 720                  message ("Field name reused: %s", uentry_rawName (current)),
 721                  uentry_whereDefined (current));
 722               llgenmsg (message ("Previous use of %s", uentry_rawName (current)),
 723                         uentry_whereDefined (old));
 724             }
 725
 726           /* okay to use exposed current since f2 is killed */
 727           /*@-exposetrans@*/ /*@-dependenttrans@*/
 728           f1 = uentryList_add (f1, current);
 729           /*@=exposetrans@*/ /*@=dependenttrans@*/
 730
 731         } end_uentryList_elements;
 732
 733       sfree (f2->elements);
 734       sfree (f2);
 735     }
 736
 737   return (f1);
 738 }
 739
 740 void
 741 uentryList_showFieldDifference (uentryList p1, uentryList p2)
 742 {
 743   uentry cp1, cp2;
 744   int index;
 745
 746   llassert (NOALIAS (p1, p2));
 747   llassert (uentryList_isDefined (p1));
 748   llassert (uentryList_isDefined (p2));
 749
 750   for (index = 0; index < p1->nelements; index++)
 751     {
 752       cp1 = p1->elements[index];
 753
 754       if (index == p2->nelements)
 755         {
 756           llgenindentmsg
 757             (message ("Field present in %s, missing in %rdeclaration: %q",
 758                       uentry_specDeclName (cp1),
 759                       uentry_isDeclared (cp1),
 760                       uentry_unparse (cp1)),
 761              uentry_whereEither (cp1));
 762           return;
 763         }
 764
 765       cp2 = p2->elements[index];
 766
 767       if (!(cstring_equal (uentry_rawName (cp1), uentry_rawName (cp2))))
 768         {
 769           llgenindentmsg
 770             (message ("Field %s in %s corresponds to %s in %rdeclaration",
 771                       uentry_rawName (cp1),
 772                       uentry_specOrDefName (cp1),
 773                       uentry_rawName (cp2),
 774                       uentry_isCodeDefined (cp1)),
 775              uentry_whereDefined (cp2));
 776           uentry_showWhereLastPlain (cp1);
 777           return;
 778         }
 779       else
 780         {
 781           if (!ctype_match (uentry_getType (cp1), uentry_getType (cp2)))
 782             {
 783               llgenindentmsg
 784                 (message ("Field %s %rdeclared as %s, %s as %s",
 785                           uentry_rawName (cp2),
 786                           uentry_isCodeDefined (cp1),
 787                           ctype_unparse (uentry_getType (cp1)),
 788                           uentry_specOrDefName (cp2),
 789                           ctype_unparse (uentry_getType (cp2))),
 790                  uentry_whereDefined (cp2));
 791               uentry_showWhereLastPlain (cp1);
 792               return;
 793             }
 794         }
 795     }
 796
 797   if (index != p2->nelements)
 798     {
 799       cp2 = p2->elements[index];
 800
 801       llgenindentmsg
 802         (message ("Extra field in new declaration: %q",
 803                   uentry_unparse (cp2)),
 804          uentry_whereEither (cp2));
 805
 806       return;
 807     }
 808
 809   llbug (message ("uentryList_showFieldDifference: match: %q / %q",
 810                   uentryList_unparse (p1), uentryList_unparse (p2)));
 811 }
 812
 813 bool
 814 uentryList_matchFields (uentryList p1, uentryList p2)
 815 {
 816   int index;
 817   uentry cp1, cp2;
 818
 819   if (p1 == p2)
 820     {
 821       return (TRUE);
 822     }
 823
 824   if (uentryList_isEmpty (p1) || uentryList_isEmpty (p2))
 825     {
 826       return (TRUE);
 827     }
 828
 829   if (uentryList_size (p1) != uentryList_size (p2))
 830     {
 831       return FALSE;
 832     }
 833
 834   for (index = 0; index < p1->nelements; index++)
 835     {
 836       cp1 = p1->elements[index];
 837       cp2 = p2->elements[index];
 838
 839       if (!(cstring_equal (uentry_rawName (cp1), uentry_rawName (cp2))
 840             && (ctype_almostEqual (uentry_getType (cp1), uentry_getType (cp2)))))
 841         {     /* was ctype_match! */
 842           return FALSE;
 843         }
 844     }
 845
 846   return TRUE;
 847 }
 848