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