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