src/symtab.c

   1 /* GNU m4 -- A simple macro processor
   2
   3    Copyright (C) 1989-1994, 2003, 2006-2014, 2016-2017, 2020-2021 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 <https://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 hash.  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, |
  92 | and zeroing all the entries.                                      |
  93 `------------------------------------------------------------------*/
  94
  95 /* Pointer to symbol table.  */
  96 static 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 ATTRIBUTE_PURE
 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       if (SYMBOL_STACK (sym) == NULL)
 148         free (SYMBOL_NAME (sym));
 149       if (SYMBOL_TYPE (sym) == TOKEN_TEXT)
 150         free (SYMBOL_TEXT (sym));
 151       free (sym);
 152     }
 153 }
 154
 155 /*-------------------------------------------------------------------.
 156 | Search in, and manipulation of the symbol table, are all done by   |
 157 | lookup_symbol ().  It basically hashes NAME to a list in the       |
 158 | symbol table, and searches this list for the first occurrence of a |
 159 | symbol with the name.                                              |
 160 |                                                                    |
 161 | The MODE parameter determines what lookup_symbol () will do.  It   |
 162 | can either just do a lookup, do a lookup and insert if not         |
 163 | present, do an insertion even if the name is already in the list,  |
 164 | delete the first occurrence of the name on the list, or delete all |
 165 | occurrences of the name on the list.                               |
 166 `-------------------------------------------------------------------*/
 167
 168 symbol *
 169 lookup_symbol (const char *name, symbol_lookup mode)
 170 {
 171   size_t h;
 172   int cmp = 1;
 173   symbol *sym, *prev;
 174   symbol **spp;
 175
 176 #if DEBUG_SYM
 177   current_mode = mode;
 178   profiles[mode].entry++;
 179 #endif /* DEBUG_SYM */
 180
 181   h = hash (name);
 182   sym = symtab[h % hash_table_size];
 183
 184   for (prev = NULL; sym != NULL; prev = sym, sym = sym->next)
 185     {
 186       cmp = (h > sym->hash) - (h < sym->hash);
 187       if (cmp == 0)
 188         cmp = strcmp (SYMBOL_NAME (sym), name);
 189       if (cmp >= 0)
 190         break;
 191     }
 192
 193   /* If just searching, return status of search.  */
 194
 195   if (mode == SYMBOL_LOOKUP)
 196     return cmp == 0 ? sym : NULL;
 197
 198   /* Symbol not found.  */
 199
 200   spp = (prev != NULL) ?  &prev->next : &symtab[h % hash_table_size];
 201
 202   switch (mode)
 203     {
 204
 205     case SYMBOL_INSERT:
 206
 207       /* If the name was found in the table, check whether it is still in
 208          use by a pending expansion.  If so, replace the table element with
 209          a new one; if not, just return the symbol.  If not found, just
 210          insert the name, and return the new symbol.  */
 211
 212       if (cmp == 0 && sym != NULL)
 213         {
 214           if (SYMBOL_PENDING_EXPANSIONS (sym) > 0)
 215             {
 216               symbol *old = sym;
 217               SYMBOL_DELETED (old) = true;
 218
 219               sym = (symbol *) xmalloc (sizeof (symbol));
 220               SYMBOL_TYPE (sym) = TOKEN_VOID;
 221               SYMBOL_TRACED (sym) = SYMBOL_TRACED (old);
 222               sym->hash = h;
 223               SYMBOL_NAME (sym) = old->name;
 224               old->name = xstrdup (name);
 225               SYMBOL_MACRO_ARGS (sym) = false;
 226               SYMBOL_BLIND_NO_ARGS (sym) = false;
 227               SYMBOL_DELETED (sym) = false;
 228               SYMBOL_PENDING_EXPANSIONS (sym) = 0;
 229
 230               SYMBOL_STACK (sym) = SYMBOL_STACK (old);
 231               SYMBOL_STACK (old) = NULL;
 232               sym->next = old->next;
 233               old->next = NULL;
 234               *spp = sym;
 235             }
 236           return sym;
 237         }
 238       FALLTHROUGH;
 239
 240     case SYMBOL_PUSHDEF:
 241
 242       /* Insert a name in the symbol table.  If there is already a symbol
 243          with the name, insert this in front of it.  */
 244
 245       sym = (symbol *) xmalloc (sizeof (symbol));
 246       SYMBOL_TYPE (sym) = TOKEN_VOID;
 247       SYMBOL_TRACED (sym) = false;
 248       sym->hash = h;
 249       SYMBOL_MACRO_ARGS (sym) = false;
 250       SYMBOL_BLIND_NO_ARGS (sym) = false;
 251       SYMBOL_DELETED (sym) = false;
 252       SYMBOL_PENDING_EXPANSIONS (sym) = 0;
 253
 254       SYMBOL_STACK (sym) = NULL;
 255       sym->next = *spp;
 256       *spp = sym;
 257
 258       if (mode == SYMBOL_PUSHDEF && cmp == 0)
 259         {
 260           SYMBOL_STACK (sym) = sym->next;
 261           sym->next = SYMBOL_STACK (sym)->next;
 262           SYMBOL_STACK (sym)->next = NULL;
 263           SYMBOL_TRACED (sym) = SYMBOL_TRACED (SYMBOL_STACK (sym));
 264           SYMBOL_NAME (sym) = SYMBOL_NAME (SYMBOL_STACK (sym));
 265         }
 266       else
 267         SYMBOL_NAME (sym) = xstrdup (name);
 268       return sym;
 269
 270     case SYMBOL_DELETE:
 271     case SYMBOL_POPDEF:
 272
 273       /* Delete occurrences of symbols with NAME.  SYMBOL_DELETE kills
 274          all definitions, SYMBOL_POPDEF kills only the first.
 275          However, if the last instance of a symbol is marked for
 276          tracing, reinsert a placeholder in the table.  And if the
 277          definition is still in use, let the caller free the memory
 278          after it is done with the symbol.  */
 279
 280       if (cmp != 0 || sym == NULL)
 281         return NULL;
 282       {
 283         bool traced = false;
 284         symbol *next;
 285         if (SYMBOL_STACK (sym) != NULL
 286             && mode == SYMBOL_POPDEF)
 287           {
 288             SYMBOL_TRACED (SYMBOL_STACK (sym)) = SYMBOL_TRACED (sym);
 289             SYMBOL_STACK (sym)->next = sym->next;
 290             *spp = SYMBOL_STACK (sym);
 291           }
 292         else
 293           {
 294             traced = SYMBOL_TRACED (sym);
 295             *spp = sym->next;
 296           }
 297         do
 298           {
 299             next = SYMBOL_STACK (sym);
 300             free_symbol (sym);
 301             sym = next;
 302           }
 303         while (next != NULL && mode == SYMBOL_DELETE);
 304         if (traced)
 305           {
 306             sym = (symbol *) xmalloc (sizeof (symbol));
 307             SYMBOL_TYPE (sym) = TOKEN_VOID;
 308             SYMBOL_TRACED (sym) = true;
 309             sym->hash = h;
 310             SYMBOL_NAME (sym) = xstrdup (name);
 311             SYMBOL_MACRO_ARGS (sym) = false;
 312             SYMBOL_BLIND_NO_ARGS (sym) = false;
 313             SYMBOL_DELETED (sym) = false;
 314             SYMBOL_PENDING_EXPANSIONS (sym) = 0;
 315
 316             SYMBOL_STACK (sym) = NULL;
 317             sym->next = *spp;
 318             *spp = sym;
 319           }
 320       }
 321       return NULL;
 322
 323     case SYMBOL_LOOKUP:
 324     default:
 325       M4ERROR ((warning_status, 0,
 326                 "INTERNAL ERROR: invalid mode to symbol_lookup ()"));
 327       abort ();
 328     }
 329 }
 330
 331 /*-----------------------------------------------------------------.
 332 | The following function is used for the cases where we want to do |
 333 | something to each and every symbol in the table.  The function   |
 334 | hack_all_symbols () traverses the symbol table, and calls a      |
 335 | specified function FUNC for each symbol in the table.  FUNC is   |
 336 | called with a pointer to the symbol, and the DATA argument.      |
 337 |                                                                  |
 338 | FUNC may safely call lookup_symbol with mode SYMBOL_POPDEF or    |
 339 | SYMBOL_LOOKUP, but any other mode can break the iteration.       |
 340 `-----------------------------------------------------------------*/
 341
 342 void
 343 hack_all_symbols (hack_symbol *func, void *data)
 344 {
 345   size_t h;
 346   symbol *sym;
 347   symbol *next;
 348
 349   for (h = 0; h < hash_table_size; h++)
 350     {
 351       /* We allow func to call SYMBOL_POPDEF, which can invalidate
 352          sym, so we must grab the next element to traverse before
 353          calling func.  */
 354       for (sym = symtab[h]; sym != NULL; sym = next)
 355         {
 356           next = sym->next;
 357           func (sym, data);
 358         }
 359     }
 360 }
 361 \f
 362 #ifdef DEBUG_SYM
 363
 364 static void symtab_print_list (int i);
 365
 366 static void MAYBE_UNUSED
 367 symtab_debug (void)
 368 {
 369   token_data td;
 370   const char *text;
 371   symbol *s;
 372   int delete;
 373   static int i;
 374
 375   while (next_token (&td, NULL) == TOKEN_WORD)
 376     {
 377       text = TOKEN_DATA_TEXT (&td);
 378       if (*text == '_')
 379         {
 380           delete = 1;
 381           text++;
 382         }
 383       else
 384         delete = 0;
 385
 386       s = lookup_symbol (text, SYMBOL_LOOKUP);
 387
 388       if (s == NULL)
 389         xprintf ("Name `%s' is unknown\n", text);
 390
 391       lookup_symbol (text, delete ? SYMBOL_DELETE : SYMBOL_INSERT);
 392     }
 393   symtab_print_list (i++);
 394 }
 395
 396 static void
 397 symtab_print_list (int i)
 398 {
 399   symbol *sym;
 400   symbol *bucket;
 401   size_t h;
 402
 403   xprintf ("Symbol dump #%d:\n", i);
 404   for (h = 0; h < hash_table_size; h++)
 405     for (bucket = symtab[h]; bucket != NULL; bucket = bucket->next)
 406       for (sym = bucket; sym; sym = sym->stack)
 407         xprintf ("\tname %s, hash %lu, bucket %lu, addr %p, stack %p, "
 408                  "next %p, flags%s%s, pending %d\n",
 409                  SYMBOL_NAME (sym), (unsigned long int) sym->hash,
 410                  (unsigned long int) h, sym, SYMBOL_STACK (sym),
 411                  sym->next,
 412                  SYMBOL_TRACED (sym) ? " traced" : "",
 413                  SYMBOL_DELETED (sym) ? " deleted" : "",
 414                  SYMBOL_PENDING_EXPANSIONS (sym));
 415 }
 416
 417 #endif /* DEBUG_SYM */