src/cpphash.c

   1 /*
   2 ** Splint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2003 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 splint: info@splint.org
  21 ** To report a bug: splint-bug@splint.org
  22 ** For more information: http://www.splint.org
  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 "splintMacros.nf"
  55 # include "basic.h"
  56 # include <string.h>
  57 # include "cpplib.h"
  58 # include "cpphash.h"
  59
  60 typedef /*@null@*/ /*@only@*/ hashNode o_hashNode;
  61 typedef /*@null@*/ /*@only@*/ hashNode n_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 static /*@null@*/ hashNode hashNode_copy (/*@null@*/ hashNode,
  77                                           /*@null@*/ /*@dependent@*/ n_hashNode *p_hdr,
  78                                           /*@dependent@*/ /*@null@*/ /*@special@*/ hashNode p_prev)
  79      /*@*/ ;
  80
  81 void cppReader_saveHashtab ()
  82 {
  83   int i;
  84
  85   for (i = 0; i < CPP_HASHSIZE; i++)
  86     {
  87       ohashtab[i] = hashNode_copy (hashtab[i], &ohashtab[i], NULL);
  88     }
  89 }
  90
  91 void cppReader_restoreHashtab ()
  92 {
  93   int i;
  94
  95   for (i = 0; i < CPP_HASHSIZE; i++) {
  96     /* hashNode_delete (hashtab[i]); */
  97     hashtab[i] = hashNode_copy (ohashtab[i], &hashtab[i], NULL);
  98   }
  99 }
 100
 101 static void hashNode_delete (/*@only@*/ /*@null@*/ hashNode node)
 102 {
 103   if (node == NULL)
 104     {
 105       ;
 106     }
 107   else
 108     {
 109       hashNode_delete (node->next);
 110
 111       if (node->type == T_MACRO)
 112         {
 113           DEFINITION *d = node->value.defn;
 114           struct reflist *ap, *nextap;
 115
 116           for (ap = d->pattern; ap != NULL; ap = nextap)
 117             {
 118               nextap = ap->next;
 119               sfree (ap);
 120             }
 121
 122           if (d->nargs >= 0)
 123             {
 124               sfree (d->args.argnames);
 125             }
 126
 127           sfree (d);
 128         }
 129
 130       cstring_free (node->name);
 131       sfree (node);
 132     }
 133 }
 134
 135 /*@null@*/ hashNode hashNode_copy (hashNode node, hashNode *hdr,
 136                                    /*@dependent@*/ hashNode prev)
 137 {
 138   if (node == NULL)
 139     {
 140       return NULL;
 141     }
 142   else
 143     {
 144       hashNode res = dmalloc (sizeof (*res));
 145
 146       res->next = hashNode_copy (node->next, hdr, res);
 147       res->prev = prev;
 148
 149       res->bucket_hdr = hdr;
 150       res->type = node->type;
 151       res->length = node->length;
 152       res->name = cstring_copy (node->name);
 153
 154       if (node->type == T_MACRO)
 155         {
 156           DEFINITION *d = node->value.defn;
 157           DEFINITION *nd = dmalloc (sizeof (*nd));
 158
 159           res->value.defn = nd;
 160           nd->nargs = d->nargs;
 161
 162           nd->length = d->length;
 163           nd->predefined = d->predefined;
 164           nd->expansion = d->expansion;
 165           nd->line = d->line;
 166           nd->file = d->file;
 167
 168           if (d->pattern != NULL)
 169             {
 170               struct reflist *ap, *nextap;
 171               struct reflist **last = &nd->pattern;
 172
 173               for (ap = d->pattern; ap != NULL; ap = nextap)
 174                 {
 175                   struct reflist *npattern = dmalloc (sizeof (* (nd->pattern)));
 176
 177                   nextap = ap->next;
 178
 179                   if (ap == d->pattern)
 180                     {
 181                       *last = npattern;
 182                       /*@-branchstate@*/
 183                     } /*@=branchstate@*/ /* npattern is propagated through loop */
 184
 185                   last = & (npattern->next);
 186                   npattern->next = NULL; /* will get filled in */
 187                   npattern->stringify = d->pattern->stringify;
 188                   npattern->raw_before = d->pattern->raw_before;
 189                   npattern->raw_after = d->pattern->raw_after;
 190                   npattern->rest_args = d->pattern->rest_args;
 191                   npattern->argno = d->pattern->argno;
 192                   /*@-mustfree@*/
 193                 }
 194               /*@=mustfree@*/
 195             }
 196           else
 197             {
 198               nd->pattern = NULL;
 199             }
 200
 201           if (d->nargs >= 0)
 202             {
 203               llassert (d->args.argnames != NULL);
 204
 205               nd->args.argnames = mstring_copy (d->args.argnames);
 206             }
 207           else
 208             {
 209               /*
 210               ** This fix found by:
 211               **
 212               **    Date: Mon, 31 May 1999 15:10:50 +0900 (JST)
 213               **    From: "N.Komazaki" <koma@focs.sei.co.jp>
 214               */
 215
 216               /*! why doesn't splint report an error for this? */
 217               nd->args.argnames = mstring_createEmpty ();
 218             }
 219         }
 220       else
 221         {
 222           if (node->type == T_CONST)
 223             {
 224               res->value.ival = node->value.ival;
 225             }
 226           else if (node->type == T_PCSTRING)
 227             {
 228               res->value.cpval = mstring_copy (node->value.cpval);
 229               llassert (res->value.cpval != NULL);
 230             }
 231           else
 232             {
 233               res->value = node->value;
 234             }
 235         }
 236
 237       /*@-uniondef@*/ /*@-compdef@*/ /* res->prev is not defined */
 238       return res;
 239       /*@=uniondef@*/ /*@=compdef@*/
 240     }
 241 }
 242
 243 /* Return hash function on name.  must be compatible with the one
 244    computed a step at a time, elsewhere  */
 245
 246 int
 247 cpphash_hashCode (const char *name, size_t len, int hashsize)
 248 {
 249   unsigned int r = 0;
 250
 251   while (len-- != 0)
 252     {
 253       r = hashStep (r, *name++);
 254     }
 255
 256   return (int) (makePositive (r) % hashsize);
 257 }
 258
 259 /*
 260 ** Find the most recent hash node for name name (ending with first
 261 ** non-identifier char) cpphash_installed by install
 262 **
 263 ** If len is >= 0, it is the length of the name.
 264 ** Otherwise, compute the length by scanning the entire name.
 265 **
 266 ** If hash is >= 0, it is the precomputed hash code.
 267 ** Otherwise, compute the hash code.
 268 */
 269
 270 /*@null@*/ hashNode cpphash_lookup (char *name, int len, int hash)
 271 {
 272   const char *bp;
 273   hashNode bucket;
 274
 275   if (len < 0)
 276     {
 277       for (bp = name; isIdentifierChar (*bp); bp++)
 278         {
 279           ;
 280         }
 281
 282       len = bp - name;
 283     }
 284
 285   if (hash < 0)
 286     {
 287       hash = cpphash_hashCode (name, size_fromInt (len), CPP_HASHSIZE);
 288     }
 289
 290   bucket = hashtab[hash];
 291
 292   while (bucket != NULL)
 293     {
 294       if (bucket->length == size_fromInt (len) &&
 295           cstring_equalLen (bucket->name, cstring_fromChars (name), size_fromInt (len)))
 296         {
 297           return bucket;
 298         }
 299
 300       bucket = bucket->next;
 301     }
 302
 303   return NULL;
 304 }
 305
 306 /*@null@*/ hashNode cpphash_lookupExpand (char *name, int len, int hash, bool forceExpand)
 307 {
 308   hashNode node = cpphash_lookup (name, len, hash);
 309
 310   DPRINTF (("Lookup expand: %s", name));
 311
 312   if (node != NULL)
 313     {
 314       if (node->type == T_MACRO)
 315         {
 316           DEFINITION *defn = (DEFINITION *) node->value.defn;
 317
 318           DPRINTF (("Check macro..."));
 319
 320           if (defn->noExpand && !forceExpand) {
 321             DPRINTF (("No expand!"));
 322             return NULL;
 323           }
 324         }
 325     }
 326
 327   return node;
 328 }
 329
 330 /*
 331  * Delete a hash node.  Some weirdness to free junk from macros.
 332  * More such weirdness will have to be added if you define more hash
 333  * types that need it.
 334  */
 335
 336 /* Note that the DEFINITION of a macro is removed from the hash table
 337    but its storage is not freed.  This would be a storage leak
 338    except that it is not reasonable to keep undefining and redefining
 339    large numbers of macros many times.
 340    In any case, this is necessary, because a macro can be #undef'd
 341    in the middle of reading the arguments to a call to it.
 342    If #undef freed the DEFINITION, that would crash.  */
 343
 344 void
 345 cppReader_deleteMacro (hashNode hp)
 346 {
 347   if (hp->prev != NULL)
 348     {
 349       /*@-mustfree@*/
 350       hp->prev->next = hp->next;
 351       /*@=mustfree@*/
 352       /*@-branchstate@*/
 353     } /*@=branchstate@*/
 354
 355   if (hp->next != NULL)
 356     {
 357       hp->next->prev = hp->prev;
 358     }
 359
 360   /* make sure that the bucket chain header that
 361      the deleted guy was on points to the right thing afterwards.  */
 362
 363   llassert (hp != NULL);
 364   llassert (hp->bucket_hdr != NULL);
 365
 366   if (hp == *hp->bucket_hdr) {
 367     *hp->bucket_hdr = hp->next;
 368   }
 369
 370   if (hp->type == T_MACRO)
 371     {
 372       DEFINITION *d = hp->value.defn;
 373       struct reflist *ap, *nextap;
 374
 375       for (ap = d->pattern; ap != NULL; ap = nextap)
 376         {
 377           nextap = ap->next;
 378           sfree (ap);
 379         }
 380
 381       if (d->nargs >= 0)
 382         {
 383           sfree (d->args.argnames);
 384         }
 385     }
 386
 387   /*@-dependenttrans@*/ /*@-exposetrans@*/ /*@-compdestroy@*/
 388   sfree (hp);
 389   /*@=dependenttrans@*/ /*@=exposetrans@*/ /*@=compdestroy@*/
 390 }
 391
 392 /* Install a name in the main hash table, even if it is already there.
 393      name stops with first non alphanumeric, except leading '#'.
 394    caller must check against redefinition if that is desired.
 395    cppReader_deleteMacro () removes things installed by install () in fifo order.
 396    this is important because of the `defined' special symbol used
 397    in #if, and also if pushdef/popdef directives are ever implemented.
 398
 399    If LEN is >= 0, it is the length of the name.
 400    Otherwise, compute the length by scanning the entire name.
 401
 402    If HASH is >= 0, it is the precomputed hash code.
 403    Otherwise, compute the hash code.  */
 404
 405 hashNode cpphash_install (char *name, int len, enum node_type type,
 406                              int ivalue, char *value, int hash)
 407 {
 408   hashNode hp;
 409   int bucket;
 410   char *p;
 411
 412   DPRINTF (("Install: %s / %d", name, len));
 413
 414   if (len < 0) {
 415     p = name;
 416
 417     while (isIdentifierChar (*p))
 418       {
 419         p++;
 420       }
 421
 422     len = p - name;
 423   }
 424
 425   if (hash < 0)
 426     {
 427       hash = cpphash_hashCode (name, size_fromInt (len), CPP_HASHSIZE);
 428     }
 429
 430   hp = (hashNode) dmalloc (sizeof (*hp));
 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 = size_fromInt (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   hp->name = cstring_clip (cstring_fromCharsNew (name), size_fromInt (len));
 458
 459   DPRINTF (("Name: *%s*", hp->name));
 460   /*@-mustfree@*/ /*@-uniondef@*/ /*@-compdef@*/ /*@-compmempass@*/
 461   return hp;
 462   /*@=mustfree@*/ /*@=uniondef@*/ /*@=compdef@*/ /*@=compmempass@*/
 463 }
 464
 465 hashNode cpphash_installMacro (char *name, size_t len,
 466                                  struct definition *defn, int hash)
 467 {
 468   DPRINTF (("install macro: %s", name));
 469   return cpphash_install (name, size_toInt (len), T_MACRO, 0, (char  *) defn, hash);
 470 }
 471
 472 void
 473 cppReader_hashCleanup (void)
 474 {
 475   int i;
 476
 477   for (i = CPP_HASHSIZE; --i >= 0; )
 478     {
 479       while (hashtab[i] != NULL)
 480         {
 481           cppReader_deleteMacro (hashtab[i]);
 482         }
 483     }
 484 }