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