granicus.if.org Git - clang/blob - AST/ASTContext.cpp

   1 //===--- ASTContext.cpp - Context to hold long-lived AST nodes ------------===//
   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 the ASTContext interface.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/ASTContext.h"
  15 #include "clang/AST/Decl.h"
  16 #include "clang/AST/DeclObjC.h"
  17 #include "clang/Basic/TargetInfo.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/StringExtras.h"
  20 #include "llvm/Bitcode/Serialize.h"
  21 #include "llvm/Bitcode/Deserialize.h"
  22
  23 using namespace clang;
  24
  25 enum FloatingRank {
  26   FloatRank, DoubleRank, LongDoubleRank
  27 };
  28
  29 ASTContext::~ASTContext() {
  30   // Deallocate all the types.
  31   while (!Types.empty()) {
  32     if (FunctionTypeProto *FT = dyn_cast<FunctionTypeProto>(Types.back())) {
  33       // Destroy the object, but don't call delete.  These are malloc'd.
  34       FT->~FunctionTypeProto();
  35       free(FT);
  36     } else {
  37       delete Types.back();
  38     }
  39     Types.pop_back();
  40   }
  41 }
  42
  43 void ASTContext::PrintStats() const {
  44   fprintf(stderr, "*** AST Context Stats:\n");
  45   fprintf(stderr, "  %d types total.\n", (int)Types.size());
  46   unsigned NumBuiltin = 0, NumPointer = 0, NumArray = 0, NumFunctionP = 0;
  47   unsigned NumVector = 0, NumComplex = 0;
  48   unsigned NumFunctionNP = 0, NumTypeName = 0, NumTagged = 0, NumReference = 0;
  49
  50   unsigned NumTagStruct = 0, NumTagUnion = 0, NumTagEnum = 0, NumTagClass = 0;
  51   unsigned NumObjCInterfaces = 0, NumObjCQualifiedInterfaces = 0;
  52   unsigned NumObjCQualifiedIds = 0;
  53
  54   for (unsigned i = 0, e = Types.size(); i != e; ++i) {
  55     Type *T = Types[i];
  56     if (isa<BuiltinType>(T))
  57       ++NumBuiltin;
  58     else if (isa<PointerType>(T))
  59       ++NumPointer;
  60     else if (isa<ReferenceType>(T))
  61       ++NumReference;
  62     else if (isa<ComplexType>(T))
  63       ++NumComplex;
  64     else if (isa<ArrayType>(T))
  65       ++NumArray;
  66     else if (isa<VectorType>(T))
  67       ++NumVector;
  68     else if (isa<FunctionTypeNoProto>(T))
  69       ++NumFunctionNP;
  70     else if (isa<FunctionTypeProto>(T))
  71       ++NumFunctionP;
  72     else if (isa<TypedefType>(T))
  73       ++NumTypeName;
  74     else if (TagType *TT = dyn_cast<TagType>(T)) {
  75       ++NumTagged;
  76       switch (TT->getDecl()->getKind()) {
  77       default: assert(0 && "Unknown tagged type!");
  78       case Decl::Struct: ++NumTagStruct; break;
  79       case Decl::Union:  ++NumTagUnion; break;
  80       case Decl::Class:  ++NumTagClass; break;
  81       case Decl::Enum:   ++NumTagEnum; break;
  82       }
  83     } else if (isa<ObjCInterfaceType>(T))
  84       ++NumObjCInterfaces;
  85     else if (isa<ObjCQualifiedInterfaceType>(T))
  86       ++NumObjCQualifiedInterfaces;
  87     else if (isa<ObjCQualifiedIdType>(T))
  88       ++NumObjCQualifiedIds;
  89     else {
  90       QualType(T, 0).dump();
  91       assert(0 && "Unknown type!");
  92     }
  93   }
  94
  95   fprintf(stderr, "    %d builtin types\n", NumBuiltin);
  96   fprintf(stderr, "    %d pointer types\n", NumPointer);
  97   fprintf(stderr, "    %d reference types\n", NumReference);
  98   fprintf(stderr, "    %d complex types\n", NumComplex);
  99   fprintf(stderr, "    %d array types\n", NumArray);
 100   fprintf(stderr, "    %d vector types\n", NumVector);
 101   fprintf(stderr, "    %d function types with proto\n", NumFunctionP);
 102   fprintf(stderr, "    %d function types with no proto\n", NumFunctionNP);
 103   fprintf(stderr, "    %d typename (typedef) types\n", NumTypeName);
 104   fprintf(stderr, "    %d tagged types\n", NumTagged);
 105   fprintf(stderr, "      %d struct types\n", NumTagStruct);
 106   fprintf(stderr, "      %d union types\n", NumTagUnion);
 107   fprintf(stderr, "      %d class types\n", NumTagClass);
 108   fprintf(stderr, "      %d enum types\n", NumTagEnum);
 109   fprintf(stderr, "    %d interface types\n", NumObjCInterfaces);
 110   fprintf(stderr, "    %d protocol qualified interface types\n",
 111           NumObjCQualifiedInterfaces);
 112   fprintf(stderr, "    %d protocol qualified id types\n",
 113           NumObjCQualifiedIds);
 114   fprintf(stderr, "Total bytes = %d\n", int(NumBuiltin*sizeof(BuiltinType)+
 115     NumPointer*sizeof(PointerType)+NumArray*sizeof(ArrayType)+
 116     NumComplex*sizeof(ComplexType)+NumVector*sizeof(VectorType)+
 117     NumFunctionP*sizeof(FunctionTypeProto)+
 118     NumFunctionNP*sizeof(FunctionTypeNoProto)+
 119     NumTypeName*sizeof(TypedefType)+NumTagged*sizeof(TagType)));
 120 }
 121
 122
 123 void ASTContext::InitBuiltinType(QualType &R, BuiltinType::Kind K) {
 124   Types.push_back((R = QualType(new BuiltinType(K),0)).getTypePtr());
 125 }
 126
 127 void ASTContext::InitBuiltinTypes() {
 128   assert(VoidTy.isNull() && "Context reinitialized?");
 129
 130   // C99 6.2.5p19.
 131   InitBuiltinType(VoidTy,              BuiltinType::Void);
 132
 133   // C99 6.2.5p2.
 134   InitBuiltinType(BoolTy,              BuiltinType::Bool);
 135   // C99 6.2.5p3.
 136   if (Target.isCharSigned(FullSourceLoc()))
 137     InitBuiltinType(CharTy,            BuiltinType::Char_S);
 138   else
 139     InitBuiltinType(CharTy,            BuiltinType::Char_U);
 140   // C99 6.2.5p4.
 141   InitBuiltinType(SignedCharTy,        BuiltinType::SChar);
 142   InitBuiltinType(ShortTy,             BuiltinType::Short);
 143   InitBuiltinType(IntTy,               BuiltinType::Int);
 144   InitBuiltinType(LongTy,              BuiltinType::Long);
 145   InitBuiltinType(LongLongTy,          BuiltinType::LongLong);
 146
 147   // C99 6.2.5p6.
 148   InitBuiltinType(UnsignedCharTy,      BuiltinType::UChar);
 149   InitBuiltinType(UnsignedShortTy,     BuiltinType::UShort);
 150   InitBuiltinType(UnsignedIntTy,       BuiltinType::UInt);
 151   InitBuiltinType(UnsignedLongTy,      BuiltinType::ULong);
 152   InitBuiltinType(UnsignedLongLongTy,  BuiltinType::ULongLong);
 153
 154   // C99 6.2.5p10.
 155   InitBuiltinType(FloatTy,             BuiltinType::Float);
 156   InitBuiltinType(DoubleTy,            BuiltinType::Double);
 157   InitBuiltinType(LongDoubleTy,        BuiltinType::LongDouble);
 158
 159   // C99 6.2.5p11.
 160   FloatComplexTy      = getComplexType(FloatTy);
 161   DoubleComplexTy     = getComplexType(DoubleTy);
 162   LongDoubleComplexTy = getComplexType(LongDoubleTy);
 163
 164   BuiltinVaListType = QualType();
 165   ObjCIdType = QualType();
 166   IdStructType = 0;
 167   ObjCClassType = QualType();
 168   ClassStructType = 0;
 169
 170   ObjCConstantStringType = QualType();
 171
 172   // void * type
 173   VoidPtrTy = getPointerType(VoidTy);
 174 }
 175
 176 //===----------------------------------------------------------------------===//
 177 //                         Type Sizing and Analysis
 178 //===----------------------------------------------------------------------===//
 179
 180 /// getTypeSize - Return the size of the specified type, in bits.  This method
 181 /// does not work on incomplete types.
 182 std::pair<uint64_t, unsigned>
 183 ASTContext::getTypeInfo(QualType T, SourceLocation L) {
 184   T = T.getCanonicalType();
 185   uint64_t Size;
 186   unsigned Align;
 187   switch (T->getTypeClass()) {
 188   case Type::TypeName: assert(0 && "Not a canonical type!");
 189   case Type::FunctionNoProto:
 190   case Type::FunctionProto:
 191   default:
 192     assert(0 && "Incomplete types have no size!");
 193   case Type::VariableArray:
 194     assert(0 && "VLAs not implemented yet!");
 195   case Type::ConstantArray: {
 196     ConstantArrayType *CAT = cast<ConstantArrayType>(T);
 197
 198     std::pair<uint64_t, unsigned> EltInfo =
 199       getTypeInfo(CAT->getElementType(), L);
 200     Size = EltInfo.first*CAT->getSize().getZExtValue();
 201     Align = EltInfo.second;
 202     break;
 203   }
 204   case Type::OCUVector:
 205   case Type::Vector: {
 206     std::pair<uint64_t, unsigned> EltInfo =
 207       getTypeInfo(cast<VectorType>(T)->getElementType(), L);
 208     Size = EltInfo.first*cast<VectorType>(T)->getNumElements();
 209     // FIXME: Vector alignment is not the alignment of its elements.
 210     Align = EltInfo.second;
 211     break;
 212   }
 213
 214   case Type::Builtin: {
 215     // FIXME: need to use TargetInfo to derive the target specific sizes. This
 216     // implementation will suffice for play with vector support.
 217     const llvm::fltSemantics *F;
 218     switch (cast<BuiltinType>(T)->getKind()) {
 219     default: assert(0 && "Unknown builtin type!");
 220     case BuiltinType::Void:
 221       assert(0 && "Incomplete types have no size!");
 222     case BuiltinType::Bool:
 223       Target.getBoolInfo(Size, Align, getFullLoc(L));
 224       break;
 225     case BuiltinType::Char_S:
 226     case BuiltinType::Char_U:
 227     case BuiltinType::UChar:
 228     case BuiltinType::SChar:
 229       Target.getCharInfo(Size, Align, getFullLoc(L));
 230       break;
 231     case BuiltinType::UShort:
 232     case BuiltinType::Short:
 233       Target.getShortInfo(Size, Align, getFullLoc(L));
 234       break;
 235     case BuiltinType::UInt:
 236     case BuiltinType::Int:
 237       Target.getIntInfo(Size, Align, getFullLoc(L));
 238       break;
 239     case BuiltinType::ULong:
 240     case BuiltinType::Long:
 241       Target.getLongInfo(Size, Align, getFullLoc(L));
 242       break;
 243     case BuiltinType::ULongLong:
 244     case BuiltinType::LongLong:
 245       Target.getLongLongInfo(Size, Align, getFullLoc(L));
 246       break;
 247     case BuiltinType::Float:
 248       Target.getFloatInfo(Size, Align, F, getFullLoc(L));
 249       break;
 250     case BuiltinType::Double:
 251       Target.getDoubleInfo(Size, Align, F, getFullLoc(L));
 252       break;
 253     case BuiltinType::LongDouble:
 254       Target.getLongDoubleInfo(Size, Align, F, getFullLoc(L));
 255       break;
 256     }
 257     break;
 258   }
 259   case Type::ASQual:
 260     return getTypeInfo(cast<ASQualType>(T)->getBaseType(), L);
 261   case Type::ObjCQualifiedId:
 262     Target.getPointerInfo(Size, Align, getFullLoc(L));
 263     break;
 264   case Type::Pointer:
 265     Target.getPointerInfo(Size, Align, getFullLoc(L));
 266     break;
 267   case Type::Reference:
 268     // "When applied to a reference or a reference type, the result is the size
 269     // of the referenced type." C++98 5.3.3p2: expr.sizeof.
 270     // FIXME: This is wrong for struct layout: a reference in a struct has
 271     // pointer size.
 272     return getTypeInfo(cast<ReferenceType>(T)->getReferenceeType(), L);
 273
 274   case Type::Complex: {
 275     // Complex types have the same alignment as their elements, but twice the
 276     // size.
 277     std::pair<uint64_t, unsigned> EltInfo =
 278       getTypeInfo(cast<ComplexType>(T)->getElementType(), L);
 279     Size = EltInfo.first*2;
 280     Align = EltInfo.second;
 281     break;
 282   }
 283   case Type::Tagged:
 284     TagType *TT = cast<TagType>(T);
 285     if (RecordType *RT = dyn_cast<RecordType>(TT)) {
 286       const ASTRecordLayout &Layout = getASTRecordLayout(RT->getDecl(), L);
 287       Size = Layout.getSize();
 288       Align = Layout.getAlignment();
 289     } else if (EnumDecl *ED = dyn_cast<EnumDecl>(TT->getDecl())) {
 290       return getTypeInfo(ED->getIntegerType(), L);
 291     } else {
 292       assert(0 && "Unimplemented type sizes!");
 293     }
 294     break;
 295   }
 296
 297   assert(Align && (Align & (Align-1)) == 0 && "Alignment must be power of 2");
 298   return std::make_pair(Size, Align);
 299 }
 300
 301 /// getASTRecordLayout - Get or compute information about the layout of the
 302 /// specified record (struct/union/class), which indicates its size and field
 303 /// position information.
 304 const ASTRecordLayout &ASTContext::getASTRecordLayout(const RecordDecl *D,
 305                                                       SourceLocation L) {
 306   assert(D->isDefinition() && "Cannot get layout of forward declarations!");
 307
 308   // Look up this layout, if already laid out, return what we have.
 309   const ASTRecordLayout *&Entry = ASTRecordLayouts[D];
 310   if (Entry) return *Entry;
 311
 312   // Allocate and assign into ASTRecordLayouts here.  The "Entry" reference can
 313   // be invalidated (dangle) if the ASTRecordLayouts hashtable is inserted into.
 314   ASTRecordLayout *NewEntry = new ASTRecordLayout();
 315   Entry = NewEntry;
 316
 317   uint64_t *FieldOffsets = new uint64_t[D->getNumMembers()];
 318   uint64_t RecordSize = 0;
 319   unsigned RecordAlign = 8;  // Default alignment = 1 byte = 8 bits.
 320
 321   if (D->getKind() != Decl::Union) {
 322     if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
 323       RecordAlign = std::max(RecordAlign, AA->getAlignment());
 324
 325     bool StructIsPacked = D->getAttr<PackedAttr>();
 326
 327     // Layout each field, for now, just sequentially, respecting alignment.  In
 328     // the future, this will need to be tweakable by targets.
 329     for (unsigned i = 0, e = D->getNumMembers(); i != e; ++i) {
 330       const FieldDecl *FD = D->getMember(i);
 331       bool FieldIsPacked = StructIsPacked || FD->getAttr<PackedAttr>();
 332       uint64_t FieldSize;
 333       unsigned FieldAlign;
 334
 335       if (const Expr *BitWidthExpr = FD->getBitWidth()) {
 336         llvm::APSInt I(32);
 337         bool BitWidthIsICE =
 338           BitWidthExpr->isIntegerConstantExpr(I, *this);
 339         assert (BitWidthIsICE  && "Invalid BitField size expression");
 340         FieldSize = I.getZExtValue();
 341
 342         std::pair<uint64_t, unsigned> TypeInfo = getTypeInfo(FD->getType(), L);
 343         uint64_t TypeSize = TypeInfo.first;
 344
 345         if (const AlignedAttr *AA = FD->getAttr<AlignedAttr>())
 346           FieldAlign = AA->getAlignment();
 347         else if (FieldIsPacked)
 348           FieldAlign = 8;
 349         else {
 350           // FIXME: This is X86 specific, use 32-bit alignment for long long.
 351           if (FD->getType()->isIntegerType() && TypeInfo.second > 32)
 352             FieldAlign = 32;
 353           else
 354             FieldAlign = TypeInfo.second;
 355         }
 356
 357         // Check if we need to add padding to give the field the correct
 358         // alignment.
 359         if (RecordSize % FieldAlign + FieldSize > TypeSize)
 360           RecordSize = (RecordSize+FieldAlign-1) & ~(FieldAlign-1);
 361
 362       } else {
 363         if (FD->getType()->isIncompleteType()) {
 364           // This must be a flexible array member; we can't directly
 365           // query getTypeInfo about these, so we figure it out here.
 366           // Flexible array members don't have any size, but they
 367           // have to be aligned appropriately for their element type.
 368
 369           if (const AlignedAttr *AA = FD->getAttr<AlignedAttr>())
 370             FieldAlign = AA->getAlignment();
 371           else if (FieldIsPacked)
 372             FieldAlign = 8;
 373           else {
 374             const ArrayType* ATy = FD->getType()->getAsArrayType();
 375             FieldAlign = getTypeAlign(ATy->getElementType(), L);
 376           }
 377           FieldSize = 0;
 378         } else {
 379           std::pair<uint64_t, unsigned> FieldInfo = getTypeInfo(FD->getType(), L);
 380           FieldSize = FieldInfo.first;
 381
 382           if (const AlignedAttr *AA = FD->getAttr<AlignedAttr>())
 383             FieldAlign = AA->getAlignment();
 384           else if (FieldIsPacked)
 385             FieldAlign = 8;
 386           else
 387             FieldAlign = FieldInfo.second;
 388         }
 389
 390         // Round up the current record size to the field's alignment boundary.
 391         RecordSize = (RecordSize+FieldAlign-1) & ~(FieldAlign-1);
 392       }
 393
 394       // Place this field at the current location.
 395       FieldOffsets[i] = RecordSize;
 396
 397       // Reserve space for this field.
 398       RecordSize += FieldSize;
 399
 400       // Remember max struct/class alignment.
 401       RecordAlign = std::max(RecordAlign, FieldAlign);
 402     }
 403
 404     // Finally, round the size of the total struct up to the alignment of the
 405     // struct itself.
 406     RecordSize = (RecordSize+RecordAlign-1) & ~(RecordAlign-1);
 407   } else {
 408     // Union layout just puts each member at the start of the record.
 409     for (unsigned i = 0, e = D->getNumMembers(); i != e; ++i) {
 410       const FieldDecl *FD = D->getMember(i);
 411       std::pair<uint64_t, unsigned> FieldInfo = getTypeInfo(FD->getType(), L);
 412       uint64_t FieldSize = FieldInfo.first;
 413       unsigned FieldAlign = FieldInfo.second;
 414
 415       // FIXME: This is X86 specific, use 32-bit alignment for long long.
 416       if (FD->getType()->isIntegerType() && FieldAlign > 32)
 417         FieldAlign = 32;
 418
 419       // Round up the current record size to the field's alignment boundary.
 420       RecordSize = std::max(RecordSize, FieldSize);
 421
 422       // Place this field at the start of the record.
 423       FieldOffsets[i] = 0;
 424
 425       // Remember max struct/class alignment.
 426       RecordAlign = std::max(RecordAlign, FieldAlign);
 427     }
 428   }
 429
 430   NewEntry->SetLayout(RecordSize, RecordAlign, FieldOffsets);
 431   return *NewEntry;
 432 }
 433
 434 //===----------------------------------------------------------------------===//
 435 //                   Type creation/memoization methods
 436 //===----------------------------------------------------------------------===//
 437
 438 QualType ASTContext::getASQualType(QualType T, unsigned AddressSpace) {
 439   // Check if we've already instantiated an address space qual'd type of this type.
 440   llvm::FoldingSetNodeID ID;
 441   ASQualType::Profile(ID, T, AddressSpace);
 442   void *InsertPos = 0;
 443   if (ASQualType *ASQy = ASQualTypes.FindNodeOrInsertPos(ID, InsertPos))
 444     return QualType(ASQy, 0);
 445
 446   // If the base type isn't canonical, this won't be a canonical type either,
 447   // so fill in the canonical type field.
 448   QualType Canonical;
 449   if (!T->isCanonical()) {
 450     Canonical = getASQualType(T.getCanonicalType(), AddressSpace);
 451
 452     // Get the new insert position for the node we care about.
 453     ASQualType *NewIP = ASQualTypes.FindNodeOrInsertPos(ID, InsertPos);
 454     assert(NewIP == 0 && "Shouldn't be in the map!");
 455   }
 456   ASQualType *New = new ASQualType(T, Canonical, AddressSpace);
 457   ASQualTypes.InsertNode(New, InsertPos);
 458   Types.push_back(New);
 459   return QualType(New, 0);
 460 }
 461
 462
 463 /// getComplexType - Return the uniqued reference to the type for a complex
 464 /// number with the specified element type.
 465 QualType ASTContext::getComplexType(QualType T) {
 466   // Unique pointers, to guarantee there is only one pointer of a particular
 467   // structure.
 468   llvm::FoldingSetNodeID ID;
 469   ComplexType::Profile(ID, T);
 470
 471   void *InsertPos = 0;
 472   if (ComplexType *CT = ComplexTypes.FindNodeOrInsertPos(ID, InsertPos))
 473     return QualType(CT, 0);
 474
 475   // If the pointee type isn't canonical, this won't be a canonical type either,
 476   // so fill in the canonical type field.
 477   QualType Canonical;
 478   if (!T->isCanonical()) {
 479     Canonical = getComplexType(T.getCanonicalType());
 480
 481     // Get the new insert position for the node we care about.
 482     ComplexType *NewIP = ComplexTypes.FindNodeOrInsertPos(ID, InsertPos);
 483     assert(NewIP == 0 && "Shouldn't be in the map!");
 484   }
 485   ComplexType *New = new ComplexType(T, Canonical);
 486   Types.push_back(New);
 487   ComplexTypes.InsertNode(New, InsertPos);
 488   return QualType(New, 0);
 489 }
 490
 491
 492 /// getPointerType - Return the uniqued reference to the type for a pointer to
 493 /// the specified type.
 494 QualType ASTContext::getPointerType(QualType T) {
 495   // Unique pointers, to guarantee there is only one pointer of a particular
 496   // structure.
 497   llvm::FoldingSetNodeID ID;
 498   PointerType::Profile(ID, T);
 499
 500   void *InsertPos = 0;
 501   if (PointerType *PT = PointerTypes.FindNodeOrInsertPos(ID, InsertPos))
 502     return QualType(PT, 0);
 503
 504   // If the pointee type isn't canonical, this won't be a canonical type either,
 505   // so fill in the canonical type field.
 506   QualType Canonical;
 507   if (!T->isCanonical()) {
 508     Canonical = getPointerType(T.getCanonicalType());
 509
 510     // Get the new insert position for the node we care about.
 511     PointerType *NewIP = PointerTypes.FindNodeOrInsertPos(ID, InsertPos);
 512     assert(NewIP == 0 && "Shouldn't be in the map!");
 513   }
 514   PointerType *New = new PointerType(T, Canonical);
 515   Types.push_back(New);
 516   PointerTypes.InsertNode(New, InsertPos);
 517   return QualType(New, 0);
 518 }
 519
 520 /// getReferenceType - Return the uniqued reference to the type for a reference
 521 /// to the specified type.
 522 QualType ASTContext::getReferenceType(QualType T) {
 523   // Unique pointers, to guarantee there is only one pointer of a particular
 524   // structure.
 525   llvm::FoldingSetNodeID ID;
 526   ReferenceType::Profile(ID, T);
 527
 528   void *InsertPos = 0;
 529   if (ReferenceType *RT = ReferenceTypes.FindNodeOrInsertPos(ID, InsertPos))
 530     return QualType(RT, 0);
 531
 532   // If the referencee type isn't canonical, this won't be a canonical type
 533   // either, so fill in the canonical type field.
 534   QualType Canonical;
 535   if (!T->isCanonical()) {
 536     Canonical = getReferenceType(T.getCanonicalType());
 537
 538     // Get the new insert position for the node we care about.
 539     ReferenceType *NewIP = ReferenceTypes.FindNodeOrInsertPos(ID, InsertPos);
 540     assert(NewIP == 0 && "Shouldn't be in the map!");
 541   }
 542
 543   ReferenceType *New = new ReferenceType(T, Canonical);
 544   Types.push_back(New);
 545   ReferenceTypes.InsertNode(New, InsertPos);
 546   return QualType(New, 0);
 547 }
 548
 549 /// getConstantArrayType - Return the unique reference to the type for an
 550 /// array of the specified element type.
 551 QualType ASTContext::getConstantArrayType(QualType EltTy,
 552                                           const llvm::APInt &ArySize,
 553                                           ArrayType::ArraySizeModifier ASM,
 554                                           unsigned EltTypeQuals) {
 555   llvm::FoldingSetNodeID ID;
 556   ConstantArrayType::Profile(ID, EltTy, ArySize);
 557
 558   void *InsertPos = 0;
 559   if (ConstantArrayType *ATP =
 560       ConstantArrayTypes.FindNodeOrInsertPos(ID, InsertPos))
 561     return QualType(ATP, 0);
 562
 563   // If the element type isn't canonical, this won't be a canonical type either,
 564   // so fill in the canonical type field.
 565   QualType Canonical;
 566   if (!EltTy->isCanonical()) {
 567     Canonical = getConstantArrayType(EltTy.getCanonicalType(), ArySize,
 568                                      ASM, EltTypeQuals);
 569     // Get the new insert position for the node we care about.
 570     ConstantArrayType *NewIP =
 571       ConstantArrayTypes.FindNodeOrInsertPos(ID, InsertPos);
 572
 573     assert(NewIP == 0 && "Shouldn't be in the map!");
 574   }
 575
 576   ConstantArrayType *New = new ConstantArrayType(EltTy, Canonical, ArySize,
 577                                                  ASM, EltTypeQuals);
 578   ConstantArrayTypes.InsertNode(New, InsertPos);
 579   Types.push_back(New);
 580   return QualType(New, 0);
 581 }
 582
 583 /// getVariableArrayType - Returns a non-unique reference to the type for a
 584 /// variable array of the specified element type.
 585 QualType ASTContext::getVariableArrayType(QualType EltTy, Expr *NumElts,
 586                                           ArrayType::ArraySizeModifier ASM,
 587                                           unsigned EltTypeQuals) {
 588   // Since we don't unique expressions, it isn't possible to unique VLA's
 589   // that have an expression provided for their size.
 590
 591   VariableArrayType *New = new VariableArrayType(EltTy, QualType(), NumElts,
 592                                                  ASM, EltTypeQuals);
 593
 594   VariableArrayTypes.push_back(New);
 595   Types.push_back(New);
 596   return QualType(New, 0);
 597 }
 598
 599 QualType ASTContext::getIncompleteArrayType(QualType EltTy,
 600                                             ArrayType::ArraySizeModifier ASM,
 601                                             unsigned EltTypeQuals) {
 602   llvm::FoldingSetNodeID ID;
 603   IncompleteArrayType::Profile(ID, EltTy);
 604
 605   void *InsertPos = 0;
 606   if (IncompleteArrayType *ATP =
 607        IncompleteArrayTypes.FindNodeOrInsertPos(ID, InsertPos))
 608     return QualType(ATP, 0);
 609
 610   // If the element type isn't canonical, this won't be a canonical type
 611   // either, so fill in the canonical type field.
 612   QualType Canonical;
 613
 614   if (!EltTy->isCanonical()) {
 615     Canonical = getIncompleteArrayType(EltTy.getCanonicalType(),
 616                                        ASM, EltTypeQuals);
 617
 618     // Get the new insert position for the node we care about.
 619     IncompleteArrayType *NewIP =
 620       IncompleteArrayTypes.FindNodeOrInsertPos(ID, InsertPos);
 621
 622     assert(NewIP == 0 && "Shouldn't be in the map!");
 623   }
 624
 625   IncompleteArrayType *New = new IncompleteArrayType(EltTy, Canonical,
 626                                                      ASM, EltTypeQuals);
 627
 628   IncompleteArrayTypes.InsertNode(New, InsertPos);
 629   Types.push_back(New);
 630   return QualType(New, 0);
 631 }
 632
 633 /// getVectorType - Return the unique reference to a vector type of
 634 /// the specified element type and size. VectorType must be a built-in type.
 635 QualType ASTContext::getVectorType(QualType vecType, unsigned NumElts) {
 636   BuiltinType *baseType;
 637
 638   baseType = dyn_cast<BuiltinType>(vecType.getCanonicalType().getTypePtr());
 639   assert(baseType != 0 && "getVectorType(): Expecting a built-in type");
 640
 641   // Check if we've already instantiated a vector of this type.
 642   llvm::FoldingSetNodeID ID;
 643   VectorType::Profile(ID, vecType, NumElts, Type::Vector);
 644   void *InsertPos = 0;
 645   if (VectorType *VTP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos))
 646     return QualType(VTP, 0);
 647
 648   // If the element type isn't canonical, this won't be a canonical type either,
 649   // so fill in the canonical type field.
 650   QualType Canonical;
 651   if (!vecType->isCanonical()) {
 652     Canonical = getVectorType(vecType.getCanonicalType(), NumElts);
 653
 654     // Get the new insert position for the node we care about.
 655     VectorType *NewIP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos);
 656     assert(NewIP == 0 && "Shouldn't be in the map!");
 657   }
 658   VectorType *New = new VectorType(vecType, NumElts, Canonical);
 659   VectorTypes.InsertNode(New, InsertPos);
 660   Types.push_back(New);
 661   return QualType(New, 0);
 662 }
 663
 664 /// getOCUVectorType - Return the unique reference to an OCU vector type of
 665 /// the specified element type and size. VectorType must be a built-in type.
 666 QualType ASTContext::getOCUVectorType(QualType vecType, unsigned NumElts) {
 667   BuiltinType *baseType;
 668
 669   baseType = dyn_cast<BuiltinType>(vecType.getCanonicalType().getTypePtr());
 670   assert(baseType != 0 && "getOCUVectorType(): Expecting a built-in type");
 671
 672   // Check if we've already instantiated a vector of this type.
 673   llvm::FoldingSetNodeID ID;
 674   VectorType::Profile(ID, vecType, NumElts, Type::OCUVector);
 675   void *InsertPos = 0;
 676   if (VectorType *VTP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos))
 677     return QualType(VTP, 0);
 678
 679   // If the element type isn't canonical, this won't be a canonical type either,
 680   // so fill in the canonical type field.
 681   QualType Canonical;
 682   if (!vecType->isCanonical()) {
 683     Canonical = getOCUVectorType(vecType.getCanonicalType(), NumElts);
 684
 685     // Get the new insert position for the node we care about.
 686     VectorType *NewIP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos);
 687     assert(NewIP == 0 && "Shouldn't be in the map!");
 688   }
 689   OCUVectorType *New = new OCUVectorType(vecType, NumElts, Canonical);
 690   VectorTypes.InsertNode(New, InsertPos);
 691   Types.push_back(New);
 692   return QualType(New, 0);
 693 }
 694
 695 /// getFunctionTypeNoProto - Return a K&R style C function type like 'int()'.
 696 ///
 697 QualType ASTContext::getFunctionTypeNoProto(QualType ResultTy) {
 698   // Unique functions, to guarantee there is only one function of a particular
 699   // structure.
 700   llvm::FoldingSetNodeID ID;
 701   FunctionTypeNoProto::Profile(ID, ResultTy);
 702
 703   void *InsertPos = 0;
 704   if (FunctionTypeNoProto *FT =
 705         FunctionTypeNoProtos.FindNodeOrInsertPos(ID, InsertPos))
 706     return QualType(FT, 0);
 707
 708   QualType Canonical;
 709   if (!ResultTy->isCanonical()) {
 710     Canonical = getFunctionTypeNoProto(ResultTy.getCanonicalType());
 711
 712     // Get the new insert position for the node we care about.
 713     FunctionTypeNoProto *NewIP =
 714       FunctionTypeNoProtos.FindNodeOrInsertPos(ID, InsertPos);
 715     assert(NewIP == 0 && "Shouldn't be in the map!");
 716   }
 717
 718   FunctionTypeNoProto *New = new FunctionTypeNoProto(ResultTy, Canonical);
 719   Types.push_back(New);
 720   FunctionTypeProtos.InsertNode(New, InsertPos);
 721   return QualType(New, 0);
 722 }
 723
 724 /// getFunctionType - Return a normal function type with a typed argument
 725 /// list.  isVariadic indicates whether the argument list includes '...'.
 726 QualType ASTContext::getFunctionType(QualType ResultTy, QualType *ArgArray,
 727                                      unsigned NumArgs, bool isVariadic) {
 728   // Unique functions, to guarantee there is only one function of a particular
 729   // structure.
 730   llvm::FoldingSetNodeID ID;
 731   FunctionTypeProto::Profile(ID, ResultTy, ArgArray, NumArgs, isVariadic);
 732
 733   void *InsertPos = 0;
 734   if (FunctionTypeProto *FTP =
 735         FunctionTypeProtos.FindNodeOrInsertPos(ID, InsertPos))
 736     return QualType(FTP, 0);
 737
 738   // Determine whether the type being created is already canonical or not.
 739   bool isCanonical = ResultTy->isCanonical();
 740   for (unsigned i = 0; i != NumArgs && isCanonical; ++i)
 741     if (!ArgArray[i]->isCanonical())
 742       isCanonical = false;
 743
 744   // If this type isn't canonical, get the canonical version of it.
 745   QualType Canonical;
 746   if (!isCanonical) {
 747     llvm::SmallVector<QualType, 16> CanonicalArgs;
 748     CanonicalArgs.reserve(NumArgs);
 749     for (unsigned i = 0; i != NumArgs; ++i)
 750       CanonicalArgs.push_back(ArgArray[i].getCanonicalType());
 751
 752     Canonical = getFunctionType(ResultTy.getCanonicalType(),
 753                                 &CanonicalArgs[0], NumArgs,
 754                                 isVariadic);
 755
 756     // Get the new insert position for the node we care about.
 757     FunctionTypeProto *NewIP =
 758       FunctionTypeProtos.FindNodeOrInsertPos(ID, InsertPos);
 759     assert(NewIP == 0 && "Shouldn't be in the map!");
 760   }
 761
 762   // FunctionTypeProto objects are not allocated with new because they have a
 763   // variable size array (for parameter types) at the end of them.
 764   FunctionTypeProto *FTP =
 765     (FunctionTypeProto*)malloc(sizeof(FunctionTypeProto) +
 766                                NumArgs*sizeof(QualType));
 767   new (FTP) FunctionTypeProto(ResultTy, ArgArray, NumArgs, isVariadic,
 768                               Canonical);
 769   Types.push_back(FTP);
 770   FunctionTypeProtos.InsertNode(FTP, InsertPos);
 771   return QualType(FTP, 0);
 772 }
 773
 774 /// getTypedefType - Return the unique reference to the type for the
 775 /// specified typename decl.
 776 QualType ASTContext::getTypedefType(TypedefDecl *Decl) {
 777   if (Decl->TypeForDecl) return QualType(Decl->TypeForDecl, 0);
 778
 779   QualType Canonical = Decl->getUnderlyingType().getCanonicalType();
 780   Decl->TypeForDecl = new TypedefType(Type::TypeName, Decl, Canonical);
 781   Types.push_back(Decl->TypeForDecl);
 782   return QualType(Decl->TypeForDecl, 0);
 783 }
 784
 785 /// getObjCInterfaceType - Return the unique reference to the type for the
 786 /// specified ObjC interface decl.
 787 QualType ASTContext::getObjCInterfaceType(ObjCInterfaceDecl *Decl) {
 788   if (Decl->TypeForDecl) return QualType(Decl->TypeForDecl, 0);
 789
 790   Decl->TypeForDecl = new ObjCInterfaceType(Type::ObjCInterface, Decl);
 791   Types.push_back(Decl->TypeForDecl);
 792   return QualType(Decl->TypeForDecl, 0);
 793 }
 794
 795 /// getObjCQualifiedInterfaceType - Return a
 796 /// ObjCQualifiedInterfaceType type for the given interface decl and
 797 /// the conforming protocol list.
 798 QualType ASTContext::getObjCQualifiedInterfaceType(ObjCInterfaceDecl *Decl,
 799                        ObjCProtocolDecl **Protocols, unsigned NumProtocols) {
 800   llvm::FoldingSetNodeID ID;
 801   ObjCQualifiedInterfaceType::Profile(ID, Protocols, NumProtocols);
 802
 803   void *InsertPos = 0;
 804   if (ObjCQualifiedInterfaceType *QT =
 805       ObjCQualifiedInterfaceTypes.FindNodeOrInsertPos(ID, InsertPos))
 806     return QualType(QT, 0);
 807
 808   // No Match;
 809   ObjCQualifiedInterfaceType *QType =
 810     new ObjCQualifiedInterfaceType(Decl, Protocols, NumProtocols);
 811   Types.push_back(QType);
 812   ObjCQualifiedInterfaceTypes.InsertNode(QType, InsertPos);
 813   return QualType(QType, 0);
 814 }
 815
 816 /// getObjCQualifiedIdType - Return a
 817 /// getObjCQualifiedIdType type for the 'id' decl and
 818 /// the conforming protocol list.
 819 QualType ASTContext::getObjCQualifiedIdType(QualType idType,
 820                                             ObjCProtocolDecl **Protocols,
 821                                             unsigned NumProtocols) {
 822   llvm::FoldingSetNodeID ID;
 823   ObjCQualifiedIdType::Profile(ID, Protocols, NumProtocols);
 824
 825   void *InsertPos = 0;
 826   if (ObjCQualifiedIdType *QT =
 827       ObjCQualifiedIdTypes.FindNodeOrInsertPos(ID, InsertPos))
 828     return QualType(QT, 0);
 829
 830   // No Match;
 831   QualType Canonical;
 832   if (!idType->isCanonical()) {
 833     Canonical = getObjCQualifiedIdType(idType.getCanonicalType(),
 834                                        Protocols, NumProtocols);
 835     ObjCQualifiedIdType *NewQT =
 836       ObjCQualifiedIdTypes.FindNodeOrInsertPos(ID, InsertPos);
 837     assert(NewQT == 0 && "Shouldn't be in the map!");
 838   }
 839
 840   ObjCQualifiedIdType *QType =
 841     new ObjCQualifiedIdType(Canonical, Protocols, NumProtocols);
 842   Types.push_back(QType);
 843   ObjCQualifiedIdTypes.InsertNode(QType, InsertPos);
 844   return QualType(QType, 0);
 845 }
 846
 847 /// getTypeOfExpr - Unlike many "get<Type>" functions, we can't unique
 848 /// TypeOfExpr AST's (since expression's are never shared). For example,
 849 /// multiple declarations that refer to "typeof(x)" all contain different
 850 /// DeclRefExpr's. This doesn't effect the type checker, since it operates
 851 /// on canonical type's (which are always unique).
 852 QualType ASTContext::getTypeOfExpr(Expr *tofExpr) {
 853   QualType Canonical = tofExpr->getType().getCanonicalType();
 854   TypeOfExpr *toe = new TypeOfExpr(tofExpr, Canonical);
 855   Types.push_back(toe);
 856   return QualType(toe, 0);
 857 }
 858
 859 /// getTypeOfType -  Unlike many "get<Type>" functions, we don't unique
 860 /// TypeOfType AST's. The only motivation to unique these nodes would be
 861 /// memory savings. Since typeof(t) is fairly uncommon, space shouldn't be
 862 /// an issue. This doesn't effect the type checker, since it operates
 863 /// on canonical type's (which are always unique).
 864 QualType ASTContext::getTypeOfType(QualType tofType) {
 865   QualType Canonical = tofType.getCanonicalType();
 866   TypeOfType *tot = new TypeOfType(tofType, Canonical);
 867   Types.push_back(tot);
 868   return QualType(tot, 0);
 869 }
 870
 871 /// getTagDeclType - Return the unique reference to the type for the
 872 /// specified TagDecl (struct/union/class/enum) decl.
 873 QualType ASTContext::getTagDeclType(TagDecl *Decl) {
 874   assert (Decl);
 875
 876   // The decl stores the type cache.
 877   if (Decl->TypeForDecl) return QualType(Decl->TypeForDecl, 0);
 878
 879   TagType* T = new TagType(Decl, QualType());
 880   Types.push_back(T);
 881   Decl->TypeForDecl = T;
 882
 883   return QualType(T, 0);
 884 }
 885
 886 /// getSizeType - Return the unique type for "size_t" (C99 7.17), the result
 887 /// of the sizeof operator (C99 6.5.3.4p4). The value is target dependent and
 888 /// needs to agree with the definition in <stddef.h>.
 889 QualType ASTContext::getSizeType() const {
 890   // On Darwin, size_t is defined as a "long unsigned int".
 891   // FIXME: should derive from "Target".
 892   return UnsignedLongTy;
 893 }
 894
 895 /// getWcharType - Return the unique type for "wchar_t" (C99 7.17), the
 896 /// width of characters in wide strings, The value is target dependent and
 897 /// needs to agree with the definition in <stddef.h>.
 898 QualType ASTContext::getWcharType() const {
 899   // On Darwin, wchar_t is defined as a "int".
 900   // FIXME: should derive from "Target".
 901   return IntTy;
 902 }
 903
 904 /// getPointerDiffType - Return the unique type for "ptrdiff_t" (ref?)
 905 /// defined in <stddef.h>. Pointer - pointer requires this (C99 6.5.6p9).
 906 QualType ASTContext::getPointerDiffType() const {
 907   // On Darwin, ptrdiff_t is defined as a "int". This seems like a bug...
 908   // FIXME: should derive from "Target".
 909   return IntTy;
 910 }
 911
 912 /// getIntegerRank - Return an integer conversion rank (C99 6.3.1.1p1). This
 913 /// routine will assert if passed a built-in type that isn't an integer or enum.
 914 static int getIntegerRank(QualType t) {
 915   if (const TagType *TT = dyn_cast<TagType>(t.getCanonicalType())) {
 916     assert(TT->getDecl()->getKind() == Decl::Enum && "not an int or enum");
 917     return 4;
 918   }
 919
 920   const BuiltinType *BT = t.getCanonicalType()->getAsBuiltinType();
 921   switch (BT->getKind()) {
 922   default:
 923     assert(0 && "getIntegerRank(): not a built-in integer");
 924   case BuiltinType::Bool:
 925     return 1;
 926   case BuiltinType::Char_S:
 927   case BuiltinType::Char_U:
 928   case BuiltinType::SChar:
 929   case BuiltinType::UChar:
 930     return 2;
 931   case BuiltinType::Short:
 932   case BuiltinType::UShort:
 933     return 3;
 934   case BuiltinType::Int:
 935   case BuiltinType::UInt:
 936     return 4;
 937   case BuiltinType::Long:
 938   case BuiltinType::ULong:
 939     return 5;
 940   case BuiltinType::LongLong:
 941   case BuiltinType::ULongLong:
 942     return 6;
 943   }
 944 }
 945
 946 /// getFloatingRank - Return a relative rank for floating point types.
 947 /// This routine will assert if passed a built-in type that isn't a float.
 948 static int getFloatingRank(QualType T) {
 949   T = T.getCanonicalType();
 950   if (const ComplexType *CT = T->getAsComplexType())
 951     return getFloatingRank(CT->getElementType());
 952
 953   switch (T->getAsBuiltinType()->getKind()) {
 954   default:  assert(0 && "getFloatingRank(): not a floating type");
 955   case BuiltinType::Float:      return FloatRank;
 956   case BuiltinType::Double:     return DoubleRank;
 957   case BuiltinType::LongDouble: return LongDoubleRank;
 958   }
 959 }
 960
 961 /// getFloatingTypeOfSizeWithinDomain - Returns a real floating
 962 /// point or a complex type (based on typeDomain/typeSize).
 963 /// 'typeDomain' is a real floating point or complex type.
 964 /// 'typeSize' is a real floating point or complex type.
 965 QualType ASTContext::getFloatingTypeOfSizeWithinDomain(
 966   QualType typeSize, QualType typeDomain) const {
 967   if (typeDomain->isComplexType()) {
 968     switch (getFloatingRank(typeSize)) {
 969     default: assert(0 && "getFloatingRank(): illegal value for rank");
 970     case FloatRank:      return FloatComplexTy;
 971     case DoubleRank:     return DoubleComplexTy;
 972     case LongDoubleRank: return LongDoubleComplexTy;
 973     }
 974   }
 975   if (typeDomain->isRealFloatingType()) {
 976     switch (getFloatingRank(typeSize)) {
 977     default: assert(0 && "getFloatingRank(): illegal value for rank");
 978     case FloatRank:      return FloatTy;
 979     case DoubleRank:     return DoubleTy;
 980     case LongDoubleRank: return LongDoubleTy;
 981     }
 982   }
 983   assert(0 && "getFloatingTypeOfSizeWithinDomain(): illegal domain");
 984   //an invalid return value, but the assert
 985   //will ensure that this code is never reached.
 986   return VoidTy;
 987 }
 988
 989 /// compareFloatingType - Handles 3 different combos:
 990 /// float/float, float/complex, complex/complex.
 991 /// If lt > rt, return 1. If lt == rt, return 0. If lt < rt, return -1.
 992 int ASTContext::compareFloatingType(QualType lt, QualType rt) {
 993   if (getFloatingRank(lt) == getFloatingRank(rt))
 994     return 0;
 995   if (getFloatingRank(lt) > getFloatingRank(rt))
 996     return 1;
 997   return -1;
 998 }
 999
