106f32e7eSjoerg //===- DeclContextInternals.h - DeclContext Representation ------*- C++ -*-===// 206f32e7eSjoerg // 306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information. 506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 606f32e7eSjoerg // 706f32e7eSjoerg //===----------------------------------------------------------------------===// 806f32e7eSjoerg // 906f32e7eSjoerg // This file defines the data structures used in the implementation 1006f32e7eSjoerg // of DeclContext. 1106f32e7eSjoerg // 1206f32e7eSjoerg //===----------------------------------------------------------------------===// 1306f32e7eSjoerg 1406f32e7eSjoerg #ifndef LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H 1506f32e7eSjoerg #define LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H 1606f32e7eSjoerg 17*13fbcb42Sjoerg #include "clang/AST/ASTContext.h" 1806f32e7eSjoerg #include "clang/AST/Decl.h" 1906f32e7eSjoerg #include "clang/AST/DeclBase.h" 2006f32e7eSjoerg #include "clang/AST/DeclCXX.h" 2106f32e7eSjoerg #include "clang/AST/DeclarationName.h" 2206f32e7eSjoerg #include "llvm/ADT/DenseMap.h" 2306f32e7eSjoerg #include "llvm/ADT/PointerIntPair.h" 2406f32e7eSjoerg #include "llvm/ADT/PointerUnion.h" 2506f32e7eSjoerg #include <cassert> 2606f32e7eSjoerg 2706f32e7eSjoerg namespace clang { 2806f32e7eSjoerg 2906f32e7eSjoerg class DependentDiagnostic; 3006f32e7eSjoerg 3106f32e7eSjoerg /// An array of decls optimized for the common case of only containing 3206f32e7eSjoerg /// one entry. 33*13fbcb42Sjoerg class StoredDeclsList { 34*13fbcb42Sjoerg using Decls = DeclListNode::Decls; 3506f32e7eSjoerg 3606f32e7eSjoerg /// A collection of declarations, with a flag to indicate if we have 3706f32e7eSjoerg /// further external declarations. 38*13fbcb42Sjoerg using DeclsAndHasExternalTy = llvm::PointerIntPair<Decls, 1, bool>; 3906f32e7eSjoerg 4006f32e7eSjoerg /// The stored data, which will be either a pointer to a NamedDecl, 41*13fbcb42Sjoerg /// or a pointer to a list with a flag to indicate if there are further 4206f32e7eSjoerg /// external declarations. 43*13fbcb42Sjoerg DeclsAndHasExternalTy Data; 44*13fbcb42Sjoerg 45*13fbcb42Sjoerg template<typename Fn> erase_if(Fn ShouldErase)46*13fbcb42Sjoerg void erase_if(Fn ShouldErase) { 47*13fbcb42Sjoerg Decls List = Data.getPointer(); 48*13fbcb42Sjoerg if (!List) 49*13fbcb42Sjoerg return; 50*13fbcb42Sjoerg ASTContext &C = getASTContext(); 51*13fbcb42Sjoerg DeclListNode::Decls NewHead = nullptr; 52*13fbcb42Sjoerg DeclListNode::Decls *NewLast = nullptr; 53*13fbcb42Sjoerg DeclListNode::Decls *NewTail = &NewHead; 54*13fbcb42Sjoerg while (true) { 55*13fbcb42Sjoerg if (!ShouldErase(*DeclListNode::iterator(List))) { 56*13fbcb42Sjoerg NewLast = NewTail; 57*13fbcb42Sjoerg *NewTail = List; 58*13fbcb42Sjoerg if (auto *Node = List.dyn_cast<DeclListNode*>()) { 59*13fbcb42Sjoerg NewTail = &Node->Rest; 60*13fbcb42Sjoerg List = Node->Rest; 61*13fbcb42Sjoerg } else { 62*13fbcb42Sjoerg break; 63*13fbcb42Sjoerg } 64*13fbcb42Sjoerg } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) { 65*13fbcb42Sjoerg List = N->Rest; 66*13fbcb42Sjoerg C.DeallocateDeclListNode(N); 67*13fbcb42Sjoerg } else { 68*13fbcb42Sjoerg // We're discarding the last declaration in the list. The last node we 69*13fbcb42Sjoerg // want to keep (if any) will be of the form DeclListNode(D, <rest>); 70*13fbcb42Sjoerg // replace it with just D. 71*13fbcb42Sjoerg if (NewLast) { 72*13fbcb42Sjoerg DeclListNode *Node = NewLast->get<DeclListNode*>(); 73*13fbcb42Sjoerg *NewLast = Node->D; 74*13fbcb42Sjoerg C.DeallocateDeclListNode(Node); 75*13fbcb42Sjoerg } 76*13fbcb42Sjoerg break; 77*13fbcb42Sjoerg } 78*13fbcb42Sjoerg } 79*13fbcb42Sjoerg Data.setPointer(NewHead); 80*13fbcb42Sjoerg 81*13fbcb42Sjoerg assert(llvm::find_if(getLookupResult(), ShouldErase) == 82*13fbcb42Sjoerg getLookupResult().end() && "Still exists!"); 83*13fbcb42Sjoerg } 84*13fbcb42Sjoerg erase(NamedDecl * ND)85*13fbcb42Sjoerg void erase(NamedDecl *ND) { 86*13fbcb42Sjoerg erase_if([ND](NamedDecl *D) { return D == ND; }); 87*13fbcb42Sjoerg } 8806f32e7eSjoerg 8906f32e7eSjoerg public: 9006f32e7eSjoerg StoredDeclsList() = default; 9106f32e7eSjoerg StoredDeclsList(StoredDeclsList && RHS)9206f32e7eSjoerg StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) { 93*13fbcb42Sjoerg RHS.Data.setPointer(nullptr); 94*13fbcb42Sjoerg RHS.Data.setInt(0); 95*13fbcb42Sjoerg } 96*13fbcb42Sjoerg MaybeDeallocList()97*13fbcb42Sjoerg void MaybeDeallocList() { 98*13fbcb42Sjoerg if (isNull()) 99*13fbcb42Sjoerg return; 100*13fbcb42Sjoerg // If this is a list-form, free the list. 101*13fbcb42Sjoerg ASTContext &C = getASTContext(); 102*13fbcb42Sjoerg Decls List = Data.getPointer(); 103*13fbcb42Sjoerg while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) { 104*13fbcb42Sjoerg List = ToDealloc->Rest; 105*13fbcb42Sjoerg C.DeallocateDeclListNode(ToDealloc); 106*13fbcb42Sjoerg } 10706f32e7eSjoerg } 10806f32e7eSjoerg ~StoredDeclsList()10906f32e7eSjoerg ~StoredDeclsList() { 110*13fbcb42Sjoerg MaybeDeallocList(); 11106f32e7eSjoerg } 11206f32e7eSjoerg 11306f32e7eSjoerg StoredDeclsList &operator=(StoredDeclsList &&RHS) { 114*13fbcb42Sjoerg MaybeDeallocList(); 115*13fbcb42Sjoerg 11606f32e7eSjoerg Data = RHS.Data; 117*13fbcb42Sjoerg RHS.Data.setPointer(nullptr); 118*13fbcb42Sjoerg RHS.Data.setInt(0); 11906f32e7eSjoerg return *this; 12006f32e7eSjoerg } 12106f32e7eSjoerg isNull()122*13fbcb42Sjoerg bool isNull() const { return Data.getPointer().isNull(); } 123*13fbcb42Sjoerg getASTContext()124*13fbcb42Sjoerg ASTContext &getASTContext() { 125*13fbcb42Sjoerg assert(!isNull() && "No ASTContext."); 126*13fbcb42Sjoerg if (NamedDecl *ND = getAsDecl()) 127*13fbcb42Sjoerg return ND->getASTContext(); 128*13fbcb42Sjoerg return getAsList()->D->getASTContext(); 129*13fbcb42Sjoerg } 130*13fbcb42Sjoerg getAsListAndHasExternal()131*13fbcb42Sjoerg DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; } 13206f32e7eSjoerg getAsDecl()13306f32e7eSjoerg NamedDecl *getAsDecl() const { 134*13fbcb42Sjoerg return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>(); 13506f32e7eSjoerg } 13606f32e7eSjoerg getAsList()137*13fbcb42Sjoerg DeclListNode *getAsList() const { 138*13fbcb42Sjoerg return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>(); 13906f32e7eSjoerg } 14006f32e7eSjoerg hasExternalDecls()14106f32e7eSjoerg bool hasExternalDecls() const { 142*13fbcb42Sjoerg return getAsListAndHasExternal().getInt(); 14306f32e7eSjoerg } 14406f32e7eSjoerg setHasExternalDecls()14506f32e7eSjoerg void setHasExternalDecls() { 146*13fbcb42Sjoerg Data.setInt(1); 14706f32e7eSjoerg } 14806f32e7eSjoerg remove(NamedDecl * D)14906f32e7eSjoerg void remove(NamedDecl *D) { 15006f32e7eSjoerg assert(!isNull() && "removing from empty list"); 151*13fbcb42Sjoerg erase(D); 152*13fbcb42Sjoerg } 153*13fbcb42Sjoerg 154*13fbcb42Sjoerg /// Remove any declarations which were imported from an external AST source. removeExternalDecls()155*13fbcb42Sjoerg void removeExternalDecls() { 156*13fbcb42Sjoerg erase_if([](NamedDecl *ND) { return ND->isFromASTFile(); }); 157*13fbcb42Sjoerg 158*13fbcb42Sjoerg // Don't have any pending external decls any more. 159*13fbcb42Sjoerg Data.setInt(0); 160*13fbcb42Sjoerg } 161*13fbcb42Sjoerg replaceExternalDecls(ArrayRef<NamedDecl * > Decls)162*13fbcb42Sjoerg void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) { 163*13fbcb42Sjoerg // Remove all declarations that are either external or are replaced with 164*13fbcb42Sjoerg // external declarations. 165*13fbcb42Sjoerg erase_if([Decls](NamedDecl *ND) { 166*13fbcb42Sjoerg if (ND->isFromASTFile()) 167*13fbcb42Sjoerg return true; 168*13fbcb42Sjoerg for (NamedDecl *D : Decls) 169*13fbcb42Sjoerg if (D->declarationReplaces(ND, /*IsKnownNewer=*/false)) 170*13fbcb42Sjoerg return true; 171*13fbcb42Sjoerg return false; 172*13fbcb42Sjoerg }); 173*13fbcb42Sjoerg 174*13fbcb42Sjoerg // Don't have any pending external decls any more. 175*13fbcb42Sjoerg Data.setInt(0); 176*13fbcb42Sjoerg 177*13fbcb42Sjoerg if (Decls.empty()) 178*13fbcb42Sjoerg return; 179*13fbcb42Sjoerg 180*13fbcb42Sjoerg // Convert Decls into a list, in order. 181*13fbcb42Sjoerg ASTContext &C = Decls.front()->getASTContext(); 182*13fbcb42Sjoerg DeclListNode::Decls DeclsAsList = Decls.back(); 183*13fbcb42Sjoerg for (size_t I = Decls.size() - 1; I != 0; --I) { 184*13fbcb42Sjoerg DeclListNode *Node = C.AllocateDeclListNode(Decls[I - 1]); 185*13fbcb42Sjoerg Node->Rest = DeclsAsList; 186*13fbcb42Sjoerg DeclsAsList = Node; 187*13fbcb42Sjoerg } 188*13fbcb42Sjoerg 189*13fbcb42Sjoerg DeclListNode::Decls Head = Data.getPointer(); 190*13fbcb42Sjoerg if (Head.isNull()) { 191*13fbcb42Sjoerg Data.setPointer(DeclsAsList); 19206f32e7eSjoerg return; 19306f32e7eSjoerg } 19406f32e7eSjoerg 195*13fbcb42Sjoerg // Find the end of the existing list. 196*13fbcb42Sjoerg // FIXME: It would be possible to preserve information from erase_if to 197*13fbcb42Sjoerg // avoid this rescan looking for the end of the list. 198*13fbcb42Sjoerg DeclListNode::Decls *Tail = &Head; 199*13fbcb42Sjoerg while (DeclListNode *Node = Tail->dyn_cast<DeclListNode *>()) 200*13fbcb42Sjoerg Tail = &Node->Rest; 20106f32e7eSjoerg 202*13fbcb42Sjoerg // Append the Decls. 203*13fbcb42Sjoerg DeclListNode *Node = C.AllocateDeclListNode(Tail->get<NamedDecl *>()); 204*13fbcb42Sjoerg Node->Rest = DeclsAsList; 205*13fbcb42Sjoerg *Tail = Node; 206*13fbcb42Sjoerg Data.setPointer(Head); 20706f32e7eSjoerg } 20806f32e7eSjoerg 209*13fbcb42Sjoerg /// Return an array of all the decls that this list represents. getLookupResult()210*13fbcb42Sjoerg DeclContext::lookup_result getLookupResult() const { 211*13fbcb42Sjoerg return DeclContext::lookup_result(Data.getPointer()); 212*13fbcb42Sjoerg } 213*13fbcb42Sjoerg 214*13fbcb42Sjoerg /// If this is a redeclaration of an existing decl, replace the old one with 215*13fbcb42Sjoerg /// D. Otherwise, append D. addOrReplaceDecl(NamedDecl * D)216*13fbcb42Sjoerg void addOrReplaceDecl(NamedDecl *D) { 217*13fbcb42Sjoerg const bool IsKnownNewer = true; 218*13fbcb42Sjoerg 21906f32e7eSjoerg if (isNull()) { 220*13fbcb42Sjoerg Data.setPointer(D); 221*13fbcb42Sjoerg return; 22206f32e7eSjoerg } 22306f32e7eSjoerg 22406f32e7eSjoerg // Most decls only have one entry in their list, special case it. 22506f32e7eSjoerg if (NamedDecl *OldD = getAsDecl()) { 22606f32e7eSjoerg if (D->declarationReplaces(OldD, IsKnownNewer)) { 227*13fbcb42Sjoerg Data.setPointer(D); 228*13fbcb42Sjoerg return; 229*13fbcb42Sjoerg } 230*13fbcb42Sjoerg 231*13fbcb42Sjoerg // Add D after OldD. 232*13fbcb42Sjoerg ASTContext &C = D->getASTContext(); 233*13fbcb42Sjoerg DeclListNode *Node = C.AllocateDeclListNode(OldD); 234*13fbcb42Sjoerg Node->Rest = D; 235*13fbcb42Sjoerg Data.setPointer(Node); 236*13fbcb42Sjoerg return; 237*13fbcb42Sjoerg } 238*13fbcb42Sjoerg 239*13fbcb42Sjoerg // FIXME: Move the assert before the single decl case when we fix the 240*13fbcb42Sjoerg // duplication coming from the ASTReader reading builtin types. 241*13fbcb42Sjoerg assert(!llvm::is_contained(getLookupResult(), D) && "Already exists!"); 242*13fbcb42Sjoerg // Determine if this declaration is actually a redeclaration. 243*13fbcb42Sjoerg for (DeclListNode *N = getAsList(); /*return in loop*/; 244*13fbcb42Sjoerg N = N->Rest.dyn_cast<DeclListNode *>()) { 245*13fbcb42Sjoerg if (D->declarationReplaces(N->D, IsKnownNewer)) { 246*13fbcb42Sjoerg N->D = D; 247*13fbcb42Sjoerg return; 248*13fbcb42Sjoerg } 249*13fbcb42Sjoerg if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) { 250*13fbcb42Sjoerg if (D->declarationReplaces(ND, IsKnownNewer)) { 251*13fbcb42Sjoerg N->Rest = D; 252*13fbcb42Sjoerg return; 253*13fbcb42Sjoerg } 254*13fbcb42Sjoerg 255*13fbcb42Sjoerg // Add D after ND. 256*13fbcb42Sjoerg ASTContext &C = D->getASTContext(); 257*13fbcb42Sjoerg DeclListNode *Node = C.AllocateDeclListNode(ND); 258*13fbcb42Sjoerg N->Rest = Node; 259*13fbcb42Sjoerg Node->Rest = D; 260*13fbcb42Sjoerg return; 261*13fbcb42Sjoerg } 26206f32e7eSjoerg } 26306f32e7eSjoerg } 26406f32e7eSjoerg 265*13fbcb42Sjoerg /// Add a declaration to the list without checking if it replaces anything. prependDeclNoReplace(NamedDecl * D)266*13fbcb42Sjoerg void prependDeclNoReplace(NamedDecl *D) { 267*13fbcb42Sjoerg if (isNull()) { 268*13fbcb42Sjoerg Data.setPointer(D); 269*13fbcb42Sjoerg return; 27006f32e7eSjoerg } 27106f32e7eSjoerg 272*13fbcb42Sjoerg ASTContext &C = D->getASTContext(); 273*13fbcb42Sjoerg DeclListNode *Node = C.AllocateDeclListNode(D); 274*13fbcb42Sjoerg Node->Rest = Data.getPointer(); 275*13fbcb42Sjoerg Data.setPointer(Node); 27606f32e7eSjoerg } 27706f32e7eSjoerg dump()278*13fbcb42Sjoerg LLVM_DUMP_METHOD void dump() const { 279*13fbcb42Sjoerg Decls D = Data.getPointer(); 280*13fbcb42Sjoerg if (!D) { 281*13fbcb42Sjoerg llvm::errs() << "<null>\n"; 282*13fbcb42Sjoerg return; 28306f32e7eSjoerg } 28406f32e7eSjoerg 285*13fbcb42Sjoerg while (true) { 286*13fbcb42Sjoerg if (auto *Node = D.dyn_cast<DeclListNode*>()) { 287*13fbcb42Sjoerg llvm::errs() << '[' << Node->D << "] -> "; 288*13fbcb42Sjoerg D = Node->Rest; 289*13fbcb42Sjoerg } else { 290*13fbcb42Sjoerg llvm::errs() << '[' << D.get<NamedDecl*>() << "]\n"; 291*13fbcb42Sjoerg return; 292*13fbcb42Sjoerg } 293*13fbcb42Sjoerg } 29406f32e7eSjoerg } 29506f32e7eSjoerg }; 29606f32e7eSjoerg 29706f32e7eSjoerg class StoredDeclsMap 29806f32e7eSjoerg : public llvm::SmallDenseMap<DeclarationName, StoredDeclsList, 4> { 29906f32e7eSjoerg friend class ASTContext; // walks the chain deleting these 30006f32e7eSjoerg friend class DeclContext; 30106f32e7eSjoerg 30206f32e7eSjoerg llvm::PointerIntPair<StoredDeclsMap*, 1> Previous; 303*13fbcb42Sjoerg public: 304*13fbcb42Sjoerg static void DestroyAll(StoredDeclsMap *Map, bool Dependent); 30506f32e7eSjoerg }; 30606f32e7eSjoerg 30706f32e7eSjoerg class DependentStoredDeclsMap : public StoredDeclsMap { 30806f32e7eSjoerg friend class DeclContext; // iterates over diagnostics 30906f32e7eSjoerg friend class DependentDiagnostic; 31006f32e7eSjoerg 31106f32e7eSjoerg DependentDiagnostic *FirstDiagnostic = nullptr; 312*13fbcb42Sjoerg public: 313*13fbcb42Sjoerg DependentStoredDeclsMap() = default; 31406f32e7eSjoerg }; 31506f32e7eSjoerg 31606f32e7eSjoerg } // namespace clang 31706f32e7eSjoerg 31806f32e7eSjoerg #endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H 319