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/ASTContext.h" 18 #include "clang/AST/Decl.h" 19 #include "clang/AST/DeclBase.h" 20 #include "clang/AST/DeclCXX.h" 21 #include "clang/AST/DeclarationName.h" 22 #include "llvm/ADT/DenseMap.h" 23 #include "llvm/ADT/PointerIntPair.h" 24 #include "llvm/ADT/PointerUnion.h" 25 #include <cassert> 26 27 namespace clang { 28 29 class DependentDiagnostic; 30 31 /// An array of decls optimized for the common case of only containing 32 /// one entry. 33 class StoredDeclsList { 34 using Decls = DeclListNode::Decls; 35 36 /// A collection of declarations, with a flag to indicate if we have 37 /// further external declarations. 38 using DeclsAndHasExternalTy = llvm::PointerIntPair<Decls, 1, bool>; 39 40 /// The stored data, which will be either a pointer to a NamedDecl, 41 /// or a pointer to a list with a flag to indicate if there are further 42 /// external declarations. 43 DeclsAndHasExternalTy Data; 44 45 template<typename Fn> erase_if(Fn ShouldErase)46 void erase_if(Fn ShouldErase) { 47 Decls List = Data.getPointer(); 48 if (!List) 49 return; 50 ASTContext &C = getASTContext(); 51 DeclListNode::Decls NewHead = nullptr; 52 DeclListNode::Decls *NewLast = nullptr; 53 DeclListNode::Decls *NewTail = &NewHead; 54 while (true) { 55 if (!ShouldErase(*DeclListNode::iterator(List))) { 56 NewLast = NewTail; 57 *NewTail = List; 58 if (auto *Node = List.dyn_cast<DeclListNode*>()) { 59 NewTail = &Node->Rest; 60 List = Node->Rest; 61 } else { 62 break; 63 } 64 } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) { 65 List = N->Rest; 66 C.DeallocateDeclListNode(N); 67 } else { 68 // We're discarding the last declaration in the list. The last node we 69 // want to keep (if any) will be of the form DeclListNode(D, <rest>); 70 // replace it with just D. 71 if (NewLast) { 72 DeclListNode *Node = NewLast->get<DeclListNode*>(); 73 *NewLast = Node->D; 74 C.DeallocateDeclListNode(Node); 75 } 76 break; 77 } 78 } 79 Data.setPointer(NewHead); 80 81 assert(llvm::find_if(getLookupResult(), ShouldErase) == 82 getLookupResult().end() && "Still exists!"); 83 } 84 erase(NamedDecl * ND)85 void erase(NamedDecl *ND) { 86 erase_if([ND](NamedDecl *D) { return D == ND; }); 87 } 88 89 public: 90 StoredDeclsList() = default; 91 StoredDeclsList(StoredDeclsList && RHS)92 StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) { 93 RHS.Data.setPointer(nullptr); 94 RHS.Data.setInt(0); 95 } 96 MaybeDeallocList()97 void MaybeDeallocList() { 98 if (isNull()) 99 return; 100 // If this is a list-form, free the list. 101 ASTContext &C = getASTContext(); 102 Decls List = Data.getPointer(); 103 while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) { 104 List = ToDealloc->Rest; 105 C.DeallocateDeclListNode(ToDealloc); 106 } 107 } 108 ~StoredDeclsList()109 ~StoredDeclsList() { 110 MaybeDeallocList(); 111 } 112 113 StoredDeclsList &operator=(StoredDeclsList &&RHS) { 114 MaybeDeallocList(); 115 116 Data = RHS.Data; 117 RHS.Data.setPointer(nullptr); 118 RHS.Data.setInt(0); 119 return *this; 120 } 121 isNull()122 bool isNull() const { return Data.getPointer().isNull(); } 123 getASTContext()124 ASTContext &getASTContext() { 125 assert(!isNull() && "No ASTContext."); 126 if (NamedDecl *ND = getAsDecl()) 127 return ND->getASTContext(); 128 return getAsList()->D->getASTContext(); 129 } 130 getAsListAndHasExternal()131 DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; } 132 getAsDecl()133 NamedDecl *getAsDecl() const { 134 return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>(); 135 } 136 getAsList()137 DeclListNode *getAsList() const { 138 return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>(); 139 } 140 hasExternalDecls()141 bool hasExternalDecls() const { 142 return getAsListAndHasExternal().getInt(); 143 } 144 setHasExternalDecls()145 void setHasExternalDecls() { 146 Data.setInt(1); 147 } 148 remove(NamedDecl * D)149 void remove(NamedDecl *D) { 150 assert(!isNull() && "removing from empty list"); 151 erase(D); 152 } 153 154 /// Remove any declarations which were imported from an external AST source. removeExternalDecls()155 void removeExternalDecls() { 156 erase_if([](NamedDecl *ND) { return ND->isFromASTFile(); }); 157 158 // Don't have any pending external decls any more. 159 Data.setInt(0); 160 } 161 replaceExternalDecls(ArrayRef<NamedDecl * > Decls)162 void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) { 163 // Remove all declarations that are either external or are replaced with 164 // external declarations. 165 erase_if([Decls](NamedDecl *ND) { 166 if (ND->isFromASTFile()) 167 return true; 168 for (NamedDecl *D : Decls) 169 if (D->declarationReplaces(ND, /*IsKnownNewer=*/false)) 170 return true; 171 return false; 172 }); 173 174 // Don't have any pending external decls any more. 175 Data.setInt(0); 176 177 if (Decls.empty()) 178 return; 179 180 // Convert Decls into a list, in order. 181 ASTContext &C = Decls.front()->getASTContext(); 182 DeclListNode::Decls DeclsAsList = Decls.back(); 183 for (size_t I = Decls.size() - 1; I != 0; --I) { 184 DeclListNode *Node = C.AllocateDeclListNode(Decls[I - 1]); 185 Node->Rest = DeclsAsList; 186 DeclsAsList = Node; 187 } 188 189 DeclListNode::Decls Head = Data.getPointer(); 190 if (Head.isNull()) { 191 Data.setPointer(DeclsAsList); 192 return; 193 } 194 195 // Find the end of the existing list. 196 // FIXME: It would be possible to preserve information from erase_if to 197 // avoid this rescan looking for the end of the list. 198 DeclListNode::Decls *Tail = &Head; 199 while (DeclListNode *Node = Tail->dyn_cast<DeclListNode *>()) 200 Tail = &Node->Rest; 201 202 // Append the Decls. 203 DeclListNode *Node = C.AllocateDeclListNode(Tail->get<NamedDecl *>()); 204 Node->Rest = DeclsAsList; 205 *Tail = Node; 206 Data.setPointer(Head); 207 } 208 209 /// Return an array of all the decls that this list represents. getLookupResult()210 DeclContext::lookup_result getLookupResult() const { 211 return DeclContext::lookup_result(Data.getPointer()); 212 } 213 214 /// If this is a redeclaration of an existing decl, replace the old one with 215 /// D. Otherwise, append D. addOrReplaceDecl(NamedDecl * D)216 void addOrReplaceDecl(NamedDecl *D) { 217 const bool IsKnownNewer = true; 218 219 if (isNull()) { 220 Data.setPointer(D); 221 return; 222 } 223 224 // Most decls only have one entry in their list, special case it. 225 if (NamedDecl *OldD = getAsDecl()) { 226 if (D->declarationReplaces(OldD, IsKnownNewer)) { 227 Data.setPointer(D); 228 return; 229 } 230 231 // Add D after OldD. 232 ASTContext &C = D->getASTContext(); 233 DeclListNode *Node = C.AllocateDeclListNode(OldD); 234 Node->Rest = D; 235 Data.setPointer(Node); 236 return; 237 } 238 239 // FIXME: Move the assert before the single decl case when we fix the 240 // duplication coming from the ASTReader reading builtin types. 241 assert(!llvm::is_contained(getLookupResult(), D) && "Already exists!"); 242 // Determine if this declaration is actually a redeclaration. 243 for (DeclListNode *N = getAsList(); /*return in loop*/; 244 N = N->Rest.dyn_cast<DeclListNode *>()) { 245 if (D->declarationReplaces(N->D, IsKnownNewer)) { 246 N->D = D; 247 return; 248 } 249 if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) { 250 if (D->declarationReplaces(ND, IsKnownNewer)) { 251 N->Rest = D; 252 return; 253 } 254 255 // Add D after ND. 256 ASTContext &C = D->getASTContext(); 257 DeclListNode *Node = C.AllocateDeclListNode(ND); 258 N->Rest = Node; 259 Node->Rest = D; 260 return; 261 } 262 } 263 } 264 265 /// Add a declaration to the list without checking if it replaces anything. prependDeclNoReplace(NamedDecl * D)266 void prependDeclNoReplace(NamedDecl *D) { 267 if (isNull()) { 268 Data.setPointer(D); 269 return; 270 } 271 272 ASTContext &C = D->getASTContext(); 273 DeclListNode *Node = C.AllocateDeclListNode(D); 274 Node->Rest = Data.getPointer(); 275 Data.setPointer(Node); 276 } 277 dump()278 LLVM_DUMP_METHOD void dump() const { 279 Decls D = Data.getPointer(); 280 if (!D) { 281 llvm::errs() << "<null>\n"; 282 return; 283 } 284 285 while (true) { 286 if (auto *Node = D.dyn_cast<DeclListNode*>()) { 287 llvm::errs() << '[' << Node->D << "] -> "; 288 D = Node->Rest; 289 } else { 290 llvm::errs() << '[' << D.get<NamedDecl*>() << "]\n"; 291 return; 292 } 293 } 294 } 295 }; 296 297 class StoredDeclsMap 298 : public llvm::SmallDenseMap<DeclarationName, StoredDeclsList, 4> { 299 friend class ASTContext; // walks the chain deleting these 300 friend class DeclContext; 301 302 llvm::PointerIntPair<StoredDeclsMap*, 1> Previous; 303 public: 304 static void DestroyAll(StoredDeclsMap *Map, bool Dependent); 305 }; 306 307 class DependentStoredDeclsMap : public StoredDeclsMap { 308 friend class DeclContext; // iterates over diagnostics 309 friend class DependentDiagnostic; 310 311 DependentDiagnostic *FirstDiagnostic = nullptr; 312 public: 313 DependentStoredDeclsMap() = default; 314 }; 315 316 } // namespace clang 317 318 #endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H 319