DeclBase.cpp revision 6037fcba3431b47de1a994c9b286feac17894eff 
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/DeclObjC.h"
16#include "clang/AST/DeclCXX.h"
17#include "clang/AST/ASTContext.h"
18#include "clang/AST/Type.h"
19#include "llvm/ADT/DenseMap.h"
20#include <algorithm>
21#include <functional>
22#include <vector>
23using namespace clang;
24
25//===----------------------------------------------------------------------===//
26//  Statistics
27//===----------------------------------------------------------------------===//
28
29// temporary statistics gathering
30static unsigned nFuncs = 0;
31static unsigned nVars = 0;
32static unsigned nParmVars = 0;
33static unsigned nOriginalParmVars = 0;
34static unsigned nSUC = 0;
35static unsigned nCXXSUC = 0;
36static unsigned nEnumConst = 0;
37static unsigned nEnumDecls = 0;
38static unsigned nNamespaces = 0;
39static unsigned nOverFuncs = 0;
40static unsigned nTypedef = 0;
41static unsigned nFieldDecls = 0;
42static unsigned nInterfaceDecls = 0;
43static unsigned nClassDecls = 0;
44static unsigned nMethodDecls = 0;
45static unsigned nProtocolDecls = 0;
46static unsigned nForwardProtocolDecls = 0;
47static unsigned nCategoryDecls = 0;
48static unsigned nIvarDecls = 0;
49static unsigned nAtDefsFieldDecls = 0;
50static unsigned nObjCImplementationDecls = 0;
51static unsigned nObjCCategoryImpl = 0;
52static unsigned nObjCCompatibleAlias = 0;
53static unsigned nObjCPropertyDecl = 0;
54static unsigned nObjCPropertyImplDecl = 0;
55static unsigned nLinkageSpecDecl = 0;
56static unsigned nFileScopeAsmDecl = 0;
57static unsigned nBlockDecls = 0;
58
59static bool StatSwitch = false;
60
61// This keeps track of all decl attributes. Since so few decls have attrs, we
62// keep them in a hash map instead of wasting space in the Decl class.
63typedef llvm::DenseMap<const Decl*, Attr*> DeclAttrMapTy;
64
65static DeclAttrMapTy *DeclAttrs = 0;
66
67const char *Decl::getDeclKindName() const {
68  switch (DeclKind) {
69  default: assert(0 && "Unknown decl kind!");
70  case Namespace:           return "Namespace";
71  case OverloadedFunction:  return "OverloadedFunction";
72  case Typedef:             return "Typedef";
73  case Function:            return "Function";
74  case Var:                 return "Var";
75  case ParmVar:             return "ParmVar";
76  case OriginalParmVar:     return "OriginalParmVar";
77  case EnumConstant:        return "EnumConstant";
78  case ObjCIvar:            return "ObjCIvar";
79  case ObjCInterface:       return "ObjCInterface";
80  case ObjCImplementation:  return "ObjCImplementation";
81  case ObjCClass:           return "ObjCClass";
82  case ObjCMethod:          return "ObjCMethod";
83  case ObjCProtocol:        return "ObjCProtocol";
84  case ObjCProperty:        return "ObjCProperty";
85  case ObjCPropertyImpl:    return "ObjCPropertyImpl";
86  case ObjCForwardProtocol: return "ObjCForwardProtocol";
87  case Record:              return "Record";
88  case CXXRecord:           return "CXXRecord";
89  case Enum:                return "Enum";
90  case Block:               return "Block";
91  }
92}
93
94bool Decl::CollectingStats(bool Enable) {
95  if (Enable)
96    StatSwitch = true;
97  return StatSwitch;
98}
99
100void Decl::PrintStats() {
101  fprintf(stderr, "*** Decl Stats:\n");
102  fprintf(stderr, "  %d decls total.\n",
103          int(nFuncs+nVars+nParmVars+nOriginalParmVars+nFieldDecls+nSUC+nCXXSUC+
104              nEnumDecls+nEnumConst+nTypedef+nInterfaceDecls+nClassDecls+
105              nMethodDecls+nProtocolDecls+nCategoryDecls+nIvarDecls+
106              nAtDefsFieldDecls+nNamespaces+nOverFuncs));
107  fprintf(stderr, "    %d namespace decls, %d each (%d bytes)\n",
108          nNamespaces, (int)sizeof(NamespaceDecl),
109          int(nNamespaces*sizeof(NamespaceDecl)));
110  fprintf(stderr, "    %d overloaded function decls, %d each (%d bytes)\n",
111          nOverFuncs, (int)sizeof(OverloadedFunctionDecl),
112          int(nOverFuncs*sizeof(OverloadedFunctionDecl)));
113  fprintf(stderr, "    %d function decls, %d each (%d bytes)\n",
114          nFuncs, (int)sizeof(FunctionDecl), int(nFuncs*sizeof(FunctionDecl)));
115  fprintf(stderr, "    %d variable decls, %d each (%d bytes)\n",
116          nVars, (int)sizeof(VarDecl),
117          int(nVars*sizeof(VarDecl)));
118  fprintf(stderr, "    %d parameter variable decls, %d each (%d bytes)\n",
119          nParmVars, (int)sizeof(ParmVarDecl),
120          int(nParmVars*sizeof(ParmVarDecl)));
121  fprintf(stderr, "    %d original parameter variable decls, %d each (%d bytes)\n",
122          nOriginalParmVars, (int)sizeof(ParmVarWithOriginalTypeDecl),
123          int(nOriginalParmVars*sizeof(ParmVarWithOriginalTypeDecl)));
124  fprintf(stderr, "    %d field decls, %d each (%d bytes)\n",
125          nFieldDecls, (int)sizeof(FieldDecl),
126          int(nFieldDecls*sizeof(FieldDecl)));
127  fprintf(stderr, "    %d @defs generated field decls, %d each (%d bytes)\n",
128          nAtDefsFieldDecls, (int)sizeof(ObjCAtDefsFieldDecl),
129          int(nAtDefsFieldDecls*sizeof(ObjCAtDefsFieldDecl)));
130  fprintf(stderr, "    %d struct/union/class decls, %d each (%d bytes)\n",
131          nSUC, (int)sizeof(RecordDecl),
132          int(nSUC*sizeof(RecordDecl)));
133  fprintf(stderr, "    %d C++ struct/union/class decls, %d each (%d bytes)\n",
134          nCXXSUC, (int)sizeof(CXXRecordDecl),
135          int(nCXXSUC*sizeof(CXXRecordDecl)));
136  fprintf(stderr, "    %d enum decls, %d each (%d bytes)\n",
137          nEnumDecls, (int)sizeof(EnumDecl),
138          int(nEnumDecls*sizeof(EnumDecl)));
139  fprintf(stderr, "    %d enum constant decls, %d each (%d bytes)\n",
140          nEnumConst, (int)sizeof(EnumConstantDecl),
141          int(nEnumConst*sizeof(EnumConstantDecl)));
142  fprintf(stderr, "    %d typedef decls, %d each (%d bytes)\n",
143          nTypedef, (int)sizeof(TypedefDecl),int(nTypedef*sizeof(TypedefDecl)));
144  // Objective-C decls...
145  fprintf(stderr, "    %d interface decls, %d each (%d bytes)\n",
146          nInterfaceDecls, (int)sizeof(ObjCInterfaceDecl),
147          int(nInterfaceDecls*sizeof(ObjCInterfaceDecl)));
148  fprintf(stderr, "    %d instance variable decls, %d each (%d bytes)\n",
149          nIvarDecls, (int)sizeof(ObjCIvarDecl),
150          int(nIvarDecls*sizeof(ObjCIvarDecl)));
151  fprintf(stderr, "    %d class decls, %d each (%d bytes)\n",
152          nClassDecls, (int)sizeof(ObjCClassDecl),
153          int(nClassDecls*sizeof(ObjCClassDecl)));
154  fprintf(stderr, "    %d method decls, %d each (%d bytes)\n",
155          nMethodDecls, (int)sizeof(ObjCMethodDecl),
156          int(nMethodDecls*sizeof(ObjCMethodDecl)));
157  fprintf(stderr, "    %d protocol decls, %d each (%d bytes)\n",
158          nProtocolDecls, (int)sizeof(ObjCProtocolDecl),
159          int(nProtocolDecls*sizeof(ObjCProtocolDecl)));
160  fprintf(stderr, "    %d forward protocol decls, %d each (%d bytes)\n",
161          nForwardProtocolDecls, (int)sizeof(ObjCForwardProtocolDecl),
162          int(nForwardProtocolDecls*sizeof(ObjCForwardProtocolDecl)));
163  fprintf(stderr, "    %d category decls, %d each (%d bytes)\n",
164          nCategoryDecls, (int)sizeof(ObjCCategoryDecl),
165          int(nCategoryDecls*sizeof(ObjCCategoryDecl)));
166
167  fprintf(stderr, "    %d class implementation decls, %d each (%d bytes)\n",
168          nObjCImplementationDecls, (int)sizeof(ObjCImplementationDecl),
169          int(nObjCImplementationDecls*sizeof(ObjCImplementationDecl)));
170
171  fprintf(stderr, "    %d class implementation decls, %d each (%d bytes)\n",
172          nObjCCategoryImpl, (int)sizeof(ObjCCategoryImplDecl),
173          int(nObjCCategoryImpl*sizeof(ObjCCategoryImplDecl)));
174
175  fprintf(stderr, "    %d compatibility alias decls, %d each (%d bytes)\n",
176          nObjCCompatibleAlias, (int)sizeof(ObjCCompatibleAliasDecl),
177          int(nObjCCompatibleAlias*sizeof(ObjCCompatibleAliasDecl)));
178
179  fprintf(stderr, "    %d property decls, %d each (%d bytes)\n",
180          nObjCPropertyDecl, (int)sizeof(ObjCPropertyDecl),
181          int(nObjCPropertyDecl*sizeof(ObjCPropertyDecl)));
182
183  fprintf(stderr, "    %d property implementation decls, %d each (%d bytes)\n",
184          nObjCPropertyImplDecl, (int)sizeof(ObjCPropertyImplDecl),
185          int(nObjCPropertyImplDecl*sizeof(ObjCPropertyImplDecl)));
186
187  fprintf(stderr, "Total bytes = %d\n",
188          int(nFuncs*sizeof(FunctionDecl)+
189              nVars*sizeof(VarDecl)+nParmVars*sizeof(ParmVarDecl)+
190              nOriginalParmVars*sizeof(ParmVarWithOriginalTypeDecl)+
191              nFieldDecls*sizeof(FieldDecl)+nSUC*sizeof(RecordDecl)+
192              nCXXSUC*sizeof(CXXRecordDecl)+
193              nEnumDecls*sizeof(EnumDecl)+nEnumConst*sizeof(EnumConstantDecl)+
194              nTypedef*sizeof(TypedefDecl)+
195              nInterfaceDecls*sizeof(ObjCInterfaceDecl)+
196              nIvarDecls*sizeof(ObjCIvarDecl)+
197              nClassDecls*sizeof(ObjCClassDecl)+
198              nMethodDecls*sizeof(ObjCMethodDecl)+
199              nProtocolDecls*sizeof(ObjCProtocolDecl)+
200              nForwardProtocolDecls*sizeof(ObjCForwardProtocolDecl)+
201              nCategoryDecls*sizeof(ObjCCategoryDecl)+
202              nObjCImplementationDecls*sizeof(ObjCImplementationDecl)+
203              nObjCCategoryImpl*sizeof(ObjCCategoryImplDecl)+
204              nObjCCompatibleAlias*sizeof(ObjCCompatibleAliasDecl)+
205              nObjCPropertyDecl*sizeof(ObjCPropertyDecl)+
206              nObjCPropertyImplDecl*sizeof(ObjCPropertyImplDecl)+
207              nLinkageSpecDecl*sizeof(LinkageSpecDecl)+
208              nFileScopeAsmDecl*sizeof(FileScopeAsmDecl)+
209              nNamespaces*sizeof(NamespaceDecl)+
210              nOverFuncs*sizeof(OverloadedFunctionDecl)));
211
212}
213
214void Decl::addDeclKind(Kind k) {
215  switch (k) {
216  case Namespace:           nNamespaces++; break;
217  case OverloadedFunction:  nOverFuncs++; break;
218  case Typedef:             nTypedef++; break;
219  case Function:            nFuncs++; break;
220  case Var:                 nVars++; break;
221  case ParmVar:             nParmVars++; break;
222  case OriginalParmVar:     nOriginalParmVars++; break;
223  case EnumConstant:        nEnumConst++; break;
224  case Field:               nFieldDecls++; break;
225  case Record:              nSUC++; break;
226  case Enum:                nEnumDecls++; break;
227  case ObjCContainer:       break; // is abstract...no need to account for.
228  case ObjCInterface:       nInterfaceDecls++; break;
229  case ObjCClass:           nClassDecls++; break;
230  case ObjCMethod:          nMethodDecls++; break;
231  case ObjCProtocol:        nProtocolDecls++; break;
232  case ObjCForwardProtocol: nForwardProtocolDecls++; break;
233  case ObjCCategory:        nCategoryDecls++; break;
234  case ObjCIvar:            nIvarDecls++; break;
235  case ObjCAtDefsField:     nAtDefsFieldDecls++; break;
236  case ObjCImplementation:  nObjCImplementationDecls++; break;
237  case ObjCCategoryImpl:    nObjCCategoryImpl++; break;
238  case ObjCCompatibleAlias: nObjCCompatibleAlias++; break;
239  case ObjCProperty:        nObjCPropertyDecl++; break;
240  case ObjCPropertyImpl:    nObjCPropertyImplDecl++; break;
241  case LinkageSpec:         nLinkageSpecDecl++; break;
242  case FileScopeAsm:        nFileScopeAsmDecl++; break;
243  case Block:               nBlockDecls++; break;
244  case ImplicitParam:
245  case TranslationUnit:     break;
246
247  case CXXRecord:           nCXXSUC++; break;
248  // FIXME: Statistics for C++ decls.
249  case TemplateTypeParm:
250  case NonTypeTemplateParm:
251  case CXXMethod:
252  case CXXConstructor:
253  case CXXDestructor:
254  case CXXConversion:
255  case CXXClassVar:
256    break;
257  }
258}
259
260//===----------------------------------------------------------------------===//
261// Decl Implementation
262//===----------------------------------------------------------------------===//
263
264// Out-of-line virtual method providing a home for Decl.
265Decl::~Decl() {
266  if (!HasAttrs)
267    return;
268
269  DeclAttrMapTy::iterator it = DeclAttrs->find(this);
270  assert(it != DeclAttrs->end() && "No attrs found but HasAttrs is true!");
271
272  // release attributes.
273  delete it->second;
274  invalidateAttrs();
275}
276
277void Decl::addAttr(Attr *NewAttr) {
278  if (!DeclAttrs)
279    DeclAttrs = new DeclAttrMapTy();
280
281  Attr *&ExistingAttr = (*DeclAttrs)[this];
282
283  NewAttr->setNext(ExistingAttr);
284  ExistingAttr = NewAttr;
285
286  HasAttrs = true;
287}
288
289void Decl::invalidateAttrs() {
290  if (!HasAttrs) return;
291
292  HasAttrs = false;
293  (*DeclAttrs)[this] = 0;
294  DeclAttrs->erase(this);
295
296  if (DeclAttrs->empty()) {
297    delete DeclAttrs;
298    DeclAttrs = 0;
299  }
300}
301
302const Attr *Decl::getAttrs() const {
303  if (!HasAttrs)
304    return 0;
305
306  return (*DeclAttrs)[this];
307}
308
309void Decl::swapAttrs(Decl *RHS) {
310  bool HasLHSAttr = this->HasAttrs;
311  bool HasRHSAttr = RHS->HasAttrs;
312
313  // Usually, neither decl has attrs, nothing to do.
314  if (!HasLHSAttr && !HasRHSAttr) return;
315
316  // If 'this' has no attrs, swap the other way.
317  if (!HasLHSAttr)
318    return RHS->swapAttrs(this);
319
320  // Handle the case when both decls have attrs.
321  if (HasRHSAttr) {
322    std::swap((*DeclAttrs)[this], (*DeclAttrs)[RHS]);
323    return;
324  }
325
326  // Otherwise, LHS has an attr and RHS doesn't.
327  (*DeclAttrs)[RHS] = (*DeclAttrs)[this];
328  (*DeclAttrs).erase(this);
329  this->HasAttrs = false;
330  RHS->HasAttrs = true;
331}
332
333
334void Decl::Destroy(ASTContext& C) {
335  if (ScopedDecl* SD = dyn_cast<ScopedDecl>(this)) {
336
337    // Observe the unrolled recursion.  By setting N->NextDeclarator = 0x0
338    // within the loop, only the Destroy method for the first ScopedDecl
339    // will deallocate all of the ScopedDecls in a chain.
340
341    ScopedDecl* N = SD->getNextDeclarator();
342
343    while (N) {
344      ScopedDecl* Tmp = N->getNextDeclarator();
345      N->NextDeclarator = 0x0;
346      N->Destroy(C);
347      N = Tmp;
348    }
349  }
350
351  this->~Decl();
352  C.getAllocator().Deallocate((void *)this);
353}
354
355Decl *Decl::castFromDeclContext (const DeclContext *D) {
356  return DeclContext::CastTo<Decl>(D);
357}
358
359DeclContext *Decl::castToDeclContext(const Decl *D) {
360  return DeclContext::CastTo<DeclContext>(D);
361}
362
363//===----------------------------------------------------------------------===//
364// DeclContext Implementation
365//===----------------------------------------------------------------------===//
366
367const DeclContext *DeclContext::getParent() const {
368  if (const ScopedDecl *SD = dyn_cast<ScopedDecl>(this))
369    return SD->getDeclContext();
370  else if (const BlockDecl *BD = dyn_cast<BlockDecl>(this))
371    return BD->getParentContext();
372  else
373    return NULL;
374}
375
376const DeclContext *DeclContext::getLexicalParent() const {
377  if (const ScopedDecl *SD = dyn_cast<ScopedDecl>(this))
378    return SD->getLexicalDeclContext();
379  return getParent();
380}
381
382// FIXME: We really want to use a DenseSet here to eliminate the
383// redundant storage of the declaration names, but (1) it doesn't give
384// us the ability to search based on DeclarationName, (2) we really
385// need something more like a DenseMultiSet, and (3) it's
386// implemented in terms of DenseMap anyway. However, this data
387// structure is really space-inefficient, so we'll have to do
388// something.
389typedef llvm::DenseMap<DeclarationName, std::vector<ScopedDecl*> >
390  StoredDeclsMap;
391
392DeclContext::~DeclContext() {
393  unsigned Size = LookupPtr.getInt();
394  if (Size == LookupIsMap) {
395    StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
396    delete Map;
397  } else {
398    ScopedDecl **Array = static_cast<ScopedDecl**>(LookupPtr.getPointer());
399    delete [] Array;
400  }
401}
402
403void DeclContext::DestroyDecls(ASTContext &C) {
404  for (decl_iterator D = decls_begin(); D != decls_end(); ++D) {
405    // FIXME: assert that this condition holds.
406    if ((*D)->getLexicalDeclContext() == this)
407      (*D)->Destroy(C);
408  }
409}
410
411bool DeclContext::isTransparentContext() const {
412  if (DeclKind == Decl::Enum)
413    return true; // FIXME: Check for C++0x scoped enums
414  else if (DeclKind == Decl::LinkageSpec)
415    return true;
416  else if (DeclKind == Decl::Record || DeclKind == Decl::CXXRecord)
417    return cast<RecordDecl>(this)->isAnonymousStructOrUnion();
418  else if (DeclKind == Decl::Namespace)
419    return false; // FIXME: Check for C++0x inline namespaces
420
421  return false;
422}
423
424DeclContext *DeclContext::getPrimaryContext() {
425  switch (DeclKind) {
426  case Decl::TranslationUnit:
427  case Decl::LinkageSpec:
428  case Decl::Block:
429    // There is only one DeclContext for these entities.
430    return this;
431
432  case Decl::Namespace:
433    // The original namespace is our primary context.
434    return static_cast<NamespaceDecl*>(this)->getOriginalNamespace();
435
436  case Decl::Enum:
437#if 0
438    // FIXME: See the comment for CXXRecord, below.
439    // The declaration associated with the enumeration type is our
440    // primary context.
441    return Context.getTypeDeclType(static_cast<EnumDecl*>(this))
442             ->getAsEnumType()->getDecl();
443#else
444    return this;
445#endif
446
447  case Decl::Record:
448  case Decl::CXXRecord: {
449    // The declaration associated with the type is be our primary
450    // context.
451#if 0
452    // FIXME: This is what we expect to do. However, it doesn't work
453    // because ASTContext::setTagDefinition changes the result of
454    // Context.getTypeDeclType, meaning that our "primary" declaration
455    // of a RecordDecl/CXXRecordDecl will change, and we won't be able
456    // to find any values inserted into the earlier "primary"
457    // declaration. We need better tracking of redeclarations and
458    // definitions.
459    QualType Type = Context.getTypeDeclType(static_cast<RecordDecl*>(this));
460    return Type->getAsRecordType()->getDecl();
461#else
462    // FIXME: This hack will work for now, because the declaration we
463    // create when we're defining the record is the one we'll use as
464    // the definition later.
465    return this;
466#endif
467  }
468
469  case Decl::ObjCMethod:
470    return this;
471
472  case Decl::ObjCInterface:
473  case Decl::ObjCProtocol:
474  case Decl::ObjCCategory:
475    // FIXME: Can Objective-C interfaces be forward-declared?
476    return this;
477
478  case Decl::ObjCImplementation:
479  case Decl::ObjCCategoryImpl:
480    return this;
481
482  default:
483    assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast &&
484          "Unknown DeclContext kind");
485    return this;
486  }
487}
488
489DeclContext *DeclContext::getNextContext() {
490  switch (DeclKind) {
491  case Decl::TranslationUnit:
492  case Decl::Enum:
493  case Decl::Record:
494  case Decl::CXXRecord:
495  case Decl::ObjCMethod:
496  case Decl::ObjCInterface:
497  case Decl::ObjCCategory:
498  case Decl::ObjCProtocol:
499  case Decl::ObjCImplementation:
500  case Decl::ObjCCategoryImpl:
501  case Decl::LinkageSpec:
502  case Decl::Block:
503    // There is only one DeclContext for these entities.
504    return 0;
505
506  case Decl::Namespace:
507    // Return the next namespace
508    return static_cast<NamespaceDecl*>(this)->getNextNamespace();
509
510  default:
511    assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast &&
512          "Unknown DeclContext kind");
513    return 0;
514  }
515}
516
517void DeclContext::addDecl(ASTContext &Context, ScopedDecl *D, bool AllowLookup) {
518  assert(D->getLexicalDeclContext() == this && "Decl inserted into wrong lexical context");
519  assert(!D->NextDeclInScope && D != LastDecl &&
520         "Decl already inserted into a DeclContext");
521
522  if (FirstDecl) {
523    LastDecl->NextDeclInScope = D;
524    LastDecl = D;
525  } else {
526    FirstDecl = LastDecl = D;
527  }
528  if (AllowLookup)
529    D->getDeclContext()->insert(Context, D);
530}
531
532/// buildLookup - Build the lookup data structure with all of the
533/// declarations in DCtx (and any other contexts linked to it or
534/// transparent contexts nested within it).
535void DeclContext::buildLookup(DeclContext *DCtx) {
536  for (; DCtx; DCtx = DCtx->getNextContext()) {
537    for (decl_iterator D = DCtx->decls_begin(), DEnd = DCtx->decls_end();
538         D != DEnd; ++D) {
539      // Insert this declaration into the lookup structure
540      insertImpl(*D);
541
542      // If this declaration is itself a transparent declaration context,
543      // add its members (recursively).
544      if (DeclContext *InnerCtx = dyn_cast<DeclContext>(*D))
545        if (InnerCtx->isTransparentContext())
546          buildLookup(InnerCtx->getPrimaryContext());
547    }
548  }
549}
550
551DeclContext::lookup_result
552DeclContext::lookup(DeclarationName Name) {
553  DeclContext *PrimaryContext = getPrimaryContext();
554  if (PrimaryContext != this)
555    return PrimaryContext->lookup(Name);
556
557  /// If there is no lookup data structure, build one now by walking
558  /// all of the linked DeclContexts (in declaration order!) and
559  /// inserting their values.
560  if (LookupPtr.getPointer() == 0)
561    buildLookup(this);
562
563  if (isLookupMap()) {
564    StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
565    StoredDeclsMap::iterator Pos = Map->find(Name);
566    if (Pos != Map->end())
567      return lookup_result(&Pos->second.front(),
568                           &Pos->second.front() + Pos->second.size());
569    return lookup_result(0, 0);
570  }
571
572  // We have a small array. Look into it.
573  unsigned Size = LookupPtr.getInt();
574  ScopedDecl **Array = static_cast<ScopedDecl**>(LookupPtr.getPointer());
575  for (unsigned Idx = 0; Idx != Size; ++Idx)
576    if (Array[Idx]->getDeclName() == Name) {
577      unsigned Last = Idx + 1;
578      while (Last != Size && Array[Last]->getDeclName() == Name)
579        ++Last;
580      return lookup_result(&Array[Idx], &Array[Last]);
581    }
582
583  return lookup_result(0, 0);
584}
585
586DeclContext::lookup_const_result
587DeclContext::lookup(DeclarationName Name) const {
588  return const_cast<DeclContext*>(this)->lookup(Name);
589}
590
591const DeclContext *DeclContext::getLookupContext() const {
592  const DeclContext *Ctx = this;
593  // Skip through transparent contexts.
594  while (Ctx->isTransparentContext())
595    Ctx = Ctx->getParent();
596  return Ctx;
597}
598
599void DeclContext::insert(ASTContext &Context, ScopedDecl *D) {
600  DeclContext *PrimaryContext = getPrimaryContext();
601  if (PrimaryContext != this) {
602    PrimaryContext->insert(Context, D);
603    return;
604  }
605
606  // If we already have a lookup data structure, perform the insertion
607  // into it. Otherwise, be lazy and don't build that structure until
608  // someone asks for it.
609  if (LookupPtr.getPointer())
610    insertImpl(D);
611
612  // If we are a transparent context, insert into our parent context,
613  // too. This operation is recursive.
614  if (isTransparentContext())
615    getParent()->insert(Context, D);
616}
617
618void DeclContext::insertImpl(ScopedDecl *D) {
619  // Skip unnamed declarations.
620  if (!D->getDeclName())
621    return;
622
623  bool MayBeRedeclaration = true;
624
625  if (!isLookupMap()) {
626    unsigned Size = LookupPtr.getInt();
627
628    // The lookup data is stored as an array. Search through the array
629    // to find the insertion location.
630    ScopedDecl **Array;
631    if (Size == 0) {
632      Array = new ScopedDecl*[LookupIsMap - 1];
633      LookupPtr.setPointer(Array);
634    } else {
635      Array = static_cast<ScopedDecl **>(LookupPtr.getPointer());
636    }
637
638    // We always keep declarations of the same name next to each other
639    // in the array, so that it is easy to return multiple results
640    // from lookup().
641    unsigned FirstMatch;
642    for (FirstMatch = 0; FirstMatch != Size; ++FirstMatch)
643      if (Array[FirstMatch]->getDeclName() == D->getDeclName())
644        break;
645
646    unsigned InsertPos = FirstMatch;
647    if (FirstMatch != Size) {
648      // We found another declaration with the same name. First
649      // determine whether this is a redeclaration of an existing
650      // declaration in this scope, in which case we will replace the
651      // existing declaration.
652      unsigned LastMatch = FirstMatch;
653      for (; LastMatch != Size; ++LastMatch) {
654        if (Array[LastMatch]->getDeclName() != D->getDeclName())
655          break;
656
657        if (D->declarationReplaces(Array[LastMatch])) {
658          // D is a redeclaration of an existing element in the
659          // array. Replace that element with D.
660          Array[LastMatch] = D;
661          return;
662        }
663      }
664
665      // [FirstMatch, LastMatch) contains the set of declarations that
666      // have the same name as this declaration. Determine where the
667      // declaration D will be inserted into this range.
668      if (D->getIdentifierNamespace() == Decl::IDNS_Tag)
669        InsertPos = LastMatch;
670      else if (Array[LastMatch-1]->getIdentifierNamespace() == Decl::IDNS_Tag)
671        InsertPos = LastMatch - 1;
672      else
673        InsertPos = LastMatch;
674    }
675
676    if (Size < LookupIsMap - 1) {
677      // The new declaration will fit in the array. Insert the new
678      // declaration at the position Match in the array.
679      for (unsigned Idx = Size; Idx > InsertPos; --Idx)
680       Array[Idx] = Array[Idx-1];
681
682      Array[InsertPos] = D;
683      LookupPtr.setInt(Size + 1);
684      return;
685    }
686
687    // We've reached capacity in this array. Create a map and copy in
688    // all of the declarations that were stored in the array.
689    StoredDeclsMap *Map = new StoredDeclsMap(16);
690    LookupPtr.setPointer(Map);
691    LookupPtr.setInt(LookupIsMap);
692    for (unsigned Idx = 0; Idx != LookupIsMap - 1; ++Idx)
693      insertImpl(Array[Idx]);
694    delete [] Array;
695
696    // Fall through to perform insertion into the map.
697    MayBeRedeclaration = false;
698  }
699
700  // Insert this declaration into the map.
701  StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
702  StoredDeclsMap::iterator Pos = Map->find(D->getDeclName());
703  if (Pos != Map->end()) {
704    if (MayBeRedeclaration) {
705      // Determine if this declaration is actually a redeclaration.
706      std::vector<ScopedDecl *>::iterator Redecl
707        = std::find_if(Pos->second.begin(), Pos->second.end(),
708                     std::bind1st(std::mem_fun(&ScopedDecl::declarationReplaces),
709                                  D));
710      if (Redecl != Pos->second.end()) {
711        *Redecl = D;
712        return;
713      }
714    }
715
716    // Put this declaration into the appropriate slot.
717    if (D->getIdentifierNamespace() == Decl::IDNS_Tag || Pos->second.empty())
718      Pos->second.push_back(D);
719    else if (Pos->second.back()->getIdentifierNamespace() == Decl::IDNS_Tag) {
720      ScopedDecl *TagD = Pos->second.back();
721      Pos->second.back() = D;
722      Pos->second.push_back(TagD);
723    } else
724      Pos->second.push_back(D);
725  } else {
726    (*Map)[D->getDeclName()].push_back(D);
727  }
728}
729