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

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