src/symtab.c

   1 /* GNU m4 -- A simple macro processor
   2
   3    Copyright (C) 1989, 1990, 1991, 1992, 1993, 1994, 2003, 2006, 2007 Free
   4    Software Foundation, Inc.
   5
   6    This file is part of GNU M4.
   7
   8    GNU M4 is free software: you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation, either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    GNU M4 is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20 */
  21
  22 /* This file handles all the low level work around the symbol table.  The
  23    symbol table is a simple chained hash table.  Each symbol is described
  24    by a struct symbol, which is placed in the hash table based upon the
  25    symbol name.  Symbols that hash to the same entry in the table are
  26    kept on a list, sorted by name.  As a special case, to facilitate the
  27    "pushdef" and "popdef" builtins, a symbol can be several times in the
  28    symbol table, one for each definition.  Since the name is the same,
  29    all the entries for the symbol will be on the same list, and will
  30    also, because the list is sorted, be adjacent.  All the entries for a
  31    name are simply ordered on the list by age.  The current definition
  32    will then always be the first found.  */
  33
  34 #include "m4.h"
  35 #include <limits.h>
  36
  37 #ifdef DEBUG_SYM
  38 /* When evaluating hash table performance, this profiling code shows
  39    how many collisions were encountered.  */
  40
  41 struct profile
  42 {
  43   int entry; /* Number of times lookup_symbol called with this mode.  */
  44   int comparisons; /* Number of times strcmp was called.  */
  45   int misses; /* Number of times strcmp did not return 0.  */
  46   long long bytes; /* Number of bytes compared.  */
  47 };
  48
  49 static struct profile profiles[5];
  50 static symbol_lookup current_mode;
  51
  52 /* On exit, show a profile of symbol table performance.  */
  53 static void
  54 show_profile (void)
  55 {
  56   int i;
  57   for (i = 0; i < 5; i++)
  58     {
  59       xfprintf(stderr, "m4: lookup mode %d called %d times, %d compares, "
  60                "%d misses, %lld bytes\n",
  61                i, profiles[i].entry, profiles[i].comparisons,
  62                profiles[i].misses, profiles[i].bytes);
  63     }
  64 }
  65
  66 /* Like strcmp (S1, S2), but also track profiling statistics.  */
  67 static int
  68 profile_strcmp (const char *s1, const char *s2)
  69 {
  70   int i = 1;
  71   int result;
  72   while (*s1 && *s1 == *s2)
  73     {
  74       s1++;
  75       s2++;
  76       i++;
  77     }
  78   result = (unsigned char) *s1 - (unsigned char) *s2;
  79   profiles[current_mode].comparisons++;
  80   if (result != 0)
  81     profiles[current_mode].misses++;
  82   profiles[current_mode].bytes += i;
  83   return result;
  84 }
  85
  86 # define strcmp profile_strcmp
  87 #endif /* DEBUG_SYM */
  88
  89 \f
  90 /*----------------------------------------------------------------------.
  91 | Initialise the symbol table, by allocating the necessary storage, and |
  92 | zeroing all the entries.                                              |
  93 `----------------------------------------------------------------------*/
  94
  95 /* Pointer to symbol table.  */
  96 symbol **symtab;
  97
  98 void
  99 symtab_init (void)
 100 {
 101   size_t i;
 102   symbol **s;
 103
 104   s = symtab = (symbol **) xnmalloc (hash_table_size, sizeof (symbol *));
 105
 106   for (i = 0; i < hash_table_size; i++)
 107     s[i] = NULL;
 108
 109 #ifdef DEBUG_SYM
 110   {
 111     int e = atexit(show_profile);
 112     if (e != 0)
 113       M4ERROR ((warning_status, 0,
 114                 "INTERNAL ERROR: unable to show symtab profile"));
 115   }
 116 #endif /* DEBUG_SYM */
 117 }
 118
 119 /*--------------------------------------------------.
 120 | Return a hashvalue for a string, from GNU-emacs.  |
 121 `--------------------------------------------------*/
 122
 123 static size_t
 124 hash (const char *s)
 125 {
 126   register size_t val = 0;
 127
 128   register const char *ptr = s;
 129   register char ch;
 130
 131   while ((ch = *ptr++) != '\0')
 132     val = (val << 7) + (val >> (sizeof (val) * CHAR_BIT - 7)) + ch;
 133   return val;
 134 }
 135
 136 /*--------------------------------------------.
 137 | Free all storage associated with a symbol.  |
 138 `--------------------------------------------*/
 139
 140 void
 141 free_symbol (symbol *sym)
 142 {
 143   if (SYMBOL_PENDING_EXPANSIONS (sym) > 0)
 144     SYMBOL_DELETED (sym) = true;
 145   else
 146     {
 147       free (SYMBOL_NAME (sym));
 148       if (SYMBOL_TYPE (sym) == TOKEN_TEXT)
 149         free (SYMBOL_TEXT (sym));
 150       free (sym);
 151     }
 152 }
 153
 154 /*-------------------------------------------------------------------.
 155 | Search in, and manipulation of the symbol table, are all done by   |
 156 | lookup_symbol ().  It basically hashes NAME to a list in the       |
 157 | symbol table, and searches this list for the first occurrence of a |
 158 | symbol with the name.                                              |
 159 |                                                                    |
 160 | The MODE parameter determines what lookup_symbol () will do.  It   |
 161 | can either just do a lookup, do a lookup and insert if not         |
 162 | present, do an insertion even if the name is already in the list,  |
 163 | delete the first occurrence of the name on the list, or delete all |
 164 | occurrences of the name on the list.                               |
 165 `-------------------------------------------------------------------*/
 166
 167 symbol *
 168 lookup_symbol (const char *name, symbol_lookup mode)
 169 {
 170   size_t h;
 171   int cmp = 1;
 172   symbol *sym, *prev;
 173   symbol **spp;
 174
 175 #if DEBUG_SYM
 176   current_mode = mode;
 177   profiles[mode].entry++;
 178 #endif /* DEBUG_SYM */
 179
 180   h = hash (name);
 181   sym = symtab[h % hash_table_size];
 182
 183   for (prev = NULL; sym != NULL; prev = sym, sym = sym->next)
 184     {
 185       cmp = strcmp (SYMBOL_NAME (sym), name);
 186       if (cmp >= 0)
 187         break;
 188     }
 189
 190   /* If just searching, return status of search.  */
 191
 192   if (mode == SYMBOL_LOOKUP)
 193     return cmp == 0 ? sym : NULL;
 194
 195   /* Symbol not found.  */
 196
 197   spp = (prev != NULL) ?  &prev->next : &symtab[h % hash_table_size];
 198
 199   switch (mode)
 200     {
 201
 202     case SYMBOL_INSERT:
 203
 204       /* If the name was found in the table, check whether it is still in
 205          use by a pending expansion.  If so, replace the table element with
 206          a new one; if not, just return the symbol.  If not found, just
 207          insert the name, and return the new symbol.  */
 208
 209       if (cmp == 0 && sym != NULL)
 210         {
 211           if (SYMBOL_PENDING_EXPANSIONS (sym) > 0)
 212             {
 213               symbol *old = sym;
 214               SYMBOL_DELETED (old) = true;
 215
 216               sym = (symbol *) xmalloc (sizeof (symbol));
 217               SYMBOL_TYPE (sym) = TOKEN_VOID;
 218               SYMBOL_TRACED (sym) = SYMBOL_TRACED (old);
 219               SYMBOL_NAME (sym) = xstrdup (name);
 220               SYMBOL_SHADOWED (sym) = false;
 221               SYMBOL_MACRO_ARGS (sym) = false;
 222               SYMBOL_BLIND_NO_ARGS (sym) = false;
 223               SYMBOL_DELETED (sym) = false;
 224               SYMBOL_PENDING_EXPANSIONS (sym) = 0;
 225
 226               SYMBOL_NEXT (sym) = SYMBOL_NEXT (old);
 227               SYMBOL_NEXT (old) = NULL;
 228               (*spp) = sym;
 229             }
 230           return sym;
 231         }
 232       /* Fall through.  */
 233
 234     case SYMBOL_PUSHDEF:
 235
 236       /* Insert a name in the symbol table.  If there is already a symbol
 237          with the name, insert this in front of it, and mark the old
 238          symbol as "shadowed".  */
 239
 240       sym = (symbol *) xmalloc (sizeof (symbol));
 241       SYMBOL_TYPE (sym) = TOKEN_VOID;
 242       SYMBOL_TRACED (sym) = false;
 243       SYMBOL_NAME (sym) = xstrdup (name);
 244       SYMBOL_SHADOWED (sym) = false;
 245       SYMBOL_MACRO_ARGS (sym) = false;
 246       SYMBOL_BLIND_NO_ARGS (sym) = false;
 247       SYMBOL_DELETED (sym) = false;
 248       SYMBOL_PENDING_EXPANSIONS (sym) = 0;
 249
 250       SYMBOL_NEXT (sym) = *spp;
 251       (*spp) = sym;
 252
 253       if (mode == SYMBOL_PUSHDEF && cmp == 0)
 254         {
 255           SYMBOL_SHADOWED (SYMBOL_NEXT (sym)) = true;
 256           SYMBOL_TRACED (sym) = SYMBOL_TRACED (SYMBOL_NEXT (sym));
 257         }
 258       return sym;
 259
 260     case SYMBOL_DELETE:
 261     case SYMBOL_POPDEF:
 262
 263       /* Delete occurrences of symbols with NAME.  SYMBOL_DELETE kills
 264          all definitions, SYMBOL_POPDEF kills only the first.
 265          However, if the last instance of a symbol is marked for
 266          tracing, reinsert a placeholder in the table.  And if the
 267          definition is still in use, let the caller free the memory
 268          after it is done with the symbol.  */
 269
 270       if (cmp != 0 || sym == NULL)
 271         return NULL;
 272       {
 273         bool traced = false;
 274         if (SYMBOL_NEXT (sym) != NULL
 275             && SYMBOL_SHADOWED (SYMBOL_NEXT (sym))
 276             && mode == SYMBOL_POPDEF)
 277           {
 278             SYMBOL_SHADOWED (SYMBOL_NEXT (sym)) = false;
 279             SYMBOL_TRACED (SYMBOL_NEXT (sym)) = SYMBOL_TRACED (sym);
 280           }
 281         else
 282           traced = SYMBOL_TRACED (sym);
 283         do
 284           {
 285             *spp = SYMBOL_NEXT (sym);
 286             free_symbol (sym);
 287             sym = *spp;
 288           }
 289         while (*spp != NULL && SYMBOL_SHADOWED (*spp)
 290                && mode == SYMBOL_DELETE);
 291         if (traced)
 292           {
 293             sym = (symbol *) xmalloc (sizeof (symbol));
 294             SYMBOL_TYPE (sym) = TOKEN_VOID;
 295             SYMBOL_TRACED (sym) = true;
 296             SYMBOL_NAME (sym) = xstrdup (name);
 297             SYMBOL_SHADOWED (sym) = false;
 298             SYMBOL_MACRO_ARGS (sym) = false;
 299             SYMBOL_BLIND_NO_ARGS (sym) = false;
 300             SYMBOL_DELETED (sym) = false;
 301             SYMBOL_PENDING_EXPANSIONS (sym) = 0;
 302
 303             SYMBOL_NEXT (sym) = *spp;
 304             (*spp) = sym;
 305           }
 306       }
 307       return NULL;
 308
 309     default:
 310       M4ERROR ((warning_status, 0,
 311                 "INTERNAL ERROR: invalid mode to symbol_lookup ()"));
 312       abort ();
 313     }
 314 }
 315
 316 /*-----------------------------------------------------------------.
 317 | The following function is used for the cases where we want to do |
 318 | something to each and every symbol in the table.  The function   |
 319 | hack_all_symbols () traverses the symbol table, and calls a      |
 320 | specified function FUNC for each symbol in the table.  FUNC is   |
 321 | called with a pointer to the symbol, and the DATA argument.      |
 322 |                                                                  |
 323 | FUNC may safely call lookup_symbol with mode SYMBOL_POPDEF or    |
 324 | SYMBOL_LOOKUP, but any other mode can break the iteration.       |
 325 `-----------------------------------------------------------------*/
 326
 327 void
 328 hack_all_symbols (hack_symbol *func, void *data)
 329 {
 330   size_t h;
 331   symbol *sym;
 332   symbol *next;
 333
 334   for (h = 0; h < hash_table_size; h++)
 335     {
 336       /* We allow func to call SYMBOL_POPDEF, which can invalidate
 337          sym, so we must grab the next element to traverse before
 338          calling func.  */
 339       for (sym = symtab[h]; sym != NULL; sym = next)
 340         {
 341           next = SYMBOL_NEXT (sym);
 342           func (sym, data);
 343         }
 344     }
 345 }
 346 \f
 347 #ifdef DEBUG_SYM
 348
 349 static void symtab_print_list (int i);
 350
 351 static void M4_GNUC_UNUSED
 352 symtab_debug (void)
 353 {
 354   token_data td;
 355   const char *text;
 356   symbol *s;
 357   int delete;
 358   static int i;
 359
 360   while (next_token (&td, NULL, "<debug>") == TOKEN_WORD)
 361     {
 362       text = TOKEN_DATA_TEXT (&td);
 363       if (*text == '_')
 364         {
 365           delete = 1;
 366           text++;
 367         }
 368       else
 369         delete = 0;
 370
 371       s = lookup_symbol (text, SYMBOL_LOOKUP);
 372
 373       if (s == NULL)
 374         xprintf ("Name `%s' is unknown\n", text);
 375
 376       if (delete)
 377         (void) lookup_symbol (text, SYMBOL_DELETE);
 378       else
 379         (void) lookup_symbol (text, SYMBOL_INSERT);
 380     }
 381   symtab_print_list (i++);
 382 }
 383
 384 static void
 385 symtab_print_list (int i)
 386 {
 387   symbol *sym;
 388   size_t h;
 389
 390   xprintf ("Symbol dump #%d:\n", i);
 391   for (h = 0; h < hash_table_size; h++)
 392     for (sym = symtab[h]; sym != NULL; sym = sym->next)
 393       xprintf ("\tname %s, bucket %lu, addr %p, next %p, "
 394                "flags%s%s%s, pending %d\n",
 395                SYMBOL_NAME (sym),
 396                (unsigned long int) h, sym, SYMBOL_NEXT (sym),
 397                SYMBOL_TRACED (sym) ? " traced" : "",
 398                SYMBOL_SHADOWED (sym) ? " shadowed" : "",
 399                SYMBOL_DELETED (sym) ? " deleted" : "",
 400                SYMBOL_PENDING_EXPANSIONS (sym));
 401 }
 402
 403 #endif /* DEBUG_SYM */