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