clang/AST/DeclContextInternals.h

0001 //===- DeclContextInternals.h - DeclContext Representation ------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file defines the data structures used in the implementation
0010 //  of DeclContext.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H
0015 #define LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H
0016
0017 #include "clang/AST/ASTContext.h"
0018 #include "clang/AST/Decl.h"
0019 #include "clang/AST/DeclBase.h"
0020 #include "clang/AST/DeclCXX.h"
0021 #include "clang/AST/DeclarationName.h"
0022 #include "llvm/ADT/DenseMap.h"
0023 #include "llvm/ADT/PointerIntPair.h"
0024 #include "llvm/ADT/PointerUnion.h"
0025 #include <cassert>
0026
0027 namespace clang {
0028
0029 class DependentDiagnostic;
0030
0031 /// An array of decls optimized for the common case of only containing
0032 /// one entry.
0033 class StoredDeclsList {
0034   using Decls = DeclListNode::Decls;
0035
0036   /// A collection of declarations, with a flag to indicate if we have
0037   /// further external declarations.
0038   using DeclsAndHasExternalTy = llvm::PointerIntPair<Decls, 1, bool>;
0039
0040   /// The stored data, which will be either a pointer to a NamedDecl,
0041   /// or a pointer to a list with a flag to indicate if there are further
0042   /// external declarations.
0043   DeclsAndHasExternalTy Data;
0044
0045   template <typename Fn> DeclListNode::Decls *erase_if(Fn ShouldErase) {
0046     Decls List = Data.getPointer();
0047
0048     if (!List)
0049       return nullptr;
0050
0051     ASTContext &C = getASTContext();
0052     DeclListNode::Decls NewHead = nullptr;
0053     DeclListNode::Decls *NewLast = nullptr;
0054     DeclListNode::Decls *NewTail = &NewHead;
0055     while (true) {
0056       if (!ShouldErase(*DeclListNode::iterator(List))) {
0057         NewLast = NewTail;
0058         *NewTail = List;
0059         if (auto *Node = List.dyn_cast<DeclListNode*>()) {
0060           NewTail = &Node->Rest;
0061           List = Node->Rest;
0062         } else {
0063           break;
0064         }
0065       } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
0066         List = N->Rest;
0067         C.DeallocateDeclListNode(N);
0068       } else {
0069         // We're discarding the last declaration in the list. The last node we
0070         // want to keep (if any) will be of the form DeclListNode(D, <rest>);
0071         // replace it with just D.
0072         if (NewLast) {
0073           DeclListNode *Node = cast<DeclListNode *>(*NewLast);
0074           *NewLast = Node->D;
0075           C.DeallocateDeclListNode(Node);
0076         }
0077         break;
0078       }
0079     }
0080     Data.setPointer(NewHead);
0081
0082     assert(llvm::none_of(getLookupResult(), ShouldErase) && "Still exists!");
0083
0084     if (!Data.getPointer())
0085       // All declarations are erased.
0086       return nullptr;
0087     else if (isa<NamedDecl *>(NewHead))
0088       // The list only contains a declaration, the header itself.
0089       return (DeclListNode::Decls *)&Data;
0090     else {
0091       assert(NewLast && isa<NamedDecl *>(*NewLast) && "Not the tail?");
0092       return NewLast;
0093     }
0094   }
0095
0096   void erase(NamedDecl *ND) {
0097     erase_if([ND](NamedDecl *D) { return D == ND; });
0098   }
0099
0100 public:
0101   StoredDeclsList() = default;
0102
0103   StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) {
0104     RHS.Data.setPointer(nullptr);
0105     RHS.Data.setInt(false);
0106   }
0107
0108   void MaybeDeallocList() {
0109     if (isNull())
0110       return;
0111     // If this is a list-form, free the list.
0112     ASTContext &C = getASTContext();
0113     Decls List = Data.getPointer();
0114     while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) {
0115       List = ToDealloc->Rest;
0116       C.DeallocateDeclListNode(ToDealloc);
0117     }
0118   }
0119
0120   ~StoredDeclsList() {
0121     MaybeDeallocList();
0122   }
0123
0124   StoredDeclsList &operator=(StoredDeclsList &&RHS) {
0125     MaybeDeallocList();
0126
0127     Data = RHS.Data;
0128     RHS.Data.setPointer(nullptr);
0129     RHS.Data.setInt(false);
0130     return *this;
0131   }
0132
0133   bool isNull() const { return Data.getPointer().isNull(); }
0134
0135   ASTContext &getASTContext() {
0136     assert(!isNull() && "No ASTContext.");
0137     if (NamedDecl *ND = getAsDecl())
0138       return ND->getASTContext();
0139     return getAsList()->D->getASTContext();
0140   }
0141
0142   DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; }
0143
0144   NamedDecl *getAsDecl() const {
0145     return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>();
0146   }
0147
0148   DeclListNode *getAsList() const {
0149     return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>();
0150   }
0151
0152   bool hasExternalDecls() const {
0153     return getAsListAndHasExternal().getInt();
0154   }
0155
0156   void setHasExternalDecls() {
0157     Data.setInt(true);
0158   }
0159
0160   void remove(NamedDecl *D) {
0161     assert(!isNull() && "removing from empty list");
0162     erase(D);
0163   }
0164
0165   /// Remove any declarations which were imported from an external AST source.
0166   void removeExternalDecls() {
0167     erase_if([](NamedDecl *ND) { return ND->isFromASTFile(); });
0168
0169     // Don't have any pending external decls any more.
0170     Data.setInt(false);
0171   }
0172
0173   void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) {
0174     // Remove all declarations that are either external or are replaced with
0175     // external declarations with higher visibilities.
0176     DeclListNode::Decls *Tail = erase_if([Decls](NamedDecl *ND) {
0177       if (ND->isFromASTFile())
0178         return true;
0179       // FIXME: Can we get rid of this loop completely?
0180       for (NamedDecl *D : Decls)
0181         // Only replace the local declaration if the external declaration has
0182         // higher visibilities.
0183         if (D->getModuleOwnershipKind() <= ND->getModuleOwnershipKind() &&
0184             D->declarationReplaces(ND, /*IsKnownNewer=*/false))
0185           return true;
0186       return false;
0187     });
0188
0189     // Don't have any pending external decls any more.
0190     Data.setInt(false);
0191
0192     if (Decls.empty())
0193       return;
0194
0195     // Convert Decls into a list, in order.
0196     ASTContext &C = Decls.front()->getASTContext();
0197     DeclListNode::Decls DeclsAsList = Decls.back();
0198     for (size_t I = Decls.size() - 1; I != 0; --I) {
0199       DeclListNode *Node = C.AllocateDeclListNode(Decls[I - 1]);
0200       Node->Rest = DeclsAsList;
0201       DeclsAsList = Node;
0202     }
0203
0204     if (!Data.getPointer()) {
0205       Data.setPointer(DeclsAsList);
0206       return;
0207     }
0208
0209     // Append the Decls.
0210     DeclListNode *Node = C.AllocateDeclListNode(cast<NamedDecl *>(*Tail));
0211     Node->Rest = DeclsAsList;
0212     *Tail = Node;
0213   }
0214
0215   /// Return the list of all the decls.
0216   DeclContext::lookup_result getLookupResult() const {
0217     return DeclContext::lookup_result(Data.getPointer());
0218   }
0219
0220   /// If this is a redeclaration of an existing decl, replace the old one with
0221   /// D. Otherwise, append D.
0222   void addOrReplaceDecl(NamedDecl *D) {
0223     const bool IsKnownNewer = true;
0224
0225     if (isNull()) {
0226       Data.setPointer(D);
0227       return;
0228     }
0229
0230     // Most decls only have one entry in their list, special case it.
0231     if (NamedDecl *OldD = getAsDecl()) {
0232       if (D->declarationReplaces(OldD, IsKnownNewer)) {
0233         Data.setPointer(D);
0234         return;
0235       }
0236
0237       // Add D after OldD.
0238       ASTContext &C = D->getASTContext();
0239       DeclListNode *Node = C.AllocateDeclListNode(OldD);
0240       Node->Rest = D;
0241       Data.setPointer(Node);
0242       return;
0243     }
0244
0245     // FIXME: Move the assert before the single decl case when we fix the
0246     // duplication coming from the ASTReader reading builtin types.
0247     assert(!llvm::is_contained(getLookupResult(), D) && "Already exists!");
0248     // Determine if this declaration is actually a redeclaration.
0249     for (DeclListNode *N = getAsList(); /*return in loop*/;
0250          N = N->Rest.dyn_cast<DeclListNode *>()) {
0251       if (D->declarationReplaces(N->D, IsKnownNewer)) {
0252         N->D = D;
0253         return;
0254       }
0255       if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) {
0256         if (D->declarationReplaces(ND, IsKnownNewer)) {
0257           N->Rest = D;
0258           return;
0259         }
0260
0261         // Add D after ND.
0262         ASTContext &C = D->getASTContext();
0263         DeclListNode *Node = C.AllocateDeclListNode(ND);
0264         N->Rest = Node;
0265         Node->Rest = D;
0266         return;
0267       }
0268     }
0269   }
0270
0271   /// Add a declaration to the list without checking if it replaces anything.
0272   void prependDeclNoReplace(NamedDecl *D) {
0273     if (isNull()) {
0274       Data.setPointer(D);
0275       return;
0276     }
0277
0278     ASTContext &C = D->getASTContext();
0279     DeclListNode *Node = C.AllocateDeclListNode(D);
0280     Node->Rest = Data.getPointer();
0281     Data.setPointer(Node);
0282   }
0283
0284   LLVM_DUMP_METHOD void dump() const {
0285     Decls D = Data.getPointer();
0286     if (!D) {
0287       llvm::errs() << "<null>\n";
0288       return;
0289     }
0290
0291     while (true) {
0292       if (auto *Node = D.dyn_cast<DeclListNode*>()) {
0293         llvm::errs() << '[' << Node->D << "] -> ";
0294         D = Node->Rest;
0295       } else {
0296         llvm::errs() << '[' << cast<NamedDecl *>(D) << "]\n";
0297         return;
0298       }
0299     }
0300   }
0301 };
0302
0303 class StoredDeclsMap
0304     : public llvm::SmallDenseMap<DeclarationName, StoredDeclsList, 4> {
0305   friend class ASTContext; // walks the chain deleting these
0306   friend class DeclContext;
0307
0308   llvm::PointerIntPair<StoredDeclsMap*, 1> Previous;
0309 public:
0310   static void DestroyAll(StoredDeclsMap *Map, bool Dependent);
0311 };
0312
0313 class DependentStoredDeclsMap : public StoredDeclsMap {
0314   friend class DeclContext; // iterates over diagnostics
0315   friend class DependentDiagnostic;
0316
0317   DependentDiagnostic *FirstDiagnostic = nullptr;
0318 public:
0319   DependentStoredDeclsMap() = default;
0320 };
0321
0322 } // namespace clang
0323
0324 #endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H