DeclBase.cpp revision 3a1c36c099df4dcc94d1d24516a8a2c809c764d4 
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/DeclFriend.h"
19#include "clang/AST/DeclObjC.h"
20#include "clang/AST/DeclTemplate.h"
21#include "clang/AST/DependentDiagnostic.h"
22#include "clang/AST/ExternalASTSource.h"
23#include "clang/AST/ASTContext.h"
24#include "clang/AST/Type.h"
25#include "clang/AST/Stmt.h"
26#include "clang/AST/StmtCXX.h"
27#include "clang/AST/ASTMutationListener.h"
28#include "llvm/ADT/DenseMap.h"
29#include "llvm/Support/raw_ostream.h"
30#include <algorithm>
31#include <cstdio>
32#include <vector>
33using namespace clang;
34
35//===----------------------------------------------------------------------===//
36//  Statistics
37//===----------------------------------------------------------------------===//
38
39#define DECL(DERIVED, BASE) static int n##DERIVED##s = 0;
40#define ABSTRACT_DECL(DECL)
41#include "clang/AST/DeclNodes.inc"
42
43static bool StatSwitch = false;
44
45const char *Decl::getDeclKindName() const {
46  switch (DeclKind) {
47  default: assert(0 && "Declaration not in DeclNodes.inc!");
48#define DECL(DERIVED, BASE) case DERIVED: return #DERIVED;
49#define ABSTRACT_DECL(DECL)
50#include "clang/AST/DeclNodes.inc"
51  }
52}
53
54void Decl::setInvalidDecl(bool Invalid) {
55  InvalidDecl = Invalid;
56  if (Invalid) {
57    // Defensive maneuver for ill-formed code: we're likely not to make it to
58    // a point where we set the access specifier, so default it to "public"
59    // to avoid triggering asserts elsewhere in the front end.
60    setAccess(AS_public);
61  }
62}
63
64const char *DeclContext::getDeclKindName() const {
65  switch (DeclKind) {
66  default: assert(0 && "Declaration context not in DeclNodes.inc!");
67#define DECL(DERIVED, BASE) case Decl::DERIVED: return #DERIVED;
68#define ABSTRACT_DECL(DECL)
69#include "clang/AST/DeclNodes.inc"
70  }
71}
72
73bool Decl::CollectingStats(bool Enable) {
74  if (Enable) StatSwitch = true;
75  return StatSwitch;
76}
77
78void Decl::PrintStats() {
79  fprintf(stderr, "*** Decl Stats:\n");
80
81  int totalDecls = 0;
82#define DECL(DERIVED, BASE) totalDecls += n##DERIVED##s;
83#define ABSTRACT_DECL(DECL)
84#include "clang/AST/DeclNodes.inc"
85  fprintf(stderr, "  %d decls total.\n", totalDecls);
86
87  int totalBytes = 0;
88#define DECL(DERIVED, BASE)                                             \
89  if (n##DERIVED##s > 0) {                                              \
90    totalBytes += (int)(n##DERIVED##s * sizeof(DERIVED##Decl));         \
91    fprintf(stderr, "    %d " #DERIVED " decls, %d each (%d bytes)\n",  \
92            n##DERIVED##s, (int)sizeof(DERIVED##Decl),                  \
93            (int)(n##DERIVED##s * sizeof(DERIVED##Decl)));              \
94  }
95#define ABSTRACT_DECL(DECL)
96#include "clang/AST/DeclNodes.inc"
97
98  fprintf(stderr, "Total bytes = %d\n", totalBytes);
99}
100
101void Decl::add(Kind k) {
102  switch (k) {
103  default: assert(0 && "Declaration not in DeclNodes.inc!");
104#define DECL(DERIVED, BASE) case DERIVED: ++n##DERIVED##s; break;
105#define ABSTRACT_DECL(DECL)
106#include "clang/AST/DeclNodes.inc"
107  }
108}
109
110bool Decl::isTemplateParameterPack() const {
111  if (const TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(this))
112    return TTP->isParameterPack();
113
114  return false;
115}
116
117bool Decl::isFunctionOrFunctionTemplate() const {
118  if (const UsingShadowDecl *UD = dyn_cast<UsingShadowDecl>(this))
119    return UD->getTargetDecl()->isFunctionOrFunctionTemplate();
120
121  return isa<FunctionDecl>(this) || isa<FunctionTemplateDecl>(this);
122}
123
124bool Decl::isDefinedOutsideFunctionOrMethod() const {
125  for (const DeclContext *DC = getDeclContext();
126       DC && !DC->isTranslationUnit();
127       DC = DC->getParent())
128    if (DC->isFunctionOrMethod())
129      return false;
130
131  return true;
132}
133
134
135//===----------------------------------------------------------------------===//
136// PrettyStackTraceDecl Implementation
137//===----------------------------------------------------------------------===//
138
139void PrettyStackTraceDecl::print(llvm::raw_ostream &OS) const {
140  SourceLocation TheLoc = Loc;
141  if (TheLoc.isInvalid() && TheDecl)
142    TheLoc = TheDecl->getLocation();
143
144  if (TheLoc.isValid()) {
145    TheLoc.print(OS, SM);
146    OS << ": ";
147  }
148
149  OS << Message;
150
151  if (const NamedDecl *DN = dyn_cast_or_null<NamedDecl>(TheDecl))
152    OS << " '" << DN->getQualifiedNameAsString() << '\'';
153  OS << '\n';
154}
155
156//===----------------------------------------------------------------------===//
157// Decl Implementation
158//===----------------------------------------------------------------------===//
159
160// Out-of-line virtual method providing a home for Decl.
161Decl::~Decl() { }
162
163void Decl::setDeclContext(DeclContext *DC) {
164  if (isOutOfSemaDC())
165    delete getMultipleDC();
166
167  DeclCtx = DC;
168}
169
170void Decl::setLexicalDeclContext(DeclContext *DC) {
171  if (DC == getLexicalDeclContext())
172    return;
173
174  if (isInSemaDC()) {
175    MultipleDC *MDC = new (getASTContext()) MultipleDC();
176    MDC->SemanticDC = getDeclContext();
177    MDC->LexicalDC = DC;
178    DeclCtx = MDC;
179  } else {
180    getMultipleDC()->LexicalDC = DC;
181  }
182}
183
184bool Decl::isInAnonymousNamespace() const {
185  const DeclContext *DC = getDeclContext();
186  do {
187    if (const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(DC))
188      if (ND->isAnonymousNamespace())
189        return true;
190  } while ((DC = DC->getParent()));
191
192  return false;
193}
194
195TranslationUnitDecl *Decl::getTranslationUnitDecl() {
196  if (TranslationUnitDecl *TUD = dyn_cast<TranslationUnitDecl>(this))
197    return TUD;
198
199  DeclContext *DC = getDeclContext();
200  assert(DC && "This decl is not contained in a translation unit!");
201
202  while (!DC->isTranslationUnit()) {
203    DC = DC->getParent();
204    assert(DC && "This decl is not contained in a translation unit!");
205  }
206
207  return cast<TranslationUnitDecl>(DC);
208}
209
210ASTContext &Decl::getASTContext() const {
211  return getTranslationUnitDecl()->getASTContext();
212}
213
214ASTMutationListener *Decl::getASTMutationListener() const {
215  return getASTContext().getASTMutationListener();
216}
217
218bool Decl::isUsed(bool CheckUsedAttr) const {
219  if (Used)
220    return true;
221
222  // Check for used attribute.
223  if (CheckUsedAttr && hasAttr<UsedAttr>())
224    return true;
225
226  // Check redeclarations for used attribute.
227  for (redecl_iterator I = redecls_begin(), E = redecls_end(); I != E; ++I) {
228    if ((CheckUsedAttr && I->hasAttr<UsedAttr>()) || I->Used)
229      return true;
230  }
231
232  return false;
233}
234
235
236unsigned Decl::getIdentifierNamespaceForKind(Kind DeclKind) {
237  switch (DeclKind) {
238    case Function:
239    case CXXMethod:
240    case CXXConstructor:
241    case CXXDestructor:
242    case CXXConversion:
243    case EnumConstant:
244    case Var:
245    case ImplicitParam:
246    case ParmVar:
247    case NonTypeTemplateParm:
248    case ObjCMethod:
249    case ObjCProperty:
250      return IDNS_Ordinary;
251
252    case IndirectField:
253      return IDNS_Ordinary | IDNS_Member;
254
255    case ObjCCompatibleAlias:
256    case ObjCInterface:
257      return IDNS_Ordinary | IDNS_Type;
258
259    case Typedef:
260    case UnresolvedUsingTypename:
261    case TemplateTypeParm:
262      return IDNS_Ordinary | IDNS_Type;
263
264    case UsingShadow:
265      return 0; // we'll actually overwrite this later
266
267    case UnresolvedUsingValue:
268      return IDNS_Ordinary | IDNS_Using;
269
270    case Using:
271      return IDNS_Using;
272
273    case ObjCProtocol:
274      return IDNS_ObjCProtocol;
275
276    case Field:
277    case ObjCAtDefsField:
278    case ObjCIvar:
279      return IDNS_Member;
280
281    case Record:
282    case CXXRecord:
283    case Enum:
284      return IDNS_Tag | IDNS_Type;
285
286    case Namespace:
287    case NamespaceAlias:
288      return IDNS_Namespace;
289
290    case FunctionTemplate:
291      return IDNS_Ordinary;
292
293    case ClassTemplate:
294    case TemplateTemplateParm:
295      return IDNS_Ordinary | IDNS_Tag | IDNS_Type;
296
297    // Never have names.
298    case Friend:
299    case FriendTemplate:
300    case AccessSpec:
301    case LinkageSpec:
302    case FileScopeAsm:
303    case StaticAssert:
304    case ObjCClass:
305    case ObjCPropertyImpl:
306    case ObjCForwardProtocol:
307    case Block:
308    case TranslationUnit:
309
310    case UsingDirective:
311    case ClassTemplateSpecialization:
312    case ClassTemplatePartialSpecialization:
313    case ObjCImplementation:
314    case ObjCCategory:
315    case ObjCCategoryImpl:
316      // Never looked up by name.
317      return 0;
318  }
319
320  return 0;
321}
322
323void Decl::setAttrs(const AttrVec &attrs) {
324  assert(!HasAttrs && "Decl already contains attrs.");
325
326  AttrVec &AttrBlank = getASTContext().getDeclAttrs(this);
327  assert(AttrBlank.empty() && "HasAttrs was wrong?");
328
329  AttrBlank = attrs;
330  HasAttrs = true;
331}
332
333void Decl::dropAttrs() {
334  if (!HasAttrs) return;
335
336  HasAttrs = false;
337  getASTContext().eraseDeclAttrs(this);
338}
339
340const AttrVec &Decl::getAttrs() const {
341  assert(HasAttrs && "No attrs to get!");
342  return getASTContext().getDeclAttrs(this);
343}
344
345void Decl::swapAttrs(Decl *RHS) {
346  bool HasLHSAttr = this->HasAttrs;
347  bool HasRHSAttr = RHS->HasAttrs;
348
349  // Usually, neither decl has attrs, nothing to do.
350  if (!HasLHSAttr && !HasRHSAttr) return;
351
352  // If 'this' has no attrs, swap the other way.
353  if (!HasLHSAttr)
354    return RHS->swapAttrs(this);
355
356  ASTContext &Context = getASTContext();
357
358  // Handle the case when both decls have attrs.
359  if (HasRHSAttr) {
360    std::swap(Context.getDeclAttrs(this), Context.getDeclAttrs(RHS));
361    return;
362  }
363
364  // Otherwise, LHS has an attr and RHS doesn't.
365  Context.getDeclAttrs(RHS) = Context.getDeclAttrs(this);
366  Context.eraseDeclAttrs(this);
367  this->HasAttrs = false;
368  RHS->HasAttrs = true;
369}
370
371Decl *Decl::castFromDeclContext (const DeclContext *D) {
372  Decl::Kind DK = D->getDeclKind();
373  switch(DK) {
374#define DECL(NAME, BASE)
375#define DECL_CONTEXT(NAME) \
376    case Decl::NAME:       \
377      return static_cast<NAME##Decl*>(const_cast<DeclContext*>(D));
378#define DECL_CONTEXT_BASE(NAME)
379#include "clang/AST/DeclNodes.inc"
380    default:
381#define DECL(NAME, BASE)
382#define DECL_CONTEXT_BASE(NAME)                  \
383      if (DK >= first##NAME && DK <= last##NAME) \
384        return static_cast<NAME##Decl*>(const_cast<DeclContext*>(D));
385#include "clang/AST/DeclNodes.inc"
386      assert(false && "a decl that inherits DeclContext isn't handled");
387      return 0;
388  }
389}
390
391DeclContext *Decl::castToDeclContext(const Decl *D) {
392  Decl::Kind DK = D->getKind();
393  switch(DK) {
394#define DECL(NAME, BASE)
395#define DECL_CONTEXT(NAME) \
396    case Decl::NAME:       \
397      return static_cast<NAME##Decl*>(const_cast<Decl*>(D));
398#define DECL_CONTEXT_BASE(NAME)
399#include "clang/AST/DeclNodes.inc"
400    default:
401#define DECL(NAME, BASE)
402#define DECL_CONTEXT_BASE(NAME)                                   \
403      if (DK >= first##NAME && DK <= last##NAME)                  \
404        return static_cast<NAME##Decl*>(const_cast<Decl*>(D));
405#include "clang/AST/DeclNodes.inc"
406      assert(false && "a decl that inherits DeclContext isn't handled");
407      return 0;
408  }
409}
410
411SourceLocation Decl::getBodyRBrace() const {
412  // Special handling of FunctionDecl to avoid de-serializing the body from PCH.
413  // FunctionDecl stores EndRangeLoc for this purpose.
414  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(this)) {
415    const FunctionDecl *Definition;
416    if (FD->hasBody(Definition))
417      return Definition->getSourceRange().getEnd();
418    return SourceLocation();
419  }
420
421  if (Stmt *Body = getBody())
422    return Body->getSourceRange().getEnd();
423
424  return SourceLocation();
425}
426
427void Decl::CheckAccessDeclContext() const {
428#ifndef NDEBUG
429  // Suppress this check if any of the following hold:
430  // 1. this is the translation unit (and thus has no parent)
431  // 2. this is a template parameter (and thus doesn't belong to its context)
432  // 3. this is a non-type template parameter
433  // 4. the context is not a record
434  // 5. it's invalid
435  // 6. it's a C++0x static_assert.
436  if (isa<TranslationUnitDecl>(this) ||
437      isa<TemplateTypeParmDecl>(this) ||
438      isa<NonTypeTemplateParmDecl>(this) ||
439      !isa<CXXRecordDecl>(getDeclContext()) ||
440      isInvalidDecl() ||
441      isa<StaticAssertDecl>(this) ||
442      // FIXME: a ParmVarDecl can have ClassTemplateSpecialization
443      // as DeclContext (?).
444      isa<ParmVarDecl>(this) ||
445      // FIXME: a ClassTemplateSpecialization or CXXRecordDecl can have
446      // AS_none as access specifier.
447      isa<CXXRecordDecl>(this))
448    return;
449
450  assert(Access != AS_none &&
451         "Access specifier is AS_none inside a record decl");
452#endif
453}
454
455
456//===----------------------------------------------------------------------===//
457// DeclContext Implementation
458//===----------------------------------------------------------------------===//
459
460bool DeclContext::classof(const Decl *D) {
461  switch (D->getKind()) {
462#define DECL(NAME, BASE)
463#define DECL_CONTEXT(NAME) case Decl::NAME:
464#define DECL_CONTEXT_BASE(NAME)
465#include "clang/AST/DeclNodes.inc"
466      return true;
467    default:
468#define DECL(NAME, BASE)
469#define DECL_CONTEXT_BASE(NAME)                 \
470      if (D->getKind() >= Decl::first##NAME &&  \
471          D->getKind() <= Decl::last##NAME)     \
472        return true;
473#include "clang/AST/DeclNodes.inc"
474      return false;
475  }
476}
477
478DeclContext::~DeclContext() { }
479
480/// \brief Find the parent context of this context that will be
481/// used for unqualified name lookup.
482///
483/// Generally, the parent lookup context is the semantic context. However, for
484/// a friend function the parent lookup context is the lexical context, which
485/// is the class in which the friend is declared.
486DeclContext *DeclContext::getLookupParent() {
487  // FIXME: Find a better way to identify friends
488  if (isa<FunctionDecl>(this))
489    if (getParent()->getRedeclContext()->isFileContext() &&
490        getLexicalParent()->getRedeclContext()->isRecord())
491      return getLexicalParent();
492
493  return getParent();
494}
495
496bool DeclContext::isInlineNamespace() const {
497  return isNamespace() &&
498         cast<NamespaceDecl>(this)->isInline();
499}
500
501bool DeclContext::isDependentContext() const {
502  if (isFileContext())
503    return false;
504
505  if (isa<ClassTemplatePartialSpecializationDecl>(this))
506    return true;
507
508  if (const CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(this))
509    if (Record->getDescribedClassTemplate())
510      return true;
511
512  if (const FunctionDecl *Function = dyn_cast<FunctionDecl>(this)) {
513    if (Function->getDescribedFunctionTemplate())
514      return true;
515
516    // Friend function declarations are dependent if their *lexical*
517    // context is dependent.
518    if (cast<Decl>(this)->getFriendObjectKind())
519      return getLexicalParent()->isDependentContext();
520  }
521
522  return getParent() && getParent()->isDependentContext();
523}
524
525bool DeclContext::isTransparentContext() const {
526  if (DeclKind == Decl::Enum)
527    return !cast<EnumDecl>(this)->isScoped();
528  else if (DeclKind == Decl::LinkageSpec)
529    return true;
530
531  return false;
532}
533
534bool DeclContext::isExternCContext() const {
535  const DeclContext *DC = this;
536  while (DC->DeclKind != Decl::TranslationUnit) {
537    if (DC->DeclKind == Decl::LinkageSpec)
538      return cast<LinkageSpecDecl>(DC)->getLanguage()
539        == LinkageSpecDecl::lang_c;
540    DC = DC->getParent();
541  }
542  return false;
543}
544
545bool DeclContext::Encloses(const DeclContext *DC) const {
546  if (getPrimaryContext() != this)
547    return getPrimaryContext()->Encloses(DC);
548
549  for (; DC; DC = DC->getParent())
550    if (DC->getPrimaryContext() == this)
551      return true;
552  return false;
553}
554
555DeclContext *DeclContext::getPrimaryContext() {
556  switch (DeclKind) {
557  case Decl::TranslationUnit:
558  case Decl::LinkageSpec:
559  case Decl::Block:
560    // There is only one DeclContext for these entities.
561    return this;
562
563  case Decl::Namespace:
564    // The original namespace is our primary context.
565    return static_cast<NamespaceDecl*>(this)->getOriginalNamespace();
566
567  case Decl::ObjCMethod:
568    return this;
569
570  case Decl::ObjCInterface:
571  case Decl::ObjCProtocol:
572  case Decl::ObjCCategory:
573    // FIXME: Can Objective-C interfaces be forward-declared?
574    return this;
575
576  case Decl::ObjCImplementation:
577  case Decl::ObjCCategoryImpl:
578    return this;
579
580  default:
581    if (DeclKind >= Decl::firstTag && DeclKind <= Decl::lastTag) {
582      // If this is a tag type that has a definition or is currently
583      // being defined, that definition is our primary context.
584      TagDecl *Tag = cast<TagDecl>(this);
585      assert(isa<TagType>(Tag->TypeForDecl) ||
586             isa<InjectedClassNameType>(Tag->TypeForDecl));
587
588      if (TagDecl *Def = Tag->getDefinition())
589        return Def;
590
591      if (!isa<InjectedClassNameType>(Tag->TypeForDecl)) {
592        const TagType *TagTy = cast<TagType>(Tag->TypeForDecl);
593        if (TagTy->isBeingDefined())
594          // FIXME: is it necessarily being defined in the decl
595          // that owns the type?
596          return TagTy->getDecl();
597      }
598
599      return Tag;
600    }
601
602    assert(DeclKind >= Decl::firstFunction && DeclKind <= Decl::lastFunction &&
603          "Unknown DeclContext kind");
604    return this;
605  }
606}
607
608DeclContext *DeclContext::getNextContext() {
609  switch (DeclKind) {
610  case Decl::Namespace:
611    // Return the next namespace
612    return static_cast<NamespaceDecl*>(this)->getNextNamespace();
613
614  default:
615    return 0;
616  }
617}
618
619std::pair<Decl *, Decl *>
620DeclContext::BuildDeclChain(const llvm::SmallVectorImpl<Decl*> &Decls) {
621  // Build up a chain of declarations via the Decl::NextDeclInContext field.
622  Decl *FirstNewDecl = 0;
623  Decl *PrevDecl = 0;
624  for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
625    Decl *D = Decls[I];
626    if (PrevDecl)
627      PrevDecl->NextDeclInContext = D;
628    else
629      FirstNewDecl = D;
630
631    PrevDecl = D;
632  }
633
634  return std::make_pair(FirstNewDecl, PrevDecl);
635}
636
637/// \brief Load the declarations within this lexical storage from an
638/// external source.
639void
640DeclContext::LoadLexicalDeclsFromExternalStorage() const {
641  ExternalASTSource *Source = getParentASTContext().getExternalSource();
642  assert(hasExternalLexicalStorage() && Source && "No external storage?");
643
644  // Notify that we have a DeclContext that is initializing.
645  ExternalASTSource::Deserializing ADeclContext(Source);
646
647  llvm::SmallVector<Decl*, 64> Decls;
648  if (Source->FindExternalLexicalDecls(this, Decls))
649    return;
650
651  // There is no longer any lexical storage in this context
652  ExternalLexicalStorage = false;
653
654  if (Decls.empty())
655    return;
656
657  // We may have already loaded just the fields of this record, in which case
658  // don't add the decls, just replace the FirstDecl/LastDecl chain.
659  if (const RecordDecl *RD = dyn_cast<RecordDecl>(this))
660    if (RD->LoadedFieldsFromExternalStorage) {
661      llvm::tie(FirstDecl, LastDecl) = BuildDeclChain(Decls);
662      return;
663    }
664
665  // Splice the newly-read declarations into the beginning of the list
666  // of declarations.
667  Decl *ExternalFirst, *ExternalLast;
668  llvm::tie(ExternalFirst, ExternalLast) = BuildDeclChain(Decls);
669  ExternalLast->NextDeclInContext = FirstDecl;
670  FirstDecl = ExternalFirst;
671  if (!LastDecl)
672    LastDecl = ExternalLast;
673}
674
675DeclContext::lookup_result
676ExternalASTSource::SetNoExternalVisibleDeclsForName(const DeclContext *DC,
677                                                    DeclarationName Name) {
678  ASTContext &Context = DC->getParentASTContext();
679  StoredDeclsMap *Map;
680  if (!(Map = DC->LookupPtr))
681    Map = DC->CreateStoredDeclsMap(Context);
682
683  StoredDeclsList &List = (*Map)[Name];
684  assert(List.isNull());
685  (void) List;
686
687  return DeclContext::lookup_result();
688}
689
690DeclContext::lookup_result
691ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC,
692                                                  DeclarationName Name,
693                                    llvm::SmallVectorImpl<NamedDecl*> &Decls) {
694  ASTContext &Context = DC->getParentASTContext();;
695
696  StoredDeclsMap *Map;
697  if (!(Map = DC->LookupPtr))
698    Map = DC->CreateStoredDeclsMap(Context);
699
700  StoredDeclsList &List = (*Map)[Name];
701  for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
702    if (List.isNull())
703      List.setOnlyValue(Decls[I]);
704    else
705      List.AddSubsequentDecl(Decls[I]);
706  }
707
708  return List.getLookupResult();
709}
710
711void ExternalASTSource::MaterializeVisibleDeclsForName(const DeclContext *DC,
712                                                       DeclarationName Name,
713                                     llvm::SmallVectorImpl<NamedDecl*> &Decls) {
714  assert(DC->LookupPtr);
715  StoredDeclsMap &Map = *DC->LookupPtr;
716
717  // If there's an entry in the table the visible decls for this name have
718  // already been deserialized.
719  if (Map.find(Name) == Map.end()) {
720    StoredDeclsList &List = Map[Name];
721    for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
722      if (List.isNull())
723        List.setOnlyValue(Decls[I]);
724      else
725        List.AddSubsequentDecl(Decls[I]);
726    }
727  }
728}
729
730DeclContext::decl_iterator DeclContext::noload_decls_begin() const {
731  return decl_iterator(FirstDecl);
732}
733
734DeclContext::decl_iterator DeclContext::noload_decls_end() const {
735  return decl_iterator();
736}
737
738DeclContext::decl_iterator DeclContext::decls_begin() const {
739  if (hasExternalLexicalStorage())
740    LoadLexicalDeclsFromExternalStorage();
741
742  // FIXME: Check whether we need to load some declarations from
743  // external storage.
744  return decl_iterator(FirstDecl);
745}
746
747DeclContext::decl_iterator DeclContext::decls_end() const {
748  if (hasExternalLexicalStorage())
749    LoadLexicalDeclsFromExternalStorage();
750
751  return decl_iterator();
752}
753
754bool DeclContext::decls_empty() const {
755  if (hasExternalLexicalStorage())
756    LoadLexicalDeclsFromExternalStorage();
757
758  return !FirstDecl;
759}
760
761void DeclContext::removeDecl(Decl *D) {
762  assert(D->getLexicalDeclContext() == this &&
763         "decl being removed from non-lexical context");
764  assert((D->NextDeclInContext || D == LastDecl) &&
765         "decl is not in decls list");
766
767  // Remove D from the decl chain.  This is O(n) but hopefully rare.
768  if (D == FirstDecl) {
769    if (D == LastDecl)
770      FirstDecl = LastDecl = 0;
771    else
772      FirstDecl = D->NextDeclInContext;
773  } else {
774    for (Decl *I = FirstDecl; true; I = I->NextDeclInContext) {
775      assert(I && "decl not found in linked list");
776      if (I->NextDeclInContext == D) {
777        I->NextDeclInContext = D->NextDeclInContext;
778        if (D == LastDecl) LastDecl = I;
779        break;
780      }
781    }
782  }
783
784  // Mark that D is no longer in the decl chain.
785  D->NextDeclInContext = 0;
786
787  // Remove D from the lookup table if necessary.
788  if (isa<NamedDecl>(D)) {
789    NamedDecl *ND = cast<NamedDecl>(D);
790
791    StoredDeclsMap *Map = getPrimaryContext()->LookupPtr;
792    if (!Map) return;
793
794    StoredDeclsMap::iterator Pos = Map->find(ND->getDeclName());
795    assert(Pos != Map->end() && "no lookup entry for decl");
796    Pos->second.remove(ND);
797  }
798}
799
800void DeclContext::addHiddenDecl(Decl *D) {
801  assert(D->getLexicalDeclContext() == this &&
802         "Decl inserted into wrong lexical context");
803  assert(!D->getNextDeclInContext() && D != LastDecl &&
804         "Decl already inserted into a DeclContext");
805
806  if (FirstDecl) {
807    LastDecl->NextDeclInContext = D;
808    LastDecl = D;
809  } else {
810    FirstDecl = LastDecl = D;
811  }
812
813  // Notify a C++ record declaration that we've added a member, so it can
814  // update it's class-specific state.
815  if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(this))
816    Record->addedMember(D);
817}
818
819void DeclContext::addDecl(Decl *D) {
820  addHiddenDecl(D);
821
822  if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
823    ND->getDeclContext()->makeDeclVisibleInContext(ND);
824}
825
826/// buildLookup - Build the lookup data structure with all of the
827/// declarations in DCtx (and any other contexts linked to it or
828/// transparent contexts nested within it).
829void DeclContext::buildLookup(DeclContext *DCtx) {
830  for (; DCtx; DCtx = DCtx->getNextContext()) {
831    for (decl_iterator D = DCtx->decls_begin(),
832                    DEnd = DCtx->decls_end();
833         D != DEnd; ++D) {
834      // Insert this declaration into the lookup structure, but only
835      // if it's semantically in its decl context.  During non-lazy
836      // lookup building, this is implicitly enforced by addDecl.
837      if (NamedDecl *ND = dyn_cast<NamedDecl>(*D))
838        if (D->getDeclContext() == DCtx)
839          makeDeclVisibleInContextImpl(ND);
840
841      // Insert any forward-declared Objective-C interfaces into the lookup
842      // data structure.
843      if (ObjCClassDecl *Class = dyn_cast<ObjCClassDecl>(*D))
844        for (ObjCClassDecl::iterator I = Class->begin(), IEnd = Class->end();
845             I != IEnd; ++I)
846          makeDeclVisibleInContextImpl(I->getInterface());
847
848      // If this declaration is itself a transparent declaration context or
849      // inline namespace, add its members (recursively).
850      if (DeclContext *InnerCtx = dyn_cast<DeclContext>(*D))
851        if (InnerCtx->isTransparentContext() || InnerCtx->isInlineNamespace())
852          buildLookup(InnerCtx->getPrimaryContext());
853    }
854  }
855}
856
857DeclContext::lookup_result
858DeclContext::lookup(DeclarationName Name) {
859  DeclContext *PrimaryContext = getPrimaryContext();
860  if (PrimaryContext != this)
861    return PrimaryContext->lookup(Name);
862
863  if (hasExternalVisibleStorage()) {
864    // Check to see if we've already cached the lookup results.
865    if (LookupPtr) {
866      StoredDeclsMap::iterator I = LookupPtr->find(Name);
867      if (I != LookupPtr->end())
868        return I->second.getLookupResult();
869    }
870
871    ExternalASTSource *Source = getParentASTContext().getExternalSource();
872    return Source->FindExternalVisibleDeclsByName(this, Name);
873  }
874
875  /// If there is no lookup data structure, build one now by walking
876  /// all of the linked DeclContexts (in declaration order!) and
877  /// inserting their values.
878  if (!LookupPtr) {
879    buildLookup(this);
880
881    if (!LookupPtr)
882      return lookup_result(lookup_iterator(0), lookup_iterator(0));
883  }
884
885  StoredDeclsMap::iterator Pos = LookupPtr->find(Name);
886  if (Pos == LookupPtr->end())
887    return lookup_result(lookup_iterator(0), lookup_iterator(0));
888  return Pos->second.getLookupResult();
889}
890
891DeclContext::lookup_const_result
892DeclContext::lookup(DeclarationName Name) const {
893  return const_cast<DeclContext*>(this)->lookup(Name);
894}
895
896DeclContext *DeclContext::getRedeclContext() {
897  DeclContext *Ctx = this;
898  // Skip through transparent contexts.
899  while (Ctx->isTransparentContext())
900    Ctx = Ctx->getParent();
901  return Ctx;
902}
903
904DeclContext *DeclContext::getEnclosingNamespaceContext() {
905  DeclContext *Ctx = this;
906  // Skip through non-namespace, non-translation-unit contexts.
907  while (!Ctx->isFileContext())
908    Ctx = Ctx->getParent();
909  return Ctx->getPrimaryContext();
910}
911
912bool DeclContext::InEnclosingNamespaceSetOf(const DeclContext *O) const {
913  // For non-file contexts, this is equivalent to Equals.
914  if (!isFileContext())
915    return O->Equals(this);
916
917  do {
918    if (O->Equals(this))
919      return true;
920
921    const NamespaceDecl *NS = dyn_cast<NamespaceDecl>(O);
922    if (!NS || !NS->isInline())
923      break;
924    O = NS->getParent();
925  } while (O);
926
927  return false;
928}
929
930void DeclContext::makeDeclVisibleInContext(NamedDecl *D, bool Recoverable) {
931  // FIXME: This feels like a hack. Should DeclarationName support
932  // template-ids, or is there a better way to keep specializations
933  // from being visible?
934  if (isa<ClassTemplateSpecializationDecl>(D))
935    return;
936  if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
937    if (FD->isFunctionTemplateSpecialization())
938      return;
939
940  DeclContext *PrimaryContext = getPrimaryContext();
941  if (PrimaryContext != this) {
942    PrimaryContext->makeDeclVisibleInContext(D, Recoverable);
943    return;
944  }
945
946  // If we already have a lookup data structure, perform the insertion
947  // into it. If we haven't deserialized externally stored decls, deserialize
948  // them so we can add the decl. Otherwise, be lazy and don't build that
949  // structure until someone asks for it.
950  if (LookupPtr || !Recoverable || hasExternalVisibleStorage())
951    makeDeclVisibleInContextImpl(D);
952
953  // If we are a transparent context or inline namespace, insert into our
954  // parent context, too. This operation is recursive.
955  if (isTransparentContext() || isInlineNamespace())
956    getParent()->makeDeclVisibleInContext(D, Recoverable);
957
958  Decl *DCAsDecl = cast<Decl>(this);
959  // Notify that a decl was made visible unless it's a Tag being defined.
960  if (!(isa<TagDecl>(DCAsDecl) && cast<TagDecl>(DCAsDecl)->isBeingDefined()))
961    if (ASTMutationListener *L = DCAsDecl->getASTMutationListener())
962      L->AddedVisibleDecl(this, D);
963}
964
965void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D) {
966  // Skip unnamed declarations.
967  if (!D->getDeclName())
968    return;
969
970  // FIXME: This feels like a hack. Should DeclarationName support
971  // template-ids, or is there a better way to keep specializations
972  // from being visible?
973  if (isa<ClassTemplateSpecializationDecl>(D))
974    return;
975
976  ASTContext *C = 0;
977  if (!LookupPtr) {
978    C = &getParentASTContext();
979    CreateStoredDeclsMap(*C);
980  }
981
982  // If there is an external AST source, load any declarations it knows about
983  // with this declaration's name.
984  // If the lookup table contains an entry about this name it means that we
985  // have already checked the external source.
986  if (ExternalASTSource *Source = getParentASTContext().getExternalSource())
987    if (hasExternalVisibleStorage() &&
988        LookupPtr->find(D->getDeclName()) == LookupPtr->end())
989      Source->FindExternalVisibleDeclsByName(this, D->getDeclName());
990
991  // Insert this declaration into the map.
992  StoredDeclsList &DeclNameEntries = (*LookupPtr)[D->getDeclName()];
993  if (DeclNameEntries.isNull()) {
994    DeclNameEntries.setOnlyValue(D);
995    return;
996  }
997
998  // If it is possible that this is a redeclaration, check to see if there is
999  // already a decl for which declarationReplaces returns true.  If there is
1000  // one, just replace it and return.
1001  if (DeclNameEntries.HandleRedeclaration(D))
1002    return;
1003
1004  // Put this declaration into the appropriate slot.
1005  DeclNameEntries.AddSubsequentDecl(D);
1006}
1007
1008void DeclContext::MaterializeVisibleDeclsFromExternalStorage() {
1009  ExternalASTSource *Source = getParentASTContext().getExternalSource();
1010  assert(hasExternalVisibleStorage() && Source && "No external storage?");
1011
1012  if (!LookupPtr)
1013    CreateStoredDeclsMap(getParentASTContext());
1014  Source->MaterializeVisibleDecls(this);
1015}
1016
1017/// Returns iterator range [First, Last) of UsingDirectiveDecls stored within
1018/// this context.
1019DeclContext::udir_iterator_range
1020DeclContext::getUsingDirectives() const {
1021  lookup_const_result Result = lookup(UsingDirectiveDecl::getName());
1022  return udir_iterator_range(reinterpret_cast<udir_iterator>(Result.first),
1023                             reinterpret_cast<udir_iterator>(Result.second));
1024}
1025
1026//===----------------------------------------------------------------------===//
1027// Creation and Destruction of StoredDeclsMaps.                               //
1028//===----------------------------------------------------------------------===//
1029
1030StoredDeclsMap *DeclContext::CreateStoredDeclsMap(ASTContext &C) const {
1031  assert(!LookupPtr && "context already has a decls map");
1032  assert(getPrimaryContext() == this &&
1033         "creating decls map on non-primary context");
1034
1035  StoredDeclsMap *M;
1036  bool Dependent = isDependentContext();
1037  if (Dependent)
1038    M = new DependentStoredDeclsMap();
1039  else
1040    M = new StoredDeclsMap();
1041  M->Previous = C.LastSDM;
1042  C.LastSDM = llvm::PointerIntPair<StoredDeclsMap*,1>(M, Dependent);
1043  LookupPtr = M;
1044  return M;
1045}
1046
1047void ASTContext::ReleaseDeclContextMaps() {
1048  // It's okay to delete DependentStoredDeclsMaps via a StoredDeclsMap
1049  // pointer because the subclass doesn't add anything that needs to
1050  // be deleted.
1051  StoredDeclsMap::DestroyAll(LastSDM.getPointer(), LastSDM.getInt());
1052}
1053
1054void StoredDeclsMap::DestroyAll(StoredDeclsMap *Map, bool Dependent) {
1055  while (Map) {
1056    // Advance the iteration before we invalidate memory.
1057    llvm::PointerIntPair<StoredDeclsMap*,1> Next = Map->Previous;
1058
1059    if (Dependent)
1060      delete static_cast<DependentStoredDeclsMap*>(Map);
1061    else
1062      delete Map;
1063
1064    Map = Next.getPointer();
1065    Dependent = Next.getInt();
1066  }
1067}
1068
1069DependentDiagnostic *DependentDiagnostic::Create(ASTContext &C,
1070                                                 DeclContext *Parent,
1071                                           const PartialDiagnostic &PDiag) {
1072  assert(Parent->isDependentContext()
1073         && "cannot iterate dependent diagnostics of non-dependent context");
1074  Parent = Parent->getPrimaryContext();
1075  if (!Parent->LookupPtr)
1076    Parent->CreateStoredDeclsMap(C);
1077
1078  DependentStoredDeclsMap *Map
1079    = static_cast<DependentStoredDeclsMap*>(Parent->LookupPtr);
1080
1081  // Allocate the copy of the PartialDiagnostic via the ASTContext's
1082  // BumpPtrAllocator, rather than the ASTContext itself.
1083  PartialDiagnostic::Storage *DiagStorage = 0;
1084  if (PDiag.hasStorage())
1085    DiagStorage = new (C) PartialDiagnostic::Storage;
1086
1087  DependentDiagnostic *DD = new (C) DependentDiagnostic(PDiag, DiagStorage);
1088
1089  // TODO: Maybe we shouldn't reverse the order during insertion.
1090  DD->NextDiagnostic = Map->FirstDiagnostic;
1091  Map->FirstDiagnostic = DD;
1092
1093  return DD;
1094}
1095