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