DeclBase.cpp revision 7f0be13b435ad110f99af83a24a50f43225f3083 
1//===--- DeclBase.cpp - Declaration AST Node Implementation ---------------===//
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 implements the Decl and DeclContext classes.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/AST/DeclBase.h"
15#include "clang/AST/Decl.h"
16#include "clang/AST/DeclCXX.h"
17#include "clang/AST/DeclObjC.h"
18#include "clang/AST/DeclTemplate.h"
19#include "clang/AST/ASTContext.h"
20#include "clang/AST/Type.h"
21#include "llvm/ADT/DenseMap.h"
22#include <algorithm>
23#include <functional>
24#include <vector>
25using namespace clang;
26
27//===----------------------------------------------------------------------===//
28//  Statistics
29//===----------------------------------------------------------------------===//
30
31#define DECL(Derived, Base) static int n##Derived##s = 0;
32#include "clang/AST/DeclNodes.def"
33
34static bool StatSwitch = false;
35
36// This keeps track of all decl attributes. Since so few decls have attrs, we
37// keep them in a hash map instead of wasting space in the Decl class.
38typedef llvm::DenseMap<const Decl*, Attr*> DeclAttrMapTy;
39
40static DeclAttrMapTy *DeclAttrs = 0;
41
42const char *Decl::getDeclKindName() const {
43  switch (DeclKind) {
44  default: assert(0 && "Declaration not in DeclNodes.def!");
45#define DECL(Derived, Base) case Derived: return #Derived;
46#include "clang/AST/DeclNodes.def"
47  }
48}
49
50const char *DeclContext::getDeclKindName() const {
51  switch (DeclKind) {
52  default: assert(0 && "Declaration context not in DeclNodes.def!");
53#define DECL(Derived, Base) case Decl::Derived: return #Derived;
54#include "clang/AST/DeclNodes.def"
55  }
56}
57
58bool Decl::CollectingStats(bool Enable) {
59  if (Enable)
60    StatSwitch = true;
61  return StatSwitch;
62}
63
64void Decl::PrintStats() {
65  fprintf(stderr, "*** Decl Stats:\n");
66
67  int totalDecls = 0;
68#define DECL(Derived, Base) totalDecls += n##Derived##s;
69#include "clang/AST/DeclNodes.def"
70  fprintf(stderr, "  %d decls total.\n", totalDecls);
71
72  int totalBytes = 0;
73#define DECL(Derived, Base)                                             \
74  if (n##Derived##s > 0) {                                              \
75    totalBytes += (int)(n##Derived##s * sizeof(Derived##Decl));         \
76    fprintf(stderr, "    %d " #Derived " decls, %d each (%d bytes)\n",  \
77            n##Derived##s, (int)sizeof(Derived##Decl),                  \
78            (int)(n##Derived##s * sizeof(Derived##Decl)));              \
79  }
80#include "clang/AST/DeclNodes.def"
81
82  fprintf(stderr, "Total bytes = %d\n", totalBytes);
83}
84
85void Decl::addDeclKind(Kind k) {
86  switch (k) {
87  default: assert(0 && "Declaration not in DeclNodes.def!");
88#define DECL(Derived, Base) case Derived: ++n##Derived##s; break;
89#include "clang/AST/DeclNodes.def"
90  }
91}
92
93//===----------------------------------------------------------------------===//
94// Decl Implementation
95//===----------------------------------------------------------------------===//
96
97void Decl::setDeclContext(DeclContext *DC) {
98  if (isOutOfSemaDC())
99    delete getMultipleDC();
100
101  DeclCtx = reinterpret_cast<uintptr_t>(DC);
102}
103
104void Decl::setLexicalDeclContext(DeclContext *DC) {
105  if (DC == getLexicalDeclContext())
106    return;
107
108  if (isInSemaDC()) {
109    MultipleDC *MDC = new MultipleDC();
110    MDC->SemanticDC = getDeclContext();
111    MDC->LexicalDC = DC;
112    DeclCtx = reinterpret_cast<uintptr_t>(MDC) | 0x1;
113  } else {
114    getMultipleDC()->LexicalDC = DC;
115  }
116}
117
118// Out-of-line virtual method providing a home for Decl.
119Decl::~Decl() {
120  if (isOutOfSemaDC())
121    delete getMultipleDC();
122
123  if (!HasAttrs)
124    return;
125
126  DeclAttrMapTy::iterator it = DeclAttrs->find(this);
127  assert(it != DeclAttrs->end() && "No attrs found but HasAttrs is true!");
128
129  // release attributes.
130  delete it->second;
131  invalidateAttrs();
132}
133
134void Decl::addAttr(Attr *NewAttr) {
135  if (!DeclAttrs)
136    DeclAttrs = new DeclAttrMapTy();
137
138  Attr *&ExistingAttr = (*DeclAttrs)[this];
139
140  NewAttr->setNext(ExistingAttr);
141  ExistingAttr = NewAttr;
142
143  HasAttrs = true;
144}
145
146void Decl::invalidateAttrs() {
147  if (!HasAttrs) return;
148
149  HasAttrs = false;
150  (*DeclAttrs)[this] = 0;
151  DeclAttrs->erase(this);
152
153  if (DeclAttrs->empty()) {
154    delete DeclAttrs;
155    DeclAttrs = 0;
156  }
157}
158
159const Attr *Decl::getAttrs() const {
160  if (!HasAttrs)
161    return 0;
162
163  return (*DeclAttrs)[this];
164}
165
166void Decl::swapAttrs(Decl *RHS) {
167  bool HasLHSAttr = this->HasAttrs;
168  bool HasRHSAttr = RHS->HasAttrs;
169
170  // Usually, neither decl has attrs, nothing to do.
171  if (!HasLHSAttr && !HasRHSAttr) return;
172
173  // If 'this' has no attrs, swap the other way.
174  if (!HasLHSAttr)
175    return RHS->swapAttrs(this);
176
177  // Handle the case when both decls have attrs.
178  if (HasRHSAttr) {
179    std::swap((*DeclAttrs)[this], (*DeclAttrs)[RHS]);
180    return;
181  }
182
183  // Otherwise, LHS has an attr and RHS doesn't.
184  (*DeclAttrs)[RHS] = (*DeclAttrs)[this];
185  (*DeclAttrs).erase(this);
186  this->HasAttrs = false;
187  RHS->HasAttrs = true;
188}
189
190
191void Decl::Destroy(ASTContext& C) {
192#if 0
193  // FIXME: Once ownership is fully understood, we can enable this code
194  if (DeclContext *DC = dyn_cast<DeclContext>(this))
195    DC->decls_begin()->Destroy(C);
196
197  // Observe the unrolled recursion.  By setting N->NextDeclInScope = 0x0
198  // within the loop, only the Destroy method for the first Decl
199  // will deallocate all of the Decls in a chain.
200
201  Decl* N = NextDeclInScope;
202
203  while (N) {
204    Decl* Tmp = N->NextDeclInScope;
205    N->NextDeclInScope = 0;
206    N->Destroy(C);
207    N = Tmp;
208  }
209
210  this->~Decl();
211  C.Deallocate((void *)this);
212#endif
213}
214
215Decl *Decl::castFromDeclContext (const DeclContext *D) {
216  Decl::Kind DK = D->getDeclKind();
217  switch(DK) {
218#define DECL_CONTEXT(Name) \
219    case Decl::Name:     \
220      return static_cast<Name##Decl*>(const_cast<DeclContext*>(D));
221#define DECL_CONTEXT_BASE(Name)
222#include "clang/AST/DeclNodes.def"
223    default:
224#define DECL_CONTEXT_BASE(Name)                                   \
225      if (DK >= Decl::Name##First && DK <= Decl::Name##Last)    \
226        return static_cast<Name##Decl*>(const_cast<DeclContext*>(D));
227#include "clang/AST/DeclNodes.def"
228      assert(false && "a decl that inherits DeclContext isn't handled");
229      return 0;
230  }
231}
232
233DeclContext *Decl::castToDeclContext(const Decl *D) {
234  Decl::Kind DK = D->getKind();
235  switch(DK) {
236#define DECL_CONTEXT(Name) \
237    case Decl::Name:     \
238      return static_cast<Name##Decl*>(const_cast<Decl*>(D));
239#define DECL_CONTEXT_BASE(Name)
240#include "clang/AST/DeclNodes.def"
241    default:
242#define DECL_CONTEXT_BASE(Name)                                   \
243      if (DK >= Decl::Name##First && DK <= Decl::Name##Last)    \
244        return static_cast<Name##Decl*>(const_cast<Decl*>(D));
245#include "clang/AST/DeclNodes.def"
246      assert(false && "a decl that inherits DeclContext isn't handled");
247      return 0;
248  }
249}
250
251//===----------------------------------------------------------------------===//
252// DeclContext Implementation
253//===----------------------------------------------------------------------===//
254
255bool DeclContext::classof(const Decl *D) {
256  switch (D->getKind()) {
257#define DECL_CONTEXT(Name) case Decl::Name:
258#define DECL_CONTEXT_BASE(Name)
259#include "clang/AST/DeclNodes.def"
260      return true;
261    default:
262#define DECL_CONTEXT_BASE(Name)                   \
263      if (D->getKind() >= Decl::Name##First &&  \
264          D->getKind() <= Decl::Name##Last)     \
265        return true;
266#include "clang/AST/DeclNodes.def"
267      return false;
268  }
269}
270
271// FIXME: We really want to use a DenseSet here to eliminate the
272// redundant storage of the declaration names, but (1) it doesn't give
273// us the ability to search based on DeclarationName, (2) we really
274// need something more like a DenseMultiSet, and (3) it's
275// implemented in terms of DenseMap anyway. However, this data
276// structure is really space-inefficient, so we'll have to do
277// something.
278typedef llvm::DenseMap<DeclarationName, std::vector<NamedDecl*> >
279  StoredDeclsMap;
280
281DeclContext::~DeclContext() {
282  unsigned Size = LookupPtr.getInt();
283  if (Size == LookupIsMap)
284    delete static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
285  else
286    delete [] static_cast<NamedDecl**>(LookupPtr.getPointer());
287}
288
289void DeclContext::DestroyDecls(ASTContext &C) {
290  for (decl_iterator D = decls_begin(); D != decls_end(); )
291    (*D++)->Destroy(C);
292}
293
294bool DeclContext::isTransparentContext() const {
295  if (DeclKind == Decl::Enum)
296    return true; // FIXME: Check for C++0x scoped enums
297  else if (DeclKind == Decl::LinkageSpec)
298    return true;
299  else if (DeclKind == Decl::Record || DeclKind == Decl::CXXRecord)
300    return cast<RecordDecl>(this)->isAnonymousStructOrUnion();
301  else if (DeclKind == Decl::Namespace)
302    return false; // FIXME: Check for C++0x inline namespaces
303
304  return false;
305}
306
307DeclContext *DeclContext::getPrimaryContext() {
308  switch (DeclKind) {
309  case Decl::TranslationUnit:
310  case Decl::LinkageSpec:
311  case Decl::Block:
312    // There is only one DeclContext for these entities.
313    return this;
314
315  case Decl::Namespace:
316    // The original namespace is our primary context.
317    return static_cast<NamespaceDecl*>(this)->getOriginalNamespace();
318
319  case Decl::ObjCMethod:
320    return this;
321
322  case Decl::ObjCInterface:
323  case Decl::ObjCProtocol:
324  case Decl::ObjCCategory:
325    // FIXME: Can Objective-C interfaces be forward-declared?
326    return this;
327
328  case Decl::ObjCImplementation:
329  case Decl::ObjCCategoryImpl:
330    return this;
331
332  default:
333    if (DeclKind >= Decl::TagFirst && DeclKind <= Decl::TagLast) {
334      // If this is a tag type that has a definition or is currently
335      // being defined, that definition is our primary context.
336      if (TagType *TagT
337            = cast_or_null<TagType>(cast<TagDecl>(this)->TypeForDecl))
338        if (TagT->isBeingDefined() ||
339            (TagT->getDecl() && TagT->getDecl()->isDefinition()))
340          return TagT->getDecl();
341      return this;
342    }
343
344    assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast &&
345          "Unknown DeclContext kind");
346    return this;
347  }
348}
349
350DeclContext *DeclContext::getNextContext() {
351  switch (DeclKind) {
352  case Decl::Namespace:
353    // Return the next namespace
354    return static_cast<NamespaceDecl*>(this)->getNextNamespace();
355
356  default:
357    return 0;
358  }
359}
360
361void DeclContext::addDecl(Decl *D) {
362  assert(D->getLexicalDeclContext() == this &&
363         "Decl inserted into wrong lexical context");
364  assert(!D->NextDeclInScope && D != LastDecl &&
365         "Decl already inserted into a DeclContext");
366
367  if (FirstDecl) {
368    LastDecl->NextDeclInScope = D;
369    LastDecl = D;
370  } else {
371    FirstDecl = LastDecl = D;
372  }
373
374  if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
375    ND->getDeclContext()->makeDeclVisibleInContext(ND);
376}
377
378/// buildLookup - Build the lookup data structure with all of the
379/// declarations in DCtx (and any other contexts linked to it or
380/// transparent contexts nested within it).
381void DeclContext::buildLookup(DeclContext *DCtx) {
382  for (; DCtx; DCtx = DCtx->getNextContext()) {
383    for (decl_iterator D = DCtx->decls_begin(), DEnd = DCtx->decls_end();
384         D != DEnd; ++D) {
385      // Insert this declaration into the lookup structure
386      if (NamedDecl *ND = dyn_cast<NamedDecl>(*D))
387        makeDeclVisibleInContextImpl(ND);
388
389      // If this declaration is itself a transparent declaration context,
390      // add its members (recursively).
391      if (DeclContext *InnerCtx = dyn_cast<DeclContext>(*D))
392        if (InnerCtx->isTransparentContext())
393          buildLookup(InnerCtx->getPrimaryContext());
394    }
395  }
396}
397
398DeclContext::lookup_result
399DeclContext::lookup(DeclarationName Name) {
400  DeclContext *PrimaryContext = getPrimaryContext();
401  if (PrimaryContext != this)
402    return PrimaryContext->lookup(Name);
403
404  /// If there is no lookup data structure, build one now by walking
405  /// all of the linked DeclContexts (in declaration order!) and
406  /// inserting their values.
407  if (LookupPtr.getPointer() == 0)
408    buildLookup(this);
409
410  if (isLookupMap()) {
411    StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
412    StoredDeclsMap::iterator Pos = Map->find(Name);
413    if (Pos == Map->end())
414      return lookup_result(0, 0);
415
416    return lookup_result(&Pos->second.front(),
417                         &Pos->second.front() + Pos->second.size());
418  }
419
420  // We have a small array. Look into it.
421  unsigned Size = LookupPtr.getInt();
422  NamedDecl **Array = static_cast<NamedDecl**>(LookupPtr.getPointer());
423  for (unsigned Idx = 0; Idx != Size; ++Idx)
424    if (Array[Idx]->getDeclName() == Name) {
425      unsigned Last = Idx + 1;
426      while (Last != Size && Array[Last]->getDeclName() == Name)
427        ++Last;
428      return lookup_result(&Array[Idx], &Array[Last]);
429    }
430
431  return lookup_result(0, 0);
432}
433
434DeclContext::lookup_const_result
435DeclContext::lookup(DeclarationName Name) const {
436  return const_cast<DeclContext*>(this)->lookup(Name);
437}
438
439const DeclContext *DeclContext::getLookupContext() const {
440  const DeclContext *Ctx = this;
441  // Skip through transparent contexts.
442  while (Ctx->isTransparentContext())
443    Ctx = Ctx->getParent();
444  return Ctx;
445}
446
447void DeclContext::makeDeclVisibleInContext(NamedDecl *D) {
448  // FIXME: This feels like a hack. Should DeclarationName support
449  // template-ids, or is there a better way to keep specializations
450  // from being visible?
451  if (isa<ClassTemplateSpecializationDecl>(D))
452    return;
453
454  DeclContext *PrimaryContext = getPrimaryContext();
455  if (PrimaryContext != this) {
456    PrimaryContext->makeDeclVisibleInContext(D);
457    return;
458  }
459
460  // If we already have a lookup data structure, perform the insertion
461  // into it. Otherwise, be lazy and don't build that structure until
462  // someone asks for it.
463  if (LookupPtr.getPointer())
464    makeDeclVisibleInContextImpl(D);
465
466  // If we are a transparent context, insert into our parent context,
467  // too. This operation is recursive.
468  if (isTransparentContext())
469    getParent()->makeDeclVisibleInContext(D);
470}
471
472void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D) {
473  // Skip unnamed declarations.
474  if (!D->getDeclName())
475    return;
476
477  // FIXME: This feels like a hack. Should DeclarationName support
478  // template-ids, or is there a better way to keep specializations
479  // from being visible?
480  if (isa<ClassTemplateSpecializationDecl>(D))
481    return;
482
483  bool MayBeRedeclaration = true;
484
485  if (!isLookupMap()) {
486    unsigned Size = LookupPtr.getInt();
487
488    // The lookup data is stored as an array. Search through the array
489    // to find the insertion location.
490    NamedDecl **Array;
491    if (Size == 0) {
492      Array = new NamedDecl*[LookupIsMap - 1];
493      LookupPtr.setPointer(Array);
494    } else {
495      Array = static_cast<NamedDecl **>(LookupPtr.getPointer());
496    }
497
498    // We always keep declarations of the same name next to each other
499    // in the array, so that it is easy to return multiple results
500    // from lookup().
501    unsigned FirstMatch;
502    for (FirstMatch = 0; FirstMatch != Size; ++FirstMatch)
503      if (Array[FirstMatch]->getDeclName() == D->getDeclName())
504        break;
505
506    unsigned InsertPos = FirstMatch;
507    if (FirstMatch != Size) {
508      // We found another declaration with the same name. First
509      // determine whether this is a redeclaration of an existing
510      // declaration in this scope, in which case we will replace the
511      // existing declaration.
512      unsigned LastMatch = FirstMatch;
513      for (; LastMatch != Size; ++LastMatch) {
514        if (Array[LastMatch]->getDeclName() != D->getDeclName())
515          break;
516
517        if (D->declarationReplaces(Array[LastMatch])) {
518          // D is a redeclaration of an existing element in the
519          // array. Replace that element with D.
520          Array[LastMatch] = D;
521          return;
522        }
523      }
524
525      // [FirstMatch, LastMatch) contains the set of declarations that
526      // have the same name as this declaration. Determine where the
527      // declaration D will be inserted into this range.
528      if (D->getKind() == Decl::UsingDirective ||
529          D->getIdentifierNamespace() == Decl::IDNS_Tag)
530        InsertPos = LastMatch;
531      else if (Array[LastMatch-1]->getIdentifierNamespace() == Decl::IDNS_Tag)
532        InsertPos = LastMatch - 1;
533      else
534        InsertPos = LastMatch;
535    }
536
537    if (Size < LookupIsMap - 1) {
538      // The new declaration will fit in the array. Insert the new
539      // declaration at the position Match in the array.
540      for (unsigned Idx = Size; Idx > InsertPos; --Idx)
541       Array[Idx] = Array[Idx-1];
542
543      Array[InsertPos] = D;
544      LookupPtr.setInt(Size + 1);
545      return;
546    }
547
548    // We've reached capacity in this array. Create a map and copy in
549    // all of the declarations that were stored in the array.
550    StoredDeclsMap *Map = new StoredDeclsMap(16);
551    LookupPtr.setPointer(Map);
552    LookupPtr.setInt(LookupIsMap);
553    for (unsigned Idx = 0; Idx != LookupIsMap - 1; ++Idx)
554      makeDeclVisibleInContextImpl(Array[Idx]);
555    delete [] Array;
556
557    // Fall through to perform insertion into the map.
558    MayBeRedeclaration = false;
559  }
560
561  // Insert this declaration into the map.
562  StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
563  std::vector<NamedDecl *> &DeclNameEntries = (*Map)[D->getDeclName()];
564  if (DeclNameEntries.empty()) {
565    DeclNameEntries.push_back(D);
566    return;
567  }
568
569  if (MayBeRedeclaration) {
570    // Determine if this declaration is actually a redeclaration.
571    std::vector<NamedDecl *>::iterator Redecl
572      = std::find_if(DeclNameEntries.begin(), DeclNameEntries.end(),
573                   std::bind1st(std::mem_fun(&NamedDecl::declarationReplaces),
574                                D));
575    if (Redecl != DeclNameEntries.end()) {
576      *Redecl = D;
577      return;
578    }
579  }
580
581  // Put this declaration into the appropriate slot.
582  if (isa<UsingDirectiveDecl>(D) ||
583      D->getIdentifierNamespace() == Decl::IDNS_Tag)
584    DeclNameEntries.push_back(D);
585  else if (DeclNameEntries.back()->getIdentifierNamespace() == Decl::IDNS_Tag) {
586    NamedDecl *TagD = DeclNameEntries.back();
587    DeclNameEntries.back() = D;
588    DeclNameEntries.push_back(TagD);
589  } else
590    DeclNameEntries.push_back(D);
591}
592
593/// Returns iterator range [First, Last) of UsingDirectiveDecls stored within
594/// this context.
595DeclContext::udir_iterator_range DeclContext::getUsingDirectives() const {
596  lookup_const_result Result = lookup(UsingDirectiveDecl::getName());
597  return udir_iterator_range(reinterpret_cast<udir_iterator>(Result.first),
598                             reinterpret_cast<udir_iterator>(Result.second));
599}
600
601