1 //===- DeclContextInternals.h - DeclContext Representation ------*- 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 data structures used in the implementation 10 // of DeclContext. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H 15 #define LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H 16 17 #include "clang/AST/Decl.h" 18 #include "clang/AST/DeclBase.h" 19 #include "clang/AST/DeclCXX.h" 20 #include "clang/AST/DeclarationName.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/PointerIntPair.h" 23 #include "llvm/ADT/PointerUnion.h" 24 #include "llvm/ADT/SmallVector.h" 25 #include <algorithm> 26 #include <cassert> 27 28 namespace clang { 29 30 class DependentDiagnostic; 31 32 /// An array of decls optimized for the common case of only containing 33 /// one entry. 34 struct StoredDeclsList { 35 /// When in vector form, this is what the Data pointer points to. 36 using DeclsTy = SmallVector<NamedDecl *, 4>; 37 38 /// A collection of declarations, with a flag to indicate if we have 39 /// further external declarations. 40 using DeclsAndHasExternalTy = llvm::PointerIntPair<DeclsTy *, 1, bool>; 41 42 /// The stored data, which will be either a pointer to a NamedDecl, 43 /// or a pointer to a vector with a flag to indicate if there are further 44 /// external declarations. 45 llvm::PointerUnion<NamedDecl *, DeclsAndHasExternalTy> Data; 46 47 public: 48 StoredDeclsList() = default; 49 StoredDeclsListStoredDeclsList50 StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) { 51 RHS.Data = (NamedDecl *)nullptr; 52 } 53 ~StoredDeclsListStoredDeclsList54 ~StoredDeclsList() { 55 // If this is a vector-form, free the vector. 56 if (DeclsTy *Vector = getAsVector()) 57 delete Vector; 58 } 59 60 StoredDeclsList &operator=(StoredDeclsList &&RHS) { 61 if (DeclsTy *Vector = getAsVector()) 62 delete Vector; 63 Data = RHS.Data; 64 RHS.Data = (NamedDecl *)nullptr; 65 return *this; 66 } 67 isNullStoredDeclsList68 bool isNull() const { return Data.isNull(); } 69 getAsDeclStoredDeclsList70 NamedDecl *getAsDecl() const { 71 return Data.dyn_cast<NamedDecl *>(); 72 } 73 getAsVectorAndHasExternalStoredDeclsList74 DeclsAndHasExternalTy getAsVectorAndHasExternal() const { 75 return Data.dyn_cast<DeclsAndHasExternalTy>(); 76 } 77 getAsVectorStoredDeclsList78 DeclsTy *getAsVector() const { 79 return getAsVectorAndHasExternal().getPointer(); 80 } 81 hasExternalDeclsStoredDeclsList82 bool hasExternalDecls() const { 83 return getAsVectorAndHasExternal().getInt(); 84 } 85 setHasExternalDeclsStoredDeclsList86 void setHasExternalDecls() { 87 if (DeclsTy *Vec = getAsVector()) 88 Data = DeclsAndHasExternalTy(Vec, true); 89 else { 90 DeclsTy *VT = new DeclsTy(); 91 if (NamedDecl *OldD = getAsDecl()) 92 VT->push_back(OldD); 93 Data = DeclsAndHasExternalTy(VT, true); 94 } 95 } 96 setOnlyValueStoredDeclsList97 void setOnlyValue(NamedDecl *ND) { 98 assert(!getAsVector() && "Not inline"); 99 Data = ND; 100 // Make sure that Data is a plain NamedDecl* so we can use its address 101 // at getLookupResult. 102 assert(*(NamedDecl **)&Data == ND && 103 "PointerUnion mangles the NamedDecl pointer!"); 104 } 105 removeStoredDeclsList106 void remove(NamedDecl *D) { 107 assert(!isNull() && "removing from empty list"); 108 if (NamedDecl *Singleton = getAsDecl()) { 109 assert(Singleton == D && "list is different singleton"); 110 (void)Singleton; 111 Data = (NamedDecl *)nullptr; 112 return; 113 } 114 115 DeclsTy &Vec = *getAsVector(); 116 DeclsTy::iterator I = llvm::find(Vec, D); 117 assert(I != Vec.end() && "list does not contain decl"); 118 Vec.erase(I); 119 120 assert(llvm::find(Vec, D) == Vec.end() && "list still contains decl"); 121 } 122 123 /// Remove any declarations which were imported from an external 124 /// AST source. removeExternalDeclsStoredDeclsList125 void removeExternalDecls() { 126 if (isNull()) { 127 // Nothing to do. 128 } else if (NamedDecl *Singleton = getAsDecl()) { 129 if (Singleton->isFromASTFile()) 130 *this = StoredDeclsList(); 131 } else { 132 DeclsTy &Vec = *getAsVector(); 133 Vec.erase(std::remove_if(Vec.begin(), Vec.end(), 134 [](Decl *D) { return D->isFromASTFile(); }), 135 Vec.end()); 136 // Don't have any external decls any more. 137 Data = DeclsAndHasExternalTy(&Vec, false); 138 } 139 } 140 141 /// getLookupResult - Return an array of all the decls that this list 142 /// represents. getLookupResultStoredDeclsList143 DeclContext::lookup_result getLookupResult() { 144 if (isNull()) 145 return DeclContext::lookup_result(); 146 147 // If we have a single NamedDecl, return it. 148 if (NamedDecl *ND = getAsDecl()) { 149 assert(!isNull() && "Empty list isn't allowed"); 150 151 // Data is a raw pointer to a NamedDecl*, return it. 152 return DeclContext::lookup_result(ND); 153 } 154 155 assert(getAsVector() && "Must have a vector at this point"); 156 DeclsTy &Vector = *getAsVector(); 157 158 // Otherwise, we have a range result. 159 return DeclContext::lookup_result(Vector); 160 } 161 162 /// HandleRedeclaration - If this is a redeclaration of an existing decl, 163 /// replace the old one with D and return true. Otherwise return false. HandleRedeclarationStoredDeclsList164 bool HandleRedeclaration(NamedDecl *D, bool IsKnownNewer) { 165 // Most decls only have one entry in their list, special case it. 166 if (NamedDecl *OldD = getAsDecl()) { 167 if (!D->declarationReplaces(OldD, IsKnownNewer)) 168 return false; 169 setOnlyValue(D); 170 return true; 171 } 172 173 // Determine if this declaration is actually a redeclaration. 174 DeclsTy &Vec = *getAsVector(); 175 for (DeclsTy::iterator OD = Vec.begin(), ODEnd = Vec.end(); 176 OD != ODEnd; ++OD) { 177 NamedDecl *OldD = *OD; 178 if (D->declarationReplaces(OldD, IsKnownNewer)) { 179 *OD = D; 180 return true; 181 } 182 } 183 184 return false; 185 } 186 187 /// AddSubsequentDecl - This is called on the second and later decl when it is 188 /// not a redeclaration to merge it into the appropriate place in our list. AddSubsequentDeclStoredDeclsList189 void AddSubsequentDecl(NamedDecl *D) { 190 assert(!isNull() && "don't AddSubsequentDecl when we have no decls"); 191 192 // If this is the second decl added to the list, convert this to vector 193 // form. 194 if (NamedDecl *OldD = getAsDecl()) { 195 DeclsTy *VT = new DeclsTy(); 196 VT->push_back(OldD); 197 Data = DeclsAndHasExternalTy(VT, false); 198 } 199 200 DeclsTy &Vec = *getAsVector(); 201 202 // Using directives end up in a special entry which contains only 203 // other using directives, so all this logic is wasted for them. 204 // But avoiding the logic wastes time in the far-more-common case 205 // that we're *not* adding a new using directive. 206 207 // Tag declarations always go at the end of the list so that an 208 // iterator which points at the first tag will start a span of 209 // decls that only contains tags. 210 if (D->hasTagIdentifierNamespace()) 211 Vec.push_back(D); 212 213 // Resolved using declarations go at the front of the list so that 214 // they won't show up in other lookup results. Unresolved using 215 // declarations (which are always in IDNS_Using | IDNS_Ordinary) 216 // follow that so that the using declarations will be contiguous. 217 else if (D->getIdentifierNamespace() & Decl::IDNS_Using) { 218 DeclsTy::iterator I = Vec.begin(); 219 if (D->getIdentifierNamespace() != Decl::IDNS_Using) { 220 while (I != Vec.end() && 221 (*I)->getIdentifierNamespace() == Decl::IDNS_Using) 222 ++I; 223 } 224 Vec.insert(I, D); 225 226 // All other declarations go at the end of the list, but before any 227 // tag declarations. But we can be clever about tag declarations 228 // because there can only ever be one in a scope. 229 } else if (!Vec.empty() && Vec.back()->hasTagIdentifierNamespace()) { 230 NamedDecl *TagD = Vec.back(); 231 Vec.back() = D; 232 Vec.push_back(TagD); 233 } else 234 Vec.push_back(D); 235 } 236 }; 237 238 class StoredDeclsMap 239 : public llvm::SmallDenseMap<DeclarationName, StoredDeclsList, 4> { 240 public: 241 static void DestroyAll(StoredDeclsMap *Map, bool Dependent); 242 243 private: 244 friend class ASTContext; // walks the chain deleting these 245 friend class DeclContext; 246 247 llvm::PointerIntPair<StoredDeclsMap*, 1> Previous; 248 }; 249 250 class DependentStoredDeclsMap : public StoredDeclsMap { 251 public: 252 DependentStoredDeclsMap() = default; 253 254 private: 255 friend class DeclContext; // iterates over diagnostics 256 friend class DependentDiagnostic; 257 258 DependentDiagnostic *FirstDiagnostic = nullptr; 259 }; 260 261 } // namespace clang 262 263 #endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H 264