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