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