clang/lib/Sema/IdentifierResolver.cpp

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