gcc/cp/name-lookup.c

   1 /* Definitions for C++ name lookup routines.
   2    Copyright (C) 2003 Free Software Foundation, Inc.
   3    Contributed by Gabriel Dos Reis <gdr@integrable-solutions.net>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "cp-tree.h"
  28 #include "name-lookup.h"
  29 #include "timevar.h"
  30
  31 /* Compute the chain index of a binding_entry given the HASH value of its
  32    name and the total COUNT of chains.  COUNT is assumed to be a power
  33    of 2.  */
  34 #define ENTRY_INDEX(HASH, COUNT) (((HASH) >> 3) & ((COUNT) - 1))
  35
  36 /* A free list of "binding_entry"s awaiting for re-use.  */
  37 static GTY((deletable(""))) binding_entry free_binding_entry = NULL;
  38
  39 /* Create a binding_entry object for (NAME, TYPE).  */
  40 static inline binding_entry
  41 binding_entry_make (tree name, tree type)
  42 {
  43   binding_entry entry;
  44
  45   if (free_binding_entry)
  46     {
  47       entry = free_binding_entry;
  48       free_binding_entry = entry->chain;
  49     }
  50   else
  51     entry = ggc_alloc (sizeof (struct binding_entry_s));
  52
  53   entry->name = name;
  54   entry->type = type;
  55   entry->chain = NULL;
  56
  57   return entry;
  58 }
  59
  60 /* Put ENTRY back on the free list.  */
  61 static inline void
  62 binding_entry_free (binding_entry entry)
  63 {
  64   entry->chain = free_binding_entry;
  65   free_binding_entry = entry;
  66 }
  67
  68 /* The datatype used to implement the mapping from names to types at
  69    a given scope.  */
  70 struct binding_table_s GTY(())
  71 {
  72   /* Array of chains of "binding_entry"s  */
  73   binding_entry * GTY((length ("%h.chain_count"))) chain;
  74
  75   /* The number of chains in this table.  This is the length of the
  76      the member "chain" considered as an array.  */
  77   size_t chain_count;
  78
  79   /* Number of "binding_entry"s in this table.  */
  80   size_t entry_count;
  81 };
  82
  83 /* Construct TABLE with an initial CHAIN_COUNT.  */
  84 static inline void
  85 binding_table_construct (binding_table table, size_t chain_count)
  86 {
  87   table->chain_count = chain_count;
  88   table->entry_count = 0;
  89   table->chain = ggc_alloc_cleared
  90     (table->chain_count * sizeof (binding_entry));
  91 }
  92
  93 /* Free TABLE by making its entries ready for reuse. */
  94 void
  95 binding_table_free (binding_table table)
  96 {
  97   size_t i;
  98   if (table == NULL)
  99     return;
 100
 101   for (i = 0; i < table->chain_count; ++i)
 102     {
 103       binding_entry temp = table->chain[i];
 104       while (temp != NULL)
 105         {
 106           binding_entry entry = temp;
 107           temp = entry->chain;
 108           entry->chain = NULL;
 109           binding_entry_free (entry);
 110         }
 111       table->chain[i] = temp;
 112     }
 113   table->entry_count = 0;
 114 }
 115
 116 /* Allocate a table with CHAIN_COUNT, assumed to be a power of two.  */
 117 binding_table
 118 binding_table_new (size_t chain_count)
 119 {
 120   binding_table table = ggc_alloc (sizeof (struct binding_table_s));
 121   table->chain = NULL;
 122   binding_table_construct (table, chain_count);
 123   return table;
 124 }
 125
 126 /* Expand TABLE to twice its current chain_count.  */
 127 static void
 128 binding_table_expand (binding_table table)
 129 {
 130   const size_t old_chain_count = table->chain_count;
 131   const size_t old_entry_count = table->entry_count;
 132   const size_t new_chain_count = 2 * old_chain_count;
 133   binding_entry *old_chains = table->chain;
 134   size_t i;
 135
 136   binding_table_construct (table, new_chain_count);
 137   for (i = 0; i < old_chain_count; ++i)
 138     {
 139       binding_entry entry = old_chains[i];
 140       for (; entry != NULL; entry = old_chains[i])
 141         {
 142           const unsigned int hash = IDENTIFIER_HASH_VALUE (entry->name);
 143           const size_t j = ENTRY_INDEX (hash, new_chain_count);
 144
 145           old_chains[i] = entry->chain;
 146           entry->chain = table->chain[j];
 147           table->chain[j] = entry;
 148         }
 149     }
 150   table->entry_count = old_entry_count;
 151 }
 152
 153 /* Insert a binding for NAME to TYPe into TABLE.  */
 154 void
 155 binding_table_insert (binding_table table, tree name, tree type)
 156 {
 157   const unsigned int hash = IDENTIFIER_HASH_VALUE (name);
 158   const size_t i = ENTRY_INDEX (hash, table->chain_count);
 159   binding_entry entry = binding_entry_make (name, type);
 160
 161   entry->chain = table->chain[i];
 162   table->chain[i] = entry;
 163   ++table->entry_count;
 164
 165   if (3 * table->chain_count < 5 * table->entry_count)
 166     binding_table_expand (table);
 167 }
 168
 169 /* Return the binding_entry, if any, that maps NAME.  */
 170 binding_entry
 171 binding_table_find (binding_table table, tree name)
 172 {
 173   const unsigned int hash = IDENTIFIER_HASH_VALUE (name);
 174   binding_entry entry = table->chain[ENTRY_INDEX (hash, table->chain_count)];
 175
 176   while (entry != NULL && entry->name != name)
 177     entry = entry->chain;
 178
 179   return entry;
 180 }
 181
 182 /* Return the binding_entry, if any, that maps name to an anonymous type.  */
 183 tree
 184 binding_table_find_anon_type (binding_table table, tree name)
 185 {
 186   const unsigned int hash = IDENTIFIER_HASH_VALUE (name);
 187   binding_entry entry = table->chain[ENTRY_INDEX (hash, table->chain_count)];
 188
 189   while (entry != NULL && TYPE_IDENTIFIER (entry->type) != name)
 190     entry = entry->chain;
 191
 192   return entry ? entry->type : NULL;
 193 }
 194
 195 /* Return the binding_entry, if any, that has TYPE as target.  If NAME
 196    is non-null, then set the domain and rehash that entry.  */
 197 binding_entry
 198 binding_table_reverse_maybe_remap (binding_table table, tree type, tree name)
 199 {
 200   const size_t chain_count = table->chain_count;
 201   binding_entry entry = NULL;
 202   binding_entry *p = NULL;
 203   size_t i;
 204
 205   for (i = 0; i < chain_count && entry == NULL; ++i)
 206     {
 207       p = &table->chain[i];
 208       while (*p != NULL && entry == NULL)
 209         if ((*p)->type == type)
 210           entry = *p;
 211         else
 212           p = &(*p)->chain;
 213     }
 214
 215   if (entry != NULL && name != NULL && entry->name != name)
 216     {
 217       /* Remove the bucket from the previous chain.  */
 218       *p = (*p)->chain;
 219
 220       /* Remap the name type to type.  */
 221       i = ENTRY_INDEX (IDENTIFIER_HASH_VALUE (name), chain_count);
 222       entry->chain = table->chain[i];
 223       entry->name = name;
 224       table->chain[i] = entry;
 225     }
 226
 227   return entry;
 228 }
 229
 230 /* Remove from TABLE all entries that map to anonymous enums or
 231    class-types.  */
 232 void
 233 binding_table_remove_anonymous_types (binding_table table)
 234 {
 235   const size_t chain_count = table->chain_count;
 236   size_t i;
 237
 238   for (i = 0; i < chain_count; ++i)
 239     {
 240       binding_entry *p = &table->chain[i];
 241
 242       while (*p != NULL)
 243         if (ANON_AGGRNAME_P ((*p)->name))
 244           {
 245             binding_entry e = *p;
 246             *p = (*p)->chain;
 247             --table->entry_count;
 248             binding_entry_free (e);
 249           }
 250         else
 251           p = &(*p)->chain;
 252     }
 253 }
 254
 255 /* Apply PROC -- with DATA -- to all entries in TABLE.  */
 256 void
 257 binding_table_foreach (binding_table table, bt_foreach_proc proc, void *data)
 258 {
 259   const size_t chain_count = table->chain_count;
 260   size_t i;
 261
 262   for (i = 0; i < chain_count; ++i)
 263     {
 264       binding_entry entry = table->chain[i];
 265       for (; entry != NULL; entry = entry->chain)
 266         proc (entry, data);
 267     }
 268 }
 269 \f
 270
 271 /* A free list of "cxx_binding"s, connected by their PREVIOUS.  */
 272 static GTY((deletable (""))) cxx_binding *free_bindings;
 273
 274 /* (GC)-allocate a binding object with VALUE and TYPE member initialized.  */
 275 cxx_binding *
 276 cxx_binding_make (tree value, tree type)
 277 {
 278   cxx_binding *binding;
 279   if (free_bindings)
 280     {
 281       binding = free_bindings;
 282       free_bindings = binding->previous;
 283     }
 284   else
 285     binding = ggc_alloc (sizeof (cxx_binding));
 286
 287   binding->value = value;
 288   binding->type = type;
 289   binding->previous = NULL;
 290
 291   return binding;
 292 }
 293
 294 /* Put BINDING back on the free list.  */
 295 void
 296 cxx_binding_free (cxx_binding *binding)
 297 {
 298   binding->previous = free_bindings;
 299   free_bindings = binding;
 300 }
 301 \f
 302 /* Return (from the stack of) the BINDING, if any, establihsed at SCOPE.  */
 303
 304 static inline cxx_binding *
 305 find_binding (cxx_scope *scope, cxx_binding *binding)
 306 {
 307   timevar_push (TV_NAME_LOOKUP);
 308
 309   for (; binding != NULL; binding = binding->previous)
 310     if (BINDING_SCOPE (binding) == scope)
 311       POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, binding);
 312
 313   POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, (cxx_binding *)0);
 314 }
 315
 316 /* Return the binding for NAME in SCOPE, if any.  Otherwise, return NULL.  */
 317 cxx_binding *
 318 cxx_scope_find_binding_for_name (cxx_scope *scope, tree name)
 319 {
 320   cxx_binding *b = IDENTIFIER_NAMESPACE_BINDINGS (name);
 321   if (b)
 322     {
 323       /* Fold-in case where NAME is used only once.  */
 324       if (scope == BINDING_SCOPE (b) && b->previous == NULL)
 325         return b;
 326       return find_binding (scope, b);
 327     }
 328   return NULL;
 329 }
 330
 331 /* Always returns a binding for name in scope.  If no binding is
 332    found, make a new one.  */
 333
 334 cxx_binding *
 335 binding_for_name (cxx_scope *scope, tree name)
 336 {
 337   cxx_binding *result;
 338
 339   result = cxx_scope_find_binding_for_name (scope, name);
 340   if (result)
 341     return result;
 342   /* Not found, make a new one.  */
 343   result = cxx_binding_make (NULL, NULL);
 344   result->previous = IDENTIFIER_NAMESPACE_BINDINGS (name);
 345   BINDING_SCOPE (result) = scope;
 346   result->is_local = false;
 347   result->value_is_inherited = false;
 348   IDENTIFIER_NAMESPACE_BINDINGS (name) = result;
 349   return result;
 350 }
 351 \f
 352 /* Namespace-scope manipulation routines.  */
 353
 354 /* Return the binding value for name in scope.  */
 355
 356 tree
 357 namespace_binding (tree name, tree scope)
 358 {
 359   cxx_binding *binding;
 360
 361   if (scope == NULL)
 362     scope = global_namespace;
 363   scope = ORIGINAL_NAMESPACE (scope);
 364   binding = cxx_scope_find_binding_for_name (NAMESPACE_LEVEL (scope), name);
 365
 366   return binding ? binding->value : NULL_TREE;
 367 }
 368
 369 /* Set the binding value for name in scope.  */
 370
 371 void
 372 set_namespace_binding (tree name, tree scope, tree val)
 373 {
 374   cxx_binding *b;
 375
 376   timevar_push (TV_NAME_LOOKUP);
 377   if (scope == NULL_TREE)
 378     scope = global_namespace;
 379   b = binding_for_name (NAMESPACE_LEVEL (scope), name);
 380   BINDING_VALUE (b) = val;
 381   timevar_pop (TV_NAME_LOOKUP);
 382 }
 383
 384 #include "gt-cp-name-lookup.h"