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