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