src/cpphash.c

   1 /*
   2 ** LCLint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2001 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 ** cpphash.c
  26 **
  27 ** Pre-processor hash table.  Derived from gnu cpp.
  28 */
  29
  30 /* Part of CPP library.  (Macro hash table support.)
  31    Copyright (C) 1986, 87, 89, 92-95, 1996 Free Software Foundation, Inc.
  32    Written by Per Bothner, 1994.
  33    Based on CCCP program by by Paul Rubin, June 1986
  34    Adapted to ANSI C, Richard Stallman, Jan 1987
  35
  36 This program is free software; you can redistribute it and/or modify it
  37 under the terms of the GNU General Public License as published by the
  38 Free Software Foundation; either version 2, or (at your option) any
  39 later version.
  40
  41 This program is distributed in the hope that it will be useful,
  42 but WITHOUT ANY WARRANTY; without even the implied warranty of
  43 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  44 GNU General Public License for more details.
  45
  46 You should have received a copy of the GNU General Public License
  47 along with this program; if not, write to the Free Software
  48 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  49
  50  In other words, you are welcome to use, share and improve this program.
  51  You are forbidden to forbid anyone else to use, share and improve
  52  what you give them.   Help stamp out software-hoarding!  */
  53
  54 # include "lclintMacros.nf"
  55 # include "llbasic.h"
  56 # include <string.h>
  57 # include "cpp.h"
  58 # include "cpplib.h"
  59 # include "cpphash.h"
  60
  61 typedef /*@null@*/ /*@only@*/ HASHNODE *o_HASHNODE;
  62
  63 static o_HASHNODE hashtab[CPP_HASHSIZE];
  64 static o_HASHNODE ohashtab[CPP_HASHSIZE];
  65
  66 static void HashNode_delete (/*@null@*/ /*@only@*/ HASHNODE *);
  67
  68 /* p_prev need not be defined, but isn't defined by HashNode_copy */
  69
  70 /*@function static unsigned int hashStep (unsigned, char) modifies nothing ; @*/
  71 # define hashStep(old, c) (((old) << 2) + (unsigned int) (c))
  72
  73 /*@function static unsigned int makePositive (unsigned int) modifies nothing ; @*/
  74 # define makePositive(v) ((v) & 0x7fffffff) /* make number positive */
  75
  76 typedef /*@null@*/ HASHNODE n_HASHNODE;
  77
  78 static /*@null@*/ HASHNODE *
  79    HashNode_copy (/*@null@*/ HASHNODE *,
  80                   /*@null@*/ /*@dependent@*/ n_HASHNODE **p_hdr,
  81                   /*@dependent@*/ /*@null@*/ /*@special@*/ HASHNODE *p_prev)
  82      /*@*/ ;
  83
  84 void cppReader_saveHashtab ()
  85 {
  86   int i;
  87
  88   for (i = 0; i < CPP_HASHSIZE; i++)
  89     {
  90       ohashtab[i] = HashNode_copy (hashtab[i], &ohashtab[i], NULL);
  91     }
  92 }
  93
  94 void cppReader_restoreHashtab ()
  95 {
  96   int i;
  97
  98   for (i = 0; i < CPP_HASHSIZE; i++) {
  99     /* HashNode_delete (hashtab[i]); */
 100     hashtab[i] = HashNode_copy (ohashtab[i], &hashtab[i], NULL);
 101   }
 102 }
 103
 104 static void HashNode_delete (/*@only@*/ /*@null@*/ HASHNODE *node)
 105 {
 106   if (node == NULL)
 107     {
 108       ;
 109     }
 110   else
 111     {
 112       HashNode_delete (node->next);
 113
 114       if (node->type == T_MACRO)
 115         {
 116           DEFINITION *d = node->value.defn;
 117           struct reflist *ap, *nextap;
 118
 119           for (ap = d->pattern; ap != NULL; ap = nextap)
 120             {
 121               nextap = ap->next;
 122               sfree (ap);
 123             }
 124
 125           if (d->nargs >= 0)
 126             {
 127               sfree (d->args.argnames);
 128             }
 129
 130           sfree (d);
 131         }
 132
 133       cstring_free (node->name);
 134       sfree (node);
 135     }
 136 }
 137
 138 /*@null@*/ HASHNODE *HashNode_copy (HASHNODE *node, HASHNODE **hdr,
 139                                     /*@dependent@*/ HASHNODE *prev)
 140 {
 141   if (node == NULL)
 142     {
 143       return NULL;
 144     }
 145   else
 146     {
 147       HASHNODE *res = dmalloc (sizeof (*res));
 148
 149       res->next = HashNode_copy (node->next, hdr, res);
 150       res->prev = prev;
 151
 152       res->bucket_hdr = hdr;
 153       res->type = node->type;
 154       res->length = node->length;
 155       res->name = cstring_copy (node->name);
 156
 157       if (node->type == T_MACRO)
 158         {
 159           DEFINITION *d = node->value.defn;
 160           DEFINITION *nd = dmalloc (sizeof (*nd));
 161
 162           res->value.defn = nd;
 163           nd->nargs = d->nargs;
 164
 165           nd->length = d->length;
 166           nd->predefined = d->predefined;
 167           nd->expansion = d->expansion;
 168           nd->line = d->line;
 169           nd->file = d->file;
 170
 171           if (d->pattern != NULL)
 172             {
 173               struct reflist *ap, *nextap;
 174               struct reflist **last = &nd->pattern;
 175
 176               for (ap = d->pattern; ap != NULL; ap = nextap)
 177                 {
 178                   struct reflist *npattern = dmalloc (sizeof (*(nd->pattern)));
 179
 180                   nextap = ap->next;
 181
 182                   if (ap == d->pattern)
 183                     {
 184                       *last = npattern;
 185                       /*@-branchstate@*/
 186                     } /*@=branchstate@*/ /* npattern is propagated through loop */
 187
 188                   last = &(npattern->next);
 189                   npattern->next = NULL; /* will get filled in */
 190                   npattern->stringify = d->pattern->stringify;
 191                   npattern->raw_before = d->pattern->raw_before;
 192                   npattern->raw_after = d->pattern->raw_after;
 193                   npattern->rest_args = d->pattern->rest_args;
 194                   npattern->argno = d->pattern->argno;
 195                   /*@-mustfree@*/
 196                 }
 197               /*@=mustfree@*/
 198             }
 199           else
 200             {
 201               nd->pattern = NULL;
 202             }
 203
 204           if (d->nargs >= 0)
 205             {
 206               llassert (d->args.argnames != NULL);
 207
 208               nd->args.argnames = mstring_copy (d->args.argnames);
 209             }
 210           else
 211             {
 212               /*
 213               ** This fix found by:
 214               **
 215               **    Date: Mon, 31 May 1999 15:10:50 +0900 (JST)
 216               **    From: "N.Komazaki" <koma@focs.sei.co.jp>
 217               */
 218
 219               /*! why doesn't lclint report an error for this? */
 220               nd->args.argnames = mstring_createEmpty ();
 221             }
 222         }
 223       else
 224         {
 225           if (node->type == T_CONST)
 226             {
 227               res->value.ival = node->value.ival;
 228             }
 229           else if (node->type == T_PCSTRING)
 230             {
 231               res->value.cpval = mstring_copy (node->value.cpval);
 232               llassert (res->value.cpval != NULL);
 233             }
 234           else
 235             {
 236               res->value = node->value;
 237             }
 238         }
 239
 240       /*@-uniondef@*/ /*@-compdef@*/ /* res->prev is not defined */
 241       return res;
 242       /*@=uniondef@*/ /*@=compdef@*/
 243     }
 244 }
 245
 246 /* Return hash function on name.  must be compatible with the one
 247    computed a step at a time, elsewhere  */
 248
 249 int
 250 hashf (const char *name, int len, int hashsize)
 251 {
 252   unsigned int r = 0;
 253
 254   while (len-- != 0)
 255     {
 256       r = hashStep (r, *name++);
 257     }
 258
 259   return (int) (makePositive (r) % hashsize);
 260 }
 261
 262 /*
 263 ** Find the most recent hash node for name name (ending with first
 264 ** non-identifier char) cppReader_installed by install
 265 **
 266 ** If LEN is >= 0, it is the length of the name.
 267 ** Otherwise, compute the length by scanning the entire name.
 268 **
 269 ** If HASH is >= 0, it is the precomputed hash code.
 270 ** Otherwise, compute the hash code.
 271 */
 272
 273 /*@null@*/ HASHNODE *cppReader_lookup (char *name, int len, int hash)
 274 {
 275   const char *bp;
 276   HASHNODE *bucket;
 277
 278   if (len < 0)
 279     {
 280       for (bp = name; isIdentifierChar (*bp); bp++)
 281         {
 282           ;
 283         }
 284
 285       len = bp - name;
 286     }
 287
 288   if (hash < 0)
 289     {
 290       hash = hashf (name, len, CPP_HASHSIZE);
 291     }
 292
 293   bucket = hashtab[hash];
 294
 295   while (bucket != NULL)
 296     {
 297       if (bucket->length == len &&
 298           cstring_equalLen (bucket->name, cstring_fromChars (name), len))
 299         {
 300           return bucket;
 301         }
 302
 303       bucket = bucket->next;
 304     }
 305
 306   return NULL;
 307 }
 308
 309 /*@null@*/ HASHNODE *cppReader_lookupExpand (char *name, int len, int hash)
 310 {
 311   HASHNODE *node = cppReader_lookup (name, len, hash);
 312
 313   DPRINTF (("Lookup expand: %s", name));
 314
 315   if (node != NULL)
 316     {
 317       if (node->type == T_MACRO)
 318         {
 319           DEFINITION *defn = (DEFINITION *) node->value.defn;
 320
 321           DPRINTF (("Check macro..."));
 322
 323           if (defn->noExpand) {
 324             DPRINTF (("No expand!"));
 325             return NULL;
 326           }
 327         }
 328     }
 329
 330   return node;
 331 }
 332
 333 /*
 334  * Delete a hash node.  Some weirdness to free junk from macros.
 335  * More such weirdness will have to be added if you define more hash
 336  * types that need it.
 337  */
 338
 339 /* Note that the DEFINITION of a macro is removed from the hash table
 340    but its storage is not freed.  This would be a storage leak
 341    except that it is not reasonable to keep undefining and redefining
 342    large numbers of macros many times.
 343    In any case, this is necessary, because a macro can be #undef'd
 344    in the middle of reading the arguments to a call to it.
 345    If #undef freed the DEFINITION, that would crash.  */
 346
 347 void
 348 cppReader_deleteMacro (HASHNODE *hp)
 349 {
 350   if (hp->prev != NULL)
 351     {
 352       /*@-mustfree@*/
 353       hp->prev->next = hp->next;
 354       /*@=mustfree@*/
 355       /*@-branchstate@*/
 356     } /*@=branchstate@*/
 357
 358   if (hp->next != NULL)
 359     {
 360       hp->next->prev = hp->prev;
 361     }
 362
 363   /* make sure that the bucket chain header that
 364      the deleted guy was on points to the right thing afterwards.  */
 365   if (hp == *hp->bucket_hdr) {
 366     *hp->bucket_hdr = hp->next;
 367   }
 368
 369   if (hp->type == T_MACRO)
 370     {
 371       DEFINITION *d = hp->value.defn;
 372       struct reflist *ap, *nextap;
 373
 374       for (ap = d->pattern; ap != NULL; ap = nextap)
 375         {
 376           nextap = ap->next;
 377           sfree (ap);
 378         }
 379
 380       if (d->nargs >= 0)
 381         {
 382           sfree (d->args.argnames);
 383         }
 384     }
 385
 386   /*@-dependenttrans@*/ /*@-exposetrans@*/ /*@-compdestroy@*/
 387   sfree (hp);
 388   /*@=dependenttrans@*/ /*@=exposetrans@*/ /*@=compdestroy@*/
 389 }
 390
 391 /* Install a name in the main hash table, even if it is already there.
 392      name stops with first non alphanumeric, except leading '#'.
 393    caller must check against redefinition if that is desired.
 394    cppReader_deleteMacro () removes things installed by install () in fifo order.
 395    this is important because of the `defined' special symbol used
 396    in #if, and also if pushdef/popdef directives are ever implemented.
 397
 398    If LEN is >= 0, it is the length of the name.
 399    Otherwise, compute the length by scanning the entire name.
 400
 401    If HASH is >= 0, it is the precomputed hash code.
 402    Otherwise, compute the hash code.  */
 403
 404 HASHNODE *cppReader_install (char *name, int len, enum node_type type,
 405                              int ivalue, char *value, int hash)
 406 {
 407   HASHNODE *hp;
 408   int i, bucket;
 409   char *p, *q;
 410
 411   if (len < 0) {
 412     p = name;
 413
 414     while (isIdentifierChar (*p))
 415       {
 416         p++;
 417       }
 418
 419     len = p - name;
 420   }
 421
 422   if (hash < 0)
 423     {
 424       hash = hashf (name, len, CPP_HASHSIZE);
 425     }
 426
 427   i = sizeof (*hp) + len + 1;
 428
 429
 430   hp = (HASHNODE *) dmalloc (size_fromInt (i));
 431   bucket = hash;
 432   hp->bucket_hdr = &hashtab[bucket];
 433
 434   hp->next = hashtab[bucket];
 435   hp->prev = NULL;
 436
 437   if (hp->next != NULL)
 438     {
 439       hp->next->prev = hp;
 440     }
 441
 442   hashtab[bucket] = hp;
 443
 444   hp->type = type;
 445   hp->length = len;
 446
 447   if (hp->type == T_CONST)
 448     {
 449       hp->value.ival = ivalue;
 450       llassert (value == NULL);
 451     }
 452   else
 453     {
 454       hp->value.cpval = value;
 455     }
 456
 457   {
 458     char *tmp = ((char *) hp) + sizeof (*hp);
 459     p = tmp;
 460     q = name;
 461
 462     for (i = 0; i < len; i++)
 463       {
 464         *p++ = *q++;
 465       }
 466
 467     tmp[len] = '\0';
 468     hp->name = cstring_fromChars (tmp);
 469   }
 470
 471   /*@-mustfree@*/ /*@-uniondef@*/ /*@-compdef@*/
 472   return hp;
 473   /*@=mustfree@*/ /*@=uniondef@*/ /*@=compdef@*/
 474 }
 475
 476 HASHNODE *cppReader_installMacro (char *name, int len,
 477                                   struct definition *defn, int hash)
 478 {
 479   return cppReader_install (name, len, T_MACRO, 0, (char  *) defn, hash);
 480 }
 481
 482 void
 483 cppReader_hashCleanup (void)
 484 {
 485   int i;
 486
 487   for (i = CPP_HASHSIZE; --i >= 0; )
 488     {
 489       while (hashtab[i] != NULL)
 490         {
 491           cppReader_deleteMacro (hashtab[i]);
 492         }
 493     }
 494 }