contrib/llvm/tools/clang/lib/AST/Type.cpp

   1 //===--- Type.cpp - Type representation and manipulation ------------------===//
   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 type-related functionality.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/ASTContext.h"
  15 #include "clang/AST/Attr.h"
  16 #include "clang/AST/CharUnits.h"
  17 #include "clang/AST/DeclCXX.h"
  18 #include "clang/AST/DeclObjC.h"
  19 #include "clang/AST/DeclTemplate.h"
  20 #include "clang/AST/Expr.h"
  21 #include "clang/AST/PrettyPrinter.h"
  22 #include "clang/AST/Type.h"
  23 #include "clang/AST/TypeVisitor.h"
  24 #include "clang/Basic/Specifiers.h"
  25 #include "clang/Basic/TargetInfo.h"
  26 #include "llvm/ADT/APSInt.h"
  27 #include "llvm/ADT/StringExtras.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include <algorithm>
  30 using namespace clang;
  31
  32 bool Qualifiers::isStrictSupersetOf(Qualifiers Other) const {
  33   return (*this != Other) &&
  34     // CVR qualifiers superset
  35     (((Mask & CVRMask) | (Other.Mask & CVRMask)) == (Mask & CVRMask)) &&
  36     // ObjC GC qualifiers superset
  37     ((getObjCGCAttr() == Other.getObjCGCAttr()) ||
  38      (hasObjCGCAttr() && !Other.hasObjCGCAttr())) &&
  39     // Address space superset.
  40     ((getAddressSpace() == Other.getAddressSpace()) ||
  41      (hasAddressSpace()&& !Other.hasAddressSpace())) &&
  42     // Lifetime qualifier superset.
  43     ((getObjCLifetime() == Other.getObjCLifetime()) ||
  44      (hasObjCLifetime() && !Other.hasObjCLifetime()));
  45 }
  46
  47 const IdentifierInfo* QualType::getBaseTypeIdentifier() const {
  48   const Type* ty = getTypePtr();
  49   NamedDecl *ND = nullptr;
  50   if (ty->isPointerType() || ty->isReferenceType())
  51     return ty->getPointeeType().getBaseTypeIdentifier();
  52   else if (ty->isRecordType())
  53     ND = ty->getAs<RecordType>()->getDecl();
  54   else if (ty->isEnumeralType())
  55     ND = ty->getAs<EnumType>()->getDecl();
  56   else if (ty->getTypeClass() == Type::Typedef)
  57     ND = ty->getAs<TypedefType>()->getDecl();
  58   else if (ty->isArrayType())
  59     return ty->castAsArrayTypeUnsafe()->
  60         getElementType().getBaseTypeIdentifier();
  61
  62   if (ND)
  63     return ND->getIdentifier();
  64   return nullptr;
  65 }
  66
  67 bool QualType::isConstant(QualType T, const ASTContext &Ctx) {
  68   if (T.isConstQualified())
  69     return true;
  70
  71   if (const ArrayType *AT = Ctx.getAsArrayType(T))
  72     return AT->getElementType().isConstant(Ctx);
  73
  74   return T.getAddressSpace() == LangAS::opencl_constant;
  75 }
  76
  77 unsigned ConstantArrayType::getNumAddressingBits(const ASTContext &Context,
  78                                                  QualType ElementType,
  79                                                const llvm::APInt &NumElements) {
  80   uint64_t ElementSize = Context.getTypeSizeInChars(ElementType).getQuantity();
  81
  82   // Fast path the common cases so we can avoid the conservative computation
  83   // below, which in common cases allocates "large" APSInt values, which are
  84   // slow.
  85
  86   // If the element size is a power of 2, we can directly compute the additional
  87   // number of addressing bits beyond those required for the element count.
  88   if (llvm::isPowerOf2_64(ElementSize)) {
  89     return NumElements.getActiveBits() + llvm::Log2_64(ElementSize);
  90   }
  91
  92   // If both the element count and element size fit in 32-bits, we can do the
  93   // computation directly in 64-bits.
  94   if ((ElementSize >> 32) == 0 && NumElements.getBitWidth() <= 64 &&
  95       (NumElements.getZExtValue() >> 32) == 0) {
  96     uint64_t TotalSize = NumElements.getZExtValue() * ElementSize;
  97     return 64 - llvm::countLeadingZeros(TotalSize);
  98   }
  99
 100   // Otherwise, use APSInt to handle arbitrary sized values.
 101   llvm::APSInt SizeExtended(NumElements, true);
 102   unsigned SizeTypeBits = Context.getTypeSize(Context.getSizeType());
 103   SizeExtended = SizeExtended.extend(std::max(SizeTypeBits,
 104                                               SizeExtended.getBitWidth()) * 2);
 105
 106   llvm::APSInt TotalSize(llvm::APInt(SizeExtended.getBitWidth(), ElementSize));
 107   TotalSize *= SizeExtended;
 108
 109   return TotalSize.getActiveBits();
 110 }
 111
 112 unsigned ConstantArrayType::getMaxSizeBits(const ASTContext &Context) {
 113   unsigned Bits = Context.getTypeSize(Context.getSizeType());
 114
 115   // Limit the number of bits in size_t so that maximal bit size fits 64 bit
 116   // integer (see PR8256).  We can do this as currently there is no hardware
 117   // that supports full 64-bit virtual space.
 118   if (Bits > 61)
 119     Bits = 61;
 120
 121   return Bits;
 122 }
 123
 124 DependentSizedArrayType::DependentSizedArrayType(const ASTContext &Context,
 125                                                  QualType et, QualType can,
 126                                                  Expr *e, ArraySizeModifier sm,
 127                                                  unsigned tq,
 128                                                  SourceRange brackets)
 129     : ArrayType(DependentSizedArray, et, can, sm, tq,
 130                 (et->containsUnexpandedParameterPack() ||
 131                  (e && e->containsUnexpandedParameterPack()))),
 132       Context(Context), SizeExpr((Stmt*) e), Brackets(brackets)
 133 {
 134 }
 135
 136 void DependentSizedArrayType::Profile(llvm::FoldingSetNodeID &ID,
 137                                       const ASTContext &Context,
 138                                       QualType ET,
 139                                       ArraySizeModifier SizeMod,
 140                                       unsigned TypeQuals,
 141                                       Expr *E) {
 142   ID.AddPointer(ET.getAsOpaquePtr());
 143   ID.AddInteger(SizeMod);
 144   ID.AddInteger(TypeQuals);
 145   E->Profile(ID, Context, true);
 146 }
 147
 148 DependentSizedExtVectorType::DependentSizedExtVectorType(const
 149                                                          ASTContext &Context,
 150                                                          QualType ElementType,
 151                                                          QualType can,
 152                                                          Expr *SizeExpr,
 153                                                          SourceLocation loc)
 154     : Type(DependentSizedExtVector, can, /*Dependent=*/true,
 155            /*InstantiationDependent=*/true,
 156            ElementType->isVariablyModifiedType(),
 157            (ElementType->containsUnexpandedParameterPack() ||
 158             (SizeExpr && SizeExpr->containsUnexpandedParameterPack()))),
 159       Context(Context), SizeExpr(SizeExpr), ElementType(ElementType),
 160       loc(loc)
 161 {
 162 }
 163
 164 void
 165 DependentSizedExtVectorType::Profile(llvm::FoldingSetNodeID &ID,
 166                                      const ASTContext &Context,
 167                                      QualType ElementType, Expr *SizeExpr) {
 168   ID.AddPointer(ElementType.getAsOpaquePtr());
 169   SizeExpr->Profile(ID, Context, true);
 170 }
 171
 172 VectorType::VectorType(QualType vecType, unsigned nElements, QualType canonType,
 173                        VectorKind vecKind)
 174     : VectorType(Vector, vecType, nElements, canonType, vecKind) {}
 175
 176 VectorType::VectorType(TypeClass tc, QualType vecType, unsigned nElements,
 177                        QualType canonType, VectorKind vecKind)
 178   : Type(tc, canonType, vecType->isDependentType(),
 179          vecType->isInstantiationDependentType(),
 180          vecType->isVariablyModifiedType(),
 181          vecType->containsUnexpandedParameterPack()),
 182     ElementType(vecType)
 183 {
 184   VectorTypeBits.VecKind = vecKind;
 185   VectorTypeBits.NumElements = nElements;
 186 }
 187
 188 /// getArrayElementTypeNoTypeQual - If this is an array type, return the
 189 /// element type of the array, potentially with type qualifiers missing.
 190 /// This method should never be used when type qualifiers are meaningful.
 191 const Type *Type::getArrayElementTypeNoTypeQual() const {
 192   // If this is directly an array type, return it.
 193   if (const ArrayType *ATy = dyn_cast<ArrayType>(this))
 194     return ATy->getElementType().getTypePtr();
 195
 196   // If the canonical form of this type isn't the right kind, reject it.
 197   if (!isa<ArrayType>(CanonicalType))
 198     return nullptr;
 199
 200   // If this is a typedef for an array type, strip the typedef off without
 201   // losing all typedef information.
 202   return cast<ArrayType>(getUnqualifiedDesugaredType())
 203     ->getElementType().getTypePtr();
 204 }
 205
 206 /// getDesugaredType - Return the specified type with any "sugar" removed from
 207 /// the type.  This takes off typedefs, typeof's etc.  If the outer level of
 208 /// the type is already concrete, it returns it unmodified.  This is similar
 209 /// to getting the canonical type, but it doesn't remove *all* typedefs.  For
 210 /// example, it returns "T*" as "T*", (not as "int*"), because the pointer is
 211 /// concrete.
 212 QualType QualType::getDesugaredType(QualType T, const ASTContext &Context) {
 213   SplitQualType split = getSplitDesugaredType(T);
 214   return Context.getQualifiedType(split.Ty, split.Quals);
 215 }
 216
 217 QualType QualType::getSingleStepDesugaredTypeImpl(QualType type,
 218                                                   const ASTContext &Context) {
 219   SplitQualType split = type.split();
 220   QualType desugar = split.Ty->getLocallyUnqualifiedSingleStepDesugaredType();
 221   return Context.getQualifiedType(desugar, split.Quals);
 222 }
 223
 224 QualType Type::getLocallyUnqualifiedSingleStepDesugaredType() const {
 225   switch (getTypeClass()) {
 226 #define ABSTRACT_TYPE(Class, Parent)
 227 #define TYPE(Class, Parent) \
 228   case Type::Class: { \
 229     const Class##Type *ty = cast<Class##Type>(this); \
 230     if (!ty->isSugared()) return QualType(ty, 0); \
 231     return ty->desugar(); \
 232   }
 233 #include "clang/AST/TypeNodes.def"
 234   }
 235   llvm_unreachable("bad type kind!");
 236 }
 237
 238 SplitQualType QualType::getSplitDesugaredType(QualType T) {
 239   QualifierCollector Qs;
 240
 241   QualType Cur = T;
 242   while (true) {
 243     const Type *CurTy = Qs.strip(Cur);
 244     switch (CurTy->getTypeClass()) {
 245 #define ABSTRACT_TYPE(Class, Parent)
 246 #define TYPE(Class, Parent) \
 247     case Type::Class: { \
 248       const Class##Type *Ty = cast<Class##Type>(CurTy); \
 249       if (!Ty->isSugared()) \
 250         return SplitQualType(Ty, Qs); \
 251       Cur = Ty->desugar(); \
 252       break; \
 253     }
 254 #include "clang/AST/TypeNodes.def"
 255     }
 256   }
 257 }
 258
 259 SplitQualType QualType::getSplitUnqualifiedTypeImpl(QualType type) {
 260   SplitQualType split = type.split();
 261
 262   // All the qualifiers we've seen so far.
 263   Qualifiers quals = split.Quals;
 264
 265   // The last type node we saw with any nodes inside it.
 266   const Type *lastTypeWithQuals = split.Ty;
 267
 268   while (true) {
 269     QualType next;
 270
 271     // Do a single-step desugar, aborting the loop if the type isn't
 272     // sugared.
 273     switch (split.Ty->getTypeClass()) {
 274 #define ABSTRACT_TYPE(Class, Parent)
 275 #define TYPE(Class, Parent) \
 276     case Type::Class: { \
 277       const Class##Type *ty = cast<Class##Type>(split.Ty); \
 278       if (!ty->isSugared()) goto done; \
 279       next = ty->desugar(); \
 280       break; \
 281     }
 282 #include "clang/AST/TypeNodes.def"
 283     }
 284
 285     // Otherwise, split the underlying type.  If that yields qualifiers,
 286     // update the information.
 287     split = next.split();
 288     if (!split.Quals.empty()) {
 289       lastTypeWithQuals = split.Ty;
 290       quals.addConsistentQualifiers(split.Quals);
 291     }
 292   }
 293
 294  done:
 295   return SplitQualType(lastTypeWithQuals, quals);
 296 }
 297
 298 QualType QualType::IgnoreParens(QualType T) {
 299   // FIXME: this seems inherently un-qualifiers-safe.
 300   while (const ParenType *PT = T->getAs<ParenType>())
 301     T = PT->getInnerType();
 302   return T;
 303 }
 304
 305 /// \brief This will check for a T (which should be a Type which can act as
 306 /// sugar, such as a TypedefType) by removing any existing sugar until it
 307 /// reaches a T or a non-sugared type.
 308 template<typename T> static const T *getAsSugar(const Type *Cur) {
 309   while (true) {
 310     if (const T *Sugar = dyn_cast<T>(Cur))
 311       return Sugar;
 312     switch (Cur->getTypeClass()) {
 313 #define ABSTRACT_TYPE(Class, Parent)
 314 #define TYPE(Class, Parent) \
 315     case Type::Class: { \
 316       const Class##Type *Ty = cast<Class##Type>(Cur); \
 317       if (!Ty->isSugared()) return 0; \
 318       Cur = Ty->desugar().getTypePtr(); \
 319       break; \
 320     }
 321 #include "clang/AST/TypeNodes.def"
 322     }
 323   }
 324 }
 325
 326 template <> const TypedefType *Type::getAs() const {
 327   return getAsSugar<TypedefType>(this);
 328 }
 329
 330 template <> const TemplateSpecializationType *Type::getAs() const {
 331   return getAsSugar<TemplateSpecializationType>(this);
 332 }
 333
 334 template <> const AttributedType *Type::getAs() const {
 335   return getAsSugar<AttributedType>(this);
 336 }
 337
 338 /// getUnqualifiedDesugaredType - Pull any qualifiers and syntactic
 339 /// sugar off the given type.  This should produce an object of the
 340 /// same dynamic type as the canonical type.
 341 const Type *Type::getUnqualifiedDesugaredType() const {
 342   const Type *Cur = this;
 343
 344   while (true) {
 345     switch (Cur->getTypeClass()) {
 346 #define ABSTRACT_TYPE(Class, Parent)
 347 #define TYPE(Class, Parent) \
 348     case Class: { \
 349       const Class##Type *Ty = cast<Class##Type>(Cur); \
 350       if (!Ty->isSugared()) return Cur; \
 351       Cur = Ty->desugar().getTypePtr(); \
 352       break; \
 353     }
 354 #include "clang/AST/TypeNodes.def"
 355     }
 356   }
 357 }
 358 bool Type::isClassType() const {
 359   if (const RecordType *RT = getAs<RecordType>())
 360     return RT->getDecl()->isClass();
 361   return false;
 362 }
 363 bool Type::isStructureType() const {
 364   if (const RecordType *RT = getAs<RecordType>())
 365     return RT->getDecl()->isStruct();
 366   return false;
 367 }
 368 bool Type::isObjCBoxableRecordType() const {
 369   if (const RecordType *RT = getAs<RecordType>())
 370     return RT->getDecl()->hasAttr<ObjCBoxableAttr>();
 371   return false;
 372 }
 373 bool Type::isInterfaceType() const {
 374   if (const RecordType *RT = getAs<RecordType>())
 375     return RT->getDecl()->isInterface();
 376   return false;
 377 }
 378 bool Type::isStructureOrClassType() const {
 379   if (const RecordType *RT = getAs<RecordType>()) {
 380     RecordDecl *RD = RT->getDecl();
 381     return RD->isStruct() || RD->isClass() || RD->isInterface();
 382   }
 383   return false;
 384 }
 385 bool Type::isVoidPointerType() const {
 386   if (const PointerType *PT = getAs<PointerType>())
 387     return PT->getPointeeType()->isVoidType();
 388   return false;
 389 }
 390
 391 bool Type::isUnionType() const {
 392   if (const RecordType *RT = getAs<RecordType>())
 393     return RT->getDecl()->isUnion();
 394   return false;
 395 }
 396
 397 bool Type::isComplexType() const {
 398   if (const ComplexType *CT = dyn_cast<ComplexType>(CanonicalType))
 399     return CT->getElementType()->isFloatingType();
 400   return false;
 401 }
 402
 403 bool Type::isComplexIntegerType() const {
 404   // Check for GCC complex integer extension.
 405   return getAsComplexIntegerType();
 406 }
 407
 408 const ComplexType *Type::getAsComplexIntegerType() const {
 409   if (const ComplexType *Complex = getAs<ComplexType>())
 410     if (Complex->getElementType()->isIntegerType())
 411       return Complex;
 412   return nullptr;
 413 }
 414
 415 QualType Type::getPointeeType() const {
 416   if (const PointerType *PT = getAs<PointerType>())
 417     return PT->getPointeeType();
 418   if (const ObjCObjectPointerType *OPT = getAs<ObjCObjectPointerType>())
 419     return OPT->getPointeeType();
 420   if (const BlockPointerType *BPT = getAs<BlockPointerType>())
 421     return BPT->getPointeeType();
 422   if (const ReferenceType *RT = getAs<ReferenceType>())
 423     return RT->getPointeeType();
 424   if (const MemberPointerType *MPT = getAs<MemberPointerType>())
 425     return MPT->getPointeeType();
 426   if (const DecayedType *DT = getAs<DecayedType>())
 427     return DT->getPointeeType();
 428   return QualType();
 429 }
 430
 431 const RecordType *Type::getAsStructureType() const {
 432   // If this is directly a structure type, return it.
 433   if (const RecordType *RT = dyn_cast<RecordType>(this)) {
 434     if (RT->getDecl()->isStruct())
 435       return RT;
 436   }
 437
 438   // If the canonical form of this type isn't the right kind, reject it.
 439   if (const RecordType *RT = dyn_cast<RecordType>(CanonicalType)) {
 440     if (!RT->getDecl()->isStruct())
 441       return nullptr;
 442
 443     // If this is a typedef for a structure type, strip the typedef off without
 444     // losing all typedef information.
 445     return cast<RecordType>(getUnqualifiedDesugaredType());
 446   }
 447   return nullptr;
 448 }
 449
 450 const RecordType *Type::getAsUnionType() const {
 451   // If this is directly a union type, return it.
 452   if (const RecordType *RT = dyn_cast<RecordType>(this)) {
 453     if (RT->getDecl()->isUnion())
 454       return RT;
 455   }
 456
 457   // If the canonical form of this type isn't the right kind, reject it.
 458   if (const RecordType *RT = dyn_cast<RecordType>(CanonicalType)) {
 459     if (!RT->getDecl()->isUnion())
 460       return nullptr;
 461
 462     // If this is a typedef for a union type, strip the typedef off without
 463     // losing all typedef information.
 464     return cast<RecordType>(getUnqualifiedDesugaredType());
 465   }
 466
 467   return nullptr;
 468 }
 469
 470 bool Type::isObjCIdOrObjectKindOfType(const ASTContext &ctx,
 471                                       const ObjCObjectType *&bound) const {
 472   bound = nullptr;
 473
 474   const ObjCObjectPointerType *OPT = getAs<ObjCObjectPointerType>();
 475   if (!OPT)
 476     return false;
 477
 478   // Easy case: id.
 479   if (OPT->isObjCIdType())
 480     return true;
 481
 482   // If it's not a __kindof type, reject it now.
 483   if (!OPT->isKindOfType())
 484     return false;
 485
 486   // If it's Class or qualified Class, it's not an object type.
 487   if (OPT->isObjCClassType() || OPT->isObjCQualifiedClassType())
 488     return false;
 489
 490   // Figure out the type bound for the __kindof type.
 491   bound = OPT->getObjectType()->stripObjCKindOfTypeAndQuals(ctx)
 492             ->getAs<ObjCObjectType>();
 493   return true;
 494 }
 495
 496 bool Type::isObjCClassOrClassKindOfType() const {
 497   const ObjCObjectPointerType *OPT = getAs<ObjCObjectPointerType>();
 498   if (!OPT)
 499     return false;
 500
 501   // Easy case: Class.
 502   if (OPT->isObjCClassType())
 503     return true;
 504
 505   // If it's not a __kindof type, reject it now.
 506   if (!OPT->isKindOfType())
 507     return false;
 508
 509   // If it's Class or qualified Class, it's a class __kindof type.
 510   return OPT->isObjCClassType() || OPT->isObjCQualifiedClassType();
 511 }
 512
 513 /// Was this type written with the special inert-in-MRC __unsafe_unretained
 514 /// qualifier?
 515 ///
 516 /// This approximates the answer to the following question: if this
 517 /// translation unit were compiled in ARC, would this type be qualified
 518 /// with __unsafe_unretained?
 519 bool Type::isObjCInertUnsafeUnretainedType() const {
 520   const Type *cur = this;
 521   while (true) {
 522     if (auto attributed = dyn_cast<AttributedType>(cur)) {
 523       if (attributed->getAttrKind() ==
 524             AttributedType::attr_objc_inert_unsafe_unretained)
 525         return true;
 526     }
 527
 528     // Single-step desugar until we run out of sugar.
 529     QualType next = cur->getLocallyUnqualifiedSingleStepDesugaredType();
 530     if (next.getTypePtr() == cur) return false;
 531     cur = next.getTypePtr();
 532   }
 533 }
 534
 535 ObjCObjectType::ObjCObjectType(QualType Canonical, QualType Base,
 536                                ArrayRef<QualType> typeArgs,
 537                                ArrayRef<ObjCProtocolDecl *> protocols,
 538                                bool isKindOf)
 539   : Type(ObjCObject, Canonical, Base->isDependentType(),
 540          Base->isInstantiationDependentType(),
 541          Base->isVariablyModifiedType(),
 542          Base->containsUnexpandedParameterPack()),
 543     BaseType(Base)
 544 {
 545   ObjCObjectTypeBits.IsKindOf = isKindOf;
 546
 547   ObjCObjectTypeBits.NumTypeArgs = typeArgs.size();
 548   assert(getTypeArgsAsWritten().size() == typeArgs.size() &&
 549          "bitfield overflow in type argument count");
 550   ObjCObjectTypeBits.NumProtocols = protocols.size();
 551   assert(getNumProtocols() == protocols.size() &&
 552          "bitfield overflow in protocol count");
 553   if (!typeArgs.empty())
 554     memcpy(getTypeArgStorage(), typeArgs.data(),
 555            typeArgs.size() * sizeof(QualType));
 556   if (!protocols.empty())
 557     memcpy(getProtocolStorage(), protocols.data(),
 558            protocols.size() * sizeof(ObjCProtocolDecl*));
 559
 560   for (auto typeArg : typeArgs) {
 561     if (typeArg->isDependentType())
 562       setDependent();
 563     else if (typeArg->isInstantiationDependentType())
 564       setInstantiationDependent();
 565
 566     if (typeArg->containsUnexpandedParameterPack())
 567       setContainsUnexpandedParameterPack();
 568   }
 569 }
 570
 571 bool ObjCObjectType::isSpecialized() const {
 572   // If we have type arguments written here, the type is specialized.
 573   if (ObjCObjectTypeBits.NumTypeArgs > 0)
 574     return true;
 575
 576   // Otherwise, check whether the base type is specialized.
 577   if (auto objcObject = getBaseType()->getAs<ObjCObjectType>()) {
 578     // Terminate when we reach an interface type.
 579     if (isa<ObjCInterfaceType>(objcObject))
 580       return false;
 581
 582     return objcObject->isSpecialized();
 583   }
 584
 585   // Not specialized.
 586   return false;
 587 }
 588
 589 ArrayRef<QualType> ObjCObjectType::getTypeArgs() const {
 590   // We have type arguments written on this type.
 591   if (isSpecializedAsWritten())
 592     return getTypeArgsAsWritten();
 593
 594   // Look at the base type, which might have type arguments.
 595   if (auto objcObject = getBaseType()->getAs<ObjCObjectType>()) {
 596     // Terminate when we reach an interface type.
 597     if (isa<ObjCInterfaceType>(objcObject))
 598       return { };
 599
 600     return objcObject->getTypeArgs();
 601   }
 602
 603   // No type arguments.
 604   return { };
 605 }
 606
 607 bool ObjCObjectType::isKindOfType() const {
 608   if (isKindOfTypeAsWritten())
 609     return true;
 610
 611   // Look at the base type, which might have type arguments.
 612   if (auto objcObject = getBaseType()->getAs<ObjCObjectType>()) {
 613     // Terminate when we reach an interface type.
 614     if (isa<ObjCInterfaceType>(objcObject))
 615       return false;
 616
 617     return objcObject->isKindOfType();
 618   }
 619
 620   // Not a "__kindof" type.
 621   return false;
 622 }
 623
 624 QualType ObjCObjectType::stripObjCKindOfTypeAndQuals(
 625            const ASTContext &ctx) const {
 626   if (!isKindOfType() && qual_empty())
 627     return QualType(this, 0);
 628
 629   // Recursively strip __kindof.
 630   SplitQualType splitBaseType = getBaseType().split();
 631   QualType baseType(splitBaseType.Ty, 0);
 632   if (const ObjCObjectType *baseObj
 633         = splitBaseType.Ty->getAs<ObjCObjectType>()) {
 634     baseType = baseObj->stripObjCKindOfTypeAndQuals(ctx);
 635   }
 636
 637   return ctx.getObjCObjectType(ctx.getQualifiedType(baseType,
 638                                                     splitBaseType.Quals),
 639                                getTypeArgsAsWritten(),
 640                                /*protocols=*/{ },
 641                                /*isKindOf=*/false);
 642 }
 643
 644 const ObjCObjectPointerType *ObjCObjectPointerType::stripObjCKindOfTypeAndQuals(
 645                                const ASTContext &ctx) const {
 646   if (!isKindOfType() && qual_empty())
 647     return this;
 648
 649   QualType obj = getObjectType()->stripObjCKindOfTypeAndQuals(ctx);
 650   return ctx.getObjCObjectPointerType(obj)->castAs<ObjCObjectPointerType>();
 651 }
 652
 653 namespace {
 654
 655 template<typename F>
 656 QualType simpleTransform(ASTContext &ctx, QualType type, F &&f);
 657
 658 /// Visitor used by simpleTransform() to perform the transformation.
 659 template<typename F>
 660 struct SimpleTransformVisitor
 661          : public TypeVisitor<SimpleTransformVisitor<F>, QualType> {
 662   ASTContext &Ctx;
 663   F &&TheFunc;
 664
 665   QualType recurse(QualType type) {
 666     return simpleTransform(Ctx, type, std::move(TheFunc));
 667   }
 668
 669 public:
 670   SimpleTransformVisitor(ASTContext &ctx, F &&f) : Ctx(ctx), TheFunc(std::move(f)) { }
 671
 672   // None of the clients of this transformation can occur where
 673   // there are dependent types, so skip dependent types.
 674 #define TYPE(Class, Base)
 675 #define DEPENDENT_TYPE(Class, Base) \
 676   QualType Visit##Class##Type(const Class##Type *T) { return QualType(T, 0); }
 677 #include "clang/AST/TypeNodes.def"
 678
 679 #define TRIVIAL_TYPE_CLASS(Class) \
 680   QualType Visit##Class##Type(const Class##Type *T) { return QualType(T, 0); }
 681
 682   TRIVIAL_TYPE_CLASS(Builtin)
 683
 684   QualType VisitComplexType(const ComplexType *T) {
 685     QualType elementType = recurse(T->getElementType());
 686     if (elementType.isNull())
 687       return QualType();
 688
 689     if (elementType.getAsOpaquePtr() == T->getElementType().getAsOpaquePtr())
 690       return QualType(T, 0);
 691
 692     return Ctx.getComplexType(elementType);
 693   }
 694
 695   QualType VisitPointerType(const PointerType *T) {
 696     QualType pointeeType = recurse(T->getPointeeType());
 697     if (pointeeType.isNull())
 698       return QualType();
 699
 700     if (pointeeType.getAsOpaquePtr() == T->getPointeeType().getAsOpaquePtr())
 701       return QualType(T, 0);
 702
 703     return Ctx.getPointerType(pointeeType);
 704   }
 705
 706   QualType VisitBlockPointerType(const BlockPointerType *T) {
 707     QualType pointeeType = recurse(T->getPointeeType());
 708     if (pointeeType.isNull())
 709       return QualType();
 710
 711     if (pointeeType.getAsOpaquePtr() == T->getPointeeType().getAsOpaquePtr())
 712       return QualType(T, 0);
 713
 714     return Ctx.getBlockPointerType(pointeeType);
 715   }
 716
 717   QualType VisitLValueReferenceType(const LValueReferenceType *T) {
 718     QualType pointeeType = recurse(T->getPointeeTypeAsWritten());
 719     if (pointeeType.isNull())
 720       return QualType();
 721
 722     if (pointeeType.getAsOpaquePtr()
 723           == T->getPointeeTypeAsWritten().getAsOpaquePtr())
 724       return QualType(T, 0);
 725
 726     return Ctx.getLValueReferenceType(pointeeType, T->isSpelledAsLValue());
 727   }
 728
 729   QualType VisitRValueReferenceType(const RValueReferenceType *T) {
 730     QualType pointeeType = recurse(T->getPointeeTypeAsWritten());
 731     if (pointeeType.isNull())
 732       return QualType();
 733
 734     if (pointeeType.getAsOpaquePtr()
 735           == T->getPointeeTypeAsWritten().getAsOpaquePtr())
 736       return QualType(T, 0);
 737
 738     return Ctx.getRValueReferenceType(pointeeType);
 739   }
 740
 741   QualType VisitMemberPointerType(const MemberPointerType *T) {
 742     QualType pointeeType = recurse(T->getPointeeType());
 743     if (pointeeType.isNull())
 744       return QualType();
 745
 746     if (pointeeType.getAsOpaquePtr() == T->getPointeeType().getAsOpaquePtr())
 747       return QualType(T, 0);
 748
 749     return Ctx.getMemberPointerType(pointeeType, T->getClass());
 750   }
 751
 752   QualType VisitConstantArrayType(const ConstantArrayType *T) {
 753     QualType elementType = recurse(T->getElementType());
 754     if (elementType.isNull())
 755       return QualType();
 756
 757     if (elementType.getAsOpaquePtr() == T->getElementType().getAsOpaquePtr())
 758       return QualType(T, 0);
 759
 760     return Ctx.getConstantArrayType(elementType, T->getSize(),
 761                                     T->getSizeModifier(),
 762                                     T->getIndexTypeCVRQualifiers());
 763   }
 764
 765   QualType VisitVariableArrayType(const VariableArrayType *T) {
 766     QualType elementType = recurse(T->getElementType());
 767     if (elementType.isNull())
 768       return QualType();
 769
 770     if (elementType.getAsOpaquePtr() == T->getElementType().getAsOpaquePtr())
 771       return QualType(T, 0);
 772
 773     return Ctx.getVariableArrayType(elementType, T->getSizeExpr(),
 774                                     T->getSizeModifier(),
 775                                     T->getIndexTypeCVRQualifiers(),
 776                                     T->getBracketsRange());
 777   }
 778
 779   QualType VisitIncompleteArrayType(const IncompleteArrayType *T) {
 780     QualType elementType = recurse(T->getElementType());
 781     if (elementType.isNull())
 782       return QualType();
 783
 784     if (elementType.getAsOpaquePtr() == T->getElementType().getAsOpaquePtr())
 785       return QualType(T, 0);
 786
 787     return Ctx.getIncompleteArrayType(elementType, T->getSizeModifier(),
 788                                       T->getIndexTypeCVRQualifiers());
 789   }
 790
 791   QualType VisitVectorType(const VectorType *T) {
 792     QualType elementType = recurse(T->getElementType());
 793     if (elementType.isNull())
 794       return QualType();
 795
 796     if (elementType.getAsOpaquePtr() == T->getElementType().getAsOpaquePtr())
 797       return QualType(T, 0);
 798
 799     return Ctx.getVectorType(elementType, T->getNumElements(),
 800                              T->getVectorKind());
 801   }
 802
 803   QualType VisitExtVectorType(const ExtVectorType *T) {
 804     QualType elementType = recurse(T->getElementType());
 805     if (elementType.isNull())
 806       return QualType();
 807
 808     if (elementType.getAsOpaquePtr() == T->getElementType().getAsOpaquePtr())
 809       return QualType(T, 0);
 810
 811     return Ctx.getExtVectorType(elementType, T->getNumElements());
 812   }
 813
 814   QualType VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
 815     QualType returnType = recurse(T->getReturnType());
 816     if (returnType.isNull())
 817       return QualType();
 818
 819     if (returnType.getAsOpaquePtr() == T->getReturnType().getAsOpaquePtr())
 820       return QualType(T, 0);
 821
 822     return Ctx.getFunctionNoProtoType(returnType, T->getExtInfo());
 823   }
 824
 825   QualType VisitFunctionProtoType(const FunctionProtoType *T) {
 826     QualType returnType = recurse(T->getReturnType());
 827     if (returnType.isNull())
 828       return QualType();
 829
 830     // Transform parameter types.
 831     SmallVector<QualType, 4> paramTypes;
 832     bool paramChanged = false;
 833     for (auto paramType : T->getParamTypes()) {
 834       QualType newParamType = recurse(paramType);
 835       if (newParamType.isNull())
 836         return QualType();
 837
 838       if (newParamType.getAsOpaquePtr() != paramType.getAsOpaquePtr())
 839         paramChanged = true;
 840
 841       paramTypes.push_back(newParamType);
 842     }
 843
 844     // Transform extended info.
 845     FunctionProtoType::ExtProtoInfo info = T->getExtProtoInfo();
 846     bool exceptionChanged = false;
 847     if (info.ExceptionSpec.Type == EST_Dynamic) {
 848       SmallVector<QualType, 4> exceptionTypes;
 849       for (auto exceptionType : info.ExceptionSpec.Exceptions) {
 850         QualType newExceptionType = recurse(exceptionType);
 851         if (newExceptionType.isNull())
 852           return QualType();
 853
 854         if (newExceptionType.getAsOpaquePtr()
 855               != exceptionType.getAsOpaquePtr())
 856           exceptionChanged = true;
 857
 858         exceptionTypes.push_back(newExceptionType);
 859       }
 860
 861       if (exceptionChanged) {
 862         info.ExceptionSpec.Exceptions =
 863             llvm::makeArrayRef(exceptionTypes).copy(Ctx);
 864       }
 865     }
 866
 867     if (returnType.getAsOpaquePtr() == T->getReturnType().getAsOpaquePtr() &&
 868         !paramChanged && !exceptionChanged)
 869       return QualType(T, 0);
 870
 871     return Ctx.getFunctionType(returnType, paramTypes, info);
 872   }
 873
 874   QualType VisitParenType(const ParenType *T) {
 875     QualType innerType = recurse(T->getInnerType());
 876     if (innerType.isNull())
 877       return QualType();
 878
 879     if (innerType.getAsOpaquePtr() == T->getInnerType().getAsOpaquePtr())
 880       return QualType(T, 0);
 881
 882     return Ctx.getParenType(innerType);
 883   }
 884
 885   TRIVIAL_TYPE_CLASS(Typedef)
 886
 887   QualType VisitAdjustedType(const AdjustedType *T) {
 888     QualType originalType = recurse(T->getOriginalType());
 889     if (originalType.isNull())
 890       return QualType();
 891
 892     QualType adjustedType = recurse(T->getAdjustedType());
 893     if (adjustedType.isNull())
 894       return QualType();
 895
 896     if (originalType.getAsOpaquePtr()
 897           == T->getOriginalType().getAsOpaquePtr() &&
 898         adjustedType.getAsOpaquePtr() == T->getAdjustedType().getAsOpaquePtr())
 899       return QualType(T, 0);
 900
 901     return Ctx.getAdjustedType(originalType, adjustedType);
 902   }
 903
 904   QualType VisitDecayedType(const DecayedType *T) {
 905     QualType originalType = recurse(T->getOriginalType());
 906     if (originalType.isNull())
 907       return QualType();
 908
 909     if (originalType.getAsOpaquePtr()
 910           == T->getOriginalType().getAsOpaquePtr())
 911       return QualType(T, 0);
 912
 913     return Ctx.getDecayedType(originalType);
 914   }
 915
 916   TRIVIAL_TYPE_CLASS(TypeOfExpr)
 917   TRIVIAL_TYPE_CLASS(TypeOf)
 918   TRIVIAL_TYPE_CLASS(Decltype)
 919   TRIVIAL_TYPE_CLASS(UnaryTransform)
 920   TRIVIAL_TYPE_CLASS(Record)
 921   TRIVIAL_TYPE_CLASS(Enum)
 922
 923   // FIXME: Non-trivial to implement, but important for C++
 924   TRIVIAL_TYPE_CLASS(Elaborated)
 925
 926   QualType VisitAttributedType(const AttributedType *T) {
 927     QualType modifiedType = recurse(T->getModifiedType());
 928     if (modifiedType.isNull())
 929       return QualType();
 930
 931     QualType equivalentType = recurse(T->getEquivalentType());
 932     if (equivalentType.isNull())
 933       return QualType();
 934
 935     if (modifiedType.getAsOpaquePtr()
 936           == T->getModifiedType().getAsOpaquePtr() &&
 937         equivalentType.getAsOpaquePtr()
 938           == T->getEquivalentType().getAsOpaquePtr())
 939       return QualType(T, 0);
 940
 941     return Ctx.getAttributedType(T->getAttrKind(), modifiedType,
 942                                  equivalentType);
 943   }
 944
 945   QualType VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T) {
 946     QualType replacementType = recurse(T->getReplacementType());
 947     if (replacementType.isNull())
 948       return QualType();
 949
 950     if (replacementType.getAsOpaquePtr()
 951           == T->getReplacementType().getAsOpaquePtr())
 952       return QualType(T, 0);
 953
 954     return Ctx.getSubstTemplateTypeParmType(T->getReplacedParameter(),
 955                                             replacementType);
 956   }
 957
 958   // FIXME: Non-trivial to implement, but important for C++
 959   TRIVIAL_TYPE_CLASS(TemplateSpecialization)
 960
 961   QualType VisitAutoType(const AutoType *T) {
 962     if (!T->isDeduced())
 963       return QualType(T, 0);
 964
 965     QualType deducedType = recurse(T->getDeducedType());
 966     if (deducedType.isNull())
 967       return QualType();
 968
 969     if (deducedType.getAsOpaquePtr()
 970           == T->getDeducedType().getAsOpaquePtr())
 971       return QualType(T, 0);
 972
 973     return Ctx.getAutoType(deducedType, T->getKeyword(),
 974                            T->isDependentType());
 975   }
 976
 977   // FIXME: Non-trivial to implement, but important for C++
 978   TRIVIAL_TYPE_CLASS(PackExpansion)
 979
 980   QualType VisitObjCObjectType(const ObjCObjectType *T) {
 981     QualType baseType = recurse(T->getBaseType());
 982     if (baseType.isNull())
 983       return QualType();
 984
 985     // Transform type arguments.
 986     bool typeArgChanged = false;
 987     SmallVector<QualType, 4> typeArgs;
 988     for (auto typeArg : T->getTypeArgsAsWritten()) {
 989       QualType newTypeArg = recurse(typeArg);
 990       if (newTypeArg.isNull())
 991         return QualType();
 992
 993       if (newTypeArg.getAsOpaquePtr() != typeArg.getAsOpaquePtr())
 994         typeArgChanged = true;
 995
 996       typeArgs.push_back(newTypeArg);
 997     }
 998
 999     if (baseType.getAsOpaquePtr() == T->getBaseType().getAsOpaquePtr() &&
1000         !typeArgChanged)
1001       return QualType(T, 0);
1002
1003     return Ctx.getObjCObjectType(baseType, typeArgs,
1004                                  llvm::makeArrayRef(T->qual_begin(),
1005                                                     T->getNumProtocols()),
1006                                  T->isKindOfTypeAsWritten());
1007   }
1008
1009   TRIVIAL_TYPE_CLASS(ObjCInterface)
1010
1011   QualType VisitObjCObjectPointerType(const ObjCObjectPointerType *T) {
1012     QualType pointeeType = recurse(T->getPointeeType());
1013     if (pointeeType.isNull())
1014       return QualType();
1015
1016     if (pointeeType.getAsOpaquePtr()
1017           == T->getPointeeType().getAsOpaquePtr())
1018       return QualType(T, 0);
1019
1020     return Ctx.getObjCObjectPointerType(pointeeType);
1021   }
1022
1023   QualType VisitAtomicType(const AtomicType *T) {
1024     QualType valueType = recurse(T->getValueType());
1025     if (valueType.isNull())
1026       return QualType();
1027
1028     if (valueType.getAsOpaquePtr()
1029           == T->getValueType().getAsOpaquePtr())
1030       return QualType(T, 0);
1031
1032     return Ctx.getAtomicType(valueType);
1033   }
1034
1035 #undef TRIVIAL_TYPE_CLASS
1036 };
1037
1038 /// Perform a simple type transformation that does not change the
1039 /// semantics of the type.
1040 template<typename F>
1041 QualType simpleTransform(ASTContext &ctx, QualType type, F &&f) {
1042   // Transform the type. If it changed, return the transformed result.
1043   QualType transformed = f(type);
1044   if (transformed.getAsOpaquePtr() != type.getAsOpaquePtr())
1045     return transformed;
1046
1047   // Split out the qualifiers from the type.
1048   SplitQualType splitType = type.split();
1049
1050   // Visit the type itself.
1051   SimpleTransformVisitor<F> visitor(ctx, std::move(f));
1052   QualType result = visitor.Visit(splitType.Ty);
1053   if (result.isNull())
1054     return result;
1055
1056   // Reconstruct the transformed type by applying the local qualifiers
1057   // from the split type.
1058   return ctx.getQualifiedType(result, splitType.Quals);
1059 }
1060
1061 } // end anonymous namespace
1062
1063 /// Substitute the given type arguments for Objective-C type
1064 /// parameters within the given type, recursively.
1065 QualType QualType::substObjCTypeArgs(
1066            ASTContext &ctx,
1067            ArrayRef<QualType> typeArgs,
1068            ObjCSubstitutionContext context) const {
1069   return simpleTransform(ctx, *this,
1070                          [&](QualType type) -> QualType {
1071     SplitQualType splitType = type.split();
1072
1073     // Replace an Objective-C type parameter reference with the corresponding
1074     // type argument.
1075     if (const auto *typedefTy = dyn_cast<TypedefType>(splitType.Ty)) {
1076       if (auto *typeParam = dyn_cast<ObjCTypeParamDecl>(typedefTy->getDecl())) {
1077         // If we have type arguments, use them.
1078         if (!typeArgs.empty()) {
1079           // FIXME: Introduce SubstObjCTypeParamType ?
1080           QualType argType = typeArgs[typeParam->getIndex()];
1081           return ctx.getQualifiedType(argType, splitType.Quals);
1082         }
1083
1084         switch (context) {
1085         case ObjCSubstitutionContext::Ordinary:
1086         case ObjCSubstitutionContext::Parameter:
1087         case ObjCSubstitutionContext::Superclass:
1088           // Substitute the bound.
1089           return ctx.getQualifiedType(typeParam->getUnderlyingType(),
1090                                       splitType.Quals);
1091
1092         case ObjCSubstitutionContext::Result:
1093         case ObjCSubstitutionContext::Property: {
1094           // Substitute the __kindof form of the underlying type.
1095           const auto *objPtr = typeParam->getUnderlyingType()
1096             ->castAs<ObjCObjectPointerType>();
1097
1098           // __kindof types, id, and Class don't need an additional
1099           // __kindof.
1100           if (objPtr->isKindOfType() || objPtr->isObjCIdOrClassType())
1101             return ctx.getQualifiedType(typeParam->getUnderlyingType(),
1102                                         splitType.Quals);
1103
1104           // Add __kindof.
1105           const auto *obj = objPtr->getObjectType();
1106           QualType resultTy = ctx.getObjCObjectType(obj->getBaseType(),
1107                                                     obj->getTypeArgsAsWritten(),
1108                                                     obj->getProtocols(),
1109                                                     /*isKindOf=*/true);
1110
1111           // Rebuild object pointer type.
1112           resultTy = ctx.getObjCObjectPointerType(resultTy);
1113           return ctx.getQualifiedType(resultTy, splitType.Quals);
1114         }
1115         }
1116       }
1117     }
1118
1119     // If we have a function type, update the context appropriately.
1120     if (const auto *funcType = dyn_cast<FunctionType>(splitType.Ty)) {
1121       // Substitute result type.
1122       QualType returnType = funcType->getReturnType().substObjCTypeArgs(
1123                               ctx,
1124                               typeArgs,
1125                               ObjCSubstitutionContext::Result);
1126       if (returnType.isNull())
1127         return QualType();
1128
1129       // Handle non-prototyped functions, which only substitute into the result
1130       // type.
1131       if (isa<FunctionNoProtoType>(funcType)) {
1132         // If the return type was unchanged, do nothing.
1133         if (returnType.getAsOpaquePtr()
1134               == funcType->getReturnType().getAsOpaquePtr())
1135           return type;
1136
1137         // Otherwise, build a new type.
1138         return ctx.getFunctionNoProtoType(returnType, funcType->getExtInfo());
1139       }
1140
1141       const auto *funcProtoType = cast<FunctionProtoType>(funcType);
1142
1143       // Transform parameter types.
1144       SmallVector<QualType, 4> paramTypes;
1145       bool paramChanged = false;
1146       for (auto paramType : funcProtoType->getParamTypes()) {
1147         QualType newParamType = paramType.substObjCTypeArgs(
1148                                   ctx,
1149                                   typeArgs,
1150                                   ObjCSubstitutionContext::Parameter);
1151         if (newParamType.isNull())
1152           return QualType();
1153
1154         if (newParamType.getAsOpaquePtr() != paramType.getAsOpaquePtr())
1155           paramChanged = true;
1156
1157         paramTypes.push_back(newParamType);
1158       }
1159
1160       // Transform extended info.
1161       FunctionProtoType::ExtProtoInfo info = funcProtoType->getExtProtoInfo();
1162       bool exceptionChanged = false;
1163       if (info.ExceptionSpec.Type == EST_Dynamic) {
1164         SmallVector<QualType, 4> exceptionTypes;
1165         for (auto exceptionType : info.ExceptionSpec.Exceptions) {
1166           QualType newExceptionType = exceptionType.substObjCTypeArgs(
1167                                         ctx,
1168                                         typeArgs,
1169                                         ObjCSubstitutionContext::Ordinary);
1170           if (newExceptionType.isNull())
1171             return QualType();
1172
1173           if (newExceptionType.getAsOpaquePtr()
1174               != exceptionType.getAsOpaquePtr())
1175             exceptionChanged = true;
1176
1177           exceptionTypes.push_back(newExceptionType);
1178         }
1179
1180         if (exceptionChanged) {
1181           info.ExceptionSpec.Exceptions =
1182               llvm::makeArrayRef(exceptionTypes).copy(ctx);
1183         }
1184       }
1185
1186       if (returnType.getAsOpaquePtr()
1187             == funcProtoType->getReturnType().getAsOpaquePtr() &&
1188           !paramChanged && !exceptionChanged)
1189         return type;
1190
1191       return ctx.getFunctionType(returnType, paramTypes, info);
1192     }
1193
1194     // Substitute into the type arguments of a specialized Objective-C object
1195     // type.
1196     if (const auto *objcObjectType = dyn_cast<ObjCObjectType>(splitType.Ty)) {
1197       if (objcObjectType->isSpecializedAsWritten()) {
1198         SmallVector<QualType, 4> newTypeArgs;
1199         bool anyChanged = false;
1200         for (auto typeArg : objcObjectType->getTypeArgsAsWritten()) {
1201           QualType newTypeArg = typeArg.substObjCTypeArgs(
1202                                   ctx, typeArgs,
1203                                   ObjCSubstitutionContext::Ordinary);
1204           if (newTypeArg.isNull())
1205             return QualType();
1206
1207           if (newTypeArg.getAsOpaquePtr() != typeArg.getAsOpaquePtr()) {
1208             // If we're substituting based on an unspecialized context type,
1209             // produce an unspecialized type.
1210             ArrayRef<ObjCProtocolDecl *> protocols(
1211                                            objcObjectType->qual_begin(),
1212                                            objcObjectType->getNumProtocols());
1213             if (typeArgs.empty() &&
1214                 context != ObjCSubstitutionContext::Superclass) {
1215               return ctx.getObjCObjectType(
1216                        objcObjectType->getBaseType(), { },
1217                        protocols,
1218                        objcObjectType->isKindOfTypeAsWritten());
1219             }
1220
1221             anyChanged = true;
1222           }
1223
1224           newTypeArgs.push_back(newTypeArg);
1225         }
1226
1227         if (anyChanged) {
1228           ArrayRef<ObjCProtocolDecl *> protocols(
1229                                          objcObjectType->qual_begin(),
1230                                          objcObjectType->getNumProtocols());
1231           return ctx.getObjCObjectType(objcObjectType->getBaseType(),
1232                                        newTypeArgs, protocols,
1233                                        objcObjectType->isKindOfTypeAsWritten());
1234         }
1235       }
1236
1237       return type;
1238     }
1239
1240     return type;
1241   });
1242 }
1243
1244 QualType QualType::substObjCMemberType(QualType objectType,
1245                                        const DeclContext *dc,
1246                                        ObjCSubstitutionContext context) const {
1247   if (auto subs = objectType->getObjCSubstitutions(dc))
1248     return substObjCTypeArgs(dc->getParentASTContext(), *subs, context);
1249
1250   return *this;
1251 }
1252
1253 QualType QualType::stripObjCKindOfType(const ASTContext &constCtx) const {
1254   // FIXME: Because ASTContext::getAttributedType() is non-const.
1255   auto &ctx = const_cast<ASTContext &>(constCtx);
1256   return simpleTransform(ctx, *this,
1257            [&](QualType type) -> QualType {
1258              SplitQualType splitType = type.split();
1259              if (auto *objType = splitType.Ty->getAs<ObjCObjectType>()) {
1260                if (!objType->isKindOfType())
1261                  return type;
1262
1263                QualType baseType
1264                  = objType->getBaseType().stripObjCKindOfType(ctx);
1265                return ctx.getQualifiedType(
1266                         ctx.getObjCObjectType(baseType,
1267                                               objType->getTypeArgsAsWritten(),
1268                                               objType->getProtocols(),
1269                                               /*isKindOf=*/false),
1270                         splitType.Quals);
1271              }
1272
1273              return type;
1274            });
1275 }
1276
1277 QualType QualType::getAtomicUnqualifiedType() const {
1278   if (auto AT = getTypePtr()->getAs<AtomicType>())
1279     return AT->getValueType().getUnqualifiedType();
1280   return getUnqualifiedType();
1281 }
1282
1283 Optional<ArrayRef<QualType>> Type::getObjCSubstitutions(
1284                                const DeclContext *dc) const {
1285   // Look through method scopes.
1286   if (auto method = dyn_cast<ObjCMethodDecl>(dc))
1287     dc = method->getDeclContext();
1288
1289   // Find the class or category in which the type we're substituting
1290   // was declared.
1291   const ObjCInterfaceDecl *dcClassDecl = dyn_cast<ObjCInterfaceDecl>(dc);
1292   const ObjCCategoryDecl *dcCategoryDecl = nullptr;
1293   ObjCTypeParamList *dcTypeParams = nullptr;
1294   if (dcClassDecl) {
1295     // If the class does not have any type parameters, there's no
1296     // substitution to do.
1297     dcTypeParams = dcClassDecl->getTypeParamList();
1298     if (!dcTypeParams)
1299       return None;
1300   } else {
1301     // If we are in neither a class nor a category, there's no
1302     // substitution to perform.
1303     dcCategoryDecl = dyn_cast<ObjCCategoryDecl>(dc);
1304     if (!dcCategoryDecl)
1305       return None;
1306
1307     // If the category does not have any type parameters, there's no
1308     // substitution to do.
1309     dcTypeParams = dcCategoryDecl->getTypeParamList();
1310     if (!dcTypeParams)
1311       return None;
1312
1313     dcClassDecl = dcCategoryDecl->getClassInterface();
1314     if (!dcClassDecl)
1315       return None;
1316   }
1317   assert(dcTypeParams && "No substitutions to perform");
1318   assert(dcClassDecl && "No class context");
1319
1320   // Find the underlying object type.
1321   const ObjCObjectType *objectType;
1322   if (const auto *objectPointerType = getAs<ObjCObjectPointerType>()) {
1323     objectType = objectPointerType->getObjectType();
1324   } else if (getAs<BlockPointerType>()) {
1325     ASTContext &ctx = dc->getParentASTContext();
1326     objectType = ctx.getObjCObjectType(ctx.ObjCBuiltinIdTy, { }, { })
1327                    ->castAs<ObjCObjectType>();;
1328   } else {
1329     objectType = getAs<ObjCObjectType>();
1330   }
1331
1332   /// Extract the class from the receiver object type.
1333   ObjCInterfaceDecl *curClassDecl = objectType ? objectType->getInterface()
1334                                                : nullptr;
1335   if (!curClassDecl) {
1336     // If we don't have a context type (e.g., this is "id" or some
1337     // variant thereof), substitute the bounds.
1338     return llvm::ArrayRef<QualType>();
1339   }
1340
1341   // Follow the superclass chain until we've mapped the receiver type
1342   // to the same class as the context.
1343   while (curClassDecl != dcClassDecl) {
1344     // Map to the superclass type.
1345     QualType superType = objectType->getSuperClassType();
1346     if (superType.isNull()) {
1347       objectType = nullptr;
1348       break;
1349     }
1350
1351     objectType = superType->castAs<ObjCObjectType>();
1352     curClassDecl = objectType->getInterface();
1353   }
1354
1355   // If we don't have a receiver type, or the receiver type does not
1356   // have type arguments, substitute in the defaults.
1357   if (!objectType || objectType->isUnspecialized()) {
1358     return llvm::ArrayRef<QualType>();
1359   }
1360
1361   // The receiver type has the type arguments we want.
1362   return objectType->getTypeArgs();
1363 }
1364
1365 bool Type::acceptsObjCTypeParams() const {
1366   if (auto *IfaceT = getAsObjCInterfaceType()) {
1367     if (auto *ID = IfaceT->getInterface()) {
1368       if (ID->getTypeParamList())
1369         return true;
1370     }
1371   }
1372
1373   return false;
1374 }
1375
1376 void ObjCObjectType::computeSuperClassTypeSlow() const {
1377   // Retrieve the class declaration for this type. If there isn't one
1378   // (e.g., this is some variant of "id" or "Class"), then there is no
1379   // superclass type.
1380   ObjCInterfaceDecl *classDecl = getInterface();
1381   if (!classDecl) {
1382     CachedSuperClassType.setInt(true);
1383     return;
1384   }
1385
1386   // Extract the superclass type.
1387   const ObjCObjectType *superClassObjTy = classDecl->getSuperClassType();
1388   if (!superClassObjTy) {
1389     CachedSuperClassType.setInt(true);
1390     return;
1391   }
1392
1393   ObjCInterfaceDecl *superClassDecl = superClassObjTy->getInterface();
1394   if (!superClassDecl) {
1395     CachedSuperClassType.setInt(true);
1396     return;
1397   }
1398
1399   // If the superclass doesn't have type parameters, then there is no
1400   // substitution to perform.
1401   QualType superClassType(superClassObjTy, 0);
1402   ObjCTypeParamList *superClassTypeParams = superClassDecl->getTypeParamList();
1403   if (!superClassTypeParams) {
1404     CachedSuperClassType.setPointerAndInt(
1405       superClassType->castAs<ObjCObjectType>(), true);
1406     return;
1407   }
1408
1409   // If the superclass reference is unspecialized, return it.
1410   if (superClassObjTy->isUnspecialized()) {
1411     CachedSuperClassType.setPointerAndInt(superClassObjTy, true);
1412     return;
1413   }
1414
1415   // If the subclass is not parameterized, there aren't any type
1416   // parameters in the superclass reference to substitute.
1417   ObjCTypeParamList *typeParams = classDecl->getTypeParamList();
1418   if (!typeParams) {
1419     CachedSuperClassType.setPointerAndInt(
1420       superClassType->castAs<ObjCObjectType>(), true);
1421     return;
1422   }
1423
1424   // If the subclass type isn't specialized, return the unspecialized
1425   // superclass.
1426   if (isUnspecialized()) {
1427     QualType unspecializedSuper
1428       = classDecl->getASTContext().getObjCInterfaceType(
1429           superClassObjTy->getInterface());
1430     CachedSuperClassType.setPointerAndInt(
1431       unspecializedSuper->castAs<ObjCObjectType>(),
1432       true);
1433     return;
1434   }
1435
1436   // Substitute the provided type arguments into the superclass type.
1437   ArrayRef<QualType> typeArgs = getTypeArgs();
1438   assert(typeArgs.size() == typeParams->size());
1439   CachedSuperClassType.setPointerAndInt(
1440     superClassType.substObjCTypeArgs(classDecl->getASTContext(), typeArgs,
1441                                      ObjCSubstitutionContext::Superclass)
1442       ->castAs<ObjCObjectType>(),
1443     true);
1444 }
1445
1446 const ObjCInterfaceType *ObjCObjectPointerType::getInterfaceType() const {
1447   if (auto interfaceDecl = getObjectType()->getInterface()) {
1448     return interfaceDecl->getASTContext().getObjCInterfaceType(interfaceDecl)
1449              ->castAs<ObjCInterfaceType>();
1450   }
1451
1452   return nullptr;
1453 }
1454
1455 QualType ObjCObjectPointerType::getSuperClassType() const {
1456   QualType superObjectType = getObjectType()->getSuperClassType();
1457   if (superObjectType.isNull())
1458     return superObjectType;
1459
1460   ASTContext &ctx = getInterfaceDecl()->getASTContext();
1461   return ctx.getObjCObjectPointerType(superObjectType);
1462 }
1463
1464 const ObjCObjectType *Type::getAsObjCQualifiedInterfaceType() const {
1465   // There is no sugar for ObjCObjectType's, just return the canonical
1466   // type pointer if it is the right class.  There is no typedef information to
1467   // return and these cannot be Address-space qualified.
1468   if (const ObjCObjectType *T = getAs<ObjCObjectType>())
1469     if (T->getNumProtocols() && T->getInterface())
1470       return T;
1471   return nullptr;
1472 }
1473
1474 bool Type::isObjCQualifiedInterfaceType() const {
1475   return getAsObjCQualifiedInterfaceType() != nullptr;
1476 }
1477
1478 const ObjCObjectPointerType *Type::getAsObjCQualifiedIdType() const {
1479   // There is no sugar for ObjCQualifiedIdType's, just return the canonical
1480   // type pointer if it is the right class.
1481   if (const ObjCObjectPointerType *OPT = getAs<ObjCObjectPointerType>()) {
1482     if (OPT->isObjCQualifiedIdType())
1483       return OPT;
1484   }
1485   return nullptr;
1486 }
1487
1488 const ObjCObjectPointerType *Type::getAsObjCQualifiedClassType() const {
1489   // There is no sugar for ObjCQualifiedClassType's, just return the canonical
1490   // type pointer if it is the right class.
1491   if (const ObjCObjectPointerType *OPT = getAs<ObjCObjectPointerType>()) {
1492     if (OPT->isObjCQualifiedClassType())
1493       return OPT;
1494   }
1495   return nullptr;
1496 }
1497
1498 const ObjCObjectType *Type::getAsObjCInterfaceType() const {
1499   if (const ObjCObjectType *OT = getAs<ObjCObjectType>()) {
1500     if (OT->getInterface())
1501       return OT;
1502   }
1503   return nullptr;
1504 }
1505 const ObjCObjectPointerType *Type::getAsObjCInterfacePointerType() const {
1506   if (const ObjCObjectPointerType *OPT = getAs<ObjCObjectPointerType>()) {
1507     if (OPT->getInterfaceType())
1508       return OPT;
1509   }
1510   return nullptr;
1511 }
1512
1513 const CXXRecordDecl *Type::getPointeeCXXRecordDecl() const {
1514   QualType PointeeType;
1515   if (const PointerType *PT = getAs<PointerType>())
1516     PointeeType = PT->getPointeeType();
1517   else if (const ReferenceType *RT = getAs<ReferenceType>())
1518     PointeeType = RT->getPointeeType();
1519   else
1520     return nullptr;
1521
1522   if (const RecordType *RT = PointeeType->getAs<RecordType>())
1523     return dyn_cast<CXXRecordDecl>(RT->getDecl());
1524
1525   return nullptr;
1526 }
1527
1528 CXXRecordDecl *Type::getAsCXXRecordDecl() const {
1529   return dyn_cast_or_null<CXXRecordDecl>(getAsTagDecl());
1530 }
1531
1532 TagDecl *Type::getAsTagDecl() const {
1533   if (const auto *TT = getAs<TagType>())
1534     return cast<TagDecl>(TT->getDecl());
1535   if (const auto *Injected = getAs<InjectedClassNameType>())
1536     return Injected->getDecl();
1537
1538   return nullptr;
1539 }
1540
1541 namespace {
1542   class GetContainedAutoVisitor :
1543     public TypeVisitor<GetContainedAutoVisitor, AutoType*> {
1544   public:
1545     using TypeVisitor<GetContainedAutoVisitor, AutoType*>::Visit;
1546     AutoType *Visit(QualType T) {
1547       if (T.isNull())
1548         return nullptr;
1549       return Visit(T.getTypePtr());
1550     }
1551
1552     // The 'auto' type itself.
1553     AutoType *VisitAutoType(const AutoType *AT) {
1554       return const_cast<AutoType*>(AT);
1555     }
1556
1557     // Only these types can contain the desired 'auto' type.
1558     AutoType *VisitPointerType(const PointerType *T) {
1559       return Visit(T->getPointeeType());
1560     }
1561     AutoType *VisitBlockPointerType(const BlockPointerType *T) {
1562       return Visit(T->getPointeeType());
1563     }
1564     AutoType *VisitReferenceType(const ReferenceType *T) {
1565       return Visit(T->getPointeeTypeAsWritten());
1566     }
1567     AutoType *VisitMemberPointerType(const MemberPointerType *T) {
1568       return Visit(T->getPointeeType());
1569     }
1570     AutoType *VisitArrayType(const ArrayType *T) {
1571       return Visit(T->getElementType());
1572     }
1573     AutoType *VisitDependentSizedExtVectorType(
1574       const DependentSizedExtVectorType *T) {
1575       return Visit(T->getElementType());
1576     }
1577     AutoType *VisitVectorType(const VectorType *T) {
1578       return Visit(T->getElementType());
1579     }
1580     AutoType *VisitFunctionType(const FunctionType *T) {
1581       return Visit(T->getReturnType());
1582     }
1583     AutoType *VisitParenType(const ParenType *T) {
1584       return Visit(T->getInnerType());
1585     }
1586     AutoType *VisitAttributedType(const AttributedType *T) {
1587       return Visit(T->getModifiedType());
1588     }
1589     AutoType *VisitAdjustedType(const AdjustedType *T) {
1590       return Visit(T->getOriginalType());
1591     }
1592   };
1593 }
1594
1595 AutoType *Type::getContainedAutoType() const {
1596   return GetContainedAutoVisitor().Visit(this);
1597 }
1598
1599 bool Type::hasIntegerRepresentation() const {
1600   if (const VectorType *VT = dyn_cast<VectorType>(CanonicalType))
1601     return VT->getElementType()->isIntegerType();
1602   else
1603     return isIntegerType();
1604 }
1605
1606 /// \brief Determine whether this type is an integral type.
1607 ///
1608 /// This routine determines whether the given type is an integral type per
1609 /// C++ [basic.fundamental]p7. Although the C standard does not define the
1610 /// term "integral type", it has a similar term "integer type", and in C++
1611 /// the two terms are equivalent. However, C's "integer type" includes
1612 /// enumeration types, while C++'s "integer type" does not. The \c ASTContext
1613 /// parameter is used to determine whether we should be following the C or
1614 /// C++ rules when determining whether this type is an integral/integer type.
1615 ///
1616 /// For cases where C permits "an integer type" and C++ permits "an integral
1617 /// type", use this routine.
1618 ///
1619 /// For cases where C permits "an integer type" and C++ permits "an integral
1620 /// or enumeration type", use \c isIntegralOrEnumerationType() instead.
1621 ///
1622 /// \param Ctx The context in which this type occurs.
1623 ///
1624 /// \returns true if the type is considered an integral type, false otherwise.
1625 bool Type::isIntegralType(const ASTContext &Ctx) const {
1626   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1627     return BT->getKind() >= BuiltinType::Bool &&
1628            BT->getKind() <= BuiltinType::Int128;
1629
1630   // Complete enum types are integral in C.
1631   if (!Ctx.getLangOpts().CPlusPlus)
1632     if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
1633       return ET->getDecl()->isComplete();
1634
1635   return false;
1636 }
1637
1638
1639 bool Type::isIntegralOrUnscopedEnumerationType() const {
1640   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1641     return BT->getKind() >= BuiltinType::Bool &&
1642            BT->getKind() <= BuiltinType::Int128;
1643
1644   // Check for a complete enum type; incomplete enum types are not properly an
1645   // enumeration type in the sense required here.
1646   // C++0x: However, if the underlying type of the enum is fixed, it is
1647   // considered complete.
1648   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
1649     return ET->getDecl()->isComplete() && !ET->getDecl()->isScoped();
1650
1651   return false;
1652 }
1653
1654
1655
1656 bool Type::isCharType() const {
1657   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1658     return BT->getKind() == BuiltinType::Char_U ||
1659            BT->getKind() == BuiltinType::UChar ||
1660            BT->getKind() == BuiltinType::Char_S ||
1661            BT->getKind() == BuiltinType::SChar;
1662   return false;
1663 }
1664
1665 bool Type::isWideCharType() const {
1666   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1667     return BT->getKind() == BuiltinType::WChar_S ||
1668            BT->getKind() == BuiltinType::WChar_U;
1669   return false;
1670 }
1671
1672 bool Type::isChar16Type() const {
1673   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1674     return BT->getKind() == BuiltinType::Char16;
1675   return false;
1676 }
1677
1678 bool Type::isChar32Type() const {
1679   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1680     return BT->getKind() == BuiltinType::Char32;
1681   return false;
1682 }
1683
1684 /// \brief Determine whether this type is any of the built-in character
1685 /// types.
1686 bool Type::isAnyCharacterType() const {
1687   const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType);
1688   if (!BT) return false;
1689   switch (BT->getKind()) {
1690   default: return false;
1691   case BuiltinType::Char_U:
1692   case BuiltinType::UChar:
1693   case BuiltinType::WChar_U:
1694   case BuiltinType::Char16:
1695   case BuiltinType::Char32:
1696   case BuiltinType::Char_S:
1697   case BuiltinType::SChar:
1698   case BuiltinType::WChar_S:
1699     return true;
1700   }
1701 }
1702
1703 /// isSignedIntegerType - Return true if this is an integer type that is
1704 /// signed, according to C99 6.2.5p4 [char, signed char, short, int, long..],
1705 /// an enum decl which has a signed representation
1706 bool Type::isSignedIntegerType() const {
1707   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType)) {
1708     return BT->getKind() >= BuiltinType::Char_S &&
1709            BT->getKind() <= BuiltinType::Int128;
1710   }
1711
1712   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType)) {
1713     // Incomplete enum types are not treated as integer types.
1714     // FIXME: In C++, enum types are never integer types.
1715     if (ET->getDecl()->isComplete() && !ET->getDecl()->isScoped())
1716       return ET->getDecl()->getIntegerType()->isSignedIntegerType();
1717   }
1718
1719   return false;
1720 }
1721
1722 bool Type::isSignedIntegerOrEnumerationType() const {
1723   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType)) {
1724     return BT->getKind() >= BuiltinType::Char_S &&
1725            BT->getKind() <= BuiltinType::Int128;
1726   }
1727
1728   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType)) {
1729     if (ET->getDecl()->isComplete())
1730       return ET->getDecl()->getIntegerType()->isSignedIntegerType();
1731   }
1732
1733   return false;
1734 }
1735
1736 bool Type::hasSignedIntegerRepresentation() const {
1737   if (const VectorType *VT = dyn_cast<VectorType>(CanonicalType))
1738     return VT->getElementType()->isSignedIntegerOrEnumerationType();
1739   else
1740     return isSignedIntegerOrEnumerationType();
1741 }
1742
1743 /// isUnsignedIntegerType - Return true if this is an integer type that is
1744 /// unsigned, according to C99 6.2.5p6 [which returns true for _Bool], an enum
1745 /// decl which has an unsigned representation
1746 bool Type::isUnsignedIntegerType() const {
1747   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType)) {
1748     return BT->getKind() >= BuiltinType::Bool &&
1749            BT->getKind() <= BuiltinType::UInt128;
1750   }
1751
1752   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType)) {
1753     // Incomplete enum types are not treated as integer types.
1754     // FIXME: In C++, enum types are never integer types.
1755     if (ET->getDecl()->isComplete() && !ET->getDecl()->isScoped())
1756       return ET->getDecl()->getIntegerType()->isUnsignedIntegerType();
1757   }
1758
1759   return false;
1760 }
1761
1762 bool Type::isUnsignedIntegerOrEnumerationType() const {
1763   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType)) {
1764     return BT->getKind() >= BuiltinType::Bool &&
1765     BT->getKind() <= BuiltinType::UInt128;
1766   }
1767
1768   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType)) {
1769     if (ET->getDecl()->isComplete())
1770       return ET->getDecl()->getIntegerType()->isUnsignedIntegerType();
1771   }
1772
1773   return false;
1774 }
1775
1776 bool Type::hasUnsignedIntegerRepresentation() const {
1777   if (const VectorType *VT = dyn_cast<VectorType>(CanonicalType))
1778     return VT->getElementType()->isUnsignedIntegerOrEnumerationType();
1779   else
1780     return isUnsignedIntegerOrEnumerationType();
1781 }
1782
1783 bool Type::isFloatingType() const {
1784   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1785     return BT->getKind() >= BuiltinType::Half &&
1786            BT->getKind() <= BuiltinType::Float128;
1787   if (const ComplexType *CT = dyn_cast<ComplexType>(CanonicalType))
1788     return CT->getElementType()->isFloatingType();
1789   return false;
1790 }
1791
1792 bool Type::hasFloatingRepresentation() const {
1793   if (const VectorType *VT = dyn_cast<VectorType>(CanonicalType))
1794     return VT->getElementType()->isFloatingType();
1795   else
1796     return isFloatingType();
1797 }
1798
1799 bool Type::isRealFloatingType() const {
1800   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1801     return BT->isFloatingPoint();
1802   return false;
1803 }
1804
1805 bool Type::isRealType() const {
1806   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1807     return BT->getKind() >= BuiltinType::Bool &&
1808            BT->getKind() <= BuiltinType::Float128;
1809   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
1810       return ET->getDecl()->isComplete() && !ET->getDecl()->isScoped();
1811   return false;
1812 }
1813
1814 bool Type::isArithmeticType() const {
1815   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
1816     return BT->getKind() >= BuiltinType::Bool &&
1817            BT->getKind() <= BuiltinType::Float128;
1818   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
1819     // GCC allows forward declaration of enum types (forbid by C99 6.7.2.3p2).
1820     // If a body isn't seen by the time we get here, return false.
1821     //
1822     // C++0x: Enumerations are not arithmetic types. For now, just return
1823     // false for scoped enumerations since that will disable any
1824     // unwanted implicit conversions.
1825     return !ET->getDecl()->isScoped() && ET->getDecl()->isComplete();
1826   return isa<ComplexType>(CanonicalType);
1827 }
1828
1829 Type::ScalarTypeKind Type::getScalarTypeKind() const {
1830   assert(isScalarType());
1831
1832   const Type *T = CanonicalType.getTypePtr();
1833   if (const BuiltinType *BT = dyn_cast<BuiltinType>(T)) {
1834     if (BT->getKind() == BuiltinType::Bool) return STK_Bool;
1835     if (BT->getKind() == BuiltinType::NullPtr) return STK_CPointer;
1836     if (BT->isInteger()) return STK_Integral;
1837     if (BT->isFloatingPoint()) return STK_Floating;
1838     llvm_unreachable("unknown scalar builtin type");
1839   } else if (isa<PointerType>(T)) {
1840     return STK_CPointer;
1841   } else if (isa<BlockPointerType>(T)) {
1842     return STK_BlockPointer;
1843   } else if (isa<ObjCObjectPointerType>(T)) {
1844     return STK_ObjCObjectPointer;
1845   } else if (isa<MemberPointerType>(T)) {
1846     return STK_MemberPointer;
1847   } else if (isa<EnumType>(T)) {
1848     assert(cast<EnumType>(T)->getDecl()->isComplete());
1849     return STK_Integral;
1850   } else if (const ComplexType *CT = dyn_cast<ComplexType>(T)) {
1851     if (CT->getElementType()->isRealFloatingType())
1852       return STK_FloatingComplex;
1853     return STK_IntegralComplex;
1854   }
1855
1856   llvm_unreachable("unknown scalar type");
1857 }
1858
1859 /// \brief Determines whether the type is a C++ aggregate type or C
1860 /// aggregate or union type.
1861 ///
1862 /// An aggregate type is an array or a class type (struct, union, or
1863 /// class) that has no user-declared constructors, no private or
1864 /// protected non-static data members, no base classes, and no virtual
1865 /// functions (C++ [dcl.init.aggr]p1). The notion of an aggregate type
1866 /// subsumes the notion of C aggregates (C99 6.2.5p21) because it also
1867 /// includes union types.
1868 bool Type::isAggregateType() const {
1869   if (const RecordType *Record = dyn_cast<RecordType>(CanonicalType)) {
1870     if (CXXRecordDecl *ClassDecl = dyn_cast<CXXRecordDecl>(Record->getDecl()))
1871       return ClassDecl->isAggregate();
1872
1873     return true;
1874   }
1875
1876   return isa<ArrayType>(CanonicalType);
1877 }
1878
1879 /// isConstantSizeType - Return true if this is not a variable sized type,
1880 /// according to the rules of C99 6.7.5p3.  It is not legal to call this on
1881 /// incomplete types or dependent types.
1882 bool Type::isConstantSizeType() const {
1883   assert(!isIncompleteType() && "This doesn't make sense for incomplete types");
1884   assert(!isDependentType() && "This doesn't make sense for dependent types");
1885   // The VAT must have a size, as it is known to be complete.
1886   return !isa<VariableArrayType>(CanonicalType);
1887 }
1888
1889 /// isIncompleteType - Return true if this is an incomplete type (C99 6.2.5p1)
1890 /// - a type that can describe objects, but which lacks information needed to
1891 /// determine its size.
1892 bool Type::isIncompleteType(NamedDecl **Def) const {
1893   if (Def)
1894     *Def = nullptr;
1895
1896   switch (CanonicalType->getTypeClass()) {
1897   default: return false;
1898   case Builtin:
1899     // Void is the only incomplete builtin type.  Per C99 6.2.5p19, it can never
1900     // be completed.
1901     return isVoidType();
1902   case Enum: {
1903     EnumDecl *EnumD = cast<EnumType>(CanonicalType)->getDecl();
1904     if (Def)
1905       *Def = EnumD;
1906
1907     // An enumeration with fixed underlying type is complete (C++0x 7.2p3).
1908     if (EnumD->isFixed())
1909       return false;
1910
1911     return !EnumD->isCompleteDefinition();
1912   }
1913   case Record: {
1914     // A tagged type (struct/union/enum/class) is incomplete if the decl is a
1915     // forward declaration, but not a full definition (C99 6.2.5p22).
1916     RecordDecl *Rec = cast<RecordType>(CanonicalType)->getDecl();
1917     if (Def)
1918       *Def = Rec;
1919     return !Rec->isCompleteDefinition();
1920   }
1921   case ConstantArray:
1922     // An array is incomplete if its element type is incomplete
1923     // (C++ [dcl.array]p1).
1924     // We don't handle variable arrays (they're not allowed in C++) or
1925     // dependent-sized arrays (dependent types are never treated as incomplete).
1926     return cast<ArrayType>(CanonicalType)->getElementType()
1927              ->isIncompleteType(Def);
1928   case IncompleteArray:
1929     // An array of unknown size is an incomplete type (C99 6.2.5p22).
1930     return true;
1931   case MemberPointer: {
1932     // Member pointers in the MS ABI have special behavior in
1933     // RequireCompleteType: they attach a MSInheritanceAttr to the CXXRecordDecl
1934     // to indicate which inheritance model to use.
1935     auto *MPTy = cast<MemberPointerType>(CanonicalType);
1936     const Type *ClassTy = MPTy->getClass();
1937     // Member pointers with dependent class types don't get special treatment.
1938     if (ClassTy->isDependentType())
1939       return false;
1940     const CXXRecordDecl *RD = ClassTy->getAsCXXRecordDecl();
1941     ASTContext &Context = RD->getASTContext();
1942     // Member pointers not in the MS ABI don't get special treatment.
1943     if (!Context.getTargetInfo().getCXXABI().isMicrosoft())
1944       return false;
1945     // The inheritance attribute might only be present on the most recent
1946     // CXXRecordDecl, use that one.
1947     RD = RD->getMostRecentDecl();
1948     // Nothing interesting to do if the inheritance attribute is already set.
1949     if (RD->hasAttr<MSInheritanceAttr>())
1950       return false;
1951     return true;
1952   }
1953   case ObjCObject:
1954     return cast<ObjCObjectType>(CanonicalType)->getBaseType()
1955              ->isIncompleteType(Def);
1956   case ObjCInterface: {
1957     // ObjC interfaces are incomplete if they are @class, not @interface.
1958     ObjCInterfaceDecl *Interface
1959       = cast<ObjCInterfaceType>(CanonicalType)->getDecl();
1960     if (Def)
1961       *Def = Interface;
1962     return !Interface->hasDefinition();
1963   }
1964   }
1965 }
1966
1967 bool QualType::isPODType(const ASTContext &Context) const {
1968   // C++11 has a more relaxed definition of POD.
1969   if (Context.getLangOpts().CPlusPlus11)
1970     return isCXX11PODType(Context);
1971
1972   return isCXX98PODType(Context);
1973 }
1974
1975 bool QualType::isCXX98PODType(const ASTContext &Context) const {
1976   // The compiler shouldn't query this for incomplete types, but the user might.
1977   // We return false for that case. Except for incomplete arrays of PODs, which
1978   // are PODs according to the standard.
1979   if (isNull())
1980     return 0;
1981
1982   if ((*this)->isIncompleteArrayType())
1983     return Context.getBaseElementType(*this).isCXX98PODType(Context);
1984
1985   if ((*this)->isIncompleteType())
1986     return false;
1987
1988   if (Context.getLangOpts().ObjCAutoRefCount) {
1989     switch (getObjCLifetime()) {
1990     case Qualifiers::OCL_ExplicitNone:
1991       return true;
1992
1993     case Qualifiers::OCL_Strong:
1994     case Qualifiers::OCL_Weak:
1995     case Qualifiers::OCL_Autoreleasing:
1996       return false;
1997
1998     case Qualifiers::OCL_None:
1999       break;
2000     }
2001   }
2002
2003   QualType CanonicalType = getTypePtr()->CanonicalType;
2004   switch (CanonicalType->getTypeClass()) {
2005     // Everything not explicitly mentioned is not POD.
2006   default: return false;
2007   case Type::VariableArray:
2008   case Type::ConstantArray:
2009     // IncompleteArray is handled above.
2010     return Context.getBaseElementType(*this).isCXX98PODType(Context);
2011
2012   case Type::ObjCObjectPointer:
2013   case Type::BlockPointer:
2014   case Type::Builtin:
2015   case Type::Complex:
2016   case Type::Pointer:
2017   case Type::MemberPointer:
2018   case Type::Vector:
2019   case Type::ExtVector:
2020     return true;
2021
2022   case Type::Enum:
2023     return true;
2024
2025   case Type::Record:
2026     if (CXXRecordDecl *ClassDecl
2027           = dyn_cast<CXXRecordDecl>(cast<RecordType>(CanonicalType)->getDecl()))
2028       return ClassDecl->isPOD();
2029
2030     // C struct/union is POD.
2031     return true;
2032   }
2033 }
2034
2035 bool QualType::isTrivialType(const ASTContext &Context) const {
2036   // The compiler shouldn't query this for incomplete types, but the user might.
2037   // We return false for that case. Except for incomplete arrays of PODs, which
2038   // are PODs according to the standard.
2039   if (isNull())
2040     return 0;
2041
2042   if ((*this)->isArrayType())
2043     return Context.getBaseElementType(*this).isTrivialType(Context);
2044
2045   // Return false for incomplete types after skipping any incomplete array
2046   // types which are expressly allowed by the standard and thus our API.
2047   if ((*this)->isIncompleteType())
2048     return false;
2049
2050   if (Context.getLangOpts().ObjCAutoRefCount) {
2051     switch (getObjCLifetime()) {
2052     case Qualifiers::OCL_ExplicitNone:
2053       return true;
2054
2055     case Qualifiers::OCL_Strong:
2056     case Qualifiers::OCL_Weak:
2057     case Qualifiers::OCL_Autoreleasing:
2058       return false;
2059
2060     case Qualifiers::OCL_None:
2061       if ((*this)->isObjCLifetimeType())
2062         return false;
2063       break;
2064     }
2065   }
2066
2067   QualType CanonicalType = getTypePtr()->CanonicalType;
2068   if (CanonicalType->isDependentType())
2069     return false;
2070
2071   // C++0x [basic.types]p9:
2072   //   Scalar types, trivial class types, arrays of such types, and
2073   //   cv-qualified versions of these types are collectively called trivial
2074   //   types.
2075
2076   // As an extension, Clang treats vector types as Scalar types.
2077   if (CanonicalType->isScalarType() || CanonicalType->isVectorType())
2078     return true;
2079   if (const RecordType *RT = CanonicalType->getAs<RecordType>()) {
2080     if (const CXXRecordDecl *ClassDecl =
2081         dyn_cast<CXXRecordDecl>(RT->getDecl())) {
2082       // C++11 [class]p6:
2083       //   A trivial class is a class that has a default constructor,
2084       //   has no non-trivial default constructors, and is trivially
2085       //   copyable.
2086       return ClassDecl->hasDefaultConstructor() &&
2087              !ClassDecl->hasNonTrivialDefaultConstructor() &&
2088              ClassDecl->isTriviallyCopyable();
2089     }
2090
2091     return true;
2092   }
2093
2094   // No other types can match.
2095   return false;
2096 }
2097
2098 bool QualType::isTriviallyCopyableType(const ASTContext &Context) const {
2099   if ((*this)->isArrayType())
2100     return Context.getBaseElementType(*this).isTriviallyCopyableType(Context);
2101
2102   if (Context.getLangOpts().ObjCAutoRefCount) {
2103     switch (getObjCLifetime()) {
2104     case Qualifiers::OCL_ExplicitNone:
2105       return true;
2106
2107     case Qualifiers::OCL_Strong:
2108     case Qualifiers::OCL_Weak:
2109     case Qualifiers::OCL_Autoreleasing:
2110       return false;
2111
2112     case Qualifiers::OCL_None:
2113       if ((*this)->isObjCLifetimeType())
2114         return false;
2115       break;
2116     }
2117   }
2118
2119   // C++11 [basic.types]p9
2120   //   Scalar types, trivially copyable class types, arrays of such types, and
2121   //   non-volatile const-qualified versions of these types are collectively
2122   //   called trivially copyable types.
2123
2124   QualType CanonicalType = getCanonicalType();
2125   if (CanonicalType->isDependentType())
2126     return false;
2127
2128   if (CanonicalType.isVolatileQualified())
2129     return false;
2130
2131   // Return false for incomplete types after skipping any incomplete array types
2132   // which are expressly allowed by the standard and thus our API.
2133   if (CanonicalType->isIncompleteType())
2134     return false;
2135
2136   // As an extension, Clang treats vector types as Scalar types.
2137   if (CanonicalType->isScalarType() || CanonicalType->isVectorType())
2138     return true;
2139
2140   if (const RecordType *RT = CanonicalType->getAs<RecordType>()) {
2141     if (const CXXRecordDecl *ClassDecl =
2142           dyn_cast<CXXRecordDecl>(RT->getDecl())) {
2143       if (!ClassDecl->isTriviallyCopyable()) return false;
2144     }
2145
2146     return true;
2147   }
2148
2149   // No other types can match.
2150   return false;
2151 }
2152
2153
2154
2155 bool Type::isLiteralType(const ASTContext &Ctx) const {
2156   if (isDependentType())
2157     return false;
2158
2159   // C++1y [basic.types]p10:
2160   //   A type is a literal type if it is:
2161   //   -- cv void; or
2162   if (Ctx.getLangOpts().CPlusPlus14 && isVoidType())
2163     return true;
2164
2165   // C++11 [basic.types]p10:
2166   //   A type is a literal type if it is:
2167   //   [...]
2168   //   -- an array of literal type other than an array of runtime bound; or
2169   if (isVariableArrayType())
2170     return false;
2171   const Type *BaseTy = getBaseElementTypeUnsafe();
2172   assert(BaseTy && "NULL element type");
2173
2174   // Return false for incomplete types after skipping any incomplete array
2175   // types; those are expressly allowed by the standard and thus our API.
2176   if (BaseTy->isIncompleteType())
2177     return false;
2178
2179   // C++11 [basic.types]p10:
2180   //   A type is a literal type if it is:
2181   //    -- a scalar type; or
2182   // As an extension, Clang treats vector types and complex types as
2183   // literal types.
2184   if (BaseTy->isScalarType() || BaseTy->isVectorType() ||
2185       BaseTy->isAnyComplexType())
2186     return true;
2187   //    -- a reference type; or
2188   if (BaseTy->isReferenceType())
2189     return true;
2190   //    -- a class type that has all of the following properties:
2191   if (const RecordType *RT = BaseTy->getAs<RecordType>()) {
2192     //    -- a trivial destructor,
2193     //    -- every constructor call and full-expression in the
2194     //       brace-or-equal-initializers for non-static data members (if any)
2195     //       is a constant expression,
2196     //    -- it is an aggregate type or has at least one constexpr
2197     //       constructor or constructor template that is not a copy or move
2198     //       constructor, and
2199     //    -- all non-static data members and base classes of literal types
2200     //
2201     // We resolve DR1361 by ignoring the second bullet.
2202     if (const CXXRecordDecl *ClassDecl =
2203         dyn_cast<CXXRecordDecl>(RT->getDecl()))
2204       return ClassDecl->isLiteral();
2205
2206     return true;
2207   }
2208
2209   // We treat _Atomic T as a literal type if T is a literal type.
2210   if (const AtomicType *AT = BaseTy->getAs<AtomicType>())
2211     return AT->getValueType()->isLiteralType(Ctx);
2212
2213   // If this type hasn't been deduced yet, then conservatively assume that
2214   // it'll work out to be a literal type.
2215   if (isa<AutoType>(BaseTy->getCanonicalTypeInternal()))
2216     return true;
2217
2218   return false;
2219 }
2220
2221 bool Type::isStandardLayoutType() const {
2222   if (isDependentType())
2223     return false;
2224
2225   // C++0x [basic.types]p9:
2226   //   Scalar types, standard-layout class types, arrays of such types, and
2227   //   cv-qualified versions of these types are collectively called
2228   //   standard-layout types.
2229   const Type *BaseTy = getBaseElementTypeUnsafe();
2230   assert(BaseTy && "NULL element type");
2231
2232   // Return false for incomplete types after skipping any incomplete array
2233   // types which are expressly allowed by the standard and thus our API.
2234   if (BaseTy->isIncompleteType())
2235     return false;
2236
2237   // As an extension, Clang treats vector types as Scalar types.
2238   if (BaseTy->isScalarType() || BaseTy->isVectorType()) return true;
2239   if (const RecordType *RT = BaseTy->getAs<RecordType>()) {
2240     if (const CXXRecordDecl *ClassDecl =
2241         dyn_cast<CXXRecordDecl>(RT->getDecl()))
2242       if (!ClassDecl->isStandardLayout())
2243         return false;
2244
2245     // Default to 'true' for non-C++ class types.
2246     // FIXME: This is a bit dubious, but plain C structs should trivially meet
2247     // all the requirements of standard layout classes.
2248     return true;
2249   }
2250
2251   // No other types can match.
2252   return false;
2253 }
2254
2255 // This is effectively the intersection of isTrivialType and
2256 // isStandardLayoutType. We implement it directly to avoid redundant
2257 // conversions from a type to a CXXRecordDecl.
2258 bool QualType::isCXX11PODType(const ASTContext &Context) const {
2259   const Type *ty = getTypePtr();
2260   if (ty->isDependentType())
2261     return false;
2262
2263   if (Context.getLangOpts().ObjCAutoRefCount) {
2264     switch (getObjCLifetime()) {
2265     case Qualifiers::OCL_ExplicitNone:
2266       return true;
2267
2268     case Qualifiers::OCL_Strong:
2269     case Qualifiers::OCL_Weak:
2270     case Qualifiers::OCL_Autoreleasing:
2271       return false;
2272
2273     case Qualifiers::OCL_None:
2274       break;
2275     }
2276   }
2277
2278   // C++11 [basic.types]p9:
2279   //   Scalar types, POD classes, arrays of such types, and cv-qualified
2280   //   versions of these types are collectively called trivial types.
2281   const Type *BaseTy = ty->getBaseElementTypeUnsafe();
2282   assert(BaseTy && "NULL element type");
2283
2284   // Return false for incomplete types after skipping any incomplete array
2285   // types which are expressly allowed by the standard and thus our API.
2286   if (BaseTy->isIncompleteType())
2287     return false;
2288
2289   // As an extension, Clang treats vector types as Scalar types.
2290   if (BaseTy->isScalarType() || BaseTy->isVectorType()) return true;
2291   if (const RecordType *RT = BaseTy->getAs<RecordType>()) {
2292     if (const CXXRecordDecl *ClassDecl =
2293         dyn_cast<CXXRecordDecl>(RT->getDecl())) {
2294       // C++11 [class]p10:
2295       //   A POD struct is a non-union class that is both a trivial class [...]
2296       if (!ClassDecl->isTrivial()) return false;
2297
2298       // C++11 [class]p10:
2299       //   A POD struct is a non-union class that is both a trivial class and
2300       //   a standard-layout class [...]
2301       if (!ClassDecl->isStandardLayout()) return false;
2302
2303       // C++11 [class]p10:
2304       //   A POD struct is a non-union class that is both a trivial class and
2305       //   a standard-layout class, and has no non-static data members of type
2306       //   non-POD struct, non-POD union (or array of such types). [...]
2307       //
2308       // We don't directly query the recursive aspect as the requirements for
2309       // both standard-layout classes and trivial classes apply recursively
2310       // already.
2311     }
2312
2313     return true;
2314   }
2315
2316   // No other types can match.
2317   return false;
2318 }
2319
2320 bool Type::isPromotableIntegerType() const {
2321   if (const BuiltinType *BT = getAs<BuiltinType>())
2322     switch (BT->getKind()) {
2323     case BuiltinType::Bool:
2324     case BuiltinType::Char_S:
2325     case BuiltinType::Char_U:
2326     case BuiltinType::SChar:
2327     case BuiltinType::UChar:
2328     case BuiltinType::Short:
2329     case BuiltinType::UShort:
2330     case BuiltinType::WChar_S:
2331     case BuiltinType::WChar_U:
2332     case BuiltinType::Char16:
2333     case BuiltinType::Char32:
2334       return true;
2335     default:
2336       return false;
2337     }
2338
2339   // Enumerated types are promotable to their compatible integer types
2340   // (C99 6.3.1.1) a.k.a. its underlying type (C++ [conv.prom]p2).
2341   if (const EnumType *ET = getAs<EnumType>()){
2342     if (this->isDependentType() || ET->getDecl()->getPromotionType().isNull()
2343         || ET->getDecl()->isScoped())
2344       return false;
2345
2346     return true;
2347   }
2348
2349   return false;
2350 }
2351
2352 bool Type::isSpecifierType() const {
2353   // Note that this intentionally does not use the canonical type.
2354   switch (getTypeClass()) {
2355   case Builtin:
2356   case Record:
2357   case Enum:
2358   case Typedef:
2359   case Complex:
2360   case TypeOfExpr:
2361   case TypeOf:
2362   case TemplateTypeParm:
2363   case SubstTemplateTypeParm:
2364   case TemplateSpecialization:
2365   case Elaborated:
2366   case DependentName:
2367   case DependentTemplateSpecialization:
2368   case ObjCInterface:
2369   case ObjCObject:
2370   case ObjCObjectPointer: // FIXME: object pointers aren't really specifiers
2371     return true;
2372   default:
2373     return false;
2374   }
2375 }
2376
2377 ElaboratedTypeKeyword
2378 TypeWithKeyword::getKeywordForTypeSpec(unsigned TypeSpec) {
2379   switch (TypeSpec) {
2380   default: return ETK_None;
2381   case TST_typename: return ETK_Typename;
2382   case TST_class: return ETK_Class;
2383   case TST_struct: return ETK_Struct;
2384   case TST_interface: return ETK_Interface;
2385   case TST_union: return ETK_Union;
2386   case TST_enum: return ETK_Enum;
2387   }
2388 }
2389
2390 TagTypeKind
2391 TypeWithKeyword::getTagTypeKindForTypeSpec(unsigned TypeSpec) {
2392   switch(TypeSpec) {
2393   case TST_class: return TTK_Class;
2394   case TST_struct: return TTK_Struct;
2395   case TST_interface: return TTK_Interface;
2396   case TST_union: return TTK_Union;
2397   case TST_enum: return TTK_Enum;
2398   }
2399
2400   llvm_unreachable("Type specifier is not a tag type kind.");
2401 }
2402
2403 ElaboratedTypeKeyword
2404 TypeWithKeyword::getKeywordForTagTypeKind(TagTypeKind Kind) {
2405   switch (Kind) {
2406   case TTK_Class: return ETK_Class;
2407   case TTK_Struct: return ETK_Struct;
2408   case TTK_Interface: return ETK_Interface;
2409   case TTK_Union: return ETK_Union;
2410   case TTK_Enum: return ETK_Enum;
2411   }
2412   llvm_unreachable("Unknown tag type kind.");
2413 }
2414
2415 TagTypeKind
2416 TypeWithKeyword::getTagTypeKindForKeyword(ElaboratedTypeKeyword Keyword) {
2417   switch (Keyword) {
2418   case ETK_Class: return TTK_Class;
2419   case ETK_Struct: return TTK_Struct;
2420   case ETK_Interface: return TTK_Interface;
2421   case ETK_Union: return TTK_Union;
2422   case ETK_Enum: return TTK_Enum;
2423   case ETK_None: // Fall through.
2424   case ETK_Typename:
2425     llvm_unreachable("Elaborated type keyword is not a tag type kind.");
2426   }
2427   llvm_unreachable("Unknown elaborated type keyword.");
2428 }
2429
2430 bool
2431 TypeWithKeyword::KeywordIsTagTypeKind(ElaboratedTypeKeyword Keyword) {
2432   switch (Keyword) {
2433   case ETK_None:
2434   case ETK_Typename:
2435     return false;
2436   case ETK_Class:
2437   case ETK_Struct:
2438   case ETK_Interface:
2439   case ETK_Union:
2440   case ETK_Enum:
2441     return true;
2442   }
2443   llvm_unreachable("Unknown elaborated type keyword.");
2444 }
2445
2446 StringRef TypeWithKeyword::getKeywordName(ElaboratedTypeKeyword Keyword) {
2447   switch (Keyword) {
2448   case ETK_None: return "";
2449   case ETK_Typename: return "typename";
2450   case ETK_Class:  return "class";
2451   case ETK_Struct: return "struct";
2452   case ETK_Interface: return "__interface";
2453   case ETK_Union:  return "union";
2454   case ETK_Enum:   return "enum";
2455   }
2456
2457   llvm_unreachable("Unknown elaborated type keyword.");
2458 }
2459
2460 DependentTemplateSpecializationType::DependentTemplateSpecializationType(
2461                          ElaboratedTypeKeyword Keyword,
2462                          NestedNameSpecifier *NNS, const IdentifierInfo *Name,
2463                          ArrayRef<TemplateArgument> Args,
2464                          QualType Canon)
2465   : TypeWithKeyword(Keyword, DependentTemplateSpecialization, Canon, true, true,
2466                     /*VariablyModified=*/false,
2467                     NNS && NNS->containsUnexpandedParameterPack()),
2468     NNS(NNS), Name(Name), NumArgs(Args.size()) {
2469   assert((!NNS || NNS->isDependent()) &&
2470          "DependentTemplateSpecializatonType requires dependent qualifier");
2471   TemplateArgument *ArgBuffer = getArgBuffer();
2472   for (const TemplateArgument &Arg : Args) {
2473     if (Arg.containsUnexpandedParameterPack())
2474       setContainsUnexpandedParameterPack();
2475
2476     new (ArgBuffer++) TemplateArgument(Arg);
2477   }
2478 }
2479
2480 void
2481 DependentTemplateSpecializationType::Profile(llvm::FoldingSetNodeID &ID,
2482                                              const ASTContext &Context,
2483                                              ElaboratedTypeKeyword Keyword,
2484                                              NestedNameSpecifier *Qualifier,
2485                                              const IdentifierInfo *Name,
2486                                              ArrayRef<TemplateArgument> Args) {
2487   ID.AddInteger(Keyword);
2488   ID.AddPointer(Qualifier);
2489   ID.AddPointer(Name);
2490   for (const TemplateArgument &Arg : Args)
2491     Arg.Profile(ID, Context);
2492 }
2493
2494 bool Type::isElaboratedTypeSpecifier() const {
2495   ElaboratedTypeKeyword Keyword;
2496   if (const ElaboratedType *Elab = dyn_cast<ElaboratedType>(this))
2497     Keyword = Elab->getKeyword();
2498   else if (const DependentNameType *DepName = dyn_cast<DependentNameType>(this))
2499     Keyword = DepName->getKeyword();
2500   else if (const DependentTemplateSpecializationType *DepTST =
2501              dyn_cast<DependentTemplateSpecializationType>(this))
2502     Keyword = DepTST->getKeyword();
2503   else
2504     return false;
2505
2506   return TypeWithKeyword::KeywordIsTagTypeKind(Keyword);
2507 }
2508
2509 const char *Type::getTypeClassName() const {
2510   switch (TypeBits.TC) {
2511 #define ABSTRACT_TYPE(Derived, Base)
2512 #define TYPE(Derived, Base) case Derived: return #Derived;
2513 #include "clang/AST/TypeNodes.def"
2514   }
2515
2516   llvm_unreachable("Invalid type class.");
2517 }
2518
2519 StringRef BuiltinType::getName(const PrintingPolicy &Policy) const {
2520   switch (getKind()) {
2521   case Void:
2522     return "void";
2523   case Bool:
2524     return Policy.Bool ? "bool" : "_Bool";
2525   case Char_S:
2526     return "char";
2527   case Char_U:
2528     return "char";
2529   case SChar:
2530     return "signed char";
2531   case Short:
2532     return "short";
2533   case Int:
2534     return "int";
2535   case Long:
2536     return "long";
2537   case LongLong:
2538     return "long long";
2539   case Int128:
2540     return "__int128";
2541   case UChar:
2542     return "unsigned char";
2543   case UShort:
2544     return "unsigned short";
2545   case UInt:
2546     return "unsigned int";
2547   case ULong:
2548     return "unsigned long";
2549   case ULongLong:
2550     return "unsigned long long";
2551   case UInt128:
2552     return "unsigned __int128";
2553   case Half:
2554     return Policy.Half ? "half" : "__fp16";
2555   case Float:
2556     return "float";
2557   case Double:
2558     return "double";
2559   case LongDouble:
2560     return "long double";
2561   case Float128:
2562     return "__float128";
2563   case WChar_S:
2564   case WChar_U:
2565     return Policy.MSWChar ? "__wchar_t" : "wchar_t";
2566   case Char16:
2567     return "char16_t";
2568   case Char32:
2569     return "char32_t";
2570   case NullPtr:
2571     return "nullptr_t";
2572   case Overload:
2573     return "<overloaded function type>";
2574   case BoundMember:
2575     return "<bound member function type>";
2576   case PseudoObject:
2577     return "<pseudo-object type>";
2578   case Dependent:
2579     return "<dependent type>";
2580   case UnknownAny:
2581     return "<unknown type>";
2582   case ARCUnbridgedCast:
2583     return "<ARC unbridged cast type>";
2584   case BuiltinFn:
2585     return "<builtin fn type>";
2586   case ObjCId:
2587     return "id";
2588   case ObjCClass:
2589     return "Class";
2590   case ObjCSel:
2591     return "SEL";
2592 #define IMAGE_TYPE(ImgType, Id, SingletonId, Access, Suffix) \
2593   case Id: \
2594     return "__" #Access " " #ImgType "_t";
2595 #include "clang/Basic/OpenCLImageTypes.def"
2596   case OCLSampler:
2597     return "sampler_t";
2598   case OCLEvent:
2599     return "event_t";
2600   case OCLClkEvent:
2601     return "clk_event_t";
2602   case OCLQueue:
2603     return "queue_t";
2604   case OCLNDRange:
2605     return "ndrange_t";
2606   case OCLReserveID:
2607     return "reserve_id_t";
2608   case OMPArraySection:
2609     return "<OpenMP array section type>";
2610   }
2611
2612   llvm_unreachable("Invalid builtin type.");
2613 }
2614
2615 QualType QualType::getNonLValueExprType(const ASTContext &Context) const {
2616   if (const ReferenceType *RefType = getTypePtr()->getAs<ReferenceType>())
2617     return RefType->getPointeeType();
2618
2619   // C++0x [basic.lval]:
2620   //   Class prvalues can have cv-qualified types; non-class prvalues always
2621   //   have cv-unqualified types.
2622   //
2623   // See also C99 6.3.2.1p2.
2624   if (!Context.getLangOpts().CPlusPlus ||
2625       (!getTypePtr()->isDependentType() && !getTypePtr()->isRecordType()))
2626     return getUnqualifiedType();
2627
2628   return *this;
2629 }
2630
2631 StringRef FunctionType::getNameForCallConv(CallingConv CC) {
2632   switch (CC) {
2633   case CC_C: return "cdecl";
2634   case CC_X86StdCall: return "stdcall";
2635   case CC_X86FastCall: return "fastcall";
2636   case CC_X86ThisCall: return "thiscall";
2637   case CC_X86Pascal: return "pascal";
2638   case CC_X86VectorCall: return "vectorcall";
2639   case CC_X86_64Win64: return "ms_abi";
2640   case CC_X86_64SysV: return "sysv_abi";
2641   case CC_AAPCS: return "aapcs";
2642   case CC_AAPCS_VFP: return "aapcs-vfp";
2643   case CC_IntelOclBicc: return "intel_ocl_bicc";
2644   case CC_SpirFunction: return "spir_function";
2645   case CC_OpenCLKernel: return "opencl_kernel";
2646   case CC_Swift: return "swiftcall";
2647   case CC_PreserveMost: return "preserve_most";
2648   case CC_PreserveAll: return "preserve_all";
2649   }
2650
2651   llvm_unreachable("Invalid calling convention.");
2652 }
2653
2654 FunctionProtoType::FunctionProtoType(QualType result, ArrayRef<QualType> params,
2655                                      QualType canonical,
2656                                      const ExtProtoInfo &epi)
2657     : FunctionType(FunctionProto, result, canonical,
2658                    result->isDependentType(),
2659                    result->isInstantiationDependentType(),
2660                    result->isVariablyModifiedType(),
2661                    result->containsUnexpandedParameterPack(), epi.ExtInfo),
2662       NumParams(params.size()),
2663       NumExceptions(epi.ExceptionSpec.Exceptions.size()),
2664       ExceptionSpecType(epi.ExceptionSpec.Type),
2665       HasExtParameterInfos(epi.ExtParameterInfos != nullptr),
2666       Variadic(epi.Variadic), HasTrailingReturn(epi.HasTrailingReturn) {
2667   assert(NumParams == params.size() && "function has too many parameters");
2668
2669   FunctionTypeBits.TypeQuals = epi.TypeQuals;
2670   FunctionTypeBits.RefQualifier = epi.RefQualifier;
2671
2672   // Fill in the trailing argument array.
2673   QualType *argSlot = reinterpret_cast<QualType*>(this+1);
2674   for (unsigned i = 0; i != NumParams; ++i) {
2675     if (params[i]->isDependentType())
2676       setDependent();
2677     else if (params[i]->isInstantiationDependentType())
2678       setInstantiationDependent();
2679
2680     if (params[i]->containsUnexpandedParameterPack())
2681       setContainsUnexpandedParameterPack();
2682
2683     argSlot[i] = params[i];
2684   }
2685
2686   if (getExceptionSpecType() == EST_Dynamic) {
2687     // Fill in the exception array.
2688     QualType *exnSlot = argSlot + NumParams;
2689     unsigned I = 0;
2690     for (QualType ExceptionType : epi.ExceptionSpec.Exceptions) {
2691       // Note that a dependent exception specification does *not* make
2692       // a type dependent; it's not even part of the C++ type system.
2693       if (ExceptionType->isInstantiationDependentType())
2694         setInstantiationDependent();
2695
2696       if (ExceptionType->containsUnexpandedParameterPack())
2697         setContainsUnexpandedParameterPack();
2698
2699       exnSlot[I++] = ExceptionType;
2700     }
2701   } else if (getExceptionSpecType() == EST_ComputedNoexcept) {
2702     // Store the noexcept expression and context.
2703     Expr **noexSlot = reinterpret_cast<Expr **>(argSlot + NumParams);
2704     *noexSlot = epi.ExceptionSpec.NoexceptExpr;
2705
2706     if (epi.ExceptionSpec.NoexceptExpr) {
2707       if (epi.ExceptionSpec.NoexceptExpr->isValueDependent() ||
2708           epi.ExceptionSpec.NoexceptExpr->isInstantiationDependent())
2709         setInstantiationDependent();
2710
2711       if (epi.ExceptionSpec.NoexceptExpr->containsUnexpandedParameterPack())
2712         setContainsUnexpandedParameterPack();
2713     }
2714   } else if (getExceptionSpecType() == EST_Uninstantiated) {
2715     // Store the function decl from which we will resolve our
2716     // exception specification.
2717     FunctionDecl **slot =
2718         reinterpret_cast<FunctionDecl **>(argSlot + NumParams);
2719     slot[0] = epi.ExceptionSpec.SourceDecl;
2720     slot[1] = epi.ExceptionSpec.SourceTemplate;
2721     // This exception specification doesn't make the type dependent, because
2722     // it's not instantiated as part of instantiating the type.
2723   } else if (getExceptionSpecType() == EST_Unevaluated) {
2724     // Store the function decl from which we will resolve our
2725     // exception specification.
2726     FunctionDecl **slot =
2727         reinterpret_cast<FunctionDecl **>(argSlot + NumParams);
2728     slot[0] = epi.ExceptionSpec.SourceDecl;
2729   }
2730
2731   if (epi.ExtParameterInfos) {
2732     ExtParameterInfo *extParamInfos =
2733       const_cast<ExtParameterInfo *>(getExtParameterInfosBuffer());
2734     for (unsigned i = 0; i != NumParams; ++i)
2735       extParamInfos[i] = epi.ExtParameterInfos[i];
2736   }
2737 }
2738
2739 bool FunctionProtoType::hasDependentExceptionSpec() const {
2740   if (Expr *NE = getNoexceptExpr())
2741     return NE->isValueDependent();
2742   for (QualType ET : exceptions())
2743     // A pack expansion with a non-dependent pattern is still dependent,
2744     // because we don't know whether the pattern is in the exception spec
2745     // or not (that depends on whether the pack has 0 expansions).
2746     if (ET->isDependentType() || ET->getAs<PackExpansionType>())
2747       return true;
2748   return false;
2749 }
2750
2751 FunctionProtoType::NoexceptResult
2752 FunctionProtoType::getNoexceptSpec(const ASTContext &ctx) const {
2753   ExceptionSpecificationType est = getExceptionSpecType();
2754   if (est == EST_BasicNoexcept)
2755     return NR_Nothrow;
2756
2757   if (est != EST_ComputedNoexcept)
2758     return NR_NoNoexcept;
2759
2760   Expr *noexceptExpr = getNoexceptExpr();
2761   if (!noexceptExpr)
2762     return NR_BadNoexcept;
2763   if (noexceptExpr->isValueDependent())
2764     return NR_Dependent;
2765
2766   llvm::APSInt value;
2767   bool isICE = noexceptExpr->isIntegerConstantExpr(value, ctx, nullptr,
2768                                                    /*evaluated*/false);
2769   (void)isICE;
2770   assert(isICE && "AST should not contain bad noexcept expressions.");
2771
2772   return value.getBoolValue() ? NR_Nothrow : NR_Throw;
2773 }
2774
2775 bool FunctionProtoType::isNothrow(const ASTContext &Ctx,
2776                                   bool ResultIfDependent) const {
2777   ExceptionSpecificationType EST = getExceptionSpecType();
2778   assert(EST != EST_Unevaluated && EST != EST_Uninstantiated);
2779   if (EST == EST_DynamicNone || EST == EST_BasicNoexcept)
2780     return true;
2781
2782   if (EST == EST_Dynamic && ResultIfDependent) {
2783     // A dynamic exception specification is throwing unless every exception
2784     // type is an (unexpanded) pack expansion type.
2785     for (unsigned I = 0, N = NumExceptions; I != N; ++I)
2786       if (!getExceptionType(I)->getAs<PackExpansionType>())
2787         return false;
2788     return ResultIfDependent;
2789   }
2790
2791   if (EST != EST_ComputedNoexcept)
2792     return false;
2793
2794   NoexceptResult NR = getNoexceptSpec(Ctx);
2795   if (NR == NR_Dependent)
2796     return ResultIfDependent;
2797   return NR == NR_Nothrow;
2798 }
2799
2800 bool FunctionProtoType::isTemplateVariadic() const {
2801   for (unsigned ArgIdx = getNumParams(); ArgIdx; --ArgIdx)
2802     if (isa<PackExpansionType>(getParamType(ArgIdx - 1)))
2803       return true;
2804
2805   return false;
2806 }
2807
2808 void FunctionProtoType::Profile(llvm::FoldingSetNodeID &ID, QualType Result,
2809                                 const QualType *ArgTys, unsigned NumParams,
2810                                 const ExtProtoInfo &epi,
2811                                 const ASTContext &Context) {
2812
2813   // We have to be careful not to get ambiguous profile encodings.
2814   // Note that valid type pointers are never ambiguous with anything else.
2815   //
2816   // The encoding grammar begins:
2817   //      type type* bool int bool
2818   // If that final bool is true, then there is a section for the EH spec:
2819   //      bool type*
2820   // This is followed by an optional "consumed argument" section of the
2821   // same length as the first type sequence:
2822   //      bool*
2823   // Finally, we have the ext info and trailing return type flag:
2824   //      int bool
2825   //
2826   // There is no ambiguity between the consumed arguments and an empty EH
2827   // spec because of the leading 'bool' which unambiguously indicates
2828   // whether the following bool is the EH spec or part of the arguments.
2829
2830   ID.AddPointer(Result.getAsOpaquePtr());
2831   for (unsigned i = 0; i != NumParams; ++i)
2832     ID.AddPointer(ArgTys[i].getAsOpaquePtr());
2833   // This method is relatively performance sensitive, so as a performance
2834   // shortcut, use one AddInteger call instead of four for the next four
2835   // fields.
2836   assert(!(unsigned(epi.Variadic) & ~1) &&
2837          !(unsigned(epi.TypeQuals) & ~255) &&
2838          !(unsigned(epi.RefQualifier) & ~3) &&
2839          !(unsigned(epi.ExceptionSpec.Type) & ~15) &&
2840          "Values larger than expected.");
2841   ID.AddInteger(unsigned(epi.Variadic) +
2842                 (epi.TypeQuals << 1) +
2843                 (epi.RefQualifier << 9) +
2844                 (epi.ExceptionSpec.Type << 11));
2845   if (epi.ExceptionSpec.Type == EST_Dynamic) {
2846     for (QualType Ex : epi.ExceptionSpec.Exceptions)
2847       ID.AddPointer(Ex.getAsOpaquePtr());
2848   } else if (epi.ExceptionSpec.Type == EST_ComputedNoexcept &&
2849              epi.ExceptionSpec.NoexceptExpr) {
2850     epi.ExceptionSpec.NoexceptExpr->Profile(ID, Context, false);
2851   } else if (epi.ExceptionSpec.Type == EST_Uninstantiated ||
2852              epi.ExceptionSpec.Type == EST_Unevaluated) {
2853     ID.AddPointer(epi.ExceptionSpec.SourceDecl->getCanonicalDecl());
2854   }
2855   if (epi.ExtParameterInfos) {
2856     for (unsigned i = 0; i != NumParams; ++i)
2857       ID.AddInteger(epi.ExtParameterInfos[i].getOpaqueValue());
2858   }
2859   epi.ExtInfo.Profile(ID);
2860   ID.AddBoolean(epi.HasTrailingReturn);
2861 }
2862
2863 void FunctionProtoType::Profile(llvm::FoldingSetNodeID &ID,
2864                                 const ASTContext &Ctx) {
2865   Profile(ID, getReturnType(), param_type_begin(), NumParams, getExtProtoInfo(),
2866           Ctx);
2867 }
2868
2869 QualType TypedefType::desugar() const {
2870   return getDecl()->getUnderlyingType();
2871 }
2872
2873 TypeOfExprType::TypeOfExprType(Expr *E, QualType can)
2874   : Type(TypeOfExpr, can, E->isTypeDependent(),
2875          E->isInstantiationDependent(),
2876          E->getType()->isVariablyModifiedType(),
2877          E->containsUnexpandedParameterPack()),
2878     TOExpr(E) {
2879 }
2880
2881 bool TypeOfExprType::isSugared() const {
2882   return !TOExpr->isTypeDependent();
2883 }
2884
2885 QualType TypeOfExprType::desugar() const {
2886   if (isSugared())
2887     return getUnderlyingExpr()->getType();
2888
2889   return QualType(this, 0);
2890 }
2891
2892 void DependentTypeOfExprType::Profile(llvm::FoldingSetNodeID &ID,
2893                                       const ASTContext &Context, Expr *E) {
2894   E->Profile(ID, Context, true);
2895 }
2896
2897 DecltypeType::DecltypeType(Expr *E, QualType underlyingType, QualType can)
2898   // C++11 [temp.type]p2: "If an expression e involves a template parameter,
2899   // decltype(e) denotes a unique dependent type." Hence a decltype type is
2900   // type-dependent even if its expression is only instantiation-dependent.
2901   : Type(Decltype, can, E->isInstantiationDependent(),
2902          E->isInstantiationDependent(),
2903          E->getType()->isVariablyModifiedType(),
2904          E->containsUnexpandedParameterPack()),
2905     E(E),
2906   UnderlyingType(underlyingType) {
2907 }
2908
2909 bool DecltypeType::isSugared() const { return !E->isInstantiationDependent(); }
2910
2911 QualType DecltypeType::desugar() const {
2912   if (isSugared())
2913     return getUnderlyingType();
2914
2915   return QualType(this, 0);
2916 }
2917
2918 DependentDecltypeType::DependentDecltypeType(const ASTContext &Context, Expr *E)
2919   : DecltypeType(E, Context.DependentTy), Context(Context) { }
2920
2921 void DependentDecltypeType::Profile(llvm::FoldingSetNodeID &ID,
2922                                     const ASTContext &Context, Expr *E) {
2923   E->Profile(ID, Context, true);
2924 }
2925
2926 UnaryTransformType::UnaryTransformType(QualType BaseType,
2927                                        QualType UnderlyingType,
2928                                        UTTKind UKind,
2929                                        QualType CanonicalType)
2930   : Type(UnaryTransform, CanonicalType, BaseType->isDependentType(),
2931          BaseType->isInstantiationDependentType(),
2932          BaseType->isVariablyModifiedType(),
2933          BaseType->containsUnexpandedParameterPack())
2934   , BaseType(BaseType), UnderlyingType(UnderlyingType), UKind(UKind)
2935 {}
2936
2937 DependentUnaryTransformType::DependentUnaryTransformType(const ASTContext &C,
2938                                                          QualType BaseType,
2939                                                          UTTKind UKind)
2940    : UnaryTransformType(BaseType, C.DependentTy, UKind, QualType())
2941 {}
2942
2943
2944 TagType::TagType(TypeClass TC, const TagDecl *D, QualType can)
2945   : Type(TC, can, D->isDependentType(),
2946          /*InstantiationDependent=*/D->isDependentType(),
2947          /*VariablyModified=*/false,
2948          /*ContainsUnexpandedParameterPack=*/false),
2949     decl(const_cast<TagDecl*>(D)) {}
2950
2951 static TagDecl *getInterestingTagDecl(TagDecl *decl) {
2952   for (auto I : decl->redecls()) {
2953     if (I->isCompleteDefinition() || I->isBeingDefined())
2954       return I;
2955   }
2956   // If there's no definition (not even in progress), return what we have.
2957   return decl;
2958 }
2959
2960 TagDecl *TagType::getDecl() const {
2961   return getInterestingTagDecl(decl);
2962 }
2963
2964 bool TagType::isBeingDefined() const {
2965   return getDecl()->isBeingDefined();
2966 }
2967
2968 bool AttributedType::isQualifier() const {
2969   switch (getAttrKind()) {
2970   // These are type qualifiers in the traditional C sense: they annotate
2971   // something about a specific value/variable of a type.  (They aren't
2972   // always part of the canonical type, though.)
2973   case AttributedType::attr_address_space:
2974   case AttributedType::attr_objc_gc:
2975   case AttributedType::attr_objc_ownership:
2976   case AttributedType::attr_objc_inert_unsafe_unretained:
2977   case AttributedType::attr_nonnull:
2978   case AttributedType::attr_nullable:
2979   case AttributedType::attr_null_unspecified:
2980     return true;
2981
2982   // These aren't qualifiers; they rewrite the modified type to be a
2983   // semantically different type.
2984   case AttributedType::attr_regparm:
2985   case AttributedType::attr_vector_size:
2986   case AttributedType::attr_neon_vector_type:
2987   case AttributedType::attr_neon_polyvector_type:
2988   case AttributedType::attr_pcs:
2989   case AttributedType::attr_pcs_vfp:
2990   case AttributedType::attr_noreturn:
2991   case AttributedType::attr_cdecl:
2992   case AttributedType::attr_fastcall:
2993   case AttributedType::attr_stdcall:
2994   case AttributedType::attr_thiscall:
2995   case AttributedType::attr_pascal:
2996   case AttributedType::attr_swiftcall:
2997   case AttributedType::attr_vectorcall:
2998   case AttributedType::attr_inteloclbicc:
2999   case AttributedType::attr_preserve_most:
3000   case AttributedType::attr_preserve_all:
3001   case AttributedType::attr_ms_abi:
3002   case AttributedType::attr_sysv_abi:
3003   case AttributedType::attr_ptr32:
3004   case AttributedType::attr_ptr64:
3005   case AttributedType::attr_sptr:
3006   case AttributedType::attr_uptr:
3007   case AttributedType::attr_objc_kindof:
3008     return false;
3009   }
3010   llvm_unreachable("bad attributed type kind");
3011 }
3012
3013 bool AttributedType::isMSTypeSpec() const {
3014   switch (getAttrKind()) {
3015   default:  return false;
3016   case attr_ptr32:
3017   case attr_ptr64:
3018   case attr_sptr:
3019   case attr_uptr:
3020     return true;
3021   }
3022   llvm_unreachable("invalid attr kind");
3023 }
3024
3025 bool AttributedType::isCallingConv() const {
3026   switch (getAttrKind()) {
3027   case attr_ptr32:
3028   case attr_ptr64:
3029   case attr_sptr:
3030   case attr_uptr:
3031   case attr_address_space:
3032   case attr_regparm:
3033   case attr_vector_size:
3034   case attr_neon_vector_type:
3035   case attr_neon_polyvector_type:
3036   case attr_objc_gc:
3037   case attr_objc_ownership:
3038   case attr_objc_inert_unsafe_unretained:
3039   case attr_noreturn:
3040   case attr_nonnull:
3041   case attr_nullable:
3042   case attr_null_unspecified:
3043   case attr_objc_kindof:
3044     return false;
3045
3046   case attr_pcs:
3047   case attr_pcs_vfp:
3048   case attr_cdecl:
3049   case attr_fastcall:
3050   case attr_stdcall:
3051   case attr_thiscall:
3052   case attr_swiftcall:
3053   case attr_vectorcall:
3054   case attr_pascal:
3055   case attr_ms_abi:
3056   case attr_sysv_abi:
3057   case attr_inteloclbicc:
3058   case attr_preserve_most:
3059   case attr_preserve_all:
3060     return true;
3061   }
3062   llvm_unreachable("invalid attr kind");
3063 }
3064
3065 CXXRecordDecl *InjectedClassNameType::getDecl() const {
3066   return cast<CXXRecordDecl>(getInterestingTagDecl(Decl));
3067 }
3068
3069 IdentifierInfo *TemplateTypeParmType::getIdentifier() const {
3070   return isCanonicalUnqualified() ? nullptr : getDecl()->getIdentifier();
3071 }
3072
3073 SubstTemplateTypeParmPackType::
3074 SubstTemplateTypeParmPackType(const TemplateTypeParmType *Param,
3075                               QualType Canon,
3076                               const TemplateArgument &ArgPack)
3077   : Type(SubstTemplateTypeParmPack, Canon, true, true, false, true),
3078     Replaced(Param),
3079     Arguments(ArgPack.pack_begin()), NumArguments(ArgPack.pack_size())
3080 {
3081 }
3082
3083 TemplateArgument SubstTemplateTypeParmPackType::getArgumentPack() const {
3084   return TemplateArgument(llvm::makeArrayRef(Arguments, NumArguments));
3085 }
3086
3087 void SubstTemplateTypeParmPackType::Profile(llvm::FoldingSetNodeID &ID) {
3088   Profile(ID, getReplacedParameter(), getArgumentPack());
3089 }
3090
3091 void SubstTemplateTypeParmPackType::Profile(llvm::FoldingSetNodeID &ID,
3092                                            const TemplateTypeParmType *Replaced,
3093                                             const TemplateArgument &ArgPack) {
3094   ID.AddPointer(Replaced);
3095   ID.AddInteger(ArgPack.pack_size());
3096   for (const auto &P : ArgPack.pack_elements())
3097     ID.AddPointer(P.getAsType().getAsOpaquePtr());
3098 }
3099
3100 bool TemplateSpecializationType::
3101 anyDependentTemplateArguments(const TemplateArgumentListInfo &Args,
3102                               bool &InstantiationDependent) {
3103   return anyDependentTemplateArguments(Args.arguments(),
3104                                        InstantiationDependent);
3105 }
3106
3107 bool TemplateSpecializationType::
3108 anyDependentTemplateArguments(ArrayRef<TemplateArgumentLoc> Args,
3109                               bool &InstantiationDependent) {
3110   for (const TemplateArgumentLoc &ArgLoc : Args) {
3111     if (ArgLoc.getArgument().isDependent()) {
3112       InstantiationDependent = true;
3113       return true;
3114     }
3115
3116     if (ArgLoc.getArgument().isInstantiationDependent())
3117       InstantiationDependent = true;
3118   }
3119   return false;
3120 }
3121
3122 TemplateSpecializationType::
3123 TemplateSpecializationType(TemplateName T,
3124                            ArrayRef<TemplateArgument> Args,
3125                            QualType Canon, QualType AliasedType)
3126   : Type(TemplateSpecialization,
3127          Canon.isNull()? QualType(this, 0) : Canon,
3128          Canon.isNull()? true : Canon->isDependentType(),
3129          Canon.isNull()? true : Canon->isInstantiationDependentType(),
3130          false,
3131          T.containsUnexpandedParameterPack()),
3132     Template(T), NumArgs(Args.size()), TypeAlias(!AliasedType.isNull()) {
3133   assert(!T.getAsDependentTemplateName() &&
3134          "Use DependentTemplateSpecializationType for dependent template-name");
3135   assert((T.getKind() == TemplateName::Template ||
3136           T.getKind() == TemplateName::SubstTemplateTemplateParm ||
3137           T.getKind() == TemplateName::SubstTemplateTemplateParmPack) &&
3138          "Unexpected template name for TemplateSpecializationType");
3139
3140   TemplateArgument *TemplateArgs
3141     = reinterpret_cast<TemplateArgument *>(this + 1);
3142   for (const TemplateArgument &Arg : Args) {
3143     // Update instantiation-dependent and variably-modified bits.
3144     // If the canonical type exists and is non-dependent, the template
3145     // specialization type can be non-dependent even if one of the type
3146     // arguments is. Given:
3147     //   template<typename T> using U = int;
3148     // U<T> is always non-dependent, irrespective of the type T.
3149     // However, U<Ts> contains an unexpanded parameter pack, even though
3150     // its expansion (and thus its desugared type) doesn't.
3151     if (Arg.isInstantiationDependent())
3152       setInstantiationDependent();
3153     if (Arg.getKind() == TemplateArgument::Type &&
3154         Arg.getAsType()->isVariablyModifiedType())
3155       setVariablyModified();
3156     if (Arg.containsUnexpandedParameterPack())
3157       setContainsUnexpandedParameterPack();
3158     new (TemplateArgs++) TemplateArgument(Arg);
3159   }
3160
3161   // Store the aliased type if this is a type alias template specialization.
3162   if (TypeAlias) {
3163     TemplateArgument *Begin = reinterpret_cast<TemplateArgument *>(this + 1);
3164     *reinterpret_cast<QualType*>(Begin + getNumArgs()) = AliasedType;
3165   }
3166 }
3167
3168 void
3169 TemplateSpecializationType::Profile(llvm::FoldingSetNodeID &ID,
3170                                     TemplateName T,
3171                                     ArrayRef<TemplateArgument> Args,
3172                                     const ASTContext &Context) {
3173   T.Profile(ID);
3174   for (const TemplateArgument &Arg : Args)
3175     Arg.Profile(ID, Context);
3176 }
3177
3178 QualType
3179 QualifierCollector::apply(const ASTContext &Context, QualType QT) const {
3180   if (!hasNonFastQualifiers())
3181     return QT.withFastQualifiers(getFastQualifiers());
3182
3183   return Context.getQualifiedType(QT, *this);
3184 }
3185
3186 QualType
3187 QualifierCollector::apply(const ASTContext &Context, const Type *T) const {
3188   if (!hasNonFastQualifiers())
3189     return QualType(T, getFastQualifiers());
3190
3191   return Context.getQualifiedType(T, *this);
3192 }
3193
3194 void ObjCObjectTypeImpl::Profile(llvm::FoldingSetNodeID &ID,
3195                                  QualType BaseType,
3196                                  ArrayRef<QualType> typeArgs,
3197                                  ArrayRef<ObjCProtocolDecl *> protocols,
3198                                  bool isKindOf) {
3199   ID.AddPointer(BaseType.getAsOpaquePtr());
3200   ID.AddInteger(typeArgs.size());
3201   for (auto typeArg : typeArgs)
3202     ID.AddPointer(typeArg.getAsOpaquePtr());
3203   ID.AddInteger(protocols.size());
3204   for (auto proto : protocols)
3205     ID.AddPointer(proto);
3206   ID.AddBoolean(isKindOf);
3207 }
3208
3209 void ObjCObjectTypeImpl::Profile(llvm::FoldingSetNodeID &ID) {
3210   Profile(ID, getBaseType(), getTypeArgsAsWritten(),
3211           llvm::makeArrayRef(qual_begin(), getNumProtocols()),
3212           isKindOfTypeAsWritten());
3213 }
3214
3215 namespace {
3216
3217 /// \brief The cached properties of a type.
3218 class CachedProperties {
3219   Linkage L;
3220   bool local;
3221
3222 public:
3223   CachedProperties(Linkage L, bool local) : L(L), local(local) {}
3224
3225   Linkage getLinkage() const { return L; }
3226   bool hasLocalOrUnnamedType() const { return local; }
3227
3228   friend CachedProperties merge(CachedProperties L, CachedProperties R) {
3229     Linkage MergedLinkage = minLinkage(L.L, R.L);
3230     return CachedProperties(MergedLinkage,
3231                          L.hasLocalOrUnnamedType() | R.hasLocalOrUnnamedType());
3232   }
3233 };
3234 }
3235
3236 static CachedProperties computeCachedProperties(const Type *T);
3237
3238 namespace clang {
3239 /// The type-property cache.  This is templated so as to be
3240 /// instantiated at an internal type to prevent unnecessary symbol
3241 /// leakage.
3242 template <class Private> class TypePropertyCache {
3243 public:
3244   static CachedProperties get(QualType T) {
3245     return get(T.getTypePtr());
3246   }
3247
3248   static CachedProperties get(const Type *T) {
3249     ensure(T);
3250     return CachedProperties(T->TypeBits.getLinkage(),
3251                             T->TypeBits.hasLocalOrUnnamedType());
3252   }
3253
3254   static void ensure(const Type *T) {
3255     // If the cache is valid, we're okay.
3256     if (T->TypeBits.isCacheValid()) return;
3257
3258     // If this type is non-canonical, ask its canonical type for the
3259     // relevant information.
3260     if (!T->isCanonicalUnqualified()) {
3261       const Type *CT = T->getCanonicalTypeInternal().getTypePtr();
3262       ensure(CT);
3263       T->TypeBits.CacheValid = true;
3264       T->TypeBits.CachedLinkage = CT->TypeBits.CachedLinkage;
3265       T->TypeBits.CachedLocalOrUnnamed = CT->TypeBits.CachedLocalOrUnnamed;
3266       return;
3267     }
3268
3269     // Compute the cached properties and then set the cache.
3270     CachedProperties Result = computeCachedProperties(T);
3271     T->TypeBits.CacheValid = true;
3272     T->TypeBits.CachedLinkage = Result.getLinkage();
3273     T->TypeBits.CachedLocalOrUnnamed = Result.hasLocalOrUnnamedType();
3274   }
3275 };
3276 }
3277
3278 // Instantiate the friend template at a private class.  In a
3279 // reasonable implementation, these symbols will be internal.
3280 // It is terrible that this is the best way to accomplish this.
3281 namespace { class Private {}; }
3282 typedef TypePropertyCache<Private> Cache;
3283
3284 static CachedProperties computeCachedProperties(const Type *T) {
3285   switch (T->getTypeClass()) {
3286 #define TYPE(Class,Base)
3287 #define NON_CANONICAL_TYPE(Class,Base) case Type::Class:
3288 #include "clang/AST/TypeNodes.def"
3289     llvm_unreachable("didn't expect a non-canonical type here");
3290
3291 #define TYPE(Class,Base)
3292 #define DEPENDENT_TYPE(Class,Base) case Type::Class:
3293 #define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class,Base) case Type::Class:
3294 #include "clang/AST/TypeNodes.def"
3295     // Treat instantiation-dependent types as external.
3296     assert(T->isInstantiationDependentType());
3297     return CachedProperties(ExternalLinkage, false);
3298
3299   case Type::Auto:
3300     // Give non-deduced 'auto' types external linkage. We should only see them
3301     // here in error recovery.
3302     return CachedProperties(ExternalLinkage, false);
3303
3304   case Type::Builtin:
3305     // C++ [basic.link]p8:
3306     //   A type is said to have linkage if and only if:
3307     //     - it is a fundamental type (3.9.1); or
3308     return CachedProperties(ExternalLinkage, false);
3309
3310   case Type::Record:
3311   case Type::Enum: {
3312     const TagDecl *Tag = cast<TagType>(T)->getDecl();
3313
3314     // C++ [basic.link]p8:
3315     //     - it is a class or enumeration type that is named (or has a name
3316     //       for linkage purposes (7.1.3)) and the name has linkage; or
3317     //     -  it is a specialization of a class template (14); or
3318     Linkage L = Tag->getLinkageInternal();
3319     bool IsLocalOrUnnamed =
3320       Tag->getDeclContext()->isFunctionOrMethod() ||
3321       !Tag->hasNameForLinkage();
3322     return CachedProperties(L, IsLocalOrUnnamed);
3323   }
3324
3325     // C++ [basic.link]p8:
3326     //   - it is a compound type (3.9.2) other than a class or enumeration,
3327     //     compounded exclusively from types that have linkage; or
3328   case Type::Complex:
3329     return Cache::get(cast<ComplexType>(T)->getElementType());
3330   case Type::Pointer:
3331     return Cache::get(cast<PointerType>(T)->getPointeeType());
3332   case Type::BlockPointer:
3333     return Cache::get(cast<BlockPointerType>(T)->getPointeeType());
3334   case Type::LValueReference:
3335   case Type::RValueReference:
3336     return Cache::get(cast<ReferenceType>(T)->getPointeeType());
3337   case Type::MemberPointer: {
3338     const MemberPointerType *MPT = cast<MemberPointerType>(T);
3339     return merge(Cache::get(MPT->getClass()),
3340                  Cache::get(MPT->getPointeeType()));
3341   }
3342   case Type::ConstantArray:
3343   case Type::IncompleteArray:
3344   case Type::VariableArray:
3345     return Cache::get(cast<ArrayType>(T)->getElementType());
3346   case Type::Vector:
3347   case Type::ExtVector:
3348     return Cache::get(cast<VectorType>(T)->getElementType());
3349   case Type::FunctionNoProto:
3350     return Cache::get(cast<FunctionType>(T)->getReturnType());
3351   case Type::FunctionProto: {
3352     const FunctionProtoType *FPT = cast<FunctionProtoType>(T);
3353     CachedProperties result = Cache::get(FPT->getReturnType());
3354     for (const auto &ai : FPT->param_types())
3355       result = merge(result, Cache::get(ai));
3356     return result;
3357   }
3358   case Type::ObjCInterface: {
3359     Linkage L = cast<ObjCInterfaceType>(T)->getDecl()->getLinkageInternal();
3360     return CachedProperties(L, false);
3361   }
3362   case Type::ObjCObject:
3363     return Cache::get(cast<ObjCObjectType>(T)->getBaseType());
3364   case Type::ObjCObjectPointer:
3365     return Cache::get(cast<ObjCObjectPointerType>(T)->getPointeeType());
3366   case Type::Atomic:
3367     return Cache::get(cast<AtomicType>(T)->getValueType());
3368   case Type::Pipe:
3369     return Cache::get(cast<PipeType>(T)->getElementType());
3370   }
3371
3372   llvm_unreachable("unhandled type class");
3373 }
3374
3375 /// \brief Determine the linkage of this type.
3376 Linkage Type::getLinkage() const {
3377   Cache::ensure(this);
3378   return TypeBits.getLinkage();
3379 }
3380
3381 bool Type::hasUnnamedOrLocalType() const {
3382   Cache::ensure(this);
3383   return TypeBits.hasLocalOrUnnamedType();
3384 }
3385
3386 static LinkageInfo computeLinkageInfo(QualType T);
3387
3388 static LinkageInfo computeLinkageInfo(const Type *T) {
3389   switch (T->getTypeClass()) {
3390 #define TYPE(Class,Base)
3391 #define NON_CANONICAL_TYPE(Class,Base) case Type::Class:
3392 #include "clang/AST/TypeNodes.def"
3393     llvm_unreachable("didn't expect a non-canonical type here");
3394
3395 #define TYPE(Class,Base)
3396 #define DEPENDENT_TYPE(Class,Base) case Type::Class:
3397 #define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class,Base) case Type::Class:
3398 #include "clang/AST/TypeNodes.def"
3399     // Treat instantiation-dependent types as external.
3400     assert(T->isInstantiationDependentType());
3401     return LinkageInfo::external();
3402
3403   case Type::Builtin:
3404     return LinkageInfo::external();
3405
3406   case Type::Auto:
3407     return LinkageInfo::external();
3408
3409   case Type::Record:
3410   case Type::Enum:
3411     return cast<TagType>(T)->getDecl()->getLinkageAndVisibility();
3412
3413   case Type::Complex:
3414     return computeLinkageInfo(cast<ComplexType>(T)->getElementType());
3415   case Type::Pointer:
3416     return computeLinkageInfo(cast<PointerType>(T)->getPointeeType());
3417   case Type::BlockPointer:
3418     return computeLinkageInfo(cast<BlockPointerType>(T)->getPointeeType());
3419   case Type::LValueReference:
3420   case Type::RValueReference:
3421     return computeLinkageInfo(cast<ReferenceType>(T)->getPointeeType());
3422   case Type::MemberPointer: {
3423     const MemberPointerType *MPT = cast<MemberPointerType>(T);
3424     LinkageInfo LV = computeLinkageInfo(MPT->getClass());
3425     LV.merge(computeLinkageInfo(MPT->getPointeeType()));
3426     return LV;
3427   }
3428   case Type::ConstantArray:
3429   case Type::IncompleteArray:
3430   case Type::VariableArray:
3431     return computeLinkageInfo(cast<ArrayType>(T)->getElementType());
3432   case Type::Vector:
3433   case Type::ExtVector:
3434     return computeLinkageInfo(cast<VectorType>(T)->getElementType());
3435   case Type::FunctionNoProto:
3436     return computeLinkageInfo(cast<FunctionType>(T)->getReturnType());
3437   case Type::FunctionProto: {
3438     const FunctionProtoType *FPT = cast<FunctionProtoType>(T);
3439     LinkageInfo LV = computeLinkageInfo(FPT->getReturnType());
3440     for (const auto &ai : FPT->param_types())
3441       LV.merge(computeLinkageInfo(ai));
3442     return LV;
3443   }
3444   case Type::ObjCInterface:
3445     return cast<ObjCInterfaceType>(T)->getDecl()->getLinkageAndVisibility();
3446   case Type::ObjCObject:
3447     return computeLinkageInfo(cast<ObjCObjectType>(T)->getBaseType());
3448   case Type::ObjCObjectPointer:
3449     return computeLinkageInfo(cast<ObjCObjectPointerType>(T)->getPointeeType());
3450   case Type::Atomic:
3451     return computeLinkageInfo(cast<AtomicType>(T)->getValueType());
3452   case Type::Pipe:
3453     return computeLinkageInfo(cast<PipeType>(T)->getElementType());
3454   }
3455
3456   llvm_unreachable("unhandled type class");
3457 }
3458
3459 static LinkageInfo computeLinkageInfo(QualType T) {
3460   return computeLinkageInfo(T.getTypePtr());
3461 }
3462
3463 bool Type::isLinkageValid() const {
3464   if (!TypeBits.isCacheValid())
3465     return true;
3466
3467   return computeLinkageInfo(getCanonicalTypeInternal()).getLinkage() ==
3468     TypeBits.getLinkage();
3469 }
3470
3471 LinkageInfo Type::getLinkageAndVisibility() const {
3472   if (!isCanonicalUnqualified())
3473     return computeLinkageInfo(getCanonicalTypeInternal());
3474
3475   LinkageInfo LV = computeLinkageInfo(this);
3476   assert(LV.getLinkage() == getLinkage());
3477   return LV;
3478 }
3479
3480 Optional<NullabilityKind> Type::getNullability(const ASTContext &context) const {
3481   QualType type(this, 0);
3482   do {
3483     // Check whether this is an attributed type with nullability
3484     // information.
3485     if (auto attributed = dyn_cast<AttributedType>(type.getTypePtr())) {
3486       if (auto nullability = attributed->getImmediateNullability())
3487         return nullability;
3488     }
3489
3490     // Desugar the type. If desugaring does nothing, we're done.
3491     QualType desugared = type.getSingleStepDesugaredType(context);
3492     if (desugared.getTypePtr() == type.getTypePtr())
3493       return None;
3494
3495     type = desugared;
3496   } while (true);
3497 }
3498
3499 bool Type::canHaveNullability() const {
3500   QualType type = getCanonicalTypeInternal();
3501
3502   switch (type->getTypeClass()) {
3503   // We'll only see canonical types here.
3504 #define NON_CANONICAL_TYPE(Class, Parent)       \
3505   case Type::Class:                             \
3506     llvm_unreachable("non-canonical type");
3507 #define TYPE(Class, Parent)
3508 #include "clang/AST/TypeNodes.def"
3509
3510   // Pointer types.
3511   case Type::Pointer:
3512   case Type::BlockPointer:
3513   case Type::MemberPointer:
3514   case Type::ObjCObjectPointer:
3515     return true;
3516
3517   // Dependent types that could instantiate to pointer types.
3518   case Type::UnresolvedUsing:
3519   case Type::TypeOfExpr:
3520   case Type::TypeOf:
3521   case Type::Decltype:
3522   case Type::UnaryTransform:
3523   case Type::TemplateTypeParm:
3524   case Type::SubstTemplateTypeParmPack:
3525   case Type::DependentName:
3526   case Type::DependentTemplateSpecialization:
3527     return true;
3528
3529   // Dependent template specializations can instantiate to pointer
3530   // types unless they're known to be specializations of a class
3531   // template.
3532   case Type::TemplateSpecialization:
3533     if (TemplateDecl *templateDecl
3534           = cast<TemplateSpecializationType>(type.getTypePtr())
3535               ->getTemplateName().getAsTemplateDecl()) {
3536       if (isa<ClassTemplateDecl>(templateDecl))
3537         return false;
3538     }
3539     return true;
3540
3541   // auto is considered dependent when it isn't deduced.
3542   case Type::Auto:
3543     return !cast<AutoType>(type.getTypePtr())->isDeduced();
3544
3545   case Type::Builtin:
3546     switch (cast<BuiltinType>(type.getTypePtr())->getKind()) {
3547       // Signed, unsigned, and floating-point types cannot have nullability.
3548 #define SIGNED_TYPE(Id, SingletonId) case BuiltinType::Id:
3549 #define UNSIGNED_TYPE(Id, SingletonId) case BuiltinType::Id:
3550 #define FLOATING_TYPE(Id, SingletonId) case BuiltinType::Id:
3551 #define BUILTIN_TYPE(Id, SingletonId)
3552 #include "clang/AST/BuiltinTypes.def"
3553       return false;
3554
3555     // Dependent types that could instantiate to a pointer type.
3556     case BuiltinType::Dependent:
3557     case BuiltinType::Overload:
3558     case BuiltinType::BoundMember:
3559     case BuiltinType::PseudoObject:
3560     case BuiltinType::UnknownAny:
3561     case BuiltinType::ARCUnbridgedCast:
3562       return true;
3563
3564     case BuiltinType::Void:
3565     case BuiltinType::ObjCId:
3566     case BuiltinType::ObjCClass:
3567     case BuiltinType::ObjCSel:
3568 #define IMAGE_TYPE(ImgType, Id, SingletonId, Access, Suffix) \
3569     case BuiltinType::Id:
3570 #include "clang/Basic/OpenCLImageTypes.def"
3571     case BuiltinType::OCLSampler:
3572     case BuiltinType::OCLEvent:
3573     case BuiltinType::OCLClkEvent:
3574     case BuiltinType::OCLQueue:
3575     case BuiltinType::OCLNDRange:
3576     case BuiltinType::OCLReserveID:
3577     case BuiltinType::BuiltinFn:
3578     case BuiltinType::NullPtr:
3579     case BuiltinType::OMPArraySection:
3580       return false;
3581     }
3582
3583   // Non-pointer types.
3584   case Type::Complex:
3585   case Type::LValueReference:
3586   case Type::RValueReference:
3587   case Type::ConstantArray:
3588   case Type::IncompleteArray:
3589   case Type::VariableArray:
3590   case Type::DependentSizedArray:
3591   case Type::DependentSizedExtVector:
3592   case Type::Vector:
3593   case Type::ExtVector:
3594   case Type::FunctionProto:
3595   case Type::FunctionNoProto:
3596   case Type::Record:
3597   case Type::Enum:
3598   case Type::InjectedClassName:
3599   case Type::PackExpansion:
3600   case Type::ObjCObject:
3601   case Type::ObjCInterface:
3602   case Type::Atomic:
3603   case Type::Pipe:
3604     return false;
3605   }
3606   llvm_unreachable("bad type kind!");
3607 }
3608
3609 llvm::Optional<NullabilityKind> AttributedType::getImmediateNullability() const {
3610   if (getAttrKind() == AttributedType::attr_nonnull)
3611     return NullabilityKind::NonNull;
3612   if (getAttrKind() == AttributedType::attr_nullable)
3613     return NullabilityKind::Nullable;
3614   if (getAttrKind() == AttributedType::attr_null_unspecified)
3615     return NullabilityKind::Unspecified;
3616   return None;
3617 }
3618
3619 Optional<NullabilityKind> AttributedType::stripOuterNullability(QualType &T) {
3620   if (auto attributed = dyn_cast<AttributedType>(T.getTypePtr())) {
3621     if (auto nullability = attributed->getImmediateNullability()) {
3622       T = attributed->getModifiedType();
3623       return nullability;
3624     }
3625   }
3626
3627   return None;
3628 }
3629
3630 bool Type::isBlockCompatibleObjCPointerType(ASTContext &ctx) const {
3631   const ObjCObjectPointerType *objcPtr = getAs<ObjCObjectPointerType>();
3632   if (!objcPtr)
3633     return false;
3634
3635   if (objcPtr->isObjCIdType()) {
3636     // id is always okay.
3637     return true;
3638   }
3639
3640   // Blocks are NSObjects.
3641   if (ObjCInterfaceDecl *iface = objcPtr->getInterfaceDecl()) {
3642     if (iface->getIdentifier() != ctx.getNSObjectName())
3643       return false;
3644
3645     // Continue to check qualifiers, below.
3646   } else if (objcPtr->isObjCQualifiedIdType()) {
3647     // Continue to check qualifiers, below.
3648   } else {
3649     return false;
3650   }
3651
3652   // Check protocol qualifiers.
3653   for (ObjCProtocolDecl *proto : objcPtr->quals()) {
3654     // Blocks conform to NSObject and NSCopying.
3655     if (proto->getIdentifier() != ctx.getNSObjectName() &&
3656         proto->getIdentifier() != ctx.getNSCopyingName())
3657       return false;
3658   }
3659
3660   return true;
3661 }
3662
3663 Qualifiers::ObjCLifetime Type::getObjCARCImplicitLifetime() const {
3664   if (isObjCARCImplicitlyUnretainedType())
3665     return Qualifiers::OCL_ExplicitNone;
3666   return Qualifiers::OCL_Strong;
3667 }
3668
3669 bool Type::isObjCARCImplicitlyUnretainedType() const {
3670   assert(isObjCLifetimeType() &&
3671          "cannot query implicit lifetime for non-inferrable type");
3672
3673   const Type *canon = getCanonicalTypeInternal().getTypePtr();
3674
3675   // Walk down to the base type.  We don't care about qualifiers for this.
3676   while (const ArrayType *array = dyn_cast<ArrayType>(canon))
3677     canon = array->getElementType().getTypePtr();
3678
3679   if (const ObjCObjectPointerType *opt
3680         = dyn_cast<ObjCObjectPointerType>(canon)) {
3681     // Class and Class<Protocol> don't require retention.
3682     if (opt->getObjectType()->isObjCClass())
3683       return true;
3684   }
3685
3686   return false;
3687 }
3688
3689 bool Type::isObjCNSObjectType() const {
3690   if (const TypedefType *typedefType = dyn_cast<TypedefType>(this))
3691     return typedefType->getDecl()->hasAttr<ObjCNSObjectAttr>();
3692   return false;
3693 }
3694 bool Type::isObjCIndependentClassType() const {
3695   if (const TypedefType *typedefType = dyn_cast<TypedefType>(this))
3696     return typedefType->getDecl()->hasAttr<ObjCIndependentClassAttr>();
3697   return false;
3698 }
3699 bool Type::isObjCRetainableType() const {
3700   return isObjCObjectPointerType() ||
3701          isBlockPointerType() ||
3702          isObjCNSObjectType();
3703 }
3704 bool Type::isObjCIndirectLifetimeType() const {
3705   if (isObjCLifetimeType())
3706     return true;
3707   if (const PointerType *OPT = getAs<PointerType>())
3708     return OPT->getPointeeType()->isObjCIndirectLifetimeType();
3709   if (const ReferenceType *Ref = getAs<ReferenceType>())
3710     return Ref->getPointeeType()->isObjCIndirectLifetimeType();
3711   if (const MemberPointerType *MemPtr = getAs<MemberPointerType>())
3712     return MemPtr->getPointeeType()->isObjCIndirectLifetimeType();
3713   return false;
3714 }
3715
3716 /// Returns true if objects of this type have lifetime semantics under
3717 /// ARC.
3718 bool Type::isObjCLifetimeType() const {
3719   const Type *type = this;
3720   while (const ArrayType *array = type->getAsArrayTypeUnsafe())
3721     type = array->getElementType().getTypePtr();
3722   return type->isObjCRetainableType();
3723 }
3724
3725 /// \brief Determine whether the given type T is a "bridgable" Objective-C type,
3726 /// which is either an Objective-C object pointer type or an
3727 bool Type::isObjCARCBridgableType() const {
3728   return isObjCObjectPointerType() || isBlockPointerType();
3729 }
3730
3731 /// \brief Determine whether the given type T is a "bridgeable" C type.
3732 bool Type::isCARCBridgableType() const {
3733   const PointerType *Pointer = getAs<PointerType>();
3734   if (!Pointer)
3735     return false;
3736
3737   QualType Pointee = Pointer->getPointeeType();
3738   return Pointee->isVoidType() || Pointee->isRecordType();
3739 }
3740
3741 bool Type::hasSizedVLAType() const {
3742   if (!isVariablyModifiedType()) return false;
3743
3744   if (const PointerType *ptr = getAs<PointerType>())
3745     return ptr->getPointeeType()->hasSizedVLAType();
3746   if (const ReferenceType *ref = getAs<ReferenceType>())
3747     return ref->getPointeeType()->hasSizedVLAType();
3748   if (const ArrayType *arr = getAsArrayTypeUnsafe()) {
3749     if (isa<VariableArrayType>(arr) &&
3750         cast<VariableArrayType>(arr)->getSizeExpr())
3751       return true;
3752
3753     return arr->getElementType()->hasSizedVLAType();
3754   }
3755
3756   return false;
3757 }
3758
3759 QualType::DestructionKind QualType::isDestructedTypeImpl(QualType type) {
3760   switch (type.getObjCLifetime()) {
3761   case Qualifiers::OCL_None:
3762   case Qualifiers::OCL_ExplicitNone:
3763   case Qualifiers::OCL_Autoreleasing:
3764     break;
3765
3766   case Qualifiers::OCL_Strong:
3767     return DK_objc_strong_lifetime;
3768   case Qualifiers::OCL_Weak:
3769     return DK_objc_weak_lifetime;
3770   }
3771
3772   /// Currently, the only destruction kind we recognize is C++ objects
3773   /// with non-trivial destructors.
3774   const CXXRecordDecl *record =
3775     type->getBaseElementTypeUnsafe()->getAsCXXRecordDecl();
3776   if (record && record->hasDefinition() && !record->hasTrivialDestructor())
3777     return DK_cxx_destructor;
3778
3779   return DK_none;
3780 }
3781
3782 CXXRecordDecl *MemberPointerType::getMostRecentCXXRecordDecl() const {
3783   return getClass()->getAsCXXRecordDecl()->getMostRecentDecl();
3784 }