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