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