contrib/llvm/tools/clang/lib/Sema/IdentifierResolver.cpp

   1 //===- IdentifierResolver.cpp - Lexical Scope Name lookup -------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the IdentifierResolver class, which is used for lexical
  11 // scoped lookup, based on declaration names.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/Sema/IdentifierResolver.h"
  16 #include "clang/AST/Decl.h"
  17 #include "clang/Basic/LangOptions.h"
  18 #include "clang/Lex/ExternalPreprocessorSource.h"
  19 #include "clang/Lex/Preprocessor.h"
  20 #include "clang/Sema/Scope.h"
  21
  22 using namespace clang;
  23
  24 //===----------------------------------------------------------------------===//
  25 // IdDeclInfoMap class
  26 //===----------------------------------------------------------------------===//
  27
  28 /// IdDeclInfoMap - Associates IdDeclInfos with declaration names.
  29 /// Allocates 'pools' (vectors of IdDeclInfos) to avoid allocating each
  30 /// individual IdDeclInfo to heap.
  31 class IdentifierResolver::IdDeclInfoMap {
  32   static const unsigned int POOL_SIZE = 512;
  33
  34   /// We use our own linked-list implementation because it is sadly
  35   /// impossible to add something to a pre-C++0x STL container without
  36   /// a completely unnecessary copy.
  37   struct IdDeclInfoPool {
  38     IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {}
  39
  40     IdDeclInfoPool *Next;
  41     IdDeclInfo Pool[POOL_SIZE];
  42   };
  43
  44   IdDeclInfoPool *CurPool;
  45   unsigned int CurIndex;
  46
  47 public:
  48   IdDeclInfoMap() : CurPool(0), CurIndex(POOL_SIZE) {}
  49
  50   ~IdDeclInfoMap() {
  51     IdDeclInfoPool *Cur = CurPool;
  52     while (IdDeclInfoPool *P = Cur) {
  53       Cur = Cur->Next;
  54       delete P;
  55     }
  56   }
  57
  58   /// Returns the IdDeclInfo associated to the DeclarationName.
  59   /// It creates a new IdDeclInfo if one was not created before for this id.
  60   IdDeclInfo &operator[](DeclarationName Name);
  61 };
  62
  63
  64 //===----------------------------------------------------------------------===//
  65 // IdDeclInfo Implementation
  66 //===----------------------------------------------------------------------===//
  67
  68 /// RemoveDecl - Remove the decl from the scope chain.
  69 /// The decl must already be part of the decl chain.
  70 void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) {
  71   for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
  72     if (D == *(I-1)) {
  73       Decls.erase(I-1);
  74       return;
  75     }
  76   }
  77
  78   llvm_unreachable("Didn't find this decl on its identifier's chain!");
  79 }
  80
  81 bool
  82 IdentifierResolver::IdDeclInfo::ReplaceDecl(NamedDecl *Old, NamedDecl *New) {
  83   for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
  84     if (Old == *(I-1)) {
  85       *(I - 1) = New;
  86       return true;
  87     }
  88   }
  89
  90   return false;
  91 }
  92
  93
  94 //===----------------------------------------------------------------------===//
  95 // IdentifierResolver Implementation
  96 //===----------------------------------------------------------------------===//
  97
  98 IdentifierResolver::IdentifierResolver(Preprocessor &PP)
  99   : LangOpt(PP.getLangOpts()), PP(PP),
 100     IdDeclInfos(new IdDeclInfoMap) {
 101 }
 102
 103 IdentifierResolver::~IdentifierResolver() {
 104   delete IdDeclInfos;
 105 }
 106
 107 /// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true
 108 /// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns
 109 /// true if 'D' belongs to the given declaration context.
 110 bool IdentifierResolver::isDeclInScope(Decl *D, DeclContext *Ctx, Scope *S,
 111                              bool ExplicitInstantiationOrSpecialization) const {
 112   Ctx = Ctx->getRedeclContext();
 113
 114   if (Ctx->isFunctionOrMethod() || S->isFunctionPrototypeScope()) {
 115     // Ignore the scopes associated within transparent declaration contexts.
 116     while (S->getEntity() &&
 117            ((DeclContext *)S->getEntity())->isTransparentContext())
 118       S = S->getParent();
 119
 120     if (S->isDeclScope(D))
 121       return true;
 122     if (LangOpt.CPlusPlus) {
 123       // C++ 3.3.2p3:
 124       // The name declared in a catch exception-declaration is local to the
 125       // handler and shall not be redeclared in the outermost block of the
 126       // handler.
 127       // C++ 3.3.2p4:
 128       // Names declared in the for-init-statement, and in the condition of if,
 129       // while, for, and switch statements are local to the if, while, for, or
 130       // switch statement (including the controlled statement), and shall not be
 131       // redeclared in a subsequent condition of that statement nor in the
 132       // outermost block (or, for the if statement, any of the outermost blocks)
 133       // of the controlled statement.
 134       //
 135       assert(S->getParent() && "No TUScope?");
 136       if (S->getParent()->getFlags() & Scope::ControlScope) {
 137         S = S->getParent();
 138         if (S->isDeclScope(D))
 139           return true;
 140       }
 141       if (S->getFlags() & Scope::FnTryCatchScope)
 142         return S->getParent()->isDeclScope(D);
 143     }
 144     return false;
 145   }
 146
 147   DeclContext *DCtx = D->getDeclContext()->getRedeclContext();
 148   return ExplicitInstantiationOrSpecialization
 149            ? Ctx->InEnclosingNamespaceSetOf(DCtx)
 150            : Ctx->Equals(DCtx);
 151 }
 152
 153 /// AddDecl - Link the decl to its shadowed decl chain.
 154 void IdentifierResolver::AddDecl(NamedDecl *D) {
 155   DeclarationName Name = D->getDeclName();
 156   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
 157     updatingIdentifier(*II);
 158
 159   void *Ptr = Name.getFETokenInfo<void>();
 160
 161   if (!Ptr) {
 162     Name.setFETokenInfo(D);
 163     return;
 164   }
 165
 166   IdDeclInfo *IDI;
 167
 168   if (isDeclPtr(Ptr)) {
 169     Name.setFETokenInfo(NULL);
 170     IDI = &(*IdDeclInfos)[Name];
 171     NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
 172     IDI->AddDecl(PrevD);
 173   } else
 174     IDI = toIdDeclInfo(Ptr);
 175
 176   IDI->AddDecl(D);
 177 }
 178
 179 void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) {
 180   DeclarationName Name = D->getDeclName();
 181   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
 182     updatingIdentifier(*II);
 183
 184   void *Ptr = Name.getFETokenInfo<void>();
 185
 186   if (!Ptr) {
 187     AddDecl(D);
 188     return;
 189   }
 190
 191   if (isDeclPtr(Ptr)) {
 192     // We only have a single declaration: insert before or after it,
 193     // as appropriate.
 194     if (Pos == iterator()) {
 195       // Add the new declaration before the existing declaration.
 196       NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
 197       RemoveDecl(PrevD);
 198       AddDecl(D);
 199       AddDecl(PrevD);
 200     } else {
 201       // Add new declaration after the existing declaration.
 202       AddDecl(D);
 203     }
 204
 205     return;
 206   }
 207
 208   // General case: insert the declaration at the appropriate point in the
 209   // list, which already has at least two elements.
 210   IdDeclInfo *IDI = toIdDeclInfo(Ptr);
 211   if (Pos.isIterator()) {
 212     IDI->InsertDecl(Pos.getIterator() + 1, D);
 213   } else
 214     IDI->InsertDecl(IDI->decls_begin(), D);
 215 }
 216
 217 /// RemoveDecl - Unlink the decl from its shadowed decl chain.
 218 /// The decl must already be part of the decl chain.
 219 void IdentifierResolver::RemoveDecl(NamedDecl *D) {
 220   assert(D && "null param passed");
 221   DeclarationName Name = D->getDeclName();
 222   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
 223     updatingIdentifier(*II);
 224
 225   void *Ptr = Name.getFETokenInfo<void>();
 226
 227   assert(Ptr && "Didn't find this decl on its identifier's chain!");
 228
 229   if (isDeclPtr(Ptr)) {
 230     assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
 231     Name.setFETokenInfo(NULL);
 232     return;
 233   }
 234
 235   return toIdDeclInfo(Ptr)->RemoveDecl(D);
 236 }
 237
 238 bool IdentifierResolver::ReplaceDecl(NamedDecl *Old, NamedDecl *New) {
 239   assert(Old->getDeclName() == New->getDeclName() &&
 240          "Cannot replace a decl with another decl of a different name");
 241
 242   DeclarationName Name = Old->getDeclName();
 243   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
 244     updatingIdentifier(*II);
 245
 246   void *Ptr = Name.getFETokenInfo<void>();
 247
 248   if (!Ptr)
 249     return false;
 250
 251   if (isDeclPtr(Ptr)) {
 252     if (Ptr == Old) {
 253       Name.setFETokenInfo(New);
 254       return true;
 255     }
 256     return false;
 257   }
 258
 259   return toIdDeclInfo(Ptr)->ReplaceDecl(Old, New);
 260 }
 261
 262 /// begin - Returns an iterator for decls with name 'Name'.
 263 IdentifierResolver::iterator
 264 IdentifierResolver::begin(DeclarationName Name) {
 265   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
 266     readingIdentifier(*II);
 267
 268   void *Ptr = Name.getFETokenInfo<void>();
 269   if (!Ptr) return end();
 270
 271   if (isDeclPtr(Ptr))
 272     return iterator(static_cast<NamedDecl*>(Ptr));
 273
 274   IdDeclInfo *IDI = toIdDeclInfo(Ptr);
 275
 276   IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
 277   if (I != IDI->decls_begin())
 278     return iterator(I-1);
 279   // No decls found.
 280   return end();
 281 }
 282
 283 namespace {
 284   enum DeclMatchKind {
 285     DMK_Different,
 286     DMK_Replace,
 287     DMK_Ignore
 288   };
 289 }
 290
 291 /// \brief Compare two declarations to see whether they are different or,
 292 /// if they are the same, whether the new declaration should replace the
 293 /// existing declaration.
 294 static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
 295   // If the declarations are identical, ignore the new one.
 296   if (Existing == New)
 297     return DMK_Ignore;
 298
 299   // If the declarations have different kinds, they're obviously different.
 300   if (Existing->getKind() != New->getKind())
 301     return DMK_Different;
 302
 303   // If the declarations are redeclarations of each other, keep the newest one.
 304   if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
 305     // If either of these is the most recent declaration, use it.
 306     Decl *MostRecent = Existing->getMostRecentDecl();
 307     if (Existing == MostRecent)
 308       return DMK_Ignore;
 309
 310     if (New == MostRecent)
 311       return DMK_Replace;
 312
 313     // If the existing declaration is somewhere in the previous declaration
 314     // chain of the new declaration, then prefer the new declaration.
 315     for (Decl::redecl_iterator RD = New->redecls_begin(),
 316                             RDEnd = New->redecls_end();
 317          RD != RDEnd; ++RD) {
 318       if (*RD == Existing)
 319         return DMK_Replace;
 320
 321       if (RD->isCanonicalDecl())
 322         break;
 323     }
 324
 325     return DMK_Ignore;
 326   }
 327
 328   return DMK_Different;
 329 }
 330
 331 bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){
 332   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
 333     readingIdentifier(*II);
 334
 335   void *Ptr = Name.getFETokenInfo<void>();
 336
 337   if (!Ptr) {
 338     Name.setFETokenInfo(D);
 339     return true;
 340   }
 341
 342   IdDeclInfo *IDI;
 343
 344   if (isDeclPtr(Ptr)) {
 345     NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
 346
 347     switch (compareDeclarations(PrevD, D)) {
 348     case DMK_Different:
 349       break;
 350
 351     case DMK_Ignore:
 352       return false;
 353
 354     case DMK_Replace:
 355       Name.setFETokenInfo(D);
 356       return true;
 357     }
 358
 359     Name.setFETokenInfo(NULL);
 360     IDI = &(*IdDeclInfos)[Name];
 361
 362     // If the existing declaration is not visible in translation unit scope,
 363     // then add the new top-level declaration first.
 364     if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
 365       IDI->AddDecl(D);
 366       IDI->AddDecl(PrevD);
 367     } else {
 368       IDI->AddDecl(PrevD);
 369       IDI->AddDecl(D);
 370     }
 371     return true;
 372   }
 373
 374   IDI = toIdDeclInfo(Ptr);
 375
 376   // See whether this declaration is identical to any existing declarations.
 377   // If not, find the right place to insert it.
 378   for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
 379                                   IEnd = IDI->decls_end();
 380        I != IEnd; ++I) {
 381
 382     switch (compareDeclarations(*I, D)) {
 383     case DMK_Different:
 384       break;
 385
 386     case DMK_Ignore:
 387       return false;
 388
 389     case DMK_Replace:
 390       *I = D;
 391       return true;
 392     }
 393
 394     if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
 395       // We've found a declaration that is not visible from the translation
 396       // unit (it's in an inner scope). Insert our declaration here.
 397       IDI->InsertDecl(I, D);
 398       return true;
 399     }
 400   }
 401
 402   // Add the declaration to the end.
 403   IDI->AddDecl(D);
 404   return true;
 405 }
 406
 407 void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
 408   if (II.isOutOfDate())
 409     PP.getExternalSource()->updateOutOfDateIdentifier(II);
 410 }
 411
 412 void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
 413   if (II.isOutOfDate())
 414     PP.getExternalSource()->updateOutOfDateIdentifier(II);
 415
 416   if (II.isFromAST())
 417     II.setChangedSinceDeserialization();
 418 }
 419
 420 //===----------------------------------------------------------------------===//
 421 // IdDeclInfoMap Implementation
 422 //===----------------------------------------------------------------------===//
 423
 424 /// Returns the IdDeclInfo associated to the DeclarationName.
 425 /// It creates a new IdDeclInfo if one was not created before for this id.
 426 IdentifierResolver::IdDeclInfo &
 427 IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) {
 428   void *Ptr = Name.getFETokenInfo<void>();
 429
 430   if (Ptr) return *toIdDeclInfo(Ptr);
 431
 432   if (CurIndex == POOL_SIZE) {
 433     CurPool = new IdDeclInfoPool(CurPool);
 434     CurIndex = 0;
 435   }
 436   IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
 437   Name.setFETokenInfo(reinterpret_cast<void*>(
 438                               reinterpret_cast<uintptr_t>(IDI) | 0x1)
 439                                                                      );
 440   ++CurIndex;
 441   return *IDI;
 442 }
 443
 444 void IdentifierResolver::iterator::incrementSlowCase() {
 445   NamedDecl *D = **this;
 446   void *InfoPtr = D->getDeclName().getFETokenInfo<void>();
 447   assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
 448   IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
 449
 450   BaseIter I = getIterator();
 451   if (I != Info->decls_begin())
 452     *this = iterator(I-1);
 453   else // No more decls.
 454     *this = iterator();
 455 }