ASTContext.cpp revision 829f20097e030229fd4c234b84948f53312eaf55 
1//===--- ASTContext.cpp - Context to hold long-lived AST nodes ------------===//
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 ASTContext interface.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/AST/ASTContext.h"
15#include "clang/AST/CharUnits.h"
16#include "clang/AST/DeclCXX.h"
17#include "clang/AST/DeclObjC.h"
18#include "clang/AST/DeclTemplate.h"
19#include "clang/AST/TypeLoc.h"
20#include "clang/AST/Expr.h"
21#include "clang/AST/ExprCXX.h"
22#include "clang/AST/ExternalASTSource.h"
23#include "clang/AST/ASTMutationListener.h"
24#include "clang/AST/RecordLayout.h"
25#include "clang/AST/Mangle.h"
26#include "clang/Basic/Builtins.h"
27#include "clang/Basic/SourceManager.h"
28#include "clang/Basic/TargetInfo.h"
29#include "llvm/ADT/SmallString.h"
30#include "llvm/ADT/StringExtras.h"
31#include "llvm/Support/MathExtras.h"
32#include "llvm/Support/raw_ostream.h"
33#include "CXXABI.h"
34#include <map>
35
36using namespace clang;
37
38unsigned ASTContext::NumImplicitDefaultConstructors;
39unsigned ASTContext::NumImplicitDefaultConstructorsDeclared;
40unsigned ASTContext::NumImplicitCopyConstructors;
41unsigned ASTContext::NumImplicitCopyConstructorsDeclared;
42unsigned ASTContext::NumImplicitMoveConstructors;
43unsigned ASTContext::NumImplicitMoveConstructorsDeclared;
44unsigned ASTContext::NumImplicitCopyAssignmentOperators;
45unsigned ASTContext::NumImplicitCopyAssignmentOperatorsDeclared;
46unsigned ASTContext::NumImplicitMoveAssignmentOperators;
47unsigned ASTContext::NumImplicitMoveAssignmentOperatorsDeclared;
48unsigned ASTContext::NumImplicitDestructors;
49unsigned ASTContext::NumImplicitDestructorsDeclared;
50
51enum FloatingRank {
52  FloatRank, DoubleRank, LongDoubleRank
53};
54
55void
56ASTContext::CanonicalTemplateTemplateParm::Profile(llvm::FoldingSetNodeID &ID,
57                                               TemplateTemplateParmDecl *Parm) {
58  ID.AddInteger(Parm->getDepth());
59  ID.AddInteger(Parm->getPosition());
60  ID.AddBoolean(Parm->isParameterPack());
61
62  TemplateParameterList *Params = Parm->getTemplateParameters();
63  ID.AddInteger(Params->size());
64  for (TemplateParameterList::const_iterator P = Params->begin(),
65                                          PEnd = Params->end();
66       P != PEnd; ++P) {
67    if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(*P)) {
68      ID.AddInteger(0);
69      ID.AddBoolean(TTP->isParameterPack());
70      continue;
71    }
72
73    if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
74      ID.AddInteger(1);
75      ID.AddBoolean(NTTP->isParameterPack());
76      ID.AddPointer(NTTP->getType().getAsOpaquePtr());
77      if (NTTP->isExpandedParameterPack()) {
78        ID.AddBoolean(true);
79        ID.AddInteger(NTTP->getNumExpansionTypes());
80        for (unsigned I = 0, N = NTTP->getNumExpansionTypes(); I != N; ++I)
81          ID.AddPointer(NTTP->getExpansionType(I).getAsOpaquePtr());
82      } else
83        ID.AddBoolean(false);
84      continue;
85    }
86
87    TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(*P);
88    ID.AddInteger(2);
89    Profile(ID, TTP);
90  }
91}
92
93TemplateTemplateParmDecl *
94ASTContext::getCanonicalTemplateTemplateParmDecl(
95                                          TemplateTemplateParmDecl *TTP) const {
96  // Check if we already have a canonical template template parameter.
97  llvm::FoldingSetNodeID ID;
98  CanonicalTemplateTemplateParm::Profile(ID, TTP);
99  void *InsertPos = 0;
100  CanonicalTemplateTemplateParm *Canonical
101    = CanonTemplateTemplateParms.FindNodeOrInsertPos(ID, InsertPos);
102  if (Canonical)
103    return Canonical->getParam();
104
105  // Build a canonical template parameter list.
106  TemplateParameterList *Params = TTP->getTemplateParameters();
107  llvm::SmallVector<NamedDecl *, 4> CanonParams;
108  CanonParams.reserve(Params->size());
109  for (TemplateParameterList::const_iterator P = Params->begin(),
110                                          PEnd = Params->end();
111       P != PEnd; ++P) {
112    if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(*P))
113      CanonParams.push_back(
114                  TemplateTypeParmDecl::Create(*this, getTranslationUnitDecl(),
115                                               SourceLocation(),
116                                               SourceLocation(),
117                                               TTP->getDepth(),
118                                               TTP->getIndex(), 0, false,
119                                               TTP->isParameterPack()));
120    else if (NonTypeTemplateParmDecl *NTTP
121             = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
122      QualType T = getCanonicalType(NTTP->getType());
123      TypeSourceInfo *TInfo = getTrivialTypeSourceInfo(T);
124      NonTypeTemplateParmDecl *Param;
125      if (NTTP->isExpandedParameterPack()) {
126        llvm::SmallVector<QualType, 2> ExpandedTypes;
127        llvm::SmallVector<TypeSourceInfo *, 2> ExpandedTInfos;
128        for (unsigned I = 0, N = NTTP->getNumExpansionTypes(); I != N; ++I) {
129          ExpandedTypes.push_back(getCanonicalType(NTTP->getExpansionType(I)));
130          ExpandedTInfos.push_back(
131                                getTrivialTypeSourceInfo(ExpandedTypes.back()));
132        }
133
134        Param = NonTypeTemplateParmDecl::Create(*this, getTranslationUnitDecl(),
135                                                SourceLocation(),
136                                                SourceLocation(),
137                                                NTTP->getDepth(),
138                                                NTTP->getPosition(), 0,
139                                                T,
140                                                TInfo,
141                                                ExpandedTypes.data(),
142                                                ExpandedTypes.size(),
143                                                ExpandedTInfos.data());
144      } else {
145        Param = NonTypeTemplateParmDecl::Create(*this, getTranslationUnitDecl(),
146                                                SourceLocation(),
147                                                SourceLocation(),
148                                                NTTP->getDepth(),
149                                                NTTP->getPosition(), 0,
150                                                T,
151                                                NTTP->isParameterPack(),
152                                                TInfo);
153      }
154      CanonParams.push_back(Param);
155
156    } else
157      CanonParams.push_back(getCanonicalTemplateTemplateParmDecl(
158                                           cast<TemplateTemplateParmDecl>(*P)));
159  }
160
161  TemplateTemplateParmDecl *CanonTTP
162    = TemplateTemplateParmDecl::Create(*this, getTranslationUnitDecl(),
163                                       SourceLocation(), TTP->getDepth(),
164                                       TTP->getPosition(),
165                                       TTP->isParameterPack(),
166                                       0,
167                         TemplateParameterList::Create(*this, SourceLocation(),
168                                                       SourceLocation(),
169                                                       CanonParams.data(),
170                                                       CanonParams.size(),
171                                                       SourceLocation()));
172
173  // Get the new insert position for the node we care about.
174  Canonical = CanonTemplateTemplateParms.FindNodeOrInsertPos(ID, InsertPos);
175  assert(Canonical == 0 && "Shouldn't be in the map!");
176  (void)Canonical;
177
178  // Create the canonical template template parameter entry.
179  Canonical = new (*this) CanonicalTemplateTemplateParm(CanonTTP);
180  CanonTemplateTemplateParms.InsertNode(Canonical, InsertPos);
181  return CanonTTP;
182}
183
184CXXABI *ASTContext::createCXXABI(const TargetInfo &T) {
185  if (!LangOpts.CPlusPlus) return 0;
186
187  switch (T.getCXXABI()) {
188  case CXXABI_ARM:
189    return CreateARMCXXABI(*this);
190  case CXXABI_Itanium:
191    return CreateItaniumCXXABI(*this);
192  case CXXABI_Microsoft:
193    return CreateMicrosoftCXXABI(*this);
194  }
195  return 0;
196}
197
198static const LangAS::Map &getAddressSpaceMap(const TargetInfo &T,
199                                             const LangOptions &LOpts) {
200  if (LOpts.FakeAddressSpaceMap) {
201    // The fake address space map must have a distinct entry for each
202    // language-specific address space.
203    static const unsigned FakeAddrSpaceMap[] = {
204      1, // opencl_global
205      2, // opencl_local
206      3  // opencl_constant
207    };
208    return FakeAddrSpaceMap;
209  } else {
210    return T.getAddressSpaceMap();
211  }
212}
213
214ASTContext::ASTContext(const LangOptions& LOpts, SourceManager &SM,
215                       const TargetInfo &t,
216                       IdentifierTable &idents, SelectorTable &sels,
217                       Builtin::Context &builtins,
218                       unsigned size_reserve) :
219  FunctionProtoTypes(this_()),
220  TemplateSpecializationTypes(this_()),
221  DependentTemplateSpecializationTypes(this_()),
222  GlobalNestedNameSpecifier(0), IsInt128Installed(false),
223  CFConstantStringTypeDecl(0), NSConstantStringTypeDecl(0),
224  ObjCFastEnumerationStateTypeDecl(0), FILEDecl(0),
225  jmp_bufDecl(0), sigjmp_bufDecl(0), BlockDescriptorType(0),
226  BlockDescriptorExtendedType(0), cudaConfigureCallDecl(0),
227  NullTypeSourceInfo(QualType()),
228  SourceMgr(SM), LangOpts(LOpts), ABI(createCXXABI(t)),
229  AddrSpaceMap(getAddressSpaceMap(t, LOpts)), Target(t),
230  Idents(idents), Selectors(sels),
231  BuiltinInfo(builtins),
232  DeclarationNames(*this),
233  ExternalSource(0), Listener(0), PrintingPolicy(LOpts),
234  LastSDM(0, 0),
235  UniqueBlockByRefTypeID(0) {
236  ObjCIdRedefinitionType = QualType();
237  ObjCClassRedefinitionType = QualType();
238  ObjCSelRedefinitionType = QualType();
239  if (size_reserve > 0) Types.reserve(size_reserve);
240  TUDecl = TranslationUnitDecl::Create(*this);
241  InitBuiltinTypes();
242}
243
244ASTContext::~ASTContext() {
245  // Release the DenseMaps associated with DeclContext objects.
246  // FIXME: Is this the ideal solution?
247  ReleaseDeclContextMaps();
248
249  // Call all of the deallocation functions.
250  for (unsigned I = 0, N = Deallocations.size(); I != N; ++I)
251    Deallocations[I].first(Deallocations[I].second);
252
253  // Release all of the memory associated with overridden C++ methods.
254  for (llvm::DenseMap<const CXXMethodDecl *, CXXMethodVector>::iterator
255         OM = OverriddenMethods.begin(), OMEnd = OverriddenMethods.end();
256       OM != OMEnd; ++OM)
257    OM->second.Destroy();
258
259  // ASTRecordLayout objects in ASTRecordLayouts must always be destroyed
260  // because they can contain DenseMaps.
261  for (llvm::DenseMap<const ObjCContainerDecl*,
262       const ASTRecordLayout*>::iterator
263       I = ObjCLayouts.begin(), E = ObjCLayouts.end(); I != E; )
264    // Increment in loop to prevent using deallocated memory.
265    if (ASTRecordLayout *R = const_cast<ASTRecordLayout*>((I++)->second))
266      R->Destroy(*this);
267
268  for (llvm::DenseMap<const RecordDecl*, const ASTRecordLayout*>::iterator
269       I = ASTRecordLayouts.begin(), E = ASTRecordLayouts.end(); I != E; ) {
270    // Increment in loop to prevent using deallocated memory.
271    if (ASTRecordLayout *R = const_cast<ASTRecordLayout*>((I++)->second))
272      R->Destroy(*this);
273  }
274
275  for (llvm::DenseMap<const Decl*, AttrVec*>::iterator A = DeclAttrs.begin(),
276                                                    AEnd = DeclAttrs.end();
277       A != AEnd; ++A)
278    A->second->~AttrVec();
279}
280
281void ASTContext::AddDeallocation(void (*Callback)(void*), void *Data) {
282  Deallocations.push_back(std::make_pair(Callback, Data));
283}
284
285void
286ASTContext::setExternalSource(llvm::OwningPtr<ExternalASTSource> &Source) {
287  ExternalSource.reset(Source.take());
288}
289
290void ASTContext::PrintStats() const {
291  fprintf(stderr, "*** AST Context Stats:\n");
292  fprintf(stderr, "  %d types total.\n", (int)Types.size());
293
294  unsigned counts[] = {
295#define TYPE(Name, Parent) 0,
296#define ABSTRACT_TYPE(Name, Parent)
297#include "clang/AST/TypeNodes.def"
298    0 // Extra
299  };
300
301  for (unsigned i = 0, e = Types.size(); i != e; ++i) {
302    Type *T = Types[i];
303    counts[(unsigned)T->getTypeClass()]++;
304  }
305
306  unsigned Idx = 0;
307  unsigned TotalBytes = 0;
308#define TYPE(Name, Parent)                                              \
309  if (counts[Idx])                                                      \
310    fprintf(stderr, "    %d %s types\n", (int)counts[Idx], #Name);      \
311  TotalBytes += counts[Idx] * sizeof(Name##Type);                       \
312  ++Idx;
313#define ABSTRACT_TYPE(Name, Parent)
314#include "clang/AST/TypeNodes.def"
315
316  fprintf(stderr, "Total bytes = %d\n", int(TotalBytes));
317
318  // Implicit special member functions.
319  fprintf(stderr, "  %u/%u implicit default constructors created\n",
320          NumImplicitDefaultConstructorsDeclared,
321          NumImplicitDefaultConstructors);
322  fprintf(stderr, "  %u/%u implicit copy constructors created\n",
323          NumImplicitCopyConstructorsDeclared,
324          NumImplicitCopyConstructors);
325  if (getLangOptions().CPlusPlus)
326    fprintf(stderr, "  %u/%u implicit move constructors created\n",
327            NumImplicitMoveConstructorsDeclared,
328            NumImplicitMoveConstructors);
329  fprintf(stderr, "  %u/%u implicit copy assignment operators created\n",
330          NumImplicitCopyAssignmentOperatorsDeclared,
331          NumImplicitCopyAssignmentOperators);
332  if (getLangOptions().CPlusPlus)
333    fprintf(stderr, "  %u/%u implicit move assignment operators created\n",
334            NumImplicitMoveAssignmentOperatorsDeclared,
335            NumImplicitMoveAssignmentOperators);
336  fprintf(stderr, "  %u/%u implicit destructors created\n",
337          NumImplicitDestructorsDeclared, NumImplicitDestructors);
338
339  if (ExternalSource.get()) {
340    fprintf(stderr, "\n");
341    ExternalSource->PrintStats();
342  }
343
344  BumpAlloc.PrintStats();
345}
346
347
348void ASTContext::InitBuiltinType(CanQualType &R, BuiltinType::Kind K) {
349  BuiltinType *Ty = new (*this, TypeAlignment) BuiltinType(K);
350  R = CanQualType::CreateUnsafe(QualType(Ty, 0));
351  Types.push_back(Ty);
352}
353
354void ASTContext::InitBuiltinTypes() {
355  assert(VoidTy.isNull() && "Context reinitialized?");
356
357  // C99 6.2.5p19.
358  InitBuiltinType(VoidTy,              BuiltinType::Void);
359
360  // C99 6.2.5p2.
361  InitBuiltinType(BoolTy,              BuiltinType::Bool);
362  // C99 6.2.5p3.
363  if (LangOpts.CharIsSigned)
364    InitBuiltinType(CharTy,            BuiltinType::Char_S);
365  else
366    InitBuiltinType(CharTy,            BuiltinType::Char_U);
367  // C99 6.2.5p4.
368  InitBuiltinType(SignedCharTy,        BuiltinType::SChar);
369  InitBuiltinType(ShortTy,             BuiltinType::Short);
370  InitBuiltinType(IntTy,               BuiltinType::Int);
371  InitBuiltinType(LongTy,              BuiltinType::Long);
372  InitBuiltinType(LongLongTy,          BuiltinType::LongLong);
373
374  // C99 6.2.5p6.
375  InitBuiltinType(UnsignedCharTy,      BuiltinType::UChar);
376  InitBuiltinType(UnsignedShortTy,     BuiltinType::UShort);
377  InitBuiltinType(UnsignedIntTy,       BuiltinType::UInt);
378  InitBuiltinType(UnsignedLongTy,      BuiltinType::ULong);
379  InitBuiltinType(UnsignedLongLongTy,  BuiltinType::ULongLong);
380
381  // C99 6.2.5p10.
382  InitBuiltinType(FloatTy,             BuiltinType::Float);
383  InitBuiltinType(DoubleTy,            BuiltinType::Double);
384  InitBuiltinType(LongDoubleTy,        BuiltinType::LongDouble);
385
386  // GNU extension, 128-bit integers.
387  InitBuiltinType(Int128Ty,            BuiltinType::Int128);
388  InitBuiltinType(UnsignedInt128Ty,    BuiltinType::UInt128);
389
390  if (LangOpts.CPlusPlus) { // C++ 3.9.1p5
391    if (TargetInfo::isTypeSigned(Target.getWCharType()))
392      InitBuiltinType(WCharTy,           BuiltinType::WChar_S);
393    else  // -fshort-wchar makes wchar_t be unsigned.
394      InitBuiltinType(WCharTy,           BuiltinType::WChar_U);
395  } else // C99
396    WCharTy = getFromTargetType(Target.getWCharType());
397
398  if (LangOpts.CPlusPlus) // C++0x 3.9.1p5, extension for C++
399    InitBuiltinType(Char16Ty,           BuiltinType::Char16);
400  else // C99
401    Char16Ty = getFromTargetType(Target.getChar16Type());
402
403  if (LangOpts.CPlusPlus) // C++0x 3.9.1p5, extension for C++
404    InitBuiltinType(Char32Ty,           BuiltinType::Char32);
405  else // C99
406    Char32Ty = getFromTargetType(Target.getChar32Type());
407
408  // Placeholder type for type-dependent expressions whose type is
409  // completely unknown. No code should ever check a type against
410  // DependentTy and users should never see it; however, it is here to
411  // help diagnose failures to properly check for type-dependent
412  // expressions.
413  InitBuiltinType(DependentTy,         BuiltinType::Dependent);
414
415  // Placeholder type for functions.
416  InitBuiltinType(OverloadTy,          BuiltinType::Overload);
417
418  // Placeholder type for bound members.
419  InitBuiltinType(BoundMemberTy,       BuiltinType::BoundMember);
420
421  // "any" type; useful for debugger-like clients.
422  InitBuiltinType(UnknownAnyTy,        BuiltinType::UnknownAny);
423
424  // C99 6.2.5p11.
425  FloatComplexTy      = getComplexType(FloatTy);
426  DoubleComplexTy     = getComplexType(DoubleTy);
427  LongDoubleComplexTy = getComplexType(LongDoubleTy);
428
429  BuiltinVaListType = QualType();
430
431  // "Builtin" typedefs set by Sema::ActOnTranslationUnitScope().
432  ObjCIdTypedefType = QualType();
433  ObjCClassTypedefType = QualType();
434  ObjCSelTypedefType = QualType();
435
436  // Builtin types for 'id', 'Class', and 'SEL'.
437  InitBuiltinType(ObjCBuiltinIdTy, BuiltinType::ObjCId);
438  InitBuiltinType(ObjCBuiltinClassTy, BuiltinType::ObjCClass);
439  InitBuiltinType(ObjCBuiltinSelTy, BuiltinType::ObjCSel);
440
441  ObjCConstantStringType = QualType();
442
443  // void * type
444  VoidPtrTy = getPointerType(VoidTy);
445
446  // nullptr type (C++0x 2.14.7)
447  InitBuiltinType(NullPtrTy,           BuiltinType::NullPtr);
448}
449
450Diagnostic &ASTContext::getDiagnostics() const {
451  return SourceMgr.getDiagnostics();
452}
453
454AttrVec& ASTContext::getDeclAttrs(const Decl *D) {
455  AttrVec *&Result = DeclAttrs[D];
456  if (!Result) {
457    void *Mem = Allocate(sizeof(AttrVec));
458    Result = new (Mem) AttrVec;
459  }
460
461  return *Result;
462}
463
464/// \brief Erase the attributes corresponding to the given declaration.
465void ASTContext::eraseDeclAttrs(const Decl *D) {
466  llvm::DenseMap<const Decl*, AttrVec*>::iterator Pos = DeclAttrs.find(D);
467  if (Pos != DeclAttrs.end()) {
468    Pos->second->~AttrVec();
469    DeclAttrs.erase(Pos);
470  }
471}
472
473MemberSpecializationInfo *
474ASTContext::getInstantiatedFromStaticDataMember(const VarDecl *Var) {
475  assert(Var->isStaticDataMember() && "Not a static data member");
476  llvm::DenseMap<const VarDecl *, MemberSpecializationInfo *>::iterator Pos
477    = InstantiatedFromStaticDataMember.find(Var);
478  if (Pos == InstantiatedFromStaticDataMember.end())
479    return 0;
480
481  return Pos->second;
482}
483
484void
485ASTContext::setInstantiatedFromStaticDataMember(VarDecl *Inst, VarDecl *Tmpl,
486                                                TemplateSpecializationKind TSK,
487                                          SourceLocation PointOfInstantiation) {
488  assert(Inst->isStaticDataMember() && "Not a static data member");
489  assert(Tmpl->isStaticDataMember() && "Not a static data member");
490  assert(!InstantiatedFromStaticDataMember[Inst] &&
491         "Already noted what static data member was instantiated from");
492  InstantiatedFromStaticDataMember[Inst]
493    = new (*this) MemberSpecializationInfo(Tmpl, TSK, PointOfInstantiation);
494}
495
496NamedDecl *
497ASTContext::getInstantiatedFromUsingDecl(UsingDecl *UUD) {
498  llvm::DenseMap<UsingDecl *, NamedDecl *>::const_iterator Pos
499    = InstantiatedFromUsingDecl.find(UUD);
500  if (Pos == InstantiatedFromUsingDecl.end())
501    return 0;
502
503  return Pos->second;
504}
505
506void
507ASTContext::setInstantiatedFromUsingDecl(UsingDecl *Inst, NamedDecl *Pattern) {
508  assert((isa<UsingDecl>(Pattern) ||
509          isa<UnresolvedUsingValueDecl>(Pattern) ||
510          isa<UnresolvedUsingTypenameDecl>(Pattern)) &&
511         "pattern decl is not a using decl");
512  assert(!InstantiatedFromUsingDecl[Inst] && "pattern already exists");
513  InstantiatedFromUsingDecl[Inst] = Pattern;
514}
515
516UsingShadowDecl *
517ASTContext::getInstantiatedFromUsingShadowDecl(UsingShadowDecl *Inst) {
518  llvm::DenseMap<UsingShadowDecl*, UsingShadowDecl*>::const_iterator Pos
519    = InstantiatedFromUsingShadowDecl.find(Inst);
520  if (Pos == InstantiatedFromUsingShadowDecl.end())
521    return 0;
522
523  return Pos->second;
524}
525
526void
527ASTContext::setInstantiatedFromUsingShadowDecl(UsingShadowDecl *Inst,
528                                               UsingShadowDecl *Pattern) {
529  assert(!InstantiatedFromUsingShadowDecl[Inst] && "pattern already exists");
530  InstantiatedFromUsingShadowDecl[Inst] = Pattern;
531}
532
533FieldDecl *ASTContext::getInstantiatedFromUnnamedFieldDecl(FieldDecl *Field) {
534  llvm::DenseMap<FieldDecl *, FieldDecl *>::iterator Pos
535    = InstantiatedFromUnnamedFieldDecl.find(Field);
536  if (Pos == InstantiatedFromUnnamedFieldDecl.end())
537    return 0;
538
539  return Pos->second;
540}
541
542void ASTContext::setInstantiatedFromUnnamedFieldDecl(FieldDecl *Inst,
543                                                     FieldDecl *Tmpl) {
544  assert(!Inst->getDeclName() && "Instantiated field decl is not unnamed");
545  assert(!Tmpl->getDeclName() && "Template field decl is not unnamed");
546  assert(!InstantiatedFromUnnamedFieldDecl[Inst] &&
547         "Already noted what unnamed field was instantiated from");
548
549  InstantiatedFromUnnamedFieldDecl[Inst] = Tmpl;
550}
551
552bool ASTContext::ZeroBitfieldFollowsNonBitfield(const FieldDecl *FD,
553                                    const FieldDecl *LastFD) const {
554  return (FD->isBitField() && LastFD && !LastFD->isBitField() &&
555          FD->getBitWidth()-> EvaluateAsInt(*this).getZExtValue() == 0);
556
557}
558
559bool ASTContext::ZeroBitfieldFollowsBitfield(const FieldDecl *FD,
560                                             const FieldDecl *LastFD) const {
561  return (FD->isBitField() && LastFD && LastFD->isBitField() &&
562          FD->getBitWidth()-> EvaluateAsInt(*this).getZExtValue() == 0 &&
563          LastFD->getBitWidth()-> EvaluateAsInt(*this).getZExtValue() != 0);
564
565}
566
567bool ASTContext::BitfieldFollowsBitfield(const FieldDecl *FD,
568                                         const FieldDecl *LastFD) const {
569  return (FD->isBitField() && LastFD && LastFD->isBitField() &&
570          FD->getBitWidth()-> EvaluateAsInt(*this).getZExtValue() &&
571          LastFD->getBitWidth()-> EvaluateAsInt(*this).getZExtValue());
572}
573
574bool ASTContext::NoneBitfieldFollowsBitfield(const FieldDecl *FD,
575                                         const FieldDecl *LastFD) const {
576  return (!FD->isBitField() && LastFD && LastFD->isBitField() &&
577          LastFD->getBitWidth()-> EvaluateAsInt(*this).getZExtValue());
578}
579
580bool ASTContext::BitfieldFollowsNoneBitfield(const FieldDecl *FD,
581                                             const FieldDecl *LastFD) const {
582  return (FD->isBitField() && LastFD && !LastFD->isBitField() &&
583          FD->getBitWidth()-> EvaluateAsInt(*this).getZExtValue());
584}
585
586ASTContext::overridden_cxx_method_iterator
587ASTContext::overridden_methods_begin(const CXXMethodDecl *Method) const {
588  llvm::DenseMap<const CXXMethodDecl *, CXXMethodVector>::const_iterator Pos
589    = OverriddenMethods.find(Method);
590  if (Pos == OverriddenMethods.end())
591    return 0;
592
593  return Pos->second.begin();
594}
595
596ASTContext::overridden_cxx_method_iterator
597ASTContext::overridden_methods_end(const CXXMethodDecl *Method) const {
598  llvm::DenseMap<const CXXMethodDecl *, CXXMethodVector>::const_iterator Pos
599    = OverriddenMethods.find(Method);
600  if (Pos == OverriddenMethods.end())
601    return 0;
602
603  return Pos->second.end();
604}
605
606unsigned
607ASTContext::overridden_methods_size(const CXXMethodDecl *Method) const {
608  llvm::DenseMap<const CXXMethodDecl *, CXXMethodVector>::const_iterator Pos
609    = OverriddenMethods.find(Method);
610  if (Pos == OverriddenMethods.end())
611    return 0;
612
613  return Pos->second.size();
614}
615
616void ASTContext::addOverriddenMethod(const CXXMethodDecl *Method,
617                                     const CXXMethodDecl *Overridden) {
618  OverriddenMethods[Method].push_back(Overridden);
619}
620
621//===----------------------------------------------------------------------===//
622//                         Type Sizing and Analysis
623//===----------------------------------------------------------------------===//
624
625/// getFloatTypeSemantics - Return the APFloat 'semantics' for the specified
626/// scalar floating point type.
627const llvm::fltSemantics &ASTContext::getFloatTypeSemantics(QualType T) const {
628  const BuiltinType *BT = T->getAs<BuiltinType>();
629  assert(BT && "Not a floating point type!");
630  switch (BT->getKind()) {
631  default: assert(0 && "Not a floating point type!");
632  case BuiltinType::Float:      return Target.getFloatFormat();
633  case BuiltinType::Double:     return Target.getDoubleFormat();
634  case BuiltinType::LongDouble: return Target.getLongDoubleFormat();
635  }
636}
637
638/// getDeclAlign - Return a conservative estimate of the alignment of the
639/// specified decl.  Note that bitfields do not have a valid alignment, so
640/// this method will assert on them.
641/// If @p RefAsPointee, references are treated like their underlying type
642/// (for alignof), else they're treated like pointers (for CodeGen).
643CharUnits ASTContext::getDeclAlign(const Decl *D, bool RefAsPointee) const {
644  unsigned Align = Target.getCharWidth();
645
646  bool UseAlignAttrOnly = false;
647  if (unsigned AlignFromAttr = D->getMaxAlignment()) {
648    Align = AlignFromAttr;
649
650    // __attribute__((aligned)) can increase or decrease alignment
651    // *except* on a struct or struct member, where it only increases
652    // alignment unless 'packed' is also specified.
653    //
654    // It is an error for [[align]] to decrease alignment, so we can
655    // ignore that possibility;  Sema should diagnose it.
656    if (isa<FieldDecl>(D)) {
657      UseAlignAttrOnly = D->hasAttr<PackedAttr>() ||
658        cast<FieldDecl>(D)->getParent()->hasAttr<PackedAttr>();
659    } else {
660      UseAlignAttrOnly = true;
661    }
662  }
663  else if (isa<FieldDecl>(D))
664      UseAlignAttrOnly =
665        D->hasAttr<PackedAttr>() ||
666        cast<FieldDecl>(D)->getParent()->hasAttr<PackedAttr>();
667
668  // If we're using the align attribute only, just ignore everything
669  // else about the declaration and its type.
670  if (UseAlignAttrOnly) {
671    // do nothing
672
673  } else if (const ValueDecl *VD = dyn_cast<ValueDecl>(D)) {
674    QualType T = VD->getType();
675    if (const ReferenceType* RT = T->getAs<ReferenceType>()) {
676      if (RefAsPointee)
677        T = RT->getPointeeType();
678      else
679        T = getPointerType(RT->getPointeeType());
680    }
681    if (!T->isIncompleteType() && !T->isFunctionType()) {
682      // Adjust alignments of declarations with array type by the
683      // large-array alignment on the target.
684      unsigned MinWidth = Target.getLargeArrayMinWidth();
685      const ArrayType *arrayType;
686      if (MinWidth && (arrayType = getAsArrayType(T))) {
687        if (isa<VariableArrayType>(arrayType))
688          Align = std::max(Align, Target.getLargeArrayAlign());
689        else if (isa<ConstantArrayType>(arrayType) &&
690                 MinWidth <= getTypeSize(cast<ConstantArrayType>(arrayType)))
691          Align = std::max(Align, Target.getLargeArrayAlign());
692
693        // Walk through any array types while we're at it.
694        T = getBaseElementType(arrayType);
695      }
696      Align = std::max(Align, getPreferredTypeAlign(T.getTypePtr()));
697    }
698
699    // Fields can be subject to extra alignment constraints, like if
700    // the field is packed, the struct is packed, or the struct has a
701    // a max-field-alignment constraint (#pragma pack).  So calculate
702    // the actual alignment of the field within the struct, and then
703    // (as we're expected to) constrain that by the alignment of the type.
704    if (const FieldDecl *field = dyn_cast<FieldDecl>(VD)) {
705      // So calculate the alignment of the field.
706      const ASTRecordLayout &layout = getASTRecordLayout(field->getParent());
707
708      // Start with the record's overall alignment.
709      unsigned fieldAlign = toBits(layout.getAlignment());
710
711      // Use the GCD of that and the offset within the record.
712      uint64_t offset = layout.getFieldOffset(field->getFieldIndex());
713      if (offset > 0) {
714        // Alignment is always a power of 2, so the GCD will be a power of 2,
715        // which means we get to do this crazy thing instead of Euclid's.
716        uint64_t lowBitOfOffset = offset & (~offset + 1);
717        if (lowBitOfOffset < fieldAlign)
718          fieldAlign = static_cast<unsigned>(lowBitOfOffset);
719      }
720
721      Align = std::min(Align, fieldAlign);
722    }
723  }
724
725  return toCharUnitsFromBits(Align);
726}
727
728std::pair<CharUnits, CharUnits>
729ASTContext::getTypeInfoInChars(const Type *T) const {
730  std::pair<uint64_t, unsigned> Info = getTypeInfo(T);
731  return std::make_pair(toCharUnitsFromBits(Info.first),
732                        toCharUnitsFromBits(Info.second));
733}
734
735std::pair<CharUnits, CharUnits>
736ASTContext::getTypeInfoInChars(QualType T) const {
737  return getTypeInfoInChars(T.getTypePtr());
738}
739
740/// getTypeSize - Return the size of the specified type, in bits.  This method
741/// does not work on incomplete types.
742///
743/// FIXME: Pointers into different addr spaces could have different sizes and
744/// alignment requirements: getPointerInfo should take an AddrSpace, this
745/// should take a QualType, &c.
746std::pair<uint64_t, unsigned>
747ASTContext::getTypeInfo(const Type *T) const {
748  uint64_t Width=0;
749  unsigned Align=8;
750  switch (T->getTypeClass()) {
751#define TYPE(Class, Base)
752#define ABSTRACT_TYPE(Class, Base)
753#define NON_CANONICAL_TYPE(Class, Base)
754#define DEPENDENT_TYPE(Class, Base) case Type::Class:
755#include "clang/AST/TypeNodes.def"
756    assert(false && "Should not see dependent types");
757    break;
758
759  case Type::FunctionNoProto:
760  case Type::FunctionProto:
761    // GCC extension: alignof(function) = 32 bits
762    Width = 0;
763    Align = 32;
764    break;
765
766  case Type::IncompleteArray:
767  case Type::VariableArray:
768    Width = 0;
769    Align = getTypeAlign(cast<ArrayType>(T)->getElementType());
770    break;
771
772  case Type::ConstantArray: {
773    const ConstantArrayType *CAT = cast<ConstantArrayType>(T);
774
775    std::pair<uint64_t, unsigned> EltInfo = getTypeInfo(CAT->getElementType());
776    Width = EltInfo.first*CAT->getSize().getZExtValue();
777    Align = EltInfo.second;
778    Width = llvm::RoundUpToAlignment(Width, Align);
779    break;
780  }
781  case Type::ExtVector:
782  case Type::Vector: {
783    const VectorType *VT = cast<VectorType>(T);
784    std::pair<uint64_t, unsigned> EltInfo = getTypeInfo(VT->getElementType());
785    Width = EltInfo.first*VT->getNumElements();
786    Align = Width;
787    // If the alignment is not a power of 2, round up to the next power of 2.
788    // This happens for non-power-of-2 length vectors.
789    if (Align & (Align-1)) {
790      Align = llvm::NextPowerOf2(Align);
791      Width = llvm::RoundUpToAlignment(Width, Align);
792    }
793    break;
794  }
795
796  case Type::Builtin:
797    switch (cast<BuiltinType>(T)->getKind()) {
798    default: assert(0 && "Unknown builtin type!");
799    case BuiltinType::Void:
800      // GCC extension: alignof(void) = 8 bits.
801      Width = 0;
802      Align = 8;
803      break;
804
805    case BuiltinType::Bool:
806      Width = Target.getBoolWidth();
807      Align = Target.getBoolAlign();
808      break;
809    case BuiltinType::Char_S:
810    case BuiltinType::Char_U:
811    case BuiltinType::UChar:
812    case BuiltinType::SChar:
813      Width = Target.getCharWidth();
814      Align = Target.getCharAlign();
815      break;
816    case BuiltinType::WChar_S:
817    case BuiltinType::WChar_U:
818      Width = Target.getWCharWidth();
819      Align = Target.getWCharAlign();
820      break;
821    case BuiltinType::Char16:
822      Width = Target.getChar16Width();
823      Align = Target.getChar16Align();
824      break;
825    case BuiltinType::Char32:
826      Width = Target.getChar32Width();
827      Align = Target.getChar32Align();
828      break;
829    case BuiltinType::UShort:
830    case BuiltinType::Short:
831      Width = Target.getShortWidth();
832      Align = Target.getShortAlign();
833      break;
834    case BuiltinType::UInt:
835    case BuiltinType::Int:
836      Width = Target.getIntWidth();
837      Align = Target.getIntAlign();
838      break;
839    case BuiltinType::ULong:
840    case BuiltinType::Long:
841      Width = Target.getLongWidth();
842      Align = Target.getLongAlign();
843      break;
844    case BuiltinType::ULongLong:
845    case BuiltinType::LongLong:
846      Width = Target.getLongLongWidth();
847      Align = Target.getLongLongAlign();
848      break;
849    case BuiltinType::Int128:
850    case BuiltinType::UInt128:
851      Width = 128;
852      Align = 128; // int128_t is 128-bit aligned on all targets.
853      break;
854    case BuiltinType::Float:
855      Width = Target.getFloatWidth();
856      Align = Target.getFloatAlign();
857      break;
858    case BuiltinType::Double:
859      Width = Target.getDoubleWidth();
860      Align = Target.getDoubleAlign();
861      break;
862    case BuiltinType::LongDouble:
863      Width = Target.getLongDoubleWidth();
864      Align = Target.getLongDoubleAlign();
865      break;
866    case BuiltinType::NullPtr:
867      Width = Target.getPointerWidth(0); // C++ 3.9.1p11: sizeof(nullptr_t)
868      Align = Target.getPointerAlign(0); //   == sizeof(void*)
869      break;
870    case BuiltinType::ObjCId:
871    case BuiltinType::ObjCClass:
872    case BuiltinType::ObjCSel:
873      Width = Target.getPointerWidth(0);
874      Align = Target.getPointerAlign(0);
875      break;
876    }
877    break;
878  case Type::ObjCObjectPointer:
879    Width = Target.getPointerWidth(0);
880    Align = Target.getPointerAlign(0);
881    break;
882  case Type::BlockPointer: {
883    unsigned AS = getTargetAddressSpace(
884        cast<BlockPointerType>(T)->getPointeeType());
885    Width = Target.getPointerWidth(AS);
886    Align = Target.getPointerAlign(AS);
887    break;
888  }
889  case Type::LValueReference:
890  case Type::RValueReference: {
891    // alignof and sizeof should never enter this code path here, so we go
892    // the pointer route.
893    unsigned AS = getTargetAddressSpace(
894        cast<ReferenceType>(T)->getPointeeType());
895    Width = Target.getPointerWidth(AS);
896    Align = Target.getPointerAlign(AS);
897    break;
898  }
899  case Type::Pointer: {
900    unsigned AS = getTargetAddressSpace(cast<PointerType>(T)->getPointeeType());
901    Width = Target.getPointerWidth(AS);
902    Align = Target.getPointerAlign(AS);
903    break;
904  }
905  case Type::MemberPointer: {
906    const MemberPointerType *MPT = cast<MemberPointerType>(T);
907    std::pair<uint64_t, unsigned> PtrDiffInfo =
908      getTypeInfo(getPointerDiffType());
909    Width = PtrDiffInfo.first * ABI->getMemberPointerSize(MPT);
910    Align = PtrDiffInfo.second;
911    break;
912  }
913  case Type::Complex: {
914    // Complex types have the same alignment as their elements, but twice the
915    // size.
916    std::pair<uint64_t, unsigned> EltInfo =
917      getTypeInfo(cast<ComplexType>(T)->getElementType());
918    Width = EltInfo.first*2;
919    Align = EltInfo.second;
920    break;
921  }
922  case Type::ObjCObject:
923    return getTypeInfo(cast<ObjCObjectType>(T)->getBaseType().getTypePtr());
924  case Type::ObjCInterface: {
925    const ObjCInterfaceType *ObjCI = cast<ObjCInterfaceType>(T);
926    const ASTRecordLayout &Layout = getASTObjCInterfaceLayout(ObjCI->getDecl());
927    Width = toBits(Layout.getSize());
928    Align = toBits(Layout.getAlignment());
929    break;
930  }
931  case Type::Record:
932  case Type::Enum: {
933    const TagType *TT = cast<TagType>(T);
934
935    if (TT->getDecl()->isInvalidDecl()) {
936      Width = 8;
937      Align = 8;
938      break;
939    }
940
941    if (const EnumType *ET = dyn_cast<EnumType>(TT))
942      return getTypeInfo(ET->getDecl()->getIntegerType());
943
944    const RecordType *RT = cast<RecordType>(TT);
945    const ASTRecordLayout &Layout = getASTRecordLayout(RT->getDecl());
946    Width = toBits(Layout.getSize());
947    Align = toBits(Layout.getAlignment());
948    break;
949  }
950
951  case Type::SubstTemplateTypeParm:
952    return getTypeInfo(cast<SubstTemplateTypeParmType>(T)->
953                       getReplacementType().getTypePtr());
954
955  case Type::Auto: {
956    const AutoType *A = cast<AutoType>(T);
957    assert(A->isDeduced() && "Cannot request the size of a dependent type");
958    return getTypeInfo(A->getDeducedType().getTypePtr());
959  }
960
961  case Type::Paren:
962    return getTypeInfo(cast<ParenType>(T)->getInnerType().getTypePtr());
963
964  case Type::Typedef: {
965    const TypedefNameDecl *Typedef = cast<TypedefType>(T)->getDecl();
966    std::pair<uint64_t, unsigned> Info
967      = getTypeInfo(Typedef->getUnderlyingType().getTypePtr());
968    // If the typedef has an aligned attribute on it, it overrides any computed
969    // alignment we have.  This violates the GCC documentation (which says that
970    // attribute(aligned) can only round up) but matches its implementation.
971    if (unsigned AttrAlign = Typedef->getMaxAlignment())
972      Align = AttrAlign;
973    else
974      Align = Info.second;
975    Width = Info.first;
976    break;
977  }
978
979  case Type::TypeOfExpr:
980    return getTypeInfo(cast<TypeOfExprType>(T)->getUnderlyingExpr()->getType()
981                         .getTypePtr());
982
983  case Type::TypeOf:
984    return getTypeInfo(cast<TypeOfType>(T)->getUnderlyingType().getTypePtr());
985
986  case Type::Decltype:
987    return getTypeInfo(cast<DecltypeType>(T)->getUnderlyingExpr()->getType()
988                        .getTypePtr());
989
990  case Type::UnaryTransform:
991    return getTypeInfo(cast<UnaryTransformType>(T)->getUnderlyingType());
992
993  case Type::Elaborated:
994    return getTypeInfo(cast<ElaboratedType>(T)->getNamedType().getTypePtr());
995
996  case Type::Attributed:
997    return getTypeInfo(
998                  cast<AttributedType>(T)->getEquivalentType().getTypePtr());
999
1000  case Type::TemplateSpecialization: {
1001    assert(getCanonicalType(T) != T &&
1002           "Cannot request the size of a dependent type");
1003    const TemplateSpecializationType *TST = cast<TemplateSpecializationType>(T);
1004    // A type alias template specialization may refer to a typedef with the
1005    // aligned attribute on it.
1006    if (TST->isTypeAlias())
1007      return getTypeInfo(TST->getAliasedType().getTypePtr());
1008    else
1009      return getTypeInfo(getCanonicalType(T));
1010  }
1011
1012  }
1013
1014  assert(Align && (Align & (Align-1)) == 0 && "Alignment must be power of 2");
1015  return std::make_pair(Width, Align);
1016}
1017
1018/// toCharUnitsFromBits - Convert a size in bits to a size in characters.
1019CharUnits ASTContext::toCharUnitsFromBits(int64_t BitSize) const {
1020  return CharUnits::fromQuantity(BitSize / getCharWidth());
1021}
1022
1023/// toBits - Convert a size in characters to a size in characters.
1024int64_t ASTContext::toBits(CharUnits CharSize) const {
1025  return CharSize.getQuantity() * getCharWidth();
1026}
1027
1028/// getTypeSizeInChars - Return the size of the specified type, in characters.
1029/// This method does not work on incomplete types.
1030CharUnits ASTContext::getTypeSizeInChars(QualType T) const {
1031  return toCharUnitsFromBits(getTypeSize(T));
1032}
1033CharUnits ASTContext::getTypeSizeInChars(const Type *T) const {
1034  return toCharUnitsFromBits(getTypeSize(T));
1035}
1036
1037/// getTypeAlignInChars - Return the ABI-specified alignment of a type, in
1038/// characters. This method does not work on incomplete types.
1039CharUnits ASTContext::getTypeAlignInChars(QualType T) const {
1040  return toCharUnitsFromBits(getTypeAlign(T));
1041}
1042CharUnits ASTContext::getTypeAlignInChars(const Type *T) const {
1043  return toCharUnitsFromBits(getTypeAlign(T));
1044}
1045
1046/// getPreferredTypeAlign - Return the "preferred" alignment of the specified
1047/// type for the current target in bits.  This can be different than the ABI
1048/// alignment in cases where it is beneficial for performance to overalign
1049/// a data type.
1050unsigned ASTContext::getPreferredTypeAlign(const Type *T) const {
1051  unsigned ABIAlign = getTypeAlign(T);
1052
1053  // Double and long long should be naturally aligned if possible.
1054  if (const ComplexType* CT = T->getAs<ComplexType>())
1055    T = CT->getElementType().getTypePtr();
1056  if (T->isSpecificBuiltinType(BuiltinType::Double) ||
1057      T->isSpecificBuiltinType(BuiltinType::LongLong))
1058    return std::max(ABIAlign, (unsigned)getTypeSize(T));
1059
1060  return ABIAlign;
1061}
1062
1063/// ShallowCollectObjCIvars -
1064/// Collect all ivars, including those synthesized, in the current class.
1065///
1066void ASTContext::ShallowCollectObjCIvars(const ObjCInterfaceDecl *OI,
1067                            llvm::SmallVectorImpl<ObjCIvarDecl*> &Ivars) const {
1068  // FIXME. This need be removed but there are two many places which
1069  // assume const-ness of ObjCInterfaceDecl
1070  ObjCInterfaceDecl *IDecl = const_cast<ObjCInterfaceDecl *>(OI);
1071  for (ObjCIvarDecl *Iv = IDecl->all_declared_ivar_begin(); Iv;
1072        Iv= Iv->getNextIvar())
1073    Ivars.push_back(Iv);
1074}
1075
1076/// DeepCollectObjCIvars -
1077/// This routine first collects all declared, but not synthesized, ivars in
1078/// super class and then collects all ivars, including those synthesized for
1079/// current class. This routine is used for implementation of current class
1080/// when all ivars, declared and synthesized are known.
1081///
1082void ASTContext::DeepCollectObjCIvars(const ObjCInterfaceDecl *OI,
1083                                      bool leafClass,
1084                            llvm::SmallVectorImpl<ObjCIvarDecl*> &Ivars) const {
1085  if (const ObjCInterfaceDecl *SuperClass = OI->getSuperClass())
1086    DeepCollectObjCIvars(SuperClass, false, Ivars);
1087  if (!leafClass) {
1088    for (ObjCInterfaceDecl::ivar_iterator I = OI->ivar_begin(),
1089         E = OI->ivar_end(); I != E; ++I)
1090      Ivars.push_back(*I);
1091  }
1092  else
1093    ShallowCollectObjCIvars(OI, Ivars);
1094}
1095
1096/// CollectInheritedProtocols - Collect all protocols in current class and
1097/// those inherited by it.
1098void ASTContext::CollectInheritedProtocols(const Decl *CDecl,
1099                          llvm::SmallPtrSet<ObjCProtocolDecl*, 8> &Protocols) {
1100  if (const ObjCInterfaceDecl *OI = dyn_cast<ObjCInterfaceDecl>(CDecl)) {
1101    // We can use protocol_iterator here instead of
1102    // all_referenced_protocol_iterator since we are walking all categories.
1103    for (ObjCInterfaceDecl::all_protocol_iterator P = OI->all_referenced_protocol_begin(),
1104         PE = OI->all_referenced_protocol_end(); P != PE; ++P) {
1105      ObjCProtocolDecl *Proto = (*P);
1106      Protocols.insert(Proto);
1107      for (ObjCProtocolDecl::protocol_iterator P = Proto->protocol_begin(),
1108           PE = Proto->protocol_end(); P != PE; ++P) {
1109        Protocols.insert(*P);
1110        CollectInheritedProtocols(*P, Protocols);
1111      }
1112    }
1113
1114    // Categories of this Interface.
1115    for (const ObjCCategoryDecl *CDeclChain = OI->getCategoryList();
1116         CDeclChain; CDeclChain = CDeclChain->getNextClassCategory())
1117      CollectInheritedProtocols(CDeclChain, Protocols);
1118    if (ObjCInterfaceDecl *SD = OI->getSuperClass())
1119      while (SD) {
1120        CollectInheritedProtocols(SD, Protocols);
1121        SD = SD->getSuperClass();
1122      }
1123  } else if (const ObjCCategoryDecl *OC = dyn_cast<ObjCCategoryDecl>(CDecl)) {
1124    for (ObjCCategoryDecl::protocol_iterator P = OC->protocol_begin(),
1125         PE = OC->protocol_end(); P != PE; ++P) {
1126      ObjCProtocolDecl *Proto = (*P);
1127      Protocols.insert(Proto);
1128      for (ObjCProtocolDecl::protocol_iterator P = Proto->protocol_begin(),
1129           PE = Proto->protocol_end(); P != PE; ++P)
1130        CollectInheritedProtocols(*P, Protocols);
1131    }
1132  } else if (const ObjCProtocolDecl *OP = dyn_cast<ObjCProtocolDecl>(CDecl)) {
1133    for (ObjCProtocolDecl::protocol_iterator P = OP->protocol_begin(),
1134         PE = OP->protocol_end(); P != PE; ++P) {
1135      ObjCProtocolDecl *Proto = (*P);
1136      Protocols.insert(Proto);
1137      for (ObjCProtocolDecl::protocol_iterator P = Proto->protocol_begin(),
1138           PE = Proto->protocol_end(); P != PE; ++P)
1139        CollectInheritedProtocols(*P, Protocols);
1140    }
1141  }
1142}
1143
1144unsigned ASTContext::CountNonClassIvars(const ObjCInterfaceDecl *OI) const {
1145  unsigned count = 0;
1146  // Count ivars declared in class extension.
1147  for (const ObjCCategoryDecl *CDecl = OI->getFirstClassExtension(); CDecl;
1148       CDecl = CDecl->getNextClassExtension())
1149    count += CDecl->ivar_size();
1150
1151  // Count ivar defined in this class's implementation.  This
1152  // includes synthesized ivars.
1153  if (ObjCImplementationDecl *ImplDecl = OI->getImplementation())
1154    count += ImplDecl->ivar_size();
1155
1156  return count;
1157}
1158
1159/// \brief Get the implementation of ObjCInterfaceDecl,or NULL if none exists.
1160ObjCImplementationDecl *ASTContext::getObjCImplementation(ObjCInterfaceDecl *D) {
1161  llvm::DenseMap<ObjCContainerDecl*, ObjCImplDecl*>::iterator
1162    I = ObjCImpls.find(D);
1163  if (I != ObjCImpls.end())
1164    return cast<ObjCImplementationDecl>(I->second);
1165  return 0;
1166}
1167/// \brief Get the implementation of ObjCCategoryDecl, or NULL if none exists.
1168ObjCCategoryImplDecl *ASTContext::getObjCImplementation(ObjCCategoryDecl *D) {
1169  llvm::DenseMap<ObjCContainerDecl*, ObjCImplDecl*>::iterator
1170    I = ObjCImpls.find(D);
1171  if (I != ObjCImpls.end())
1172    return cast<ObjCCategoryImplDecl>(I->second);
1173  return 0;
1174}
1175
1176/// \brief Set the implementation of ObjCInterfaceDecl.
1177void ASTContext::setObjCImplementation(ObjCInterfaceDecl *IFaceD,
1178                           ObjCImplementationDecl *ImplD) {
1179  assert(IFaceD && ImplD && "Passed null params");
1180  ObjCImpls[IFaceD] = ImplD;
1181}
1182/// \brief Set the implementation of ObjCCategoryDecl.
1183void ASTContext::setObjCImplementation(ObjCCategoryDecl *CatD,
1184                           ObjCCategoryImplDecl *ImplD) {
1185  assert(CatD && ImplD && "Passed null params");
1186  ObjCImpls[CatD] = ImplD;
1187}
1188
1189/// \brief Get the copy initialization expression of VarDecl,or NULL if
1190/// none exists.
1191Expr *ASTContext::getBlockVarCopyInits(const VarDecl*VD) {
1192  assert(VD && "Passed null params");
1193  assert(VD->hasAttr<BlocksAttr>() &&
1194         "getBlockVarCopyInits - not __block var");
1195  llvm::DenseMap<const VarDecl*, Expr*>::iterator
1196    I = BlockVarCopyInits.find(VD);
1197  return (I != BlockVarCopyInits.end()) ? cast<Expr>(I->second) : 0;
1198}
1199
1200/// \brief Set the copy inialization expression of a block var decl.
1201void ASTContext::setBlockVarCopyInits(VarDecl*VD, Expr* Init) {
1202  assert(VD && Init && "Passed null params");
1203  assert(VD->hasAttr<BlocksAttr>() &&
1204         "setBlockVarCopyInits - not __block var");
1205  BlockVarCopyInits[VD] = Init;
1206}
1207
1208/// \brief Allocate an uninitialized TypeSourceInfo.
1209///
1210/// The caller should initialize the memory held by TypeSourceInfo using
1211/// the TypeLoc wrappers.
1212///
1213/// \param T the type that will be the basis for type source info. This type
1214/// should refer to how the declarator was written in source code, not to
1215/// what type semantic analysis resolved the declarator to.
1216TypeSourceInfo *ASTContext::CreateTypeSourceInfo(QualType T,
1217                                                 unsigned DataSize) const {
1218  if (!DataSize)
1219    DataSize = TypeLoc::getFullDataSizeForType(T);
1220  else
1221    assert(DataSize == TypeLoc::getFullDataSizeForType(T) &&
1222           "incorrect data size provided to CreateTypeSourceInfo!");
1223
1224  TypeSourceInfo *TInfo =
1225    (TypeSourceInfo*)BumpAlloc.Allocate(sizeof(TypeSourceInfo) + DataSize, 8);
1226  new (TInfo) TypeSourceInfo(T);
1227  return TInfo;
1228}
1229
1230TypeSourceInfo *ASTContext::getTrivialTypeSourceInfo(QualType T,
1231                                                     SourceLocation L) const {
1232  TypeSourceInfo *DI = CreateTypeSourceInfo(T);
1233  DI->getTypeLoc().initialize(const_cast<ASTContext &>(*this), L);
1234  return DI;
1235}
1236
1237const ASTRecordLayout &
1238ASTContext::getASTObjCInterfaceLayout(const ObjCInterfaceDecl *D) const {
1239  return getObjCLayout(D, 0);
1240}
1241
1242const ASTRecordLayout &
1243ASTContext::getASTObjCImplementationLayout(
1244                                        const ObjCImplementationDecl *D) const {
1245  return getObjCLayout(D->getClassInterface(), D);
1246}
1247
1248//===----------------------------------------------------------------------===//
1249//                   Type creation/memoization methods
1250//===----------------------------------------------------------------------===//
1251
1252QualType
1253ASTContext::getExtQualType(const Type *baseType, Qualifiers quals) const {
1254  unsigned fastQuals = quals.getFastQualifiers();
1255  quals.removeFastQualifiers();
1256
1257  // Check if we've already instantiated this type.
1258  llvm::FoldingSetNodeID ID;
1259  ExtQuals::Profile(ID, baseType, quals);
1260  void *insertPos = 0;
1261  if (ExtQuals *eq = ExtQualNodes.FindNodeOrInsertPos(ID, insertPos)) {
1262    assert(eq->getQualifiers() == quals);
1263    return QualType(eq, fastQuals);
1264  }
1265
1266  // If the base type is not canonical, make the appropriate canonical type.
1267  QualType canon;
1268  if (!baseType->isCanonicalUnqualified()) {
1269    SplitQualType canonSplit = baseType->getCanonicalTypeInternal().split();
1270    canonSplit.second.addConsistentQualifiers(quals);
1271    canon = getExtQualType(canonSplit.first, canonSplit.second);
1272
1273    // Re-find the insert position.
1274    (void) ExtQualNodes.FindNodeOrInsertPos(ID, insertPos);
1275  }
1276
1277  ExtQuals *eq = new (*this, TypeAlignment) ExtQuals(baseType, canon, quals);
1278  ExtQualNodes.InsertNode(eq, insertPos);
1279  return QualType(eq, fastQuals);
1280}
1281
1282QualType
1283ASTContext::getAddrSpaceQualType(QualType T, unsigned AddressSpace) const {
1284  QualType CanT = getCanonicalType(T);
1285  if (CanT.getAddressSpace() == AddressSpace)
1286    return T;
1287
1288  // If we are composing extended qualifiers together, merge together
1289  // into one ExtQuals node.
1290  QualifierCollector Quals;
1291  const Type *TypeNode = Quals.strip(T);
1292
1293  // If this type already has an address space specified, it cannot get
1294  // another one.
1295  assert(!Quals.hasAddressSpace() &&
1296         "Type cannot be in multiple addr spaces!");
1297  Quals.addAddressSpace(AddressSpace);
1298
1299  return getExtQualType(TypeNode, Quals);
1300}
1301
1302QualType ASTContext::getObjCGCQualType(QualType T,
1303                                       Qualifiers::GC GCAttr) const {
1304  QualType CanT = getCanonicalType(T);
1305  if (CanT.getObjCGCAttr() == GCAttr)
1306    return T;
1307
1308  if (const PointerType *ptr = T->getAs<PointerType>()) {
1309    QualType Pointee = ptr->getPointeeType();
1310    if (Pointee->isAnyPointerType()) {
1311      QualType ResultType = getObjCGCQualType(Pointee, GCAttr);
1312      return getPointerType(ResultType);
1313    }
1314  }
1315
1316  // If we are composing extended qualifiers together, merge together
1317  // into one ExtQuals node.
1318  QualifierCollector Quals;
1319  const Type *TypeNode = Quals.strip(T);
1320
1321  // If this type already has an ObjCGC specified, it cannot get
1322  // another one.
1323  assert(!Quals.hasObjCGCAttr() &&
1324         "Type cannot have multiple ObjCGCs!");
1325  Quals.addObjCGCAttr(GCAttr);
1326
1327  return getExtQualType(TypeNode, Quals);
1328}
1329
1330const FunctionType *ASTContext::adjustFunctionType(const FunctionType *T,
1331                                                   FunctionType::ExtInfo Info) {
1332  if (T->getExtInfo() == Info)
1333    return T;
1334
1335  QualType Result;
1336  if (const FunctionNoProtoType *FNPT = dyn_cast<FunctionNoProtoType>(T)) {
1337    Result = getFunctionNoProtoType(FNPT->getResultType(), Info);
1338  } else {
1339    const FunctionProtoType *FPT = cast<FunctionProtoType>(T);
1340    FunctionProtoType::ExtProtoInfo EPI = FPT->getExtProtoInfo();
1341    EPI.ExtInfo = Info;
1342    Result = getFunctionType(FPT->getResultType(), FPT->arg_type_begin(),
1343                             FPT->getNumArgs(), EPI);
1344  }
1345
1346  return cast<FunctionType>(Result.getTypePtr());
1347}
1348
1349/// getComplexType - Return the uniqued reference to the type for a complex
1350/// number with the specified element type.
1351QualType ASTContext::getComplexType(QualType T) const {
1352  // Unique pointers, to guarantee there is only one pointer of a particular
1353  // structure.
1354  llvm::FoldingSetNodeID ID;
1355  ComplexType::Profile(ID, T);
1356
1357  void *InsertPos = 0;
1358  if (ComplexType *CT = ComplexTypes.FindNodeOrInsertPos(ID, InsertPos))
1359    return QualType(CT, 0);
1360
1361  // If the pointee type isn't canonical, this won't be a canonical type either,
1362  // so fill in the canonical type field.
1363  QualType Canonical;
1364  if (!T.isCanonical()) {
1365    Canonical = getComplexType(getCanonicalType(T));
1366
1367    // Get the new insert position for the node we care about.
1368    ComplexType *NewIP = ComplexTypes.FindNodeOrInsertPos(ID, InsertPos);
1369    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1370  }
1371  ComplexType *New = new (*this, TypeAlignment) ComplexType(T, Canonical);
1372  Types.push_back(New);
1373  ComplexTypes.InsertNode(New, InsertPos);
1374  return QualType(New, 0);
1375}
1376
1377/// getPointerType - Return the uniqued reference to the type for a pointer to
1378/// the specified type.
1379QualType ASTContext::getPointerType(QualType T) const {
1380  // Unique pointers, to guarantee there is only one pointer of a particular
1381  // structure.
1382  llvm::FoldingSetNodeID ID;
1383  PointerType::Profile(ID, T);
1384
1385  void *InsertPos = 0;
1386  if (PointerType *PT = PointerTypes.FindNodeOrInsertPos(ID, InsertPos))
1387    return QualType(PT, 0);
1388
1389  // If the pointee type isn't canonical, this won't be a canonical type either,
1390  // so fill in the canonical type field.
1391  QualType Canonical;
1392  if (!T.isCanonical()) {
1393    Canonical = getPointerType(getCanonicalType(T));
1394
1395    // Get the new insert position for the node we care about.
1396    PointerType *NewIP = PointerTypes.FindNodeOrInsertPos(ID, InsertPos);
1397    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1398  }
1399  PointerType *New = new (*this, TypeAlignment) PointerType(T, Canonical);
1400  Types.push_back(New);
1401  PointerTypes.InsertNode(New, InsertPos);
1402  return QualType(New, 0);
1403}
1404
1405/// getBlockPointerType - Return the uniqued reference to the type for
1406/// a pointer to the specified block.
1407QualType ASTContext::getBlockPointerType(QualType T) const {
1408  assert(T->isFunctionType() && "block of function types only");
1409  // Unique pointers, to guarantee there is only one block of a particular
1410  // structure.
1411  llvm::FoldingSetNodeID ID;
1412  BlockPointerType::Profile(ID, T);
1413
1414  void *InsertPos = 0;
1415  if (BlockPointerType *PT =
1416        BlockPointerTypes.FindNodeOrInsertPos(ID, InsertPos))
1417    return QualType(PT, 0);
1418
1419  // If the block pointee type isn't canonical, this won't be a canonical
1420  // type either so fill in the canonical type field.
1421  QualType Canonical;
1422  if (!T.isCanonical()) {
1423    Canonical = getBlockPointerType(getCanonicalType(T));
1424
1425    // Get the new insert position for the node we care about.
1426    BlockPointerType *NewIP =
1427      BlockPointerTypes.FindNodeOrInsertPos(ID, InsertPos);
1428    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1429  }
1430  BlockPointerType *New
1431    = new (*this, TypeAlignment) BlockPointerType(T, Canonical);
1432  Types.push_back(New);
1433  BlockPointerTypes.InsertNode(New, InsertPos);
1434  return QualType(New, 0);
1435}
1436
1437/// getLValueReferenceType - Return the uniqued reference to the type for an
1438/// lvalue reference to the specified type.
1439QualType
1440ASTContext::getLValueReferenceType(QualType T, bool SpelledAsLValue) const {
1441  assert(getCanonicalType(T) != OverloadTy &&
1442         "Unresolved overloaded function type");
1443
1444  // Unique pointers, to guarantee there is only one pointer of a particular
1445  // structure.
1446  llvm::FoldingSetNodeID ID;
1447  ReferenceType::Profile(ID, T, SpelledAsLValue);
1448
1449  void *InsertPos = 0;
1450  if (LValueReferenceType *RT =
1451        LValueReferenceTypes.FindNodeOrInsertPos(ID, InsertPos))
1452    return QualType(RT, 0);
1453
1454  const ReferenceType *InnerRef = T->getAs<ReferenceType>();
1455
1456  // If the referencee type isn't canonical, this won't be a canonical type
1457  // either, so fill in the canonical type field.
1458  QualType Canonical;
1459  if (!SpelledAsLValue || InnerRef || !T.isCanonical()) {
1460    QualType PointeeType = (InnerRef ? InnerRef->getPointeeType() : T);
1461    Canonical = getLValueReferenceType(getCanonicalType(PointeeType));
1462
1463    // Get the new insert position for the node we care about.
1464    LValueReferenceType *NewIP =
1465      LValueReferenceTypes.FindNodeOrInsertPos(ID, InsertPos);
1466    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1467  }
1468
1469  LValueReferenceType *New
1470    = new (*this, TypeAlignment) LValueReferenceType(T, Canonical,
1471                                                     SpelledAsLValue);
1472  Types.push_back(New);
1473  LValueReferenceTypes.InsertNode(New, InsertPos);
1474
1475  return QualType(New, 0);
1476}
1477
1478/// getRValueReferenceType - Return the uniqued reference to the type for an
1479/// rvalue reference to the specified type.
1480QualType ASTContext::getRValueReferenceType(QualType T) const {
1481  // Unique pointers, to guarantee there is only one pointer of a particular
1482  // structure.
1483  llvm::FoldingSetNodeID ID;
1484  ReferenceType::Profile(ID, T, false);
1485
1486  void *InsertPos = 0;
1487  if (RValueReferenceType *RT =
1488        RValueReferenceTypes.FindNodeOrInsertPos(ID, InsertPos))
1489    return QualType(RT, 0);
1490
1491  const ReferenceType *InnerRef = T->getAs<ReferenceType>();
1492
1493  // If the referencee type isn't canonical, this won't be a canonical type
1494  // either, so fill in the canonical type field.
1495  QualType Canonical;
1496  if (InnerRef || !T.isCanonical()) {
1497    QualType PointeeType = (InnerRef ? InnerRef->getPointeeType() : T);
1498    Canonical = getRValueReferenceType(getCanonicalType(PointeeType));
1499
1500    // Get the new insert position for the node we care about.
1501    RValueReferenceType *NewIP =
1502      RValueReferenceTypes.FindNodeOrInsertPos(ID, InsertPos);
1503    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1504  }
1505
1506  RValueReferenceType *New
1507    = new (*this, TypeAlignment) RValueReferenceType(T, Canonical);
1508  Types.push_back(New);
1509  RValueReferenceTypes.InsertNode(New, InsertPos);
1510  return QualType(New, 0);
1511}
1512
1513/// getMemberPointerType - Return the uniqued reference to the type for a
1514/// member pointer to the specified type, in the specified class.
1515QualType ASTContext::getMemberPointerType(QualType T, const Type *Cls) const {
1516  // Unique pointers, to guarantee there is only one pointer of a particular
1517  // structure.
1518  llvm::FoldingSetNodeID ID;
1519  MemberPointerType::Profile(ID, T, Cls);
1520
1521  void *InsertPos = 0;
1522  if (MemberPointerType *PT =
1523      MemberPointerTypes.FindNodeOrInsertPos(ID, InsertPos))
1524    return QualType(PT, 0);
1525
1526  // If the pointee or class type isn't canonical, this won't be a canonical
1527  // type either, so fill in the canonical type field.
1528  QualType Canonical;
1529  if (!T.isCanonical() || !Cls->isCanonicalUnqualified()) {
1530    Canonical = getMemberPointerType(getCanonicalType(T),getCanonicalType(Cls));
1531
1532    // Get the new insert position for the node we care about.
1533    MemberPointerType *NewIP =
1534      MemberPointerTypes.FindNodeOrInsertPos(ID, InsertPos);
1535    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1536  }
1537  MemberPointerType *New
1538    = new (*this, TypeAlignment) MemberPointerType(T, Cls, Canonical);
1539  Types.push_back(New);
1540  MemberPointerTypes.InsertNode(New, InsertPos);
1541  return QualType(New, 0);
1542}
1543
1544/// getConstantArrayType - Return the unique reference to the type for an
1545/// array of the specified element type.
1546QualType ASTContext::getConstantArrayType(QualType EltTy,
1547                                          const llvm::APInt &ArySizeIn,
1548                                          ArrayType::ArraySizeModifier ASM,
1549                                          unsigned IndexTypeQuals) const {
1550  assert((EltTy->isDependentType() ||
1551          EltTy->isIncompleteType() || EltTy->isConstantSizeType()) &&
1552         "Constant array of VLAs is illegal!");
1553
1554  // Convert the array size into a canonical width matching the pointer size for
1555  // the target.
1556  llvm::APInt ArySize(ArySizeIn);
1557  ArySize =
1558    ArySize.zextOrTrunc(Target.getPointerWidth(getTargetAddressSpace(EltTy)));
1559
1560  llvm::FoldingSetNodeID ID;
1561  ConstantArrayType::Profile(ID, EltTy, ArySize, ASM, IndexTypeQuals);
1562
1563  void *InsertPos = 0;
1564  if (ConstantArrayType *ATP =
1565      ConstantArrayTypes.FindNodeOrInsertPos(ID, InsertPos))
1566    return QualType(ATP, 0);
1567
1568  // If the element type isn't canonical or has qualifiers, this won't
1569  // be a canonical type either, so fill in the canonical type field.
1570  QualType Canon;
1571  if (!EltTy.isCanonical() || EltTy.hasLocalQualifiers()) {
1572    SplitQualType canonSplit = getCanonicalType(EltTy).split();
1573    Canon = getConstantArrayType(QualType(canonSplit.first, 0), ArySize,
1574                                 ASM, IndexTypeQuals);
1575    Canon = getQualifiedType(Canon, canonSplit.second);
1576
1577    // Get the new insert position for the node we care about.
1578    ConstantArrayType *NewIP =
1579      ConstantArrayTypes.FindNodeOrInsertPos(ID, InsertPos);
1580    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1581  }
1582
1583  ConstantArrayType *New = new(*this,TypeAlignment)
1584    ConstantArrayType(EltTy, Canon, ArySize, ASM, IndexTypeQuals);
1585  ConstantArrayTypes.InsertNode(New, InsertPos);
1586  Types.push_back(New);
1587  return QualType(New, 0);
1588}
1589
1590/// getVariableArrayDecayedType - Turns the given type, which may be
1591/// variably-modified, into the corresponding type with all the known
1592/// sizes replaced with [*].
1593QualType ASTContext::getVariableArrayDecayedType(QualType type) const {
1594  // Vastly most common case.
1595  if (!type->isVariablyModifiedType()) return type;
1596
1597  QualType result;
1598
1599  SplitQualType split = type.getSplitDesugaredType();
1600  const Type *ty = split.first;
1601  switch (ty->getTypeClass()) {
1602#define TYPE(Class, Base)
1603#define ABSTRACT_TYPE(Class, Base)
1604#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
1605#include "clang/AST/TypeNodes.def"
1606    llvm_unreachable("didn't desugar past all non-canonical types?");
1607
1608  // These types should never be variably-modified.
1609  case Type::Builtin:
1610  case Type::Complex:
1611  case Type::Vector:
1612  case Type::ExtVector:
1613  case Type::DependentSizedExtVector:
1614  case Type::ObjCObject:
1615  case Type::ObjCInterface:
1616  case Type::ObjCObjectPointer:
1617  case Type::Record:
1618  case Type::Enum:
1619  case Type::UnresolvedUsing:
1620  case Type::TypeOfExpr:
1621  case Type::TypeOf:
1622  case Type::Decltype:
1623  case Type::UnaryTransform:
1624  case Type::DependentName:
1625  case Type::InjectedClassName:
1626  case Type::TemplateSpecialization:
1627  case Type::DependentTemplateSpecialization:
1628  case Type::TemplateTypeParm:
1629  case Type::SubstTemplateTypeParmPack:
1630  case Type::Auto:
1631  case Type::PackExpansion:
1632    llvm_unreachable("type should never be variably-modified");
1633
1634  // These types can be variably-modified but should never need to
1635  // further decay.
1636  case Type::FunctionNoProto:
1637  case Type::FunctionProto:
1638  case Type::BlockPointer:
1639  case Type::MemberPointer:
1640    return type;
1641
1642  // These types can be variably-modified.  All these modifications
1643  // preserve structure except as noted by comments.
1644  // TODO: if we ever care about optimizing VLAs, there are no-op
1645  // optimizations available here.
1646  case Type::Pointer:
1647    result = getPointerType(getVariableArrayDecayedType(
1648                              cast<PointerType>(ty)->getPointeeType()));
1649    break;
1650
1651  case Type::LValueReference: {
1652    const LValueReferenceType *lv = cast<LValueReferenceType>(ty);
1653    result = getLValueReferenceType(
1654                 getVariableArrayDecayedType(lv->getPointeeType()),
1655                                    lv->isSpelledAsLValue());
1656    break;
1657  }
1658
1659  case Type::RValueReference: {
1660    const RValueReferenceType *lv = cast<RValueReferenceType>(ty);
1661    result = getRValueReferenceType(
1662                 getVariableArrayDecayedType(lv->getPointeeType()));
1663    break;
1664  }
1665
1666  case Type::ConstantArray: {
1667    const ConstantArrayType *cat = cast<ConstantArrayType>(ty);
1668    result = getConstantArrayType(
1669                 getVariableArrayDecayedType(cat->getElementType()),
1670                                  cat->getSize(),
1671                                  cat->getSizeModifier(),
1672                                  cat->getIndexTypeCVRQualifiers());
1673    break;
1674  }
1675
1676  case Type::DependentSizedArray: {
1677    const DependentSizedArrayType *dat = cast<DependentSizedArrayType>(ty);
1678    result = getDependentSizedArrayType(
1679                 getVariableArrayDecayedType(dat->getElementType()),
1680                                        dat->getSizeExpr(),
1681                                        dat->getSizeModifier(),
1682                                        dat->getIndexTypeCVRQualifiers(),
1683                                        dat->getBracketsRange());
1684    break;
1685  }
1686
1687  // Turn incomplete types into [*] types.
1688  case Type::IncompleteArray: {
1689    const IncompleteArrayType *iat = cast<IncompleteArrayType>(ty);
1690    result = getVariableArrayType(
1691                 getVariableArrayDecayedType(iat->getElementType()),
1692                                  /*size*/ 0,
1693                                  ArrayType::Normal,
1694                                  iat->getIndexTypeCVRQualifiers(),
1695                                  SourceRange());
1696    break;
1697  }
1698
1699  // Turn VLA types into [*] types.
1700  case Type::VariableArray: {
1701    const VariableArrayType *vat = cast<VariableArrayType>(ty);
1702    result = getVariableArrayType(
1703                 getVariableArrayDecayedType(vat->getElementType()),
1704                                  /*size*/ 0,
1705                                  ArrayType::Star,
1706                                  vat->getIndexTypeCVRQualifiers(),
1707                                  vat->getBracketsRange());
1708    break;
1709  }
1710  }
1711
1712  // Apply the top-level qualifiers from the original.
1713  return getQualifiedType(result, split.second);
1714}
1715
1716/// getVariableArrayType - Returns a non-unique reference to the type for a
1717/// variable array of the specified element type.
1718QualType ASTContext::getVariableArrayType(QualType EltTy,
1719                                          Expr *NumElts,
1720                                          ArrayType::ArraySizeModifier ASM,
1721                                          unsigned IndexTypeQuals,
1722                                          SourceRange Brackets) const {
1723  // Since we don't unique expressions, it isn't possible to unique VLA's
1724  // that have an expression provided for their size.
1725  QualType Canon;
1726
1727  // Be sure to pull qualifiers off the element type.
1728  if (!EltTy.isCanonical() || EltTy.hasLocalQualifiers()) {
1729    SplitQualType canonSplit = getCanonicalType(EltTy).split();
1730    Canon = getVariableArrayType(QualType(canonSplit.first, 0), NumElts, ASM,
1731                                 IndexTypeQuals, Brackets);
1732    Canon = getQualifiedType(Canon, canonSplit.second);
1733  }
1734
1735  VariableArrayType *New = new(*this, TypeAlignment)
1736    VariableArrayType(EltTy, Canon, NumElts, ASM, IndexTypeQuals, Brackets);
1737
1738  VariableArrayTypes.push_back(New);
1739  Types.push_back(New);
1740  return QualType(New, 0);
1741}
1742
1743/// getDependentSizedArrayType - Returns a non-unique reference to
1744/// the type for a dependently-sized array of the specified element
1745/// type.
1746QualType ASTContext::getDependentSizedArrayType(QualType elementType,
1747                                                Expr *numElements,
1748                                                ArrayType::ArraySizeModifier ASM,
1749                                                unsigned elementTypeQuals,
1750                                                SourceRange brackets) const {
1751  assert((!numElements || numElements->isTypeDependent() ||
1752          numElements->isValueDependent()) &&
1753         "Size must be type- or value-dependent!");
1754
1755  // Dependently-sized array types that do not have a specified number
1756  // of elements will have their sizes deduced from a dependent
1757  // initializer.  We do no canonicalization here at all, which is okay
1758  // because they can't be used in most locations.
1759  if (!numElements) {
1760    DependentSizedArrayType *newType
1761      = new (*this, TypeAlignment)
1762          DependentSizedArrayType(*this, elementType, QualType(),
1763                                  numElements, ASM, elementTypeQuals,
1764                                  brackets);
1765    Types.push_back(newType);
1766    return QualType(newType, 0);
1767  }
1768
1769  // Otherwise, we actually build a new type every time, but we
1770  // also build a canonical type.
1771
1772  SplitQualType canonElementType = getCanonicalType(elementType).split();
1773
1774  void *insertPos = 0;
1775  llvm::FoldingSetNodeID ID;
1776  DependentSizedArrayType::Profile(ID, *this,
1777                                   QualType(canonElementType.first, 0),
1778                                   ASM, elementTypeQuals, numElements);
1779
1780  // Look for an existing type with these properties.
1781  DependentSizedArrayType *canonTy =
1782    DependentSizedArrayTypes.FindNodeOrInsertPos(ID, insertPos);
1783
1784  // If we don't have one, build one.
1785  if (!canonTy) {
1786    canonTy = new (*this, TypeAlignment)
1787      DependentSizedArrayType(*this, QualType(canonElementType.first, 0),
1788                              QualType(), numElements, ASM, elementTypeQuals,
1789                              brackets);
1790    DependentSizedArrayTypes.InsertNode(canonTy, insertPos);
1791    Types.push_back(canonTy);
1792  }
1793
1794  // Apply qualifiers from the element type to the array.
1795  QualType canon = getQualifiedType(QualType(canonTy,0),
1796                                    canonElementType.second);
1797
1798  // If we didn't need extra canonicalization for the element type,
1799  // then just use that as our result.
1800  if (QualType(canonElementType.first, 0) == elementType)
1801    return canon;
1802
1803  // Otherwise, we need to build a type which follows the spelling
1804  // of the element type.
1805  DependentSizedArrayType *sugaredType
1806    = new (*this, TypeAlignment)
1807        DependentSizedArrayType(*this, elementType, canon, numElements,
1808                                ASM, elementTypeQuals, brackets);
1809  Types.push_back(sugaredType);
1810  return QualType(sugaredType, 0);
1811}
1812
1813QualType ASTContext::getIncompleteArrayType(QualType elementType,
1814                                            ArrayType::ArraySizeModifier ASM,
1815                                            unsigned elementTypeQuals) const {
1816  llvm::FoldingSetNodeID ID;
1817  IncompleteArrayType::Profile(ID, elementType, ASM, elementTypeQuals);
1818
1819  void *insertPos = 0;
1820  if (IncompleteArrayType *iat =
1821       IncompleteArrayTypes.FindNodeOrInsertPos(ID, insertPos))
1822    return QualType(iat, 0);
1823
1824  // If the element type isn't canonical, this won't be a canonical type
1825  // either, so fill in the canonical type field.  We also have to pull
1826  // qualifiers off the element type.
1827  QualType canon;
1828
1829  if (!elementType.isCanonical() || elementType.hasLocalQualifiers()) {
1830    SplitQualType canonSplit = getCanonicalType(elementType).split();
1831    canon = getIncompleteArrayType(QualType(canonSplit.first, 0),
1832                                   ASM, elementTypeQuals);
1833    canon = getQualifiedType(canon, canonSplit.second);
1834
1835    // Get the new insert position for the node we care about.
1836    IncompleteArrayType *existing =
1837      IncompleteArrayTypes.FindNodeOrInsertPos(ID, insertPos);
1838    assert(!existing && "Shouldn't be in the map!"); (void) existing;
1839  }
1840
1841  IncompleteArrayType *newType = new (*this, TypeAlignment)
1842    IncompleteArrayType(elementType, canon, ASM, elementTypeQuals);
1843
1844  IncompleteArrayTypes.InsertNode(newType, insertPos);
1845  Types.push_back(newType);
1846  return QualType(newType, 0);
1847}
1848
1849/// getVectorType - Return the unique reference to a vector type of
1850/// the specified element type and size. VectorType must be a built-in type.
1851QualType ASTContext::getVectorType(QualType vecType, unsigned NumElts,
1852                                   VectorType::VectorKind VecKind) const {
1853  assert(vecType->isBuiltinType());
1854
1855  // Check if we've already instantiated a vector of this type.
1856  llvm::FoldingSetNodeID ID;
1857  VectorType::Profile(ID, vecType, NumElts, Type::Vector, VecKind);
1858
1859  void *InsertPos = 0;
1860  if (VectorType *VTP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos))
1861    return QualType(VTP, 0);
1862
1863  // If the element type isn't canonical, this won't be a canonical type either,
1864  // so fill in the canonical type field.
1865  QualType Canonical;
1866  if (!vecType.isCanonical()) {
1867    Canonical = getVectorType(getCanonicalType(vecType), NumElts, VecKind);
1868
1869    // Get the new insert position for the node we care about.
1870    VectorType *NewIP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos);
1871    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1872  }
1873  VectorType *New = new (*this, TypeAlignment)
1874    VectorType(vecType, NumElts, Canonical, VecKind);
1875  VectorTypes.InsertNode(New, InsertPos);
1876  Types.push_back(New);
1877  return QualType(New, 0);
1878}
1879
1880/// getExtVectorType - Return the unique reference to an extended vector type of
1881/// the specified element type and size. VectorType must be a built-in type.
1882QualType
1883ASTContext::getExtVectorType(QualType vecType, unsigned NumElts) const {
1884  assert(vecType->isBuiltinType() || vecType->isDependentType());
1885
1886  // Check if we've already instantiated a vector of this type.
1887  llvm::FoldingSetNodeID ID;
1888  VectorType::Profile(ID, vecType, NumElts, Type::ExtVector,
1889                      VectorType::GenericVector);
1890  void *InsertPos = 0;
1891  if (VectorType *VTP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos))
1892    return QualType(VTP, 0);
1893
1894  // If the element type isn't canonical, this won't be a canonical type either,
1895  // so fill in the canonical type field.
1896  QualType Canonical;
1897  if (!vecType.isCanonical()) {
1898    Canonical = getExtVectorType(getCanonicalType(vecType), NumElts);
1899
1900    // Get the new insert position for the node we care about.
1901    VectorType *NewIP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos);
1902    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1903  }
1904  ExtVectorType *New = new (*this, TypeAlignment)
1905    ExtVectorType(vecType, NumElts, Canonical);
1906  VectorTypes.InsertNode(New, InsertPos);
1907  Types.push_back(New);
1908  return QualType(New, 0);
1909}
1910
1911QualType
1912ASTContext::getDependentSizedExtVectorType(QualType vecType,
1913                                           Expr *SizeExpr,
1914                                           SourceLocation AttrLoc) const {
1915  llvm::FoldingSetNodeID ID;
1916  DependentSizedExtVectorType::Profile(ID, *this, getCanonicalType(vecType),
1917                                       SizeExpr);
1918
1919  void *InsertPos = 0;
1920  DependentSizedExtVectorType *Canon
1921    = DependentSizedExtVectorTypes.FindNodeOrInsertPos(ID, InsertPos);
1922  DependentSizedExtVectorType *New;
1923  if (Canon) {
1924    // We already have a canonical version of this array type; use it as
1925    // the canonical type for a newly-built type.
1926    New = new (*this, TypeAlignment)
1927      DependentSizedExtVectorType(*this, vecType, QualType(Canon, 0),
1928                                  SizeExpr, AttrLoc);
1929  } else {
1930    QualType CanonVecTy = getCanonicalType(vecType);
1931    if (CanonVecTy == vecType) {
1932      New = new (*this, TypeAlignment)
1933        DependentSizedExtVectorType(*this, vecType, QualType(), SizeExpr,
1934                                    AttrLoc);
1935
1936      DependentSizedExtVectorType *CanonCheck
1937        = DependentSizedExtVectorTypes.FindNodeOrInsertPos(ID, InsertPos);
1938      assert(!CanonCheck && "Dependent-sized ext_vector canonical type broken");
1939      (void)CanonCheck;
1940      DependentSizedExtVectorTypes.InsertNode(New, InsertPos);
1941    } else {
1942      QualType Canon = getDependentSizedExtVectorType(CanonVecTy, SizeExpr,
1943                                                      SourceLocation());
1944      New = new (*this, TypeAlignment)
1945        DependentSizedExtVectorType(*this, vecType, Canon, SizeExpr, AttrLoc);
1946    }
1947  }
1948
1949  Types.push_back(New);
1950  return QualType(New, 0);
1951}
1952
1953/// getFunctionNoProtoType - Return a K&R style C function type like 'int()'.
1954///
1955QualType
1956ASTContext::getFunctionNoProtoType(QualType ResultTy,
1957                                   const FunctionType::ExtInfo &Info) const {
1958  const CallingConv DefaultCC = Info.getCC();
1959  const CallingConv CallConv = (LangOpts.MRTD && DefaultCC == CC_Default) ?
1960                               CC_X86StdCall : DefaultCC;
1961  // Unique functions, to guarantee there is only one function of a particular
1962  // structure.
1963  llvm::FoldingSetNodeID ID;
1964  FunctionNoProtoType::Profile(ID, ResultTy, Info);
1965
1966  void *InsertPos = 0;
1967  if (FunctionNoProtoType *FT =
1968        FunctionNoProtoTypes.FindNodeOrInsertPos(ID, InsertPos))
1969    return QualType(FT, 0);
1970
1971  QualType Canonical;
1972  if (!ResultTy.isCanonical() ||
1973      getCanonicalCallConv(CallConv) != CallConv) {
1974    Canonical =
1975      getFunctionNoProtoType(getCanonicalType(ResultTy),
1976                     Info.withCallingConv(getCanonicalCallConv(CallConv)));
1977
1978    // Get the new insert position for the node we care about.
1979    FunctionNoProtoType *NewIP =
1980      FunctionNoProtoTypes.FindNodeOrInsertPos(ID, InsertPos);
1981    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
1982  }
1983
1984  FunctionProtoType::ExtInfo newInfo = Info.withCallingConv(CallConv);
1985  FunctionNoProtoType *New = new (*this, TypeAlignment)
1986    FunctionNoProtoType(ResultTy, Canonical, newInfo);
1987  Types.push_back(New);
1988  FunctionNoProtoTypes.InsertNode(New, InsertPos);
1989  return QualType(New, 0);
1990}
1991
1992/// getFunctionType - Return a normal function type with a typed argument
1993/// list.  isVariadic indicates whether the argument list includes '...'.
1994QualType
1995ASTContext::getFunctionType(QualType ResultTy,
1996                            const QualType *ArgArray, unsigned NumArgs,
1997                            const FunctionProtoType::ExtProtoInfo &EPI) const {
1998  // Unique functions, to guarantee there is only one function of a particular
1999  // structure.
2000  llvm::FoldingSetNodeID ID;
2001  FunctionProtoType::Profile(ID, ResultTy, ArgArray, NumArgs, EPI, *this);
2002
2003  void *InsertPos = 0;
2004  if (FunctionProtoType *FTP =
2005        FunctionProtoTypes.FindNodeOrInsertPos(ID, InsertPos))
2006    return QualType(FTP, 0);
2007
2008  // Determine whether the type being created is already canonical or not.
2009  bool isCanonical= EPI.ExceptionSpecType == EST_None && ResultTy.isCanonical();
2010  for (unsigned i = 0; i != NumArgs && isCanonical; ++i)
2011    if (!ArgArray[i].isCanonicalAsParam())
2012      isCanonical = false;
2013
2014  const CallingConv DefaultCC = EPI.ExtInfo.getCC();
2015  const CallingConv CallConv = (LangOpts.MRTD && DefaultCC == CC_Default) ?
2016                               CC_X86StdCall : DefaultCC;
2017
2018  // If this type isn't canonical, get the canonical version of it.
2019  // The exception spec is not part of the canonical type.
2020  QualType Canonical;
2021  if (!isCanonical || getCanonicalCallConv(CallConv) != CallConv) {
2022    llvm::SmallVector<QualType, 16> CanonicalArgs;
2023    CanonicalArgs.reserve(NumArgs);
2024    for (unsigned i = 0; i != NumArgs; ++i)
2025      CanonicalArgs.push_back(getCanonicalParamType(ArgArray[i]));
2026
2027    FunctionProtoType::ExtProtoInfo CanonicalEPI = EPI;
2028    CanonicalEPI.ExceptionSpecType = EST_None;
2029    CanonicalEPI.NumExceptions = 0;
2030    CanonicalEPI.ExtInfo
2031      = CanonicalEPI.ExtInfo.withCallingConv(getCanonicalCallConv(CallConv));
2032
2033    Canonical = getFunctionType(getCanonicalType(ResultTy),
2034                                CanonicalArgs.data(), NumArgs,
2035                                CanonicalEPI);
2036
2037    // Get the new insert position for the node we care about.
2038    FunctionProtoType *NewIP =
2039      FunctionProtoTypes.FindNodeOrInsertPos(ID, InsertPos);
2040    assert(NewIP == 0 && "Shouldn't be in the map!"); (void)NewIP;
2041  }
2042
2043  // FunctionProtoType objects are allocated with extra bytes after
2044  // them for three variable size arrays at the end:
2045  //  - parameter types
2046  //  - exception types
2047  //  - consumed-arguments flags
2048  // Instead of the exception types, there could be a noexcept
2049  // expression.
2050  size_t Size = sizeof(FunctionProtoType) +
2051                NumArgs * sizeof(QualType);
2052  if (EPI.ExceptionSpecType == EST_Dynamic)
2053    Size += EPI.NumExceptions * sizeof(QualType);
2054  else if (EPI.ExceptionSpecType == EST_ComputedNoexcept) {
2055    Size += sizeof(Expr*);
2056  }
2057  if (EPI.ConsumedArguments)
2058    Size += NumArgs * sizeof(bool);
2059
2060  FunctionProtoType *FTP = (FunctionProtoType*) Allocate(Size, TypeAlignment);
2061  FunctionProtoType::ExtProtoInfo newEPI = EPI;
2062  newEPI.ExtInfo = EPI.ExtInfo.withCallingConv(CallConv);
2063  new (FTP) FunctionProtoType(ResultTy, ArgArray, NumArgs, Canonical, newEPI);
2064  Types.push_back(FTP);
2065  FunctionProtoTypes.InsertNode(FTP, InsertPos);
2066  return QualType(FTP, 0);
2067}
2068
2069#ifndef NDEBUG
2070static bool NeedsInjectedClassNameType(const RecordDecl *D) {
2071  if (!isa<CXXRecordDecl>(D)) return false;
2072  const CXXRecordDecl *RD = cast<CXXRecordDecl>(D);
2073  if (isa<ClassTemplatePartialSpecializationDecl>(RD))
2074    return true;
2075  if (RD->getDescribedClassTemplate() &&
2076      !isa<ClassTemplateSpecializationDecl>(RD))
2077    return true;
2078  return false;
2079}
2080#endif
2081
2082/// getInjectedClassNameType - Return the unique reference to the
2083/// injected class name type for the specified templated declaration.
2084QualType ASTContext::getInjectedClassNameType(CXXRecordDecl *Decl,
2085                                              QualType TST) const {
2086  assert(NeedsInjectedClassNameType(Decl));
2087  if (Decl->TypeForDecl) {
2088    assert(isa<InjectedClassNameType>(Decl->TypeForDecl));
2089  } else if (CXXRecordDecl *PrevDecl = Decl->getPreviousDeclaration()) {
2090    assert(PrevDecl->TypeForDecl && "previous declaration has no type");
2091    Decl->TypeForDecl = PrevDecl->TypeForDecl;
2092    assert(isa<InjectedClassNameType>(Decl->TypeForDecl));
2093  } else {
2094    Type *newType =
2095      new (*this, TypeAlignment) InjectedClassNameType(Decl, TST);
2096    Decl->TypeForDecl = newType;
2097    Types.push_back(newType);
2098  }
2099  return QualType(Decl->TypeForDecl, 0);
2100}
2101
2102/// getTypeDeclType - Return the unique reference to the type for the
2103/// specified type declaration.
2104QualType ASTContext::getTypeDeclTypeSlow(const TypeDecl *Decl) const {
2105  assert(Decl && "Passed null for Decl param");
2106  assert(!Decl->TypeForDecl && "TypeForDecl present in slow case");
2107
2108  if (const TypedefNameDecl *Typedef = dyn_cast<TypedefNameDecl>(Decl))
2109    return getTypedefType(Typedef);
2110
2111  assert(!isa<TemplateTypeParmDecl>(Decl) &&
2112         "Template type parameter types are always available.");
2113
2114  if (const RecordDecl *Record = dyn_cast<RecordDecl>(Decl)) {
2115    assert(!Record->getPreviousDeclaration() &&
2116           "struct/union has previous declaration");
2117    assert(!NeedsInjectedClassNameType(Record));
2118    return getRecordType(Record);
2119  } else if (const EnumDecl *Enum = dyn_cast<EnumDecl>(Decl)) {
2120    assert(!Enum->getPreviousDeclaration() &&
2121           "enum has previous declaration");
2122    return getEnumType(Enum);
2123  } else if (const UnresolvedUsingTypenameDecl *Using =
2124               dyn_cast<UnresolvedUsingTypenameDecl>(Decl)) {
2125    Type *newType = new (*this, TypeAlignment) UnresolvedUsingType(Using);
2126    Decl->TypeForDecl = newType;
2127    Types.push_back(newType);
2128  } else
2129    llvm_unreachable("TypeDecl without a type?");
2130
2131  return QualType(Decl->TypeForDecl, 0);
2132}
2133
2134/// getTypedefType - Return the unique reference to the type for the
2135/// specified typedef name decl.
2136QualType
2137ASTContext::getTypedefType(const TypedefNameDecl *Decl,
2138                           QualType Canonical) const {
2139  if (Decl->TypeForDecl) return QualType(Decl->TypeForDecl, 0);
2140
2141  if (Canonical.isNull())
2142    Canonical = getCanonicalType(Decl->getUnderlyingType());
2143  TypedefType *newType = new(*this, TypeAlignment)
2144    TypedefType(Type::Typedef, Decl, Canonical);
2145  Decl->TypeForDecl = newType;
2146  Types.push_back(newType);
2147  return QualType(newType, 0);
2148}
2149
2150QualType ASTContext::getRecordType(const RecordDecl *Decl) const {
2151  if (Decl->TypeForDecl) return QualType(Decl->TypeForDecl, 0);
2152
2153  if (const RecordDecl *PrevDecl = Decl->getPreviousDeclaration())
2154    if (PrevDecl->TypeForDecl)
2155      return QualType(Decl->TypeForDecl = PrevDecl->TypeForDecl, 0);
2156
2157  RecordType *newType = new (*this, TypeAlignment) RecordType(Decl);
2158  Decl->TypeForDecl = newType;
2159  Types.push_back(newType);
2160  return QualType(newType, 0);
2161}
2162
2163QualType ASTContext::getEnumType(const EnumDecl *Decl) const {
2164  if (Decl->TypeForDecl) return QualType(Decl->TypeForDecl, 0);
2165
2166  if (const EnumDecl *PrevDecl = Decl->getPreviousDeclaration())
2167    if (PrevDecl->TypeForDecl)
2168      return QualType(Decl->TypeForDecl = PrevDecl->TypeForDecl, 0);
2169
2170  EnumType *newType = new (*this, TypeAlignment) EnumType(Decl);
2171  Decl->TypeForDecl = newType;
2172  Types.push_back(newType);
2173  return QualType(newType, 0);
2174}
2175
2176QualType ASTContext::getAttributedType(AttributedType::Kind attrKind,
2177                                       QualType modifiedType,
2178                                       QualType equivalentType) {
2179  llvm::FoldingSetNodeID id;
2180  AttributedType::Profile(id, attrKind, modifiedType, equivalentType);
2181
2182  void *insertPos = 0;
2183  AttributedType *type = AttributedTypes.FindNodeOrInsertPos(id, insertPos);
2184  if (type) return QualType(type, 0);
2185
2186  QualType canon = getCanonicalType(equivalentType);
2187  type = new (*this, TypeAlignment)
2188           AttributedType(canon, attrKind, modifiedType, equivalentType);
2189
2190  Types.push_back(type);
2191  AttributedTypes.InsertNode(type, insertPos);
2192
2193  return QualType(type, 0);
2194}
2195
2196
2197/// \brief Retrieve a substitution-result type.
2198QualType
2199ASTContext::getSubstTemplateTypeParmType(const TemplateTypeParmType *Parm,
2200                                         QualType Replacement) const {
2201  assert(Replacement.isCanonical()
2202         && "replacement types must always be canonical");
2203
2204  llvm::FoldingSetNodeID ID;
2205  SubstTemplateTypeParmType::Profile(ID, Parm, Replacement);
2206  void *InsertPos = 0;
2207  SubstTemplateTypeParmType *SubstParm
2208    = SubstTemplateTypeParmTypes.FindNodeOrInsertPos(ID, InsertPos);
2209
2210  if (!SubstParm) {
2211    SubstParm = new (*this, TypeAlignment)
2212      SubstTemplateTypeParmType(Parm, Replacement);
2213    Types.push_back(SubstParm);
2214    SubstTemplateTypeParmTypes.InsertNode(SubstParm, InsertPos);
2215  }
2216
2217  return QualType(SubstParm, 0);
2218}
2219
2220/// \brief Retrieve a
2221QualType ASTContext::getSubstTemplateTypeParmPackType(
2222                                          const TemplateTypeParmType *Parm,
2223                                              const TemplateArgument &ArgPack) {
2224#ifndef NDEBUG
2225  for (TemplateArgument::pack_iterator P = ArgPack.pack_begin(),
2226                                    PEnd = ArgPack.pack_end();
2227       P != PEnd; ++P) {
2228    assert(P->getKind() == TemplateArgument::Type &&"Pack contains a non-type");
2229    assert(P->getAsType().isCanonical() && "Pack contains non-canonical type");
2230  }
2231#endif
2232
2233  llvm::FoldingSetNodeID ID;
2234  SubstTemplateTypeParmPackType::Profile(ID, Parm, ArgPack);
2235  void *InsertPos = 0;
2236  if (SubstTemplateTypeParmPackType *SubstParm
2237        = SubstTemplateTypeParmPackTypes.FindNodeOrInsertPos(ID, InsertPos))
2238    return QualType(SubstParm, 0);
2239
2240  QualType Canon;
2241  if (!Parm->isCanonicalUnqualified()) {
2242    Canon = getCanonicalType(QualType(Parm, 0));
2243    Canon = getSubstTemplateTypeParmPackType(cast<TemplateTypeParmType>(Canon),
2244                                             ArgPack);
2245    SubstTemplateTypeParmPackTypes.FindNodeOrInsertPos(ID, InsertPos);
2246  }
2247
2248  SubstTemplateTypeParmPackType *SubstParm
2249    = new (*this, TypeAlignment) SubstTemplateTypeParmPackType(Parm, Canon,
2250                                                               ArgPack);
2251  Types.push_back(SubstParm);
2252  SubstTemplateTypeParmTypes.InsertNode(SubstParm, InsertPos);
2253  return QualType(SubstParm, 0);
2254}
2255
2256/// \brief Retrieve the template type parameter type for a template
2257/// parameter or parameter pack with the given depth, index, and (optionally)
2258/// name.
2259QualType ASTContext::getTemplateTypeParmType(unsigned Depth, unsigned Index,
2260                                             bool ParameterPack,
2261                                             TemplateTypeParmDecl *TTPDecl) const {
2262  llvm::FoldingSetNodeID ID;
2263  TemplateTypeParmType::Profile(ID, Depth, Index, ParameterPack, TTPDecl);
2264  void *InsertPos = 0;
2265  TemplateTypeParmType *TypeParm
2266    = TemplateTypeParmTypes.FindNodeOrInsertPos(ID, InsertPos);
2267
2268  if (TypeParm)
2269    return QualType(TypeParm, 0);
2270
2271  if (TTPDecl) {
2272    QualType Canon = getTemplateTypeParmType(Depth, Index, ParameterPack);
2273    TypeParm = new (*this, TypeAlignment) TemplateTypeParmType(TTPDecl, Canon);
2274
2275    TemplateTypeParmType *TypeCheck
2276      = TemplateTypeParmTypes.FindNodeOrInsertPos(ID, InsertPos);
2277    assert(!TypeCheck && "Template type parameter canonical type broken");
2278    (void)TypeCheck;
2279  } else
2280    TypeParm = new (*this, TypeAlignment)
2281      TemplateTypeParmType(Depth, Index, ParameterPack);
2282
2283  Types.push_back(TypeParm);
2284  TemplateTypeParmTypes.InsertNode(TypeParm, InsertPos);
2285
2286  return QualType(TypeParm, 0);
2287}
2288
2289TypeSourceInfo *
2290ASTContext::getTemplateSpecializationTypeInfo(TemplateName Name,
2291                                              SourceLocation NameLoc,
2292                                        const TemplateArgumentListInfo &Args,
2293                                              QualType Underlying) const {
2294  assert(!Name.getAsDependentTemplateName() &&
2295         "No dependent template names here!");
2296  QualType TST = getTemplateSpecializationType(Name, Args, Underlying);
2297
2298  TypeSourceInfo *DI = CreateTypeSourceInfo(TST);
2299  TemplateSpecializationTypeLoc TL
2300    = cast<TemplateSpecializationTypeLoc>(DI->getTypeLoc());
2301  TL.setTemplateNameLoc(NameLoc);
2302  TL.setLAngleLoc(Args.getLAngleLoc());
2303  TL.setRAngleLoc(Args.getRAngleLoc());
2304  for (unsigned i = 0, e = TL.getNumArgs(); i != e; ++i)
2305    TL.setArgLocInfo(i, Args[i].getLocInfo());
2306  return DI;
2307}
2308
2309QualType
2310ASTContext::getTemplateSpecializationType(TemplateName Template,
2311                                          const TemplateArgumentListInfo &Args,
2312                                          QualType Underlying) const {
2313  assert(!Template.getAsDependentTemplateName() &&
2314         "No dependent template names here!");
2315
2316  unsigned NumArgs = Args.size();
2317
2318  llvm::SmallVector<TemplateArgument, 4> ArgVec;
2319  ArgVec.reserve(NumArgs);
2320  for (unsigned i = 0; i != NumArgs; ++i)
2321    ArgVec.push_back(Args[i].getArgument());
2322
2323  return getTemplateSpecializationType(Template, ArgVec.data(), NumArgs,
2324                                       Underlying);
2325}
2326
2327QualType
2328ASTContext::getTemplateSpecializationType(TemplateName Template,
2329                                          const TemplateArgument *Args,
2330                                          unsigned NumArgs,
2331                                          QualType Underlying) const {
2332  assert(!Template.getAsDependentTemplateName() &&
2333         "No dependent template names here!");
2334  // Look through qualified template names.
2335  if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName())
2336    Template = TemplateName(QTN->getTemplateDecl());
2337
2338  bool isTypeAlias =
2339    Template.getAsTemplateDecl() &&
2340    isa<TypeAliasTemplateDecl>(Template.getAsTemplateDecl());
2341
2342  QualType CanonType;
2343  if (!Underlying.isNull())
2344    CanonType = getCanonicalType(Underlying);
2345  else {
2346    assert(!isTypeAlias &&
2347           "Underlying type for template alias must be computed by caller");
2348    CanonType = getCanonicalTemplateSpecializationType(Template, Args,
2349                                                       NumArgs);
2350  }
2351
2352  // Allocate the (non-canonical) template specialization type, but don't
2353  // try to unique it: these types typically have location information that
2354  // we don't unique and don't want to lose.
2355  void *Mem = Allocate(sizeof(TemplateSpecializationType) +
2356                       sizeof(TemplateArgument) * NumArgs +
2357                       (isTypeAlias ? sizeof(QualType) : 0),
2358                       TypeAlignment);
2359  TemplateSpecializationType *Spec
2360    = new (Mem) TemplateSpecializationType(Template,
2361                                           Args, NumArgs,
2362                                           CanonType,
2363                                         isTypeAlias ? Underlying : QualType());
2364
2365  Types.push_back(Spec);
2366  return QualType(Spec, 0);
2367}
2368
2369QualType
2370ASTContext::getCanonicalTemplateSpecializationType(TemplateName Template,
2371                                                   const TemplateArgument *Args,
2372                                                   unsigned NumArgs) const {
2373  assert(!Template.getAsDependentTemplateName() &&
2374         "No dependent template names here!");
2375  assert((!Template.getAsTemplateDecl() ||
2376          !isa<TypeAliasTemplateDecl>(Template.getAsTemplateDecl())) &&
2377         "Underlying type for template alias must be computed by caller");
2378
2379  // Look through qualified template names.
2380  if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName())
2381    Template = TemplateName(QTN->getTemplateDecl());
2382
2383  // Build the canonical template specialization type.
2384  TemplateName CanonTemplate = getCanonicalTemplateName(Template);
2385  llvm::SmallVector<TemplateArgument, 4> CanonArgs;
2386  CanonArgs.reserve(NumArgs);
2387  for (unsigned I = 0; I != NumArgs; ++I)
2388    CanonArgs.push_back(getCanonicalTemplateArgument(Args[I]));
2389
2390  // Determine whether this canonical template specialization type already
2391  // exists.
2392  llvm::FoldingSetNodeID ID;
2393  TemplateSpecializationType::Profile(ID, CanonTemplate,
2394                                      CanonArgs.data(), NumArgs, *this);
2395
2396  void *InsertPos = 0;
2397  TemplateSpecializationType *Spec
2398    = TemplateSpecializationTypes.FindNodeOrInsertPos(ID, InsertPos);
2399
2400  if (!Spec) {
2401    // Allocate a new canonical template specialization type.
2402    void *Mem = Allocate((sizeof(TemplateSpecializationType) +
2403                          sizeof(TemplateArgument) * NumArgs),
2404                         TypeAlignment);
2405    Spec = new (Mem) TemplateSpecializationType(CanonTemplate,
2406                                                CanonArgs.data(), NumArgs,
2407                                                QualType(), QualType());
2408    Types.push_back(Spec);
2409    TemplateSpecializationTypes.InsertNode(Spec, InsertPos);
2410  }
2411
2412  assert(Spec->isDependentType() &&
2413         "Non-dependent template-id type must have a canonical type");
2414  return QualType(Spec, 0);
2415}
2416
2417QualType
2418ASTContext::getElaboratedType(ElaboratedTypeKeyword Keyword,
2419                              NestedNameSpecifier *NNS,
2420                              QualType NamedType) const {
2421  llvm::FoldingSetNodeID ID;
2422  ElaboratedType::Profile(ID, Keyword, NNS, NamedType);
2423
2424  void *InsertPos = 0;
2425  ElaboratedType *T = ElaboratedTypes.FindNodeOrInsertPos(ID, InsertPos);
2426  if (T)
2427    return QualType(T, 0);
2428
2429  QualType Canon = NamedType;
2430  if (!Canon.isCanonical()) {
2431    Canon = getCanonicalType(NamedType);
2432    ElaboratedType *CheckT = ElaboratedTypes.FindNodeOrInsertPos(ID, InsertPos);
2433    assert(!CheckT && "Elaborated canonical type broken");
2434    (void)CheckT;
2435  }
2436
2437  T = new (*this) ElaboratedType(Keyword, NNS, NamedType, Canon);
2438  Types.push_back(T);
2439  ElaboratedTypes.InsertNode(T, InsertPos);
2440  return QualType(T, 0);
2441}
2442
2443QualType
2444ASTContext::getParenType(QualType InnerType) const {
2445  llvm::FoldingSetNodeID ID;
2446  ParenType::Profile(ID, InnerType);
2447
2448  void *InsertPos = 0;
2449  ParenType *T = ParenTypes.FindNodeOrInsertPos(ID, InsertPos);
2450  if (T)
2451    return QualType(T, 0);
2452
2453  QualType Canon = InnerType;
2454  if (!Canon.isCanonical()) {
2455    Canon = getCanonicalType(InnerType);
2456    ParenType *CheckT = ParenTypes.FindNodeOrInsertPos(ID, InsertPos);
2457    assert(!CheckT && "Paren canonical type broken");
2458    (void)CheckT;
2459  }
2460
2461  T = new (*this) ParenType(InnerType, Canon);
2462  Types.push_back(T);
2463  ParenTypes.InsertNode(T, InsertPos);
2464  return QualType(T, 0);
2465}
2466
2467QualType ASTContext::getDependentNameType(ElaboratedTypeKeyword Keyword,
2468                                          NestedNameSpecifier *NNS,
2469                                          const IdentifierInfo *Name,
2470                                          QualType Canon) const {
2471  assert(NNS->isDependent() && "nested-name-specifier must be dependent");
2472
2473  if (Canon.isNull()) {
2474    NestedNameSpecifier *CanonNNS = getCanonicalNestedNameSpecifier(NNS);
2475    ElaboratedTypeKeyword CanonKeyword = Keyword;
2476    if (Keyword == ETK_None)
2477      CanonKeyword = ETK_Typename;
2478
2479    if (CanonNNS != NNS || CanonKeyword != Keyword)
2480      Canon = getDependentNameType(CanonKeyword, CanonNNS, Name);
2481  }
2482
2483  llvm::FoldingSetNodeID ID;
2484  DependentNameType::Profile(ID, Keyword, NNS, Name);
2485
2486  void *InsertPos = 0;
2487  DependentNameType *T
2488    = DependentNameTypes.FindNodeOrInsertPos(ID, InsertPos);
2489  if (T)
2490    return QualType(T, 0);
2491
2492  T = new (*this) DependentNameType(Keyword, NNS, Name, Canon);
2493  Types.push_back(T);
2494  DependentNameTypes.InsertNode(T, InsertPos);
2495  return QualType(T, 0);
2496}
2497
2498QualType
2499ASTContext::getDependentTemplateSpecializationType(
2500                                 ElaboratedTypeKeyword Keyword,
2501                                 NestedNameSpecifier *NNS,
2502                                 const IdentifierInfo *Name,
2503                                 const TemplateArgumentListInfo &Args) const {
2504  // TODO: avoid this copy
2505  llvm::SmallVector<TemplateArgument, 16> ArgCopy;
2506  for (unsigned I = 0, E = Args.size(); I != E; ++I)
2507    ArgCopy.push_back(Args[I].getArgument());
2508  return getDependentTemplateSpecializationType(Keyword, NNS, Name,
2509                                                ArgCopy.size(),
2510                                                ArgCopy.data());
2511}
2512
2513QualType
2514ASTContext::getDependentTemplateSpecializationType(
2515                                 ElaboratedTypeKeyword Keyword,
2516                                 NestedNameSpecifier *NNS,
2517                                 const IdentifierInfo *Name,
2518                                 unsigned NumArgs,
2519                                 const TemplateArgument *Args) const {
2520  assert((!NNS || NNS->isDependent()) &&
2521         "nested-name-specifier must be dependent");
2522
2523  llvm::FoldingSetNodeID ID;
2524  DependentTemplateSpecializationType::Profile(ID, *this, Keyword, NNS,
2525                                               Name, NumArgs, Args);
2526
2527  void *InsertPos = 0;
2528  DependentTemplateSpecializationType *T
2529    = DependentTemplateSpecializationTypes.FindNodeOrInsertPos(ID, InsertPos);
2530  if (T)
2531    return QualType(T, 0);
2532
2533  NestedNameSpecifier *CanonNNS = getCanonicalNestedNameSpecifier(NNS);
2534
2535  ElaboratedTypeKeyword CanonKeyword = Keyword;
2536  if (Keyword == ETK_None) CanonKeyword = ETK_Typename;
2537
2538  bool AnyNonCanonArgs = false;
2539  llvm::SmallVector<TemplateArgument, 16> CanonArgs(NumArgs);
2540  for (unsigned I = 0; I != NumArgs; ++I) {
2541    CanonArgs[I] = getCanonicalTemplateArgument(Args[I]);
2542    if (!CanonArgs[I].structurallyEquals(Args[I]))
2543      AnyNonCanonArgs = true;
2544  }
2545
2546  QualType Canon;
2547  if (AnyNonCanonArgs || CanonNNS != NNS || CanonKeyword != Keyword) {
2548    Canon = getDependentTemplateSpecializationType(CanonKeyword, CanonNNS,
2549                                                   Name, NumArgs,
2550                                                   CanonArgs.data());
2551
2552    // Find the insert position again.
2553    DependentTemplateSpecializationTypes.FindNodeOrInsertPos(ID, InsertPos);
2554  }
2555
2556  void *Mem = Allocate((sizeof(DependentTemplateSpecializationType) +
2557                        sizeof(TemplateArgument) * NumArgs),
2558                       TypeAlignment);
2559  T = new (Mem) DependentTemplateSpecializationType(Keyword, NNS,
2560                                                    Name, NumArgs, Args, Canon);
2561  Types.push_back(T);
2562  DependentTemplateSpecializationTypes.InsertNode(T, InsertPos);
2563  return QualType(T, 0);
2564}
2565
2566QualType ASTContext::getPackExpansionType(QualType Pattern,
2567                                      llvm::Optional<unsigned> NumExpansions) {
2568  llvm::FoldingSetNodeID ID;
2569  PackExpansionType::Profile(ID, Pattern, NumExpansions);
2570
2571  assert(Pattern->containsUnexpandedParameterPack() &&
2572         "Pack expansions must expand one or more parameter packs");
2573  void *InsertPos = 0;
2574  PackExpansionType *T
2575    = PackExpansionTypes.FindNodeOrInsertPos(ID, InsertPos);
2576  if (T)
2577    return QualType(T, 0);
2578
2579  QualType Canon;
2580  if (!Pattern.isCanonical()) {
2581    Canon = getPackExpansionType(getCanonicalType(Pattern), NumExpansions);
2582
2583    // Find the insert position again.
2584    PackExpansionTypes.FindNodeOrInsertPos(ID, InsertPos);
2585  }
2586
2587  T = new (*this) PackExpansionType(Pattern, Canon, NumExpansions);
2588  Types.push_back(T);
2589  PackExpansionTypes.InsertNode(T, InsertPos);
2590  return QualType(T, 0);
2591}
2592
2593/// CmpProtocolNames - Comparison predicate for sorting protocols
2594/// alphabetically.
2595static bool CmpProtocolNames(const ObjCProtocolDecl *LHS,
2596                            const ObjCProtocolDecl *RHS) {
2597  return LHS->getDeclName() < RHS->getDeclName();
2598}
2599
2600static bool areSortedAndUniqued(ObjCProtocolDecl * const *Protocols,
2601                                unsigned NumProtocols) {
2602  if (NumProtocols == 0) return true;
2603
2604  for (unsigned i = 1; i != NumProtocols; ++i)
2605    if (!CmpProtocolNames(Protocols[i-1], Protocols[i]))
2606      return false;
2607  return true;
2608}
2609
2610static void SortAndUniqueProtocols(ObjCProtocolDecl **Protocols,
2611                                   unsigned &NumProtocols) {
2612  ObjCProtocolDecl **ProtocolsEnd = Protocols+NumProtocols;
2613
2614  // Sort protocols, keyed by name.
2615  std::sort(Protocols, Protocols+NumProtocols, CmpProtocolNames);
2616
2617  // Remove duplicates.
2618  ProtocolsEnd = std::unique(Protocols, ProtocolsEnd);
2619  NumProtocols = ProtocolsEnd-Protocols;
2620}
2621
2622QualType ASTContext::getObjCObjectType(QualType BaseType,
2623                                       ObjCProtocolDecl * const *Protocols,
2624                                       unsigned NumProtocols) const {
2625  // If the base type is an interface and there aren't any protocols
2626  // to add, then the interface type will do just fine.
2627  if (!NumProtocols && isa<ObjCInterfaceType>(BaseType))
2628    return BaseType;
2629
2630  // Look in the folding set for an existing type.
2631  llvm::FoldingSetNodeID ID;
2632  ObjCObjectTypeImpl::Profile(ID, BaseType, Protocols, NumProtocols);
2633  void *InsertPos = 0;
2634  if (ObjCObjectType *QT = ObjCObjectTypes.FindNodeOrInsertPos(ID, InsertPos))
2635    return QualType(QT, 0);
2636
2637  // Build the canonical type, which has the canonical base type and
2638  // a sorted-and-uniqued list of protocols.
2639  QualType Canonical;
2640  bool ProtocolsSorted = areSortedAndUniqued(Protocols, NumProtocols);
2641  if (!ProtocolsSorted || !BaseType.isCanonical()) {
2642    if (!ProtocolsSorted) {
2643      llvm::SmallVector<ObjCProtocolDecl*, 8> Sorted(Protocols,
2644                                                     Protocols + NumProtocols);
2645      unsigned UniqueCount = NumProtocols;
2646
2647      SortAndUniqueProtocols(&Sorted[0], UniqueCount);
2648      Canonical = getObjCObjectType(getCanonicalType(BaseType),
2649                                    &Sorted[0], UniqueCount);
2650    } else {
2651      Canonical = getObjCObjectType(getCanonicalType(BaseType),
2652                                    Protocols, NumProtocols);
2653    }
2654
2655    // Regenerate InsertPos.
2656    ObjCObjectTypes.FindNodeOrInsertPos(ID, InsertPos);
2657  }
2658
2659  unsigned Size = sizeof(ObjCObjectTypeImpl);
2660  Size += NumProtocols * sizeof(ObjCProtocolDecl *);
2661  void *Mem = Allocate(Size, TypeAlignment);
2662  ObjCObjectTypeImpl *T =
2663    new (Mem) ObjCObjectTypeImpl(Canonical, BaseType, Protocols, NumProtocols);
2664
2665  Types.push_back(T);
2666  ObjCObjectTypes.InsertNode(T, InsertPos);
2667  return QualType(T, 0);
2668}
2669
2670/// getObjCObjectPointerType - Return a ObjCObjectPointerType type for
2671/// the given object type.
2672QualType ASTContext::getObjCObjectPointerType(QualType ObjectT) const {
2673  llvm::FoldingSetNodeID ID;
2674  ObjCObjectPointerType::Profile(ID, ObjectT);
2675
2676  void *InsertPos = 0;
2677  if (ObjCObjectPointerType *QT =
2678              ObjCObjectPointerTypes.FindNodeOrInsertPos(ID, InsertPos))
2679    return QualType(QT, 0);
2680
2681  // Find the canonical object type.
2682  QualType Canonical;
2683  if (!ObjectT.isCanonical()) {
2684    Canonical = getObjCObjectPointerType(getCanonicalType(ObjectT));
2685
2686    // Regenerate InsertPos.
2687    ObjCObjectPointerTypes.FindNodeOrInsertPos(ID, InsertPos);
2688  }
2689
2690  // No match.
2691  void *Mem = Allocate(sizeof(ObjCObjectPointerType), TypeAlignment);
2692  ObjCObjectPointerType *QType =
2693    new (Mem) ObjCObjectPointerType(Canonical, ObjectT);
2694
2695  Types.push_back(QType);
2696  ObjCObjectPointerTypes.InsertNode(QType, InsertPos);
2697  return QualType(QType, 0);
2698}
2699
2700/// getObjCInterfaceType - Return the unique reference to the type for the
2701/// specified ObjC interface decl. The list of protocols is optional.
2702QualType ASTContext::getObjCInterfaceType(const ObjCInterfaceDecl *Decl) const {
2703  if (Decl->TypeForDecl)
2704    return QualType(Decl->TypeForDecl, 0);
2705
2706  // FIXME: redeclarations?
2707  void *Mem = Allocate(sizeof(ObjCInterfaceType), TypeAlignment);
2708  ObjCInterfaceType *T = new (Mem) ObjCInterfaceType(Decl);
2709  Decl->TypeForDecl = T;
2710  Types.push_back(T);
2711  return QualType(T, 0);
2712}
2713
2714/// getTypeOfExprType - Unlike many "get<Type>" functions, we can't unique
2715/// TypeOfExprType AST's (since expression's are never shared). For example,
2716/// multiple declarations that refer to "typeof(x)" all contain different
2717/// DeclRefExpr's. This doesn't effect the type checker, since it operates
2718/// on canonical type's (which are always unique).
2719QualType ASTContext::getTypeOfExprType(Expr *tofExpr) const {
2720  TypeOfExprType *toe;
2721  if (tofExpr->isTypeDependent()) {
2722    llvm::FoldingSetNodeID ID;
2723    DependentTypeOfExprType::Profile(ID, *this, tofExpr);
2724
2725    void *InsertPos = 0;
2726    DependentTypeOfExprType *Canon
2727      = DependentTypeOfExprTypes.FindNodeOrInsertPos(ID, InsertPos);
2728    if (Canon) {
2729      // We already have a "canonical" version of an identical, dependent
2730      // typeof(expr) type. Use that as our canonical type.
2731      toe = new (*this, TypeAlignment) TypeOfExprType(tofExpr,
2732                                          QualType((TypeOfExprType*)Canon, 0));
2733    }
2734    else {
2735      // Build a new, canonical typeof(expr) type.
2736      Canon
2737        = new (*this, TypeAlignment) DependentTypeOfExprType(*this, tofExpr);
2738      DependentTypeOfExprTypes.InsertNode(Canon, InsertPos);
2739      toe = Canon;
2740    }
2741  } else {
2742    QualType Canonical = getCanonicalType(tofExpr->getType());
2743    toe = new (*this, TypeAlignment) TypeOfExprType(tofExpr, Canonical);
2744  }
2745  Types.push_back(toe);
2746  return QualType(toe, 0);
2747}
2748
2749/// getTypeOfType -  Unlike many "get<Type>" functions, we don't unique
2750/// TypeOfType AST's. The only motivation to unique these nodes would be
2751/// memory savings. Since typeof(t) is fairly uncommon, space shouldn't be
2752/// an issue. This doesn't effect the type checker, since it operates
2753/// on canonical type's (which are always unique).
2754QualType ASTContext::getTypeOfType(QualType tofType) const {
2755  QualType Canonical = getCanonicalType(tofType);
2756  TypeOfType *tot = new (*this, TypeAlignment) TypeOfType(tofType, Canonical);
2757  Types.push_back(tot);
2758  return QualType(tot, 0);
2759}
2760
2761/// getDecltypeForExpr - Given an expr, will return the decltype for that
2762/// expression, according to the rules in C++0x [dcl.type.simple]p4
2763static QualType getDecltypeForExpr(const Expr *e, const ASTContext &Context) {
2764  if (e->isTypeDependent())
2765    return Context.DependentTy;
2766
2767  // If e is an id expression or a class member access, decltype(e) is defined
2768  // as the type of the entity named by e.
2769  if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(e)) {
2770    if (const ValueDecl *VD = dyn_cast<ValueDecl>(DRE->getDecl()))
2771      return VD->getType();
2772  }
2773  if (const MemberExpr *ME = dyn_cast<MemberExpr>(e)) {
2774    if (const FieldDecl *FD = dyn_cast<FieldDecl>(ME->getMemberDecl()))
2775      return FD->getType();
2776  }
2777  // If e is a function call or an invocation of an overloaded operator,
2778  // (parentheses around e are ignored), decltype(e) is defined as the
2779  // return type of that function.
2780  if (const CallExpr *CE = dyn_cast<CallExpr>(e->IgnoreParens()))
2781    return CE->getCallReturnType();
2782
2783  QualType T = e->getType();
2784
2785  // Otherwise, where T is the type of e, if e is an lvalue, decltype(e) is
2786  // defined as T&, otherwise decltype(e) is defined as T.
2787  if (e->isLValue())
2788    T = Context.getLValueReferenceType(T);
2789
2790  return T;
2791}
2792
2793/// getDecltypeType -  Unlike many "get<Type>" functions, we don't unique
2794/// DecltypeType AST's. The only motivation to unique these nodes would be
2795/// memory savings. Since decltype(t) is fairly uncommon, space shouldn't be
2796/// an issue. This doesn't effect the type checker, since it operates
2797/// on canonical type's (which are always unique).
2798QualType ASTContext::getDecltypeType(Expr *e) const {
2799  DecltypeType *dt;
2800  if (e->isTypeDependent()) {
2801    llvm::FoldingSetNodeID ID;
2802    DependentDecltypeType::Profile(ID, *this, e);
2803
2804    void *InsertPos = 0;
2805    DependentDecltypeType *Canon
2806      = DependentDecltypeTypes.FindNodeOrInsertPos(ID, InsertPos);
2807    if (Canon) {
2808      // We already have a "canonical" version of an equivalent, dependent
2809      // decltype type. Use that as our canonical type.
2810      dt = new (*this, TypeAlignment) DecltypeType(e, DependentTy,
2811                                       QualType((DecltypeType*)Canon, 0));
2812    }
2813    else {
2814      // Build a new, canonical typeof(expr) type.
2815      Canon = new (*this, TypeAlignment) DependentDecltypeType(*this, e);
2816      DependentDecltypeTypes.InsertNode(Canon, InsertPos);
2817      dt = Canon;
2818    }
2819  } else {
2820    QualType T = getDecltypeForExpr(e, *this);
2821    dt = new (*this, TypeAlignment) DecltypeType(e, T, getCanonicalType(T));
2822  }
2823  Types.push_back(dt);
2824  return QualType(dt, 0);
2825}
2826
2827/// getUnaryTransformationType - We don't unique these, since the memory
2828/// savings are minimal and these are rare.
2829QualType ASTContext::getUnaryTransformType(QualType BaseType,
2830                                           QualType UnderlyingType,
2831                                           UnaryTransformType::UTTKind Kind)
2832    const {
2833  UnaryTransformType *Ty =
2834    new (*this, TypeAlignment) UnaryTransformType (BaseType, UnderlyingType,
2835                                                   Kind,
2836                                 UnderlyingType->isDependentType() ?
2837                                    QualType() : UnderlyingType);
2838  Types.push_back(Ty);
2839  return QualType(Ty, 0);
2840}
2841
2842/// getAutoType - We only unique auto types after they've been deduced.
2843QualType ASTContext::getAutoType(QualType DeducedType) const {
2844  void *InsertPos = 0;
2845  if (!DeducedType.isNull()) {
2846    // Look in the folding set for an existing type.
2847    llvm::FoldingSetNodeID ID;
2848    AutoType::Profile(ID, DeducedType);
2849    if (AutoType *AT = AutoTypes.FindNodeOrInsertPos(ID, InsertPos))
2850      return QualType(AT, 0);
2851  }
2852
2853  AutoType *AT = new (*this, TypeAlignment) AutoType(DeducedType);
2854  Types.push_back(AT);
2855  if (InsertPos)
2856    AutoTypes.InsertNode(AT, InsertPos);
2857  return QualType(AT, 0);
2858}
2859
2860/// getAutoDeductType - Get type pattern for deducing against 'auto'.
2861QualType ASTContext::getAutoDeductType() const {
2862  if (AutoDeductTy.isNull())
2863    AutoDeductTy = getAutoType(QualType());
2864  assert(!AutoDeductTy.isNull() && "can't build 'auto' pattern");
2865  return AutoDeductTy;
2866}
2867
2868/// getAutoRRefDeductType - Get type pattern for deducing against 'auto &&'.
2869QualType ASTContext::getAutoRRefDeductType() const {
2870  if (AutoRRefDeductTy.isNull())
2871    AutoRRefDeductTy = getRValueReferenceType(getAutoDeductType());
2872  assert(!AutoRRefDeductTy.isNull() && "can't build 'auto &&' pattern");
2873  return AutoRRefDeductTy;
2874}
2875
2876/// getTagDeclType - Return the unique reference to the type for the
2877/// specified TagDecl (struct/union/class/enum) decl.
2878QualType ASTContext::getTagDeclType(const TagDecl *Decl) const {
2879  assert (Decl);
2880  // FIXME: What is the design on getTagDeclType when it requires casting
2881  // away const?  mutable?
2882  return getTypeDeclType(const_cast<TagDecl*>(Decl));
2883}
2884
2885/// getSizeType - Return the unique type for "size_t" (C99 7.17), the result
2886/// of the sizeof operator (C99 6.5.3.4p4). The value is target dependent and
2887/// needs to agree with the definition in <stddef.h>.
2888CanQualType ASTContext::getSizeType() const {
2889  return getFromTargetType(Target.getSizeType());
2890}
2891
2892/// getSignedWCharType - Return the type of "signed wchar_t".
2893/// Used when in C++, as a GCC extension.
2894QualType ASTContext::getSignedWCharType() const {
2895  // FIXME: derive from "Target" ?
2896  return WCharTy;
2897}
2898
2899/// getUnsignedWCharType - Return the type of "unsigned wchar_t".
2900/// Used when in C++, as a GCC extension.
2901QualType ASTContext::getUnsignedWCharType() const {
2902  // FIXME: derive from "Target" ?
2903  return UnsignedIntTy;
2904}
2905
2906/// getPointerDiffType - Return the unique type for "ptrdiff_t" (ref?)
2907/// defined in <stddef.h>. Pointer - pointer requires this (C99 6.5.6p9).
2908QualType ASTContext::getPointerDiffType() const {
2909  return getFromTargetType(Target.getPtrDiffType(0));
2910}
2911
2912//===----------------------------------------------------------------------===//
2913//                              Type Operators
2914//===----------------------------------------------------------------------===//
2915
2916CanQualType ASTContext::getCanonicalParamType(QualType T) const {
2917  // Push qualifiers into arrays, and then discard any remaining
2918  // qualifiers.
2919  T = getCanonicalType(T);
2920  T = getVariableArrayDecayedType(T);
2921  const Type *Ty = T.getTypePtr();
2922  QualType Result;
2923  if (isa<ArrayType>(Ty)) {
2924    Result = getArrayDecayedType(QualType(Ty,0));
2925  } else if (isa<FunctionType>(Ty)) {
2926    Result = getPointerType(QualType(Ty, 0));
2927  } else {
2928    Result = QualType(Ty, 0);
2929  }
2930
2931  return CanQualType::CreateUnsafe(Result);
2932}
2933
2934QualType ASTContext::getUnqualifiedArrayType(QualType type,
2935                                             Qualifiers &quals) {
2936  SplitQualType splitType = type.getSplitUnqualifiedType();
2937
2938  // FIXME: getSplitUnqualifiedType() actually walks all the way to
2939  // the unqualified desugared type and then drops it on the floor.
2940  // We then have to strip that sugar back off with
2941  // getUnqualifiedDesugaredType(), which is silly.
2942  const ArrayType *AT =
2943    dyn_cast<ArrayType>(splitType.first->getUnqualifiedDesugaredType());
2944
2945  // If we don't have an array, just use the results in splitType.
2946  if (!AT) {
2947    quals = splitType.second;
2948    return QualType(splitType.first, 0);
2949  }
2950
2951  // Otherwise, recurse on the array's element type.
2952  QualType elementType = AT->getElementType();
2953  QualType unqualElementType = getUnqualifiedArrayType(elementType, quals);
2954
2955  // If that didn't change the element type, AT has no qualifiers, so we
2956  // can just use the results in splitType.
2957  if (elementType == unqualElementType) {
2958    assert(quals.empty()); // from the recursive call
2959    quals = splitType.second;
2960    return QualType(splitType.first, 0);
2961  }
2962
2963  // Otherwise, add in the qualifiers from the outermost type, then
2964  // build the type back up.
2965  quals.addConsistentQualifiers(splitType.second);
2966
2967  if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT)) {
2968    return getConstantArrayType(unqualElementType, CAT->getSize(),
2969                                CAT->getSizeModifier(), 0);
2970  }
2971
2972  if (const IncompleteArrayType *IAT = dyn_cast<IncompleteArrayType>(AT)) {
2973    return getIncompleteArrayType(unqualElementType, IAT->getSizeModifier(), 0);
2974  }
2975
2976  if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(AT)) {
2977    return getVariableArrayType(unqualElementType,
2978                                VAT->getSizeExpr(),
2979                                VAT->getSizeModifier(),
2980                                VAT->getIndexTypeCVRQualifiers(),
2981                                VAT->getBracketsRange());
2982  }
2983
2984  const DependentSizedArrayType *DSAT = cast<DependentSizedArrayType>(AT);
2985  return getDependentSizedArrayType(unqualElementType, DSAT->getSizeExpr(),
2986                                    DSAT->getSizeModifier(), 0,
2987                                    SourceRange());
2988}
2989
2990/// UnwrapSimilarPointerTypes - If T1 and T2 are pointer types  that
2991/// may be similar (C++ 4.4), replaces T1 and T2 with the type that
2992/// they point to and return true. If T1 and T2 aren't pointer types
2993/// or pointer-to-member types, or if they are not similar at this
2994/// level, returns false and leaves T1 and T2 unchanged. Top-level
2995/// qualifiers on T1 and T2 are ignored. This function will typically
2996/// be called in a loop that successively "unwraps" pointer and
2997/// pointer-to-member types to compare them at each level.
2998bool ASTContext::UnwrapSimilarPointerTypes(QualType &T1, QualType &T2) {
2999  const PointerType *T1PtrType = T1->getAs<PointerType>(),
3000                    *T2PtrType = T2->getAs<PointerType>();
3001  if (T1PtrType && T2PtrType) {
3002    T1 = T1PtrType->getPointeeType();
3003    T2 = T2PtrType->getPointeeType();
3004    return true;
3005  }
3006
3007  const MemberPointerType *T1MPType = T1->getAs<MemberPointerType>(),
3008                          *T2MPType = T2->getAs<MemberPointerType>();
3009  if (T1MPType && T2MPType &&
3010      hasSameUnqualifiedType(QualType(T1MPType->getClass(), 0),
3011                             QualType(T2MPType->getClass(), 0))) {
3012    T1 = T1MPType->getPointeeType();
3013    T2 = T2MPType->getPointeeType();
3014    return true;
3015  }
3016
3017  if (getLangOptions().ObjC1) {
3018    const ObjCObjectPointerType *T1OPType = T1->getAs<ObjCObjectPointerType>(),
3019                                *T2OPType = T2->getAs<ObjCObjectPointerType>();
3020    if (T1OPType && T2OPType) {
3021      T1 = T1OPType->getPointeeType();
3022      T2 = T2OPType->getPointeeType();
3023      return true;
3024    }
3025  }
3026
3027  // FIXME: Block pointers, too?
3028
3029  return false;
3030}
3031
3032DeclarationNameInfo
3033ASTContext::getNameForTemplate(TemplateName Name,
3034                               SourceLocation NameLoc) const {
3035  if (TemplateDecl *TD = Name.getAsTemplateDecl())
3036    // DNInfo work in progress: CHECKME: what about DNLoc?
3037    return DeclarationNameInfo(TD->getDeclName(), NameLoc);
3038
3039  if (DependentTemplateName *DTN = Name.getAsDependentTemplateName()) {
3040    DeclarationName DName;
3041    if (DTN->isIdentifier()) {
3042      DName = DeclarationNames.getIdentifier(DTN->getIdentifier());
3043      return DeclarationNameInfo(DName, NameLoc);
3044    } else {
3045      DName = DeclarationNames.getCXXOperatorName(DTN->getOperator());
3046      // DNInfo work in progress: FIXME: source locations?
3047      DeclarationNameLoc DNLoc;
3048      DNLoc.CXXOperatorName.BeginOpNameLoc = SourceLocation().getRawEncoding();
3049      DNLoc.CXXOperatorName.EndOpNameLoc = SourceLocation().getRawEncoding();
3050      return DeclarationNameInfo(DName, NameLoc, DNLoc);
3051    }
3052  }
3053
3054  OverloadedTemplateStorage *Storage = Name.getAsOverloadedTemplate();
3055  assert(Storage);
3056  // DNInfo work in progress: CHECKME: what about DNLoc?
3057  return DeclarationNameInfo((*Storage->begin())->getDeclName(), NameLoc);
3058}
3059
3060TemplateName ASTContext::getCanonicalTemplateName(TemplateName Name) const {
3061  if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
3062    if (TemplateTemplateParmDecl *TTP
3063                              = dyn_cast<TemplateTemplateParmDecl>(Template))
3064      Template = getCanonicalTemplateTemplateParmDecl(TTP);
3065
3066    // The canonical template name is the canonical template declaration.
3067    return TemplateName(cast<TemplateDecl>(Template->getCanonicalDecl()));
3068  }
3069
3070  if (SubstTemplateTemplateParmPackStorage *SubstPack
3071                                  = Name.getAsSubstTemplateTemplateParmPack()) {
3072    TemplateTemplateParmDecl *CanonParam
3073      = getCanonicalTemplateTemplateParmDecl(SubstPack->getParameterPack());
3074    TemplateArgument CanonArgPack
3075      = getCanonicalTemplateArgument(SubstPack->getArgumentPack());
3076    return getSubstTemplateTemplateParmPack(CanonParam, CanonArgPack);
3077  }
3078
3079  assert(!Name.getAsOverloadedTemplate());
3080
3081  DependentTemplateName *DTN = Name.getAsDependentTemplateName();
3082  assert(DTN && "Non-dependent template names must refer to template decls.");
3083  return DTN->CanonicalTemplateName;
3084}
3085
3086bool ASTContext::hasSameTemplateName(TemplateName X, TemplateName Y) {
3087  X = getCanonicalTemplateName(X);
3088  Y = getCanonicalTemplateName(Y);
3089  return X.getAsVoidPointer() == Y.getAsVoidPointer();
3090}
3091
3092TemplateArgument
3093ASTContext::getCanonicalTemplateArgument(const TemplateArgument &Arg) const {
3094  switch (Arg.getKind()) {
3095    case TemplateArgument::Null:
3096      return Arg;
3097
3098    case TemplateArgument::Expression:
3099      return Arg;
3100
3101    case TemplateArgument::Declaration:
3102      return TemplateArgument(Arg.getAsDecl()->getCanonicalDecl());
3103
3104    case TemplateArgument::Template:
3105      return TemplateArgument(getCanonicalTemplateName(Arg.getAsTemplate()));
3106
3107    case TemplateArgument::TemplateExpansion:
3108      return TemplateArgument(getCanonicalTemplateName(
3109                                         Arg.getAsTemplateOrTemplatePattern()),
3110                              Arg.getNumTemplateExpansions());
3111
3112    case TemplateArgument::Integral:
3113      return TemplateArgument(*Arg.getAsIntegral(),
3114                              getCanonicalType(Arg.getIntegralType()));
3115
3116    case TemplateArgument::Type:
3117      return TemplateArgument(getCanonicalType(Arg.getAsType()));
3118
3119    case TemplateArgument::Pack: {
3120      if (Arg.pack_size() == 0)
3121        return Arg;
3122
3123      TemplateArgument *CanonArgs
3124        = new (*this) TemplateArgument[Arg.pack_size()];
3125      unsigned Idx = 0;
3126      for (TemplateArgument::pack_iterator A = Arg.pack_begin(),
3127                                        AEnd = Arg.pack_end();
3128           A != AEnd; (void)++A, ++Idx)
3129        CanonArgs[Idx] = getCanonicalTemplateArgument(*A);
3130
3131      return TemplateArgument(CanonArgs, Arg.pack_size());
3132    }
3133  }
3134
3135  // Silence GCC warning
3136  assert(false && "Unhandled template argument kind");
3137  return TemplateArgument();
3138}
3139
3140NestedNameSpecifier *
3141ASTContext::getCanonicalNestedNameSpecifier(NestedNameSpecifier *NNS) const {
3142  if (!NNS)
3143    return 0;
3144
3145  switch (NNS->getKind()) {
3146  case NestedNameSpecifier::Identifier:
3147    // Canonicalize the prefix but keep the identifier the same.
3148    return NestedNameSpecifier::Create(*this,
3149                         getCanonicalNestedNameSpecifier(NNS->getPrefix()),
3150                                       NNS->getAsIdentifier());
3151
3152  case NestedNameSpecifier::Namespace:
3153    // A namespace is canonical; build a nested-name-specifier with
3154    // this namespace and no prefix.
3155    return NestedNameSpecifier::Create(*this, 0,
3156                                 NNS->getAsNamespace()->getOriginalNamespace());
3157
3158  case NestedNameSpecifier::NamespaceAlias:
3159    // A namespace is canonical; build a nested-name-specifier with
3160    // this namespace and no prefix.
3161    return NestedNameSpecifier::Create(*this, 0,
3162                                    NNS->getAsNamespaceAlias()->getNamespace()
3163                                                      ->getOriginalNamespace());
3164
3165  case NestedNameSpecifier::TypeSpec:
3166  case NestedNameSpecifier::TypeSpecWithTemplate: {
3167    QualType T = getCanonicalType(QualType(NNS->getAsType(), 0));
3168
3169    // If we have some kind of dependent-named type (e.g., "typename T::type"),
3170    // break it apart into its prefix and identifier, then reconsititute those
3171    // as the canonical nested-name-specifier. This is required to canonicalize
3172    // a dependent nested-name-specifier involving typedefs of dependent-name
3173    // types, e.g.,
3174    //   typedef typename T::type T1;
3175    //   typedef typename T1::type T2;
3176    if (const DependentNameType *DNT = T->getAs<DependentNameType>()) {
3177      NestedNameSpecifier *Prefix
3178        = getCanonicalNestedNameSpecifier(DNT->getQualifier());
3179      return NestedNameSpecifier::Create(*this, Prefix,
3180                           const_cast<IdentifierInfo *>(DNT->getIdentifier()));
3181    }
3182
3183    // Do the same thing as above, but with dependent-named specializations.
3184    if (const DependentTemplateSpecializationType *DTST
3185          = T->getAs<DependentTemplateSpecializationType>()) {
3186      NestedNameSpecifier *Prefix
3187        = getCanonicalNestedNameSpecifier(DTST->getQualifier());
3188
3189      T = getDependentTemplateSpecializationType(DTST->getKeyword(),
3190                                                 Prefix, DTST->getIdentifier(),
3191                                                 DTST->getNumArgs(),
3192                                                 DTST->getArgs());
3193      T = getCanonicalType(T);
3194    }
3195
3196    return NestedNameSpecifier::Create(*this, 0, false,
3197                                       const_cast<Type*>(T.getTypePtr()));
3198  }
3199
3200  case NestedNameSpecifier::Global:
3201    // The global specifier is canonical and unique.
3202    return NNS;
3203  }
3204
3205  // Required to silence a GCC warning
3206  return 0;
3207}
3208
3209
3210const ArrayType *ASTContext::getAsArrayType(QualType T) const {
3211  // Handle the non-qualified case efficiently.
3212  if (!T.hasLocalQualifiers()) {
3213    // Handle the common positive case fast.
3214    if (const ArrayType *AT = dyn_cast<ArrayType>(T))
3215      return AT;
3216  }
3217
3218  // Handle the common negative case fast.
3219  if (!isa<ArrayType>(T.getCanonicalType()))
3220    return 0;
3221
3222  // Apply any qualifiers from the array type to the element type.  This
3223  // implements C99 6.7.3p8: "If the specification of an array type includes
3224  // any type qualifiers, the element type is so qualified, not the array type."
3225
3226  // If we get here, we either have type qualifiers on the type, or we have
3227  // sugar such as a typedef in the way.  If we have type qualifiers on the type
3228  // we must propagate them down into the element type.
3229
3230  SplitQualType split = T.getSplitDesugaredType();
3231  Qualifiers qs = split.second;
3232
3233  // If we have a simple case, just return now.
3234  const ArrayType *ATy = dyn_cast<ArrayType>(split.first);
3235  if (ATy == 0 || qs.empty())
3236    return ATy;
3237
3238  // Otherwise, we have an array and we have qualifiers on it.  Push the
3239  // qualifiers into the array element type and return a new array type.
3240  QualType NewEltTy = getQualifiedType(ATy->getElementType(), qs);
3241
3242  if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(ATy))
3243    return cast<ArrayType>(getConstantArrayType(NewEltTy, CAT->getSize(),
3244                                                CAT->getSizeModifier(),
3245                                           CAT->getIndexTypeCVRQualifiers()));
3246  if (const IncompleteArrayType *IAT = dyn_cast<IncompleteArrayType>(ATy))
3247    return cast<ArrayType>(getIncompleteArrayType(NewEltTy,
3248                                                  IAT->getSizeModifier(),
3249                                           IAT->getIndexTypeCVRQualifiers()));
3250
3251  if (const DependentSizedArrayType *DSAT
3252        = dyn_cast<DependentSizedArrayType>(ATy))
3253    return cast<ArrayType>(
3254                     getDependentSizedArrayType(NewEltTy,
3255                                                DSAT->getSizeExpr(),
3256                                                DSAT->getSizeModifier(),
3257                                              DSAT->getIndexTypeCVRQualifiers(),
3258                                                DSAT->getBracketsRange()));
3259
3260  const VariableArrayType *VAT = cast<VariableArrayType>(ATy);
3261  return cast<ArrayType>(getVariableArrayType(NewEltTy,
3262                                              VAT->getSizeExpr(),
3263                                              VAT->getSizeModifier(),
3264                                              VAT->getIndexTypeCVRQualifiers(),
3265                                              VAT->getBracketsRange()));
3266}
3267
3268/// getArrayDecayedType - Return the properly qualified result of decaying the
3269/// specified array type to a pointer.  This operation is non-trivial when
3270/// handling typedefs etc.  The canonical type of "T" must be an array type,
3271/// this returns a pointer to a properly qualified element of the array.
3272///
3273/// See C99 6.7.5.3p7 and C99 6.3.2.1p3.
3274QualType ASTContext::getArrayDecayedType(QualType Ty) const {
3275  // Get the element type with 'getAsArrayType' so that we don't lose any
3276  // typedefs in the element type of the array.  This also handles propagation
3277  // of type qualifiers from the array type into the element type if present
3278  // (C99 6.7.3p8).
3279  const ArrayType *PrettyArrayType = getAsArrayType(Ty);
3280  assert(PrettyArrayType && "Not an array type!");
3281
3282  QualType PtrTy = getPointerType(PrettyArrayType->getElementType());
3283
3284  // int x[restrict 4] ->  int *restrict
3285  return getQualifiedType(PtrTy, PrettyArrayType->getIndexTypeQualifiers());
3286}
3287
3288QualType ASTContext::getBaseElementType(const ArrayType *array) const {
3289  return getBaseElementType(array->getElementType());
3290}
3291
3292QualType ASTContext::getBaseElementType(QualType type) const {
3293  Qualifiers qs;
3294  while (true) {
3295    SplitQualType split = type.getSplitDesugaredType();
3296    const ArrayType *array = split.first->getAsArrayTypeUnsafe();
3297    if (!array) break;
3298
3299    type = array->getElementType();
3300    qs.addConsistentQualifiers(split.second);
3301  }
3302
3303  return getQualifiedType(type, qs);
3304}
3305
3306/// getConstantArrayElementCount - Returns number of constant array elements.
3307uint64_t
3308ASTContext::getConstantArrayElementCount(const ConstantArrayType *CA)  const {
3309  uint64_t ElementCount = 1;
3310  do {
3311    ElementCount *= CA->getSize().getZExtValue();
3312    CA = dyn_cast<ConstantArrayType>(CA->getElementType());
3313  } while (CA);
3314  return ElementCount;
3315}
3316
3317/// getFloatingRank - Return a relative rank for floating point types.
3318/// This routine will assert if passed a built-in type that isn't a float.
3319static FloatingRank getFloatingRank(QualType T) {
3320  if (const ComplexType *CT = T->getAs<ComplexType>())
3321    return getFloatingRank(CT->getElementType());
3322
3323  assert(T->getAs<BuiltinType>() && "getFloatingRank(): not a floating type");
3324  switch (T->getAs<BuiltinType>()->getKind()) {
3325  default: assert(0 && "getFloatingRank(): not a floating type");
3326  case BuiltinType::Float:      return FloatRank;
3327  case BuiltinType::Double:     return DoubleRank;
3328  case BuiltinType::LongDouble: return LongDoubleRank;
3329  }
3330}
3331
3332/// getFloatingTypeOfSizeWithinDomain - Returns a real floating
3333/// point or a complex type (based on typeDomain/typeSize).
3334/// 'typeDomain' is a real floating point or complex type.
3335/// 'typeSize' is a real floating point or complex type.
3336QualType ASTContext::getFloatingTypeOfSizeWithinDomain(QualType Size,
3337                                                       QualType Domain) const {
3338  FloatingRank EltRank = getFloatingRank(Size);
3339  if (Domain->isComplexType()) {
3340    switch (EltRank) {
3341    default: assert(0 && "getFloatingRank(): illegal value for rank");
3342    case FloatRank:      return FloatComplexTy;
3343    case DoubleRank:     return DoubleComplexTy;
3344    case LongDoubleRank: return LongDoubleComplexTy;
3345    }
3346  }
3347
3348  assert(Domain->isRealFloatingType() && "Unknown domain!");
3349  switch (EltRank) {
3350  default: assert(0 && "getFloatingRank(): illegal value for rank");
3351  case FloatRank:      return FloatTy;
3352  case DoubleRank:     return DoubleTy;
3353  case LongDoubleRank: return LongDoubleTy;
3354  }
3355}
3356
3357/// getFloatingTypeOrder - Compare the rank of the two specified floating
3358/// point types, ignoring the domain of the type (i.e. 'double' ==
3359/// '_Complex double').  If LHS > RHS, return 1.  If LHS == RHS, return 0. If
3360/// LHS < RHS, return -1.
3361int ASTContext::getFloatingTypeOrder(QualType LHS, QualType RHS) const {
3362  FloatingRank LHSR = getFloatingRank(LHS);
3363  FloatingRank RHSR = getFloatingRank(RHS);
3364
3365  if (LHSR == RHSR)
3366    return 0;
3367  if (LHSR > RHSR)
3368    return 1;
3369  return -1;
3370}
3371
3372/// getIntegerRank - Return an integer conversion rank (C99 6.3.1.1p1). This
3373/// routine will assert if passed a built-in type that isn't an integer or enum,
3374/// or if it is not canonicalized.
3375unsigned ASTContext::getIntegerRank(const Type *T) const {
3376  assert(T->isCanonicalUnqualified() && "T should be canonicalized");
3377  if (const EnumType* ET = dyn_cast<EnumType>(T))
3378    T = ET->getDecl()->getPromotionType().getTypePtr();
3379
3380  if (T->isSpecificBuiltinType(BuiltinType::WChar_S) ||
3381      T->isSpecificBuiltinType(BuiltinType::WChar_U))
3382    T = getFromTargetType(Target.getWCharType()).getTypePtr();
3383
3384  if (T->isSpecificBuiltinType(BuiltinType::Char16))
3385    T = getFromTargetType(Target.getChar16Type()).getTypePtr();
3386
3387  if (T->isSpecificBuiltinType(BuiltinType::Char32))
3388    T = getFromTargetType(Target.getChar32Type()).getTypePtr();
3389
3390  switch (cast<BuiltinType>(T)->getKind()) {
3391  default: assert(0 && "getIntegerRank(): not a built-in integer");
3392  case BuiltinType::Bool:
3393    return 1 + (getIntWidth(BoolTy) << 3);
3394  case BuiltinType::Char_S:
3395  case BuiltinType::Char_U:
3396  case BuiltinType::SChar:
3397  case BuiltinType::UChar:
3398    return 2 + (getIntWidth(CharTy) << 3);
3399  case BuiltinType::Short:
3400  case BuiltinType::UShort:
3401    return 3 + (getIntWidth(ShortTy) << 3);
3402  case BuiltinType::Int:
3403  case BuiltinType::UInt:
3404    return 4 + (getIntWidth(IntTy) << 3);
3405  case BuiltinType::Long:
3406  case BuiltinType::ULong:
3407    return 5 + (getIntWidth(LongTy) << 3);
3408  case BuiltinType::LongLong:
3409  case BuiltinType::ULongLong:
3410    return 6 + (getIntWidth(LongLongTy) << 3);
3411  case BuiltinType::Int128:
3412  case BuiltinType::UInt128:
3413    return 7 + (getIntWidth(Int128Ty) << 3);
3414  }
3415}
3416
3417/// \brief Whether this is a promotable bitfield reference according
3418/// to C99 6.3.1.1p2, bullet 2 (and GCC extensions).
3419///
3420/// \returns the type this bit-field will promote to, or NULL if no
3421/// promotion occurs.
3422QualType ASTContext::isPromotableBitField(Expr *E) const {
3423  if (E->isTypeDependent() || E->isValueDependent())
3424    return QualType();
3425
3426  FieldDecl *Field = E->getBitField();
3427  if (!Field)
3428    return QualType();
3429
3430  QualType FT = Field->getType();
3431
3432  llvm::APSInt BitWidthAP = Field->getBitWidth()->EvaluateAsInt(*this);
3433  uint64_t BitWidth = BitWidthAP.getZExtValue();
3434  uint64_t IntSize = getTypeSize(IntTy);
3435  // GCC extension compatibility: if the bit-field size is less than or equal
3436  // to the size of int, it gets promoted no matter what its type is.
3437  // For instance, unsigned long bf : 4 gets promoted to signed int.
3438  if (BitWidth < IntSize)
3439    return IntTy;
3440
3441  if (BitWidth == IntSize)
3442    return FT->isSignedIntegerType() ? IntTy : UnsignedIntTy;
3443
3444  // Types bigger than int are not subject to promotions, and therefore act
3445  // like the base type.
3446  // FIXME: This doesn't quite match what gcc does, but what gcc does here
3447  // is ridiculous.
3448  return QualType();
3449}
3450
3451/// getPromotedIntegerType - Returns the type that Promotable will
3452/// promote to: C99 6.3.1.1p2, assuming that Promotable is a promotable
3453/// integer type.
3454QualType ASTContext::getPromotedIntegerType(QualType Promotable) const {
3455  assert(!Promotable.isNull());
3456  assert(Promotable->isPromotableIntegerType());
3457  if (const EnumType *ET = Promotable->getAs<EnumType>())
3458    return ET->getDecl()->getPromotionType();
3459  if (Promotable->isSignedIntegerType())
3460    return IntTy;
3461  uint64_t PromotableSize = getTypeSize(Promotable);
3462  uint64_t IntSize = getTypeSize(IntTy);
3463  assert(Promotable->isUnsignedIntegerType() && PromotableSize <= IntSize);
3464  return (PromotableSize != IntSize) ? IntTy : UnsignedIntTy;
3465}
3466
3467/// getIntegerTypeOrder - Returns the highest ranked integer type:
3468/// C99 6.3.1.8p1.  If LHS > RHS, return 1.  If LHS == RHS, return 0. If
3469/// LHS < RHS, return -1.
3470int ASTContext::getIntegerTypeOrder(QualType LHS, QualType RHS) const {
3471  const Type *LHSC = getCanonicalType(LHS).getTypePtr();
3472  const Type *RHSC = getCanonicalType(RHS).getTypePtr();
3473  if (LHSC == RHSC) return 0;
3474
3475  bool LHSUnsigned = LHSC->isUnsignedIntegerType();
3476  bool RHSUnsigned = RHSC->isUnsignedIntegerType();
3477
3478  unsigned LHSRank = getIntegerRank(LHSC);
3479  unsigned RHSRank = getIntegerRank(RHSC);
3480
3481  if (LHSUnsigned == RHSUnsigned) {  // Both signed or both unsigned.
3482    if (LHSRank == RHSRank) return 0;
3483    return LHSRank > RHSRank ? 1 : -1;
3484  }
3485
3486  // Otherwise, the LHS is signed and the RHS is unsigned or visa versa.
3487  if (LHSUnsigned) {
3488    // If the unsigned [LHS] type is larger, return it.
3489    if (LHSRank >= RHSRank)
3490      return 1;
3491
3492    // If the signed type can represent all values of the unsigned type, it
3493    // wins.  Because we are dealing with 2's complement and types that are
3494    // powers of two larger than each other, this is always safe.
3495    return -1;
3496  }
3497
3498  // If the unsigned [RHS] type is larger, return it.
3499  if (RHSRank >= LHSRank)
3500    return -1;
3501
3502  // If the signed type can represent all values of the unsigned type, it
3503  // wins.  Because we are dealing with 2's complement and types that are
3504  // powers of two larger than each other, this is always safe.
3505  return 1;
3506}
3507
3508static RecordDecl *
3509CreateRecordDecl(const ASTContext &Ctx, RecordDecl::TagKind TK,
3510                 DeclContext *DC, IdentifierInfo *Id) {
3511  SourceLocation Loc;
3512  if (Ctx.getLangOptions().CPlusPlus)
3513    return CXXRecordDecl::Create(Ctx, TK, DC, Loc, Loc, Id);
3514  else
3515    return RecordDecl::Create(Ctx, TK, DC, Loc, Loc, Id);
3516}
3517
3518// getCFConstantStringType - Return the type used for constant CFStrings.
3519QualType ASTContext::getCFConstantStringType() const {
3520  if (!CFConstantStringTypeDecl) {
3521    CFConstantStringTypeDecl =
3522      CreateRecordDecl(*this, TTK_Struct, TUDecl,
3523                       &Idents.get("NSConstantString"));
3524    CFConstantStringTypeDecl->startDefinition();
3525
3526    QualType FieldTypes[4];
3527
3528    // const int *isa;
3529    FieldTypes[0] = getPointerType(IntTy.withConst());
3530    // int flags;
3531    FieldTypes[1] = IntTy;
3532    // const char *str;
3533    FieldTypes[2] = getPointerType(CharTy.withConst());
3534    // long length;
3535    FieldTypes[3] = LongTy;
3536
3537    // Create fields
3538    for (unsigned i = 0; i < 4; ++i) {
3539      FieldDecl *Field = FieldDecl::Create(*this, CFConstantStringTypeDecl,
3540                                           SourceLocation(),
3541                                           SourceLocation(), 0,
3542                                           FieldTypes[i], /*TInfo=*/0,
3543                                           /*BitWidth=*/0,
3544                                           /*Mutable=*/false,
3545                                           /*HasInit=*/false);
3546      Field->setAccess(AS_public);
3547      CFConstantStringTypeDecl->addDecl(Field);
3548    }
3549
3550    CFConstantStringTypeDecl->completeDefinition();
3551  }
3552
3553  return getTagDeclType(CFConstantStringTypeDecl);
3554}
3555
3556void ASTContext::setCFConstantStringType(QualType T) {
3557  const RecordType *Rec = T->getAs<RecordType>();
3558  assert(Rec && "Invalid CFConstantStringType");
3559  CFConstantStringTypeDecl = Rec->getDecl();
3560}
3561
3562// getNSConstantStringType - Return the type used for constant NSStrings.
3563QualType ASTContext::getNSConstantStringType() const {
3564  if (!NSConstantStringTypeDecl) {
3565    NSConstantStringTypeDecl =
3566    CreateRecordDecl(*this, TTK_Struct, TUDecl,
3567                     &Idents.get("__builtin_NSString"));
3568    NSConstantStringTypeDecl->startDefinition();
3569
3570    QualType FieldTypes[3];
3571
3572    // const int *isa;
3573    FieldTypes[0] = getPointerType(IntTy.withConst());
3574    // const char *str;
3575    FieldTypes[1] = getPointerType(CharTy.withConst());
3576    // unsigned int length;
3577    FieldTypes[2] = UnsignedIntTy;
3578
3579    // Create fields
3580    for (unsigned i = 0; i < 3; ++i) {
3581      FieldDecl *Field = FieldDecl::Create(*this, NSConstantStringTypeDecl,
3582                                           SourceLocation(),
3583                                           SourceLocation(), 0,
3584                                           FieldTypes[i], /*TInfo=*/0,
3585                                           /*BitWidth=*/0,
3586                                           /*Mutable=*/false,
3587                                           /*HasInit=*/false);
3588      Field->setAccess(AS_public);
3589      NSConstantStringTypeDecl->addDecl(Field);
3590    }
3591
3592    NSConstantStringTypeDecl->completeDefinition();
3593  }
3594
3595  return getTagDeclType(NSConstantStringTypeDecl);
3596}
3597
3598void ASTContext::setNSConstantStringType(QualType T) {
3599  const RecordType *Rec = T->getAs<RecordType>();
3600  assert(Rec && "Invalid NSConstantStringType");
3601  NSConstantStringTypeDecl = Rec->getDecl();
3602}
3603
3604QualType ASTContext::getObjCFastEnumerationStateType() const {
3605  if (!ObjCFastEnumerationStateTypeDecl) {
3606    ObjCFastEnumerationStateTypeDecl =
3607      CreateRecordDecl(*this, TTK_Struct, TUDecl,
3608                       &Idents.get("__objcFastEnumerationState"));
3609    ObjCFastEnumerationStateTypeDecl->startDefinition();
3610
3611    QualType FieldTypes[] = {
3612      UnsignedLongTy,
3613      getPointerType(ObjCIdTypedefType),
3614      getPointerType(UnsignedLongTy),
3615      getConstantArrayType(UnsignedLongTy,
3616                           llvm::APInt(32, 5), ArrayType::Normal, 0)
3617    };
3618
3619    for (size_t i = 0; i < 4; ++i) {
3620      FieldDecl *Field = FieldDecl::Create(*this,
3621                                           ObjCFastEnumerationStateTypeDecl,
3622                                           SourceLocation(),
3623                                           SourceLocation(), 0,
3624                                           FieldTypes[i], /*TInfo=*/0,
3625                                           /*BitWidth=*/0,
3626                                           /*Mutable=*/false,
3627                                           /*HasInit=*/false);
3628      Field->setAccess(AS_public);
3629      ObjCFastEnumerationStateTypeDecl->addDecl(Field);
3630    }
3631
3632    ObjCFastEnumerationStateTypeDecl->completeDefinition();
3633  }
3634
3635  return getTagDeclType(ObjCFastEnumerationStateTypeDecl);
3636}
3637
3638QualType ASTContext::getBlockDescriptorType() const {
3639  if (BlockDescriptorType)
3640    return getTagDeclType(BlockDescriptorType);
3641
3642  RecordDecl *T;
3643  // FIXME: Needs the FlagAppleBlock bit.
3644  T = CreateRecordDecl(*this, TTK_Struct, TUDecl,
3645                       &Idents.get("__block_descriptor"));
3646  T->startDefinition();
3647
3648  QualType FieldTypes[] = {
3649    UnsignedLongTy,
3650    UnsignedLongTy,
3651  };
3652
3653  const char *FieldNames[] = {
3654    "reserved",
3655    "Size"
3656  };
3657
3658  for (size_t i = 0; i < 2; ++i) {
3659    FieldDecl *Field = FieldDecl::Create(*this, T, SourceLocation(),
3660                                         SourceLocation(),
3661                                         &Idents.get(FieldNames[i]),
3662                                         FieldTypes[i], /*TInfo=*/0,
3663                                         /*BitWidth=*/0,
3664                                         /*Mutable=*/false,
3665                                         /*HasInit=*/false);
3666    Field->setAccess(AS_public);
3667    T->addDecl(Field);
3668  }
3669
3670  T->completeDefinition();
3671
3672  BlockDescriptorType = T;
3673
3674  return getTagDeclType(BlockDescriptorType);
3675}
3676
3677void ASTContext::setBlockDescriptorType(QualType T) {
3678  const RecordType *Rec = T->getAs<RecordType>();
3679  assert(Rec && "Invalid BlockDescriptorType");
3680  BlockDescriptorType = Rec->getDecl();
3681}
3682
3683QualType ASTContext::getBlockDescriptorExtendedType() const {
3684  if (BlockDescriptorExtendedType)
3685    return getTagDeclType(BlockDescriptorExtendedType);
3686
3687  RecordDecl *T;
3688  // FIXME: Needs the FlagAppleBlock bit.
3689  T = CreateRecordDecl(*this, TTK_Struct, TUDecl,
3690                       &Idents.get("__block_descriptor_withcopydispose"));
3691  T->startDefinition();
3692
3693  QualType FieldTypes[] = {
3694    UnsignedLongTy,
3695    UnsignedLongTy,
3696    getPointerType(VoidPtrTy),
3697    getPointerType(VoidPtrTy)
3698  };
3699
3700  const char *FieldNames[] = {
3701    "reserved",
3702    "Size",
3703    "CopyFuncPtr",
3704    "DestroyFuncPtr"
3705  };
3706
3707  for (size_t i = 0; i < 4; ++i) {
3708    FieldDecl *Field = FieldDecl::Create(*this, T, SourceLocation(),
3709                                         SourceLocation(),
3710                                         &Idents.get(FieldNames[i]),
3711                                         FieldTypes[i], /*TInfo=*/0,
3712                                         /*BitWidth=*/0,
3713                                         /*Mutable=*/false,
3714                                         /*HasInit=*/false);
3715    Field->setAccess(AS_public);
3716    T->addDecl(Field);
3717  }
3718
3719  T->completeDefinition();
3720
3721  BlockDescriptorExtendedType = T;
3722
3723  return getTagDeclType(BlockDescriptorExtendedType);
3724}
3725
3726void ASTContext::setBlockDescriptorExtendedType(QualType T) {
3727  const RecordType *Rec = T->getAs<RecordType>();
3728  assert(Rec && "Invalid BlockDescriptorType");
3729  BlockDescriptorExtendedType = Rec->getDecl();
3730}
3731
3732bool ASTContext::BlockRequiresCopying(QualType Ty) const {
3733  if (Ty->isObjCRetainableType())
3734    return true;
3735  if (getLangOptions().CPlusPlus) {
3736    if (const RecordType *RT = Ty->getAs<RecordType>()) {
3737      CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
3738      return RD->hasConstCopyConstructor();
3739
3740    }
3741  }
3742  return false;
3743}
3744
3745QualType
3746ASTContext::BuildByRefType(llvm::StringRef DeclName, QualType Ty) const {
3747  //  type = struct __Block_byref_1_X {
3748  //    void *__isa;
3749  //    struct __Block_byref_1_X *__forwarding;
3750  //    unsigned int __flags;
3751  //    unsigned int __size;
3752  //    void *__copy_helper;            // as needed
3753  //    void *__destroy_help            // as needed
3754  //    int X;
3755  //  } *
3756
3757  bool HasCopyAndDispose = BlockRequiresCopying(Ty);
3758
3759  // FIXME: Move up
3760  llvm::SmallString<36> Name;
3761  llvm::raw_svector_ostream(Name) << "__Block_byref_" <<
3762                                  ++UniqueBlockByRefTypeID << '_' << DeclName;
3763  RecordDecl *T;
3764  T = CreateRecordDecl(*this, TTK_Struct, TUDecl, &Idents.get(Name.str()));
3765  T->startDefinition();
3766  QualType Int32Ty = IntTy;
3767  assert(getIntWidth(IntTy) == 32 && "non-32bit int not supported");
3768  QualType FieldTypes[] = {
3769    getPointerType(VoidPtrTy),
3770    getPointerType(getTagDeclType(T)),
3771    Int32Ty,
3772    Int32Ty,
3773    getPointerType(VoidPtrTy),
3774    getPointerType(VoidPtrTy),
3775    Ty
3776  };
3777
3778  llvm::StringRef FieldNames[] = {
3779    "__isa",
3780    "__forwarding",
3781    "__flags",
3782    "__size",
3783    "__copy_helper",
3784    "__destroy_helper",
3785    DeclName,
3786  };
3787
3788  for (size_t i = 0; i < 7; ++i) {
3789    if (!HasCopyAndDispose && i >=4 && i <= 5)
3790      continue;
3791    FieldDecl *Field = FieldDecl::Create(*this, T, SourceLocation(),
3792                                         SourceLocation(),
3793                                         &Idents.get(FieldNames[i]),
3794                                         FieldTypes[i], /*TInfo=*/0,
3795                                         /*BitWidth=*/0, /*Mutable=*/false,
3796                                         /*HasInit=*/false);
3797    Field->setAccess(AS_public);
3798    T->addDecl(Field);
3799  }
3800
3801  T->completeDefinition();
3802
3803  return getPointerType(getTagDeclType(T));
3804}
3805
3806void ASTContext::setObjCFastEnumerationStateType(QualType T) {
3807  const RecordType *Rec = T->getAs<RecordType>();
3808  assert(Rec && "Invalid ObjCFAstEnumerationStateType");
3809  ObjCFastEnumerationStateTypeDecl = Rec->getDecl();
3810}
3811
3812// This returns true if a type has been typedefed to BOOL:
3813// typedef <type> BOOL;
3814static bool isTypeTypedefedAsBOOL(QualType T) {
3815  if (const TypedefType *TT = dyn_cast<TypedefType>(T))
3816    if (IdentifierInfo *II = TT->getDecl()->getIdentifier())
3817      return II->isStr("BOOL");
3818
3819  return false;
3820}
3821
3822/// getObjCEncodingTypeSize returns size of type for objective-c encoding
3823/// purpose.
3824CharUnits ASTContext::getObjCEncodingTypeSize(QualType type) const {
3825  if (!type->isIncompleteArrayType() && type->isIncompleteType())
3826    return CharUnits::Zero();
3827
3828  CharUnits sz = getTypeSizeInChars(type);
3829
3830  // Make all integer and enum types at least as large as an int
3831  if (sz.isPositive() && type->isIntegralOrEnumerationType())
3832    sz = std::max(sz, getTypeSizeInChars(IntTy));
3833  // Treat arrays as pointers, since that's how they're passed in.
3834  else if (type->isArrayType())
3835    sz = getTypeSizeInChars(VoidPtrTy);
3836  return sz;
3837}
3838
3839static inline
3840std::string charUnitsToString(const CharUnits &CU) {
3841  return llvm::itostr(CU.getQuantity());
3842}
3843
3844/// getObjCEncodingForBlock - Return the encoded type for this block
3845/// declaration.
3846std::string ASTContext::getObjCEncodingForBlock(const BlockExpr *Expr) const {
3847  std::string S;
3848
3849  const BlockDecl *Decl = Expr->getBlockDecl();
3850  QualType BlockTy =
3851      Expr->getType()->getAs<BlockPointerType>()->getPointeeType();
3852  // Encode result type.
3853  getObjCEncodingForType(BlockTy->getAs<FunctionType>()->getResultType(), S);
3854  // Compute size of all parameters.
3855  // Start with computing size of a pointer in number of bytes.
3856  // FIXME: There might(should) be a better way of doing this computation!
3857  SourceLocation Loc;
3858  CharUnits PtrSize = getTypeSizeInChars(VoidPtrTy);
3859  CharUnits ParmOffset = PtrSize;
3860  for (BlockDecl::param_const_iterator PI = Decl->param_begin(),
3861       E = Decl->param_end(); PI != E; ++PI) {
3862    QualType PType = (*PI)->getType();
3863    CharUnits sz = getObjCEncodingTypeSize(PType);
3864    assert (sz.isPositive() && "BlockExpr - Incomplete param type");
3865    ParmOffset += sz;
3866  }
3867  // Size of the argument frame
3868  S += charUnitsToString(ParmOffset);
3869  // Block pointer and offset.
3870  S += "@?0";
3871  ParmOffset = PtrSize;
3872
3873  // Argument types.
3874  ParmOffset = PtrSize;
3875  for (BlockDecl::param_const_iterator PI = Decl->param_begin(), E =
3876       Decl->param_end(); PI != E; ++PI) {
3877    ParmVarDecl *PVDecl = *PI;
3878    QualType PType = PVDecl->getOriginalType();
3879    if (const ArrayType *AT =
3880          dyn_cast<ArrayType>(PType->getCanonicalTypeInternal())) {
3881      // Use array's original type only if it has known number of
3882      // elements.
3883      if (!isa<ConstantArrayType>(AT))
3884        PType = PVDecl->getType();
3885    } else if (PType->isFunctionType())
3886      PType = PVDecl->getType();
3887    getObjCEncodingForType(PType, S);
3888    S += charUnitsToString(ParmOffset);
3889    ParmOffset += getObjCEncodingTypeSize(PType);
3890  }
3891
3892  return S;
3893}
3894
3895bool ASTContext::getObjCEncodingForFunctionDecl(const FunctionDecl *Decl,
3896                                                std::string& S) {
3897  // Encode result type.
3898  getObjCEncodingForType(Decl->getResultType(), S);
3899  CharUnits ParmOffset;
3900  // Compute size of all parameters.
3901  for (FunctionDecl::param_const_iterator PI = Decl->param_begin(),
3902       E = Decl->param_end(); PI != E; ++PI) {
3903    QualType PType = (*PI)->getType();
3904    CharUnits sz = getObjCEncodingTypeSize(PType);
3905    if (sz.isZero())
3906      return true;
3907
3908    assert (sz.isPositive() &&
3909        "getObjCEncodingForFunctionDecl - Incomplete param type");
3910    ParmOffset += sz;
3911  }
3912  S += charUnitsToString(ParmOffset);
3913  ParmOffset = CharUnits::Zero();
3914
3915  // Argument types.
3916  for (FunctionDecl::param_const_iterator PI = Decl->param_begin(),
3917       E = Decl->param_end(); PI != E; ++PI) {
3918    ParmVarDecl *PVDecl = *PI;
3919    QualType PType = PVDecl->getOriginalType();
3920    if (const ArrayType *AT =
3921          dyn_cast<ArrayType>(PType->getCanonicalTypeInternal())) {
3922      // Use array's original type only if it has known number of
3923      // elements.
3924      if (!isa<ConstantArrayType>(AT))
3925        PType = PVDecl->getType();
3926    } else if (PType->isFunctionType())
3927      PType = PVDecl->getType();
3928    getObjCEncodingForType(PType, S);
3929    S += charUnitsToString(ParmOffset);
3930    ParmOffset += getObjCEncodingTypeSize(PType);
3931  }
3932
3933  return false;
3934}
3935
3936/// getObjCEncodingForMethodDecl - Return the encoded type for this method
3937/// declaration.
3938bool ASTContext::getObjCEncodingForMethodDecl(const ObjCMethodDecl *Decl,
3939                                              std::string& S) const {
3940  // FIXME: This is not very efficient.
3941  // Encode type qualifer, 'in', 'inout', etc. for the return type.
3942  getObjCEncodingForTypeQualifier(Decl->getObjCDeclQualifier(), S);
3943  // Encode result type.
3944  getObjCEncodingForType(Decl->getResultType(), S);
3945  // Compute size of all parameters.
3946  // Start with computing size of a pointer in number of bytes.
3947  // FIXME: There might(should) be a better way of doing this computation!
3948  SourceLocation Loc;
3949  CharUnits PtrSize = getTypeSizeInChars(VoidPtrTy);
3950  // The first two arguments (self and _cmd) are pointers; account for
3951  // their size.
3952  CharUnits ParmOffset = 2 * PtrSize;
3953  for (ObjCMethodDecl::param_iterator PI = Decl->param_begin(),
3954       E = Decl->sel_param_end(); PI != E; ++PI) {
3955    QualType PType = (*PI)->getType();
3956    CharUnits sz = getObjCEncodingTypeSize(PType);
3957    if (sz.isZero())
3958      return true;
3959
3960    assert (sz.isPositive() &&
3961        "getObjCEncodingForMethodDecl - Incomplete param type");
3962    ParmOffset += sz;
3963  }
3964  S += charUnitsToString(ParmOffset);
3965  S += "@0:";
3966  S += charUnitsToString(PtrSize);
3967
3968  // Argument types.
3969  ParmOffset = 2 * PtrSize;
3970  for (ObjCMethodDecl::param_iterator PI = Decl->param_begin(),
3971       E = Decl->sel_param_end(); PI != E; ++PI) {
3972    ParmVarDecl *PVDecl = *PI;
3973    QualType PType = PVDecl->getOriginalType();
3974    if (const ArrayType *AT =
3975          dyn_cast<ArrayType>(PType->getCanonicalTypeInternal())) {
3976      // Use array's original type only if it has known number of
3977      // elements.
3978      if (!isa<ConstantArrayType>(AT))
3979        PType = PVDecl->getType();
3980    } else if (PType->isFunctionType())
3981      PType = PVDecl->getType();
3982    // Process argument qualifiers for user supplied arguments; such as,
3983    // 'in', 'inout', etc.
3984    getObjCEncodingForTypeQualifier(PVDecl->getObjCDeclQualifier(), S);
3985    getObjCEncodingForType(PType, S);
3986    S += charUnitsToString(ParmOffset);
3987    ParmOffset += getObjCEncodingTypeSize(PType);
3988  }
3989
3990  return false;
3991}
3992
3993/// getObjCEncodingForPropertyDecl - Return the encoded type for this
3994/// property declaration. If non-NULL, Container must be either an
3995/// ObjCCategoryImplDecl or ObjCImplementationDecl; it should only be
3996/// NULL when getting encodings for protocol properties.
3997/// Property attributes are stored as a comma-delimited C string. The simple
3998/// attributes readonly and bycopy are encoded as single characters. The
3999/// parametrized attributes, getter=name, setter=name, and ivar=name, are
4000/// encoded as single characters, followed by an identifier. Property types
4001/// are also encoded as a parametrized attribute. The characters used to encode
4002/// these attributes are defined by the following enumeration:
4003/// @code
4004/// enum PropertyAttributes {
4005/// kPropertyReadOnly = 'R',   // property is read-only.
4006/// kPropertyBycopy = 'C',     // property is a copy of the value last assigned
4007/// kPropertyByref = '&',  // property is a reference to the value last assigned
4008/// kPropertyDynamic = 'D',    // property is dynamic
4009/// kPropertyGetter = 'G',     // followed by getter selector name
4010/// kPropertySetter = 'S',     // followed by setter selector name
4011/// kPropertyInstanceVariable = 'V'  // followed by instance variable  name
4012/// kPropertyType = 't'              // followed by old-style type encoding.
4013/// kPropertyWeak = 'W'              // 'weak' property
4014/// kPropertyStrong = 'P'            // property GC'able
4015/// kPropertyNonAtomic = 'N'         // property non-atomic
4016/// };
4017/// @endcode
4018void ASTContext::getObjCEncodingForPropertyDecl(const ObjCPropertyDecl *PD,
4019                                                const Decl *Container,
4020                                                std::string& S) const {
4021  // Collect information from the property implementation decl(s).
4022  bool Dynamic = false;
4023  ObjCPropertyImplDecl *SynthesizePID = 0;
4024
4025  // FIXME: Duplicated code due to poor abstraction.
4026  if (Container) {
4027    if (const ObjCCategoryImplDecl *CID =
4028        dyn_cast<ObjCCategoryImplDecl>(Container)) {
4029      for (ObjCCategoryImplDecl::propimpl_iterator
4030             i = CID->propimpl_begin(), e = CID->propimpl_end();
4031           i != e; ++i) {
4032        ObjCPropertyImplDecl *PID = *i;
4033        if (PID->getPropertyDecl() == PD) {
4034          if (PID->getPropertyImplementation()==ObjCPropertyImplDecl::Dynamic) {
4035            Dynamic = true;
4036          } else {
4037            SynthesizePID = PID;
4038          }
4039        }
4040      }
4041    } else {
4042      const ObjCImplementationDecl *OID=cast<ObjCImplementationDecl>(Container);
4043      for (ObjCCategoryImplDecl::propimpl_iterator
4044             i = OID->propimpl_begin(), e = OID->propimpl_end();
4045           i != e; ++i) {
4046        ObjCPropertyImplDecl *PID = *i;
4047        if (PID->getPropertyDecl() == PD) {
4048          if (PID->getPropertyImplementation()==ObjCPropertyImplDecl::Dynamic) {
4049            Dynamic = true;
4050          } else {
4051            SynthesizePID = PID;
4052          }
4053        }
4054      }
4055    }
4056  }
4057
4058  // FIXME: This is not very efficient.
4059  S = "T";
4060
4061  // Encode result type.
4062  // GCC has some special rules regarding encoding of properties which
4063  // closely resembles encoding of ivars.
4064  getObjCEncodingForTypeImpl(PD->getType(), S, true, true, 0,
4065                             true /* outermost type */,
4066                             true /* encoding for property */);
4067
4068  if (PD->isReadOnly()) {
4069    S += ",R";
4070  } else {
4071    switch (PD->getSetterKind()) {
4072    case ObjCPropertyDecl::Assign: break;
4073    case ObjCPropertyDecl::Copy:   S += ",C"; break;
4074    case ObjCPropertyDecl::Retain: S += ",&"; break;
4075    }
4076  }
4077
4078  // It really isn't clear at all what this means, since properties
4079  // are "dynamic by default".
4080  if (Dynamic)
4081    S += ",D";
4082
4083  if (PD->getPropertyAttributes() & ObjCPropertyDecl::OBJC_PR_nonatomic)
4084    S += ",N";
4085
4086  if (PD->getPropertyAttributes() & ObjCPropertyDecl::OBJC_PR_getter) {
4087    S += ",G";
4088    S += PD->getGetterName().getAsString();
4089  }
4090
4091  if (PD->getPropertyAttributes() & ObjCPropertyDecl::OBJC_PR_setter) {
4092    S += ",S";
4093    S += PD->getSetterName().getAsString();
4094  }
4095
4096  if (SynthesizePID) {
4097    const ObjCIvarDecl *OID = SynthesizePID->getPropertyIvarDecl();
4098    S += ",V";
4099    S += OID->getNameAsString();
4100  }
4101
4102  // FIXME: OBJCGC: weak & strong
4103}
4104
4105/// getLegacyIntegralTypeEncoding -
4106/// Another legacy compatibility encoding: 32-bit longs are encoded as
4107/// 'l' or 'L' , but not always.  For typedefs, we need to use
4108/// 'i' or 'I' instead if encoding a struct field, or a pointer!
4109///
4110void ASTContext::getLegacyIntegralTypeEncoding (QualType &PointeeTy) const {
4111  if (isa<TypedefType>(PointeeTy.getTypePtr())) {
4112    if (const BuiltinType *BT = PointeeTy->getAs<BuiltinType>()) {
4113      if (BT->getKind() == BuiltinType::ULong && getIntWidth(PointeeTy) == 32)
4114        PointeeTy = UnsignedIntTy;
4115      else
4116        if (BT->getKind() == BuiltinType::Long && getIntWidth(PointeeTy) == 32)
4117          PointeeTy = IntTy;
4118    }
4119  }
4120}
4121
4122void ASTContext::getObjCEncodingForType(QualType T, std::string& S,
4123                                        const FieldDecl *Field) const {
4124  // We follow the behavior of gcc, expanding structures which are
4125  // directly pointed to, and expanding embedded structures. Note that
4126  // these rules are sufficient to prevent recursive encoding of the
4127  // same type.
4128  getObjCEncodingForTypeImpl(T, S, true, true, Field,
4129                             true /* outermost type */);
4130}
4131
4132static char ObjCEncodingForPrimitiveKind(const ASTContext *C, QualType T) {
4133    switch (T->getAs<BuiltinType>()->getKind()) {
4134    default: assert(0 && "Unhandled builtin type kind");
4135    case BuiltinType::Void:       return 'v';
4136    case BuiltinType::Bool:       return 'B';
4137    case BuiltinType::Char_U:
4138    case BuiltinType::UChar:      return 'C';
4139    case BuiltinType::UShort:     return 'S';
4140    case BuiltinType::UInt:       return 'I';
4141    case BuiltinType::ULong:
4142        return C->getIntWidth(T) == 32 ? 'L' : 'Q';
4143    case BuiltinType::UInt128:    return 'T';
4144    case BuiltinType::ULongLong:  return 'Q';
4145    case BuiltinType::Char_S:
4146    case BuiltinType::SChar:      return 'c';
4147    case BuiltinType::Short:      return 's';
4148    case BuiltinType::WChar_S:
4149    case BuiltinType::WChar_U:
4150    case BuiltinType::Int:        return 'i';
4151    case BuiltinType::Long:
4152      return C->getIntWidth(T) == 32 ? 'l' : 'q';
4153    case BuiltinType::LongLong:   return 'q';
4154    case BuiltinType::Int128:     return 't';
4155    case BuiltinType::Float:      return 'f';
4156    case BuiltinType::Double:     return 'd';
4157    case BuiltinType::LongDouble: return 'D';
4158    }
4159}
4160
4161static void EncodeBitField(const ASTContext *Ctx, std::string& S,
4162                           QualType T, const FieldDecl *FD) {
4163  const Expr *E = FD->getBitWidth();
4164  assert(E && "bitfield width not there - getObjCEncodingForTypeImpl");
4165  S += 'b';
4166  // The NeXT runtime encodes bit fields as b followed by the number of bits.
4167  // The GNU runtime requires more information; bitfields are encoded as b,
4168  // then the offset (in bits) of the first element, then the type of the
4169  // bitfield, then the size in bits.  For example, in this structure:
4170  //
4171  // struct
4172  // {
4173  //    int integer;
4174  //    int flags:2;
4175  // };
4176  // On a 32-bit system, the encoding for flags would be b2 for the NeXT
4177  // runtime, but b32i2 for the GNU runtime.  The reason for this extra
4178  // information is not especially sensible, but we're stuck with it for
4179  // compatibility with GCC, although providing it breaks anything that
4180  // actually uses runtime introspection and wants to work on both runtimes...
4181  if (!Ctx->getLangOptions().NeXTRuntime) {
4182    const RecordDecl *RD = FD->getParent();
4183    const ASTRecordLayout &RL = Ctx->getASTRecordLayout(RD);
4184    // FIXME: This same linear search is also used in ExprConstant - it might
4185    // be better if the FieldDecl stored its offset.  We'd be increasing the
4186    // size of the object slightly, but saving some time every time it is used.
4187    unsigned i = 0;
4188    for (RecordDecl::field_iterator Field = RD->field_begin(),
4189                                 FieldEnd = RD->field_end();
4190         Field != FieldEnd; (void)++Field, ++i) {
4191      if (*Field == FD)
4192        break;
4193    }
4194    S += llvm::utostr(RL.getFieldOffset(i));
4195    if (T->isEnumeralType())
4196      S += 'i';
4197    else
4198      S += ObjCEncodingForPrimitiveKind(Ctx, T);
4199  }
4200  unsigned N = E->EvaluateAsInt(*Ctx).getZExtValue();
4201  S += llvm::utostr(N);
4202}
4203
4204// FIXME: Use SmallString for accumulating string.
4205void ASTContext::getObjCEncodingForTypeImpl(QualType T, std::string& S,
4206                                            bool ExpandPointedToStructures,
4207                                            bool ExpandStructures,
4208                                            const FieldDecl *FD,
4209                                            bool OutermostType,
4210                                            bool EncodingProperty,
4211                                            bool StructField) const {
4212  if (T->getAs<BuiltinType>()) {
4213    if (FD && FD->isBitField())
4214      return EncodeBitField(this, S, T, FD);
4215    S += ObjCEncodingForPrimitiveKind(this, T);
4216    return;
4217  }
4218
4219  if (const ComplexType *CT = T->getAs<ComplexType>()) {
4220    S += 'j';
4221    getObjCEncodingForTypeImpl(CT->getElementType(), S, false, false, 0, false,
4222                               false);
4223    return;
4224  }
4225
4226  // encoding for pointer or r3eference types.
4227  QualType PointeeTy;
4228  if (const PointerType *PT = T->getAs<PointerType>()) {
4229    if (PT->isObjCSelType()) {
4230      S += ':';
4231      return;
4232    }
4233    PointeeTy = PT->getPointeeType();
4234  }
4235  else if (const ReferenceType *RT = T->getAs<ReferenceType>())
4236    PointeeTy = RT->getPointeeType();
4237  if (!PointeeTy.isNull()) {
4238    bool isReadOnly = false;
4239    // For historical/compatibility reasons, the read-only qualifier of the
4240    // pointee gets emitted _before_ the '^'.  The read-only qualifier of
4241    // the pointer itself gets ignored, _unless_ we are looking at a typedef!
4242    // Also, do not emit the 'r' for anything but the outermost type!
4243    if (isa<TypedefType>(T.getTypePtr())) {
4244      if (OutermostType && T.isConstQualified()) {
4245        isReadOnly = true;
4246        S += 'r';
4247      }
4248    } else if (OutermostType) {
4249      QualType P = PointeeTy;
4250      while (P->getAs<PointerType>())
4251        P = P->getAs<PointerType>()->getPointeeType();
4252      if (P.isConstQualified()) {
4253        isReadOnly = true;
4254        S += 'r';
4255      }
4256    }
4257    if (isReadOnly) {
4258      // Another legacy compatibility encoding. Some ObjC qualifier and type
4259      // combinations need to be rearranged.
4260      // Rewrite "in const" from "nr" to "rn"
4261      if (llvm::StringRef(S).endswith("nr"))
4262        S.replace(S.end()-2, S.end(), "rn");
4263    }
4264
4265    if (PointeeTy->isCharType()) {
4266      // char pointer types should be encoded as '*' unless it is a
4267      // type that has been typedef'd to 'BOOL'.
4268      if (!isTypeTypedefedAsBOOL(PointeeTy)) {
4269        S += '*';
4270        return;
4271      }
4272    } else if (const RecordType *RTy = PointeeTy->getAs<RecordType>()) {
4273      // GCC binary compat: Need to convert "struct objc_class *" to "#".
4274      if (RTy->getDecl()->getIdentifier() == &Idents.get("objc_class")) {
4275        S += '#';
4276        return;
4277      }
4278      // GCC binary compat: Need to convert "struct objc_object *" to "@".
4279      if (RTy->getDecl()->getIdentifier() == &Idents.get("objc_object")) {
4280        S += '@';
4281        return;
4282      }
4283      // fall through...
4284    }
4285    S += '^';
4286    getLegacyIntegralTypeEncoding(PointeeTy);
4287
4288    getObjCEncodingForTypeImpl(PointeeTy, S, false, ExpandPointedToStructures,
4289                               NULL);
4290    return;
4291  }
4292
4293  if (const ArrayType *AT =
4294      // Ignore type qualifiers etc.
4295        dyn_cast<ArrayType>(T->getCanonicalTypeInternal())) {
4296    if (isa<IncompleteArrayType>(AT) && !StructField) {
4297      // Incomplete arrays are encoded as a pointer to the array element.
4298      S += '^';
4299
4300      getObjCEncodingForTypeImpl(AT->getElementType(), S,
4301                                 false, ExpandStructures, FD);
4302    } else {
4303      S += '[';
4304
4305      if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT)) {
4306        if (getTypeSize(CAT->getElementType()) == 0)
4307          S += '0';
4308        else
4309          S += llvm::utostr(CAT->getSize().getZExtValue());
4310      } else {
4311        //Variable length arrays are encoded as a regular array with 0 elements.
4312        assert((isa<VariableArrayType>(AT) || isa<IncompleteArrayType>(AT)) &&
4313               "Unknown array type!");
4314        S += '0';
4315      }
4316
4317      getObjCEncodingForTypeImpl(AT->getElementType(), S,
4318                                 false, ExpandStructures, FD);
4319      S += ']';
4320    }
4321    return;
4322  }
4323
4324  if (T->getAs<FunctionType>()) {
4325    S += '?';
4326    return;
4327  }
4328
4329  if (const RecordType *RTy = T->getAs<RecordType>()) {
4330    RecordDecl *RDecl = RTy->getDecl();
4331    S += RDecl->isUnion() ? '(' : '{';
4332    // Anonymous structures print as '?'
4333    if (const IdentifierInfo *II = RDecl->getIdentifier()) {
4334      S += II->getName();
4335      if (ClassTemplateSpecializationDecl *Spec
4336          = dyn_cast<ClassTemplateSpecializationDecl>(RDecl)) {
4337        const TemplateArgumentList &TemplateArgs = Spec->getTemplateArgs();
4338        std::string TemplateArgsStr
4339          = TemplateSpecializationType::PrintTemplateArgumentList(
4340                                            TemplateArgs.data(),
4341                                            TemplateArgs.size(),
4342                                            (*this).PrintingPolicy);
4343
4344        S += TemplateArgsStr;
4345      }
4346    } else {
4347      S += '?';
4348    }
4349    if (ExpandStructures) {
4350      S += '=';
4351      if (!RDecl->isUnion()) {
4352        getObjCEncodingForStructureImpl(RDecl, S, FD);
4353      } else {
4354        for (RecordDecl::field_iterator Field = RDecl->field_begin(),
4355                                     FieldEnd = RDecl->field_end();
4356             Field != FieldEnd; ++Field) {
4357          if (FD) {
4358            S += '"';
4359            S += Field->getNameAsString();
4360            S += '"';
4361          }
4362
4363          // Special case bit-fields.
4364          if (Field->isBitField()) {
4365            getObjCEncodingForTypeImpl(Field->getType(), S, false, true,
4366                                       (*Field));
4367          } else {
4368            QualType qt = Field->getType();
4369            getLegacyIntegralTypeEncoding(qt);
4370            getObjCEncodingForTypeImpl(qt, S, false, true,
4371                                       FD, /*OutermostType*/false,
4372                                       /*EncodingProperty*/false,
4373                                       /*StructField*/true);
4374          }
4375        }
4376      }
4377    }
4378    S += RDecl->isUnion() ? ')' : '}';
4379    return;
4380  }
4381
4382  if (T->isEnumeralType()) {
4383    if (FD && FD->isBitField())
4384      EncodeBitField(this, S, T, FD);
4385    else
4386      S += 'i';
4387    return;
4388  }
4389
4390  if (T->isBlockPointerType()) {
4391    S += "@?"; // Unlike a pointer-to-function, which is "^?".
4392    return;
4393  }
4394
4395  // Ignore protocol qualifiers when mangling at this level.
4396  if (const ObjCObjectType *OT = T->getAs<ObjCObjectType>())
4397    T = OT->getBaseType();
4398
4399  if (const ObjCInterfaceType *OIT = T->getAs<ObjCInterfaceType>()) {
4400    // @encode(class_name)
4401    ObjCInterfaceDecl *OI = OIT->getDecl();
4402    S += '{';
4403    const IdentifierInfo *II = OI->getIdentifier();
4404    S += II->getName();
4405    S += '=';
4406    llvm::SmallVector<ObjCIvarDecl*, 32> Ivars;
4407    DeepCollectObjCIvars(OI, true, Ivars);
4408    for (unsigned i = 0, e = Ivars.size(); i != e; ++i) {
4409      FieldDecl *Field = cast<FieldDecl>(Ivars[i]);
4410      if (Field->isBitField())
4411        getObjCEncodingForTypeImpl(Field->getType(), S, false, true, Field);
4412      else
4413        getObjCEncodingForTypeImpl(Field->getType(), S, false, true, FD);
4414    }
4415    S += '}';
4416    return;
4417  }
4418
4419  if (const ObjCObjectPointerType *OPT = T->getAs<ObjCObjectPointerType>()) {
4420    if (OPT->isObjCIdType()) {
4421      S += '@';
4422      return;
4423    }
4424
4425    if (OPT->isObjCClassType() || OPT->isObjCQualifiedClassType()) {
4426      // FIXME: Consider if we need to output qualifiers for 'Class<p>'.
4427      // Since this is a binary compatibility issue, need to consult with runtime
4428      // folks. Fortunately, this is a *very* obsure construct.
4429      S += '#';
4430      return;
4431    }
4432
4433    if (OPT->isObjCQualifiedIdType()) {
4434      getObjCEncodingForTypeImpl(getObjCIdType(), S,
4435                                 ExpandPointedToStructures,
4436                                 ExpandStructures, FD);
4437      if (FD || EncodingProperty) {
4438        // Note that we do extended encoding of protocol qualifer list
4439        // Only when doing ivar or property encoding.
4440        S += '"';
4441        for (ObjCObjectPointerType::qual_iterator I = OPT->qual_begin(),
4442             E = OPT->qual_end(); I != E; ++I) {
4443          S += '<';
4444          S += (*I)->getNameAsString();
4445          S += '>';
4446        }
4447        S += '"';
4448      }
4449      return;
4450    }
4451
4452    QualType PointeeTy = OPT->getPointeeType();
4453    if (!EncodingProperty &&
4454        isa<TypedefType>(PointeeTy.getTypePtr())) {
4455      // Another historical/compatibility reason.
4456      // We encode the underlying type which comes out as
4457      // {...};
4458      S += '^';
4459      getObjCEncodingForTypeImpl(PointeeTy, S,
4460                                 false, ExpandPointedToStructures,
4461                                 NULL);
4462      return;
4463    }
4464
4465    S += '@';
4466    if (OPT->getInterfaceDecl() && (FD || EncodingProperty)) {
4467      S += '"';
4468      S += OPT->getInterfaceDecl()->getIdentifier()->getName();
4469      for (ObjCObjectPointerType::qual_iterator I = OPT->qual_begin(),
4470           E = OPT->qual_end(); I != E; ++I) {
4471        S += '<';
4472        S += (*I)->getNameAsString();
4473        S += '>';
4474      }
4475      S += '"';
4476    }
4477    return;
4478  }
4479
4480  // gcc just blithely ignores member pointers.
4481  // TODO: maybe there should be a mangling for these
4482  if (T->getAs<MemberPointerType>())
4483    return;
4484
4485  if (T->isVectorType()) {
4486    // This matches gcc's encoding, even though technically it is
4487    // insufficient.
4488    // FIXME. We should do a better job than gcc.
4489    return;
4490  }
4491
4492  assert(0 && "@encode for type not implemented!");
4493}
4494
4495void ASTContext::getObjCEncodingForStructureImpl(RecordDecl *RDecl,
4496                                                 std::string &S,
4497                                                 const FieldDecl *FD,
4498                                                 bool includeVBases) const {
4499  assert(RDecl && "Expected non-null RecordDecl");
4500  assert(!RDecl->isUnion() && "Should not be called for unions");
4501  if (!RDecl->getDefinition())
4502    return;
4503
4504  CXXRecordDecl *CXXRec = dyn_cast<CXXRecordDecl>(RDecl);
4505  std::multimap<uint64_t, NamedDecl *> FieldOrBaseOffsets;
4506  const ASTRecordLayout &layout = getASTRecordLayout(RDecl);
4507
4508  if (CXXRec) {
4509    for (CXXRecordDecl::base_class_iterator
4510           BI = CXXRec->bases_begin(),
4511           BE = CXXRec->bases_end(); BI != BE; ++BI) {
4512      if (!BI->isVirtual()) {
4513        CXXRecordDecl *base = BI->getType()->getAsCXXRecordDecl();
4514        if (base->isEmpty())
4515          continue;
4516        uint64_t offs = layout.getBaseClassOffsetInBits(base);
4517        FieldOrBaseOffsets.insert(FieldOrBaseOffsets.upper_bound(offs),
4518                                  std::make_pair(offs, base));
4519      }
4520    }
4521  }
4522
4523  unsigned i = 0;
4524  for (RecordDecl::field_iterator Field = RDecl->field_begin(),
4525                               FieldEnd = RDecl->field_end();
4526       Field != FieldEnd; ++Field, ++i) {
4527    uint64_t offs = layout.getFieldOffset(i);
4528    FieldOrBaseOffsets.insert(FieldOrBaseOffsets.upper_bound(offs),
4529                              std::make_pair(offs, *Field));
4530  }
4531
4532  if (CXXRec && includeVBases) {
4533    for (CXXRecordDecl::base_class_iterator
4534           BI = CXXRec->vbases_begin(),
4535           BE = CXXRec->vbases_end(); BI != BE; ++BI) {
4536      CXXRecordDecl *base = BI->getType()->getAsCXXRecordDecl();
4537      if (base->isEmpty())
4538        continue;
4539      uint64_t offs = layout.getVBaseClassOffsetInBits(base);
4540      FieldOrBaseOffsets.insert(FieldOrBaseOffsets.upper_bound(offs),
4541                                std::make_pair(offs, base));
4542    }
4543  }
4544
4545  CharUnits size;
4546  if (CXXRec) {
4547    size = includeVBases ? layout.getSize() : layout.getNonVirtualSize();
4548  } else {
4549    size = layout.getSize();
4550  }
4551
4552  uint64_t CurOffs = 0;
4553  std::multimap<uint64_t, NamedDecl *>::iterator
4554    CurLayObj = FieldOrBaseOffsets.begin();
4555
4556  if (CurLayObj != FieldOrBaseOffsets.end() && CurLayObj->first != 0) {
4557    assert(CXXRec && CXXRec->isDynamicClass() &&
4558           "Offset 0 was empty but no VTable ?");
4559    if (FD) {
4560      S += "\"_vptr$";
4561      std::string recname = CXXRec->getNameAsString();
4562      if (recname.empty()) recname = "?";
4563      S += recname;
4564      S += '"';
4565    }
4566    S += "^^?";
4567    CurOffs += getTypeSize(VoidPtrTy);
4568  }
4569
4570  if (!RDecl->hasFlexibleArrayMember()) {
4571    // Mark the end of the structure.
4572    uint64_t offs = toBits(size);
4573    FieldOrBaseOffsets.insert(FieldOrBaseOffsets.upper_bound(offs),
4574                              std::make_pair(offs, (NamedDecl*)0));
4575  }
4576
4577  for (; CurLayObj != FieldOrBaseOffsets.end(); ++CurLayObj) {
4578    assert(CurOffs <= CurLayObj->first);
4579
4580    if (CurOffs < CurLayObj->first) {
4581      uint64_t padding = CurLayObj->first - CurOffs;
4582      // FIXME: There doesn't seem to be a way to indicate in the encoding that
4583      // packing/alignment of members is different that normal, in which case
4584      // the encoding will be out-of-sync with the real layout.
4585      // If the runtime switches to just consider the size of types without
4586      // taking into account alignment, we could make padding explicit in the
4587      // encoding (e.g. using arrays of chars). The encoding strings would be
4588      // longer then though.
4589      CurOffs += padding;
4590    }
4591
4592    NamedDecl *dcl = CurLayObj->second;
4593    if (dcl == 0)
4594      break; // reached end of structure.
4595
4596    if (CXXRecordDecl *base = dyn_cast<CXXRecordDecl>(dcl)) {
4597      // We expand the bases without their virtual bases since those are going
4598      // in the initial structure. Note that this differs from gcc which
4599      // expands virtual bases each time one is encountered in the hierarchy,
4600      // making the encoding type bigger than it really is.
4601      getObjCEncodingForStructureImpl(base, S, FD, /*includeVBases*/false);
4602      assert(!base->isEmpty());
4603      CurOffs += toBits(getASTRecordLayout(base).getNonVirtualSize());
4604    } else {
4605      FieldDecl *field = cast<FieldDecl>(dcl);
4606      if (FD) {
4607        S += '"';
4608        S += field->getNameAsString();
4609        S += '"';
4610      }
4611
4612      if (field->isBitField()) {
4613        EncodeBitField(this, S, field->getType(), field);
4614        CurOffs += field->getBitWidth()->EvaluateAsInt(*this).getZExtValue();
4615      } else {
4616        QualType qt = field->getType();
4617        getLegacyIntegralTypeEncoding(qt);
4618        getObjCEncodingForTypeImpl(qt, S, false, true, FD,
4619                                   /*OutermostType*/false,
4620                                   /*EncodingProperty*/false,
4621                                   /*StructField*/true);
4622        CurOffs += getTypeSize(field->getType());
4623      }
4624    }
4625  }
4626}
4627
4628void ASTContext::getObjCEncodingForTypeQualifier(Decl::ObjCDeclQualifier QT,
4629                                                 std::string& S) const {
4630  if (QT & Decl::OBJC_TQ_In)
4631    S += 'n';
4632  if (QT & Decl::OBJC_TQ_Inout)
4633    S += 'N';
4634  if (QT & Decl::OBJC_TQ_Out)
4635    S += 'o';
4636  if (QT & Decl::OBJC_TQ_Bycopy)
4637    S += 'O';
4638  if (QT & Decl::OBJC_TQ_Byref)
4639    S += 'R';
4640  if (QT & Decl::OBJC_TQ_Oneway)
4641    S += 'V';
4642}
4643
4644void ASTContext::setBuiltinVaListType(QualType T) {
4645  assert(BuiltinVaListType.isNull() && "__builtin_va_list type already set!");
4646
4647  BuiltinVaListType = T;
4648}
4649
4650void ASTContext::setObjCIdType(QualType T) {
4651  ObjCIdTypedefType = T;
4652}
4653
4654void ASTContext::setObjCSelType(QualType T) {
4655  ObjCSelTypedefType = T;
4656}
4657
4658void ASTContext::setObjCProtoType(QualType QT) {
4659  ObjCProtoType = QT;
4660}
4661
4662void ASTContext::setObjCClassType(QualType T) {
4663  ObjCClassTypedefType = T;
4664}
4665
4666void ASTContext::setObjCConstantStringInterface(ObjCInterfaceDecl *Decl) {
4667  assert(ObjCConstantStringType.isNull() &&
4668         "'NSConstantString' type already set!");
4669
4670  ObjCConstantStringType = getObjCInterfaceType(Decl);
4671}
4672
4673/// \brief Retrieve the template name that corresponds to a non-empty
4674/// lookup.
4675TemplateName
4676ASTContext::getOverloadedTemplateName(UnresolvedSetIterator Begin,
4677                                      UnresolvedSetIterator End) const {
4678  unsigned size = End - Begin;
4679  assert(size > 1 && "set is not overloaded!");
4680
4681  void *memory = Allocate(sizeof(OverloadedTemplateStorage) +
4682                          size * sizeof(FunctionTemplateDecl*));
4683  OverloadedTemplateStorage *OT = new(memory) OverloadedTemplateStorage(size);
4684
4685  NamedDecl **Storage = OT->getStorage();
4686  for (UnresolvedSetIterator I = Begin; I != End; ++I) {
4687    NamedDecl *D = *I;
4688    assert(isa<FunctionTemplateDecl>(D) ||
4689           (isa<UsingShadowDecl>(D) &&
4690            isa<FunctionTemplateDecl>(D->getUnderlyingDecl())));
4691    *Storage++ = D;
4692  }
4693
4694  return TemplateName(OT);
4695}
4696
4697/// \brief Retrieve the template name that represents a qualified
4698/// template name such as \c std::vector.
4699TemplateName
4700ASTContext::getQualifiedTemplateName(NestedNameSpecifier *NNS,
4701                                     bool TemplateKeyword,
4702                                     TemplateDecl *Template) const {
4703  assert(NNS && "Missing nested-name-specifier in qualified template name");
4704
4705  // FIXME: Canonicalization?
4706  llvm::FoldingSetNodeID ID;
4707  QualifiedTemplateName::Profile(ID, NNS, TemplateKeyword, Template);
4708
4709  void *InsertPos = 0;
4710  QualifiedTemplateName *QTN =
4711    QualifiedTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4712  if (!QTN) {
4713    QTN = new (*this,4) QualifiedTemplateName(NNS, TemplateKeyword, Template);
4714    QualifiedTemplateNames.InsertNode(QTN, InsertPos);
4715  }
4716
4717  return TemplateName(QTN);
4718}
4719
4720/// \brief Retrieve the template name that represents a dependent
4721/// template name such as \c MetaFun::template apply.
4722TemplateName
4723ASTContext::getDependentTemplateName(NestedNameSpecifier *NNS,
4724                                     const IdentifierInfo *Name) const {
4725  assert((!NNS || NNS->isDependent()) &&
4726         "Nested name specifier must be dependent");
4727
4728  llvm::FoldingSetNodeID ID;
4729  DependentTemplateName::Profile(ID, NNS, Name);
4730
4731  void *InsertPos = 0;
4732  DependentTemplateName *QTN =
4733    DependentTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4734
4735  if (QTN)
4736    return TemplateName(QTN);
4737
4738  NestedNameSpecifier *CanonNNS = getCanonicalNestedNameSpecifier(NNS);
4739  if (CanonNNS == NNS) {
4740    QTN = new (*this,4) DependentTemplateName(NNS, Name);
4741  } else {
4742    TemplateName Canon = getDependentTemplateName(CanonNNS, Name);
4743    QTN = new (*this,4) DependentTemplateName(NNS, Name, Canon);
4744    DependentTemplateName *CheckQTN =
4745      DependentTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4746    assert(!CheckQTN && "Dependent type name canonicalization broken");
4747    (void)CheckQTN;
4748  }
4749
4750  DependentTemplateNames.InsertNode(QTN, InsertPos);
4751  return TemplateName(QTN);
4752}
4753
4754/// \brief Retrieve the template name that represents a dependent
4755/// template name such as \c MetaFun::template operator+.
4756TemplateName
4757ASTContext::getDependentTemplateName(NestedNameSpecifier *NNS,
4758                                     OverloadedOperatorKind Operator) const {
4759  assert((!NNS || NNS->isDependent()) &&
4760         "Nested name specifier must be dependent");
4761
4762  llvm::FoldingSetNodeID ID;
4763  DependentTemplateName::Profile(ID, NNS, Operator);
4764
4765  void *InsertPos = 0;
4766  DependentTemplateName *QTN
4767    = DependentTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4768
4769  if (QTN)
4770    return TemplateName(QTN);
4771
4772  NestedNameSpecifier *CanonNNS = getCanonicalNestedNameSpecifier(NNS);
4773  if (CanonNNS == NNS) {
4774    QTN = new (*this,4) DependentTemplateName(NNS, Operator);
4775  } else {
4776    TemplateName Canon = getDependentTemplateName(CanonNNS, Operator);
4777    QTN = new (*this,4) DependentTemplateName(NNS, Operator, Canon);
4778
4779    DependentTemplateName *CheckQTN
4780      = DependentTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4781    assert(!CheckQTN && "Dependent template name canonicalization broken");
4782    (void)CheckQTN;
4783  }
4784
4785  DependentTemplateNames.InsertNode(QTN, InsertPos);
4786  return TemplateName(QTN);
4787}
4788
4789TemplateName
4790ASTContext::getSubstTemplateTemplateParmPack(TemplateTemplateParmDecl *Param,
4791                                       const TemplateArgument &ArgPack) const {
4792  ASTContext &Self = const_cast<ASTContext &>(*this);
4793  llvm::FoldingSetNodeID ID;
4794  SubstTemplateTemplateParmPackStorage::Profile(ID, Self, Param, ArgPack);
4795
4796  void *InsertPos = 0;
4797  SubstTemplateTemplateParmPackStorage *Subst
4798    = SubstTemplateTemplateParmPacks.FindNodeOrInsertPos(ID, InsertPos);
4799
4800  if (!Subst) {
4801    Subst = new (*this) SubstTemplateTemplateParmPackStorage(Self, Param,
4802                                                           ArgPack.pack_size(),
4803                                                         ArgPack.pack_begin());
4804    SubstTemplateTemplateParmPacks.InsertNode(Subst, InsertPos);
4805  }
4806
4807  return TemplateName(Subst);
4808}
4809
4810/// getFromTargetType - Given one of the integer types provided by
4811/// TargetInfo, produce the corresponding type. The unsigned @p Type
4812/// is actually a value of type @c TargetInfo::IntType.
4813CanQualType ASTContext::getFromTargetType(unsigned Type) const {
4814  switch (Type) {
4815  case TargetInfo::NoInt: return CanQualType();
4816  case TargetInfo::SignedShort: return ShortTy;
4817  case TargetInfo::UnsignedShort: return UnsignedShortTy;
4818  case TargetInfo::SignedInt: return IntTy;
4819  case TargetInfo::UnsignedInt: return UnsignedIntTy;
4820  case TargetInfo::SignedLong: return LongTy;
4821  case TargetInfo::UnsignedLong: return UnsignedLongTy;
4822  case TargetInfo::SignedLongLong: return LongLongTy;
4823  case TargetInfo::UnsignedLongLong: return UnsignedLongLongTy;
4824  }
4825
4826  assert(false && "Unhandled TargetInfo::IntType value");
4827  return CanQualType();
4828}
4829
4830//===----------------------------------------------------------------------===//
4831//                        Type Predicates.
4832//===----------------------------------------------------------------------===//
4833
4834/// getObjCGCAttr - Returns one of GCNone, Weak or Strong objc's
4835/// garbage collection attribute.
4836///
4837Qualifiers::GC ASTContext::getObjCGCAttrKind(QualType Ty) const {
4838  if (getLangOptions().getGCMode() == LangOptions::NonGC)
4839    return Qualifiers::GCNone;
4840
4841  assert(getLangOptions().ObjC1);
4842  Qualifiers::GC GCAttrs = Ty.getObjCGCAttr();
4843
4844  // Default behaviour under objective-C's gc is for ObjC pointers
4845  // (or pointers to them) be treated as though they were declared
4846  // as __strong.
4847  if (GCAttrs == Qualifiers::GCNone) {
4848    if (Ty->isObjCObjectPointerType() || Ty->isBlockPointerType())
4849      return Qualifiers::Strong;
4850    else if (Ty->isPointerType())
4851      return getObjCGCAttrKind(Ty->getAs<PointerType>()->getPointeeType());
4852  } else {
4853    // It's not valid to set GC attributes on anything that isn't a
4854    // pointer.
4855#ifndef NDEBUG
4856    QualType CT = Ty->getCanonicalTypeInternal();
4857    while (const ArrayType *AT = dyn_cast<ArrayType>(CT))
4858      CT = AT->getElementType();
4859    assert(CT->isAnyPointerType() || CT->isBlockPointerType());
4860#endif
4861  }
4862  return GCAttrs;
4863}
4864
4865//===----------------------------------------------------------------------===//
4866//                        Type Compatibility Testing
4867//===----------------------------------------------------------------------===//
4868
4869/// areCompatVectorTypes - Return true if the two specified vector types are
4870/// compatible.
4871static bool areCompatVectorTypes(const VectorType *LHS,
4872                                 const VectorType *RHS) {
4873  assert(LHS->isCanonicalUnqualified() && RHS->isCanonicalUnqualified());
4874  return LHS->getElementType() == RHS->getElementType() &&
4875         LHS->getNumElements() == RHS->getNumElements();
4876}
4877
4878bool ASTContext::areCompatibleVectorTypes(QualType FirstVec,
4879                                          QualType SecondVec) {
4880  assert(FirstVec->isVectorType() && "FirstVec should be a vector type");
4881  assert(SecondVec->isVectorType() && "SecondVec should be a vector type");
4882
4883  if (hasSameUnqualifiedType(FirstVec, SecondVec))
4884    return true;
4885
4886  // Treat Neon vector types and most AltiVec vector types as if they are the
4887  // equivalent GCC vector types.
4888  const VectorType *First = FirstVec->getAs<VectorType>();
4889  const VectorType *Second = SecondVec->getAs<VectorType>();
4890  if (First->getNumElements() == Second->getNumElements() &&
4891      hasSameType(First->getElementType(), Second->getElementType()) &&
4892      First->getVectorKind() != VectorType::AltiVecPixel &&
4893      First->getVectorKind() != VectorType::AltiVecBool &&
4894      Second->getVectorKind() != VectorType::AltiVecPixel &&
4895      Second->getVectorKind() != VectorType::AltiVecBool)
4896    return true;
4897
4898  return false;
4899}
4900
4901//===----------------------------------------------------------------------===//
4902// ObjCQualifiedIdTypesAreCompatible - Compatibility testing for qualified id's.
4903//===----------------------------------------------------------------------===//
4904
4905/// ProtocolCompatibleWithProtocol - return 'true' if 'lProto' is in the
4906/// inheritance hierarchy of 'rProto'.
4907bool
4908ASTContext::ProtocolCompatibleWithProtocol(ObjCProtocolDecl *lProto,
4909                                           ObjCProtocolDecl *rProto) const {
4910  if (lProto == rProto)
4911    return true;
4912  for (ObjCProtocolDecl::protocol_iterator PI = rProto->protocol_begin(),
4913       E = rProto->protocol_end(); PI != E; ++PI)
4914    if (ProtocolCompatibleWithProtocol(lProto, *PI))
4915      return true;
4916  return false;
4917}
4918
4919/// QualifiedIdConformsQualifiedId - compare id<p,...> with id<p1,...>
4920/// return true if lhs's protocols conform to rhs's protocol; false
4921/// otherwise.
4922bool ASTContext::QualifiedIdConformsQualifiedId(QualType lhs, QualType rhs) {
4923  if (lhs->isObjCQualifiedIdType() && rhs->isObjCQualifiedIdType())
4924    return ObjCQualifiedIdTypesAreCompatible(lhs, rhs, false);
4925  return false;
4926}
4927
4928/// ObjCQualifiedClassTypesAreCompatible - compare  Class<p,...> and
4929/// Class<p1, ...>.
4930bool ASTContext::ObjCQualifiedClassTypesAreCompatible(QualType lhs,
4931                                                      QualType rhs) {
4932  const ObjCObjectPointerType *lhsQID = lhs->getAs<ObjCObjectPointerType>();
4933  const ObjCObjectPointerType *rhsOPT = rhs->getAs<ObjCObjectPointerType>();
4934  assert ((lhsQID && rhsOPT) && "ObjCQualifiedClassTypesAreCompatible");
4935
4936  for (ObjCObjectPointerType::qual_iterator I = lhsQID->qual_begin(),
4937       E = lhsQID->qual_end(); I != E; ++I) {
4938    bool match = false;
4939    ObjCProtocolDecl *lhsProto = *I;
4940    for (ObjCObjectPointerType::qual_iterator J = rhsOPT->qual_begin(),
4941         E = rhsOPT->qual_end(); J != E; ++J) {
4942      ObjCProtocolDecl *rhsProto = *J;
4943      if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto)) {
4944        match = true;
4945        break;
4946      }
4947    }
4948    if (!match)
4949      return false;
4950  }
4951  return true;
4952}
4953
4954/// ObjCQualifiedIdTypesAreCompatible - We know that one of lhs/rhs is an
4955/// ObjCQualifiedIDType.
4956bool ASTContext::ObjCQualifiedIdTypesAreCompatible(QualType lhs, QualType rhs,
4957                                                   bool compare) {
4958  // Allow id<P..> and an 'id' or void* type in all cases.
4959  if (lhs->isVoidPointerType() ||
4960      lhs->isObjCIdType() || lhs->isObjCClassType())
4961    return true;
4962  else if (rhs->isVoidPointerType() ||
4963           rhs->isObjCIdType() || rhs->isObjCClassType())
4964    return true;
4965
4966  if (const ObjCObjectPointerType *lhsQID = lhs->getAsObjCQualifiedIdType()) {
4967    const ObjCObjectPointerType *rhsOPT = rhs->getAs<ObjCObjectPointerType>();
4968
4969    if (!rhsOPT) return false;
4970
4971    if (rhsOPT->qual_empty()) {
4972      // If the RHS is a unqualified interface pointer "NSString*",
4973      // make sure we check the class hierarchy.
4974      if (ObjCInterfaceDecl *rhsID = rhsOPT->getInterfaceDecl()) {
4975        for (ObjCObjectPointerType::qual_iterator I = lhsQID->qual_begin(),
4976             E = lhsQID->qual_end(); I != E; ++I) {
4977          // when comparing an id<P> on lhs with a static type on rhs,
4978          // see if static class implements all of id's protocols, directly or
4979          // through its super class and categories.
4980          if (!rhsID->ClassImplementsProtocol(*I, true))
4981            return false;
4982        }
4983      }
4984      // If there are no qualifiers and no interface, we have an 'id'.
4985      return true;
4986    }
4987    // Both the right and left sides have qualifiers.
4988    for (ObjCObjectPointerType::qual_iterator I = lhsQID->qual_begin(),
4989         E = lhsQID->qual_end(); I != E; ++I) {
4990      ObjCProtocolDecl *lhsProto = *I;
4991      bool match = false;
4992
4993      // when comparing an id<P> on lhs with a static type on rhs,
4994      // see if static class implements all of id's protocols, directly or
4995      // through its super class and categories.
4996      for (ObjCObjectPointerType::qual_iterator J = rhsOPT->qual_begin(),
4997           E = rhsOPT->qual_end(); J != E; ++J) {
4998        ObjCProtocolDecl *rhsProto = *J;
4999        if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto) ||
5000            (compare && ProtocolCompatibleWithProtocol(rhsProto, lhsProto))) {
5001          match = true;
5002          break;
5003        }
5004      }
5005      // If the RHS is a qualified interface pointer "NSString<P>*",
5006      // make sure we check the class hierarchy.
5007      if (ObjCInterfaceDecl *rhsID = rhsOPT->getInterfaceDecl()) {
5008        for (ObjCObjectPointerType::qual_iterator I = lhsQID->qual_begin(),
5009             E = lhsQID->qual_end(); I != E; ++I) {
5010          // when comparing an id<P> on lhs with a static type on rhs,
5011          // see if static class implements all of id's protocols, directly or
5012          // through its super class and categories.
5013          if (rhsID->ClassImplementsProtocol(*I, true)) {
5014            match = true;
5015            break;
5016          }
5017        }
5018      }
5019      if (!match)
5020        return false;
5021    }
5022
5023    return true;
5024  }
5025
5026  const ObjCObjectPointerType *rhsQID = rhs->getAsObjCQualifiedIdType();
5027  assert(rhsQID && "One of the LHS/RHS should be id<x>");
5028
5029  if (const ObjCObjectPointerType *lhsOPT =
5030        lhs->getAsObjCInterfacePointerType()) {
5031    // If both the right and left sides have qualifiers.
5032    for (ObjCObjectPointerType::qual_iterator I = lhsOPT->qual_begin(),
5033         E = lhsOPT->qual_end(); I != E; ++I) {
5034      ObjCProtocolDecl *lhsProto = *I;
5035      bool match = false;
5036
5037      // when comparing an id<P> on rhs with a static type on lhs,
5038      // see if static class implements all of id's protocols, directly or
5039      // through its super class and categories.
5040      // First, lhs protocols in the qualifier list must be found, direct
5041      // or indirect in rhs's qualifier list or it is a mismatch.
5042      for (ObjCObjectPointerType::qual_iterator J = rhsQID->qual_begin(),
5043           E = rhsQID->qual_end(); J != E; ++J) {
5044        ObjCProtocolDecl *rhsProto = *J;
5045        if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto) ||
5046            (compare && ProtocolCompatibleWithProtocol(rhsProto, lhsProto))) {
5047          match = true;
5048          break;
5049        }
5050      }
5051      if (!match)
5052        return false;
5053    }
5054
5055    // Static class's protocols, or its super class or category protocols
5056    // must be found, direct or indirect in rhs's qualifier list or it is a mismatch.
5057    if (ObjCInterfaceDecl *lhsID = lhsOPT->getInterfaceDecl()) {
5058      llvm::SmallPtrSet<ObjCProtocolDecl *, 8> LHSInheritedProtocols;
5059      CollectInheritedProtocols(lhsID, LHSInheritedProtocols);
5060      // This is rather dubious but matches gcc's behavior. If lhs has
5061      // no type qualifier and its class has no static protocol(s)
5062      // assume that it is mismatch.
5063      if (LHSInheritedProtocols.empty() && lhsOPT->qual_empty())
5064        return false;
5065      for (llvm::SmallPtrSet<ObjCProtocolDecl*,8>::iterator I =
5066           LHSInheritedProtocols.begin(),
5067           E = LHSInheritedProtocols.end(); I != E; ++I) {
5068        bool match = false;
5069        ObjCProtocolDecl *lhsProto = (*I);
5070        for (ObjCObjectPointerType::qual_iterator J = rhsQID->qual_begin(),
5071             E = rhsQID->qual_end(); J != E; ++J) {
5072          ObjCProtocolDecl *rhsProto = *J;
5073          if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto) ||
5074              (compare && ProtocolCompatibleWithProtocol(rhsProto, lhsProto))) {
5075            match = true;
5076            break;
5077          }
5078        }
5079        if (!match)
5080          return false;
5081      }
5082    }
5083    return true;
5084  }
5085  return false;
5086}
5087
5088/// canAssignObjCInterfaces - Return true if the two interface types are
5089/// compatible for assignment from RHS to LHS.  This handles validation of any
5090/// protocol qualifiers on the LHS or RHS.
5091///
5092bool ASTContext::canAssignObjCInterfaces(const ObjCObjectPointerType *LHSOPT,
5093                                         const ObjCObjectPointerType *RHSOPT) {
5094  const ObjCObjectType* LHS = LHSOPT->getObjectType();
5095  const ObjCObjectType* RHS = RHSOPT->getObjectType();
5096
5097  // If either type represents the built-in 'id' or 'Class' types, return true.
5098  if (LHS->isObjCUnqualifiedIdOrClass() ||
5099      RHS->isObjCUnqualifiedIdOrClass())
5100    return true;
5101
5102  if (LHS->isObjCQualifiedId() || RHS->isObjCQualifiedId())
5103    return ObjCQualifiedIdTypesAreCompatible(QualType(LHSOPT,0),
5104                                             QualType(RHSOPT,0),
5105                                             false);
5106
5107  if (LHS->isObjCQualifiedClass() && RHS->isObjCQualifiedClass())
5108    return ObjCQualifiedClassTypesAreCompatible(QualType(LHSOPT,0),
5109                                                QualType(RHSOPT,0));
5110
5111  // If we have 2 user-defined types, fall into that path.
5112  if (LHS->getInterface() && RHS->getInterface())
5113    return canAssignObjCInterfaces(LHS, RHS);
5114
5115  return false;
5116}
5117
5118/// canAssignObjCInterfacesInBlockPointer - This routine is specifically written
5119/// for providing type-safety for objective-c pointers used to pass/return
5120/// arguments in block literals. When passed as arguments, passing 'A*' where
5121/// 'id' is expected is not OK. Passing 'Sub *" where 'Super *" is expected is
5122/// not OK. For the return type, the opposite is not OK.
5123bool ASTContext::canAssignObjCInterfacesInBlockPointer(
5124                                         const ObjCObjectPointerType *LHSOPT,
5125                                         const ObjCObjectPointerType *RHSOPT,
5126                                         bool BlockReturnType) {
5127  if (RHSOPT->isObjCBuiltinType() || LHSOPT->isObjCIdType())
5128    return true;
5129
5130  if (LHSOPT->isObjCBuiltinType()) {
5131    return RHSOPT->isObjCBuiltinType() || RHSOPT->isObjCQualifiedIdType();
5132  }
5133
5134  if (LHSOPT->isObjCQualifiedIdType() || RHSOPT->isObjCQualifiedIdType())
5135    return ObjCQualifiedIdTypesAreCompatible(QualType(LHSOPT,0),
5136                                             QualType(RHSOPT,0),
5137                                             false);
5138
5139  const ObjCInterfaceType* LHS = LHSOPT->getInterfaceType();
5140  const ObjCInterfaceType* RHS = RHSOPT->getInterfaceType();
5141  if (LHS && RHS)  { // We have 2 user-defined types.
5142    if (LHS != RHS) {
5143      if (LHS->getDecl()->isSuperClassOf(RHS->getDecl()))
5144        return BlockReturnType;
5145      if (RHS->getDecl()->isSuperClassOf(LHS->getDecl()))
5146        return !BlockReturnType;
5147    }
5148    else
5149      return true;
5150  }
5151  return false;
5152}
5153
5154/// getIntersectionOfProtocols - This routine finds the intersection of set
5155/// of protocols inherited from two distinct objective-c pointer objects.
5156/// It is used to build composite qualifier list of the composite type of
5157/// the conditional expression involving two objective-c pointer objects.
5158static
5159void getIntersectionOfProtocols(ASTContext &Context,
5160                                const ObjCObjectPointerType *LHSOPT,
5161                                const ObjCObjectPointerType *RHSOPT,
5162      llvm::SmallVectorImpl<ObjCProtocolDecl *> &IntersectionOfProtocols) {
5163
5164  const ObjCObjectType* LHS = LHSOPT->getObjectType();
5165  const ObjCObjectType* RHS = RHSOPT->getObjectType();
5166  assert(LHS->getInterface() && "LHS must have an interface base");
5167  assert(RHS->getInterface() && "RHS must have an interface base");
5168
5169  llvm::SmallPtrSet<ObjCProtocolDecl *, 8> InheritedProtocolSet;
5170  unsigned LHSNumProtocols = LHS->getNumProtocols();
5171  if (LHSNumProtocols > 0)
5172    InheritedProtocolSet.insert(LHS->qual_begin(), LHS->qual_end());
5173  else {
5174    llvm::SmallPtrSet<ObjCProtocolDecl *, 8> LHSInheritedProtocols;
5175    Context.CollectInheritedProtocols(LHS->getInterface(),
5176                                      LHSInheritedProtocols);
5177    InheritedProtocolSet.insert(LHSInheritedProtocols.begin(),
5178                                LHSInheritedProtocols.end());
5179  }
5180
5181  unsigned RHSNumProtocols = RHS->getNumProtocols();
5182  if (RHSNumProtocols > 0) {
5183    ObjCProtocolDecl **RHSProtocols =
5184      const_cast<ObjCProtocolDecl **>(RHS->qual_begin());
5185    for (unsigned i = 0; i < RHSNumProtocols; ++i)
5186      if (InheritedProtocolSet.count(RHSProtocols[i]))
5187        IntersectionOfProtocols.push_back(RHSProtocols[i]);
5188  }
5189  else {
5190    llvm::SmallPtrSet<ObjCProtocolDecl *, 8> RHSInheritedProtocols;
5191    Context.CollectInheritedProtocols(RHS->getInterface(),
5192                                      RHSInheritedProtocols);
5193    for (llvm::SmallPtrSet<ObjCProtocolDecl*,8>::iterator I =
5194         RHSInheritedProtocols.begin(),
5195         E = RHSInheritedProtocols.end(); I != E; ++I)
5196      if (InheritedProtocolSet.count((*I)))
5197        IntersectionOfProtocols.push_back((*I));
5198  }
5199}
5200
5201/// areCommonBaseCompatible - Returns common base class of the two classes if
5202/// one found. Note that this is O'2 algorithm. But it will be called as the
5203/// last type comparison in a ?-exp of ObjC pointer types before a
5204/// warning is issued. So, its invokation is extremely rare.
5205QualType ASTContext::areCommonBaseCompatible(
5206                                          const ObjCObjectPointerType *Lptr,
5207                                          const ObjCObjectPointerType *Rptr) {
5208  const ObjCObjectType *LHS = Lptr->getObjectType();
5209  const ObjCObjectType *RHS = Rptr->getObjectType();
5210  const ObjCInterfaceDecl* LDecl = LHS->getInterface();
5211  const ObjCInterfaceDecl* RDecl = RHS->getInterface();
5212  if (!LDecl || !RDecl || (LDecl == RDecl))
5213    return QualType();
5214
5215  do {
5216    LHS = cast<ObjCInterfaceType>(getObjCInterfaceType(LDecl));
5217    if (canAssignObjCInterfaces(LHS, RHS)) {
5218      llvm::SmallVector<ObjCProtocolDecl *, 8> Protocols;
5219      getIntersectionOfProtocols(*this, Lptr, Rptr, Protocols);
5220
5221      QualType Result = QualType(LHS, 0);
5222      if (!Protocols.empty())
5223        Result = getObjCObjectType(Result, Protocols.data(), Protocols.size());
5224      Result = getObjCObjectPointerType(Result);
5225      return Result;
5226    }
5227  } while ((LDecl = LDecl->getSuperClass()));
5228
5229  return QualType();
5230}
5231
5232bool ASTContext::canAssignObjCInterfaces(const ObjCObjectType *LHS,
5233                                         const ObjCObjectType *RHS) {
5234  assert(LHS->getInterface() && "LHS is not an interface type");
5235  assert(RHS->getInterface() && "RHS is not an interface type");
5236
5237  // Verify that the base decls are compatible: the RHS must be a subclass of
5238  // the LHS.
5239  if (!LHS->getInterface()->isSuperClassOf(RHS->getInterface()))
5240    return false;
5241
5242  // RHS must have a superset of the protocols in the LHS.  If the LHS is not
5243  // protocol qualified at all, then we are good.
5244  if (LHS->getNumProtocols() == 0)
5245    return true;
5246
5247  // Okay, we know the LHS has protocol qualifiers.  If the RHS doesn't,
5248  // more detailed analysis is required.
5249  if (RHS->getNumProtocols() == 0) {
5250    // OK, if LHS is a superclass of RHS *and*
5251    // this superclass is assignment compatible with LHS.
5252    // false otherwise.
5253    bool IsSuperClass =
5254      LHS->getInterface()->isSuperClassOf(RHS->getInterface());
5255    if (IsSuperClass) {
5256      // OK if conversion of LHS to SuperClass results in narrowing of types
5257      // ; i.e., SuperClass may implement at least one of the protocols
5258      // in LHS's protocol list. Example, SuperObj<P1> = lhs<P1,P2> is ok.
5259      // But not SuperObj<P1,P2,P3> = lhs<P1,P2>.
5260      llvm::SmallPtrSet<ObjCProtocolDecl *, 8> SuperClassInheritedProtocols;
5261      CollectInheritedProtocols(RHS->getInterface(), SuperClassInheritedProtocols);
5262      // If super class has no protocols, it is not a match.
5263      if (SuperClassInheritedProtocols.empty())
5264        return false;
5265
5266      for (ObjCObjectType::qual_iterator LHSPI = LHS->qual_begin(),
5267           LHSPE = LHS->qual_end();
5268           LHSPI != LHSPE; LHSPI++) {
5269        bool SuperImplementsProtocol = false;
5270        ObjCProtocolDecl *LHSProto = (*LHSPI);
5271
5272        for (llvm::SmallPtrSet<ObjCProtocolDecl*,8>::iterator I =
5273             SuperClassInheritedProtocols.begin(),
5274             E = SuperClassInheritedProtocols.end(); I != E; ++I) {
5275          ObjCProtocolDecl *SuperClassProto = (*I);
5276          if (SuperClassProto->lookupProtocolNamed(LHSProto->getIdentifier())) {
5277            SuperImplementsProtocol = true;
5278            break;
5279          }
5280        }
5281        if (!SuperImplementsProtocol)
5282          return false;
5283      }
5284      return true;
5285    }
5286    return false;
5287  }
5288
5289  for (ObjCObjectType::qual_iterator LHSPI = LHS->qual_begin(),
5290                                     LHSPE = LHS->qual_end();
5291       LHSPI != LHSPE; LHSPI++) {
5292    bool RHSImplementsProtocol = false;
5293
5294    // If the RHS doesn't implement the protocol on the left, the types
5295    // are incompatible.
5296    for (ObjCObjectType::qual_iterator RHSPI = RHS->qual_begin(),
5297                                       RHSPE = RHS->qual_end();
5298         RHSPI != RHSPE; RHSPI++) {
5299      if ((*RHSPI)->lookupProtocolNamed((*LHSPI)->getIdentifier())) {
5300        RHSImplementsProtocol = true;
5301        break;
5302      }
5303    }
5304    // FIXME: For better diagnostics, consider passing back the protocol name.
5305    if (!RHSImplementsProtocol)
5306      return false;
5307  }
5308  // The RHS implements all protocols listed on the LHS.
5309  return true;
5310}
5311
5312bool ASTContext::areComparableObjCPointerTypes(QualType LHS, QualType RHS) {
5313  // get the "pointed to" types
5314  const ObjCObjectPointerType *LHSOPT = LHS->getAs<ObjCObjectPointerType>();
5315  const ObjCObjectPointerType *RHSOPT = RHS->getAs<ObjCObjectPointerType>();
5316
5317  if (!LHSOPT || !RHSOPT)
5318    return false;
5319
5320  return canAssignObjCInterfaces(LHSOPT, RHSOPT) ||
5321         canAssignObjCInterfaces(RHSOPT, LHSOPT);
5322}
5323
5324bool ASTContext::canBindObjCObjectType(QualType To, QualType From) {
5325  return canAssignObjCInterfaces(
5326                getObjCObjectPointerType(To)->getAs<ObjCObjectPointerType>(),
5327                getObjCObjectPointerType(From)->getAs<ObjCObjectPointerType>());
5328}
5329
5330/// typesAreCompatible - C99 6.7.3p9: For two qualified types to be compatible,
5331/// both shall have the identically qualified version of a compatible type.
5332/// C99 6.2.7p1: Two types have compatible types if their types are the
5333/// same. See 6.7.[2,3,5] for additional rules.
5334bool ASTContext::typesAreCompatible(QualType LHS, QualType RHS,
5335                                    bool CompareUnqualified) {
5336  if (getLangOptions().CPlusPlus)
5337    return hasSameType(LHS, RHS);
5338
5339  return !mergeTypes(LHS, RHS, false, CompareUnqualified).isNull();
5340}
5341
5342bool ASTContext::typesAreBlockPointerCompatible(QualType LHS, QualType RHS) {
5343  return !mergeTypes(LHS, RHS, true).isNull();
5344}
5345
5346/// mergeTransparentUnionType - if T is a transparent union type and a member
5347/// of T is compatible with SubType, return the merged type, else return
5348/// QualType()
5349QualType ASTContext::mergeTransparentUnionType(QualType T, QualType SubType,
5350                                               bool OfBlockPointer,
5351                                               bool Unqualified) {
5352  if (const RecordType *UT = T->getAsUnionType()) {
5353    RecordDecl *UD = UT->getDecl();
5354    if (UD->hasAttr<TransparentUnionAttr>()) {
5355      for (RecordDecl::field_iterator it = UD->field_begin(),
5356           itend = UD->field_end(); it != itend; ++it) {
5357        QualType ET = it->getType().getUnqualifiedType();
5358        QualType MT = mergeTypes(ET, SubType, OfBlockPointer, Unqualified);
5359        if (!MT.isNull())
5360          return MT;
5361      }
5362    }
5363  }
5364
5365  return QualType();
5366}
5367
5368/// mergeFunctionArgumentTypes - merge two types which appear as function
5369/// argument types
5370QualType ASTContext::mergeFunctionArgumentTypes(QualType lhs, QualType rhs,
5371                                                bool OfBlockPointer,
5372                                                bool Unqualified) {
5373  // GNU extension: two types are compatible if they appear as a function
5374  // argument, one of the types is a transparent union type and the other
5375  // type is compatible with a union member
5376  QualType lmerge = mergeTransparentUnionType(lhs, rhs, OfBlockPointer,
5377                                              Unqualified);
5378  if (!lmerge.isNull())
5379    return lmerge;
5380
5381  QualType rmerge = mergeTransparentUnionType(rhs, lhs, OfBlockPointer,
5382                                              Unqualified);
5383  if (!rmerge.isNull())
5384    return rmerge;
5385
5386  return mergeTypes(lhs, rhs, OfBlockPointer, Unqualified);
5387}
5388
5389QualType ASTContext::mergeFunctionTypes(QualType lhs, QualType rhs,
5390                                        bool OfBlockPointer,
5391                                        bool Unqualified) {
5392  const FunctionType *lbase = lhs->getAs<FunctionType>();
5393  const FunctionType *rbase = rhs->getAs<FunctionType>();
5394  const FunctionProtoType *lproto = dyn_cast<FunctionProtoType>(lbase);
5395  const FunctionProtoType *rproto = dyn_cast<FunctionProtoType>(rbase);
5396  bool allLTypes = true;
5397  bool allRTypes = true;
5398
5399  // Check return type
5400  QualType retType;
5401  if (OfBlockPointer) {
5402    QualType RHS = rbase->getResultType();
5403    QualType LHS = lbase->getResultType();
5404    bool UnqualifiedResult = Unqualified;
5405    if (!UnqualifiedResult)
5406      UnqualifiedResult = (!RHS.hasQualifiers() && LHS.hasQualifiers());
5407    retType = mergeTypes(LHS, RHS, true, UnqualifiedResult, true);
5408  }
5409  else
5410    retType = mergeTypes(lbase->getResultType(), rbase->getResultType(), false,
5411                         Unqualified);
5412  if (retType.isNull()) return QualType();
5413
5414  if (Unqualified)
5415    retType = retType.getUnqualifiedType();
5416
5417  CanQualType LRetType = getCanonicalType(lbase->getResultType());
5418  CanQualType RRetType = getCanonicalType(rbase->getResultType());
5419  if (Unqualified) {
5420    LRetType = LRetType.getUnqualifiedType();
5421    RRetType = RRetType.getUnqualifiedType();
5422  }
5423
5424  if (getCanonicalType(retType) != LRetType)
5425    allLTypes = false;
5426  if (getCanonicalType(retType) != RRetType)
5427    allRTypes = false;
5428
5429  // FIXME: double check this
5430  // FIXME: should we error if lbase->getRegParmAttr() != 0 &&
5431  //                           rbase->getRegParmAttr() != 0 &&
5432  //                           lbase->getRegParmAttr() != rbase->getRegParmAttr()?
5433  FunctionType::ExtInfo lbaseInfo = lbase->getExtInfo();
5434  FunctionType::ExtInfo rbaseInfo = rbase->getExtInfo();
5435
5436  // Compatible functions must have compatible calling conventions
5437  if (!isSameCallConv(lbaseInfo.getCC(), rbaseInfo.getCC()))
5438    return QualType();
5439
5440  // Regparm is part of the calling convention.
5441  if (lbaseInfo.getHasRegParm() != rbaseInfo.getHasRegParm())
5442    return QualType();
5443  if (lbaseInfo.getRegParm() != rbaseInfo.getRegParm())
5444    return QualType();
5445
5446  if (lbaseInfo.getProducesResult() != rbaseInfo.getProducesResult())
5447    return QualType();
5448
5449  // It's noreturn if either type is.
5450  // FIXME: some uses, e.g. conditional exprs, really want this to be 'both'.
5451  bool NoReturn = lbaseInfo.getNoReturn() || rbaseInfo.getNoReturn();
5452  if (NoReturn != lbaseInfo.getNoReturn())
5453    allLTypes = false;
5454  if (NoReturn != rbaseInfo.getNoReturn())
5455    allRTypes = false;
5456
5457  FunctionType::ExtInfo einfo = lbaseInfo.withNoReturn(NoReturn);
5458
5459  if (lproto && rproto) { // two C99 style function prototypes
5460    assert(!lproto->hasExceptionSpec() && !rproto->hasExceptionSpec() &&
5461           "C++ shouldn't be here");
5462    unsigned lproto_nargs = lproto->getNumArgs();
5463    unsigned rproto_nargs = rproto->getNumArgs();
5464
5465    // Compatible functions must have the same number of arguments
5466    if (lproto_nargs != rproto_nargs)
5467      return QualType();
5468
5469    // Variadic and non-variadic functions aren't compatible
5470    if (lproto->isVariadic() != rproto->isVariadic())
5471      return QualType();
5472
5473    if (lproto->getTypeQuals() != rproto->getTypeQuals())
5474      return QualType();
5475
5476    // Check argument compatibility
5477    llvm::SmallVector<QualType, 10> types;
5478    for (unsigned i = 0; i < lproto_nargs; i++) {
5479      QualType largtype = lproto->getArgType(i).getUnqualifiedType();
5480      QualType rargtype = rproto->getArgType(i).getUnqualifiedType();
5481      QualType argtype = mergeFunctionArgumentTypes(largtype, rargtype,
5482                                                    OfBlockPointer,
5483                                                    Unqualified);
5484      if (argtype.isNull()) return QualType();
5485
5486      if (Unqualified)
5487        argtype = argtype.getUnqualifiedType();
5488
5489      types.push_back(argtype);
5490      if (Unqualified) {
5491        largtype = largtype.getUnqualifiedType();
5492        rargtype = rargtype.getUnqualifiedType();
5493      }
5494
5495      if (getCanonicalType(argtype) != getCanonicalType(largtype))
5496        allLTypes = false;
5497      if (getCanonicalType(argtype) != getCanonicalType(rargtype))
5498        allRTypes = false;
5499    }
5500    if (allLTypes) return lhs;
5501    if (allRTypes) return rhs;
5502
5503    FunctionProtoType::ExtProtoInfo EPI = lproto->getExtProtoInfo();
5504    EPI.ExtInfo = einfo;
5505    return getFunctionType(retType, types.begin(), types.size(), EPI);
5506  }
5507
5508  if (lproto) allRTypes = false;
5509  if (rproto) allLTypes = false;
5510
5511  const FunctionProtoType *proto = lproto ? lproto : rproto;
5512  if (proto) {
5513    assert(!proto->hasExceptionSpec() && "C++ shouldn't be here");
5514    if (proto->isVariadic()) return QualType();
5515    // Check that the types are compatible with the types that
5516    // would result from default argument promotions (C99 6.7.5.3p15).
5517    // The only types actually affected are promotable integer
5518    // types and floats, which would be passed as a different
5519    // type depending on whether the prototype is visible.
5520    unsigned proto_nargs = proto->getNumArgs();
5521    for (unsigned i = 0; i < proto_nargs; ++i) {
5522      QualType argTy = proto->getArgType(i);
5523
5524      // Look at the promotion type of enum types, since that is the type used
5525      // to pass enum values.
5526      if (const EnumType *Enum = argTy->getAs<EnumType>())
5527        argTy = Enum->getDecl()->getPromotionType();
5528
5529      if (argTy->isPromotableIntegerType() ||
5530          getCanonicalType(argTy).getUnqualifiedType() == FloatTy)
5531        return QualType();
5532    }
5533
5534    if (allLTypes) return lhs;
5535    if (allRTypes) return rhs;
5536
5537    FunctionProtoType::ExtProtoInfo EPI = proto->getExtProtoInfo();
5538    EPI.ExtInfo = einfo;
5539    return getFunctionType(retType, proto->arg_type_begin(),
5540                           proto->getNumArgs(), EPI);
5541  }
5542
5543  if (allLTypes) return lhs;
5544  if (allRTypes) return rhs;
5545  return getFunctionNoProtoType(retType, einfo);
5546}
5547
5548QualType ASTContext::mergeTypes(QualType LHS, QualType RHS,
5549                                bool OfBlockPointer,
5550                                bool Unqualified, bool BlockReturnType) {
5551  // C++ [expr]: If an expression initially has the type "reference to T", the
5552  // type is adjusted to "T" prior to any further analysis, the expression
5553  // designates the object or function denoted by the reference, and the
5554  // expression is an lvalue unless the reference is an rvalue reference and
5555  // the expression is a function call (possibly inside parentheses).
5556  assert(!LHS->getAs<ReferenceType>() && "LHS is a reference type?");
5557  assert(!RHS->getAs<ReferenceType>() && "RHS is a reference type?");
5558
5559  if (Unqualified) {
5560    LHS = LHS.getUnqualifiedType();
5561    RHS = RHS.getUnqualifiedType();
5562  }
5563
5564  QualType LHSCan = getCanonicalType(LHS),
5565           RHSCan = getCanonicalType(RHS);
5566
5567  // If two types are identical, they are compatible.
5568  if (LHSCan == RHSCan)
5569    return LHS;
5570
5571  // If the qualifiers are different, the types aren't compatible... mostly.
5572  Qualifiers LQuals = LHSCan.getLocalQualifiers();
5573  Qualifiers RQuals = RHSCan.getLocalQualifiers();
5574  if (LQuals != RQuals) {
5575    // If any of these qualifiers are different, we have a type
5576    // mismatch.
5577    if (LQuals.getCVRQualifiers() != RQuals.getCVRQualifiers() ||
5578        LQuals.getAddressSpace() != RQuals.getAddressSpace() ||
5579        LQuals.getObjCLifetime() != RQuals.getObjCLifetime())
5580      return QualType();
5581
5582    // Exactly one GC qualifier difference is allowed: __strong is
5583    // okay if the other type has no GC qualifier but is an Objective
5584    // C object pointer (i.e. implicitly strong by default).  We fix
5585    // this by pretending that the unqualified type was actually
5586    // qualified __strong.
5587    Qualifiers::GC GC_L = LQuals.getObjCGCAttr();
5588    Qualifiers::GC GC_R = RQuals.getObjCGCAttr();
5589    assert((GC_L != GC_R) && "unequal qualifier sets had only equal elements");
5590
5591    if (GC_L == Qualifiers::Weak || GC_R == Qualifiers::Weak)
5592      return QualType();
5593
5594    if (GC_L == Qualifiers::Strong && RHSCan->isObjCObjectPointerType()) {
5595      return mergeTypes(LHS, getObjCGCQualType(RHS, Qualifiers::Strong));
5596    }
5597    if (GC_R == Qualifiers::Strong && LHSCan->isObjCObjectPointerType()) {
5598      return mergeTypes(getObjCGCQualType(LHS, Qualifiers::Strong), RHS);
5599    }
5600    return QualType();
5601  }
5602
5603  // Okay, qualifiers are equal.
5604
5605  Type::TypeClass LHSClass = LHSCan->getTypeClass();
5606  Type::TypeClass RHSClass = RHSCan->getTypeClass();
5607
5608  // We want to consider the two function types to be the same for these
5609  // comparisons, just force one to the other.
5610  if (LHSClass == Type::FunctionProto) LHSClass = Type::FunctionNoProto;
5611  if (RHSClass == Type::FunctionProto) RHSClass = Type::FunctionNoProto;
5612
5613  // Same as above for arrays
5614  if (LHSClass == Type::VariableArray || LHSClass == Type::IncompleteArray)
5615    LHSClass = Type::ConstantArray;
5616  if (RHSClass == Type::VariableArray || RHSClass == Type::IncompleteArray)
5617    RHSClass = Type::ConstantArray;
5618
5619  // ObjCInterfaces are just specialized ObjCObjects.
5620  if (LHSClass == Type::ObjCInterface) LHSClass = Type::ObjCObject;
5621  if (RHSClass == Type::ObjCInterface) RHSClass = Type::ObjCObject;
5622
5623  // Canonicalize ExtVector -> Vector.
5624  if (LHSClass == Type::ExtVector) LHSClass = Type::Vector;
5625  if (RHSClass == Type::ExtVector) RHSClass = Type::Vector;
5626
5627  // If the canonical type classes don't match.
5628  if (LHSClass != RHSClass) {
5629    // C99 6.7.2.2p4: Each enumerated type shall be compatible with char,
5630    // a signed integer type, or an unsigned integer type.
5631    // Compatibility is based on the underlying type, not the promotion
5632    // type.
5633    if (const EnumType* ETy = LHS->getAs<EnumType>()) {
5634      if (ETy->getDecl()->getIntegerType() == RHSCan.getUnqualifiedType())
5635        return RHS;
5636    }
5637    if (const EnumType* ETy = RHS->getAs<EnumType>()) {
5638      if (ETy->getDecl()->getIntegerType() == LHSCan.getUnqualifiedType())
5639        return LHS;
5640    }
5641
5642    return QualType();
5643  }
5644
5645  // The canonical type classes match.
5646  switch (LHSClass) {
5647#define TYPE(Class, Base)
5648#define ABSTRACT_TYPE(Class, Base)
5649#define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class, Base) case Type::Class:
5650#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
5651#define DEPENDENT_TYPE(Class, Base) case Type::Class:
5652#include "clang/AST/TypeNodes.def"
5653    assert(false && "Non-canonical and dependent types shouldn't get here");
5654    return QualType();
5655
5656  case Type::LValueReference:
5657  case Type::RValueReference:
5658  case Type::MemberPointer:
5659    assert(false && "C++ should never be in mergeTypes");
5660    return QualType();
5661
5662  case Type::ObjCInterface:
5663  case Type::IncompleteArray:
5664  case Type::VariableArray:
5665  case Type::FunctionProto:
5666  case Type::ExtVector:
5667    assert(false && "Types are eliminated above");
5668    return QualType();
5669
5670  case Type::Pointer:
5671  {
5672    // Merge two pointer types, while trying to preserve typedef info
5673    QualType LHSPointee = LHS->getAs<PointerType>()->getPointeeType();
5674    QualType RHSPointee = RHS->getAs<PointerType>()->getPointeeType();
5675    if (Unqualified) {
5676      LHSPointee = LHSPointee.getUnqualifiedType();
5677      RHSPointee = RHSPointee.getUnqualifiedType();
5678    }
5679    QualType ResultType = mergeTypes(LHSPointee, RHSPointee, false,
5680                                     Unqualified);
5681    if (ResultType.isNull()) return QualType();
5682    if (getCanonicalType(LHSPointee) == getCanonicalType(ResultType))
5683      return LHS;
5684    if (getCanonicalType(RHSPointee) == getCanonicalType(ResultType))
5685      return RHS;
5686    return getPointerType(ResultType);
5687  }
5688  case Type::BlockPointer:
5689  {
5690    // Merge two block pointer types, while trying to preserve typedef info
5691    QualType LHSPointee = LHS->getAs<BlockPointerType>()->getPointeeType();
5692    QualType RHSPointee = RHS->getAs<BlockPointerType>()->getPointeeType();
5693    if (Unqualified) {
5694      LHSPointee = LHSPointee.getUnqualifiedType();
5695      RHSPointee = RHSPointee.getUnqualifiedType();
5696    }
5697    QualType ResultType = mergeTypes(LHSPointee, RHSPointee, OfBlockPointer,
5698                                     Unqualified);
5699    if (ResultType.isNull()) return QualType();
5700    if (getCanonicalType(LHSPointee) == getCanonicalType(ResultType))
5701      return LHS;
5702    if (getCanonicalType(RHSPointee) == getCanonicalType(ResultType))
5703      return RHS;
5704    return getBlockPointerType(ResultType);
5705  }
5706  case Type::ConstantArray:
5707  {
5708    const ConstantArrayType* LCAT = getAsConstantArrayType(LHS);
5709    const ConstantArrayType* RCAT = getAsConstantArrayType(RHS);
5710    if (LCAT && RCAT && RCAT->getSize() != LCAT->getSize())
5711      return QualType();
5712
5713    QualType LHSElem = getAsArrayType(LHS)->getElementType();
5714    QualType RHSElem = getAsArrayType(RHS)->getElementType();
5715    if (Unqualified) {
5716      LHSElem = LHSElem.getUnqualifiedType();
5717      RHSElem = RHSElem.getUnqualifiedType();
5718    }
5719
5720    QualType ResultType = mergeTypes(LHSElem, RHSElem, false, Unqualified);
5721    if (ResultType.isNull()) return QualType();
5722    if (LCAT && getCanonicalType(LHSElem) == getCanonicalType(ResultType))
5723      return LHS;
5724    if (RCAT && getCanonicalType(RHSElem) == getCanonicalType(ResultType))
5725      return RHS;
5726    if (LCAT) return getConstantArrayType(ResultType, LCAT->getSize(),
5727                                          ArrayType::ArraySizeModifier(), 0);
5728    if (RCAT) return getConstantArrayType(ResultType, RCAT->getSize(),
5729                                          ArrayType::ArraySizeModifier(), 0);
5730    const VariableArrayType* LVAT = getAsVariableArrayType(LHS);
5731    const VariableArrayType* RVAT = getAsVariableArrayType(RHS);
5732    if (LVAT && getCanonicalType(LHSElem) == getCanonicalType(ResultType))
5733      return LHS;
5734    if (RVAT && getCanonicalType(RHSElem) == getCanonicalType(ResultType))
5735      return RHS;
5736    if (LVAT) {
5737      // FIXME: This isn't correct! But tricky to implement because
5738      // the array's size has to be the size of LHS, but the type
5739      // has to be different.
5740      return LHS;
5741    }
5742    if (RVAT) {
5743      // FIXME: This isn't correct! But tricky to implement because
5744      // the array's size has to be the size of RHS, but the type
5745      // has to be different.
5746      return RHS;
5747    }
5748    if (getCanonicalType(LHSElem) == getCanonicalType(ResultType)) return LHS;
5749    if (getCanonicalType(RHSElem) == getCanonicalType(ResultType)) return RHS;
5750    return getIncompleteArrayType(ResultType,
5751                                  ArrayType::ArraySizeModifier(), 0);
5752  }
5753  case Type::FunctionNoProto:
5754    return mergeFunctionTypes(LHS, RHS, OfBlockPointer, Unqualified);
5755  case Type::Record:
5756  case Type::Enum:
5757    return QualType();
5758  case Type::Builtin:
5759    // Only exactly equal builtin types are compatible, which is tested above.
5760    return QualType();
5761  case Type::Complex:
5762    // Distinct complex types are incompatible.
5763    return QualType();
5764  case Type::Vector:
5765    // FIXME: The merged type should be an ExtVector!
5766    if (areCompatVectorTypes(LHSCan->getAs<VectorType>(),
5767                             RHSCan->getAs<VectorType>()))
5768      return LHS;
5769    return QualType();
5770  case Type::ObjCObject: {
5771    // Check if the types are assignment compatible.
5772    // FIXME: This should be type compatibility, e.g. whether
5773    // "LHS x; RHS x;" at global scope is legal.
5774    const ObjCObjectType* LHSIface = LHS->getAs<ObjCObjectType>();
5775    const ObjCObjectType* RHSIface = RHS->getAs<ObjCObjectType>();
5776    if (canAssignObjCInterfaces(LHSIface, RHSIface))
5777      return LHS;
5778
5779    return QualType();
5780  }
5781  case Type::ObjCObjectPointer: {
5782    if (OfBlockPointer) {
5783      if (canAssignObjCInterfacesInBlockPointer(
5784                                          LHS->getAs<ObjCObjectPointerType>(),
5785                                          RHS->getAs<ObjCObjectPointerType>(),
5786                                          BlockReturnType))
5787      return LHS;
5788      return QualType();
5789    }
5790    if (canAssignObjCInterfaces(LHS->getAs<ObjCObjectPointerType>(),
5791                                RHS->getAs<ObjCObjectPointerType>()))
5792      return LHS;
5793
5794    return QualType();
5795    }
5796  }
5797
5798  return QualType();
5799}
5800
5801/// mergeObjCGCQualifiers - This routine merges ObjC's GC attribute of 'LHS' and
5802/// 'RHS' attributes and returns the merged version; including for function
5803/// return types.
5804QualType ASTContext::mergeObjCGCQualifiers(QualType LHS, QualType RHS) {
5805  QualType LHSCan = getCanonicalType(LHS),
5806  RHSCan = getCanonicalType(RHS);
5807  // If two types are identical, they are compatible.
5808  if (LHSCan == RHSCan)
5809    return LHS;
5810  if (RHSCan->isFunctionType()) {
5811    if (!LHSCan->isFunctionType())
5812      return QualType();
5813    QualType OldReturnType =
5814      cast<FunctionType>(RHSCan.getTypePtr())->getResultType();
5815    QualType NewReturnType =
5816      cast<FunctionType>(LHSCan.getTypePtr())->getResultType();
5817    QualType ResReturnType =
5818      mergeObjCGCQualifiers(NewReturnType, OldReturnType);
5819    if (ResReturnType.isNull())
5820      return QualType();
5821    if (ResReturnType == NewReturnType || ResReturnType == OldReturnType) {
5822      // id foo(); ... __strong id foo(); or: __strong id foo(); ... id foo();
5823      // In either case, use OldReturnType to build the new function type.
5824      const FunctionType *F = LHS->getAs<FunctionType>();
5825      if (const FunctionProtoType *FPT = cast<FunctionProtoType>(F)) {
5826        FunctionProtoType::ExtProtoInfo EPI = FPT->getExtProtoInfo();
5827        EPI.ExtInfo = getFunctionExtInfo(LHS);
5828        QualType ResultType
5829          = getFunctionType(OldReturnType, FPT->arg_type_begin(),
5830                            FPT->getNumArgs(), EPI);
5831        return ResultType;
5832      }
5833    }
5834    return QualType();
5835  }
5836
5837  // If the qualifiers are different, the types can still be merged.
5838  Qualifiers LQuals = LHSCan.getLocalQualifiers();
5839  Qualifiers RQuals = RHSCan.getLocalQualifiers();
5840  if (LQuals != RQuals) {
5841    // If any of these qualifiers are different, we have a type mismatch.
5842    if (LQuals.getCVRQualifiers() != RQuals.getCVRQualifiers() ||
5843        LQuals.getAddressSpace() != RQuals.getAddressSpace())
5844      return QualType();
5845
5846    // Exactly one GC qualifier difference is allowed: __strong is
5847    // okay if the other type has no GC qualifier but is an Objective
5848    // C object pointer (i.e. implicitly strong by default).  We fix
5849    // this by pretending that the unqualified type was actually
5850    // qualified __strong.
5851    Qualifiers::GC GC_L = LQuals.getObjCGCAttr();
5852    Qualifiers::GC GC_R = RQuals.getObjCGCAttr();
5853    assert((GC_L != GC_R) && "unequal qualifier sets had only equal elements");
5854
5855    if (GC_L == Qualifiers::Weak || GC_R == Qualifiers::Weak)
5856      return QualType();
5857
5858    if (GC_L == Qualifiers::Strong)
5859      return LHS;
5860    if (GC_R == Qualifiers::Strong)
5861      return RHS;
5862    return QualType();
5863  }
5864
5865  if (LHSCan->isObjCObjectPointerType() && RHSCan->isObjCObjectPointerType()) {
5866    QualType LHSBaseQT = LHS->getAs<ObjCObjectPointerType>()->getPointeeType();
5867    QualType RHSBaseQT = RHS->getAs<ObjCObjectPointerType>()->getPointeeType();
5868    QualType ResQT = mergeObjCGCQualifiers(LHSBaseQT, RHSBaseQT);
5869    if (ResQT == LHSBaseQT)
5870      return LHS;
5871    if (ResQT == RHSBaseQT)
5872      return RHS;
5873  }
5874  return QualType();
5875}
5876
5877//===----------------------------------------------------------------------===//
5878//                         Integer Predicates
5879//===----------------------------------------------------------------------===//
5880
5881unsigned ASTContext::getIntWidth(QualType T) const {
5882  if (const EnumType *ET = dyn_cast<EnumType>(T))
5883    T = ET->getDecl()->getIntegerType();
5884  if (T->isBooleanType())
5885    return 1;
5886  // For builtin types, just use the standard type sizing method
5887  return (unsigned)getTypeSize(T);
5888}
5889
5890QualType ASTContext::getCorrespondingUnsignedType(QualType T) {
5891  assert(T->hasSignedIntegerRepresentation() && "Unexpected type");
5892
5893  // Turn <4 x signed int> -> <4 x unsigned int>
5894  if (const VectorType *VTy = T->getAs<VectorType>())
5895    return getVectorType(getCorrespondingUnsignedType(VTy->getElementType()),
5896                         VTy->getNumElements(), VTy->getVectorKind());
5897
5898  // For enums, we return the unsigned version of the base type.
5899  if (const EnumType *ETy = T->getAs<EnumType>())
5900    T = ETy->getDecl()->getIntegerType();
5901
5902  const BuiltinType *BTy = T->getAs<BuiltinType>();
5903  assert(BTy && "Unexpected signed integer type");
5904  switch (BTy->getKind()) {
5905  case BuiltinType::Char_S:
5906  case BuiltinType::SChar:
5907    return UnsignedCharTy;
5908  case BuiltinType::Short:
5909    return UnsignedShortTy;
5910  case BuiltinType::Int:
5911    return UnsignedIntTy;
5912  case BuiltinType::Long:
5913    return UnsignedLongTy;
5914  case BuiltinType::LongLong:
5915    return UnsignedLongLongTy;
5916  case BuiltinType::Int128:
5917    return UnsignedInt128Ty;
5918  default:
5919    assert(0 && "Unexpected signed integer type");
5920    return QualType();
5921  }
5922}
5923
5924ASTMutationListener::~ASTMutationListener() { }
5925
5926
5927//===----------------------------------------------------------------------===//
5928//                          Builtin Type Computation
5929//===----------------------------------------------------------------------===//
5930
5931/// DecodeTypeFromStr - This decodes one type descriptor from Str, advancing the
5932/// pointer over the consumed characters.  This returns the resultant type.  If
5933/// AllowTypeModifiers is false then modifier like * are not parsed, just basic
5934/// types.  This allows "v2i*" to be parsed as a pointer to a v2i instead of
5935/// a vector of "i*".
5936///
5937/// RequiresICE is filled in on return to indicate whether the value is required
5938/// to be an Integer Constant Expression.
5939static QualType DecodeTypeFromStr(const char *&Str, const ASTContext &Context,
5940                                  ASTContext::GetBuiltinTypeError &Error,
5941                                  bool &RequiresICE,
5942                                  bool AllowTypeModifiers) {
5943  // Modifiers.
5944  int HowLong = 0;
5945  bool Signed = false, Unsigned = false;
5946  RequiresICE = false;
5947
5948  // Read the prefixed modifiers first.
5949  bool Done = false;
5950  while (!Done) {
5951    switch (*Str++) {
5952    default: Done = true; --Str; break;
5953    case 'I':
5954      RequiresICE = true;
5955      break;
5956    case 'S':
5957      assert(!Unsigned && "Can't use both 'S' and 'U' modifiers!");
5958      assert(!Signed && "Can't use 'S' modifier multiple times!");
5959      Signed = true;
5960      break;
5961    case 'U':
5962      assert(!Signed && "Can't use both 'S' and 'U' modifiers!");
5963      assert(!Unsigned && "Can't use 'S' modifier multiple times!");
5964      Unsigned = true;
5965      break;
5966    case 'L':
5967      assert(HowLong <= 2 && "Can't have LLLL modifier");
5968      ++HowLong;
5969      break;
5970    }
5971  }
5972
5973  QualType Type;
5974
5975  // Read the base type.
5976  switch (*Str++) {
5977  default: assert(0 && "Unknown builtin type letter!");
5978  case 'v':
5979    assert(HowLong == 0 && !Signed && !Unsigned &&
5980           "Bad modifiers used with 'v'!");
5981    Type = Context.VoidTy;
5982    break;
5983  case 'f':
5984    assert(HowLong == 0 && !Signed && !Unsigned &&
5985           "Bad modifiers used with 'f'!");
5986    Type = Context.FloatTy;
5987    break;
5988  case 'd':
5989    assert(HowLong < 2 && !Signed && !Unsigned &&
5990           "Bad modifiers used with 'd'!");
5991    if (HowLong)
5992      Type = Context.LongDoubleTy;
5993    else
5994      Type = Context.DoubleTy;
5995    break;
5996  case 's':
5997    assert(HowLong == 0 && "Bad modifiers used with 's'!");
5998    if (Unsigned)
5999      Type = Context.UnsignedShortTy;
6000    else
6001      Type = Context.ShortTy;
6002    break;
6003  case 'i':
6004    if (HowLong == 3)
6005      Type = Unsigned ? Context.UnsignedInt128Ty : Context.Int128Ty;
6006    else if (HowLong == 2)
6007      Type = Unsigned ? Context.UnsignedLongLongTy : Context.LongLongTy;
6008    else if (HowLong == 1)
6009      Type = Unsigned ? Context.UnsignedLongTy : Context.LongTy;
6010    else
6011      Type = Unsigned ? Context.UnsignedIntTy : Context.IntTy;
6012    break;
6013  case 'c':
6014    assert(HowLong == 0 && "Bad modifiers used with 'c'!");
6015    if (Signed)
6016      Type = Context.SignedCharTy;
6017    else if (Unsigned)
6018      Type = Context.UnsignedCharTy;
6019    else
6020      Type = Context.CharTy;
6021    break;
6022  case 'b': // boolean
6023    assert(HowLong == 0 && !Signed && !Unsigned && "Bad modifiers for 'b'!");
6024    Type = Context.BoolTy;
6025    break;
6026  case 'z':  // size_t.
6027    assert(HowLong == 0 && !Signed && !Unsigned && "Bad modifiers for 'z'!");
6028    Type = Context.getSizeType();
6029    break;
6030  case 'F':
6031    Type = Context.getCFConstantStringType();
6032    break;
6033  case 'G':
6034    Type = Context.getObjCIdType();
6035    break;
6036  case 'H':
6037    Type = Context.getObjCSelType();
6038    break;
6039  case 'a':
6040    Type = Context.getBuiltinVaListType();
6041    assert(!Type.isNull() && "builtin va list type not initialized!");
6042    break;
6043  case 'A':
6044    // This is a "reference" to a va_list; however, what exactly
6045    // this means depends on how va_list is defined. There are two
6046    // different kinds of va_list: ones passed by value, and ones
6047    // passed by reference.  An example of a by-value va_list is
6048    // x86, where va_list is a char*. An example of by-ref va_list
6049    // is x86-64, where va_list is a __va_list_tag[1]. For x86,
6050    // we want this argument to be a char*&; for x86-64, we want
6051    // it to be a __va_list_tag*.
6052    Type = Context.getBuiltinVaListType();
6053    assert(!Type.isNull() && "builtin va list type not initialized!");
6054    if (Type->isArrayType())
6055      Type = Context.getArrayDecayedType(Type);
6056    else
6057      Type = Context.getLValueReferenceType(Type);
6058    break;
6059  case 'V': {
6060    char *End;
6061    unsigned NumElements = strtoul(Str, &End, 10);
6062    assert(End != Str && "Missing vector size");
6063    Str = End;
6064
6065    QualType ElementType = DecodeTypeFromStr(Str, Context, Error,
6066                                             RequiresICE, false);
6067    assert(!RequiresICE && "Can't require vector ICE");
6068
6069    // TODO: No way to make AltiVec vectors in builtins yet.
6070    Type = Context.getVectorType(ElementType, NumElements,
6071                                 VectorType::GenericVector);
6072    break;
6073  }
6074  case 'X': {
6075    QualType ElementType = DecodeTypeFromStr(Str, Context, Error, RequiresICE,
6076                                             false);
6077    assert(!RequiresICE && "Can't require complex ICE");
6078    Type = Context.getComplexType(ElementType);
6079    break;
6080  }
6081  case 'P':
6082    Type = Context.getFILEType();
6083    if (Type.isNull()) {
6084      Error = ASTContext::GE_Missing_stdio;
6085      return QualType();
6086    }
6087    break;
6088  case 'J':
6089    if (Signed)
6090      Type = Context.getsigjmp_bufType();
6091    else
6092      Type = Context.getjmp_bufType();
6093
6094    if (Type.isNull()) {
6095      Error = ASTContext::GE_Missing_setjmp;
6096      return QualType();
6097    }
6098    break;
6099  }
6100
6101  // If there are modifiers and if we're allowed to parse them, go for it.
6102  Done = !AllowTypeModifiers;
6103  while (!Done) {
6104    switch (char c = *Str++) {
6105    default: Done = true; --Str; break;
6106    case '*':
6107    case '&': {
6108      // Both pointers and references can have their pointee types
6109      // qualified with an address space.
6110      char *End;
6111      unsigned AddrSpace = strtoul(Str, &End, 10);
6112      if (End != Str && AddrSpace != 0) {
6113        Type = Context.getAddrSpaceQualType(Type, AddrSpace);
6114        Str = End;
6115      }
6116      if (c == '*')
6117        Type = Context.getPointerType(Type);
6118      else
6119        Type = Context.getLValueReferenceType(Type);
6120      break;
6121    }
6122    // FIXME: There's no way to have a built-in with an rvalue ref arg.
6123    case 'C':
6124      Type = Type.withConst();
6125      break;
6126    case 'D':
6127      Type = Context.getVolatileType(Type);
6128      break;
6129    }
6130  }
6131
6132  assert((!RequiresICE || Type->isIntegralOrEnumerationType()) &&
6133         "Integer constant 'I' type must be an integer");
6134
6135  return Type;
6136}
6137
6138/// GetBuiltinType - Return the type for the specified builtin.
6139QualType ASTContext::GetBuiltinType(unsigned Id,
6140                                    GetBuiltinTypeError &Error,
6141                                    unsigned *IntegerConstantArgs) const {
6142  const char *TypeStr = BuiltinInfo.GetTypeString(Id);
6143
6144  llvm::SmallVector<QualType, 8> ArgTypes;
6145
6146  bool RequiresICE = false;
6147  Error = GE_None;
6148  QualType ResType = DecodeTypeFromStr(TypeStr, *this, Error,
6149                                       RequiresICE, true);
6150  if (Error != GE_None)
6151    return QualType();
6152
6153  assert(!RequiresICE && "Result of intrinsic cannot be required to be an ICE");
6154
6155  while (TypeStr[0] && TypeStr[0] != '.') {
6156    QualType Ty = DecodeTypeFromStr(TypeStr, *this, Error, RequiresICE, true);
6157    if (Error != GE_None)
6158      return QualType();
6159
6160    // If this argument is required to be an IntegerConstantExpression and the
6161    // caller cares, fill in the bitmask we return.
6162    if (RequiresICE && IntegerConstantArgs)
6163      *IntegerConstantArgs |= 1 << ArgTypes.size();
6164
6165    // Do array -> pointer decay.  The builtin should use the decayed type.
6166    if (Ty->isArrayType())
6167      Ty = getArrayDecayedType(Ty);
6168
6169    ArgTypes.push_back(Ty);
6170  }
6171
6172  assert((TypeStr[0] != '.' || TypeStr[1] == 0) &&
6173         "'.' should only occur at end of builtin type list!");
6174
6175  FunctionType::ExtInfo EI;
6176  if (BuiltinInfo.isNoReturn(Id)) EI = EI.withNoReturn(true);
6177
6178  bool Variadic = (TypeStr[0] == '.');
6179
6180  // We really shouldn't be making a no-proto type here, especially in C++.
6181  if (ArgTypes.empty() && Variadic)
6182    return getFunctionNoProtoType(ResType, EI);
6183
6184  FunctionProtoType::ExtProtoInfo EPI;
6185  EPI.ExtInfo = EI;
6186  EPI.Variadic = Variadic;
6187
6188  return getFunctionType(ResType, ArgTypes.data(), ArgTypes.size(), EPI);
6189}
6190
6191GVALinkage ASTContext::GetGVALinkageForFunction(const FunctionDecl *FD) {
6192  GVALinkage External = GVA_StrongExternal;
6193
6194  Linkage L = FD->getLinkage();
6195  switch (L) {
6196  case NoLinkage:
6197  case InternalLinkage:
6198  case UniqueExternalLinkage:
6199    return GVA_Internal;
6200
6201  case ExternalLinkage:
6202    switch (FD->getTemplateSpecializationKind()) {
6203    case TSK_Undeclared:
6204    case TSK_ExplicitSpecialization:
6205      External = GVA_StrongExternal;
6206      break;
6207
6208    case TSK_ExplicitInstantiationDefinition:
6209      return GVA_ExplicitTemplateInstantiation;
6210
6211    case TSK_ExplicitInstantiationDeclaration:
6212    case TSK_ImplicitInstantiation:
6213      External = GVA_TemplateInstantiation;
6214      break;
6215    }
6216  }
6217
6218  if (!FD->isInlined())
6219    return External;
6220
6221  if (!getLangOptions().CPlusPlus || FD->hasAttr<GNUInlineAttr>()) {
6222    // GNU or C99 inline semantics. Determine whether this symbol should be
6223    // externally visible.
6224    if (FD->isInlineDefinitionExternallyVisible())
6225      return External;
6226
6227    // C99 inline semantics, where the symbol is not externally visible.
6228    return GVA_C99Inline;
6229  }
6230
6231  // C++0x [temp.explicit]p9:
6232  //   [ Note: The intent is that an inline function that is the subject of
6233  //   an explicit instantiation declaration will still be implicitly
6234  //   instantiated when used so that the body can be considered for
6235  //   inlining, but that no out-of-line copy of the inline function would be
6236  //   generated in the translation unit. -- end note ]
6237  if (FD->getTemplateSpecializationKind()
6238                                       == TSK_ExplicitInstantiationDeclaration)
6239    return GVA_C99Inline;
6240
6241  return GVA_CXXInline;
6242}
6243
6244GVALinkage ASTContext::GetGVALinkageForVariable(const VarDecl *VD) {
6245  // If this is a static data member, compute the kind of template
6246  // specialization. Otherwise, this variable is not part of a
6247  // template.
6248  TemplateSpecializationKind TSK = TSK_Undeclared;
6249  if (VD->isStaticDataMember())
6250    TSK = VD->getTemplateSpecializationKind();
6251
6252  Linkage L = VD->getLinkage();
6253  if (L == ExternalLinkage && getLangOptions().CPlusPlus &&
6254      VD->getType()->getLinkage() == UniqueExternalLinkage)
6255    L = UniqueExternalLinkage;
6256
6257  switch (L) {
6258  case NoLinkage:
6259  case InternalLinkage:
6260  case UniqueExternalLinkage:
6261    return GVA_Internal;
6262
6263  case ExternalLinkage:
6264    switch (TSK) {
6265    case TSK_Undeclared:
6266    case TSK_ExplicitSpecialization:
6267      return GVA_StrongExternal;
6268
6269    case TSK_ExplicitInstantiationDeclaration:
6270      llvm_unreachable("Variable should not be instantiated");
6271      // Fall through to treat this like any other instantiation.
6272
6273    case TSK_ExplicitInstantiationDefinition:
6274      return GVA_ExplicitTemplateInstantiation;
6275
6276    case TSK_ImplicitInstantiation:
6277      return GVA_TemplateInstantiation;
6278    }
6279  }
6280
6281  return GVA_StrongExternal;
6282}
6283
6284bool ASTContext::DeclMustBeEmitted(const Decl *D) {
6285  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
6286    if (!VD->isFileVarDecl())
6287      return false;
6288  } else if (!isa<FunctionDecl>(D))
6289    return false;
6290
6291  // Weak references don't produce any output by themselves.
6292  if (D->hasAttr<WeakRefAttr>())
6293    return false;
6294
6295  // Aliases and used decls are required.
6296  if (D->hasAttr<AliasAttr>() || D->hasAttr<UsedAttr>())
6297    return true;
6298
6299  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
6300    // Forward declarations aren't required.
6301    if (!FD->doesThisDeclarationHaveABody())
6302      return false;
6303
6304    // Constructors and destructors are required.
6305    if (FD->hasAttr<ConstructorAttr>() || FD->hasAttr<DestructorAttr>())
6306      return true;
6307
6308    // The key function for a class is required.
6309    if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(FD)) {
6310      const CXXRecordDecl *RD = MD->getParent();
6311      if (MD->isOutOfLine() && RD->isDynamicClass()) {
6312        const CXXMethodDecl *KeyFunc = getKeyFunction(RD);
6313        if (KeyFunc && KeyFunc->getCanonicalDecl() == MD->getCanonicalDecl())
6314          return true;
6315      }
6316    }
6317
6318    GVALinkage Linkage = GetGVALinkageForFunction(FD);
6319
6320    // static, static inline, always_inline, and extern inline functions can
6321    // always be deferred.  Normal inline functions can be deferred in C99/C++.
6322    // Implicit template instantiations can also be deferred in C++.
6323    if (Linkage == GVA_Internal  || Linkage == GVA_C99Inline ||
6324        Linkage == GVA_CXXInline || Linkage == GVA_TemplateInstantiation)
6325      return false;
6326    return true;
6327  }
6328
6329  const VarDecl *VD = cast<VarDecl>(D);
6330  assert(VD->isFileVarDecl() && "Expected file scoped var");
6331
6332  if (VD->isThisDeclarationADefinition() == VarDecl::DeclarationOnly)
6333    return false;
6334
6335  // Structs that have non-trivial constructors or destructors are required.
6336
6337  // FIXME: Handle references.
6338  // FIXME: Be more selective about which constructors we care about.
6339  if (const RecordType *RT = VD->getType()->getAs<RecordType>()) {
6340    if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl())) {
6341      if (RD->hasDefinition() && !(RD->hasTrivialDefaultConstructor() &&
6342                                   RD->hasTrivialCopyConstructor() &&
6343                                   RD->hasTrivialMoveConstructor() &&
6344                                   RD->hasTrivialDestructor()))
6345        return true;
6346    }
6347  }
6348
6349  GVALinkage L = GetGVALinkageForVariable(VD);
6350  if (L == GVA_Internal || L == GVA_TemplateInstantiation) {
6351    if (!(VD->getInit() && VD->getInit()->HasSideEffects(*this)))
6352      return false;
6353  }
6354
6355  return true;
6356}
6357
6358CallingConv ASTContext::getDefaultMethodCallConv() {
6359  // Pass through to the C++ ABI object
6360  return ABI->getDefaultMethodCallConv();
6361}
6362
6363bool ASTContext::isNearlyEmpty(const CXXRecordDecl *RD) const {
6364  // Pass through to the C++ ABI object
6365  return ABI->isNearlyEmpty(RD);
6366}
6367
6368MangleContext *ASTContext::createMangleContext() {
6369  switch (Target.getCXXABI()) {
6370  case CXXABI_ARM:
6371  case CXXABI_Itanium:
6372    return createItaniumMangleContext(*this, getDiagnostics());
6373  case CXXABI_Microsoft:
6374    return createMicrosoftMangleContext(*this, getDiagnostics());
6375  }
6376  assert(0 && "Unsupported ABI");
6377  return 0;
6378}
6379
6380CXXABI::~CXXABI() {}
6381
6382size_t ASTContext::getSideTableAllocatedMemory() const {
6383  size_t bytes = 0;
6384  bytes += ASTRecordLayouts.getMemorySize();
6385  bytes += ObjCLayouts.getMemorySize();
6386  bytes += KeyFunctions.getMemorySize();
6387  bytes += ObjCImpls.getMemorySize();
6388  bytes += BlockVarCopyInits.getMemorySize();
6389  bytes += DeclAttrs.getMemorySize();
6390  bytes += InstantiatedFromStaticDataMember.getMemorySize();
6391  bytes += InstantiatedFromUsingDecl.getMemorySize();
6392  bytes += InstantiatedFromUsingShadowDecl.getMemorySize();
6393  bytes += InstantiatedFromUnnamedFieldDecl.getMemorySize();
6394  return bytes;
6395}
6396
6397