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