ASTContext.cpp revision f85e193739c953358c865005855253af4f68a497 
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        uint64_t offs = layout.getBaseClassOffsetInBits(base);
4515        FieldOrBaseOffsets.insert(FieldOrBaseOffsets.upper_bound(offs),
4516                                  std::make_pair(offs, base));
4517      }
4518    }
4519  }
4520
4521  unsigned i = 0;
4522  for (RecordDecl::field_iterator Field = RDecl->field_begin(),
4523                               FieldEnd = RDecl->field_end();
4524       Field != FieldEnd; ++Field, ++i) {
4525    uint64_t offs = layout.getFieldOffset(i);
4526    FieldOrBaseOffsets.insert(FieldOrBaseOffsets.upper_bound(offs),
4527                              std::make_pair(offs, *Field));
4528  }
4529
4530  if (CXXRec && includeVBases) {
4531    for (CXXRecordDecl::base_class_iterator
4532           BI = CXXRec->vbases_begin(),
4533           BE = CXXRec->vbases_end(); BI != BE; ++BI) {
4534      CXXRecordDecl *base = BI->getType()->getAsCXXRecordDecl();
4535      uint64_t offs = layout.getVBaseClassOffsetInBits(base);
4536      FieldOrBaseOffsets.insert(FieldOrBaseOffsets.upper_bound(offs),
4537                                std::make_pair(offs, base));
4538    }
4539  }
4540
4541  CharUnits size;
4542  if (CXXRec) {
4543    size = includeVBases ? layout.getSize() : layout.getNonVirtualSize();
4544  } else {
4545    size = layout.getSize();
4546  }
4547
4548  uint64_t CurOffs = 0;
4549  std::multimap<uint64_t, NamedDecl *>::iterator
4550    CurLayObj = FieldOrBaseOffsets.begin();
4551
4552  if (CurLayObj != FieldOrBaseOffsets.end() && CurLayObj->first != 0) {
4553    assert(CXXRec && CXXRec->isDynamicClass() &&
4554           "Offset 0 was empty but no VTable ?");
4555    if (FD) {
4556      S += "\"_vptr$";
4557      std::string recname = CXXRec->getNameAsString();
4558      if (recname.empty()) recname = "?";
4559      S += recname;
4560      S += '"';
4561    }
4562    S += "^^?";
4563    CurOffs += getTypeSize(VoidPtrTy);
4564  }
4565
4566  if (!RDecl->hasFlexibleArrayMember()) {
4567    // Mark the end of the structure.
4568    uint64_t offs = toBits(size);
4569    FieldOrBaseOffsets.insert(FieldOrBaseOffsets.upper_bound(offs),
4570                              std::make_pair(offs, (NamedDecl*)0));
4571  }
4572
4573  for (; CurLayObj != FieldOrBaseOffsets.end(); ++CurLayObj) {
4574    assert(CurOffs <= CurLayObj->first);
4575
4576    if (CurOffs < CurLayObj->first) {
4577      uint64_t padding = CurLayObj->first - CurOffs;
4578      // FIXME: There doesn't seem to be a way to indicate in the encoding that
4579      // packing/alignment of members is different that normal, in which case
4580      // the encoding will be out-of-sync with the real layout.
4581      // If the runtime switches to just consider the size of types without
4582      // taking into account alignment, we could make padding explicit in the
4583      // encoding (e.g. using arrays of chars). The encoding strings would be
4584      // longer then though.
4585      CurOffs += padding;
4586    }
4587
4588    NamedDecl *dcl = CurLayObj->second;
4589    if (dcl == 0)
4590      break; // reached end of structure.
4591
4592    if (CXXRecordDecl *base = dyn_cast<CXXRecordDecl>(dcl)) {
4593      // We expand the bases without their virtual bases since those are going
4594      // in the initial structure. Note that this differs from gcc which
4595      // expands virtual bases each time one is encountered in the hierarchy,
4596      // making the encoding type bigger than it really is.
4597      getObjCEncodingForStructureImpl(base, S, FD, /*includeVBases*/false);
4598      if (!base->isEmpty())
4599        CurOffs += toBits(getASTRecordLayout(base).getNonVirtualSize());
4600    } else {
4601      FieldDecl *field = cast<FieldDecl>(dcl);
4602      if (FD) {
4603        S += '"';
4604        S += field->getNameAsString();
4605        S += '"';
4606      }
4607
4608      if (field->isBitField()) {
4609        EncodeBitField(this, S, field->getType(), field);
4610        CurOffs += field->getBitWidth()->EvaluateAsInt(*this).getZExtValue();
4611      } else {
4612        QualType qt = field->getType();
4613        getLegacyIntegralTypeEncoding(qt);
4614        getObjCEncodingForTypeImpl(qt, S, false, true, FD,
4615                                   /*OutermostType*/false,
4616                                   /*EncodingProperty*/false,
4617                                   /*StructField*/true);
4618        CurOffs += getTypeSize(field->getType());
4619      }
4620    }
4621  }
4622}
4623
4624void ASTContext::getObjCEncodingForTypeQualifier(Decl::ObjCDeclQualifier QT,
4625                                                 std::string& S) const {
4626  if (QT & Decl::OBJC_TQ_In)
4627    S += 'n';
4628  if (QT & Decl::OBJC_TQ_Inout)
4629    S += 'N';
4630  if (QT & Decl::OBJC_TQ_Out)
4631    S += 'o';
4632  if (QT & Decl::OBJC_TQ_Bycopy)
4633    S += 'O';
4634  if (QT & Decl::OBJC_TQ_Byref)
4635    S += 'R';
4636  if (QT & Decl::OBJC_TQ_Oneway)
4637    S += 'V';
4638}
4639
4640void ASTContext::setBuiltinVaListType(QualType T) {
4641  assert(BuiltinVaListType.isNull() && "__builtin_va_list type already set!");
4642
4643  BuiltinVaListType = T;
4644}
4645
4646void ASTContext::setObjCIdType(QualType T) {
4647  ObjCIdTypedefType = T;
4648}
4649
4650void ASTContext::setObjCSelType(QualType T) {
4651  ObjCSelTypedefType = T;
4652}
4653
4654void ASTContext::setObjCProtoType(QualType QT) {
4655  ObjCProtoType = QT;
4656}
4657
4658void ASTContext::setObjCClassType(QualType T) {
4659  ObjCClassTypedefType = T;
4660}
4661
4662void ASTContext::setObjCConstantStringInterface(ObjCInterfaceDecl *Decl) {
4663  assert(ObjCConstantStringType.isNull() &&
4664         "'NSConstantString' type already set!");
4665
4666  ObjCConstantStringType = getObjCInterfaceType(Decl);
4667}
4668
4669/// \brief Retrieve the template name that corresponds to a non-empty
4670/// lookup.
4671TemplateName
4672ASTContext::getOverloadedTemplateName(UnresolvedSetIterator Begin,
4673                                      UnresolvedSetIterator End) const {
4674  unsigned size = End - Begin;
4675  assert(size > 1 && "set is not overloaded!");
4676
4677  void *memory = Allocate(sizeof(OverloadedTemplateStorage) +
4678                          size * sizeof(FunctionTemplateDecl*));
4679  OverloadedTemplateStorage *OT = new(memory) OverloadedTemplateStorage(size);
4680
4681  NamedDecl **Storage = OT->getStorage();
4682  for (UnresolvedSetIterator I = Begin; I != End; ++I) {
4683    NamedDecl *D = *I;
4684    assert(isa<FunctionTemplateDecl>(D) ||
4685           (isa<UsingShadowDecl>(D) &&
4686            isa<FunctionTemplateDecl>(D->getUnderlyingDecl())));
4687    *Storage++ = D;
4688  }
4689
4690  return TemplateName(OT);
4691}
4692
4693/// \brief Retrieve the template name that represents a qualified
4694/// template name such as \c std::vector.
4695TemplateName
4696ASTContext::getQualifiedTemplateName(NestedNameSpecifier *NNS,
4697                                     bool TemplateKeyword,
4698                                     TemplateDecl *Template) const {
4699  assert(NNS && "Missing nested-name-specifier in qualified template name");
4700
4701  // FIXME: Canonicalization?
4702  llvm::FoldingSetNodeID ID;
4703  QualifiedTemplateName::Profile(ID, NNS, TemplateKeyword, Template);
4704
4705  void *InsertPos = 0;
4706  QualifiedTemplateName *QTN =
4707    QualifiedTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4708  if (!QTN) {
4709    QTN = new (*this,4) QualifiedTemplateName(NNS, TemplateKeyword, Template);
4710    QualifiedTemplateNames.InsertNode(QTN, InsertPos);
4711  }
4712
4713  return TemplateName(QTN);
4714}
4715
4716/// \brief Retrieve the template name that represents a dependent
4717/// template name such as \c MetaFun::template apply.
4718TemplateName
4719ASTContext::getDependentTemplateName(NestedNameSpecifier *NNS,
4720                                     const IdentifierInfo *Name) const {
4721  assert((!NNS || NNS->isDependent()) &&
4722         "Nested name specifier must be dependent");
4723
4724  llvm::FoldingSetNodeID ID;
4725  DependentTemplateName::Profile(ID, NNS, Name);
4726
4727  void *InsertPos = 0;
4728  DependentTemplateName *QTN =
4729    DependentTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4730
4731  if (QTN)
4732    return TemplateName(QTN);
4733
4734  NestedNameSpecifier *CanonNNS = getCanonicalNestedNameSpecifier(NNS);
4735  if (CanonNNS == NNS) {
4736    QTN = new (*this,4) DependentTemplateName(NNS, Name);
4737  } else {
4738    TemplateName Canon = getDependentTemplateName(CanonNNS, Name);
4739    QTN = new (*this,4) DependentTemplateName(NNS, Name, Canon);
4740    DependentTemplateName *CheckQTN =
4741      DependentTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4742    assert(!CheckQTN && "Dependent type name canonicalization broken");
4743    (void)CheckQTN;
4744  }
4745
4746  DependentTemplateNames.InsertNode(QTN, InsertPos);
4747  return TemplateName(QTN);
4748}
4749
4750/// \brief Retrieve the template name that represents a dependent
4751/// template name such as \c MetaFun::template operator+.
4752TemplateName
4753ASTContext::getDependentTemplateName(NestedNameSpecifier *NNS,
4754                                     OverloadedOperatorKind Operator) const {
4755  assert((!NNS || NNS->isDependent()) &&
4756         "Nested name specifier must be dependent");
4757
4758  llvm::FoldingSetNodeID ID;
4759  DependentTemplateName::Profile(ID, NNS, Operator);
4760
4761  void *InsertPos = 0;
4762  DependentTemplateName *QTN
4763    = DependentTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4764
4765  if (QTN)
4766    return TemplateName(QTN);
4767
4768  NestedNameSpecifier *CanonNNS = getCanonicalNestedNameSpecifier(NNS);
4769  if (CanonNNS == NNS) {
4770    QTN = new (*this,4) DependentTemplateName(NNS, Operator);
4771  } else {
4772    TemplateName Canon = getDependentTemplateName(CanonNNS, Operator);
4773    QTN = new (*this,4) DependentTemplateName(NNS, Operator, Canon);
4774
4775    DependentTemplateName *CheckQTN
4776      = DependentTemplateNames.FindNodeOrInsertPos(ID, InsertPos);
4777    assert(!CheckQTN && "Dependent template name canonicalization broken");
4778    (void)CheckQTN;
4779  }
4780
4781  DependentTemplateNames.InsertNode(QTN, InsertPos);
4782  return TemplateName(QTN);
4783}
4784
4785TemplateName
4786ASTContext::getSubstTemplateTemplateParmPack(TemplateTemplateParmDecl *Param,
4787                                       const TemplateArgument &ArgPack) const {
4788  ASTContext &Self = const_cast<ASTContext &>(*this);
4789  llvm::FoldingSetNodeID ID;
4790  SubstTemplateTemplateParmPackStorage::Profile(ID, Self, Param, ArgPack);
4791
4792  void *InsertPos = 0;
4793  SubstTemplateTemplateParmPackStorage *Subst
4794    = SubstTemplateTemplateParmPacks.FindNodeOrInsertPos(ID, InsertPos);
4795
4796  if (!Subst) {
4797    Subst = new (*this) SubstTemplateTemplateParmPackStorage(Self, Param,
4798                                                           ArgPack.pack_size(),
4799                                                         ArgPack.pack_begin());
4800    SubstTemplateTemplateParmPacks.InsertNode(Subst, InsertPos);
4801  }
4802
4803  return TemplateName(Subst);
4804}
4805
4806/// getFromTargetType - Given one of the integer types provided by
4807/// TargetInfo, produce the corresponding type. The unsigned @p Type
4808/// is actually a value of type @c TargetInfo::IntType.
4809CanQualType ASTContext::getFromTargetType(unsigned Type) const {
4810  switch (Type) {
4811  case TargetInfo::NoInt: return CanQualType();
4812  case TargetInfo::SignedShort: return ShortTy;
4813  case TargetInfo::UnsignedShort: return UnsignedShortTy;
4814  case TargetInfo::SignedInt: return IntTy;
4815  case TargetInfo::UnsignedInt: return UnsignedIntTy;
4816  case TargetInfo::SignedLong: return LongTy;
4817  case TargetInfo::UnsignedLong: return UnsignedLongTy;
4818  case TargetInfo::SignedLongLong: return LongLongTy;
4819  case TargetInfo::UnsignedLongLong: return UnsignedLongLongTy;
4820  }
4821
4822  assert(false && "Unhandled TargetInfo::IntType value");
4823  return CanQualType();
4824}
4825
4826//===----------------------------------------------------------------------===//
4827//                        Type Predicates.
4828//===----------------------------------------------------------------------===//
4829
4830/// getObjCGCAttr - Returns one of GCNone, Weak or Strong objc's
4831/// garbage collection attribute.
4832///
4833Qualifiers::GC ASTContext::getObjCGCAttrKind(QualType Ty) const {
4834  if (getLangOptions().getGCMode() == LangOptions::NonGC)
4835    return Qualifiers::GCNone;
4836
4837  assert(getLangOptions().ObjC1);
4838  Qualifiers::GC GCAttrs = Ty.getObjCGCAttr();
4839
4840  // Default behaviour under objective-C's gc is for ObjC pointers
4841  // (or pointers to them) be treated as though they were declared
4842  // as __strong.
4843  if (GCAttrs == Qualifiers::GCNone) {
4844    if (Ty->isObjCObjectPointerType() || Ty->isBlockPointerType())
4845      return Qualifiers::Strong;
4846    else if (Ty->isPointerType())
4847      return getObjCGCAttrKind(Ty->getAs<PointerType>()->getPointeeType());
4848  } else {
4849    // It's not valid to set GC attributes on anything that isn't a
4850    // pointer.
4851#ifndef NDEBUG
4852    QualType CT = Ty->getCanonicalTypeInternal();
4853    while (const ArrayType *AT = dyn_cast<ArrayType>(CT))
4854      CT = AT->getElementType();
4855    assert(CT->isAnyPointerType() || CT->isBlockPointerType());
4856#endif
4857  }
4858  return GCAttrs;
4859}
4860
4861//===----------------------------------------------------------------------===//
4862//                        Type Compatibility Testing
4863//===----------------------------------------------------------------------===//
4864
4865/// areCompatVectorTypes - Return true if the two specified vector types are
4866/// compatible.
4867static bool areCompatVectorTypes(const VectorType *LHS,
4868                                 const VectorType *RHS) {
4869  assert(LHS->isCanonicalUnqualified() && RHS->isCanonicalUnqualified());
4870  return LHS->getElementType() == RHS->getElementType() &&
4871         LHS->getNumElements() == RHS->getNumElements();
4872}
4873
4874bool ASTContext::areCompatibleVectorTypes(QualType FirstVec,
4875                                          QualType SecondVec) {
4876  assert(FirstVec->isVectorType() && "FirstVec should be a vector type");
4877  assert(SecondVec->isVectorType() && "SecondVec should be a vector type");
4878
4879  if (hasSameUnqualifiedType(FirstVec, SecondVec))
4880    return true;
4881
4882  // Treat Neon vector types and most AltiVec vector types as if they are the
4883  // equivalent GCC vector types.
4884  const VectorType *First = FirstVec->getAs<VectorType>();
4885  const VectorType *Second = SecondVec->getAs<VectorType>();
4886  if (First->getNumElements() == Second->getNumElements() &&
4887      hasSameType(First->getElementType(), Second->getElementType()) &&
4888      First->getVectorKind() != VectorType::AltiVecPixel &&
4889      First->getVectorKind() != VectorType::AltiVecBool &&
4890      Second->getVectorKind() != VectorType::AltiVecPixel &&
4891      Second->getVectorKind() != VectorType::AltiVecBool)
4892    return true;
4893
4894  return false;
4895}
4896
4897//===----------------------------------------------------------------------===//
4898// ObjCQualifiedIdTypesAreCompatible - Compatibility testing for qualified id's.
4899//===----------------------------------------------------------------------===//
4900
4901/// ProtocolCompatibleWithProtocol - return 'true' if 'lProto' is in the
4902/// inheritance hierarchy of 'rProto'.
4903bool
4904ASTContext::ProtocolCompatibleWithProtocol(ObjCProtocolDecl *lProto,
4905                                           ObjCProtocolDecl *rProto) const {
4906  if (lProto == rProto)
4907    return true;
4908  for (ObjCProtocolDecl::protocol_iterator PI = rProto->protocol_begin(),
4909       E = rProto->protocol_end(); PI != E; ++PI)
4910    if (ProtocolCompatibleWithProtocol(lProto, *PI))
4911      return true;
4912  return false;
4913}
4914
4915/// QualifiedIdConformsQualifiedId - compare id<p,...> with id<p1,...>
4916/// return true if lhs's protocols conform to rhs's protocol; false
4917/// otherwise.
4918bool ASTContext::QualifiedIdConformsQualifiedId(QualType lhs, QualType rhs) {
4919  if (lhs->isObjCQualifiedIdType() && rhs->isObjCQualifiedIdType())
4920    return ObjCQualifiedIdTypesAreCompatible(lhs, rhs, false);
4921  return false;
4922}
4923
4924/// ObjCQualifiedClassTypesAreCompatible - compare  Class<p,...> and
4925/// Class<p1, ...>.
4926bool ASTContext::ObjCQualifiedClassTypesAreCompatible(QualType lhs,
4927                                                      QualType rhs) {
4928  const ObjCObjectPointerType *lhsQID = lhs->getAs<ObjCObjectPointerType>();
4929  const ObjCObjectPointerType *rhsOPT = rhs->getAs<ObjCObjectPointerType>();
4930  assert ((lhsQID && rhsOPT) && "ObjCQualifiedClassTypesAreCompatible");
4931
4932  for (ObjCObjectPointerType::qual_iterator I = lhsQID->qual_begin(),
4933       E = lhsQID->qual_end(); I != E; ++I) {
4934    bool match = false;
4935    ObjCProtocolDecl *lhsProto = *I;
4936    for (ObjCObjectPointerType::qual_iterator J = rhsOPT->qual_begin(),
4937         E = rhsOPT->qual_end(); J != E; ++J) {
4938      ObjCProtocolDecl *rhsProto = *J;
4939      if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto)) {
4940        match = true;
4941        break;
4942      }
4943    }
4944    if (!match)
4945      return false;
4946  }
4947  return true;
4948}
4949
4950/// ObjCQualifiedIdTypesAreCompatible - We know that one of lhs/rhs is an
4951/// ObjCQualifiedIDType.
4952bool ASTContext::ObjCQualifiedIdTypesAreCompatible(QualType lhs, QualType rhs,
4953                                                   bool compare) {
4954  // Allow id<P..> and an 'id' or void* type in all cases.
4955  if (lhs->isVoidPointerType() ||
4956      lhs->isObjCIdType() || lhs->isObjCClassType())
4957    return true;
4958  else if (rhs->isVoidPointerType() ||
4959           rhs->isObjCIdType() || rhs->isObjCClassType())
4960    return true;
4961
4962  if (const ObjCObjectPointerType *lhsQID = lhs->getAsObjCQualifiedIdType()) {
4963    const ObjCObjectPointerType *rhsOPT = rhs->getAs<ObjCObjectPointerType>();
4964
4965    if (!rhsOPT) return false;
4966
4967    if (rhsOPT->qual_empty()) {
4968      // If the RHS is a unqualified interface pointer "NSString*",
4969      // make sure we check the class hierarchy.
4970      if (ObjCInterfaceDecl *rhsID = rhsOPT->getInterfaceDecl()) {
4971        for (ObjCObjectPointerType::qual_iterator I = lhsQID->qual_begin(),
4972             E = lhsQID->qual_end(); I != E; ++I) {
4973          // when comparing an id<P> on lhs with a static type on rhs,
4974          // see if static class implements all of id's protocols, directly or
4975          // through its super class and categories.
4976          if (!rhsID->ClassImplementsProtocol(*I, true))
4977            return false;
4978        }
4979      }
4980      // If there are no qualifiers and no interface, we have an 'id'.
4981      return true;
4982    }
4983    // Both the right and left sides have qualifiers.
4984    for (ObjCObjectPointerType::qual_iterator I = lhsQID->qual_begin(),
4985         E = lhsQID->qual_end(); I != E; ++I) {
4986      ObjCProtocolDecl *lhsProto = *I;
4987      bool match = false;
4988
4989      // when comparing an id<P> on lhs with a static type on rhs,
4990      // see if static class implements all of id's protocols, directly or
4991      // through its super class and categories.
4992      for (ObjCObjectPointerType::qual_iterator J = rhsOPT->qual_begin(),
4993           E = rhsOPT->qual_end(); J != E; ++J) {
4994        ObjCProtocolDecl *rhsProto = *J;
4995        if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto) ||
4996            (compare && ProtocolCompatibleWithProtocol(rhsProto, lhsProto))) {
4997          match = true;
4998          break;
4999        }
5000      }
5001      // If the RHS is a qualified interface pointer "NSString<P>*",
5002      // make sure we check the class hierarchy.
5003      if (ObjCInterfaceDecl *rhsID = rhsOPT->getInterfaceDecl()) {
5004        for (ObjCObjectPointerType::qual_iterator I = lhsQID->qual_begin(),
5005             E = lhsQID->qual_end(); I != E; ++I) {
5006          // when comparing an id<P> on lhs with a static type on rhs,
5007          // see if static class implements all of id's protocols, directly or
5008          // through its super class and categories.
5009          if (rhsID->ClassImplementsProtocol(*I, true)) {
5010            match = true;
5011            break;
5012          }
5013        }
5014      }
5015      if (!match)
5016        return false;
5017    }
5018
5019    return true;
5020  }
5021
5022  const ObjCObjectPointerType *rhsQID = rhs->getAsObjCQualifiedIdType();
5023  assert(rhsQID && "One of the LHS/RHS should be id<x>");
5024
5025  if (const ObjCObjectPointerType *lhsOPT =
5026        lhs->getAsObjCInterfacePointerType()) {
5027    // If both the right and left sides have qualifiers.
5028    for (ObjCObjectPointerType::qual_iterator I = lhsOPT->qual_begin(),
5029         E = lhsOPT->qual_end(); I != E; ++I) {
5030      ObjCProtocolDecl *lhsProto = *I;
5031      bool match = false;
5032
5033      // when comparing an id<P> on rhs with a static type on lhs,
5034      // see if static class implements all of id's protocols, directly or
5035      // through its super class and categories.
5036      // First, lhs protocols in the qualifier list must be found, direct
5037      // or indirect in rhs's qualifier list or it is a mismatch.
5038      for (ObjCObjectPointerType::qual_iterator J = rhsQID->qual_begin(),
5039           E = rhsQID->qual_end(); J != E; ++J) {
5040        ObjCProtocolDecl *rhsProto = *J;
5041        if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto) ||
5042            (compare && ProtocolCompatibleWithProtocol(rhsProto, lhsProto))) {
5043          match = true;
5044          break;
5045        }
5046      }
5047      if (!match)
5048        return false;
5049    }
5050
5051    // Static class's protocols, or its super class or category protocols
5052    // must be found, direct or indirect in rhs's qualifier list or it is a mismatch.
5053    if (ObjCInterfaceDecl *lhsID = lhsOPT->getInterfaceDecl()) {
5054      llvm::SmallPtrSet<ObjCProtocolDecl *, 8> LHSInheritedProtocols;
5055      CollectInheritedProtocols(lhsID, LHSInheritedProtocols);
5056      // This is rather dubious but matches gcc's behavior. If lhs has
5057      // no type qualifier and its class has no static protocol(s)
5058      // assume that it is mismatch.
5059      if (LHSInheritedProtocols.empty() && lhsOPT->qual_empty())
5060        return false;
5061      for (llvm::SmallPtrSet<ObjCProtocolDecl*,8>::iterator I =
5062           LHSInheritedProtocols.begin(),
5063           E = LHSInheritedProtocols.end(); I != E; ++I) {
5064        bool match = false;
5065        ObjCProtocolDecl *lhsProto = (*I);
5066        for (ObjCObjectPointerType::qual_iterator J = rhsQID->qual_begin(),
5067             E = rhsQID->qual_end(); J != E; ++J) {
5068          ObjCProtocolDecl *rhsProto = *J;
5069          if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto) ||
5070              (compare && ProtocolCompatibleWithProtocol(rhsProto, lhsProto))) {
5071            match = true;
5072            break;
5073          }
5074        }
5075        if (!match)
5076          return false;
5077      }
5078    }
5079    return true;
5080  }
5081  return false;
5082}
5083
5084/// canAssignObjCInterfaces - Return true if the two interface types are
5085/// compatible for assignment from RHS to LHS.  This handles validation of any
5086/// protocol qualifiers on the LHS or RHS.
5087///
5088bool ASTContext::canAssignObjCInterfaces(const ObjCObjectPointerType *LHSOPT,
5089                                         const ObjCObjectPointerType *RHSOPT) {
5090  const ObjCObjectType* LHS = LHSOPT->getObjectType();
5091  const ObjCObjectType* RHS = RHSOPT->getObjectType();
5092
5093  // If either type represents the built-in 'id' or 'Class' types, return true.
5094  if (LHS->isObjCUnqualifiedIdOrClass() ||
5095      RHS->isObjCUnqualifiedIdOrClass())
5096    return true;
5097
5098  if (LHS->isObjCQualifiedId() || RHS->isObjCQualifiedId())
5099    return ObjCQualifiedIdTypesAreCompatible(QualType(LHSOPT,0),
5100                                             QualType(RHSOPT,0),
5101                                             false);
5102
5103  if (LHS->isObjCQualifiedClass() && RHS->isObjCQualifiedClass())
5104    return ObjCQualifiedClassTypesAreCompatible(QualType(LHSOPT,0),
5105                                                QualType(RHSOPT,0));
5106
5107  // If we have 2 user-defined types, fall into that path.
5108  if (LHS->getInterface() && RHS->getInterface())
5109    return canAssignObjCInterfaces(LHS, RHS);
5110
5111  return false;
5112}
5113
5114/// canAssignObjCInterfacesInBlockPointer - This routine is specifically written
5115/// for providing type-safety for objective-c pointers used to pass/return
5116/// arguments in block literals. When passed as arguments, passing 'A*' where
5117/// 'id' is expected is not OK. Passing 'Sub *" where 'Super *" is expected is
5118/// not OK. For the return type, the opposite is not OK.
5119bool ASTContext::canAssignObjCInterfacesInBlockPointer(
5120                                         const ObjCObjectPointerType *LHSOPT,
5121                                         const ObjCObjectPointerType *RHSOPT,
5122                                         bool BlockReturnType) {
5123  if (RHSOPT->isObjCBuiltinType() || LHSOPT->isObjCIdType())
5124    return true;
5125
5126  if (LHSOPT->isObjCBuiltinType()) {
5127    return RHSOPT->isObjCBuiltinType() || RHSOPT->isObjCQualifiedIdType();
5128  }
5129
5130  if (LHSOPT->isObjCQualifiedIdType() || RHSOPT->isObjCQualifiedIdType())
5131    return ObjCQualifiedIdTypesAreCompatible(QualType(LHSOPT,0),
5132                                             QualType(RHSOPT,0),
5133                                             false);
5134
5135  const ObjCInterfaceType* LHS = LHSOPT->getInterfaceType();
5136  const ObjCInterfaceType* RHS = RHSOPT->getInterfaceType();
5137  if (LHS && RHS)  { // We have 2 user-defined types.
5138    if (LHS != RHS) {
5139      if (LHS->getDecl()->isSuperClassOf(RHS->getDecl()))
5140        return BlockReturnType;
5141      if (RHS->getDecl()->isSuperClassOf(LHS->getDecl()))
5142        return !BlockReturnType;
5143    }
5144    else
5145      return true;
5146  }
5147  return false;
5148}
5149
5150/// getIntersectionOfProtocols - This routine finds the intersection of set
5151/// of protocols inherited from two distinct objective-c pointer objects.
5152/// It is used to build composite qualifier list of the composite type of
5153/// the conditional expression involving two objective-c pointer objects.
5154static
5155void getIntersectionOfProtocols(ASTContext &Context,
5156                                const ObjCObjectPointerType *LHSOPT,
5157                                const ObjCObjectPointerType *RHSOPT,
5158      llvm::SmallVectorImpl<ObjCProtocolDecl *> &IntersectionOfProtocols) {
5159
5160  const ObjCObjectType* LHS = LHSOPT->getObjectType();
5161  const ObjCObjectType* RHS = RHSOPT->getObjectType();
5162  assert(LHS->getInterface() && "LHS must have an interface base");
5163  assert(RHS->getInterface() && "RHS must have an interface base");
5164
5165  llvm::SmallPtrSet<ObjCProtocolDecl *, 8> InheritedProtocolSet;
5166  unsigned LHSNumProtocols = LHS->getNumProtocols();
5167  if (LHSNumProtocols > 0)
5168    InheritedProtocolSet.insert(LHS->qual_begin(), LHS->qual_end());
5169  else {
5170    llvm::SmallPtrSet<ObjCProtocolDecl *, 8> LHSInheritedProtocols;
5171    Context.CollectInheritedProtocols(LHS->getInterface(),
5172                                      LHSInheritedProtocols);
5173    InheritedProtocolSet.insert(LHSInheritedProtocols.begin(),
5174                                LHSInheritedProtocols.end());
5175  }
5176
5177  unsigned RHSNumProtocols = RHS->getNumProtocols();
5178  if (RHSNumProtocols > 0) {
5179    ObjCProtocolDecl **RHSProtocols =
5180      const_cast<ObjCProtocolDecl **>(RHS->qual_begin());
5181    for (unsigned i = 0; i < RHSNumProtocols; ++i)
5182      if (InheritedProtocolSet.count(RHSProtocols[i]))
5183        IntersectionOfProtocols.push_back(RHSProtocols[i]);
5184  }
5185  else {
5186    llvm::SmallPtrSet<ObjCProtocolDecl *, 8> RHSInheritedProtocols;
5187    Context.CollectInheritedProtocols(RHS->getInterface(),
5188                                      RHSInheritedProtocols);
5189    for (llvm::SmallPtrSet<ObjCProtocolDecl*,8>::iterator I =
5190         RHSInheritedProtocols.begin(),
5191         E = RHSInheritedProtocols.end(); I != E; ++I)
5192      if (InheritedProtocolSet.count((*I)))
5193        IntersectionOfProtocols.push_back((*I));
5194  }
5195}
5196
5197/// areCommonBaseCompatible - Returns common base class of the two classes if
5198/// one found. Note that this is O'2 algorithm. But it will be called as the
5199/// last type comparison in a ?-exp of ObjC pointer types before a
5200/// warning is issued. So, its invokation is extremely rare.
5201QualType ASTContext::areCommonBaseCompatible(
5202                                          const ObjCObjectPointerType *Lptr,
5203                                          const ObjCObjectPointerType *Rptr) {
5204  const ObjCObjectType *LHS = Lptr->getObjectType();
5205  const ObjCObjectType *RHS = Rptr->getObjectType();
5206  const ObjCInterfaceDecl* LDecl = LHS->getInterface();
5207  const ObjCInterfaceDecl* RDecl = RHS->getInterface();
5208  if (!LDecl || !RDecl || (LDecl == RDecl))
5209    return QualType();
5210
5211  do {
5212    LHS = cast<ObjCInterfaceType>(getObjCInterfaceType(LDecl));
5213    if (canAssignObjCInterfaces(LHS, RHS)) {
5214      llvm::SmallVector<ObjCProtocolDecl *, 8> Protocols;
5215      getIntersectionOfProtocols(*this, Lptr, Rptr, Protocols);
5216
5217      QualType Result = QualType(LHS, 0);
5218      if (!Protocols.empty())
5219        Result = getObjCObjectType(Result, Protocols.data(), Protocols.size());
5220      Result = getObjCObjectPointerType(Result);
5221      return Result;
5222    }
5223  } while ((LDecl = LDecl->getSuperClass()));
5224
5225  return QualType();
5226}
5227
5228bool ASTContext::canAssignObjCInterfaces(const ObjCObjectType *LHS,
5229                                         const ObjCObjectType *RHS) {
5230  assert(LHS->getInterface() && "LHS is not an interface type");
5231  assert(RHS->getInterface() && "RHS is not an interface type");
5232
5233  // Verify that the base decls are compatible: the RHS must be a subclass of
5234  // the LHS.
5235  if (!LHS->getInterface()->isSuperClassOf(RHS->getInterface()))
5236    return false;
5237
5238  // RHS must have a superset of the protocols in the LHS.  If the LHS is not
5239  // protocol qualified at all, then we are good.
5240  if (LHS->getNumProtocols() == 0)
5241    return true;
5242
5243  // Okay, we know the LHS has protocol qualifiers.  If the RHS doesn't,
5244  // more detailed analysis is required.
5245  if (RHS->getNumProtocols() == 0) {
5246    // OK, if LHS is a superclass of RHS *and*
5247    // this superclass is assignment compatible with LHS.
5248    // false otherwise.
5249    bool IsSuperClass =
5250      LHS->getInterface()->isSuperClassOf(RHS->getInterface());
5251    if (IsSuperClass) {
5252      // OK if conversion of LHS to SuperClass results in narrowing of types
5253      // ; i.e., SuperClass may implement at least one of the protocols
5254      // in LHS's protocol list. Example, SuperObj<P1> = lhs<P1,P2> is ok.
5255      // But not SuperObj<P1,P2,P3> = lhs<P1,P2>.
5256      llvm::SmallPtrSet<ObjCProtocolDecl *, 8> SuperClassInheritedProtocols;
5257      CollectInheritedProtocols(RHS->getInterface(), SuperClassInheritedProtocols);
5258      // If super class has no protocols, it is not a match.
5259      if (SuperClassInheritedProtocols.empty())
5260        return false;
5261
5262      for (ObjCObjectType::qual_iterator LHSPI = LHS->qual_begin(),
5263           LHSPE = LHS->qual_end();
5264           LHSPI != LHSPE; LHSPI++) {
5265        bool SuperImplementsProtocol = false;
5266        ObjCProtocolDecl *LHSProto = (*LHSPI);
5267
5268        for (llvm::SmallPtrSet<ObjCProtocolDecl*,8>::iterator I =
5269             SuperClassInheritedProtocols.begin(),
5270             E = SuperClassInheritedProtocols.end(); I != E; ++I) {
5271          ObjCProtocolDecl *SuperClassProto = (*I);
5272          if (SuperClassProto->lookupProtocolNamed(LHSProto->getIdentifier())) {
5273            SuperImplementsProtocol = true;
5274            break;
5275          }
5276        }
5277        if (!SuperImplementsProtocol)
5278          return false;
5279      }
5280      return true;
5281    }
5282    return false;
5283  }
5284
5285  for (ObjCObjectType::qual_iterator LHSPI = LHS->qual_begin(),
5286                                     LHSPE = LHS->qual_end();
5287       LHSPI != LHSPE; LHSPI++) {
5288    bool RHSImplementsProtocol = false;
5289
5290    // If the RHS doesn't implement the protocol on the left, the types
5291    // are incompatible.
5292    for (ObjCObjectType::qual_iterator RHSPI = RHS->qual_begin(),
5293                                       RHSPE = RHS->qual_end();
5294         RHSPI != RHSPE; RHSPI++) {
5295      if ((*RHSPI)->lookupProtocolNamed((*LHSPI)->getIdentifier())) {
5296        RHSImplementsProtocol = true;
5297        break;
5298      }
5299    }
5300    // FIXME: For better diagnostics, consider passing back the protocol name.
5301    if (!RHSImplementsProtocol)
5302      return false;
5303  }
5304  // The RHS implements all protocols listed on the LHS.
5305  return true;
5306}
5307
5308bool ASTContext::areComparableObjCPointerTypes(QualType LHS, QualType RHS) {
5309  // get the "pointed to" types
5310  const ObjCObjectPointerType *LHSOPT = LHS->getAs<ObjCObjectPointerType>();
5311  const ObjCObjectPointerType *RHSOPT = RHS->getAs<ObjCObjectPointerType>();
5312
5313  if (!LHSOPT || !RHSOPT)
5314    return false;
5315
5316  return canAssignObjCInterfaces(LHSOPT, RHSOPT) ||
5317         canAssignObjCInterfaces(RHSOPT, LHSOPT);
5318}
5319
5320bool ASTContext::canBindObjCObjectType(QualType To, QualType From) {
5321  return canAssignObjCInterfaces(
5322                getObjCObjectPointerType(To)->getAs<ObjCObjectPointerType>(),
5323                getObjCObjectPointerType(From)->getAs<ObjCObjectPointerType>());
5324}
5325
5326/// typesAreCompatible - C99 6.7.3p9: For two qualified types to be compatible,
5327/// both shall have the identically qualified version of a compatible type.
5328/// C99 6.2.7p1: Two types have compatible types if their types are the
5329/// same. See 6.7.[2,3,5] for additional rules.
5330bool ASTContext::typesAreCompatible(QualType LHS, QualType RHS,
5331                                    bool CompareUnqualified) {
5332  if (getLangOptions().CPlusPlus)
5333    return hasSameType(LHS, RHS);
5334
5335  return !mergeTypes(LHS, RHS, false, CompareUnqualified).isNull();
5336}
5337
5338bool ASTContext::typesAreBlockPointerCompatible(QualType LHS, QualType RHS) {
5339  return !mergeTypes(LHS, RHS, true).isNull();
5340}
5341
5342/// mergeTransparentUnionType - if T is a transparent union type and a member
5343/// of T is compatible with SubType, return the merged type, else return
5344/// QualType()
5345QualType ASTContext::mergeTransparentUnionType(QualType T, QualType SubType,
5346                                               bool OfBlockPointer,
5347                                               bool Unqualified) {
5348  if (const RecordType *UT = T->getAsUnionType()) {
5349    RecordDecl *UD = UT->getDecl();
5350    if (UD->hasAttr<TransparentUnionAttr>()) {
5351      for (RecordDecl::field_iterator it = UD->field_begin(),
5352           itend = UD->field_end(); it != itend; ++it) {
5353        QualType ET = it->getType().getUnqualifiedType();
5354        QualType MT = mergeTypes(ET, SubType, OfBlockPointer, Unqualified);
5355        if (!MT.isNull())
5356          return MT;
5357      }
5358    }
5359  }
5360
5361  return QualType();
5362}
5363
5364/// mergeFunctionArgumentTypes - merge two types which appear as function
5365/// argument types
5366QualType ASTContext::mergeFunctionArgumentTypes(QualType lhs, QualType rhs,
5367                                                bool OfBlockPointer,
5368                                                bool Unqualified) {
5369  // GNU extension: two types are compatible if they appear as a function
5370  // argument, one of the types is a transparent union type and the other
5371  // type is compatible with a union member
5372  QualType lmerge = mergeTransparentUnionType(lhs, rhs, OfBlockPointer,
5373                                              Unqualified);
5374  if (!lmerge.isNull())
5375    return lmerge;
5376
5377  QualType rmerge = mergeTransparentUnionType(rhs, lhs, OfBlockPointer,
5378                                              Unqualified);
5379  if (!rmerge.isNull())
5380    return rmerge;
5381
5382  return mergeTypes(lhs, rhs, OfBlockPointer, Unqualified);
5383}
5384
5385QualType ASTContext::mergeFunctionTypes(QualType lhs, QualType rhs,
5386                                        bool OfBlockPointer,
5387                                        bool Unqualified) {
5388  const FunctionType *lbase = lhs->getAs<FunctionType>();
5389  const FunctionType *rbase = rhs->getAs<FunctionType>();
5390  const FunctionProtoType *lproto = dyn_cast<FunctionProtoType>(lbase);
5391  const FunctionProtoType *rproto = dyn_cast<FunctionProtoType>(rbase);
5392  bool allLTypes = true;
5393  bool allRTypes = true;
5394
5395  // Check return type
5396  QualType retType;
5397  if (OfBlockPointer) {
5398    QualType RHS = rbase->getResultType();
5399    QualType LHS = lbase->getResultType();
5400    bool UnqualifiedResult = Unqualified;
5401    if (!UnqualifiedResult)
5402      UnqualifiedResult = (!RHS.hasQualifiers() && LHS.hasQualifiers());
5403    retType = mergeTypes(LHS, RHS, true, UnqualifiedResult, true);
5404  }
5405  else
5406    retType = mergeTypes(lbase->getResultType(), rbase->getResultType(), false,
5407                         Unqualified);
5408  if (retType.isNull()) return QualType();
5409
5410  if (Unqualified)
5411    retType = retType.getUnqualifiedType();
5412
5413  CanQualType LRetType = getCanonicalType(lbase->getResultType());
5414  CanQualType RRetType = getCanonicalType(rbase->getResultType());
5415  if (Unqualified) {
5416    LRetType = LRetType.getUnqualifiedType();
5417    RRetType = RRetType.getUnqualifiedType();
5418  }
5419
5420  if (getCanonicalType(retType) != LRetType)
5421    allLTypes = false;
5422  if (getCanonicalType(retType) != RRetType)
5423    allRTypes = false;
5424
5425  // FIXME: double check this
5426  // FIXME: should we error if lbase->getRegParmAttr() != 0 &&
5427  //                           rbase->getRegParmAttr() != 0 &&
5428  //                           lbase->getRegParmAttr() != rbase->getRegParmAttr()?
5429  FunctionType::ExtInfo lbaseInfo = lbase->getExtInfo();
5430  FunctionType::ExtInfo rbaseInfo = rbase->getExtInfo();
5431
5432  // Compatible functions must have compatible calling conventions
5433  if (!isSameCallConv(lbaseInfo.getCC(), rbaseInfo.getCC()))
5434    return QualType();
5435
5436  // Regparm is part of the calling convention.
5437  if (lbaseInfo.getHasRegParm() != rbaseInfo.getHasRegParm())
5438    return QualType();
5439  if (lbaseInfo.getRegParm() != rbaseInfo.getRegParm())
5440    return QualType();
5441
5442  if (lbaseInfo.getProducesResult() != rbaseInfo.getProducesResult())
5443    return QualType();
5444
5445  // It's noreturn if either type is.
5446  // FIXME: some uses, e.g. conditional exprs, really want this to be 'both'.
5447  bool NoReturn = lbaseInfo.getNoReturn() || rbaseInfo.getNoReturn();
5448  if (NoReturn != lbaseInfo.getNoReturn())
5449    allLTypes = false;
5450  if (NoReturn != rbaseInfo.getNoReturn())
5451    allRTypes = false;
5452
5453  FunctionType::ExtInfo einfo = lbaseInfo.withNoReturn(NoReturn);
5454
5455  if (lproto && rproto) { // two C99 style function prototypes
5456    assert(!lproto->hasExceptionSpec() && !rproto->hasExceptionSpec() &&
5457           "C++ shouldn't be here");
5458    unsigned lproto_nargs = lproto->getNumArgs();
5459    unsigned rproto_nargs = rproto->getNumArgs();
5460
5461    // Compatible functions must have the same number of arguments
5462    if (lproto_nargs != rproto_nargs)
5463      return QualType();
5464
5465    // Variadic and non-variadic functions aren't compatible
5466    if (lproto->isVariadic() != rproto->isVariadic())
5467      return QualType();
5468
5469    if (lproto->getTypeQuals() != rproto->getTypeQuals())
5470      return QualType();
5471
5472    // Check argument compatibility
5473    llvm::SmallVector<QualType, 10> types;
5474    for (unsigned i = 0; i < lproto_nargs; i++) {
5475      QualType largtype = lproto->getArgType(i).getUnqualifiedType();
5476      QualType rargtype = rproto->getArgType(i).getUnqualifiedType();
5477      QualType argtype = mergeFunctionArgumentTypes(largtype, rargtype,
5478                                                    OfBlockPointer,
5479                                                    Unqualified);
5480      if (argtype.isNull()) return QualType();
5481
5482      if (Unqualified)
5483        argtype = argtype.getUnqualifiedType();
5484
5485      types.push_back(argtype);
5486      if (Unqualified) {
5487        largtype = largtype.getUnqualifiedType();
5488        rargtype = rargtype.getUnqualifiedType();
5489      }
5490
5491      if (getCanonicalType(argtype) != getCanonicalType(largtype))
5492        allLTypes = false;
5493      if (getCanonicalType(argtype) != getCanonicalType(rargtype))
5494        allRTypes = false;
5495    }
5496    if (allLTypes) return lhs;
5497    if (allRTypes) return rhs;
5498
5499    FunctionProtoType::ExtProtoInfo EPI = lproto->getExtProtoInfo();
5500    EPI.ExtInfo = einfo;
5501    return getFunctionType(retType, types.begin(), types.size(), EPI);
5502  }
5503
5504  if (lproto) allRTypes = false;
5505  if (rproto) allLTypes = false;
5506
5507  const FunctionProtoType *proto = lproto ? lproto : rproto;
5508  if (proto) {
5509    assert(!proto->hasExceptionSpec() && "C++ shouldn't be here");
5510    if (proto->isVariadic()) return QualType();
5511    // Check that the types are compatible with the types that
5512    // would result from default argument promotions (C99 6.7.5.3p15).
5513    // The only types actually affected are promotable integer
5514    // types and floats, which would be passed as a different
5515    // type depending on whether the prototype is visible.
5516    unsigned proto_nargs = proto->getNumArgs();
5517    for (unsigned i = 0; i < proto_nargs; ++i) {
5518      QualType argTy = proto->getArgType(i);
5519
5520      // Look at the promotion type of enum types, since that is the type used
5521      // to pass enum values.
5522      if (const EnumType *Enum = argTy->getAs<EnumType>())
5523        argTy = Enum->getDecl()->getPromotionType();
5524
5525      if (argTy->isPromotableIntegerType() ||
5526          getCanonicalType(argTy).getUnqualifiedType() == FloatTy)
5527        return QualType();
5528    }
5529
5530    if (allLTypes) return lhs;
5531    if (allRTypes) return rhs;
5532
5533    FunctionProtoType::ExtProtoInfo EPI = proto->getExtProtoInfo();
5534    EPI.ExtInfo = einfo;
5535    return getFunctionType(retType, proto->arg_type_begin(),
5536                           proto->getNumArgs(), EPI);
5537  }
5538
5539  if (allLTypes) return lhs;
5540  if (allRTypes) return rhs;
5541  return getFunctionNoProtoType(retType, einfo);
5542}
5543
5544QualType ASTContext::mergeTypes(QualType LHS, QualType RHS,
5545                                bool OfBlockPointer,
5546                                bool Unqualified, bool BlockReturnType) {
5547  // C++ [expr]: If an expression initially has the type "reference to T", the
5548  // type is adjusted to "T" prior to any further analysis, the expression
5549  // designates the object or function denoted by the reference, and the
5550  // expression is an lvalue unless the reference is an rvalue reference and
5551  // the expression is a function call (possibly inside parentheses).
5552  assert(!LHS->getAs<ReferenceType>() && "LHS is a reference type?");
5553  assert(!RHS->getAs<ReferenceType>() && "RHS is a reference type?");
5554
5555  if (Unqualified) {
5556    LHS = LHS.getUnqualifiedType();
5557    RHS = RHS.getUnqualifiedType();
5558  }
5559
5560  QualType LHSCan = getCanonicalType(LHS),
5561           RHSCan = getCanonicalType(RHS);
5562
5563  // If two types are identical, they are compatible.
5564  if (LHSCan == RHSCan)
5565    return LHS;
5566
5567  // If the qualifiers are different, the types aren't compatible... mostly.
5568  Qualifiers LQuals = LHSCan.getLocalQualifiers();
5569  Qualifiers RQuals = RHSCan.getLocalQualifiers();
5570  if (LQuals != RQuals) {
5571    // If any of these qualifiers are different, we have a type
5572    // mismatch.
5573    if (LQuals.getCVRQualifiers() != RQuals.getCVRQualifiers() ||
5574        LQuals.getAddressSpace() != RQuals.getAddressSpace() ||
5575        LQuals.getObjCLifetime() != RQuals.getObjCLifetime())
5576      return QualType();
5577
5578    // Exactly one GC qualifier difference is allowed: __strong is
5579    // okay if the other type has no GC qualifier but is an Objective
5580    // C object pointer (i.e. implicitly strong by default).  We fix
5581    // this by pretending that the unqualified type was actually
5582    // qualified __strong.
5583    Qualifiers::GC GC_L = LQuals.getObjCGCAttr();
5584    Qualifiers::GC GC_R = RQuals.getObjCGCAttr();
5585    assert((GC_L != GC_R) && "unequal qualifier sets had only equal elements");
5586
5587    if (GC_L == Qualifiers::Weak || GC_R == Qualifiers::Weak)
5588      return QualType();
5589
5590    if (GC_L == Qualifiers::Strong && RHSCan->isObjCObjectPointerType()) {
5591      return mergeTypes(LHS, getObjCGCQualType(RHS, Qualifiers::Strong));
5592    }
5593    if (GC_R == Qualifiers::Strong && LHSCan->isObjCObjectPointerType()) {
5594      return mergeTypes(getObjCGCQualType(LHS, Qualifiers::Strong), RHS);
5595    }
5596    return QualType();
5597  }
5598
5599  // Okay, qualifiers are equal.
5600
5601  Type::TypeClass LHSClass = LHSCan->getTypeClass();
5602  Type::TypeClass RHSClass = RHSCan->getTypeClass();
5603
5604  // We want to consider the two function types to be the same for these
5605  // comparisons, just force one to the other.
5606  if (LHSClass == Type::FunctionProto) LHSClass = Type::FunctionNoProto;
5607  if (RHSClass == Type::FunctionProto) RHSClass = Type::FunctionNoProto;
5608
5609  // Same as above for arrays
5610  if (LHSClass == Type::VariableArray || LHSClass == Type::IncompleteArray)
5611    LHSClass = Type::ConstantArray;
5612  if (RHSClass == Type::VariableArray || RHSClass == Type::IncompleteArray)
5613    RHSClass = Type::ConstantArray;
5614
5615  // ObjCInterfaces are just specialized ObjCObjects.
5616  if (LHSClass == Type::ObjCInterface) LHSClass = Type::ObjCObject;
5617  if (RHSClass == Type::ObjCInterface) RHSClass = Type::ObjCObject;
5618
5619  // Canonicalize ExtVector -> Vector.
5620  if (LHSClass == Type::ExtVector) LHSClass = Type::Vector;
5621  if (RHSClass == Type::ExtVector) RHSClass = Type::Vector;
5622
5623  // If the canonical type classes don't match.
5624  if (LHSClass != RHSClass) {
5625    // C99 6.7.2.2p4: Each enumerated type shall be compatible with char,
5626    // a signed integer type, or an unsigned integer type.
5627    // Compatibility is based on the underlying type, not the promotion
5628    // type.
5629    if (const EnumType* ETy = LHS->getAs<EnumType>()) {
5630      if (ETy->getDecl()->getIntegerType() == RHSCan.getUnqualifiedType())
5631        return RHS;
5632    }
5633    if (const EnumType* ETy = RHS->getAs<EnumType>()) {
5634      if (ETy->getDecl()->getIntegerType() == LHSCan.getUnqualifiedType())
5635        return LHS;
5636    }
5637
5638    return QualType();
5639  }
5640
5641  // The canonical type classes match.
5642  switch (LHSClass) {
5643#define TYPE(Class, Base)
5644#define ABSTRACT_TYPE(Class, Base)
5645#define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class, Base) case Type::Class:
5646#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
5647#define DEPENDENT_TYPE(Class, Base) case Type::Class:
5648#include "clang/AST/TypeNodes.def"
5649    assert(false && "Non-canonical and dependent types shouldn't get here");
5650    return QualType();
5651
5652  case Type::LValueReference:
5653  case Type::RValueReference:
5654  case Type::MemberPointer:
5655    assert(false && "C++ should never be in mergeTypes");
5656    return QualType();
5657
5658  case Type::ObjCInterface:
5659  case Type::IncompleteArray:
5660  case Type::VariableArray:
5661  case Type::FunctionProto:
5662  case Type::ExtVector:
5663    assert(false && "Types are eliminated above");
5664    return QualType();
5665
5666  case Type::Pointer:
5667  {
5668    // Merge two pointer types, while trying to preserve typedef info
5669    QualType LHSPointee = LHS->getAs<PointerType>()->getPointeeType();
5670    QualType RHSPointee = RHS->getAs<PointerType>()->getPointeeType();
5671    if (Unqualified) {
5672      LHSPointee = LHSPointee.getUnqualifiedType();
5673      RHSPointee = RHSPointee.getUnqualifiedType();
5674    }
5675    QualType ResultType = mergeTypes(LHSPointee, RHSPointee, false,
5676                                     Unqualified);
5677    if (ResultType.isNull()) return QualType();
5678    if (getCanonicalType(LHSPointee) == getCanonicalType(ResultType))
5679      return LHS;
5680    if (getCanonicalType(RHSPointee) == getCanonicalType(ResultType))
5681      return RHS;
5682    return getPointerType(ResultType);
5683  }
5684  case Type::BlockPointer:
5685  {
5686    // Merge two block pointer types, while trying to preserve typedef info
5687    QualType LHSPointee = LHS->getAs<BlockPointerType>()->getPointeeType();
5688    QualType RHSPointee = RHS->getAs<BlockPointerType>()->getPointeeType();
5689    if (Unqualified) {
5690      LHSPointee = LHSPointee.getUnqualifiedType();
5691      RHSPointee = RHSPointee.getUnqualifiedType();
5692    }
5693    QualType ResultType = mergeTypes(LHSPointee, RHSPointee, OfBlockPointer,
5694                                     Unqualified);
5695    if (ResultType.isNull()) return QualType();
5696    if (getCanonicalType(LHSPointee) == getCanonicalType(ResultType))
5697      return LHS;
5698    if (getCanonicalType(RHSPointee) == getCanonicalType(ResultType))
5699      return RHS;
5700    return getBlockPointerType(ResultType);
5701  }
5702  case Type::ConstantArray:
5703  {
5704    const ConstantArrayType* LCAT = getAsConstantArrayType(LHS);
5705    const ConstantArrayType* RCAT = getAsConstantArrayType(RHS);
5706    if (LCAT && RCAT && RCAT->getSize() != LCAT->getSize())
5707      return QualType();
5708
5709    QualType LHSElem = getAsArrayType(LHS)->getElementType();
5710    QualType RHSElem = getAsArrayType(RHS)->getElementType();
5711    if (Unqualified) {
5712      LHSElem = LHSElem.getUnqualifiedType();
5713      RHSElem = RHSElem.getUnqualifiedType();
5714    }
5715
5716    QualType ResultType = mergeTypes(LHSElem, RHSElem, false, Unqualified);
5717    if (ResultType.isNull()) return QualType();
5718    if (LCAT && getCanonicalType(LHSElem) == getCanonicalType(ResultType))
5719      return LHS;
5720    if (RCAT && getCanonicalType(RHSElem) == getCanonicalType(ResultType))
5721      return RHS;
5722    if (LCAT) return getConstantArrayType(ResultType, LCAT->getSize(),
5723                                          ArrayType::ArraySizeModifier(), 0);
5724    if (RCAT) return getConstantArrayType(ResultType, RCAT->getSize(),
5725                                          ArrayType::ArraySizeModifier(), 0);
5726    const VariableArrayType* LVAT = getAsVariableArrayType(LHS);
5727    const VariableArrayType* RVAT = getAsVariableArrayType(RHS);
5728    if (LVAT && getCanonicalType(LHSElem) == getCanonicalType(ResultType))
5729      return LHS;
5730    if (RVAT && getCanonicalType(RHSElem) == getCanonicalType(ResultType))
5731      return RHS;
5732    if (LVAT) {
5733      // FIXME: This isn't correct! But tricky to implement because
5734      // the array's size has to be the size of LHS, but the type
5735      // has to be different.
5736      return LHS;
5737    }
5738    if (RVAT) {
5739      // FIXME: This isn't correct! But tricky to implement because
5740      // the array's size has to be the size of RHS, but the type
5741      // has to be different.
5742      return RHS;
5743    }
5744    if (getCanonicalType(LHSElem) == getCanonicalType(ResultType)) return LHS;
5745    if (getCanonicalType(RHSElem) == getCanonicalType(ResultType)) return RHS;
5746    return getIncompleteArrayType(ResultType,
5747                                  ArrayType::ArraySizeModifier(), 0);
5748  }
5749  case Type::FunctionNoProto:
5750    return mergeFunctionTypes(LHS, RHS, OfBlockPointer, Unqualified);
5751  case Type::Record:
5752  case Type::Enum:
5753    return QualType();
5754  case Type::Builtin:
5755    // Only exactly equal builtin types are compatible, which is tested above.
5756    return QualType();
5757  case Type::Complex:
5758    // Distinct complex types are incompatible.
5759    return QualType();
5760  case Type::Vector:
5761    // FIXME: The merged type should be an ExtVector!
5762    if (areCompatVectorTypes(LHSCan->getAs<VectorType>(),
5763                             RHSCan->getAs<VectorType>()))
5764      return LHS;
5765    return QualType();
5766  case Type::ObjCObject: {
5767    // Check if the types are assignment compatible.
5768    // FIXME: This should be type compatibility, e.g. whether
5769    // "LHS x; RHS x;" at global scope is legal.
5770    const ObjCObjectType* LHSIface = LHS->getAs<ObjCObjectType>();
5771    const ObjCObjectType* RHSIface = RHS->getAs<ObjCObjectType>();
5772    if (canAssignObjCInterfaces(LHSIface, RHSIface))
5773      return LHS;
5774
5775    return QualType();
5776  }
5777  case Type::ObjCObjectPointer: {
5778    if (OfBlockPointer) {
5779      if (canAssignObjCInterfacesInBlockPointer(
5780                                          LHS->getAs<ObjCObjectPointerType>(),
5781                                          RHS->getAs<ObjCObjectPointerType>(),
5782                                          BlockReturnType))
5783      return LHS;
5784      return QualType();
5785    }
5786    if (canAssignObjCInterfaces(LHS->getAs<ObjCObjectPointerType>(),
5787                                RHS->getAs<ObjCObjectPointerType>()))
5788      return LHS;
5789
5790    return QualType();
5791    }
5792  }
5793
5794  return QualType();
5795}
5796
5797/// mergeObjCGCQualifiers - This routine merges ObjC's GC attribute of 'LHS' and
5798/// 'RHS' attributes and returns the merged version; including for function
5799/// return types.
5800QualType ASTContext::mergeObjCGCQualifiers(QualType LHS, QualType RHS) {
5801  QualType LHSCan = getCanonicalType(LHS),
5802  RHSCan = getCanonicalType(RHS);
5803  // If two types are identical, they are compatible.
5804  if (LHSCan == RHSCan)
5805    return LHS;
5806  if (RHSCan->isFunctionType()) {
5807    if (!LHSCan->isFunctionType())
5808      return QualType();
5809    QualType OldReturnType =
5810      cast<FunctionType>(RHSCan.getTypePtr())->getResultType();
5811    QualType NewReturnType =
5812      cast<FunctionType>(LHSCan.getTypePtr())->getResultType();
5813    QualType ResReturnType =
5814      mergeObjCGCQualifiers(NewReturnType, OldReturnType);
5815    if (ResReturnType.isNull())
5816      return QualType();
5817    if (ResReturnType == NewReturnType || ResReturnType == OldReturnType) {
5818      // id foo(); ... __strong id foo(); or: __strong id foo(); ... id foo();
5819      // In either case, use OldReturnType to build the new function type.
5820      const FunctionType *F = LHS->getAs<FunctionType>();
5821      if (const FunctionProtoType *FPT = cast<FunctionProtoType>(F)) {
5822        FunctionProtoType::ExtProtoInfo EPI = FPT->getExtProtoInfo();
5823        EPI.ExtInfo = getFunctionExtInfo(LHS);
5824        QualType ResultType
5825          = getFunctionType(OldReturnType, FPT->arg_type_begin(),
5826                            FPT->getNumArgs(), EPI);
5827        return ResultType;
5828      }
5829    }
5830    return QualType();
5831  }
5832
5833  // If the qualifiers are different, the types can still be merged.
5834  Qualifiers LQuals = LHSCan.getLocalQualifiers();
5835  Qualifiers RQuals = RHSCan.getLocalQualifiers();
5836  if (LQuals != RQuals) {
5837    // If any of these qualifiers are different, we have a type mismatch.
5838    if (LQuals.getCVRQualifiers() != RQuals.getCVRQualifiers() ||
5839        LQuals.getAddressSpace() != RQuals.getAddressSpace())
5840      return QualType();
5841
5842    // Exactly one GC qualifier difference is allowed: __strong is
5843    // okay if the other type has no GC qualifier but is an Objective
5844    // C object pointer (i.e. implicitly strong by default).  We fix
5845    // this by pretending that the unqualified type was actually
5846    // qualified __strong.
5847    Qualifiers::GC GC_L = LQuals.getObjCGCAttr();
5848    Qualifiers::GC GC_R = RQuals.getObjCGCAttr();
5849    assert((GC_L != GC_R) && "unequal qualifier sets had only equal elements");
5850
5851    if (GC_L == Qualifiers::Weak || GC_R == Qualifiers::Weak)
5852      return QualType();
5853
5854    if (GC_L == Qualifiers::Strong)
5855      return LHS;
5856    if (GC_R == Qualifiers::Strong)
5857      return RHS;
5858    return QualType();
5859  }
5860
5861  if (LHSCan->isObjCObjectPointerType() && RHSCan->isObjCObjectPointerType()) {
5862    QualType LHSBaseQT = LHS->getAs<ObjCObjectPointerType>()->getPointeeType();
5863    QualType RHSBaseQT = RHS->getAs<ObjCObjectPointerType>()->getPointeeType();
5864    QualType ResQT = mergeObjCGCQualifiers(LHSBaseQT, RHSBaseQT);
5865    if (ResQT == LHSBaseQT)
5866      return LHS;
5867    if (ResQT == RHSBaseQT)
5868      return RHS;
5869  }
5870  return QualType();
5871}
5872
5873//===----------------------------------------------------------------------===//
5874//                         Integer Predicates
5875//===----------------------------------------------------------------------===//
5876
5877unsigned ASTContext::getIntWidth(QualType T) const {
5878  if (const EnumType *ET = dyn_cast<EnumType>(T))
5879    T = ET->getDecl()->getIntegerType();
5880  if (T->isBooleanType())
5881    return 1;
5882  // For builtin types, just use the standard type sizing method
5883  return (unsigned)getTypeSize(T);
5884}
5885
5886QualType ASTContext::getCorrespondingUnsignedType(QualType T) {
5887  assert(T->hasSignedIntegerRepresentation() && "Unexpected type");
5888
5889  // Turn <4 x signed int> -> <4 x unsigned int>
5890  if (const VectorType *VTy = T->getAs<VectorType>())
5891    return getVectorType(getCorrespondingUnsignedType(VTy->getElementType()),
5892                         VTy->getNumElements(), VTy->getVectorKind());
5893
5894  // For enums, we return the unsigned version of the base type.
5895  if (const EnumType *ETy = T->getAs<EnumType>())
5896    T = ETy->getDecl()->getIntegerType();
5897
5898  const BuiltinType *BTy = T->getAs<BuiltinType>();
5899  assert(BTy && "Unexpected signed integer type");
5900  switch (BTy->getKind()) {
5901  case BuiltinType::Char_S:
5902  case BuiltinType::SChar:
5903    return UnsignedCharTy;
5904  case BuiltinType::Short:
5905    return UnsignedShortTy;
5906  case BuiltinType::Int:
5907    return UnsignedIntTy;
5908  case BuiltinType::Long:
5909    return UnsignedLongTy;
5910  case BuiltinType::LongLong:
5911    return UnsignedLongLongTy;
5912  case BuiltinType::Int128:
5913    return UnsignedInt128Ty;
5914  default:
5915    assert(0 && "Unexpected signed integer type");
5916    return QualType();
5917  }
5918}
5919
5920ASTMutationListener::~ASTMutationListener() { }
5921
5922
5923//===----------------------------------------------------------------------===//
5924//                          Builtin Type Computation
5925//===----------------------------------------------------------------------===//
5926
5927/// DecodeTypeFromStr - This decodes one type descriptor from Str, advancing the
5928/// pointer over the consumed characters.  This returns the resultant type.  If
5929/// AllowTypeModifiers is false then modifier like * are not parsed, just basic
5930/// types.  This allows "v2i*" to be parsed as a pointer to a v2i instead of
5931/// a vector of "i*".
5932///
5933/// RequiresICE is filled in on return to indicate whether the value is required
5934/// to be an Integer Constant Expression.
5935static QualType DecodeTypeFromStr(const char *&Str, const ASTContext &Context,
5936                                  ASTContext::GetBuiltinTypeError &Error,
5937                                  bool &RequiresICE,
5938                                  bool AllowTypeModifiers) {
5939  // Modifiers.
5940  int HowLong = 0;
5941  bool Signed = false, Unsigned = false;
5942  RequiresICE = false;
5943
5944  // Read the prefixed modifiers first.
5945  bool Done = false;
5946  while (!Done) {
5947    switch (*Str++) {
5948    default: Done = true; --Str; break;
5949    case 'I':
5950      RequiresICE = true;
5951      break;
5952    case 'S':
5953      assert(!Unsigned && "Can't use both 'S' and 'U' modifiers!");
5954      assert(!Signed && "Can't use 'S' modifier multiple times!");
5955      Signed = true;
5956      break;
5957    case 'U':
5958      assert(!Signed && "Can't use both 'S' and 'U' modifiers!");
5959      assert(!Unsigned && "Can't use 'S' modifier multiple times!");
5960      Unsigned = true;
5961      break;
5962    case 'L':
5963      assert(HowLong <= 2 && "Can't have LLLL modifier");
5964      ++HowLong;
5965      break;
5966    }
5967  }
5968
5969  QualType Type;
5970
5971  // Read the base type.
5972  switch (*Str++) {
5973  default: assert(0 && "Unknown builtin type letter!");
5974  case 'v':
5975    assert(HowLong == 0 && !Signed && !Unsigned &&
5976           "Bad modifiers used with 'v'!");
5977    Type = Context.VoidTy;
5978    break;
5979  case 'f':
5980    assert(HowLong == 0 && !Signed && !Unsigned &&
5981           "Bad modifiers used with 'f'!");
5982    Type = Context.FloatTy;
5983    break;
5984  case 'd':
5985    assert(HowLong < 2 && !Signed && !Unsigned &&
5986           "Bad modifiers used with 'd'!");
5987    if (HowLong)
5988      Type = Context.LongDoubleTy;
5989    else
5990      Type = Context.DoubleTy;
5991    break;
5992  case 's':
5993    assert(HowLong == 0 && "Bad modifiers used with 's'!");
5994    if (Unsigned)
5995      Type = Context.UnsignedShortTy;
5996    else
5997      Type = Context.ShortTy;
5998    break;
5999  case 'i':
6000    if (HowLong == 3)
6001      Type = Unsigned ? Context.UnsignedInt128Ty : Context.Int128Ty;
6002    else if (HowLong == 2)
6003      Type = Unsigned ? Context.UnsignedLongLongTy : Context.LongLongTy;
6004    else if (HowLong == 1)
6005      Type = Unsigned ? Context.UnsignedLongTy : Context.LongTy;
6006    else
6007      Type = Unsigned ? Context.UnsignedIntTy : Context.IntTy;
6008    break;
6009  case 'c':
6010    assert(HowLong == 0 && "Bad modifiers used with 'c'!");
6011    if (Signed)
6012      Type = Context.SignedCharTy;
6013    else if (Unsigned)
6014      Type = Context.UnsignedCharTy;
6015    else
6016      Type = Context.CharTy;
6017    break;
6018  case 'b': // boolean
6019    assert(HowLong == 0 && !Signed && !Unsigned && "Bad modifiers for 'b'!");
6020    Type = Context.BoolTy;
6021    break;
6022  case 'z':  // size_t.
6023    assert(HowLong == 0 && !Signed && !Unsigned && "Bad modifiers for 'z'!");
6024    Type = Context.getSizeType();
6025    break;
6026  case 'F':
6027    Type = Context.getCFConstantStringType();
6028    break;
6029  case 'G':
6030    Type = Context.getObjCIdType();
6031    break;
6032  case 'H':
6033    Type = Context.getObjCSelType();
6034    break;
6035  case 'a':
6036    Type = Context.getBuiltinVaListType();
6037    assert(!Type.isNull() && "builtin va list type not initialized!");
6038    break;
6039  case 'A':
6040    // This is a "reference" to a va_list; however, what exactly
6041    // this means depends on how va_list is defined. There are two
6042    // different kinds of va_list: ones passed by value, and ones
6043    // passed by reference.  An example of a by-value va_list is
6044    // x86, where va_list is a char*. An example of by-ref va_list
6045    // is x86-64, where va_list is a __va_list_tag[1]. For x86,
6046    // we want this argument to be a char*&; for x86-64, we want
6047    // it to be a __va_list_tag*.
6048    Type = Context.getBuiltinVaListType();
6049    assert(!Type.isNull() && "builtin va list type not initialized!");
6050    if (Type->isArrayType())
6051      Type = Context.getArrayDecayedType(Type);
6052    else
6053      Type = Context.getLValueReferenceType(Type);
6054    break;
6055  case 'V': {
6056    char *End;
6057    unsigned NumElements = strtoul(Str, &End, 10);
6058    assert(End != Str && "Missing vector size");
6059    Str = End;
6060
6061    QualType ElementType = DecodeTypeFromStr(Str, Context, Error,
6062                                             RequiresICE, false);
6063    assert(!RequiresICE && "Can't require vector ICE");
6064
6065    // TODO: No way to make AltiVec vectors in builtins yet.
6066    Type = Context.getVectorType(ElementType, NumElements,
6067                                 VectorType::GenericVector);
6068    break;
6069  }
6070  case 'X': {
6071    QualType ElementType = DecodeTypeFromStr(Str, Context, Error, RequiresICE,
6072                                             false);
6073    assert(!RequiresICE && "Can't require complex ICE");
6074    Type = Context.getComplexType(ElementType);
6075    break;
6076  }
6077  case 'P':
6078    Type = Context.getFILEType();
6079    if (Type.isNull()) {
6080      Error = ASTContext::GE_Missing_stdio;
6081      return QualType();
6082    }
6083    break;
6084  case 'J':
6085    if (Signed)
6086      Type = Context.getsigjmp_bufType();
6087    else
6088      Type = Context.getjmp_bufType();
6089
6090    if (Type.isNull()) {
6091      Error = ASTContext::GE_Missing_setjmp;
6092      return QualType();
6093    }
6094    break;
6095  }
6096
6097  // If there are modifiers and if we're allowed to parse them, go for it.
6098  Done = !AllowTypeModifiers;
6099  while (!Done) {
6100    switch (char c = *Str++) {
6101    default: Done = true; --Str; break;
6102    case '*':
6103    case '&': {
6104      // Both pointers and references can have their pointee types
6105      // qualified with an address space.
6106      char *End;
6107      unsigned AddrSpace = strtoul(Str, &End, 10);
6108      if (End != Str && AddrSpace != 0) {
6109        Type = Context.getAddrSpaceQualType(Type, AddrSpace);
6110        Str = End;
6111      }
6112      if (c == '*')
6113        Type = Context.getPointerType(Type);
6114      else
6115        Type = Context.getLValueReferenceType(Type);
6116      break;
6117    }
6118    // FIXME: There's no way to have a built-in with an rvalue ref arg.
6119    case 'C':
6120      Type = Type.withConst();
6121      break;
6122    case 'D':
6123      Type = Context.getVolatileType(Type);
6124      break;
6125    }
6126  }
6127
6128  assert((!RequiresICE || Type->isIntegralOrEnumerationType()) &&
6129         "Integer constant 'I' type must be an integer");
6130
6131  return Type;
6132}
6133
6134/// GetBuiltinType - Return the type for the specified builtin.
6135QualType ASTContext::GetBuiltinType(unsigned Id,
6136                                    GetBuiltinTypeError &Error,
6137                                    unsigned *IntegerConstantArgs) const {
6138  const char *TypeStr = BuiltinInfo.GetTypeString(Id);
6139
6140  llvm::SmallVector<QualType, 8> ArgTypes;
6141
6142  bool RequiresICE = false;
6143  Error = GE_None;
6144  QualType ResType = DecodeTypeFromStr(TypeStr, *this, Error,
6145                                       RequiresICE, true);
6146  if (Error != GE_None)
6147    return QualType();
6148
6149  assert(!RequiresICE && "Result of intrinsic cannot be required to be an ICE");
6150
6151  while (TypeStr[0] && TypeStr[0] != '.') {
6152    QualType Ty = DecodeTypeFromStr(TypeStr, *this, Error, RequiresICE, true);
6153    if (Error != GE_None)
6154      return QualType();
6155
6156    // If this argument is required to be an IntegerConstantExpression and the
6157    // caller cares, fill in the bitmask we return.
6158    if (RequiresICE && IntegerConstantArgs)
6159      *IntegerConstantArgs |= 1 << ArgTypes.size();
6160
6161    // Do array -> pointer decay.  The builtin should use the decayed type.
6162    if (Ty->isArrayType())
6163      Ty = getArrayDecayedType(Ty);
6164
6165    ArgTypes.push_back(Ty);
6166  }
6167
6168  assert((TypeStr[0] != '.' || TypeStr[1] == 0) &&
6169         "'.' should only occur at end of builtin type list!");
6170
6171  FunctionType::ExtInfo EI;
6172  if (BuiltinInfo.isNoReturn(Id)) EI = EI.withNoReturn(true);
6173
6174  bool Variadic = (TypeStr[0] == '.');
6175
6176  // We really shouldn't be making a no-proto type here, especially in C++.
6177  if (ArgTypes.empty() && Variadic)
6178    return getFunctionNoProtoType(ResType, EI);
6179
6180  FunctionProtoType::ExtProtoInfo EPI;
6181  EPI.ExtInfo = EI;
6182  EPI.Variadic = Variadic;
6183
6184  return getFunctionType(ResType, ArgTypes.data(), ArgTypes.size(), EPI);
6185}
6186
6187GVALinkage ASTContext::GetGVALinkageForFunction(const FunctionDecl *FD) {
6188  GVALinkage External = GVA_StrongExternal;
6189
6190  Linkage L = FD->getLinkage();
6191  switch (L) {
6192  case NoLinkage:
6193  case InternalLinkage:
6194  case UniqueExternalLinkage:
6195    return GVA_Internal;
6196
6197  case ExternalLinkage:
6198    switch (FD->getTemplateSpecializationKind()) {
6199    case TSK_Undeclared:
6200    case TSK_ExplicitSpecialization:
6201      External = GVA_StrongExternal;
6202      break;
6203
6204    case TSK_ExplicitInstantiationDefinition:
6205      return GVA_ExplicitTemplateInstantiation;
6206
6207    case TSK_ExplicitInstantiationDeclaration:
6208    case TSK_ImplicitInstantiation:
6209      External = GVA_TemplateInstantiation;
6210      break;
6211    }
6212  }
6213
6214  if (!FD->isInlined())
6215    return External;
6216
6217  if (!getLangOptions().CPlusPlus || FD->hasAttr<GNUInlineAttr>()) {
6218    // GNU or C99 inline semantics. Determine whether this symbol should be
6219    // externally visible.
6220    if (FD->isInlineDefinitionExternallyVisible())
6221      return External;
6222
6223    // C99 inline semantics, where the symbol is not externally visible.
6224    return GVA_C99Inline;
6225  }
6226
6227  // C++0x [temp.explicit]p9:
6228  //   [ Note: The intent is that an inline function that is the subject of
6229  //   an explicit instantiation declaration will still be implicitly
6230  //   instantiated when used so that the body can be considered for
6231  //   inlining, but that no out-of-line copy of the inline function would be
6232  //   generated in the translation unit. -- end note ]
6233  if (FD->getTemplateSpecializationKind()
6234                                       == TSK_ExplicitInstantiationDeclaration)
6235    return GVA_C99Inline;
6236
6237  return GVA_CXXInline;
6238}
6239
6240GVALinkage ASTContext::GetGVALinkageForVariable(const VarDecl *VD) {
6241  // If this is a static data member, compute the kind of template
6242  // specialization. Otherwise, this variable is not part of a
6243  // template.
6244  TemplateSpecializationKind TSK = TSK_Undeclared;
6245  if (VD->isStaticDataMember())
6246    TSK = VD->getTemplateSpecializationKind();
6247
6248  Linkage L = VD->getLinkage();
6249  if (L == ExternalLinkage && getLangOptions().CPlusPlus &&
6250      VD->getType()->getLinkage() == UniqueExternalLinkage)
6251    L = UniqueExternalLinkage;
6252
6253  switch (L) {
6254  case NoLinkage:
6255  case InternalLinkage:
6256  case UniqueExternalLinkage:
6257    return GVA_Internal;
6258
6259  case ExternalLinkage:
6260    switch (TSK) {
6261    case TSK_Undeclared:
6262    case TSK_ExplicitSpecialization:
6263      return GVA_StrongExternal;
6264
6265    case TSK_ExplicitInstantiationDeclaration:
6266      llvm_unreachable("Variable should not be instantiated");
6267      // Fall through to treat this like any other instantiation.
6268
6269    case TSK_ExplicitInstantiationDefinition:
6270      return GVA_ExplicitTemplateInstantiation;
6271
6272    case TSK_ImplicitInstantiation:
6273      return GVA_TemplateInstantiation;
6274    }
6275  }
6276
6277  return GVA_StrongExternal;
6278}
6279
6280bool ASTContext::DeclMustBeEmitted(const Decl *D) {
6281  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
6282    if (!VD->isFileVarDecl())
6283      return false;
6284  } else if (!isa<FunctionDecl>(D))
6285    return false;
6286
6287  // Weak references don't produce any output by themselves.
6288  if (D->hasAttr<WeakRefAttr>())
6289    return false;
6290
6291  // Aliases and used decls are required.
6292  if (D->hasAttr<AliasAttr>() || D->hasAttr<UsedAttr>())
6293    return true;
6294
6295  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
6296    // Forward declarations aren't required.
6297    if (!FD->doesThisDeclarationHaveABody())
6298      return false;
6299
6300    // Constructors and destructors are required.
6301    if (FD->hasAttr<ConstructorAttr>() || FD->hasAttr<DestructorAttr>())
6302      return true;
6303
6304    // The key function for a class is required.
6305    if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(FD)) {
6306      const CXXRecordDecl *RD = MD->getParent();
6307      if (MD->isOutOfLine() && RD->isDynamicClass()) {
6308        const CXXMethodDecl *KeyFunc = getKeyFunction(RD);
6309        if (KeyFunc && KeyFunc->getCanonicalDecl() == MD->getCanonicalDecl())
6310          return true;
6311      }
6312    }
6313
6314    GVALinkage Linkage = GetGVALinkageForFunction(FD);
6315
6316    // static, static inline, always_inline, and extern inline functions can
6317    // always be deferred.  Normal inline functions can be deferred in C99/C++.
6318    // Implicit template instantiations can also be deferred in C++.
6319    if (Linkage == GVA_Internal  || Linkage == GVA_C99Inline ||
6320        Linkage == GVA_CXXInline || Linkage == GVA_TemplateInstantiation)
6321      return false;
6322    return true;
6323  }
6324
6325  const VarDecl *VD = cast<VarDecl>(D);
6326  assert(VD->isFileVarDecl() && "Expected file scoped var");
6327
6328  if (VD->isThisDeclarationADefinition() == VarDecl::DeclarationOnly)
6329    return false;
6330
6331  // Structs that have non-trivial constructors or destructors are required.
6332
6333  // FIXME: Handle references.
6334  // FIXME: Be more selective about which constructors we care about.
6335  if (const RecordType *RT = VD->getType()->getAs<RecordType>()) {
6336    if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl())) {
6337      if (RD->hasDefinition() && !(RD->hasTrivialDefaultConstructor() &&
6338                                   RD->hasTrivialCopyConstructor() &&
6339                                   RD->hasTrivialMoveConstructor() &&
6340                                   RD->hasTrivialDestructor()))
6341        return true;
6342    }
6343  }
6344
6345  GVALinkage L = GetGVALinkageForVariable(VD);
6346  if (L == GVA_Internal || L == GVA_TemplateInstantiation) {
6347    if (!(VD->getInit() && VD->getInit()->HasSideEffects(*this)))
6348      return false;
6349  }
6350
6351  return true;
6352}
6353
6354CallingConv ASTContext::getDefaultMethodCallConv() {
6355  // Pass through to the C++ ABI object
6356  return ABI->getDefaultMethodCallConv();
6357}
6358
6359bool ASTContext::isNearlyEmpty(const CXXRecordDecl *RD) const {
6360  // Pass through to the C++ ABI object
6361  return ABI->isNearlyEmpty(RD);
6362}
6363
6364MangleContext *ASTContext::createMangleContext() {
6365  switch (Target.getCXXABI()) {
6366  case CXXABI_ARM:
6367  case CXXABI_Itanium:
6368    return createItaniumMangleContext(*this, getDiagnostics());
6369  case CXXABI_Microsoft:
6370    return createMicrosoftMangleContext(*this, getDiagnostics());
6371  }
6372  assert(0 && "Unsupported ABI");
6373  return 0;
6374}
6375
6376CXXABI::~CXXABI() {}
6377
6378size_t ASTContext::getSideTableAllocatedMemory() const {
6379  size_t bytes = 0;
6380  bytes += ASTRecordLayouts.getMemorySize();
6381  bytes += ObjCLayouts.getMemorySize();
6382  bytes += KeyFunctions.getMemorySize();
6383  bytes += ObjCImpls.getMemorySize();
6384  bytes += BlockVarCopyInits.getMemorySize();
6385  bytes += DeclAttrs.getMemorySize();
6386  bytes += InstantiatedFromStaticDataMember.getMemorySize();
6387  bytes += InstantiatedFromUsingDecl.getMemorySize();
6388  bytes += InstantiatedFromUsingShadowDecl.getMemorySize();
6389  bytes += InstantiatedFromUnnamedFieldDecl.getMemorySize();
6390  return bytes;
6391}
6392
6393