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