1000 // maxIntegerType - Returns the highest ranked integer type. Handles 3 case:
1001 // unsigned/unsigned, signed/signed, signed/unsigned. C99 6.3.1.8p1.
1002 QualType ASTContext::maxIntegerType(QualType lhs, QualType rhs) {
1003   if (lhs == rhs) return lhs;
1004
1005   bool t1Unsigned = lhs->isUnsignedIntegerType();
1006   bool t2Unsigned = rhs->isUnsignedIntegerType();
1007
1008   if ((t1Unsigned && t2Unsigned) || (!t1Unsigned && !t2Unsigned))
1009     return getIntegerRank(lhs) >= getIntegerRank(rhs) ? lhs : rhs;
1010
1011   // We have two integer types with differing signs
1012   QualType unsignedType = t1Unsigned ? lhs : rhs;
1013   QualType signedType = t1Unsigned ? rhs : lhs;
1014
1015   if (getIntegerRank(unsignedType) >= getIntegerRank(signedType))
1016     return unsignedType;
1017   else {
1018     // FIXME: Need to check if the signed type can represent all values of the
1019     // unsigned type. If it can, then the result is the signed type.
1020     // If it can't, then the result is the unsigned version of the signed type.
1021     // Should probably add a helper that returns a signed integer type from
1022     // an unsigned (and vice versa). C99 6.3.1.8.
1023     return signedType;
1024   }
1025 }
1026
1027 // getCFConstantStringType - Return the type used for constant CFStrings.
1028 QualType ASTContext::getCFConstantStringType() {
1029   if (!CFConstantStringTypeDecl) {
1030     CFConstantStringTypeDecl = new RecordDecl(Decl::Struct, SourceLocation(),
1031                                               &Idents.get("NSConstantString"),
1032                                               0);
1033     QualType FieldTypes[4];
1034
1035     // const int *isa;
1036     FieldTypes[0] = getPointerType(IntTy.getQualifiedType(QualType::Const));
1037     // int flags;
1038     FieldTypes[1] = IntTy;
1039     // const char *str;
1040     FieldTypes[2] = getPointerType(CharTy.getQualifiedType(QualType::Const));
1041     // long length;
1042     FieldTypes[3] = LongTy;
1043     // Create fields
1044     FieldDecl *FieldDecls[4];
1045
1046     for (unsigned i = 0; i < 4; ++i)
1047       FieldDecls[i] = new FieldDecl(SourceLocation(), 0, FieldTypes[i]);
1048
1049     CFConstantStringTypeDecl->defineBody(FieldDecls, 4);
1050   }
1051
1052   return getTagDeclType(CFConstantStringTypeDecl);
1053 }
1054
1055 // This returns true if a type has been typedefed to BOOL:
1056 // typedef <type> BOOL;
1057 static bool isTypeTypedefedAsBOOL(QualType T) {
1058   if (const TypedefType *TT = dyn_cast<TypedefType>(T))
1059     return !strcmp(TT->getDecl()->getName(), "BOOL");
1060
1061   return false;
1062 }
1063
1064 /// getObjCEncodingTypeSize returns size of type for objective-c encoding
1065 /// purpose.
1066 int ASTContext::getObjCEncodingTypeSize(QualType type) {
1067   SourceLocation Loc;
1068   uint64_t sz = getTypeSize(type, Loc);
1069
1070   // Make all integer and enum types at least as large as an int
1071   if (sz > 0 && type->isIntegralType())
1072     sz = std::max(sz, getTypeSize(IntTy, Loc));
1073   // Treat arrays as pointers, since that's how they're passed in.
1074   else if (type->isArrayType())
1075     sz = getTypeSize(VoidPtrTy, Loc);
1076   return sz / getTypeSize(CharTy, Loc);
1077 }
1078
1079 /// getObjCEncodingForMethodDecl - Return the encoded type for this method
1080 /// declaration.
1081 void ASTContext::getObjCEncodingForMethodDecl(ObjCMethodDecl *Decl,
1082                                               std::string& S)
1083 {
1084   // Encode type qualifer, 'in', 'inout', etc. for the return type.
1085   getObjCEncodingForTypeQualifier(Decl->getObjCDeclQualifier(), S);
1086   // Encode result type.
1087   getObjCEncodingForType(Decl->getResultType(), S, EncodingRecordTypes);
1088   // Compute size of all parameters.
1089   // Start with computing size of a pointer in number of bytes.
1090   // FIXME: There might(should) be a better way of doing this computation!
1091   SourceLocation Loc;
1092   int PtrSize = getTypeSize(VoidPtrTy, Loc) / getTypeSize(CharTy, Loc);
1093   // The first two arguments (self and _cmd) are pointers; account for
1094   // their size.
1095   int ParmOffset = 2 * PtrSize;
1096   int NumOfParams = Decl->getNumParams();
1097   for (int i = 0; i < NumOfParams; i++) {
1098     QualType PType = Decl->getParamDecl(i)->getType();
1099     int sz = getObjCEncodingTypeSize (PType);
1100     assert (sz > 0 && "getObjCEncodingForMethodDecl - Incomplete param type");
1101     ParmOffset += sz;
1102   }
1103   S += llvm::utostr(ParmOffset);
1104   S += "@0:";
1105   S += llvm::utostr(PtrSize);
1106
1107   // Argument types.
1108   ParmOffset = 2 * PtrSize;
1109   for (int i = 0; i < NumOfParams; i++) {
1110     QualType PType = Decl->getParamDecl(i)->getType();
1111     // Process argument qualifiers for user supplied arguments; such as,
1112     // 'in', 'inout', etc.
1113     getObjCEncodingForTypeQualifier(
1114       Decl->getParamDecl(i)->getObjCDeclQualifier(), S);
1115     getObjCEncodingForType(PType, S, EncodingRecordTypes);
1116     S += llvm::utostr(ParmOffset);
1117     ParmOffset += getObjCEncodingTypeSize(PType);
1118   }
1119 }
1120
1121 void ASTContext::getObjCEncodingForType(QualType T, std::string& S,
1122        llvm::SmallVector<const RecordType *, 8> &ERType) const
1123 {
1124   // FIXME: This currently doesn't encode:
1125   // @ An object (whether statically typed or typed id)
1126   // # A class object (Class)
1127   // : A method selector (SEL)
1128   // {name=type...} A structure
1129   // (name=type...) A union
1130   // bnum A bit field of num bits
1131
1132   if (const BuiltinType *BT = T->getAsBuiltinType()) {
1133     char encoding;
1134     switch (BT->getKind()) {
1135     case BuiltinType::Void:
1136       encoding = 'v';
1137       break;
1138     case BuiltinType::Bool:
1139       encoding = 'B';
1140       break;
1141     case BuiltinType::Char_U:
1142     case BuiltinType::UChar:
1143       encoding = 'C';
1144       break;
1145     case BuiltinType::UShort:
1146       encoding = 'S';
1147       break;
1148     case BuiltinType::UInt:
1149       encoding = 'I';
1150       break;
1151     case BuiltinType::ULong:
1152       encoding = 'L';
1153       break;
1154     case BuiltinType::ULongLong:
1155       encoding = 'Q';
1156       break;
1157     case BuiltinType::Char_S:
1158     case BuiltinType::SChar:
1159       encoding = 'c';
1160       break;
1161     case BuiltinType::Short:
1162       encoding = 's';
1163       break;
1164     case BuiltinType::Int:
1165       encoding = 'i';
1166       break;
1167     case BuiltinType::Long:
1168       encoding = 'l';
1169       break;
1170     case BuiltinType::LongLong:
1171       encoding = 'q';
1172       break;
1173     case BuiltinType::Float:
1174       encoding = 'f';
1175       break;
1176     case BuiltinType::Double:
1177       encoding = 'd';
1178       break;
1179     case BuiltinType::LongDouble:
1180       encoding = 'd';
1181       break;
1182     default:
1183       assert(0 && "Unhandled builtin type kind");
1184     }
1185
1186     S += encoding;
1187   }
1188   else if (T->isObjCQualifiedIdType()) {
1189     // Treat id<P...> same as 'id' for encoding purposes.
1190     return getObjCEncodingForType(getObjCIdType(), S, ERType);
1191
1192   }
1193   else if (const PointerType *PT = T->getAsPointerType()) {
1194     QualType PointeeTy = PT->getPointeeType();
1195     if (isObjCIdType(PointeeTy) || PointeeTy->isObjCInterfaceType()) {
1196       S += '@';
1197       return;
1198     } else if (isObjCClassType(PointeeTy)) {
1199       S += '#';
1200       return;
1201     } else if (isObjCSelType(PointeeTy)) {
1202       S += ':';
1203       return;
1204     }
1205
1206     if (PointeeTy->isCharType()) {
1207       // char pointer types should be encoded as '*' unless it is a
1208       // type that has been typedef'd to 'BOOL'.
1209       if (!isTypeTypedefedAsBOOL(PointeeTy)) {
1210         S += '*';
1211         return;
1212       }
1213     }
1214
1215     S += '^';
1216     getObjCEncodingForType(PT->getPointeeType(), S, ERType);
1217   } else if (const ArrayType *AT = T->getAsArrayType()) {
1218     S += '[';
1219
1220     if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT))
1221       S += llvm::utostr(CAT->getSize().getZExtValue());
1222     else
1223       assert(0 && "Unhandled array type!");
1224
1225     getObjCEncodingForType(AT->getElementType(), S, ERType);
1226     S += ']';
1227   } else if (T->getAsFunctionType()) {
1228     S += '?';
1229   } else if (const RecordType *RTy = T->getAsRecordType()) {
1230     RecordDecl *RDecl= RTy->getDecl();
1231     S += '{';
1232     S += RDecl->getName();
1233     bool found = false;
1234     for (unsigned i = 0, e = ERType.size(); i != e; ++i)
1235       if (ERType[i] == RTy) {
1236         found = true;
1237         break;
1238       }
1239     if (!found) {
1240       ERType.push_back(RTy);
1241       S += '=';
1242       for (int i = 0; i < RDecl->getNumMembers(); i++) {
1243         FieldDecl *field = RDecl->getMember(i);
1244         getObjCEncodingForType(field->getType(), S, ERType);
1245       }
1246       assert(ERType.back() == RTy && "Record Type stack mismatch.");
1247       ERType.pop_back();
1248     }
1249     S += '}';
1250   } else if (T->isEnumeralType()) {
1251     S += 'i';
1252   } else
1253     assert(0 && "@encode for type not implemented!");
1254 }
1255
1256 void ASTContext::getObjCEncodingForTypeQualifier(Decl::ObjCDeclQualifier QT,
1257                                                  std::string& S) const {
1258   if (QT & Decl::OBJC_TQ_In)
1259     S += 'n';
1260   if (QT & Decl::OBJC_TQ_Inout)
1261     S += 'N';
1262   if (QT & Decl::OBJC_TQ_Out)
1263     S += 'o';
1264   if (QT & Decl::OBJC_TQ_Bycopy)
1265     S += 'O';
1266   if (QT & Decl::OBJC_TQ_Byref)
1267     S += 'R';
1268   if (QT & Decl::OBJC_TQ_Oneway)
1269     S += 'V';
1270 }
1271
1272 void ASTContext::setBuiltinVaListType(QualType T)
1273 {
1274   assert(BuiltinVaListType.isNull() && "__builtin_va_list type already set!");
1275
1276   BuiltinVaListType = T;
1277 }
1278
1279 void ASTContext::setObjCIdType(TypedefDecl *TD)
1280 {
1281   assert(ObjCIdType.isNull() && "'id' type already set!");
1282
1283   ObjCIdType = getTypedefType(TD);
1284
1285   // typedef struct objc_object *id;
1286   const PointerType *ptr = TD->getUnderlyingType()->getAsPointerType();
1287   assert(ptr && "'id' incorrectly typed");
1288   const RecordType *rec = ptr->getPointeeType()->getAsStructureType();
1289   assert(rec && "'id' incorrectly typed");
1290   IdStructType = rec;
1291 }
1292
1293 void ASTContext::setObjCSelType(TypedefDecl *TD)
1294 {
1295   assert(ObjCSelType.isNull() && "'SEL' type already set!");
1296
1297   ObjCSelType = getTypedefType(TD);
1298
1299   // typedef struct objc_selector *SEL;
1300   const PointerType *ptr = TD->getUnderlyingType()->getAsPointerType();
1301   assert(ptr && "'SEL' incorrectly typed");
1302   const RecordType *rec = ptr->getPointeeType()->getAsStructureType();
1303   assert(rec && "'SEL' incorrectly typed");
1304   SelStructType = rec;
1305 }
1306
1307 void ASTContext::setObjCProtoType(QualType QT)
1308 {
1309   assert(ObjCProtoType.isNull() && "'Protocol' type already set!");
1310   ObjCProtoType = QT;
1311 }
1312
1313 void ASTContext::setObjCClassType(TypedefDecl *TD)
1314 {
1315   assert(ObjCClassType.isNull() && "'Class' type already set!");
1316
1317   ObjCClassType = getTypedefType(TD);
1318
1319   // typedef struct objc_class *Class;
1320   const PointerType *ptr = TD->getUnderlyingType()->getAsPointerType();
1321   assert(ptr && "'Class' incorrectly typed");
1322   const RecordType *rec = ptr->getPointeeType()->getAsStructureType();
1323   assert(rec && "'Class' incorrectly typed");
1324   ClassStructType = rec;
1325 }
1326
1327 void ASTContext::setObjCConstantStringInterface(ObjCInterfaceDecl *Decl) {
1328   assert(ObjCConstantStringType.isNull() &&
1329          "'NSConstantString' type already set!");
1330
1331   ObjCConstantStringType = getObjCInterfaceType(Decl);
1332 }
1333
1334 bool ASTContext::builtinTypesAreCompatible(QualType lhs, QualType rhs) {
1335   const BuiltinType *lBuiltin = lhs->getAsBuiltinType();
1336   const BuiltinType *rBuiltin = rhs->getAsBuiltinType();
1337
1338   return lBuiltin->getKind() == rBuiltin->getKind();
1339 }
1340
1341 /// objcTypesAreCompatible - This routine is called when two types
1342 /// are of different class; one is interface type or is
1343 /// a qualified interface type and the other type is of a different class.
1344 /// Example, II or II<P>.
1345 bool ASTContext::objcTypesAreCompatible(QualType lhs, QualType rhs) {
1346   if (lhs->isObjCInterfaceType() && isObjCIdType(rhs))
1347     return true;
1348   else if (isObjCIdType(lhs) && rhs->isObjCInterfaceType())
1349     return true;
1350   if (ObjCInterfaceType *lhsIT =
1351       dyn_cast<ObjCInterfaceType>(lhs.getCanonicalType().getTypePtr())) {
1352     ObjCQualifiedInterfaceType *rhsQI =
1353       dyn_cast<ObjCQualifiedInterfaceType>(rhs.getCanonicalType().getTypePtr());
1354     return rhsQI && (lhsIT->getDecl() == rhsQI->getDecl());
1355   }
1356   else if (ObjCInterfaceType *rhsIT =
1357            dyn_cast<ObjCInterfaceType>(rhs.getCanonicalType().getTypePtr())) {
1358     ObjCQualifiedInterfaceType *lhsQI =
1359     dyn_cast<ObjCQualifiedInterfaceType>(lhs.getCanonicalType().getTypePtr());
1360     return lhsQI && (rhsIT->getDecl() == lhsQI->getDecl());
1361   }
1362   return false;
1363 }
1364
1365 /// Check that 'lhs' and 'rhs' are compatible interface types. Both types
1366 /// must be canonical types.
1367 bool ASTContext::interfaceTypesAreCompatible(QualType lhs, QualType rhs) {
1368   assert (lhs->isCanonical() &&
1369           "interfaceTypesAreCompatible strip typedefs of lhs");
1370   assert (rhs->isCanonical() &&
1371           "interfaceTypesAreCompatible strip typedefs of rhs");
1372   if (lhs == rhs)
1373     return true;
1374   ObjCInterfaceType *lhsIT = cast<ObjCInterfaceType>(lhs.getTypePtr());
1375   ObjCInterfaceType *rhsIT = cast<ObjCInterfaceType>(rhs.getTypePtr());
1376   ObjCInterfaceDecl *rhsIDecl = rhsIT->getDecl();
1377   ObjCInterfaceDecl *lhsIDecl = lhsIT->getDecl();
1378   // rhs is derived from lhs it is OK; else it is not OK.
1379   while (rhsIDecl != NULL) {
1380     if (rhsIDecl == lhsIDecl)
1381       return true;
1382     rhsIDecl = rhsIDecl->getSuperClass();
1383   }
1384   return false;
1385 }
1386
1387 bool ASTContext::QualifiedInterfaceTypesAreCompatible(QualType lhs,
1388                                                       QualType rhs) {
1389   ObjCQualifiedInterfaceType *lhsQI =
1390     dyn_cast<ObjCQualifiedInterfaceType>(lhs.getCanonicalType().getTypePtr());
1391   assert(lhsQI && "QualifiedInterfaceTypesAreCompatible - bad lhs type");
1392   ObjCQualifiedInterfaceType *rhsQI =
1393     dyn_cast<ObjCQualifiedInterfaceType>(rhs.getCanonicalType().getTypePtr());
1394   assert(rhsQI && "QualifiedInterfaceTypesAreCompatible - bad rhs type");
1395   if (!interfaceTypesAreCompatible(
1396          getObjCInterfaceType(lhsQI->getDecl()).getCanonicalType(),
1397          getObjCInterfaceType(rhsQI->getDecl()).getCanonicalType()))
1398     return false;
1399   /* All protocols in lhs must have a presense in rhs. */
1400   for (unsigned i =0; i < lhsQI->getNumProtocols(); i++) {
1401     bool match = false;
1402     ObjCProtocolDecl *lhsProto = lhsQI->getProtocols(i);
1403     for (unsigned j = 0; j < rhsQI->getNumProtocols(); j++) {
1404       ObjCProtocolDecl *rhsProto = rhsQI->getProtocols(j);
1405       if (lhsProto == rhsProto) {
1406         match = true;
1407         break;
1408       }
1409     }
1410     if (!match)
1411       return false;
1412   }
1413   return true;
1414 }
1415
1416 /// ProtocolCompatibleWithProtocol - return 'true' if 'lProto' is in the
1417 /// inheritance hierarchy of 'rProto'.
1418 static bool ProtocolCompatibleWithProtocol(ObjCProtocolDecl *lProto,
1419                                            ObjCProtocolDecl *rProto) {
1420   if (lProto == rProto)
1421     return true;
1422   ObjCProtocolDecl** RefPDecl = rProto->getReferencedProtocols();
1423   for (unsigned i = 0; i < rProto->getNumReferencedProtocols(); i++)
1424     if (ProtocolCompatibleWithProtocol(lProto, RefPDecl[i]))
1425       return true;
1426   return false;
1427 }
1428
1429 /// ClassImplementsProtocol - Checks that 'lProto' protocol
1430 /// has been implemented in IDecl class, its super class or categories (if
1431 /// lookupCategory is true).
1432 static bool ClassImplementsProtocol(ObjCProtocolDecl *lProto,
1433                                     ObjCInterfaceDecl *IDecl,
1434                                     bool lookupCategory) {
1435
1436   // 1st, look up the class.
1437   ObjCProtocolDecl **protoList = IDecl->getReferencedProtocols();
1438   for (unsigned i = 0; i < IDecl->getNumIntfRefProtocols(); i++) {
1439     if (ProtocolCompatibleWithProtocol(lProto, protoList[i]))
1440       return true;
1441   }
1442
1443   // 2nd, look up the category.
1444   if (lookupCategory)
1445     for (ObjCCategoryDecl *CDecl = IDecl->getCategoryList(); CDecl;
1446          CDecl = CDecl->getNextClassCategory()) {
1447       protoList = CDecl->getReferencedProtocols();
1448       for (unsigned i = 0; i < CDecl->getNumReferencedProtocols(); i++) {
1449         if (ProtocolCompatibleWithProtocol(lProto, protoList[i]))
1450           return true;
1451       }
1452     }
1453
1454   // 3rd, look up the super class(s)
1455   if (IDecl->getSuperClass())
1456     return
1457       ClassImplementsProtocol(lProto, IDecl->getSuperClass(), lookupCategory);
1458
1459   return false;
1460 }
1461
1462 /// ObjCQualifiedIdTypesAreCompatible - Compares two types, at least
1463 /// one of which is a protocol qualified 'id' type. When 'compare'
1464 /// is true it is for comparison; when false, for assignment/initialization.
1465 bool ASTContext::ObjCQualifiedIdTypesAreCompatible(QualType lhs,
1466                                                    QualType rhs,
1467                                                    bool compare) {
1468   // match id<P..> with an 'id' type in all cases.
1469   if (const PointerType *PT = lhs->getAsPointerType()) {
1470     QualType PointeeTy = PT->getPointeeType();
1471     if (isObjCIdType(PointeeTy) || PointeeTy->isVoidType())
1472       return true;
1473
1474   }
1475   else if (const PointerType *PT = rhs->getAsPointerType()) {
1476     QualType PointeeTy = PT->getPointeeType();
1477     if (isObjCIdType(PointeeTy) || PointeeTy->isVoidType())
1478       return true;
1479
1480   }
1481
1482   ObjCQualifiedInterfaceType *lhsQI = 0;
1483   ObjCQualifiedInterfaceType *rhsQI = 0;
1484   ObjCInterfaceDecl *lhsID = 0;
1485   ObjCInterfaceDecl *rhsID = 0;
1486   ObjCQualifiedIdType *lhsQID = dyn_cast<ObjCQualifiedIdType>(lhs);
1487   ObjCQualifiedIdType *rhsQID = dyn_cast<ObjCQualifiedIdType>(rhs);
1488
1489   if (lhsQID) {
1490     if (!rhsQID && rhs->getTypeClass() == Type::Pointer) {
1491       QualType rtype =
1492         cast<PointerType>(rhs.getCanonicalType())->getPointeeType();
1493       rhsQI =
1494         dyn_cast<ObjCQualifiedInterfaceType>(
1495           rtype.getCanonicalType().getTypePtr());
1496       if (!rhsQI) {
1497         ObjCInterfaceType *IT = dyn_cast<ObjCInterfaceType>(
1498                                   rtype.getCanonicalType().getTypePtr());
1499         if (IT)
1500           rhsID = IT->getDecl();
1501       }
1502     }
1503     if (!rhsQI && !rhsQID && !rhsID)
1504       return false;
1505
1506     unsigned numRhsProtocols = 0;
1507     ObjCProtocolDecl **rhsProtoList = 0;
1508     if (rhsQI) {
1509       numRhsProtocols = rhsQI->getNumProtocols();
1510       rhsProtoList = rhsQI->getReferencedProtocols();
1511     }
1512     else if (rhsQID) {
1513       numRhsProtocols = rhsQID->getNumProtocols();
1514       rhsProtoList = rhsQID->getReferencedProtocols();
1515     }
1516
1517     for (unsigned i =0; i < lhsQID->getNumProtocols(); i++) {
1518       ObjCProtocolDecl *lhsProto = lhsQID->getProtocols(i);
1519       bool match = false;
1520
1521       // when comparing an id<P> on lhs with a static type on rhs,
1522       // see if static class implements all of id's protocols, directly or
1523       // through its super class and categories.
1524       if (rhsID) {
1525         if (ClassImplementsProtocol(lhsProto, rhsID, true))
1526           match = true;
1527       }
1528       else for (unsigned j = 0; j < numRhsProtocols; j++) {
1529         ObjCProtocolDecl *rhsProto = rhsProtoList[j];
1530         if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto) ||
1531             compare && ProtocolCompatibleWithProtocol(rhsProto, lhsProto)) {
1532           match = true;
1533           break;
1534         }
1535       }
1536       if (!match)
1537         return false;
1538     }
1539   }
1540   else if (rhsQID) {
1541     if (!lhsQID && lhs->getTypeClass() == Type::Pointer) {
1542       QualType ltype =
1543       cast<PointerType>(lhs.getCanonicalType())->getPointeeType();
1544       lhsQI =
1545       dyn_cast<ObjCQualifiedInterfaceType>(
1546         ltype.getCanonicalType().getTypePtr());
1547       if (!lhsQI) {
1548         ObjCInterfaceType *IT = dyn_cast<ObjCInterfaceType>(
1549                                   ltype.getCanonicalType().getTypePtr());
1550         if (IT)
1551           lhsID = IT->getDecl();
1552       }
1553     }
1554     if (!lhsQI && !lhsQID && !lhsID)
1555       return false;
1556
1557     unsigned numLhsProtocols = 0;
1558     ObjCProtocolDecl **lhsProtoList = 0;
1559     if (lhsQI) {
1560       numLhsProtocols = lhsQI->getNumProtocols();
1561       lhsProtoList = lhsQI->getReferencedProtocols();
1562     }
1563     else if (lhsQID) {
1564       numLhsProtocols = lhsQID->getNumProtocols();
1565       lhsProtoList = lhsQID->getReferencedProtocols();
1566     }
1567     bool match = false;
1568     // for static type vs. qualified 'id' type, check that class implements
1569     // one of 'id's protocols.
1570     if (lhsID) {
1571       for (unsigned j = 0; j < rhsQID->getNumProtocols(); j++) {
1572         ObjCProtocolDecl *rhsProto = rhsQID->getProtocols(j);
1573         if (ClassImplementsProtocol(rhsProto, lhsID, compare)) {
1574           match = true;
1575           break;
1576         }
1577       }
1578     }
1579     else for (unsigned i =0; i < numLhsProtocols; i++) {
1580       match = false;
1581       ObjCProtocolDecl *lhsProto = lhsProtoList[i];
1582       for (unsigned j = 0; j < rhsQID->getNumProtocols(); j++) {
1583         ObjCProtocolDecl *rhsProto = rhsQID->getProtocols(j);
1584         if (ProtocolCompatibleWithProtocol(lhsProto, rhsProto) ||
1585           compare && ProtocolCompatibleWithProtocol(rhsProto, lhsProto)) {
1586           match = true;
1587           break;
1588         }
1589       }
1590     }
1591     if (!match)
1592       return false;
1593   }
1594   return true;
1595 }
1596
1597 bool ASTContext::vectorTypesAreCompatible(QualType lhs, QualType rhs) {
1598   const VectorType *lVector = lhs->getAsVectorType();
1599   const VectorType *rVector = rhs->getAsVectorType();
1600
1601   if ((lVector->getElementType().getCanonicalType() ==
1602       rVector->getElementType().getCanonicalType()) &&
1603       (lVector->getNumElements() == rVector->getNumElements()))
1604     return true;
1605   return false;
1606 }
1607
1608 // C99 6.2.7p1: If both are complete types, then the following additional
1609 // requirements apply...FIXME (handle compatibility across source files).
1610 bool ASTContext::tagTypesAreCompatible(QualType lhs, QualType rhs) {
1611   // "Class" and "id" are compatible built-in structure types.
1612   if (isObjCIdType(lhs) && isObjCClassType(rhs) ||
1613       isObjCClassType(lhs) && isObjCIdType(rhs))
1614     return true;
1615
1616   // Within a translation unit a tag type is
1617   // only compatible with itself.
1618   return lhs.getCanonicalType() == rhs.getCanonicalType();
1619 }
1620
1621 bool ASTContext::pointerTypesAreCompatible(QualType lhs, QualType rhs) {
1622   // C99 6.7.5.1p2: For two pointer types to be compatible, both shall be
1623   // identically qualified and both shall be pointers to compatible types.
1624   if (lhs.getQualifiers() != rhs.getQualifiers())
1625     return false;
1626
1627   QualType ltype = cast<PointerType>(lhs.getCanonicalType())->getPointeeType();
1628   QualType rtype = cast<PointerType>(rhs.getCanonicalType())->getPointeeType();
1629
1630   return typesAreCompatible(ltype, rtype);
1631 }
1632
1633 // C++ 5.17p6: When the left operand of an assignment operator denotes a
1634 // reference to T, the operation assigns to the object of type T denoted by the
1635 // reference.
1636 bool ASTContext::referenceTypesAreCompatible(QualType lhs, QualType rhs) {
1637   QualType ltype = lhs;
1638
1639   if (lhs->isReferenceType())
1640     ltype = cast<ReferenceType>(lhs.getCanonicalType())->getReferenceeType();
1641
1642   QualType rtype = rhs;
1643
1644   if (rhs->isReferenceType())
1645     rtype = cast<ReferenceType>(rhs.getCanonicalType())->getReferenceeType();
1646
1647   return typesAreCompatible(ltype, rtype);
1648 }
1649
1650 bool ASTContext::functionTypesAreCompatible(QualType lhs, QualType rhs) {
1651   const FunctionType *lbase = cast<FunctionType>(lhs.getCanonicalType());
1652   const FunctionType *rbase = cast<FunctionType>(rhs.getCanonicalType());
1653   const FunctionTypeProto *lproto = dyn_cast<FunctionTypeProto>(lbase);
1654   const FunctionTypeProto *rproto = dyn_cast<FunctionTypeProto>(rbase);
1655
1656   // first check the return types (common between C99 and K&R).
1657   if (!typesAreCompatible(lbase->getResultType(), rbase->getResultType()))
1658     return false;
1659
1660   if (lproto && rproto) { // two C99 style function prototypes
1661     unsigned lproto_nargs = lproto->getNumArgs();
1662     unsigned rproto_nargs = rproto->getNumArgs();
1663
1664     if (lproto_nargs != rproto_nargs)
1665       return false;
1666
1667     // both prototypes have the same number of arguments.
1668     if ((lproto->isVariadic() && !rproto->isVariadic()) ||
1669         (rproto->isVariadic() && !lproto->isVariadic()))
1670       return false;
1671
1672     // The use of ellipsis agree...now check the argument types.
1673     for (unsigned i = 0; i < lproto_nargs; i++)
1674       // C99 6.7.5.3p15: ...and each parameter declared with qualified type
1675       // is taken as having the unqualified version of it's declared type.
1676       if (!typesAreCompatible(lproto->getArgType(i).getUnqualifiedType(),
1677                               rproto->getArgType(i).getUnqualifiedType()))
1678         return false;
1679     return true;
1680   }
1681   if (!lproto && !rproto) // two K&R style function decls, nothing to do.
1682     return true;
1683
1684   // we have a mixture of K&R style with C99 prototypes
1685   const FunctionTypeProto *proto = lproto ? lproto : rproto;
1686
1687   if (proto->isVariadic())
1688     return false;
1689
1690   // FIXME: Each parameter type T in the prototype must be compatible with the
1691   // type resulting from applying the usual argument conversions to T.
1692   return true;
1693 }
1694
1695 bool ASTContext::arrayTypesAreCompatible(QualType lhs, QualType rhs) {
1696   // Compatible arrays must have compatible element types
1697   QualType ltype = lhs->getAsArrayType()->getElementType();
1698   QualType rtype = rhs->getAsArrayType()->getElementType();
1699
1700   if (!typesAreCompatible(ltype, rtype))
1701     return false;
1702
1703   // Compatible arrays must be the same size
1704   if (const ConstantArrayType* LCAT = lhs->getAsConstantArrayType())
1705     if (const ConstantArrayType* RCAT = rhs->getAsConstantArrayType())
1706       return RCAT->getSize() == LCAT->getSize();
1707
1708   return true;
1709 }
1710
1711 /// typesAreCompatible - C99 6.7.3p9: For two qualified types to be compatible,
1712 /// both shall have the identically qualified version of a compatible type.
1713 /// C99 6.2.7p1: Two types have compatible types if their types are the
1714 /// same. See 6.7.[2,3,5] for additional rules.
1715 bool ASTContext::typesAreCompatible(QualType lhs, QualType rhs) {
1716   if (lhs.getQualifiers() != rhs.getQualifiers())
1717     return false;
1718
1719   QualType lcanon = lhs.getCanonicalType();
1720   QualType rcanon = rhs.getCanonicalType();
1721
1722   // If two types are identical, they are are compatible
1723   if (lcanon == rcanon)
1724     return true;
1725
1726   // C++ [expr]: If an expression initially has the type "reference to T", the
1727   // type is adjusted to "T" prior to any further analysis, the expression
1728   // designates the object or function denoted by the reference, and the
1729   // expression is an lvalue.
1730   if (ReferenceType *RT = dyn_cast<ReferenceType>(lcanon))
1731     lcanon = RT->getReferenceeType();
1732   if (ReferenceType *RT = dyn_cast<ReferenceType>(rcanon))
1733     rcanon = RT->getReferenceeType();
1734
1735   Type::TypeClass LHSClass = lcanon->getTypeClass();
1736   Type::TypeClass RHSClass = rcanon->getTypeClass();
1737
1738   // We want to consider the two function types to be the same for these
1739   // comparisons, just force one to the other.
1740   if (LHSClass == Type::FunctionProto) LHSClass = Type::FunctionNoProto;
1741   if (RHSClass == Type::FunctionProto) RHSClass = Type::FunctionNoProto;
1742
1743   // Same as above for arrays
1744   if (LHSClass == Type::VariableArray) LHSClass = Type::ConstantArray;
1745   if (RHSClass == Type::VariableArray) RHSClass = Type::ConstantArray;
1746   if (LHSClass == Type::IncompleteArray) LHSClass = Type::ConstantArray;
1747   if (RHSClass == Type::IncompleteArray) RHSClass = Type::ConstantArray;
1748
1749   // If the canonical type classes don't match...
1750   if (LHSClass != RHSClass) {
1751     // For Objective-C, it is possible for two types to be compatible
1752     // when their classes don't match (when dealing with "id"). If either type
1753     // is an interface, we defer to objcTypesAreCompatible().
1754     if (lcanon->isObjCInterfaceType() || rcanon->isObjCInterfaceType())
1755       return objcTypesAreCompatible(lcanon, rcanon);
1756
1757     // C99 6.7.2.2p4: Each enumerated type shall be compatible with char,
1758     // a signed integer type, or an unsigned integer type.
1759     if (lcanon->isEnumeralType() && rcanon->isIntegralType()) {
1760       EnumDecl* EDecl = cast<EnumDecl>(cast<TagType>(lcanon)->getDecl());
1761       return EDecl->getIntegerType() == rcanon;
1762     }
1763     if (rcanon->isEnumeralType() && lcanon->isIntegralType()) {
1764       EnumDecl* EDecl = cast<EnumDecl>(cast<TagType>(rcanon)->getDecl());
1765       return EDecl->getIntegerType() == lcanon;
1766     }
1767
1768     return false;
1769   }
1770   // The canonical type classes match.
1771   switch (LHSClass) {
1772   case Type::FunctionProto: assert(0 && "Canonicalized away above");
1773   case Type::Pointer:
1774     return pointerTypesAreCompatible(lcanon, rcanon);
1775   case Type::ConstantArray:
1776   case Type::VariableArray:
1777   case Type::IncompleteArray:
1778     return arrayTypesAreCompatible(lcanon, rcanon);
1779   case Type::FunctionNoProto:
1780     return functionTypesAreCompatible(lcanon, rcanon);
1781   case Type::Tagged: // handle structures, unions
1782     return tagTypesAreCompatible(lcanon, rcanon);
1783   case Type::Builtin:
1784     return builtinTypesAreCompatible(lcanon, rcanon);
1785   case Type::ObjCInterface:
1786     return interfaceTypesAreCompatible(lcanon, rcanon);
1787   case Type::Vector:
1788   case Type::OCUVector:
1789     return vectorTypesAreCompatible(lcanon, rcanon);
1790   case Type::ObjCQualifiedInterface:
1791     return QualifiedInterfaceTypesAreCompatible(lcanon, rcanon);
1792   default:
1793     assert(0 && "unexpected type");
1794   }
1795   return true; // should never get here...
1796 }
1797
1798 /// Emit - Serialize an ASTContext object to Bitcode.
1799 void ASTContext::Emit(llvm::Serializer& S) const {
1800   S.EmitRef(SourceMgr);
1801   S.EmitRef(Target);
1802   S.EmitRef(Idents);
1803   S.EmitRef(Selectors);
1804
1805   // Emit the size of the type vector so that we can reserve that size
1806   // when we reconstitute the ASTContext object.
1807   S.EmitInt(Types.size());
1808
1809   for (std::vector<Type*>::const_iterator I=Types.begin(), E=Types.end();
1810                                           I!=E;++I)
1811     (*I)->Emit(S);
1812
1813   // FIXME: S.EmitOwnedPtr(CFConstantStringTypeDecl);
1814 }
1815
1816 ASTContext* ASTContext::Create(llvm::Deserializer& D) {
1817   SourceManager &SM = D.ReadRef<SourceManager>();
1818   TargetInfo &t = D.ReadRef<TargetInfo>();
1819   IdentifierTable &idents = D.ReadRef<IdentifierTable>();
1820   SelectorTable &sels = D.ReadRef<SelectorTable>();
1821
1822   unsigned size_reserve = D.ReadInt();
1823
1824   ASTContext* A = new ASTContext(SM,t,idents,sels,size_reserve);
1825
1826   for (unsigned i = 0; i < size_reserve; ++i)
1827     Type::Create(*A,i,D);
1828
1829   // FIXME: A->CFConstantStringTypeDecl = D.ReadOwnedPtr<RecordDecl>();
1830
1831   return A;
1832 }