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