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