1 //===- IdentifierResolver.h - Lexical Scope Name lookup ---------*- C++ -*-===// 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 defines the IdentifierResolver class, which is used for lexical 10 // scoped lookup, based on declaration names. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_SEMA_IDENTIFIERRESOLVER_H 15 #define LLVM_CLANG_SEMA_IDENTIFIERRESOLVER_H 16 17 #include "clang/Basic/LLVM.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include <cassert> 20 #include <cstddef> 21 #include <cstdint> 22 #include <iterator> 23 24 namespace clang { 25 26 class Decl; 27 class DeclarationName; 28 class DeclContext; 29 class IdentifierInfo; 30 class LangOptions; 31 class NamedDecl; 32 class Preprocessor; 33 class Scope; 34 35 /// IdentifierResolver - Keeps track of shadowed decls on enclosing 36 /// scopes. It manages the shadowing chains of declaration names and 37 /// implements efficient decl lookup based on a declaration name. 38 class IdentifierResolver { 39 /// IdDeclInfo - Keeps track of information about decls associated 40 /// to a particular declaration name. IdDeclInfos are lazily 41 /// constructed and assigned to a declaration name the first time a 42 /// decl with that declaration name is shadowed in some scope. 43 class IdDeclInfo { 44 public: 45 using DeclsTy = SmallVector<NamedDecl *, 2>; 46 decls_begin()47 DeclsTy::iterator decls_begin() { return Decls.begin(); } decls_end()48 DeclsTy::iterator decls_end() { return Decls.end(); } 49 AddDecl(NamedDecl * D)50 void AddDecl(NamedDecl *D) { Decls.push_back(D); } 51 52 /// RemoveDecl - Remove the decl from the scope chain. 53 /// The decl must already be part of the decl chain. 54 void RemoveDecl(NamedDecl *D); 55 56 /// Insert the given declaration at the given position in the list. InsertDecl(DeclsTy::iterator Pos,NamedDecl * D)57 void InsertDecl(DeclsTy::iterator Pos, NamedDecl *D) { 58 Decls.insert(Pos, D); 59 } 60 61 private: 62 DeclsTy Decls; 63 }; 64 65 public: 66 /// iterator - Iterate over the decls of a specified declaration name. 67 /// It will walk or not the parent declaration contexts depending on how 68 /// it was instantiated. 69 class iterator { 70 public: 71 friend class IdentifierResolver; 72 73 using value_type = NamedDecl *; 74 using reference = NamedDecl *; 75 using pointer = NamedDecl *; 76 using iterator_category = std::input_iterator_tag; 77 using difference_type = std::ptrdiff_t; 78 79 /// Ptr - There are 2 forms that 'Ptr' represents: 80 /// 1) A single NamedDecl. (Ptr & 0x1 == 0) 81 /// 2) A IdDeclInfo::DeclsTy::iterator that traverses only the decls of the 82 /// same declaration context. (Ptr & 0x1 == 0x1) 83 uintptr_t Ptr = 0; 84 using BaseIter = IdDeclInfo::DeclsTy::iterator; 85 86 /// A single NamedDecl. (Ptr & 0x1 == 0) iterator(NamedDecl * D)87 iterator(NamedDecl *D) { 88 Ptr = reinterpret_cast<uintptr_t>(D); 89 assert((Ptr & 0x1) == 0 && "Invalid Ptr!"); 90 } 91 92 /// A IdDeclInfo::DeclsTy::iterator that walks or not the parent declaration 93 /// contexts depending on 'LookInParentCtx'. iterator(BaseIter I)94 iterator(BaseIter I) { 95 Ptr = reinterpret_cast<uintptr_t>(I) | 0x1; 96 } 97 isIterator()98 bool isIterator() const { return (Ptr & 0x1); } 99 getIterator()100 BaseIter getIterator() const { 101 assert(isIterator() && "Ptr not an iterator!"); 102 return reinterpret_cast<BaseIter>(Ptr & ~0x1); 103 } 104 105 void incrementSlowCase(); 106 107 public: 108 iterator() = default; 109 110 NamedDecl *operator*() const { 111 if (isIterator()) 112 return *getIterator(); 113 else 114 return reinterpret_cast<NamedDecl*>(Ptr); 115 } 116 117 bool operator==(const iterator &RHS) const { 118 return Ptr == RHS.Ptr; 119 } 120 bool operator!=(const iterator &RHS) const { 121 return Ptr != RHS.Ptr; 122 } 123 124 // Preincrement. 125 iterator& operator++() { 126 if (!isIterator()) // common case. 127 Ptr = 0; 128 else 129 incrementSlowCase(); 130 return *this; 131 } 132 }; 133 134 explicit IdentifierResolver(Preprocessor &PP); 135 ~IdentifierResolver(); 136 137 IdentifierResolver(const IdentifierResolver &) = delete; 138 IdentifierResolver &operator=(const IdentifierResolver &) = delete; 139 140 /// Returns a range of decls with the name 'Name'. 141 llvm::iterator_range<iterator> decls(DeclarationName Name); 142 143 /// Returns an iterator over decls with the name 'Name'. 144 iterator begin(DeclarationName Name); 145 146 /// Returns the end iterator. end()147 iterator end() { return iterator(); } 148 149 /// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true 150 /// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns 151 /// true if 'D' belongs to the given declaration context. 152 /// 153 /// \param AllowInlineNamespace If \c true, we are checking whether a prior 154 /// declaration is in scope in a declaration that requires a prior 155 /// declaration (because it is either explicitly qualified or is a 156 /// template instantiation or specialization). In this case, a 157 /// declaration is in scope if it's in the inline namespace set of the 158 /// context. 159 bool isDeclInScope(Decl *D, DeclContext *Ctx, Scope *S = nullptr, 160 bool AllowInlineNamespace = false) const; 161 162 /// AddDecl - Link the decl to its shadowed decl chain. 163 void AddDecl(NamedDecl *D); 164 165 /// RemoveDecl - Unlink the decl from its shadowed decl chain. 166 /// The decl must already be part of the decl chain. 167 void RemoveDecl(NamedDecl *D); 168 169 /// Insert the given declaration after the given iterator 170 /// position. 171 void InsertDeclAfter(iterator Pos, NamedDecl *D); 172 173 /// Try to add the given declaration to the top level scope, if it 174 /// (or a redeclaration of it) hasn't already been added. 175 /// 176 /// \param D The externally-produced declaration to add. 177 /// 178 /// \param Name The name of the externally-produced declaration. 179 /// 180 /// \returns true if the declaration was added, false otherwise. 181 bool tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name); 182 183 private: 184 const LangOptions &LangOpt; 185 Preprocessor &PP; 186 187 class IdDeclInfoMap; 188 IdDeclInfoMap *IdDeclInfos; 189 190 void updatingIdentifier(IdentifierInfo &II); 191 void readingIdentifier(IdentifierInfo &II); 192 193 /// FETokenInfo contains a Decl pointer if lower bit == 0. isDeclPtr(void * Ptr)194 static inline bool isDeclPtr(void *Ptr) { 195 return (reinterpret_cast<uintptr_t>(Ptr) & 0x1) == 0; 196 } 197 198 /// FETokenInfo contains a IdDeclInfo pointer if lower bit == 1. toIdDeclInfo(void * Ptr)199 static inline IdDeclInfo *toIdDeclInfo(void *Ptr) { 200 assert((reinterpret_cast<uintptr_t>(Ptr) & 0x1) == 1 201 && "Ptr not a IdDeclInfo* !"); 202 return reinterpret_cast<IdDeclInfo*>( 203 reinterpret_cast<uintptr_t>(Ptr) & ~0x1); 204 } 205 }; 206 207 } // namespace clang 208 209 #endif // LLVM_CLANG_SEMA_IDENTIFIERRESOLVER_H 210