1 //===-- DeclContextInternals.h - DeclContext Representation -----*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defines the data structures used in the implementation
11 //  of DeclContext.
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/DeclCXX.h"
19 #include "clang/AST/DeclarationName.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/PointerIntPair.h"
22 #include "llvm/ADT/PointerUnion.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include <algorithm>
25 
26 namespace clang {
27 
28 class DependentDiagnostic;
29 
30 /// \brief An array of decls optimized for the common case of only containing
31 /// one entry.
32 struct StoredDeclsList {
33 
34   /// \brief When in vector form, this is what the Data pointer points to.
35   typedef SmallVector<NamedDecl *, 4> DeclsTy;
36 
37   /// \brief A collection of declarations, with a flag to indicate if we have
38   /// further external declarations.
39   typedef llvm::PointerIntPair<DeclsTy *, 1, bool> DeclsAndHasExternalTy;
40 
41   /// \brief The stored data, which will be either a pointer to a NamedDecl,
42   /// or a pointer to a vector with a flag to indicate if there are further
43   /// external declarations.
44   llvm::PointerUnion<NamedDecl*, DeclsAndHasExternalTy> Data;
45 
46 public:
StoredDeclsListStoredDeclsList47   StoredDeclsList() {}
48 
StoredDeclsListStoredDeclsList49   StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) {
50     RHS.Data = (NamedDecl *)nullptr;
51   }
52 
~StoredDeclsListStoredDeclsList53   ~StoredDeclsList() {
54     // If this is a vector-form, free the vector.
55     if (DeclsTy *Vector = getAsVector())
56       delete Vector;
57   }
58 
59   StoredDeclsList &operator=(StoredDeclsList &&RHS) {
60     if (DeclsTy *Vector = getAsVector())
61       delete Vector;
62     Data = RHS.Data;
63     RHS.Data = (NamedDecl *)nullptr;
64     return *this;
65   }
66 
isNullStoredDeclsList67   bool isNull() const { return Data.isNull(); }
68 
getAsDeclStoredDeclsList69   NamedDecl *getAsDecl() const {
70     return Data.dyn_cast<NamedDecl *>();
71   }
72 
getAsVectorAndHasExternalStoredDeclsList73   DeclsAndHasExternalTy getAsVectorAndHasExternal() const {
74     return Data.dyn_cast<DeclsAndHasExternalTy>();
75   }
76 
getAsVectorStoredDeclsList77   DeclsTy *getAsVector() const {
78     return getAsVectorAndHasExternal().getPointer();
79   }
80 
hasExternalDeclsStoredDeclsList81   bool hasExternalDecls() const {
82     return getAsVectorAndHasExternal().getInt();
83   }
84 
setHasExternalDeclsStoredDeclsList85   void setHasExternalDecls() {
86     if (DeclsTy *Vec = getAsVector())
87       Data = DeclsAndHasExternalTy(Vec, true);
88     else {
89       DeclsTy *VT = new DeclsTy();
90       if (NamedDecl *OldD = getAsDecl())
91         VT->push_back(OldD);
92       Data = DeclsAndHasExternalTy(VT, true);
93     }
94   }
95 
setOnlyValueStoredDeclsList96   void setOnlyValue(NamedDecl *ND) {
97     assert(!getAsVector() && "Not inline");
98     Data = ND;
99     // Make sure that Data is a plain NamedDecl* so we can use its address
100     // at getLookupResult.
101     assert(*(NamedDecl **)&Data == ND &&
102            "PointerUnion mangles the NamedDecl pointer!");
103   }
104 
removeStoredDeclsList105   void remove(NamedDecl *D) {
106     assert(!isNull() && "removing from empty list");
107     if (NamedDecl *Singleton = getAsDecl()) {
108       assert(Singleton == D && "list is different singleton");
109       (void)Singleton;
110       Data = (NamedDecl *)nullptr;
111       return;
112     }
113 
114     DeclsTy &Vec = *getAsVector();
115     DeclsTy::iterator I = std::find(Vec.begin(), Vec.end(), D);
116     assert(I != Vec.end() && "list does not contain decl");
117     Vec.erase(I);
118 
119     assert(std::find(Vec.begin(), Vec.end(), D)
120              == Vec.end() && "list still contains decl");
121   }
122 
123   /// \brief 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                                std::mem_fun(&Decl::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.
189   ///
AddSubsequentDeclStoredDeclsList190   void AddSubsequentDecl(NamedDecl *D) {
191     assert(!isNull() && "don't AddSubsequentDecl when we have no decls");
192 
193     // If this is the second decl added to the list, convert this to vector
194     // form.
195     if (NamedDecl *OldD = getAsDecl()) {
196       DeclsTy *VT = new DeclsTy();
197       VT->push_back(OldD);
198       Data = DeclsAndHasExternalTy(VT, false);
199     }
200 
201     DeclsTy &Vec = *getAsVector();
202 
203     // Using directives end up in a special entry which contains only
204     // other using directives, so all this logic is wasted for them.
205     // But avoiding the logic wastes time in the far-more-common case
206     // that we're *not* adding a new using directive.
207 
208     // Tag declarations always go at the end of the list so that an
209     // iterator which points at the first tag will start a span of
210     // decls that only contains tags.
211     if (D->hasTagIdentifierNamespace())
212       Vec.push_back(D);
213 
214     // Resolved using declarations go at the front of the list so that
215     // they won't show up in other lookup results.  Unresolved using
216     // declarations (which are always in IDNS_Using | IDNS_Ordinary)
217     // follow that so that the using declarations will be contiguous.
218     else if (D->getIdentifierNamespace() & Decl::IDNS_Using) {
219       DeclsTy::iterator I = Vec.begin();
220       if (D->getIdentifierNamespace() != Decl::IDNS_Using) {
221         while (I != Vec.end() &&
222                (*I)->getIdentifierNamespace() == Decl::IDNS_Using)
223           ++I;
224       }
225       Vec.insert(I, D);
226 
227     // All other declarations go at the end of the list, but before any
228     // tag declarations.  But we can be clever about tag declarations
229     // because there can only ever be one in a scope.
230     } else if (!Vec.empty() && Vec.back()->hasTagIdentifierNamespace()) {
231       NamedDecl *TagD = Vec.back();
232       Vec.back() = D;
233       Vec.push_back(TagD);
234     } else
235       Vec.push_back(D);
236   }
237 };
238 
239 class StoredDeclsMap
240   : public llvm::SmallDenseMap<DeclarationName, StoredDeclsList, 4> {
241 
242 public:
243   static void DestroyAll(StoredDeclsMap *Map, bool Dependent);
244 
245 private:
246   friend class ASTContext; // walks the chain deleting these
247   friend class DeclContext;
248   llvm::PointerIntPair<StoredDeclsMap*, 1> Previous;
249 };
250 
251 class DependentStoredDeclsMap : public StoredDeclsMap {
252 public:
DependentStoredDeclsMap()253   DependentStoredDeclsMap() : FirstDiagnostic(nullptr) {}
254 
255 private:
256   friend class DependentDiagnostic;
257   friend class DeclContext; // iterates over diagnostics
258 
259   DependentDiagnostic *FirstDiagnostic;
260 };
261 
262 } // end namespace clang
263 
264 #endif
265