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