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