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