DeclContextInternals.h revision 208600 
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/DeclarationName.h"
19#include "clang/AST/DeclCXX.h"
20#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/PointerUnion.h"
22#include "llvm/ADT/SmallVector.h"
23#include <algorithm>
24
25namespace clang {
26
27class DependentDiagnostic;
28
29/// StoredDeclsList - This is an array of decls optimized a common case of only
30/// containing one entry.
31struct StoredDeclsList {
32  /// The kind of data encoded in this list.
33  enum DataKind {
34    /// \brief The data is a NamedDecl*.
35    DK_Decl = 0,
36    /// \brief The data is a declaration ID (an unsigned value),
37    /// shifted left by 2 bits.
38    DK_DeclID = 1,
39    /// \brief The data is a pointer to a vector (of type VectorTy)
40    /// that contains declarations.
41    DK_Decl_Vector = 2,
42    /// \brief The data is a pointer to a vector (of type VectorTy)
43    /// that contains declaration ID.
44    DK_ID_Vector = 3
45  };
46
47  /// VectorTy - When in vector form, this is what the Data pointer points to.
48  typedef llvm::SmallVector<uintptr_t, 4> VectorTy;
49
50  /// \brief The stored data, which will be either a declaration ID, a
51  /// pointer to a NamedDecl, or a pointer to a vector.
52  uintptr_t Data;
53
54public:
55  StoredDeclsList() : Data(0) {}
56
57  StoredDeclsList(const StoredDeclsList &RHS) : Data(RHS.Data) {
58    if (VectorTy *RHSVec = RHS.getAsVector()) {
59      VectorTy *New = new VectorTy(*RHSVec);
60      Data = reinterpret_cast<uintptr_t>(New) | (Data & 0x03);
61    }
62  }
63
64  ~StoredDeclsList() {
65    // If this is a vector-form, free the vector.
66    if (VectorTy *Vector = getAsVector())
67      delete Vector;
68  }
69
70  StoredDeclsList &operator=(const StoredDeclsList &RHS) {
71    if (VectorTy *Vector = getAsVector())
72      delete Vector;
73    Data = RHS.Data;
74    if (VectorTy *RHSVec = RHS.getAsVector()) {
75      VectorTy *New = new VectorTy(*RHSVec);
76      Data = reinterpret_cast<uintptr_t>(New) | (Data & 0x03);
77    }
78    return *this;
79  }
80
81  bool isNull() const { return (Data & ~0x03) == 0; }
82
83  NamedDecl *getAsDecl() const {
84    if ((Data & 0x03) != DK_Decl)
85      return 0;
86
87    return reinterpret_cast<NamedDecl *>(Data & ~0x03);
88  }
89
90  VectorTy *getAsVector() const {
91    if ((Data & 0x03) != DK_ID_Vector && (Data & 0x03) != DK_Decl_Vector)
92      return 0;
93
94    return reinterpret_cast<VectorTy *>(Data & ~0x03);
95  }
96
97  void setOnlyValue(NamedDecl *ND) {
98    assert(!getAsVector() && "Not inline");
99    Data = reinterpret_cast<uintptr_t>(ND);
100  }
101
102  void setFromDeclIDs(const llvm::SmallVectorImpl<unsigned> &Vec) {
103    if (Vec.size() > 1) {
104      VectorTy *Vector = getAsVector();
105      if (!Vector) {
106        Vector = new VectorTy;
107        Data = reinterpret_cast<uintptr_t>(Vector) | DK_ID_Vector;
108      }
109
110      Vector->resize(Vec.size());
111      std::copy(Vec.begin(), Vec.end(), Vector->begin());
112      return;
113    }
114
115    if (VectorTy *Vector = getAsVector())
116      delete Vector;
117
118    if (Vec.empty())
119      Data = 0;
120    else
121      Data = (Vec[0] << 2) | DK_DeclID;
122  }
123
124  /// \brief Force the stored declarations list to contain actual
125  /// declarations.
126  ///
127  /// This routine will resolve any declaration IDs for declarations
128  /// that may not yet have been loaded from external storage.
129  void materializeDecls(ASTContext &Context);
130
131  bool hasDeclarationIDs() const {
132    DataKind DK = (DataKind)(Data & 0x03);
133    return DK == DK_DeclID || DK == DK_ID_Vector;
134  }
135
136  void remove(NamedDecl *D) {
137    assert(!isNull() && "removing from empty list");
138    if (NamedDecl *Singleton = getAsDecl()) {
139      assert(Singleton == D && "list is different singleton");
140      (void)Singleton;
141      Data = 0;
142      return;
143    }
144
145    VectorTy &Vec = *getAsVector();
146    VectorTy::iterator I = std::find(Vec.begin(), Vec.end(),
147                                     reinterpret_cast<uintptr_t>(D));
148    assert(I != Vec.end() && "list does not contain decl");
149    Vec.erase(I);
150
151    assert(std::find(Vec.begin(), Vec.end(), reinterpret_cast<uintptr_t>(D))
152             == Vec.end() && "list still contains decl");
153  }
154
155  /// getLookupResult - Return an array of all the decls that this list
156  /// represents.
157  DeclContext::lookup_result getLookupResult(ASTContext &Context) {
158    if (isNull())
159      return DeclContext::lookup_result(DeclContext::lookup_iterator(0),
160                                        DeclContext::lookup_iterator(0));
161
162    if (hasDeclarationIDs())
163      materializeDecls(Context);
164
165    // If we have a single NamedDecl, return it.
166    if (getAsDecl()) {
167      assert(!isNull() && "Empty list isn't allowed");
168
169      // Data is a raw pointer to a NamedDecl*, return it.
170      void *Ptr = &Data;
171      return DeclContext::lookup_result((NamedDecl**)Ptr, (NamedDecl**)Ptr+1);
172    }
173
174    assert(getAsVector() && "Must have a vector at this point");
175    VectorTy &Vector = *getAsVector();
176
177    // Otherwise, we have a range result.
178    return DeclContext::lookup_result((NamedDecl **)&Vector[0],
179                                      (NamedDecl **)&Vector[0]+Vector.size());
180  }
181
182  /// HandleRedeclaration - If this is a redeclaration of an existing decl,
183  /// replace the old one with D and return true.  Otherwise return false.
184  bool HandleRedeclaration(ASTContext &Context, NamedDecl *D) {
185    if (hasDeclarationIDs())
186      materializeDecls(Context);
187
188    // Most decls only have one entry in their list, special case it.
189    if (NamedDecl *OldD = getAsDecl()) {
190      if (!D->declarationReplaces(OldD))
191        return false;
192      setOnlyValue(D);
193      return true;
194    }
195
196    // Determine if this declaration is actually a redeclaration.
197    VectorTy &Vec = *getAsVector();
198    for (VectorTy::iterator OD = Vec.begin(), ODEnd = Vec.end();
199         OD != ODEnd; ++OD) {
200      NamedDecl *OldD = reinterpret_cast<NamedDecl *>(*OD);
201      if (D->declarationReplaces(OldD)) {
202        *OD = reinterpret_cast<uintptr_t>(D);
203        return true;
204      }
205    }
206
207    return false;
208  }
209
210  /// AddSubsequentDecl - This is called on the second and later decl when it is
211  /// not a redeclaration to merge it into the appropriate place in our list.
212  ///
213  void AddSubsequentDecl(NamedDecl *D) {
214    assert(!hasDeclarationIDs() && "Must materialize before adding decls");
215
216    // If this is the second decl added to the list, convert this to vector
217    // form.
218    if (NamedDecl *OldD = getAsDecl()) {
219      VectorTy *VT = new VectorTy();
220      VT->push_back(reinterpret_cast<uintptr_t>(OldD));
221      Data = reinterpret_cast<uintptr_t>(VT) | DK_Decl_Vector;
222    }
223
224    VectorTy &Vec = *getAsVector();
225
226    // Using directives end up in a special entry which contains only
227    // other using directives, so all this logic is wasted for them.
228    // But avoiding the logic wastes time in the far-more-common case
229    // that we're *not* adding a new using directive.
230
231    // Tag declarations always go at the end of the list so that an
232    // iterator which points at the first tag will start a span of
233    // decls that only contains tags.
234    if (D->hasTagIdentifierNamespace())
235      Vec.push_back(reinterpret_cast<uintptr_t>(D));
236
237    // Resolved using declarations go at the front of the list so that
238    // they won't show up in other lookup results.  Unresolved using
239    // declarations (which are always in IDNS_Using | IDNS_Ordinary)
240    // follow that so that the using declarations will be contiguous.
241    else if (D->getIdentifierNamespace() & Decl::IDNS_Using) {
242      VectorTy::iterator I = Vec.begin();
243      if (D->getIdentifierNamespace() != Decl::IDNS_Using) {
244        while (I != Vec.end() &&
245               reinterpret_cast<NamedDecl *>(*I)
246                 ->getIdentifierNamespace() == Decl::IDNS_Using)
247          ++I;
248      }
249      Vec.insert(I, reinterpret_cast<uintptr_t>(D));
250
251    // All other declarations go at the end of the list, but before any
252    // tag declarations.  But we can be clever about tag declarations
253    // because there can only ever be one in a scope.
254    } else if (reinterpret_cast<NamedDecl *>(Vec.back())
255                 ->hasTagIdentifierNamespace()) {
256      uintptr_t TagD = Vec.back();
257      Vec.back() = reinterpret_cast<uintptr_t>(D);
258      Vec.push_back(TagD);
259    } else
260      Vec.push_back(reinterpret_cast<uintptr_t>(D));
261  }
262};
263
264class StoredDeclsMap
265  : public llvm::DenseMap<DeclarationName, StoredDeclsList> {
266
267public:
268  static void DestroyAll(StoredDeclsMap *Map, bool Dependent);
269
270private:
271  friend class ASTContext; // walks the chain deleting these
272  friend class DeclContext;
273  llvm::PointerIntPair<StoredDeclsMap*, 1> Previous;
274};
275
276class DependentStoredDeclsMap : public StoredDeclsMap {
277public:
278  DependentStoredDeclsMap() : FirstDiagnostic(0) {}
279
280private:
281  friend class DependentDiagnostic;
282  friend class DeclContext; // iterates over diagnostics
283
284  DependentDiagnostic *FirstDiagnostic;
285};
286
287} // end namespace clang
288
289#endif
290