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