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

   1 //===--- Type.cpp - Type representation and manipulation ------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file implements type-related functionality.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/ASTContext.h"
  15 #include "clang/AST/CharUnits.h"
  16 #include "clang/AST/Type.h"
  17 #include "clang/AST/DeclCXX.h"
  18 #include "clang/AST/DeclObjC.h"
  19 #include "clang/AST/DeclTemplate.h"
  20 #include "clang/AST/Expr.h"
  21 #include "clang/AST/PrettyPrinter.h"
  22 #include "clang/AST/TypeVisitor.h"
  23 #include "clang/Basic/Specifiers.h"
  24 #include "llvm/ADT/StringExtras.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include <algorithm>
  27 using namespace clang;
  28
  29 bool QualType::isConstant(QualType T, ASTContext &Ctx) {
  30   if (T.isConstQualified())
  31     return true;
  32
  33   if (const ArrayType *AT = Ctx.getAsArrayType(T))
  34     return AT->getElementType().isConstant(Ctx);
  35
  36   return false;
  37 }
  38
  39 unsigned ConstantArrayType::getNumAddressingBits(ASTContext &Context,
  40                                                  QualType ElementType,
  41                                                const llvm::APInt &NumElements) {
  42   llvm::APSInt SizeExtended(NumElements, true);
  43   unsigned SizeTypeBits = Context.getTypeSize(Context.getSizeType());
  44   SizeExtended = SizeExtended.extend(std::max(SizeTypeBits,
  45                                               SizeExtended.getBitWidth()) * 2);
  46
  47   uint64_t ElementSize
  48     = Context.getTypeSizeInChars(ElementType).getQuantity();
  49   llvm::APSInt TotalSize(llvm::APInt(SizeExtended.getBitWidth(), ElementSize));
  50   TotalSize *= SizeExtended;
  51
  52   return TotalSize.getActiveBits();
  53 }
  54
  55 unsigned ConstantArrayType::getMaxSizeBits(ASTContext &Context) {
  56   unsigned Bits = Context.getTypeSize(Context.getSizeType());
  57
  58   // GCC appears to only allow 63 bits worth of address space when compiling
  59   // for 64-bit, so we do the same.
  60   if (Bits == 64)
  61     --Bits;
  62
  63   return Bits;
  64 }
  65
  66 DependentSizedArrayType::DependentSizedArrayType(const ASTContext &Context,
  67                                                  QualType et, QualType can,
  68                                                  Expr *e, ArraySizeModifier sm,
  69                                                  unsigned tq,
  70                                                  SourceRange brackets)
  71     : ArrayType(DependentSizedArray, et, can, sm, tq,
  72                 (et->containsUnexpandedParameterPack() ||
  73                  (e && e->containsUnexpandedParameterPack()))),
  74       Context(Context), SizeExpr((Stmt*) e), Brackets(brackets)
  75 {
  76 }
  77
  78 void DependentSizedArrayType::Profile(llvm::FoldingSetNodeID &ID,
  79                                       const ASTContext &Context,
  80                                       QualType ET,
  81                                       ArraySizeModifier SizeMod,
  82                                       unsigned TypeQuals,
  83                                       Expr *E) {
  84   ID.AddPointer(ET.getAsOpaquePtr());
  85   ID.AddInteger(SizeMod);
  86   ID.AddInteger(TypeQuals);
  87   E->Profile(ID, Context, true);
  88 }
  89
  90 DependentSizedExtVectorType::DependentSizedExtVectorType(const
  91                                                          ASTContext &Context,
  92                                                          QualType ElementType,
  93                                                          QualType can,
  94                                                          Expr *SizeExpr,
  95                                                          SourceLocation loc)
  96     : Type(DependentSizedExtVector, can, /*Dependent=*/true,
  97            ElementType->isVariablyModifiedType(),
  98            (ElementType->containsUnexpandedParameterPack() ||
  99             (SizeExpr && SizeExpr->containsUnexpandedParameterPack()))),
 100       Context(Context), SizeExpr(SizeExpr), ElementType(ElementType),
 101       loc(loc)
 102 {
 103 }
 104
 105 void
 106 DependentSizedExtVectorType::Profile(llvm::FoldingSetNodeID &ID,
 107                                      const ASTContext &Context,
 108                                      QualType ElementType, Expr *SizeExpr) {
 109   ID.AddPointer(ElementType.getAsOpaquePtr());
 110   SizeExpr->Profile(ID, Context, true);
 111 }
 112
 113 VectorType::VectorType(QualType vecType, unsigned nElements, QualType canonType,
 114                        VectorKind vecKind)
 115   : Type(Vector, canonType, vecType->isDependentType(),
 116          vecType->isVariablyModifiedType(),
 117          vecType->containsUnexpandedParameterPack()),
 118     ElementType(vecType)
 119 {
 120   VectorTypeBits.VecKind = vecKind;
 121   VectorTypeBits.NumElements = nElements;
 122 }
 123
 124 VectorType::VectorType(TypeClass tc, QualType vecType, unsigned nElements,
 125                        QualType canonType, VectorKind vecKind)
 126   : Type(tc, canonType, vecType->isDependentType(),
 127          vecType->isVariablyModifiedType(),
 128          vecType->containsUnexpandedParameterPack()),
 129     ElementType(vecType)
 130 {
 131   VectorTypeBits.VecKind = vecKind;
 132   VectorTypeBits.NumElements = nElements;
 133 }
 134
 135 /// getArrayElementTypeNoTypeQual - If this is an array type, return the
 136 /// element type of the array, potentially with type qualifiers missing.
 137 /// This method should never be used when type qualifiers are meaningful.
 138 const Type *Type::getArrayElementTypeNoTypeQual() const {
 139   // If this is directly an array type, return it.
 140   if (const ArrayType *ATy = dyn_cast<ArrayType>(this))
 141     return ATy->getElementType().getTypePtr();
 142
 143   // If the canonical form of this type isn't the right kind, reject it.
 144   if (!isa<ArrayType>(CanonicalType))
 145     return 0;
 146
 147   // If this is a typedef for an array type, strip the typedef off without
 148   // losing all typedef information.
 149   return cast<ArrayType>(getUnqualifiedDesugaredType())
 150     ->getElementType().getTypePtr();
 151 }
 152
 153 /// getDesugaredType - Return the specified type with any "sugar" removed from
 154 /// the type.  This takes off typedefs, typeof's etc.  If the outer level of
 155 /// the type is already concrete, it returns it unmodified.  This is similar
 156 /// to getting the canonical type, but it doesn't remove *all* typedefs.  For
 157 /// example, it returns "T*" as "T*", (not as "int*"), because the pointer is
 158 /// concrete.
 159 QualType QualType::getDesugaredType(QualType T, const ASTContext &Context) {
 160   SplitQualType split = getSplitDesugaredType(T);
 161   return Context.getQualifiedType(split.first, split.second);
 162 }
 163
 164 SplitQualType QualType::getSplitDesugaredType(QualType T) {
 165   QualifierCollector Qs;
 166
 167   QualType Cur = T;
 168   while (true) {
 169     const Type *CurTy = Qs.strip(Cur);
 170     switch (CurTy->getTypeClass()) {
 171 #define ABSTRACT_TYPE(Class, Parent)
 172 #define TYPE(Class, Parent) \
 173     case Type::Class: { \
 174       const Class##Type *Ty = cast<Class##Type>(CurTy); \
 175       if (!Ty->isSugared()) \
 176         return SplitQualType(Ty, Qs); \
 177       Cur = Ty->desugar(); \
 178       break; \
 179     }
 180 #include "clang/AST/TypeNodes.def"
 181     }
 182   }
 183 }
 184
 185 SplitQualType QualType::getSplitUnqualifiedTypeImpl(QualType type) {
 186   SplitQualType split = type.split();
 187
 188   // All the qualifiers we've seen so far.
 189   Qualifiers quals = split.second;
 190
 191   // The last type node we saw with any nodes inside it.
 192   const Type *lastTypeWithQuals = split.first;
 193
 194   while (true) {
 195     QualType next;
 196
 197     // Do a single-step desugar, aborting the loop if the type isn't
 198     // sugared.
 199     switch (split.first->getTypeClass()) {
 200 #define ABSTRACT_TYPE(Class, Parent)
 201 #define TYPE(Class, Parent) \
 202     case Type::Class: { \
 203       const Class##Type *ty = cast<Class##Type>(split.first); \
 204       if (!ty->isSugared()) goto done; \
 205       next = ty->desugar(); \
 206       break; \
 207     }
 208 #include "clang/AST/TypeNodes.def"
 209     }
 210
 211     // Otherwise, split the underlying type.  If that yields qualifiers,
 212     // update the information.
 213     split = next.split();
 214     if (!split.second.empty()) {
 215       lastTypeWithQuals = split.first;
 216       quals.addConsistentQualifiers(split.second);
 217     }
 218   }
 219
 220  done:
 221   return SplitQualType(lastTypeWithQuals, quals);
 222 }
 223
 224 QualType QualType::IgnoreParens(QualType T) {
 225   // FIXME: this seems inherently un-qualifiers-safe.
 226   while (const ParenType *PT = T->getAs<ParenType>())
 227     T = PT->getInnerType();
 228   return T;
 229 }
 230
 231 /// getUnqualifiedDesugaredType - Pull any qualifiers and syntactic
 232 /// sugar off the given type.  This should produce an object of the
 233 /// same dynamic type as the canonical type.
 234 const Type *Type::getUnqualifiedDesugaredType() const {
 235   const Type *Cur = this;
 236
 237   while (true) {
 238     switch (Cur->getTypeClass()) {
 239 #define ABSTRACT_TYPE(Class, Parent)
 240 #define TYPE(Class, Parent) \
 241     case Class: { \
 242       const Class##Type *Ty = cast<Class##Type>(Cur); \
 243       if (!Ty->isSugared()) return Cur; \
 244       Cur = Ty->desugar().getTypePtr(); \
 245       break; \
 246     }
 247 #include "clang/AST/TypeNodes.def"
 248     }
 249   }
 250 }
 251
 252 /// isVoidType - Helper method to determine if this is the 'void' type.
 253 bool Type::isVoidType() const {
 254   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 255     return BT->getKind() == BuiltinType::Void;
 256   return false;
 257 }
 258
 259 bool Type::isDerivedType() const {
 260   switch (CanonicalType->getTypeClass()) {
 261   case Pointer:
 262   case VariableArray:
 263   case ConstantArray:
 264   case IncompleteArray:
 265   case FunctionProto:
 266   case FunctionNoProto:
 267   case LValueReference:
 268   case RValueReference:
 269   case Record:
 270     return true;
 271   default:
 272     return false;
 273   }
 274 }
 275
 276 bool Type::isClassType() const {
 277   if (const RecordType *RT = getAs<RecordType>())
 278     return RT->getDecl()->isClass();
 279   return false;
 280 }
 281 bool Type::isStructureType() const {
 282   if (const RecordType *RT = getAs<RecordType>())
 283     return RT->getDecl()->isStruct();
 284   return false;
 285 }
 286 bool Type::isStructureOrClassType() const {
 287   if (const RecordType *RT = getAs<RecordType>())
 288     return RT->getDecl()->isStruct() || RT->getDecl()->isClass();
 289   return false;
 290 }
 291 bool Type::isVoidPointerType() const {
 292   if (const PointerType *PT = getAs<PointerType>())
 293     return PT->getPointeeType()->isVoidType();
 294   return false;
 295 }
 296
 297 bool Type::isUnionType() const {
 298   if (const RecordType *RT = getAs<RecordType>())
 299     return RT->getDecl()->isUnion();
 300   return false;
 301 }
 302
 303 bool Type::isComplexType() const {
 304   if (const ComplexType *CT = dyn_cast<ComplexType>(CanonicalType))
 305     return CT->getElementType()->isFloatingType();
 306   return false;
 307 }
 308
 309 bool Type::isComplexIntegerType() const {
 310   // Check for GCC complex integer extension.
 311   return getAsComplexIntegerType();
 312 }
 313
 314 const ComplexType *Type::getAsComplexIntegerType() const {
 315   if (const ComplexType *Complex = getAs<ComplexType>())
 316     if (Complex->getElementType()->isIntegerType())
 317       return Complex;
 318   return 0;
 319 }
 320
 321 QualType Type::getPointeeType() const {
 322   if (const PointerType *PT = getAs<PointerType>())
 323     return PT->getPointeeType();
 324   if (const ObjCObjectPointerType *OPT = getAs<ObjCObjectPointerType>())
 325     return OPT->getPointeeType();
 326   if (const BlockPointerType *BPT = getAs<BlockPointerType>())
 327     return BPT->getPointeeType();
 328   if (const ReferenceType *RT = getAs<ReferenceType>())
 329     return RT->getPointeeType();
 330   return QualType();
 331 }
 332
 333 const RecordType *Type::getAsStructureType() const {
 334   // If this is directly a structure type, return it.
 335   if (const RecordType *RT = dyn_cast<RecordType>(this)) {
 336     if (RT->getDecl()->isStruct())
 337       return RT;
 338   }
 339
 340   // If the canonical form of this type isn't the right kind, reject it.
 341   if (const RecordType *RT = dyn_cast<RecordType>(CanonicalType)) {
 342     if (!RT->getDecl()->isStruct())
 343       return 0;
 344
 345     // If this is a typedef for a structure type, strip the typedef off without
 346     // losing all typedef information.
 347     return cast<RecordType>(getUnqualifiedDesugaredType());
 348   }
 349   return 0;
 350 }
 351
 352 const RecordType *Type::getAsUnionType() const {
 353   // If this is directly a union type, return it.
 354   if (const RecordType *RT = dyn_cast<RecordType>(this)) {
 355     if (RT->getDecl()->isUnion())
 356       return RT;
 357   }
 358
 359   // If the canonical form of this type isn't the right kind, reject it.
 360   if (const RecordType *RT = dyn_cast<RecordType>(CanonicalType)) {
 361     if (!RT->getDecl()->isUnion())
 362       return 0;
 363
 364     // If this is a typedef for a union type, strip the typedef off without
 365     // losing all typedef information.
 366     return cast<RecordType>(getUnqualifiedDesugaredType());
 367   }
 368
 369   return 0;
 370 }
 371
 372 ObjCObjectType::ObjCObjectType(QualType Canonical, QualType Base,
 373                                ObjCProtocolDecl * const *Protocols,
 374                                unsigned NumProtocols)
 375   : Type(ObjCObject, Canonical, false, false, false),
 376     BaseType(Base)
 377 {
 378   ObjCObjectTypeBits.NumProtocols = NumProtocols;
 379   assert(getNumProtocols() == NumProtocols &&
 380          "bitfield overflow in protocol count");
 381   if (NumProtocols)
 382     memcpy(getProtocolStorage(), Protocols,
 383            NumProtocols * sizeof(ObjCProtocolDecl*));
 384 }
 385
 386 const ObjCObjectType *Type::getAsObjCQualifiedInterfaceType() const {
 387   // There is no sugar for ObjCObjectType's, just return the canonical
 388   // type pointer if it is the right class.  There is no typedef information to
 389   // return and these cannot be Address-space qualified.
 390   if (const ObjCObjectType *T = getAs<ObjCObjectType>())
 391     if (T->getNumProtocols() && T->getInterface())
 392       return T;
 393   return 0;
 394 }
 395
 396 bool Type::isObjCQualifiedInterfaceType() const {
 397   return getAsObjCQualifiedInterfaceType() != 0;
 398 }
 399
 400 const ObjCObjectPointerType *Type::getAsObjCQualifiedIdType() const {
 401   // There is no sugar for ObjCQualifiedIdType's, just return the canonical
 402   // type pointer if it is the right class.
 403   if (const ObjCObjectPointerType *OPT = getAs<ObjCObjectPointerType>()) {
 404     if (OPT->isObjCQualifiedIdType())
 405       return OPT;
 406   }
 407   return 0;
 408 }
 409
 410 const ObjCObjectPointerType *Type::getAsObjCInterfacePointerType() const {
 411   if (const ObjCObjectPointerType *OPT = getAs<ObjCObjectPointerType>()) {
 412     if (OPT->getInterfaceType())
 413       return OPT;
 414   }
 415   return 0;
 416 }
 417
 418 const CXXRecordDecl *Type::getCXXRecordDeclForPointerType() const {
 419   if (const PointerType *PT = getAs<PointerType>())
 420     if (const RecordType *RT = PT->getPointeeType()->getAs<RecordType>())
 421       return dyn_cast<CXXRecordDecl>(RT->getDecl());
 422   return 0;
 423 }
 424
 425 CXXRecordDecl *Type::getAsCXXRecordDecl() const {
 426   if (const RecordType *RT = getAs<RecordType>())
 427     return dyn_cast<CXXRecordDecl>(RT->getDecl());
 428   else if (const InjectedClassNameType *Injected
 429                                   = getAs<InjectedClassNameType>())
 430     return Injected->getDecl();
 431
 432   return 0;
 433 }
 434
 435 namespace {
 436   class GetContainedAutoVisitor :
 437     public TypeVisitor<GetContainedAutoVisitor, AutoType*> {
 438   public:
 439     using TypeVisitor<GetContainedAutoVisitor, AutoType*>::Visit;
 440     AutoType *Visit(QualType T) {
 441       if (T.isNull())
 442         return 0;
 443       return Visit(T.getTypePtr());
 444     }
 445
 446     // The 'auto' type itself.
 447     AutoType *VisitAutoType(const AutoType *AT) {
 448       return const_cast<AutoType*>(AT);
 449     }
 450
 451     // Only these types can contain the desired 'auto' type.
 452     AutoType *VisitPointerType(const PointerType *T) {
 453       return Visit(T->getPointeeType());
 454     }
 455     AutoType *VisitBlockPointerType(const BlockPointerType *T) {
 456       return Visit(T->getPointeeType());
 457     }
 458     AutoType *VisitReferenceType(const ReferenceType *T) {
 459       return Visit(T->getPointeeTypeAsWritten());
 460     }
 461     AutoType *VisitMemberPointerType(const MemberPointerType *T) {
 462       return Visit(T->getPointeeType());
 463     }
 464     AutoType *VisitArrayType(const ArrayType *T) {
 465       return Visit(T->getElementType());
 466     }
 467     AutoType *VisitDependentSizedExtVectorType(
 468       const DependentSizedExtVectorType *T) {
 469       return Visit(T->getElementType());
 470     }
 471     AutoType *VisitVectorType(const VectorType *T) {
 472       return Visit(T->getElementType());
 473     }
 474     AutoType *VisitFunctionType(const FunctionType *T) {
 475       return Visit(T->getResultType());
 476     }
 477     AutoType *VisitParenType(const ParenType *T) {
 478       return Visit(T->getInnerType());
 479     }
 480     AutoType *VisitAttributedType(const AttributedType *T) {
 481       return Visit(T->getModifiedType());
 482     }
 483   };
 484 }
 485
 486 AutoType *Type::getContainedAutoType() const {
 487   return GetContainedAutoVisitor().Visit(this);
 488 }
 489
 490 bool Type::isIntegerType() const {
 491   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 492     return BT->getKind() >= BuiltinType::Bool &&
 493            BT->getKind() <= BuiltinType::Int128;
 494   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
 495     // Incomplete enum types are not treated as integer types.
 496     // FIXME: In C++, enum types are never integer types.
 497     return ET->getDecl()->isComplete();
 498   return false;
 499 }
 500
 501 bool Type::hasIntegerRepresentation() const {
 502   if (const VectorType *VT = dyn_cast<VectorType>(CanonicalType))
 503     return VT->getElementType()->isIntegerType();
 504   else
 505     return isIntegerType();
 506 }
 507
 508 /// \brief Determine whether this type is an integral type.
 509 ///
 510 /// This routine determines whether the given type is an integral type per
 511 /// C++ [basic.fundamental]p7. Although the C standard does not define the
 512 /// term "integral type", it has a similar term "integer type", and in C++
 513 /// the two terms are equivalent. However, C's "integer type" includes
 514 /// enumeration types, while C++'s "integer type" does not. The \c ASTContext
 515 /// parameter is used to determine whether we should be following the C or
 516 /// C++ rules when determining whether this type is an integral/integer type.
 517 ///
 518 /// For cases where C permits "an integer type" and C++ permits "an integral
 519 /// type", use this routine.
 520 ///
 521 /// For cases where C permits "an integer type" and C++ permits "an integral
 522 /// or enumeration type", use \c isIntegralOrEnumerationType() instead.
 523 ///
 524 /// \param Ctx The context in which this type occurs.
 525 ///
 526 /// \returns true if the type is considered an integral type, false otherwise.
 527 bool Type::isIntegralType(ASTContext &Ctx) const {
 528   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 529     return BT->getKind() >= BuiltinType::Bool &&
 530     BT->getKind() <= BuiltinType::Int128;
 531
 532   if (!Ctx.getLangOptions().CPlusPlus)
 533     if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
 534       return ET->getDecl()->isComplete(); // Complete enum types are integral in C.
 535
 536   return false;
 537 }
 538
 539 bool Type::isIntegralOrEnumerationType() const {
 540   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 541     return BT->getKind() >= BuiltinType::Bool &&
 542            BT->getKind() <= BuiltinType::Int128;
 543
 544   // Check for a complete enum type; incomplete enum types are not properly an
 545   // enumeration type in the sense required here.
 546   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
 547     return ET->getDecl()->isComplete();
 548
 549   return false;
 550 }
 551
 552 bool Type::isIntegralOrUnscopedEnumerationType() const {
 553   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 554     return BT->getKind() >= BuiltinType::Bool &&
 555            BT->getKind() <= BuiltinType::Int128;
 556
 557   // Check for a complete enum type; incomplete enum types are not properly an
 558   // enumeration type in the sense required here.
 559   // C++0x: However, if the underlying type of the enum is fixed, it is
 560   // considered complete.
 561   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
 562     return ET->getDecl()->isComplete() && !ET->getDecl()->isScoped();
 563
 564   return false;
 565 }
 566
 567
 568 bool Type::isBooleanType() const {
 569   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 570     return BT->getKind() == BuiltinType::Bool;
 571   return false;
 572 }
 573
 574 bool Type::isCharType() const {
 575   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 576     return BT->getKind() == BuiltinType::Char_U ||
 577            BT->getKind() == BuiltinType::UChar ||
 578            BT->getKind() == BuiltinType::Char_S ||
 579            BT->getKind() == BuiltinType::SChar;
 580   return false;
 581 }
 582
 583 bool Type::isWideCharType() const {
 584   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 585     return BT->getKind() == BuiltinType::WChar_S ||
 586            BT->getKind() == BuiltinType::WChar_U;
 587   return false;
 588 }
 589
 590 /// \brief Determine whether this type is any of the built-in character
 591 /// types.
 592 bool Type::isAnyCharacterType() const {
 593   const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType);
 594   if (BT == 0) return false;
 595   switch (BT->getKind()) {
 596   default: return false;
 597   case BuiltinType::Char_U:
 598   case BuiltinType::UChar:
 599   case BuiltinType::WChar_U:
 600   case BuiltinType::Char16:
 601   case BuiltinType::Char32:
 602   case BuiltinType::Char_S:
 603   case BuiltinType::SChar:
 604   case BuiltinType::WChar_S:
 605     return true;
 606   }
 607 }
 608
 609 /// isSignedIntegerType - Return true if this is an integer type that is
 610 /// signed, according to C99 6.2.5p4 [char, signed char, short, int, long..],
 611 /// an enum decl which has a signed representation
 612 bool Type::isSignedIntegerType() const {
 613   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType)) {
 614     return BT->getKind() >= BuiltinType::Char_S &&
 615            BT->getKind() <= BuiltinType::Int128;
 616   }
 617
 618   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType)) {
 619     // Incomplete enum types are not treated as integer types.
 620     // FIXME: In C++, enum types are never integer types.
 621     if (ET->getDecl()->isComplete())
 622       return ET->getDecl()->getIntegerType()->isSignedIntegerType();
 623   }
 624
 625   return false;
 626 }
 627
 628 bool Type::hasSignedIntegerRepresentation() const {
 629   if (const VectorType *VT = dyn_cast<VectorType>(CanonicalType))
 630     return VT->getElementType()->isSignedIntegerType();
 631   else
 632     return isSignedIntegerType();
 633 }
 634
 635 /// isUnsignedIntegerType - Return true if this is an integer type that is
 636 /// unsigned, according to C99 6.2.5p6 [which returns true for _Bool], an enum
 637 /// decl which has an unsigned representation
 638 bool Type::isUnsignedIntegerType() const {
 639   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType)) {
 640     return BT->getKind() >= BuiltinType::Bool &&
 641            BT->getKind() <= BuiltinType::UInt128;
 642   }
 643
 644   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType)) {
 645     // Incomplete enum types are not treated as integer types.
 646     // FIXME: In C++, enum types are never integer types.
 647     if (ET->getDecl()->isComplete())
 648       return ET->getDecl()->getIntegerType()->isUnsignedIntegerType();
 649   }
 650
 651   return false;
 652 }
 653
 654 bool Type::hasUnsignedIntegerRepresentation() const {
 655   if (const VectorType *VT = dyn_cast<VectorType>(CanonicalType))
 656     return VT->getElementType()->isUnsignedIntegerType();
 657   else
 658     return isUnsignedIntegerType();
 659 }
 660
 661 bool Type::isFloatingType() const {
 662   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 663     return BT->getKind() >= BuiltinType::Float &&
 664            BT->getKind() <= BuiltinType::LongDouble;
 665   if (const ComplexType *CT = dyn_cast<ComplexType>(CanonicalType))
 666     return CT->getElementType()->isFloatingType();
 667   return false;
 668 }
 669
 670 bool Type::hasFloatingRepresentation() const {
 671   if (const VectorType *VT = dyn_cast<VectorType>(CanonicalType))
 672     return VT->getElementType()->isFloatingType();
 673   else
 674     return isFloatingType();
 675 }
 676
 677 bool Type::isRealFloatingType() const {
 678   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 679     return BT->isFloatingPoint();
 680   return false;
 681 }
 682
 683 bool Type::isRealType() const {
 684   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 685     return BT->getKind() >= BuiltinType::Bool &&
 686            BT->getKind() <= BuiltinType::LongDouble;
 687   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
 688       return ET->getDecl()->isComplete() && !ET->getDecl()->isScoped();
 689   return false;
 690 }
 691
 692 bool Type::isArithmeticType() const {
 693   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 694     return BT->getKind() >= BuiltinType::Bool &&
 695            BT->getKind() <= BuiltinType::LongDouble;
 696   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
 697     // GCC allows forward declaration of enum types (forbid by C99 6.7.2.3p2).
 698     // If a body isn't seen by the time we get here, return false.
 699     //
 700     // C++0x: Enumerations are not arithmetic types. For now, just return
 701     // false for scoped enumerations since that will disable any
 702     // unwanted implicit conversions.
 703     return !ET->getDecl()->isScoped() && ET->getDecl()->isComplete();
 704   return isa<ComplexType>(CanonicalType);
 705 }
 706
 707 bool Type::isScalarType() const {
 708   if (const BuiltinType *BT = dyn_cast<BuiltinType>(CanonicalType))
 709     return BT->getKind() > BuiltinType::Void &&
 710            BT->getKind() <= BuiltinType::NullPtr;
 711   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType))
 712     // Enums are scalar types, but only if they are defined.  Incomplete enums
 713     // are not treated as scalar types.
 714     return ET->getDecl()->isComplete();
 715   return isa<PointerType>(CanonicalType) ||
 716          isa<BlockPointerType>(CanonicalType) ||
 717          isa<MemberPointerType>(CanonicalType) ||
 718          isa<ComplexType>(CanonicalType) ||
 719          isa<ObjCObjectPointerType>(CanonicalType);
 720 }
 721
 722 Type::ScalarTypeKind Type::getScalarTypeKind() const {
 723   assert(isScalarType());
 724
 725   const Type *T = CanonicalType.getTypePtr();
 726   if (const BuiltinType *BT = dyn_cast<BuiltinType>(T)) {
 727     if (BT->getKind() == BuiltinType::Bool) return STK_Bool;
 728     if (BT->getKind() == BuiltinType::NullPtr) return STK_Pointer;
 729     if (BT->isInteger()) return STK_Integral;
 730     if (BT->isFloatingPoint()) return STK_Floating;
 731     llvm_unreachable("unknown scalar builtin type");
 732   } else if (isa<PointerType>(T) ||
 733              isa<BlockPointerType>(T) ||
 734              isa<ObjCObjectPointerType>(T)) {
 735     return STK_Pointer;
 736   } else if (isa<MemberPointerType>(T)) {
 737     return STK_MemberPointer;
 738   } else if (isa<EnumType>(T)) {
 739     assert(cast<EnumType>(T)->getDecl()->isComplete());
 740     return STK_Integral;
 741   } else if (const ComplexType *CT = dyn_cast<ComplexType>(T)) {
 742     if (CT->getElementType()->isRealFloatingType())
 743       return STK_FloatingComplex;
 744     return STK_IntegralComplex;
 745   }
 746
 747   llvm_unreachable("unknown scalar type");
 748   return STK_Pointer;
 749 }
 750
 751 /// \brief Determines whether the type is a C++ aggregate type or C
 752 /// aggregate or union type.
 753 ///
 754 /// An aggregate type is an array or a class type (struct, union, or
 755 /// class) that has no user-declared constructors, no private or
 756 /// protected non-static data members, no base classes, and no virtual
 757 /// functions (C++ [dcl.init.aggr]p1). The notion of an aggregate type
 758 /// subsumes the notion of C aggregates (C99 6.2.5p21) because it also
 759 /// includes union types.
 760 bool Type::isAggregateType() const {
 761   if (const RecordType *Record = dyn_cast<RecordType>(CanonicalType)) {
 762     if (CXXRecordDecl *ClassDecl = dyn_cast<CXXRecordDecl>(Record->getDecl()))
 763       return ClassDecl->isAggregate();
 764
 765     return true;
 766   }
 767
 768   return isa<ArrayType>(CanonicalType);
 769 }
 770
 771 /// isConstantSizeType - Return true if this is not a variable sized type,
 772 /// according to the rules of C99 6.7.5p3.  It is not legal to call this on
 773 /// incomplete types or dependent types.
 774 bool Type::isConstantSizeType() const {
 775   assert(!isIncompleteType() && "This doesn't make sense for incomplete types");
 776   assert(!isDependentType() && "This doesn't make sense for dependent types");
 777   // The VAT must have a size, as it is known to be complete.
 778   return !isa<VariableArrayType>(CanonicalType);
 779 }
 780
 781 /// isIncompleteType - Return true if this is an incomplete type (C99 6.2.5p1)
 782 /// - a type that can describe objects, but which lacks information needed to
 783 /// determine its size.
 784 bool Type::isIncompleteType() const {
 785   switch (CanonicalType->getTypeClass()) {
 786   default: return false;
 787   case Builtin:
 788     // Void is the only incomplete builtin type.  Per C99 6.2.5p19, it can never
 789     // be completed.
 790     return isVoidType();
 791   case Enum:
 792     // An enumeration with fixed underlying type is complete (C++0x 7.2p3).
 793     if (cast<EnumType>(CanonicalType)->getDecl()->isFixed())
 794         return false;
 795     // Fall through.
 796   case Record:
 797     // A tagged type (struct/union/enum/class) is incomplete if the decl is a
 798     // forward declaration, but not a full definition (C99 6.2.5p22).
 799     return !cast<TagType>(CanonicalType)->getDecl()->isDefinition();
 800   case ConstantArray:
 801     // An array is incomplete if its element type is incomplete
 802     // (C++ [dcl.array]p1).
 803     // We don't handle variable arrays (they're not allowed in C++) or
 804     // dependent-sized arrays (dependent types are never treated as incomplete).
 805     return cast<ArrayType>(CanonicalType)->getElementType()->isIncompleteType();
 806   case IncompleteArray:
 807     // An array of unknown size is an incomplete type (C99 6.2.5p22).
 808     return true;
 809   case ObjCObject:
 810     return cast<ObjCObjectType>(CanonicalType)->getBaseType()
 811                                                          ->isIncompleteType();
 812   case ObjCInterface:
 813     // ObjC interfaces are incomplete if they are @class, not @interface.
 814     return cast<ObjCInterfaceType>(CanonicalType)->getDecl()->isForwardDecl();
 815   }
 816 }
 817
 818 /// isPODType - Return true if this is a plain-old-data type (C++ 3.9p10)
 819 bool Type::isPODType() const {
 820   // The compiler shouldn't query this for incomplete types, but the user might.
 821   // We return false for that case. Except for incomplete arrays of PODs, which
 822   // are PODs according to the standard.
 823   if (isIncompleteArrayType() &&
 824       cast<ArrayType>(CanonicalType)->getElementType()->isPODType())
 825     return true;
 826   if (isIncompleteType())
 827     return false;
 828
 829   switch (CanonicalType->getTypeClass()) {
 830     // Everything not explicitly mentioned is not POD.
 831   default: return false;
 832   case VariableArray:
 833   case ConstantArray:
 834     // IncompleteArray is handled above.
 835     return cast<ArrayType>(CanonicalType)->getElementType()->isPODType();
 836
 837   case Builtin:
 838   case Complex:
 839   case Pointer:
 840   case MemberPointer:
 841   case Vector:
 842   case ExtVector:
 843   case ObjCObjectPointer:
 844   case BlockPointer:
 845     return true;
 846
 847   case Enum:
 848     return true;
 849
 850   case Record:
 851     if (CXXRecordDecl *ClassDecl
 852           = dyn_cast<CXXRecordDecl>(cast<RecordType>(CanonicalType)->getDecl()))
 853       return ClassDecl->isPOD();
 854
 855     // C struct/union is POD.
 856     return true;
 857   }
 858 }
 859
 860 bool Type::isLiteralType() const {
 861   if (isIncompleteType())
 862     return false;
 863
 864   // C++0x [basic.types]p10:
 865   //   A type is a literal type if it is:
 866   switch (CanonicalType->getTypeClass()) {
 867     // We're whitelisting
 868   default: return false;
 869
 870     //   -- a scalar type
 871   case Builtin:
 872   case Complex:
 873   case Pointer:
 874   case MemberPointer:
 875   case Vector:
 876   case ExtVector:
 877   case ObjCObjectPointer:
 878   case Enum:
 879     return true;
 880
 881     //   -- a class type with ...
 882   case Record:
 883     // FIXME: Do the tests
 884     return false;
 885
 886     //   -- an array of literal type
 887     // Extension: variable arrays cannot be literal types, since they're
 888     // runtime-sized.
 889   case ConstantArray:
 890     return cast<ArrayType>(CanonicalType)->getElementType()->isLiteralType();
 891   }
 892 }
 893
 894 bool Type::isPromotableIntegerType() const {
 895   if (const BuiltinType *BT = getAs<BuiltinType>())
 896     switch (BT->getKind()) {
 897     case BuiltinType::Bool:
 898     case BuiltinType::Char_S:
 899     case BuiltinType::Char_U:
 900     case BuiltinType::SChar:
 901     case BuiltinType::UChar:
 902     case BuiltinType::Short:
 903     case BuiltinType::UShort:
 904       return true;
 905     default:
 906       return false;
 907     }
 908
 909   // Enumerated types are promotable to their compatible integer types
 910   // (C99 6.3.1.1) a.k.a. its underlying type (C++ [conv.prom]p2).
 911   if (const EnumType *ET = getAs<EnumType>()){
 912     if (this->isDependentType() || ET->getDecl()->getPromotionType().isNull()
 913         || ET->getDecl()->isScoped())
 914       return false;
 915
 916     const BuiltinType *BT
 917       = ET->getDecl()->getPromotionType()->getAs<BuiltinType>();
 918     return BT->getKind() == BuiltinType::Int
 919            || BT->getKind() == BuiltinType::UInt;
 920   }
 921
 922   return false;
 923 }
 924
 925 bool Type::isNullPtrType() const {
 926   if (const BuiltinType *BT = getAs<BuiltinType>())
 927     return BT->getKind() == BuiltinType::NullPtr;
 928   return false;
 929 }
 930
 931 bool Type::isSpecifierType() const {
 932   // Note that this intentionally does not use the canonical type.
 933   switch (getTypeClass()) {
 934   case Builtin:
 935   case Record:
 936   case Enum:
 937   case Typedef:
 938   case Complex:
 939   case TypeOfExpr:
 940   case TypeOf:
 941   case TemplateTypeParm:
 942   case SubstTemplateTypeParm:
 943   case TemplateSpecialization:
 944   case Elaborated:
 945   case DependentName:
 946   case DependentTemplateSpecialization:
 947   case ObjCInterface:
 948   case ObjCObject:
 949   case ObjCObjectPointer: // FIXME: object pointers aren't really specifiers
 950     return true;
 951   default:
 952     return false;
 953   }
 954 }
 955
 956 ElaboratedTypeKeyword
 957 TypeWithKeyword::getKeywordForTypeSpec(unsigned TypeSpec) {
 958   switch (TypeSpec) {
 959   default: return ETK_None;
 960   case TST_typename: return ETK_Typename;
 961   case TST_class: return ETK_Class;
 962   case TST_struct: return ETK_Struct;
 963   case TST_union: return ETK_Union;
 964   case TST_enum: return ETK_Enum;
 965   }
 966 }
 967
 968 TagTypeKind
 969 TypeWithKeyword::getTagTypeKindForTypeSpec(unsigned TypeSpec) {
 970   switch(TypeSpec) {
 971   case TST_class: return TTK_Class;
 972   case TST_struct: return TTK_Struct;
 973   case TST_union: return TTK_Union;
 974   case TST_enum: return TTK_Enum;
 975   }
 976
 977   llvm_unreachable("Type specifier is not a tag type kind.");
 978   return TTK_Union;
 979 }
 980
 981 ElaboratedTypeKeyword
 982 TypeWithKeyword::getKeywordForTagTypeKind(TagTypeKind Kind) {
 983   switch (Kind) {
 984   case TTK_Class: return ETK_Class;
 985   case TTK_Struct: return ETK_Struct;
 986   case TTK_Union: return ETK_Union;
 987   case TTK_Enum: return ETK_Enum;
 988   }
 989   llvm_unreachable("Unknown tag type kind.");
 990 }
 991
 992 TagTypeKind
 993 TypeWithKeyword::getTagTypeKindForKeyword(ElaboratedTypeKeyword Keyword) {
 994   switch (Keyword) {
 995   case ETK_Class: return TTK_Class;
 996   case ETK_Struct: return TTK_Struct;
 997   case ETK_Union: return TTK_Union;
 998   case ETK_Enum: return TTK_Enum;
 999   case ETK_None: // Fall through.
1000   case ETK_Typename:
1001     llvm_unreachable("Elaborated type keyword is not a tag type kind.");
1002   }
1003   llvm_unreachable("Unknown elaborated type keyword.");
1004 }
1005
1006 bool
1007 TypeWithKeyword::KeywordIsTagTypeKind(ElaboratedTypeKeyword Keyword) {
1008   switch (Keyword) {
1009   case ETK_None:
1010   case ETK_Typename:
1011     return false;
1012   case ETK_Class:
1013   case ETK_Struct:
1014   case ETK_Union:
1015   case ETK_Enum:
1016     return true;
1017   }
1018   llvm_unreachable("Unknown elaborated type keyword.");
1019 }
1020
1021 const char*
1022 TypeWithKeyword::getKeywordName(ElaboratedTypeKeyword Keyword) {
1023   switch (Keyword) {
1024   case ETK_None: return "";
1025   case ETK_Typename: return "typename";
1026   case ETK_Class:  return "class";
1027   case ETK_Struct: return "struct";
1028   case ETK_Union:  return "union";
1029   case ETK_Enum:   return "enum";
1030   }
1031
1032   llvm_unreachable("Unknown elaborated type keyword.");
1033   return "";
1034 }
1035
1036 DependentTemplateSpecializationType::DependentTemplateSpecializationType(
1037                          ElaboratedTypeKeyword Keyword,
1038                          NestedNameSpecifier *NNS, const IdentifierInfo *Name,
1039                          unsigned NumArgs, const TemplateArgument *Args,
1040                          QualType Canon)
1041   : TypeWithKeyword(Keyword, DependentTemplateSpecialization, Canon, true,
1042                     /*VariablyModified=*/false,
1043                     NNS->containsUnexpandedParameterPack()),
1044     NNS(NNS), Name(Name), NumArgs(NumArgs) {
1045   assert(NNS && NNS->isDependent() &&
1046          "DependentTemplateSpecializatonType requires dependent qualifier");
1047   for (unsigned I = 0; I != NumArgs; ++I) {
1048     if (Args[I].containsUnexpandedParameterPack())
1049       setContainsUnexpandedParameterPack();
1050
1051     new (&getArgBuffer()[I]) TemplateArgument(Args[I]);
1052   }
1053 }
1054
1055 void
1056 DependentTemplateSpecializationType::Profile(llvm::FoldingSetNodeID &ID,
1057                                              const ASTContext &Context,
1058                                              ElaboratedTypeKeyword Keyword,
1059                                              NestedNameSpecifier *Qualifier,
1060                                              const IdentifierInfo *Name,
1061                                              unsigned NumArgs,
1062                                              const TemplateArgument *Args) {
1063   ID.AddInteger(Keyword);
1064   ID.AddPointer(Qualifier);
1065   ID.AddPointer(Name);
1066   for (unsigned Idx = 0; Idx < NumArgs; ++Idx)
1067     Args[Idx].Profile(ID, Context);
1068 }
1069
1070 bool Type::isElaboratedTypeSpecifier() const {
1071   ElaboratedTypeKeyword Keyword;
1072   if (const ElaboratedType *Elab = dyn_cast<ElaboratedType>(this))
1073     Keyword = Elab->getKeyword();
1074   else if (const DependentNameType *DepName = dyn_cast<DependentNameType>(this))
1075     Keyword = DepName->getKeyword();
1076   else if (const DependentTemplateSpecializationType *DepTST =
1077              dyn_cast<DependentTemplateSpecializationType>(this))
1078     Keyword = DepTST->getKeyword();
1079   else
1080     return false;
1081
1082   return TypeWithKeyword::KeywordIsTagTypeKind(Keyword);
1083 }
1084
1085 const char *Type::getTypeClassName() const {
1086   switch (TypeBits.TC) {
1087 #define ABSTRACT_TYPE(Derived, Base)
1088 #define TYPE(Derived, Base) case Derived: return #Derived;
1089 #include "clang/AST/TypeNodes.def"
1090   }
1091
1092   llvm_unreachable("Invalid type class.");
1093   return 0;
1094 }
1095
1096 const char *BuiltinType::getName(const LangOptions &LO) const {
1097   switch (getKind()) {
1098   case Void:              return "void";
1099   case Bool:              return LO.Bool ? "bool" : "_Bool";
1100   case Char_S:            return "char";
1101   case Char_U:            return "char";
1102   case SChar:             return "signed char";
1103   case Short:             return "short";
1104   case Int:               return "int";
1105   case Long:              return "long";
1106   case LongLong:          return "long long";
1107   case Int128:            return "__int128_t";
1108   case UChar:             return "unsigned char";
1109   case UShort:            return "unsigned short";
1110   case UInt:              return "unsigned int";
1111   case ULong:             return "unsigned long";
1112   case ULongLong:         return "unsigned long long";
1113   case UInt128:           return "__uint128_t";
1114   case Float:             return "float";
1115   case Double:            return "double";
1116   case LongDouble:        return "long double";
1117   case WChar_S:
1118   case WChar_U:           return "wchar_t";
1119   case Char16:            return "char16_t";
1120   case Char32:            return "char32_t";
1121   case NullPtr:           return "nullptr_t";
1122   case Overload:          return "<overloaded function type>";
1123   case Dependent:         return "<dependent type>";
1124   case ObjCId:            return "id";
1125   case ObjCClass:         return "Class";
1126   case ObjCSel:           return "SEL";
1127   }
1128
1129   llvm_unreachable("Invalid builtin type.");
1130   return 0;
1131 }
1132
1133 QualType QualType::getNonLValueExprType(ASTContext &Context) const {
1134   if (const ReferenceType *RefType = getTypePtr()->getAs<ReferenceType>())
1135     return RefType->getPointeeType();
1136
1137   // C++0x [basic.lval]:
1138   //   Class prvalues can have cv-qualified types; non-class prvalues always
1139   //   have cv-unqualified types.
1140   //
1141   // See also C99 6.3.2.1p2.
1142   if (!Context.getLangOptions().CPlusPlus ||
1143       (!getTypePtr()->isDependentType() && !getTypePtr()->isRecordType()))
1144     return getUnqualifiedType();
1145
1146   return *this;
1147 }
1148
1149 llvm::StringRef FunctionType::getNameForCallConv(CallingConv CC) {
1150   switch (CC) {
1151   case CC_Default:
1152     llvm_unreachable("no name for default cc");
1153     return "";
1154
1155   case CC_C: return "cdecl";
1156   case CC_X86StdCall: return "stdcall";
1157   case CC_X86FastCall: return "fastcall";
1158   case CC_X86ThisCall: return "thiscall";
1159   case CC_X86Pascal: return "pascal";
1160   }
1161
1162   llvm_unreachable("Invalid calling convention.");
1163   return "";
1164 }
1165
1166 FunctionProtoType::FunctionProtoType(QualType result, const QualType *args,
1167                                      unsigned numArgs, QualType canonical,
1168                                      const ExtProtoInfo &epi)
1169   : FunctionType(FunctionProto, result, epi.Variadic, epi.TypeQuals,
1170                  epi.RefQualifier, canonical,
1171                  result->isDependentType(),
1172                  result->isVariablyModifiedType(),
1173                  result->containsUnexpandedParameterPack(),
1174                  epi.ExtInfo),
1175     NumArgs(numArgs), NumExceptions(epi.NumExceptions),
1176     HasExceptionSpec(epi.HasExceptionSpec),
1177     HasAnyExceptionSpec(epi.HasAnyExceptionSpec)
1178 {
1179   // Fill in the trailing argument array.
1180   QualType *argSlot = reinterpret_cast<QualType*>(this+1);
1181   for (unsigned i = 0; i != numArgs; ++i) {
1182     if (args[i]->isDependentType())
1183       setDependent();
1184
1185     if (args[i]->containsUnexpandedParameterPack())
1186       setContainsUnexpandedParameterPack();
1187
1188     argSlot[i] = args[i];
1189   }
1190
1191   // Fill in the exception array.
1192   QualType *exnSlot = argSlot + numArgs;
1193   for (unsigned i = 0, e = epi.NumExceptions; i != e; ++i) {
1194     if (epi.Exceptions[i]->isDependentType())
1195       setDependent();
1196
1197     if (epi.Exceptions[i]->containsUnexpandedParameterPack())
1198       setContainsUnexpandedParameterPack();
1199
1200     exnSlot[i] = epi.Exceptions[i];
1201   }
1202 }
1203
1204 bool FunctionProtoType::isTemplateVariadic() const {
1205   for (unsigned ArgIdx = getNumArgs(); ArgIdx; --ArgIdx)
1206     if (isa<PackExpansionType>(getArgType(ArgIdx - 1)))
1207       return true;
1208
1209   return false;
1210 }
1211
1212 void FunctionProtoType::Profile(llvm::FoldingSetNodeID &ID, QualType Result,
1213                                 const QualType *ArgTys, unsigned NumArgs,
1214                                 const ExtProtoInfo &epi) {
1215   ID.AddPointer(Result.getAsOpaquePtr());
1216   for (unsigned i = 0; i != NumArgs; ++i)
1217     ID.AddPointer(ArgTys[i].getAsOpaquePtr());
1218   ID.AddBoolean(epi.Variadic);
1219   ID.AddInteger(epi.TypeQuals);
1220   ID.AddInteger(epi.RefQualifier);
1221   if (epi.HasExceptionSpec) {
1222     ID.AddBoolean(epi.HasAnyExceptionSpec);
1223     for (unsigned i = 0; i != epi.NumExceptions; ++i)
1224       ID.AddPointer(epi.Exceptions[i].getAsOpaquePtr());
1225   }
1226   epi.ExtInfo.Profile(ID);
1227 }
1228
1229 void FunctionProtoType::Profile(llvm::FoldingSetNodeID &ID) {
1230   Profile(ID, getResultType(), arg_type_begin(), NumArgs, getExtProtoInfo());
1231 }
1232
1233 QualType TypedefType::desugar() const {
1234   return getDecl()->getUnderlyingType();
1235 }
1236
1237 TypeOfExprType::TypeOfExprType(Expr *E, QualType can)
1238   : Type(TypeOfExpr, can, E->isTypeDependent(),
1239          E->getType()->isVariablyModifiedType(),
1240          E->containsUnexpandedParameterPack()),
1241     TOExpr(E) {
1242 }
1243
1244 QualType TypeOfExprType::desugar() const {
1245   return getUnderlyingExpr()->getType();
1246 }
1247
1248 void DependentTypeOfExprType::Profile(llvm::FoldingSetNodeID &ID,
1249                                       const ASTContext &Context, Expr *E) {
1250   E->Profile(ID, Context, true);
1251 }
1252
1253 DecltypeType::DecltypeType(Expr *E, QualType underlyingType, QualType can)
1254   : Type(Decltype, can, E->isTypeDependent(),
1255          E->getType()->isVariablyModifiedType(),
1256          E->containsUnexpandedParameterPack()),
1257     E(E),
1258   UnderlyingType(underlyingType) {
1259 }
1260
1261 DependentDecltypeType::DependentDecltypeType(const ASTContext &Context, Expr *E)
1262   : DecltypeType(E, Context.DependentTy), Context(Context) { }
1263
1264 void DependentDecltypeType::Profile(llvm::FoldingSetNodeID &ID,
1265                                     const ASTContext &Context, Expr *E) {
1266   E->Profile(ID, Context, true);
1267 }
1268
1269 TagType::TagType(TypeClass TC, const TagDecl *D, QualType can)
1270   : Type(TC, can, D->isDependentType(), /*VariablyModified=*/false,
1271          /*ContainsUnexpandedParameterPack=*/false),
1272     decl(const_cast<TagDecl*>(D)) {}
1273
1274 static TagDecl *getInterestingTagDecl(TagDecl *decl) {
1275   for (TagDecl::redecl_iterator I = decl->redecls_begin(),
1276                                 E = decl->redecls_end();
1277        I != E; ++I) {
1278     if (I->isDefinition() || I->isBeingDefined())
1279       return *I;
1280   }
1281   // If there's no definition (not even in progress), return what we have.
1282   return decl;
1283 }
1284
1285 TagDecl *TagType::getDecl() const {
1286   return getInterestingTagDecl(decl);
1287 }
1288
1289 bool TagType::isBeingDefined() const {
1290   return getDecl()->isBeingDefined();
1291 }
1292
1293 CXXRecordDecl *InjectedClassNameType::getDecl() const {
1294   return cast<CXXRecordDecl>(getInterestingTagDecl(Decl));
1295 }
1296
1297 bool RecordType::classof(const TagType *TT) {
1298   return isa<RecordDecl>(TT->getDecl());
1299 }
1300
1301 bool EnumType::classof(const TagType *TT) {
1302   return isa<EnumDecl>(TT->getDecl());
1303 }
1304
1305 SubstTemplateTypeParmPackType::
1306 SubstTemplateTypeParmPackType(const TemplateTypeParmType *Param,
1307                               QualType Canon,
1308                               const TemplateArgument &ArgPack)
1309   : Type(SubstTemplateTypeParmPack, Canon, true, false, true), Replaced(Param),
1310     Arguments(ArgPack.pack_begin()), NumArguments(ArgPack.pack_size())
1311 {
1312 }
1313
1314 TemplateArgument SubstTemplateTypeParmPackType::getArgumentPack() const {
1315   return TemplateArgument(Arguments, NumArguments);
1316 }
1317
1318 void SubstTemplateTypeParmPackType::Profile(llvm::FoldingSetNodeID &ID) {
1319   Profile(ID, getReplacedParameter(), getArgumentPack());
1320 }
1321
1322 void SubstTemplateTypeParmPackType::Profile(llvm::FoldingSetNodeID &ID,
1323                                            const TemplateTypeParmType *Replaced,
1324                                             const TemplateArgument &ArgPack) {
1325   ID.AddPointer(Replaced);
1326   ID.AddInteger(ArgPack.pack_size());
1327   for (TemplateArgument::pack_iterator P = ArgPack.pack_begin(),
1328                                     PEnd = ArgPack.pack_end();
1329        P != PEnd; ++P)
1330     ID.AddPointer(P->getAsType().getAsOpaquePtr());
1331 }
1332
1333 bool TemplateSpecializationType::
1334 anyDependentTemplateArguments(const TemplateArgumentListInfo &Args) {
1335   return anyDependentTemplateArguments(Args.getArgumentArray(), Args.size());
1336 }
1337
1338 bool TemplateSpecializationType::
1339 anyDependentTemplateArguments(const TemplateArgumentLoc *Args, unsigned N) {
1340   for (unsigned i = 0; i != N; ++i)
1341     if (Args[i].getArgument().isDependent())
1342       return true;
1343   return false;
1344 }
1345
1346 bool TemplateSpecializationType::
1347 anyDependentTemplateArguments(const TemplateArgument *Args, unsigned N) {
1348   for (unsigned i = 0; i != N; ++i)
1349     if (Args[i].isDependent())
1350       return true;
1351   return false;
1352 }
1353
1354 TemplateSpecializationType::
1355 TemplateSpecializationType(TemplateName T,
1356                            const TemplateArgument *Args,
1357                            unsigned NumArgs, QualType Canon)
1358   : Type(TemplateSpecialization,
1359          Canon.isNull()? QualType(this, 0) : Canon,
1360          T.isDependent(), false,
1361          T.containsUnexpandedParameterPack()),
1362     Template(T), NumArgs(NumArgs)
1363 {
1364   assert((!Canon.isNull() ||
1365           T.isDependent() || anyDependentTemplateArguments(Args, NumArgs)) &&
1366          "No canonical type for non-dependent class template specialization");
1367
1368   TemplateArgument *TemplateArgs
1369     = reinterpret_cast<TemplateArgument *>(this + 1);
1370   for (unsigned Arg = 0; Arg < NumArgs; ++Arg) {
1371     // Update dependent and variably-modified bits.
1372     if (Args[Arg].isDependent())
1373       setDependent();
1374     if (Args[Arg].getKind() == TemplateArgument::Type &&
1375         Args[Arg].getAsType()->isVariablyModifiedType())
1376       setVariablyModified();
1377     if (Args[Arg].containsUnexpandedParameterPack())
1378       setContainsUnexpandedParameterPack();
1379
1380     new (&TemplateArgs[Arg]) TemplateArgument(Args[Arg]);
1381   }
1382 }
1383
1384 void
1385 TemplateSpecializationType::Profile(llvm::FoldingSetNodeID &ID,
1386                                     TemplateName T,
1387                                     const TemplateArgument *Args,
1388                                     unsigned NumArgs,
1389                                     const ASTContext &Context) {
1390   T.Profile(ID);
1391   for (unsigned Idx = 0; Idx < NumArgs; ++Idx)
1392     Args[Idx].Profile(ID, Context);
1393 }
1394
1395 QualType
1396 QualifierCollector::apply(const ASTContext &Context, QualType QT) const {
1397   if (!hasNonFastQualifiers())
1398     return QT.withFastQualifiers(getFastQualifiers());
1399
1400   return Context.getQualifiedType(QT, *this);
1401 }
1402
1403 QualType
1404 QualifierCollector::apply(const ASTContext &Context, const Type *T) const {
1405   if (!hasNonFastQualifiers())
1406     return QualType(T, getFastQualifiers());
1407
1408   return Context.getQualifiedType(T, *this);
1409 }
1410
1411 void ObjCObjectTypeImpl::Profile(llvm::FoldingSetNodeID &ID,
1412                                  QualType BaseType,
1413                                  ObjCProtocolDecl * const *Protocols,
1414                                  unsigned NumProtocols) {
1415   ID.AddPointer(BaseType.getAsOpaquePtr());
1416   for (unsigned i = 0; i != NumProtocols; i++)
1417     ID.AddPointer(Protocols[i]);
1418 }
1419
1420 void ObjCObjectTypeImpl::Profile(llvm::FoldingSetNodeID &ID) {
1421   Profile(ID, getBaseType(), qual_begin(), getNumProtocols());
1422 }
1423
1424 namespace {
1425
1426 /// \brief The cached properties of a type.
1427 class CachedProperties {
1428   char linkage;
1429   char visibility;
1430   bool local;
1431
1432 public:
1433   CachedProperties(Linkage linkage, Visibility visibility, bool local)
1434     : linkage(linkage), visibility(visibility), local(local) {}
1435
1436   Linkage getLinkage() const { return (Linkage) linkage; }
1437   Visibility getVisibility() const { return (Visibility) visibility; }
1438   bool hasLocalOrUnnamedType() const { return local; }
1439
1440   friend CachedProperties merge(CachedProperties L, CachedProperties R) {
1441     return CachedProperties(minLinkage(L.getLinkage(), R.getLinkage()),
1442                             minVisibility(L.getVisibility(), R.getVisibility()),
1443                          L.hasLocalOrUnnamedType() | R.hasLocalOrUnnamedType());
1444   }
1445 };
1446 }
1447
1448 static CachedProperties computeCachedProperties(const Type *T);
1449
1450 namespace clang {
1451 /// The type-property cache.  This is templated so as to be
1452 /// instantiated at an internal type to prevent unnecessary symbol
1453 /// leakage.
1454 template <class Private> class TypePropertyCache {
1455 public:
1456   static CachedProperties get(QualType T) {
1457     return get(T.getTypePtr());
1458   }
1459
1460   static CachedProperties get(const Type *T) {
1461     ensure(T);
1462     return CachedProperties(T->TypeBits.getLinkage(),
1463                             T->TypeBits.getVisibility(),
1464                             T->TypeBits.hasLocalOrUnnamedType());
1465   }
1466
1467   static void ensure(const Type *T) {
1468     // If the cache is valid, we're okay.
1469     if (T->TypeBits.isCacheValid()) return;
1470
1471     // If this type is non-canonical, ask its canonical type for the
1472     // relevant information.
1473     if (!T->isCanonicalUnqualified()) {
1474       const Type *CT = T->getCanonicalTypeInternal().getTypePtr();
1475       ensure(CT);
1476       T->TypeBits.CacheValidAndVisibility =
1477         CT->TypeBits.CacheValidAndVisibility;
1478       T->TypeBits.CachedLinkage = CT->TypeBits.CachedLinkage;
1479       T->TypeBits.CachedLocalOrUnnamed = CT->TypeBits.CachedLocalOrUnnamed;
1480       return;
1481     }
1482
1483     // Compute the cached properties and then set the cache.
1484     CachedProperties Result = computeCachedProperties(T);
1485     T->TypeBits.CacheValidAndVisibility = Result.getVisibility() + 1U;
1486     assert(T->TypeBits.isCacheValid() &&
1487            T->TypeBits.getVisibility() == Result.getVisibility());
1488     T->TypeBits.CachedLinkage = Result.getLinkage();
1489     T->TypeBits.CachedLocalOrUnnamed = Result.hasLocalOrUnnamedType();
1490   }
1491 };
1492 }
1493
1494 // Instantiate the friend template at a private class.  In a
1495 // reasonable implementation, these symbols will be internal.
1496 // It is terrible that this is the best way to accomplish this.
1497 namespace { class Private {}; }
1498 typedef TypePropertyCache<Private> Cache;
1499
1500 static CachedProperties computeCachedProperties(const Type *T) {
1501   switch (T->getTypeClass()) {
1502 #define TYPE(Class,Base)
1503 #define NON_CANONICAL_TYPE(Class,Base) case Type::Class:
1504 #include "clang/AST/TypeNodes.def"
1505     llvm_unreachable("didn't expect a non-canonical type here");
1506
1507 #define TYPE(Class,Base)
1508 #define DEPENDENT_TYPE(Class,Base) case Type::Class:
1509 #define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class,Base) case Type::Class:
1510 #include "clang/AST/TypeNodes.def"
1511     // Treat dependent types as external.
1512     assert(T->isDependentType());
1513     return CachedProperties(ExternalLinkage, DefaultVisibility, false);
1514
1515   case Type::Builtin:
1516     // C++ [basic.link]p8:
1517     //   A type is said to have linkage if and only if:
1518     //     - it is a fundamental type (3.9.1); or
1519     return CachedProperties(ExternalLinkage, DefaultVisibility, false);
1520
1521   case Type::Record:
1522   case Type::Enum: {
1523     const TagDecl *Tag = cast<TagType>(T)->getDecl();
1524
1525     // C++ [basic.link]p8:
1526     //     - it is a class or enumeration type that is named (or has a name
1527     //       for linkage purposes (7.1.3)) and the name has linkage; or
1528     //     -  it is a specialization of a class template (14); or
1529     NamedDecl::LinkageInfo LV = Tag->getLinkageAndVisibility();
1530     bool IsLocalOrUnnamed =
1531       Tag->getDeclContext()->isFunctionOrMethod() ||
1532       (!Tag->getIdentifier() && !Tag->getTypedefForAnonDecl());
1533     return CachedProperties(LV.linkage(), LV.visibility(), IsLocalOrUnnamed);
1534   }
1535
1536     // C++ [basic.link]p8:
1537     //   - it is a compound type (3.9.2) other than a class or enumeration,
1538     //     compounded exclusively from types that have linkage; or
1539   case Type::Complex:
1540     return Cache::get(cast<ComplexType>(T)->getElementType());
1541   case Type::Pointer:
1542     return Cache::get(cast<PointerType>(T)->getPointeeType());
1543   case Type::BlockPointer:
1544     return Cache::get(cast<BlockPointerType>(T)->getPointeeType());
1545   case Type::LValueReference:
1546   case Type::RValueReference:
1547     return Cache::get(cast<ReferenceType>(T)->getPointeeType());
1548   case Type::MemberPointer: {
1549     const MemberPointerType *MPT = cast<MemberPointerType>(T);
1550     return merge(Cache::get(MPT->getClass()),
1551                  Cache::get(MPT->getPointeeType()));
1552   }
1553   case Type::ConstantArray:
1554   case Type::IncompleteArray:
1555   case Type::VariableArray:
1556     return Cache::get(cast<ArrayType>(T)->getElementType());
1557   case Type::Vector:
1558   case Type::ExtVector:
1559     return Cache::get(cast<VectorType>(T)->getElementType());
1560   case Type::FunctionNoProto:
1561     return Cache::get(cast<FunctionType>(T)->getResultType());
1562   case Type::FunctionProto: {
1563     const FunctionProtoType *FPT = cast<FunctionProtoType>(T);
1564     CachedProperties result = Cache::get(FPT->getResultType());
1565     for (FunctionProtoType::arg_type_iterator ai = FPT->arg_type_begin(),
1566            ae = FPT->arg_type_end(); ai != ae; ++ai)
1567       result = merge(result, Cache::get(*ai));
1568     return result;
1569   }
1570   case Type::ObjCInterface: {
1571     NamedDecl::LinkageInfo LV =
1572       cast<ObjCInterfaceType>(T)->getDecl()->getLinkageAndVisibility();
1573     return CachedProperties(LV.linkage(), LV.visibility(), false);
1574   }
1575   case Type::ObjCObject:
1576     return Cache::get(cast<ObjCObjectType>(T)->getBaseType());
1577   case Type::ObjCObjectPointer:
1578     return Cache::get(cast<ObjCObjectPointerType>(T)->getPointeeType());
1579   }
1580
1581   llvm_unreachable("unhandled type class");
1582
1583   // C++ [basic.link]p8:
1584   //   Names not covered by these rules have no linkage.
1585   return CachedProperties(NoLinkage, DefaultVisibility, false);
1586 }
1587
1588 /// \brief Determine the linkage of this type.
1589 Linkage Type::getLinkage() const {
1590   Cache::ensure(this);
1591   return TypeBits.getLinkage();
1592 }
1593
1594 /// \brief Determine the linkage of this type.
1595 Visibility Type::getVisibility() const {
1596   Cache::ensure(this);
1597   return TypeBits.getVisibility();
1598 }
1599
1600 bool Type::hasUnnamedOrLocalType() const {
1601   Cache::ensure(this);
1602   return TypeBits.hasLocalOrUnnamedType();
1603 }
1604
1605 std::pair<Linkage,Visibility> Type::getLinkageAndVisibility() const {
1606   Cache::ensure(this);
1607   return std::make_pair(TypeBits.getLinkage(), TypeBits.getVisibility());
1608 }
1609
1610 void Type::ClearLinkageCache() {
1611   TypeBits.CacheValidAndVisibility = 0;
1612   if (QualType(this, 0) != CanonicalType)
1613     CanonicalType->TypeBits.CacheValidAndVisibility = 0;
1614 }
1615
1616 bool Type::hasSizedVLAType() const {
1617   if (!isVariablyModifiedType()) return false;
1618
1619   if (const PointerType *ptr = getAs<PointerType>())
1620     return ptr->getPointeeType()->hasSizedVLAType();
1621   if (const ReferenceType *ref = getAs<ReferenceType>())
1622     return ref->getPointeeType()->hasSizedVLAType();
1623   if (const ArrayType *arr = getAsArrayTypeUnsafe()) {
1624     if (isa<VariableArrayType>(arr) &&
1625         cast<VariableArrayType>(arr)->getSizeExpr())
1626       return true;
1627
1628     return arr->getElementType()->hasSizedVLAType();
1629   }
1630
1631   return false;
1632 }
1633
1634 QualType::DestructionKind QualType::isDestructedTypeImpl(QualType type) {
1635   /// Currently, the only destruction kind we recognize is C++ objects
1636   /// with non-trivial destructors.
1637   const CXXRecordDecl *record =
1638     type->getBaseElementTypeUnsafe()->getAsCXXRecordDecl();
1639   if (record && !record->hasTrivialDestructor())
1640     return DK_cxx_destructor;
1641
1642   return DK_none;
1643 }