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