contrib/llvm-project/clang/lib/AST/Type.cpp

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