IdentifierResolver.cpp 13 KB

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