clang/lib/AST/ASTContext.cpp

   1 //===- ASTContext.cpp - Context to hold long-lived AST nodes --------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file implements the ASTContext interface.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/AST/ASTContext.h"
  14 #include "CXXABI.h"
  15 #include "Interp/Context.h"
  16 #include "clang/AST/APValue.h"
  17 #include "clang/AST/ASTConcept.h"
  18 #include "clang/AST/ASTMutationListener.h"
  19 #include "clang/AST/ASTTypeTraits.h"
  20 #include "clang/AST/Attr.h"
  21 #include "clang/AST/AttrIterator.h"
  22 #include "clang/AST/CharUnits.h"
  23 #include "clang/AST/Comment.h"
  24 #include "clang/AST/Decl.h"
  25 #include "clang/AST/DeclBase.h"
  26 #include "clang/AST/DeclCXX.h"
  27 #include "clang/AST/DeclContextInternals.h"
  28 #include "clang/AST/DeclObjC.h"
  29 #include "clang/AST/DeclOpenMP.h"
  30 #include "clang/AST/DeclTemplate.h"
  31 #include "clang/AST/DeclarationName.h"
  32 #include "clang/AST/Expr.h"
  33 #include "clang/AST/ExprCXX.h"
  34 #include "clang/AST/ExprConcepts.h"
  35 #include "clang/AST/ExternalASTSource.h"
  36 #include "clang/AST/Mangle.h"
  37 #include "clang/AST/MangleNumberingContext.h"
  38 #include "clang/AST/NestedNameSpecifier.h"
  39 #include "clang/AST/ParentMapContext.h"
  40 #include "clang/AST/RawCommentList.h"
  41 #include "clang/AST/RecordLayout.h"
  42 #include "clang/AST/Stmt.h"
  43 #include "clang/AST/TemplateBase.h"
  44 #include "clang/AST/TemplateName.h"
  45 #include "clang/AST/Type.h"
  46 #include "clang/AST/TypeLoc.h"
  47 #include "clang/AST/UnresolvedSet.h"
  48 #include "clang/AST/VTableBuilder.h"
  49 #include "clang/Basic/AddressSpaces.h"
  50 #include "clang/Basic/Builtins.h"
  51 #include "clang/Basic/CommentOptions.h"
  52 #include "clang/Basic/ExceptionSpecificationType.h"
  53 #include "clang/Basic/FixedPoint.h"
  54 #include "clang/Basic/IdentifierTable.h"
  55 #include "clang/Basic/LLVM.h"
  56 #include "clang/Basic/LangOptions.h"
  57 #include "clang/Basic/Linkage.h"
  58 #include "clang/Basic/Module.h"
  59 #include "clang/Basic/ObjCRuntime.h"
  60 #include "clang/Basic/SanitizerBlacklist.h"
  61 #include "clang/Basic/SourceLocation.h"
  62 #include "clang/Basic/SourceManager.h"
  63 #include "clang/Basic/Specifiers.h"
  64 #include "clang/Basic/TargetCXXABI.h"
  65 #include "clang/Basic/TargetInfo.h"
  66 #include "clang/Basic/XRayLists.h"
  67 #include "llvm/ADT/APInt.h"
  68 #include "llvm/ADT/APSInt.h"
  69 #include "llvm/ADT/ArrayRef.h"
  70 #include "llvm/ADT/DenseMap.h"
  71 #include "llvm/ADT/DenseSet.h"
  72 #include "llvm/ADT/FoldingSet.h"
  73 #include "llvm/ADT/None.h"
  74 #include "llvm/ADT/Optional.h"
  75 #include "llvm/ADT/PointerUnion.h"
  76 #include "llvm/ADT/STLExtras.h"
  77 #include "llvm/ADT/SmallPtrSet.h"
  78 #include "llvm/ADT/SmallVector.h"
  79 #include "llvm/ADT/StringExtras.h"
  80 #include "llvm/ADT/StringRef.h"
  81 #include "llvm/ADT/Triple.h"
  82 #include "llvm/Support/Capacity.h"
  83 #include "llvm/Support/Casting.h"
  84 #include "llvm/Support/Compiler.h"
  85 #include "llvm/Support/ErrorHandling.h"
  86 #include "llvm/Support/MathExtras.h"
  87 #include "llvm/Support/raw_ostream.h"
  88 #include <algorithm>
  89 #include <cassert>
  90 #include <cstddef>
  91 #include <cstdint>
  92 #include <cstdlib>
  93 #include <map>
  94 #include <memory>
  95 #include <string>
  96 #include <tuple>
  97 #include <utility>
  98
  99 using namespace clang;
 100
 101 enum FloatingRank {
 102   Float16Rank, HalfRank, FloatRank, DoubleRank, LongDoubleRank, Float128Rank
 103 };
 104
 105 /// \returns location that is relevant when searching for Doc comments related
 106 /// to \p D.
 107 static SourceLocation getDeclLocForCommentSearch(const Decl *D,
 108                                                  SourceManager &SourceMgr) {
 109   assert(D);
 110
 111   // User can not attach documentation to implicit declarations.
 112   if (D->isImplicit())
 113     return {};
 114
 115   // User can not attach documentation to implicit instantiations.
 116   if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
 117     if (FD->getTemplateSpecializationKind() == TSK_ImplicitInstantiation)
 118       return {};
 119   }
 120
 121   if (const auto *VD = dyn_cast<VarDecl>(D)) {
 122     if (VD->isStaticDataMember() &&
 123         VD->getTemplateSpecializationKind() == TSK_ImplicitInstantiation)
 124       return {};
 125   }
 126
 127   if (const auto *CRD = dyn_cast<CXXRecordDecl>(D)) {
 128     if (CRD->getTemplateSpecializationKind() == TSK_ImplicitInstantiation)
 129       return {};
 130   }
 131
 132   if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(D)) {
 133     TemplateSpecializationKind TSK = CTSD->getSpecializationKind();
 134     if (TSK == TSK_ImplicitInstantiation ||
 135         TSK == TSK_Undeclared)
 136       return {};
 137   }
 138
 139   if (const auto *ED = dyn_cast<EnumDecl>(D)) {
 140     if (ED->getTemplateSpecializationKind() == TSK_ImplicitInstantiation)
 141       return {};
 142   }
 143   if (const auto *TD = dyn_cast<TagDecl>(D)) {
 144     // When tag declaration (but not definition!) is part of the
 145     // decl-specifier-seq of some other declaration, it doesn't get comment
 146     if (TD->isEmbeddedInDeclarator() && !TD->isCompleteDefinition())
 147       return {};
 148   }
 149   // TODO: handle comments for function parameters properly.
 150   if (isa<ParmVarDecl>(D))
 151     return {};
 152
 153   // TODO: we could look up template parameter documentation in the template
 154   // documentation.
 155   if (isa<TemplateTypeParmDecl>(D) ||
 156       isa<NonTypeTemplateParmDecl>(D) ||
 157       isa<TemplateTemplateParmDecl>(D))
 158     return {};
 159
 160   // Find declaration location.
 161   // For Objective-C declarations we generally don't expect to have multiple
 162   // declarators, thus use declaration starting location as the "declaration
 163   // location".
 164   // For all other declarations multiple declarators are used quite frequently,
 165   // so we use the location of the identifier as the "declaration location".
 166   if (isa<ObjCMethodDecl>(D) || isa<ObjCContainerDecl>(D) ||
 167       isa<ObjCPropertyDecl>(D) ||
 168       isa<RedeclarableTemplateDecl>(D) ||
 169       isa<ClassTemplateSpecializationDecl>(D) ||
 170       // Allow association with Y across {} in `typedef struct X {} Y`.
 171       isa<TypedefDecl>(D))
 172     return D->getBeginLoc();
 173   else {
 174     const SourceLocation DeclLoc = D->getLocation();
 175     if (DeclLoc.isMacroID()) {
 176       if (isa<TypedefDecl>(D)) {
 177         // If location of the typedef name is in a macro, it is because being
 178         // declared via a macro. Try using declaration's starting location as
 179         // the "declaration location".
 180         return D->getBeginLoc();
 181       } else if (const auto *TD = dyn_cast<TagDecl>(D)) {
 182         // If location of the tag decl is inside a macro, but the spelling of
 183         // the tag name comes from a macro argument, it looks like a special
 184         // macro like NS_ENUM is being used to define the tag decl.  In that
 185         // case, adjust the source location to the expansion loc so that we can
 186         // attach the comment to the tag decl.
 187         if (SourceMgr.isMacroArgExpansion(DeclLoc) &&
 188             TD->isCompleteDefinition())
 189           return SourceMgr.getExpansionLoc(DeclLoc);
 190       }
 191     }
 192     return DeclLoc;
 193   }
 194
 195   return {};
 196 }
 197
 198 RawComment *ASTContext::getRawCommentForDeclNoCacheImpl(
 199     const Decl *D, const SourceLocation RepresentativeLocForDecl,
 200     const std::map<unsigned, RawComment *> &CommentsInTheFile) const {
 201   // If the declaration doesn't map directly to a location in a file, we
 202   // can't find the comment.
 203   if (RepresentativeLocForDecl.isInvalid() ||
 204       !RepresentativeLocForDecl.isFileID())
 205     return nullptr;
 206
 207   // If there are no comments anywhere, we won't find anything.
 208   if (CommentsInTheFile.empty())
 209     return nullptr;
 210
 211   // Decompose the location for the declaration and find the beginning of the
 212   // file buffer.
 213   const std::pair<FileID, unsigned> DeclLocDecomp =
 214       SourceMgr.getDecomposedLoc(RepresentativeLocForDecl);
 215
 216   // Slow path.
 217   auto OffsetCommentBehindDecl =
 218       CommentsInTheFile.lower_bound(DeclLocDecomp.second);
 219
 220   // First check whether we have a trailing comment.
 221   if (OffsetCommentBehindDecl != CommentsInTheFile.end()) {
 222     RawComment *CommentBehindDecl = OffsetCommentBehindDecl->second;
 223     if ((CommentBehindDecl->isDocumentation() ||
 224          LangOpts.CommentOpts.ParseAllComments) &&
 225         CommentBehindDecl->isTrailingComment() &&
 226         (isa<FieldDecl>(D) || isa<EnumConstantDecl>(D) || isa<VarDecl>(D) ||
 227          isa<ObjCMethodDecl>(D) || isa<ObjCPropertyDecl>(D))) {
 228
 229       // Check that Doxygen trailing comment comes after the declaration, starts
 230       // on the same line and in the same file as the declaration.
 231       if (SourceMgr.getLineNumber(DeclLocDecomp.first, DeclLocDecomp.second) ==
 232           Comments.getCommentBeginLine(CommentBehindDecl, DeclLocDecomp.first,
 233                                        OffsetCommentBehindDecl->first)) {
 234         return CommentBehindDecl;
 235       }
 236     }
 237   }
 238
 239   // The comment just after the declaration was not a trailing comment.
 240   // Let's look at the previous comment.
 241   if (OffsetCommentBehindDecl == CommentsInTheFile.begin())
 242     return nullptr;
 243
 244   auto OffsetCommentBeforeDecl = --OffsetCommentBehindDecl;
 245   RawComment *CommentBeforeDecl = OffsetCommentBeforeDecl->second;
 246
 247   // Check that we actually have a non-member Doxygen comment.
 248   if (!(CommentBeforeDecl->isDocumentation() ||
 249         LangOpts.CommentOpts.ParseAllComments) ||
 250       CommentBeforeDecl->isTrailingComment())
 251     return nullptr;
 252
 253   // Decompose the end of the comment.
 254   const unsigned CommentEndOffset =
 255       Comments.getCommentEndOffset(CommentBeforeDecl);
 256
 257   // Get the corresponding buffer.
 258   bool Invalid = false;
 259   const char *Buffer = SourceMgr.getBufferData(DeclLocDecomp.first,
 260                                                &Invalid).data();
 261   if (Invalid)
 262     return nullptr;
 263
 264   // Extract text between the comment and declaration.
 265   StringRef Text(Buffer + CommentEndOffset,
 266                  DeclLocDecomp.second - CommentEndOffset);
 267
 268   // There should be no other declarations or preprocessor directives between
 269   // comment and declaration.
 270   if (Text.find_first_of(";{}#@") != StringRef::npos)
 271     return nullptr;
 272
 273   return CommentBeforeDecl;
 274 }
 275
 276 RawComment *ASTContext::getRawCommentForDeclNoCache(const Decl *D) const {
 277   const SourceLocation DeclLoc = getDeclLocForCommentSearch(D, SourceMgr);
 278
 279   // If the declaration doesn't map directly to a location in a file, we
 280   // can't find the comment.
 281   if (DeclLoc.isInvalid() || !DeclLoc.isFileID())
 282     return nullptr;
 283
 284   if (ExternalSource && !CommentsLoaded) {
 285     ExternalSource->ReadComments();
 286     CommentsLoaded = true;
 287   }
 288
 289   if (Comments.empty())
 290     return nullptr;
 291
 292   const FileID File = SourceMgr.getDecomposedLoc(DeclLoc).first;
 293   const auto CommentsInThisFile = Comments.getCommentsInFile(File);
 294   if (!CommentsInThisFile || CommentsInThisFile->empty())
 295     return nullptr;
 296
 297   return getRawCommentForDeclNoCacheImpl(D, DeclLoc, *CommentsInThisFile);
 298 }
 299
 300 void ASTContext::addComment(const RawComment &RC) {
 301   assert(LangOpts.RetainCommentsFromSystemHeaders ||
 302          !SourceMgr.isInSystemHeader(RC.getSourceRange().getBegin()));
 303   Comments.addComment(RC, LangOpts.CommentOpts, BumpAlloc);
 304 }
 305
 306 /// If we have a 'templated' declaration for a template, adjust 'D' to
 307 /// refer to the actual template.
 308 /// If we have an implicit instantiation, adjust 'D' to refer to template.
 309 static const Decl &adjustDeclToTemplate(const Decl &D) {
 310   if (const auto *FD = dyn_cast<FunctionDecl>(&D)) {
 311     // Is this function declaration part of a function template?
 312     if (const FunctionTemplateDecl *FTD = FD->getDescribedFunctionTemplate())
 313       return *FTD;
 314
 315     // Nothing to do if function is not an implicit instantiation.
 316     if (FD->getTemplateSpecializationKind() != TSK_ImplicitInstantiation)
 317       return D;
 318
 319     // Function is an implicit instantiation of a function template?
 320     if (const FunctionTemplateDecl *FTD = FD->getPrimaryTemplate())
 321       return *FTD;
 322
 323     // Function is instantiated from a member definition of a class template?
 324     if (const FunctionDecl *MemberDecl =
 325             FD->getInstantiatedFromMemberFunction())
 326       return *MemberDecl;
 327
 328     return D;
 329   }
 330   if (const auto *VD = dyn_cast<VarDecl>(&D)) {
 331     // Static data member is instantiated from a member definition of a class
 332     // template?
 333     if (VD->isStaticDataMember())
 334       if (const VarDecl *MemberDecl = VD->getInstantiatedFromStaticDataMember())
 335         return *MemberDecl;
 336
 337     return D;
 338   }
 339   if (const auto *CRD = dyn_cast<CXXRecordDecl>(&D)) {
 340     // Is this class declaration part of a class template?
 341     if (const ClassTemplateDecl *CTD = CRD->getDescribedClassTemplate())
 342       return *CTD;
 343
 344     // Class is an implicit instantiation of a class template or partial
 345     // specialization?
 346     if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CRD)) {
 347       if (CTSD->getSpecializationKind() != TSK_ImplicitInstantiation)
 348         return D;
 349       llvm::PointerUnion<ClassTemplateDecl *,
 350                          ClassTemplatePartialSpecializationDecl *>
 351           PU = CTSD->getSpecializedTemplateOrPartial();
 352       return PU.is<ClassTemplateDecl *>()
 353                  ? *static_cast<const Decl *>(PU.get<ClassTemplateDecl *>())
 354                  : *static_cast<const Decl *>(
 355                        PU.get<ClassTemplatePartialSpecializationDecl *>());
 356     }
 357
 358     // Class is instantiated from a member definition of a class template?
 359     if (const MemberSpecializationInfo *Info =
 360             CRD->getMemberSpecializationInfo())
 361       return *Info->getInstantiatedFrom();
 362
 363     return D;
 364   }
 365   if (const auto *ED = dyn_cast<EnumDecl>(&D)) {
 366     // Enum is instantiated from a member definition of a class template?
 367     if (const EnumDecl *MemberDecl = ED->getInstantiatedFromMemberEnum())
 368       return *MemberDecl;
 369
 370     return D;
 371   }
 372   // FIXME: Adjust alias templates?
 373   return D;
 374 }
 375
 376 const RawComment *ASTContext::getRawCommentForAnyRedecl(
 377                                                 const Decl *D,
 378                                                 const Decl **OriginalDecl) const {
 379   if (!D) {
 380     if (OriginalDecl)
 381       OriginalDecl = nullptr;
 382     return nullptr;
 383   }
 384
 385   D = &adjustDeclToTemplate(*D);
 386
 387   // Any comment directly attached to D?
 388   {
 389     auto DeclComment = DeclRawComments.find(D);
 390     if (DeclComment != DeclRawComments.end()) {
 391       if (OriginalDecl)
 392         *OriginalDecl = D;
 393       return DeclComment->second;
 394     }
 395   }
 396
 397   // Any comment attached to any redeclaration of D?
 398   const Decl *CanonicalD = D->getCanonicalDecl();
 399   if (!CanonicalD)
 400     return nullptr;
 401
 402   {
 403     auto RedeclComment = RedeclChainComments.find(CanonicalD);
 404     if (RedeclComment != RedeclChainComments.end()) {
 405       if (OriginalDecl)
 406         *OriginalDecl = RedeclComment->second;
 407       auto CommentAtRedecl = DeclRawComments.find(RedeclComment->second);
 408       assert(CommentAtRedecl != DeclRawComments.end() &&
 409              "This decl is supposed to have comment attached.");
 410       return CommentAtRedecl->second;
 411     }
 412   }
 413
 414   // Any redeclarations of D that we haven't checked for comments yet?
 415   // We can't use DenseMap::iterator directly since it'd get invalid.
 416   auto LastCheckedRedecl = [this, CanonicalD]() -> const Decl * {
 417     auto LookupRes = CommentlessRedeclChains.find(CanonicalD);
 418     if (LookupRes != CommentlessRedeclChains.end())
 419       return LookupRes->second;
 420     return nullptr;
 421   }();
 422
 423   for (const auto Redecl : D->redecls()) {
 424     assert(Redecl);
 425     // Skip all redeclarations that have been checked previously.
 426     if (LastCheckedRedecl) {
 427       if (LastCheckedRedecl == Redecl) {
 428         LastCheckedRedecl = nullptr;
 429       }
 430       continue;
 431     }
 432     const RawComment *RedeclComment = getRawCommentForDeclNoCache(Redecl);
 433     if (RedeclComment) {
 434       cacheRawCommentForDecl(*Redecl, *RedeclComment);
 435       if (OriginalDecl)
 436         *OriginalDecl = Redecl;
 437       return RedeclComment;
 438     }
 439     CommentlessRedeclChains[CanonicalD] = Redecl;
 440   }
 441
 442   if (OriginalDecl)
 443     *OriginalDecl = nullptr;
 444   return nullptr;
 445 }
 446
 447 void ASTContext::cacheRawCommentForDecl(const Decl &OriginalD,
 448                                         const RawComment &Comment) const {
 449   assert(Comment.isDocumentation() || LangOpts.CommentOpts.ParseAllComments);
 450   DeclRawComments.try_emplace(&OriginalD, &Comment);
 451   const Decl *const CanonicalDecl = OriginalD.getCanonicalDecl();
 452   RedeclChainComments.try_emplace(CanonicalDecl, &OriginalD);
 453   CommentlessRedeclChains.erase(CanonicalDecl);
 454 }
 455
 456 static void addRedeclaredMethods(const ObjCMethodDecl *ObjCMethod,
 457                    SmallVectorImpl<const NamedDecl *> &Redeclared) {
 458   const DeclContext *DC = ObjCMethod->getDeclContext();
 459   if (const auto *IMD = dyn_cast<ObjCImplDecl>(DC)) {
 460     const ObjCInterfaceDecl *ID = IMD->getClassInterface();
 461     if (!ID)
 462       return;
 463     // Add redeclared method here.
 464     for (const auto *Ext : ID->known_extensions()) {
 465       if (ObjCMethodDecl *RedeclaredMethod =
 466             Ext->getMethod(ObjCMethod->getSelector(),
 467                                   ObjCMethod->isInstanceMethod()))
 468         Redeclared.push_back(RedeclaredMethod);
 469     }
 470   }
 471 }
 472
 473 void ASTContext::attachCommentsToJustParsedDecls(ArrayRef<Decl *> Decls,
 474                                                  const Preprocessor *PP) {
 475   if (Comments.empty() || Decls.empty())
 476     return;
 477
 478   FileID File;
 479   for (Decl *D : Decls) {
 480     SourceLocation Loc = D->getLocation();
 481     if (Loc.isValid()) {
 482       // See if there are any new comments that are not attached to a decl.
 483       // The location doesn't have to be precise - we care only about the file.
 484       File = SourceMgr.getDecomposedLoc(Loc).first;
 485       break;
 486     }
 487   }
 488
 489   if (File.isInvalid())
 490     return;
 491
 492   auto CommentsInThisFile = Comments.getCommentsInFile(File);
 493   if (!CommentsInThisFile || CommentsInThisFile->empty() ||
 494       CommentsInThisFile->rbegin()->second->isAttached())
 495     return;
 496
 497   // There is at least one comment not attached to a decl.
 498   // Maybe it should be attached to one of Decls?
 499   //
 500   // Note that this way we pick up not only comments that precede the
 501   // declaration, but also comments that *follow* the declaration -- thanks to
 502   // the lookahead in the lexer: we've consumed the semicolon and looked
 503   // ahead through comments.
 504
 505   for (const Decl *D : Decls) {
 506     assert(D);
 507     if (D->isInvalidDecl())
 508       continue;
 509
 510     D = &adjustDeclToTemplate(*D);
 511
 512     const SourceLocation DeclLoc = getDeclLocForCommentSearch(D, SourceMgr);
 513
 514     if (DeclLoc.isInvalid() || !DeclLoc.isFileID())
 515       continue;
 516
 517     if (DeclRawComments.count(D) > 0)
 518       continue;
 519
 520     if (RawComment *const DocComment =
 521             getRawCommentForDeclNoCacheImpl(D, DeclLoc, *CommentsInThisFile)) {
 522       cacheRawCommentForDecl(*D, *DocComment);
 523       comments::FullComment *FC = DocComment->parse(*this, PP, D);
 524       ParsedComments[D->getCanonicalDecl()] = FC;
 525     }
 526   }
 527 }
 528
 529 comments::FullComment *ASTContext::cloneFullComment(comments::FullComment *FC,
 530                                                     const Decl *D) const {
 531   auto *ThisDeclInfo = new (*this) comments::DeclInfo;
 532   ThisDeclInfo->CommentDecl = D;
 533   ThisDeclInfo->IsFilled = false;
 534   ThisDeclInfo->fill();
 535   ThisDeclInfo->CommentDecl = FC->getDecl();
 536   if (!ThisDeclInfo->TemplateParameters)
 537     ThisDeclInfo->TemplateParameters = FC->getDeclInfo()->TemplateParameters;
 538   comments::FullComment *CFC =
 539     new (*this) comments::FullComment(FC->getBlocks(),
 540                                       ThisDeclInfo);
 541   return CFC;
 542 }
 543
 544 comments::FullComment *ASTContext::getLocalCommentForDeclUncached(const Decl *D) const {
 545   const RawComment *RC = getRawCommentForDeclNoCache(D);
 546   return RC ? RC->parse(*this, nullptr, D) : nullptr;
 547 }
 548
 549 comments::FullComment *ASTContext::getCommentForDecl(
 550                                               const Decl *D,
 551                                               const Preprocessor *PP) const {
 552   if (!D || D->isInvalidDecl())
 553     return nullptr;
 554   D = &adjustDeclToTemplate(*D);
 555
 556   const Decl *Canonical = D->getCanonicalDecl();
 557   llvm::DenseMap<const Decl *, comments::FullComment *>::iterator Pos =
 558       ParsedComments.find(Canonical);
 559
 560   if (Pos != ParsedComments.end()) {
 561     if (Canonical != D) {
 562       comments::FullComment *FC = Pos->second;
 563       comments::FullComment *CFC = cloneFullComment(FC, D);
 564       return CFC;
 565     }
 566     return Pos->second;
 567   }
 568
 569   const Decl *OriginalDecl = nullptr;
 570
 571   const RawComment *RC = getRawCommentForAnyRedecl(D, &OriginalDecl);
 572   if (!RC) {
 573     if (isa<ObjCMethodDecl>(D) || isa<FunctionDecl>(D)) {
 574       SmallVector<const NamedDecl*, 8> Overridden;
 575       const auto *OMD = dyn_cast<ObjCMethodDecl>(D);
 576       if (OMD && OMD->isPropertyAccessor())
 577         if (const ObjCPropertyDecl *PDecl = OMD->findPropertyDecl())
 578           if (comments::FullComment *FC = getCommentForDecl(PDecl, PP))
 579             return cloneFullComment(FC, D);
 580       if (OMD)
 581         addRedeclaredMethods(OMD, Overridden);
 582       getOverriddenMethods(dyn_cast<NamedDecl>(D), Overridden);
 583       for (unsigned i = 0, e = Overridden.size(); i < e; i++)
 584         if (comments::FullComment *FC = getCommentForDecl(Overridden[i], PP))
 585           return cloneFullComment(FC, D);
 586     }
 587     else if (const auto *TD = dyn_cast<TypedefNameDecl>(D)) {
 588       // Attach any tag type's documentation to its typedef if latter
 589       // does not have one of its own.
 590       QualType QT = TD->getUnderlyingType();
 591       if (const auto *TT = QT->getAs<TagType>())
 592         if (const Decl *TD = TT->getDecl())
 593           if (comments::FullComment *FC = getCommentForDecl(TD, PP))
 594             return cloneFullComment(FC, D);
 595     }
 596     else if (const auto *IC = dyn_cast<ObjCInterfaceDecl>(D)) {
 597       while (IC->getSuperClass()) {
 598         IC = IC->getSuperClass();
 599         if (comments::FullComment *FC = getCommentForDecl(IC, PP))
 600           return cloneFullComment(FC, D);
 601       }
 602     }
 603     else if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D)) {
 604       if (const ObjCInterfaceDecl *IC = CD->getClassInterface())
 605         if (comments::FullComment *FC = getCommentForDecl(IC, PP))
 606           return cloneFullComment(FC, D);
 607     }
 608     else if (const auto *RD = dyn_cast<CXXRecordDecl>(D)) {
 609       if (!(RD = RD->getDefinition()))
 610         return nullptr;
 611       // Check non-virtual bases.
 612       for (const auto &I : RD->bases()) {
 613         if (I.isVirtual() || (I.getAccessSpecifier() != AS_public))
 614           continue;
 615         QualType Ty = I.getType();
 616         if (Ty.isNull())
 617           continue;
 618         if (const CXXRecordDecl *NonVirtualBase = Ty->getAsCXXRecordDecl()) {
 619           if (!(NonVirtualBase= NonVirtualBase->getDefinition()))
 620             continue;
 621
 622           if (comments::FullComment *FC = getCommentForDecl((NonVirtualBase), PP))
 623             return cloneFullComment(FC, D);
 624         }
 625       }
 626       // Check virtual bases.
 627       for (const auto &I : RD->vbases()) {
 628         if (I.getAccessSpecifier() != AS_public)
 629           continue;
 630         QualType Ty = I.getType();
 631         if (Ty.isNull())
 632           continue;
 633         if (const CXXRecordDecl *VirtualBase = Ty->getAsCXXRecordDecl()) {
 634           if (!(VirtualBase= VirtualBase->getDefinition()))
 635             continue;
 636           if (comments::FullComment *FC = getCommentForDecl((VirtualBase), PP))
 637             return cloneFullComment(FC, D);
 638         }
 639       }
 640     }
 641     return nullptr;
 642   }
 643
 644   // If the RawComment was attached to other redeclaration of this Decl, we
 645   // should parse the comment in context of that other Decl.  This is important
 646   // because comments can contain references to parameter names which can be
 647   // different across redeclarations.
 648   if (D != OriginalDecl && OriginalDecl)
 649     return getCommentForDecl(OriginalDecl, PP);
 650
 651   comments::FullComment *FC = RC->parse(*this, PP, D);
 652   ParsedComments[Canonical] = FC;
 653   return FC;
 654 }
 655
 656 void
 657 ASTContext::CanonicalTemplateTemplateParm::Profile(llvm::FoldingSetNodeID &ID,
 658                                                    const ASTContext &C,
 659                                                TemplateTemplateParmDecl *Parm) {
 660   ID.AddInteger(Parm->getDepth());
 661   ID.AddInteger(Parm->getPosition());
 662   ID.AddBoolean(Parm->isParameterPack());
 663
 664   TemplateParameterList *Params = Parm->getTemplateParameters();
 665   ID.AddInteger(Params->size());
 666   for (TemplateParameterList::const_iterator P = Params->begin(),
 667                                           PEnd = Params->end();
 668        P != PEnd; ++P) {
 669     if (const auto *TTP = dyn_cast<TemplateTypeParmDecl>(*P)) {
 670       ID.AddInteger(0);
 671       ID.AddBoolean(TTP->isParameterPack());
 672       const TypeConstraint *TC = TTP->getTypeConstraint();
 673       ID.AddBoolean(TC != nullptr);
 674       if (TC)
 675         TC->getImmediatelyDeclaredConstraint()->Profile(ID, C,
 676                                                         /*Canonical=*/true);
 677       if (TTP->isExpandedParameterPack()) {
 678         ID.AddBoolean(true);
 679         ID.AddInteger(TTP->getNumExpansionParameters());
 680       } else
 681         ID.AddBoolean(false);
 682       continue;
 683     }
 684
 685     if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
 686       ID.AddInteger(1);
 687       ID.AddBoolean(NTTP->isParameterPack());
 688       ID.AddPointer(NTTP->getType().getCanonicalType().getAsOpaquePtr());
 689       if (NTTP->isExpandedParameterPack()) {
 690         ID.AddBoolean(true);
 691         ID.AddInteger(NTTP->getNumExpansionTypes());
 692         for (unsigned I = 0, N = NTTP->getNumExpansionTypes(); I != N; ++I) {
 693           QualType T = NTTP->getExpansionType(I);
 694           ID.AddPointer(T.getCanonicalType().getAsOpaquePtr());
 695         }
 696       } else
 697         ID.AddBoolean(false);
 698       continue;
 699     }
 700
 701     auto *TTP = cast<TemplateTemplateParmDecl>(*P);
 702     ID.AddInteger(2);
 703     Profile(ID, C, TTP);
 704   }
 705   Expr *RequiresClause = Parm->getTemplateParameters()->getRequiresClause();
 706   ID.AddBoolean(RequiresClause != nullptr);
 707   if (RequiresClause)
 708     RequiresClause->Profile(ID, C, /*Canonical=*/true);
 709 }
 710
 711 static Expr *
 712 canonicalizeImmediatelyDeclaredConstraint(const ASTContext &C, Expr *IDC,
 713                                           QualType ConstrainedType) {
 714   // This is a bit ugly - we need to form a new immediately-declared
 715   // constraint that references the new parameter; this would ideally
 716   // require semantic analysis (e.g. template<C T> struct S {}; - the
 717   // converted arguments of C<T> could be an argument pack if C is
 718   // declared as template<typename... T> concept C = ...).
 719   // We don't have semantic analysis here so we dig deep into the
 720   // ready-made constraint expr and change the thing manually.
 721   ConceptSpecializationExpr *CSE;
 722   if (const auto *Fold = dyn_cast<CXXFoldExpr>(IDC))
 723     CSE = cast<ConceptSpecializationExpr>(Fold->getLHS());
 724   else
 725     CSE = cast<ConceptSpecializationExpr>(IDC);
 726   ArrayRef<TemplateArgument> OldConverted = CSE->getTemplateArguments();
 727   SmallVector<TemplateArgument, 3> NewConverted;
 728   NewConverted.reserve(OldConverted.size());
 729   if (OldConverted.front().getKind() == TemplateArgument::Pack) {
 730     // The case:
 731     // template<typename... T> concept C = true;
 732     // template<C<int> T> struct S; -> constraint is C<{T, int}>
 733     NewConverted.push_back(ConstrainedType);
 734     for (auto &Arg : OldConverted.front().pack_elements().drop_front(1))
 735       NewConverted.push_back(Arg);
 736     TemplateArgument NewPack(NewConverted);
 737
 738     NewConverted.clear();
 739     NewConverted.push_back(NewPack);
 740     assert(OldConverted.size() == 1 &&
 741            "Template parameter pack should be the last parameter");
 742   } else {
 743     assert(OldConverted.front().getKind() == TemplateArgument::Type &&
 744            "Unexpected first argument kind for immediately-declared "
 745            "constraint");
 746     NewConverted.push_back(ConstrainedType);
 747     for (auto &Arg : OldConverted.drop_front(1))
 748       NewConverted.push_back(Arg);
 749   }
 750   Expr *NewIDC = ConceptSpecializationExpr::Create(
 751       C, CSE->getNamedConcept(), NewConverted, nullptr,
 752       CSE->isInstantiationDependent(), CSE->containsUnexpandedParameterPack());
 753
 754   if (auto *OrigFold = dyn_cast<CXXFoldExpr>(IDC))
 755     NewIDC = new (C) CXXFoldExpr(OrigFold->getType(), SourceLocation(), NewIDC,
 756                                  BinaryOperatorKind::BO_LAnd,
 757                                  SourceLocation(), /*RHS=*/nullptr,
 758                                  SourceLocation(), /*NumExpansions=*/None);
 759   return NewIDC;
 760 }
 761
 762 TemplateTemplateParmDecl *
 763 ASTContext::getCanonicalTemplateTemplateParmDecl(
 764                                           TemplateTemplateParmDecl *TTP) const {
 765   // Check if we already have a canonical template template parameter.
 766   llvm::FoldingSetNodeID ID;
 767   CanonicalTemplateTemplateParm::Profile(ID, *this, TTP);
 768   void *InsertPos = nullptr;
 769   CanonicalTemplateTemplateParm *Canonical
 770     = CanonTemplateTemplateParms.FindNodeOrInsertPos(ID, InsertPos);
 771   if (Canonical)
 772     return Canonical->getParam();
 773
 774   // Build a canonical template parameter list.
 775   TemplateParameterList *Params = TTP->getTemplateParameters();
 776   SmallVector<NamedDecl *, 4> CanonParams;
 777   CanonParams.reserve(Params->size());
 778   for (TemplateParameterList::const_iterator P = Params->begin(),
 779                                           PEnd = Params->end();
 780        P != PEnd; ++P) {
 781     if (const auto *TTP = dyn_cast<TemplateTypeParmDecl>(*P)) {
 782       TemplateTypeParmDecl *NewTTP = TemplateTypeParmDecl::Create(*this,
 783           getTranslationUnitDecl(), SourceLocation(), SourceLocation(),
 784           TTP->getDepth(), TTP->getIndex(), nullptr, false,
 785           TTP->isParameterPack(), TTP->hasTypeConstraint(),
 786           TTP->isExpandedParameterPack() ?
 787           llvm::Optional<unsigned>(TTP->getNumExpansionParameters()) : None);
 788       if (const auto *TC = TTP->getTypeConstraint()) {
 789         QualType ParamAsArgument(NewTTP->getTypeForDecl(), 0);
 790         Expr *NewIDC = canonicalizeImmediatelyDeclaredConstraint(
 791                 *this, TC->getImmediatelyDeclaredConstraint(),
 792                 ParamAsArgument);
 793         TemplateArgumentListInfo CanonArgsAsWritten;
 794         if (auto *Args = TC->getTemplateArgsAsWritten())
 795           for (const auto &ArgLoc : Args->arguments())
 796             CanonArgsAsWritten.addArgument(
 797                 TemplateArgumentLoc(ArgLoc.getArgument(),
 798                                     TemplateArgumentLocInfo()));
 799         NewTTP->setTypeConstraint(
 800             NestedNameSpecifierLoc(),
 801             DeclarationNameInfo(TC->getNamedConcept()->getDeclName(),
 802                                 SourceLocation()), /*FoundDecl=*/nullptr,
 803             // Actually canonicalizing a TemplateArgumentLoc is difficult so we
 804             // simply omit the ArgsAsWritten
 805             TC->getNamedConcept(), /*ArgsAsWritten=*/nullptr, NewIDC);
 806       }
 807       CanonParams.push_back(NewTTP);
 808     } else if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(*P)) {
 809       QualType T = getCanonicalType(NTTP->getType());
 810       TypeSourceInfo *TInfo = getTrivialTypeSourceInfo(T);
 811       NonTypeTemplateParmDecl *Param;
 812       if (NTTP->isExpandedParameterPack()) {
 813         SmallVector<QualType, 2> ExpandedTypes;
 814         SmallVector<TypeSourceInfo *, 2> ExpandedTInfos;
 815         for (unsigned I = 0, N = NTTP->getNumExpansionTypes(); I != N; ++I) {
 816           ExpandedTypes.push_back(getCanonicalType(NTTP->getExpansionType(I)));
 817           ExpandedTInfos.push_back(
 818                                 getTrivialTypeSourceInfo(ExpandedTypes.back()));
 819         }
 820
 821         Param = NonTypeTemplateParmDecl::Create(*this, getTranslationUnitDecl(),
 822                                                 SourceLocation(),
 823                                                 SourceLocation(),
 824                                                 NTTP->getDepth(),
 825                                                 NTTP->getPosition(), nullptr,
 826                                                 T,
 827                                                 TInfo,
 828                                                 ExpandedTypes,
 829                                                 ExpandedTInfos);
 830       } else {
 831         Param = NonTypeTemplateParmDecl::Create(*this, getTranslationUnitDecl(),
 832                                                 SourceLocation(),
 833                                                 SourceLocation(),
 834                                                 NTTP->getDepth(),
 835                                                 NTTP->getPosition(), nullptr,
 836                                                 T,
 837                                                 NTTP->isParameterPack(),
 838                                                 TInfo);
 839       }
 840       if (AutoType *AT = T->getContainedAutoType()) {
 841         if (AT->isConstrained()) {
 842           Param->setPlaceholderTypeConstraint(
 843               canonicalizeImmediatelyDeclaredConstraint(
 844                   *this, NTTP->getPlaceholderTypeConstraint(), T));
 845         }
 846       }
 847       CanonParams.push_back(Param);
 848
 849     } else
 850       CanonParams.push_back(getCanonicalTemplateTemplateParmDecl(
 851                                            cast<TemplateTemplateParmDecl>(*P)));
 852   }
 853
 854   Expr *CanonRequiresClause = nullptr;
 855   if (Expr *RequiresClause = TTP->getTemplateParameters()->getRequiresClause())
 856     CanonRequiresClause = RequiresClause;
 857
 858   TemplateTemplateParmDecl *CanonTTP
 859     = TemplateTemplateParmDecl::Create(*this, getTranslationUnitDecl(),
 860                                        SourceLocation(), TTP->getDepth(),
 861                                        TTP->getPosition(),
 862                                        TTP->isParameterPack(),
 863                                        nullptr,
 864                          TemplateParameterList::Create(*this, SourceLocation(),
 865                                                        SourceLocation(),
 866                                                        CanonParams,
 867                                                        SourceLocation(),
 868                                                        CanonRequiresClause));
 869
 870   // Get the new insert position for the node we care about.
 871   Canonical = CanonTemplateTemplateParms.FindNodeOrInsertPos(ID, InsertPos);
 872   assert(!Canonical && "Shouldn't be in the map!");
 873   (void)Canonical;
 874
 875   // Create the canonical template template parameter entry.
 876   Canonical = new (*this) CanonicalTemplateTemplateParm(CanonTTP);
 877   CanonTemplateTemplateParms.InsertNode(Canonical, InsertPos);
 878   return CanonTTP;
 879 }
 880
 881 CXXABI *ASTContext::createCXXABI(const TargetInfo &T) {
 882   if (!LangOpts.CPlusPlus) return nullptr;
 883
 884   switch (T.getCXXABI().getKind()) {
 885   case TargetCXXABI::Fuchsia:
 886   case TargetCXXABI::GenericARM: // Same as Itanium at this level
 887   case TargetCXXABI::iOS:
 888   case TargetCXXABI::iOS64:
 889   case TargetCXXABI::WatchOS:
 890   case TargetCXXABI::GenericAArch64:
 891   case TargetCXXABI::GenericMIPS:
 892   case TargetCXXABI::GenericItanium:
 893   case TargetCXXABI::WebAssembly:
 894   case TargetCXXABI::XL:
 895     return CreateItaniumCXXABI(*this);
 896   case TargetCXXABI::Microsoft:
 897     return CreateMicrosoftCXXABI(*this);
 898   }
 899   llvm_unreachable("Invalid CXXABI type!");
 900 }
 901
 902 interp::Context &ASTContext::getInterpContext() {
 903   if (!InterpContext) {
 904     InterpContext.reset(new interp::Context(*this));
 905   }
 906   return *InterpContext.get();
 907 }
 908
 909 ParentMapContext &ASTContext::getParentMapContext() {
 910   if (!ParentMapCtx)
 911     ParentMapCtx.reset(new ParentMapContext(*this));
 912   return *ParentMapCtx.get();
 913 }
 914
 915 static const LangASMap *getAddressSpaceMap(const TargetInfo &T,
 916                                            const LangOptions &LOpts) {
 917   if (LOpts.FakeAddressSpaceMap) {
 918     // The fake address space map must have a distinct entry for each
 919     // language-specific address space.
 920     static const unsigned FakeAddrSpaceMap[] = {
 921         0, // Default
 922         1, // opencl_global
 923         3, // opencl_local
 924         2, // opencl_constant
 925         0, // opencl_private
 926         4, // opencl_generic
 927         5, // cuda_device
 928         6, // cuda_constant
 929         7, // cuda_shared
 930         8, // ptr32_sptr
 931         9, // ptr32_uptr
 932         10 // ptr64
 933     };
 934     return &FakeAddrSpaceMap;
 935   } else {
 936     return &T.getAddressSpaceMap();
 937   }
 938 }
 939
 940 static bool isAddrSpaceMapManglingEnabled(const TargetInfo &TI,
 941                                           const LangOptions &LangOpts) {
 942   switch (LangOpts.getAddressSpaceMapMangling()) {
 943   case LangOptions::ASMM_Target:
 944     return TI.useAddressSpaceMapMangling();
 945   case LangOptions::ASMM_On:
 946     return true;
 947   case LangOptions::ASMM_Off:
 948     return false;
 949   }
 950   llvm_unreachable("getAddressSpaceMapMangling() doesn't cover anything.");
 951 }
 952
 953 ASTContext::ASTContext(LangOptions &LOpts, SourceManager &SM,
 954                        IdentifierTable &idents, SelectorTable &sels,
 955                        Builtin::Context &builtins)
 956     : ConstantArrayTypes(this_()), FunctionProtoTypes(this_()),
 957       TemplateSpecializationTypes(this_()),
 958       DependentTemplateSpecializationTypes(this_()), AutoTypes(this_()),
 959       SubstTemplateTemplateParmPacks(this_()),
 960       CanonTemplateTemplateParms(this_()), SourceMgr(SM), LangOpts(LOpts),
 961       SanitizerBL(new SanitizerBlacklist(LangOpts.SanitizerBlacklistFiles, SM)),
 962       XRayFilter(new XRayFunctionFilter(LangOpts.XRayAlwaysInstrumentFiles,
 963                                         LangOpts.XRayNeverInstrumentFiles,
 964                                         LangOpts.XRayAttrListFiles, SM)),
 965       PrintingPolicy(LOpts), Idents(idents), Selectors(sels),
 966       BuiltinInfo(builtins), DeclarationNames(*this), Comments(SM),
 967       CommentCommandTraits(BumpAlloc, LOpts.CommentOpts),
 968       CompCategories(this_()), LastSDM(nullptr, 0) {
 969   TUDecl = TranslationUnitDecl::Create(*this);
 970   TraversalScope = {TUDecl};
 971 }
 972
 973 ASTContext::~ASTContext() {
 974   // Release the DenseMaps associated with DeclContext objects.
 975   // FIXME: Is this the ideal solution?
 976   ReleaseDeclContextMaps();
 977
 978   // Call all of the deallocation functions on all of their targets.
 979   for (auto &Pair : Deallocations)
 980     (Pair.first)(Pair.second);
 981
 982   // ASTRecordLayout objects in ASTRecordLayouts must always be destroyed
 983   // because they can contain DenseMaps.
 984   for (llvm::DenseMap<const ObjCContainerDecl*,
 985        const ASTRecordLayout*>::iterator
 986        I = ObjCLayouts.begin(), E = ObjCLayouts.end(); I != E; )
 987     // Increment in loop to prevent using deallocated memory.
 988     if (auto *R = const_cast<ASTRecordLayout *>((I++)->second))
 989       R->Destroy(*this);
 990
 991   for (llvm::DenseMap<const RecordDecl*, const ASTRecordLayout*>::iterator
 992        I = ASTRecordLayouts.begin(), E = ASTRecordLayouts.end(); I != E; ) {
 993     // Increment in loop to prevent using deallocated memory.
 994     if (auto *R = const_cast<ASTRecordLayout *>((I++)->second))
 995       R->Destroy(*this);
 996   }
 997
 998   for (llvm::DenseMap<const Decl*, AttrVec*>::iterator A = DeclAttrs.begin(),
 999                                                     AEnd = DeclAttrs.end();
1000        A != AEnd; ++A)
1001     A->second->~AttrVec();
1002
1003   for (const auto &Value : ModuleInitializers)
1004     Value.second->~PerModuleInitializers();
1005
1006   for (APValue *Value : APValueCleanups)
1007     Value->~APValue();
1008 }
1009
1010 void ASTContext::setTraversalScope(const std::vector<Decl *> &TopLevelDecls) {
1011   TraversalScope = TopLevelDecls;
1012   getParentMapContext().clear();
1013 }
1014
1015 void ASTContext::AddDeallocation(void (*Callback)(void *), void *Data) const {
1016   Deallocations.push_back({Callback, Data});
1017 }
1018
1019 void
1020 ASTContext::setExternalSource(IntrusiveRefCntPtr<ExternalASTSource> Source) {
1021   ExternalSource = std::move(Source);
1022 }
1023
1024 void ASTContext::PrintStats() const {
1025   llvm::errs() << "\n*** AST Context Stats:\n";
1026   llvm::errs() << "  " << Types.size() << " types total.\n";
1027
1028   unsigned counts[] = {
1029 #define TYPE(Name, Parent) 0,
1030 #define ABSTRACT_TYPE(Name, Parent)
1031 #include "clang/AST/TypeNodes.inc"
1032     0 // Extra
1033   };
1034
1035   for (unsigned i = 0, e = Types.size(); i != e; ++i) {
1036     Type *T = Types[i];
1037     counts[(unsigned)T->getTypeClass()]++;
1038   }
1039
1040   unsigned Idx = 0;
1041   unsigned TotalBytes = 0;
1042 #define TYPE(Name, Parent)                                              \
1043   if (counts[Idx])                                                      \
1044     llvm::errs() << "    " << counts[Idx] << " " << #Name               \
1045                  << " types, " << sizeof(Name##Type) << " each "        \
1046                  << "(" << counts[Idx] * sizeof(Name##Type)             \
1047                  << " bytes)\n";                                        \
1048   TotalBytes += counts[Idx] * sizeof(Name##Type);                       \
1049   ++Idx;
1050 #define ABSTRACT_TYPE(Name, Parent)
1051 #include "clang/AST/TypeNodes.inc"
1052
1053   llvm::errs() << "Total bytes = " << TotalBytes << "\n";
1054
1055   // Implicit special member functions.
1056   llvm::errs() << NumImplicitDefaultConstructorsDeclared << "/"
1057                << NumImplicitDefaultConstructors
1058                << " implicit default constructors created\n";
1059   llvm::errs() << NumImplicitCopyConstructorsDeclared << "/"
1060                << NumImplicitCopyConstructors
1061                << " implicit copy constructors created\n";
1062   if (getLangOpts().CPlusPlus)
1063     llvm::errs() << NumImplicitMoveConstructorsDeclared << "/"
1064                  << NumImplicitMoveConstructors
1065                  << " implicit move constructors created\n";
1066   llvm::errs() << NumImplicitCopyAssignmentOperatorsDeclared << "/"
1067                << NumImplicitCopyAssignmentOperators
1068                << " implicit copy assignment operators created\n";
1069   if (getLangOpts().CPlusPlus)
1070     llvm::errs() << NumImplicitMoveAssignmentOperatorsDeclared << "/"
1071                  << NumImplicitMoveAssignmentOperators
1072                  << " implicit move assignment operators created\n";
1073   llvm::errs() << NumImplicitDestructorsDeclared << "/"
1074                << NumImplicitDestructors
1075                << " implicit destructors created\n";
1076
1077   if (ExternalSource) {
1078     llvm::errs() << "\n";
1079     ExternalSource->PrintStats();
1080   }
1081
1082   BumpAlloc.PrintStats();
1083 }
1084
1085 void ASTContext::mergeDefinitionIntoModule(NamedDecl *ND, Module *M,
1086                                            bool NotifyListeners) {
1087   if (NotifyListeners)
1088     if (auto *Listener = getASTMutationListener())
1089       Listener->RedefinedHiddenDefinition(ND, M);
1090
1091   MergedDefModules[cast<NamedDecl>(ND->getCanonicalDecl())].push_back(M);
1092 }
1093
1094 void ASTContext::deduplicateMergedDefinitonsFor(NamedDecl *ND) {
1095   auto It = MergedDefModules.find(cast<NamedDecl>(ND->getCanonicalDecl()));
1096   if (It == MergedDefModules.end())
1097     return;
1098
1099   auto &Merged = It->second;
1100   llvm::DenseSet<Module*> Found;
1101   for (Module *&M : Merged)
1102     if (!Found.insert(M).second)
1103       M = nullptr;
1104   Merged.erase(std::remove(Merged.begin(), Merged.end(), nullptr), Merged.end());
1105 }
1106
1107 ArrayRef<Module *>
1108 ASTContext::getModulesWithMergedDefinition(const NamedDecl *Def) {
1109   auto MergedIt =
1110       MergedDefModules.find(cast<NamedDecl>(Def->getCanonicalDecl()));
1111   if (MergedIt == MergedDefModules.end())
1112     return None;
1113   return MergedIt->second;
1114 }
1115
1116 void ASTContext::PerModuleInitializers::resolve(ASTContext &Ctx) {
1117   if (LazyInitializers.empty())
1118     return;
1119
1120   auto *Source = Ctx.getExternalSource();
1121   assert(Source && "lazy initializers but no external source");
1122
1123   auto LazyInits = std::move(LazyInitializers);
1124   LazyInitializers.clear();
1125
1126   for (auto ID : LazyInits)
1127     Initializers.push_back(Source->GetExternalDecl(ID));
1128
1129   assert(LazyInitializers.empty() &&
1130          "GetExternalDecl for lazy module initializer added more inits");
1131 }
1132
1133 void ASTContext::addModuleInitializer(Module *M, Decl *D) {
1134   // One special case: if we add a module initializer that imports another
1135   // module, and that module's only initializer is an ImportDecl, simplify.
1136   if (const auto *ID = dyn_cast<ImportDecl>(D)) {
1137     auto It = ModuleInitializers.find(ID->getImportedModule());
1138
1139     // Maybe the ImportDecl does nothing at all. (Common case.)
1140     if (It == ModuleInitializers.end())
1141       return;
1142
1143     // Maybe the ImportDecl only imports another ImportDecl.
1144     auto &Imported = *It->second;
1145     if (Imported.Initializers.size() + Imported.LazyInitializers.size() == 1) {
1146       Imported.resolve(*this);
1147       auto *OnlyDecl = Imported.Initializers.front();
1148       if (isa<ImportDecl>(OnlyDecl))
1149         D = OnlyDecl;
1150     }
1151   }
1152
1153   auto *&Inits = ModuleInitializers[M];
1154   if (!Inits)
1155     Inits = new (*this) PerModuleInitializers;
1156   Inits->Initializers.push_back(D);
1157 }
1158
1159 void ASTContext::addLazyModuleInitializers(Module *M, ArrayRef<uint32_t> IDs) {
1160   auto *&Inits = ModuleInitializers[M];
1161   if (!Inits)
1162     Inits = new (*this) PerModuleInitializers;
1163   Inits->LazyInitializers.insert(Inits->LazyInitializers.end(),
1164                                  IDs.begin(), IDs.end());
1165 }
1166
1167 ArrayRef<Decl *> ASTContext::getModuleInitializers(Module *M) {
1168   auto It = ModuleInitializers.find(M);
1169   if (It == ModuleInitializers.end())
1170     return None;
1171
1172   auto *Inits = It->second;
1173   Inits->resolve(*this);
1174   return Inits->Initializers;
1175 }
1176
1177 ExternCContextDecl *ASTContext::getExternCContextDecl() const {
1178   if (!ExternCContext)
1179     ExternCContext = ExternCContextDecl::Create(*this, getTranslationUnitDecl());
1180
1181   return ExternCContext;
1182 }
1183
1184 BuiltinTemplateDecl *
1185 ASTContext::buildBuiltinTemplateDecl(BuiltinTemplateKind BTK,
1186                                      const IdentifierInfo *II) const {
1187   auto *BuiltinTemplate = BuiltinTemplateDecl::Create(*this, TUDecl, II, BTK);
1188   BuiltinTemplate->setImplicit();
1189   TUDecl->addDecl(BuiltinTemplate);
1190
1191   return BuiltinTemplate;
1192 }
1193
1194 BuiltinTemplateDecl *
1195 ASTContext::getMakeIntegerSeqDecl() const {
1196   if (!MakeIntegerSeqDecl)
1197     MakeIntegerSeqDecl = buildBuiltinTemplateDecl(BTK__make_integer_seq,
1198                                                   getMakeIntegerSeqName());
1199   return MakeIntegerSeqDecl;
1200 }
1201
1202 BuiltinTemplateDecl *
1203 ASTContext::getTypePackElementDecl() const {
1204   if (!TypePackElementDecl)
1205     TypePackElementDecl = buildBuiltinTemplateDecl(BTK__type_pack_element,
1206                                                    getTypePackElementName());
1207   return TypePackElementDecl;
1208 }
1209
1210 RecordDecl *ASTContext::buildImplicitRecord(StringRef Name,
1211                                             RecordDecl::TagKind TK) const {
1212   SourceLocation Loc;
1213   RecordDecl *NewDecl;
1214   if (getLangOpts().CPlusPlus)
1215     NewDecl = CXXRecordDecl::Create(*this, TK, getTranslationUnitDecl(), Loc,
1216                                     Loc, &Idents.get(Name));
1217   else
1218     NewDecl = RecordDecl::Create(*this, TK, getTranslationUnitDecl(), Loc, Loc,
1219                                  &Idents.get(Name));
1220   NewDecl->setImplicit();
1221   NewDecl->addAttr(TypeVisibilityAttr::CreateImplicit(
1222       const_cast<ASTContext &>(*this), TypeVisibilityAttr::Default));
1223   return NewDecl;
1224 }
1225
1226 TypedefDecl *ASTContext::buildImplicitTypedef(QualType T,
1227                                               StringRef Name) const {
1228   TypeSourceInfo *TInfo = getTrivialTypeSourceInfo(T);
1229   TypedefDecl *NewDecl = TypedefDecl::Create(
1230       const_cast<ASTContext &>(*this), getTranslationUnitDecl(),
1231       SourceLocation(), SourceLocation(), &Idents.get(Name), TInfo);
1232   NewDecl->setImplicit();
1233   return NewDecl;
1234 }
1235
1236 TypedefDecl *ASTContext::getInt128Decl() const {
1237   if (!Int128Decl)
1238     Int128Decl = buildImplicitTypedef(Int128Ty, "__int128_t");
1239   return Int128Decl;
1240 }
1241
1242 TypedefDecl *ASTContext::getUInt128Decl() const {
1243   if (!UInt128Decl)
1244     UInt128Decl = buildImplicitTypedef(UnsignedInt128Ty, "__uint128_t");
1245   return UInt128Decl;
1246 }
1247
1248 void ASTContext::InitBuiltinType(CanQualType &R, BuiltinType::Kind K) {
1249   auto *Ty = new (*this, TypeAlignment) BuiltinType(K);
1250   R = CanQualType::CreateUnsafe(QualType(Ty, 0));
1251   Types.push_back(Ty);
1252 }
1253
1254 void ASTContext::InitBuiltinTypes(const TargetInfo &Target,
1255                                   const TargetInfo *AuxTarget) {
1256   assert((!this->Target || this->Target == &Target) &&
1257          "Incorrect target reinitialization");
1258   assert(VoidTy.isNull() && "Context reinitialized?");
1259
1260   this->Target = &Target;
1261   this->AuxTarget = AuxTarget;
1262
1263   ABI.reset(createCXXABI(Target));
1264   AddrSpaceMap = getAddressSpaceMap(Target, LangOpts);
1265   AddrSpaceMapMangling = isAddrSpaceMapManglingEnabled(Target, LangOpts);
1266
1267   // C99 6.2.5p19.
1268   InitBuiltinType(VoidTy,              BuiltinType::Void);
1269
1270   // C99 6.2.5p2.
1271   InitBuiltinType(BoolTy,              BuiltinType::Bool);
1272   // C99 6.2.5p3.
1273   if (LangOpts.CharIsSigned)
1274     InitBuiltinType(CharTy,            BuiltinType::Char_S);
1275   else
1276     InitBuiltinType(CharTy,            BuiltinType::Char_U);
1277   // C99 6.2.5p4.
1278   InitBuiltinType(SignedCharTy,        BuiltinType::SChar);
1279   InitBuiltinType(ShortTy,             BuiltinType::Short);
1280   InitBuiltinType(IntTy,               BuiltinType::Int);
1281   InitBuiltinType(LongTy,              BuiltinType::Long);
1282   InitBuiltinType(LongLongTy,          BuiltinType::LongLong);
1283
1284   // C99 6.2.5p6.
1285   InitBuiltinType(UnsignedCharTy,      BuiltinType::UChar);
1286   InitBuiltinType(UnsignedShortTy,     BuiltinType::UShort);
1287   InitBuiltinType(UnsignedIntTy,       BuiltinType::UInt);
1288   InitBuiltinType(UnsignedLongTy,      BuiltinType::ULong);
1289   InitBuiltinType(UnsignedLongLongTy,  BuiltinType::ULongLong);
1290
1291   // C99 6.2.5p10.
1292   InitBuiltinType(FloatTy,             BuiltinType::Float);
1293   InitBuiltinType(DoubleTy,            BuiltinType::Double);
1294   InitBuiltinType(LongDoubleTy,        BuiltinType::LongDouble);
1295
1296   // GNU extension, __float128 for IEEE quadruple precision
1297   InitBuiltinType(Float128Ty,          BuiltinType::Float128);
1298
1299   // C11 extension ISO/IEC TS 18661-3
1300   InitBuiltinType(Float16Ty,           BuiltinType::Float16);
1301
1302   // ISO/IEC JTC1 SC22 WG14 N1169 Extension
1303   InitBuiltinType(ShortAccumTy,            BuiltinType::ShortAccum);
1304   InitBuiltinType(AccumTy,                 BuiltinType::Accum);
1305   InitBuiltinType(LongAccumTy,             BuiltinType::LongAccum);
1306   InitBuiltinType(UnsignedShortAccumTy,    BuiltinType::UShortAccum);
1307   InitBuiltinType(UnsignedAccumTy,         BuiltinType::UAccum);
1308   InitBuiltinType(UnsignedLongAccumTy,     BuiltinType::ULongAccum);
1309   InitBuiltinType(ShortFractTy,            BuiltinType::ShortFract);
1310   InitBuiltinType(FractTy,                 BuiltinType::Fract);
1311   InitBuiltinType(LongFractTy,             BuiltinType::LongFract);
1312   InitBuiltinType(UnsignedShortFractTy,    BuiltinType::UShortFract);
1313   InitBuiltinType(UnsignedFractTy,         BuiltinType::UFract);
1314   InitBuiltinType(UnsignedLongFractTy,     BuiltinType::ULongFract);
1315   InitBuiltinType(SatShortAccumTy,         BuiltinType::SatShortAccum);
1316   InitBuiltinType(SatAccumTy,              BuiltinType::SatAccum);
1317   InitBuiltinType(SatLongAccumTy,          BuiltinType::SatLongAccum);
1318   InitBuiltinType(SatUnsignedShortAccumTy, BuiltinType::SatUShortAccum);
1319   InitBuiltinType(SatUnsignedAccumTy,      BuiltinType::SatUAccum);
1320   InitBuiltinType(SatUnsignedLongAccumTy,  BuiltinType::SatULongAccum);
1321   InitBuiltinType(SatShortFractTy,         BuiltinType::SatShortFract);
1322   InitBuiltinType(SatFractTy,              BuiltinType::SatFract);
1323   InitBuiltinType(SatLongFractTy,          BuiltinType::SatLongFract);
1324   InitBuiltinType(SatUnsignedShortFractTy, BuiltinType::SatUShortFract);
1325   InitBuiltinType(SatUnsignedFractTy,      BuiltinType::SatUFract);
1326   InitBuiltinType(SatUnsignedLongFractTy,  BuiltinType::SatULongFract);
1327
1328   // GNU extension, 128-bit integers.
1329   InitBuiltinType(Int128Ty,            BuiltinType::Int128);
1330   InitBuiltinType(UnsignedInt128Ty,    BuiltinType::UInt128);
1331
1332   // C++ 3.9.1p5
1333   if (TargetInfo::isTypeSigned(Target.getWCharType()))
1334     InitBuiltinType(WCharTy,           BuiltinType::WChar_S);
1335   else  // -fshort-wchar makes wchar_t be unsigned.
1336     InitBuiltinType(WCharTy,           BuiltinType::WChar_U);
1337   if (LangOpts.CPlusPlus && LangOpts.WChar)
1338     WideCharTy = WCharTy;
1339   else {
1340     // C99 (or C++ using -fno-wchar).
1341     WideCharTy = getFromTargetType(Target.getWCharType());
1342   }
1343
1344   WIntTy = getFromTargetType(Target.getWIntType());
1345
1346   // C++20 (proposed)
1347   InitBuiltinType(Char8Ty,              BuiltinType::Char8);
1348
1349   if (LangOpts.CPlusPlus) // C++0x 3.9.1p5, extension for C++
1350     InitBuiltinType(Char16Ty,           BuiltinType::Char16);
1351   else // C99
1352     Char16Ty = getFromTargetType(Target.getChar16Type());
1353
1354   if (LangOpts.CPlusPlus) // C++0x 3.9.1p5, extension for C++
1355     InitBuiltinType(Char32Ty,           BuiltinType::Char32);
1356   else // C99
1357     Char32Ty = getFromTargetType(Target.getChar32Type());
1358
1359   // Placeholder type for type-dependent expressions whose type is
1360   // completely unknown. No code should ever check a type against
1361   // DependentTy and users should never see it; however, it is here to
1362   // help diagnose failures to properly check for type-dependent
1363   // expressions.
1364   InitBuiltinType(DependentTy,         BuiltinType::Dependent);
1365
1366   // Placeholder type for functions.
1367   InitBuiltinType(OverloadTy,          BuiltinType::Overload);
1368
1369   // Placeholder type for bound members.
1370   InitBuiltinType(BoundMemberTy,       BuiltinType::BoundMember);
1371
1372   // Placeholder type for pseudo-objects.
1373   InitBuiltinType(PseudoObjectTy,      BuiltinType::PseudoObject);
1374
1375   // "any" type; useful for debugger-like clients.
1376   InitBuiltinType(UnknownAnyTy,        BuiltinType::UnknownAny);
1377
1378   // Placeholder type for unbridged ARC casts.
1379   InitBuiltinType(ARCUnbridgedCastTy,  BuiltinType::ARCUnbridgedCast);
1380
1381   // Placeholder type for builtin functions.
1382   InitBuiltinType(BuiltinFnTy,  BuiltinType::BuiltinFn);
1383
1384   // Placeholder type for OMP array sections.
1385   if (LangOpts.OpenMP)
1386     InitBuiltinType(OMPArraySectionTy, BuiltinType::OMPArraySection);
1387
1388   // C99 6.2.5p11.
1389   FloatComplexTy      = getComplexType(FloatTy);
1390   DoubleComplexTy     = getComplexType(DoubleTy);
1391   LongDoubleComplexTy = getComplexType(LongDoubleTy);
1392   Float128ComplexTy   = getComplexType(Float128Ty);
1393
1394   // Builtin types for 'id', 'Class', and 'SEL'.
1395   InitBuiltinType(ObjCBuiltinIdTy, BuiltinType::ObjCId);
1396   InitBuiltinType(ObjCBuiltinClassTy, BuiltinType::ObjCClass);
1397   InitBuiltinType(ObjCBuiltinSelTy, BuiltinType::ObjCSel);
1398
1399   if (LangOpts.OpenCL) {
1400 #define IMAGE_TYPE(ImgType, Id, SingletonId, Access, Suffix) \
1401     InitBuiltinType(SingletonId, BuiltinType::Id);
1402 #include "clang/Basic/OpenCLImageTypes.def"
1403
1404     InitBuiltinType(OCLSamplerTy, BuiltinType::OCLSampler);
1405     InitBuiltinType(OCLEventTy, BuiltinType::OCLEvent);
1406     InitBuiltinType(OCLClkEventTy, BuiltinType::OCLClkEvent);
1407     InitBuiltinType(OCLQueueTy, BuiltinType::OCLQueue);
1408     InitBuiltinType(OCLReserveIDTy, BuiltinType::OCLReserveID);
1409
1410 #define EXT_OPAQUE_TYPE(ExtType, Id, Ext) \
1411     InitBuiltinType(Id##Ty, BuiltinType::Id);
1412 #include "clang/Basic/OpenCLExtensionTypes.def"
1413   }
1414
1415   if (Target.hasAArch64SVETypes()) {
1416 #define SVE_TYPE(Name, Id, SingletonId) \
1417     InitBuiltinType(SingletonId, BuiltinType::Id);
1418 #include "clang/Basic/AArch64SVEACLETypes.def"
1419   }
1420
1421   // Builtin type for __objc_yes and __objc_no
1422   ObjCBuiltinBoolTy = (Target.useSignedCharForObjCBool() ?
1423                        SignedCharTy : BoolTy);
1424
1425   ObjCConstantStringType = QualType();
1426
1427   ObjCSuperType = QualType();
1428
1429   // void * type
1430   if (LangOpts.OpenCLVersion >= 200) {
1431     auto Q = VoidTy.getQualifiers();
1432     Q.setAddressSpace(LangAS::opencl_generic);
1433     VoidPtrTy = getPointerType(getCanonicalType(
1434         getQualifiedType(VoidTy.getUnqualifiedType(), Q)));
1435   } else {
1436     VoidPtrTy = getPointerType(VoidTy);
1437   }
1438
1439   // nullptr type (C++0x 2.14.7)
1440   InitBuiltinType(NullPtrTy,           BuiltinType::NullPtr);
1441
1442   // half type (OpenCL 6.1.1.1) / ARM NEON __fp16
1443   InitBuiltinType(HalfTy, BuiltinType::Half);
1444
1445   // Builtin type used to help define __builtin_va_list.
1446   VaListTagDecl = nullptr;
1447 }
1448
1449 DiagnosticsEngine &ASTContext::getDiagnostics() const {
1450   return SourceMgr.getDiagnostics();
1451 }
1452
1453 AttrVec& ASTContext::getDeclAttrs(const Decl *D) {
1454   AttrVec *&Result = DeclAttrs[D];
1455   if (!Result) {
1456     void *Mem = Allocate(sizeof(AttrVec));
1457     Result = new (Mem) AttrVec;
1458   }
1459
1460   return *Result;
1461 }
1462
1463 /// Erase the attributes corresponding to the given declaration.
1464 void ASTContext::eraseDeclAttrs(const Decl *D) {
1465   llvm::DenseMap<const Decl*, AttrVec*>::iterator Pos = DeclAttrs.find(D);
1466   if (Pos != DeclAttrs.end()) {
1467     Pos->second->~AttrVec();
1468     DeclAttrs.erase(Pos);
1469   }
1470 }
1471
1472 // FIXME: Remove ?
1473 MemberSpecializationInfo *
1474 ASTContext::getInstantiatedFromStaticDataMember(const VarDecl *Var) {
1475   assert(Var->isStaticDataMember() && "Not a static data member");
1476   return getTemplateOrSpecializationInfo(Var)
1477       .dyn_cast<MemberSpecializationInfo *>();
1478 }
1479
1480 ASTContext::TemplateOrSpecializationInfo
1481 ASTContext::getTemplateOrSpecializationInfo(const VarDecl *Var) {
1482   llvm::DenseMap<const VarDecl *, TemplateOrSpecializationInfo>::iterator Pos =
1483       TemplateOrInstantiation.find(Var);
1484   if (Pos == TemplateOrInstantiation.end())
1485     return {};
1486
1487   return Pos->second;
1488 }
1489
1490 void
1491 ASTContext::setInstantiatedFromStaticDataMember(VarDecl *Inst, VarDecl *Tmpl,
1492                                                 TemplateSpecializationKind TSK,
1493                                           SourceLocation PointOfInstantiation) {
1494   assert(Inst->isStaticDataMember() && "Not a static data member");
1495   assert(Tmpl->isStaticDataMember() && "Not a static data member");
1496   setTemplateOrSpecializationInfo(Inst, new (*this) MemberSpecializationInfo(
1497                                             Tmpl, TSK, PointOfInstantiation));
1498 }
1499
1500 void
1501 ASTContext::setTemplateOrSpecializationInfo(VarDecl *Inst,
1502                                             TemplateOrSpecializationInfo TSI) {
1503   assert(!TemplateOrInstantiation[Inst] &&
1504          "Already noted what the variable was instantiated from");
1505   TemplateOrInstantiation[Inst] = TSI;
1506 }
1507
1508 NamedDecl *
1509 ASTContext::getInstantiatedFromUsingDecl(NamedDecl *UUD) {
1510   auto Pos = InstantiatedFromUsingDecl.find(UUD);
1511   if (Pos == InstantiatedFromUsingDecl.end())
1512     return nullptr;
1513
1514   return Pos->second;
1515 }
1516
1517 void
1518 ASTContext::setInstantiatedFromUsingDecl(NamedDecl *Inst, NamedDecl *Pattern) {
1519   assert((isa<UsingDecl>(Pattern) ||
1520           isa<UnresolvedUsingValueDecl>(Pattern) ||
1521           isa<UnresolvedUsingTypenameDecl>(Pattern)) &&
1522          "pattern decl is not a using decl");
1523   assert((isa<UsingDecl>(Inst) ||
1524           isa<UnresolvedUsingValueDecl>(Inst) ||
1525           isa<UnresolvedUsingTypenameDecl>(Inst)) &&
1526          "instantiation did not produce a using decl");
1527   assert(!InstantiatedFromUsingDecl[Inst] && "pattern already exists");
1528   InstantiatedFromUsingDecl[Inst] = Pattern;
1529 }
1530
1531 UsingShadowDecl *
1532 ASTContext::getInstantiatedFromUsingShadowDecl(UsingShadowDecl *Inst) {
1533   llvm::DenseMap<UsingShadowDecl*, UsingShadowDecl*>::const_iterator Pos
1534     = InstantiatedFromUsingShadowDecl.find(Inst);
1535   if (Pos == InstantiatedFromUsingShadowDecl.end())
1536     return nullptr;
1537
1538   return Pos->second;
1539 }
1540
1541 void
1542 ASTContext::setInstantiatedFromUsingShadowDecl(UsingShadowDecl *Inst,
1543                                                UsingShadowDecl *Pattern) {
1544   assert(!InstantiatedFromUsingShadowDecl[Inst] && "pattern already exists");
1545   InstantiatedFromUsingShadowDecl[Inst] = Pattern;
1546 }
1547
1548 FieldDecl *ASTContext::getInstantiatedFromUnnamedFieldDecl(FieldDecl *Field) {
1549   llvm::DenseMap<FieldDecl *, FieldDecl *>::iterator Pos
1550     = InstantiatedFromUnnamedFieldDecl.find(Field);
1551   if (Pos == InstantiatedFromUnnamedFieldDecl.end())
1552     return nullptr;
1553
1554   return Pos->second;
1555 }
1556
1557 void ASTContext::setInstantiatedFromUnnamedFieldDecl(FieldDecl *Inst,
1558                                                      FieldDecl *Tmpl) {
1559   assert(!Inst->getDeclName() && "Instantiated field decl is not unnamed");
1560   assert(!Tmpl->getDeclName() && "Template field decl is not unnamed");
1561   assert(!InstantiatedFromUnnamedFieldDecl[Inst] &&
1562          "Already noted what unnamed field was instantiated from");
1563
1564   InstantiatedFromUnnamedFieldDecl[Inst] = Tmpl;
1565 }
1566
1567 ASTContext::overridden_cxx_method_iterator
1568 ASTContext::overridden_methods_begin(const CXXMethodDecl *Method) const {
1569   return overridden_methods(Method).begin();
1570 }
1571
1572 ASTContext::overridden_cxx_method_iterator
1573 ASTContext::overridden_methods_end(const CXXMethodDecl *Method) const {
1574   return overridden_methods(Method).end();
1575 }
1576
1577 unsigned
1578 ASTContext::overridden_methods_size(const CXXMethodDecl *Method) const {
1579   auto Range = overridden_methods(Method);
1580   return Range.end() - Range.begin();
1581 }
1582
1583 ASTContext::overridden_method_range
1584 ASTContext::overridden_methods(const CXXMethodDecl *Method) const {
1585   llvm::DenseMap<const CXXMethodDecl *, CXXMethodVector>::const_iterator Pos =
1586       OverriddenMethods.find(Method->getCanonicalDecl());
1587   if (Pos == OverriddenMethods.end())
1588     return overridden_method_range(nullptr, nullptr);
1589   return overridden_method_range(Pos->second.begin(), Pos->second.end());
1590 }
1591
1592 void ASTContext::addOverriddenMethod(const CXXMethodDecl *Method,
1593                                      const CXXMethodDecl *Overridden) {
1594   assert(Method->isCanonicalDecl() && Overridden->isCanonicalDecl());
1595   OverriddenMethods[Method].push_back(Overridden);
1596 }
1597
1598 void ASTContext::getOverriddenMethods(
1599                       const NamedDecl *D,
1600                       SmallVectorImpl<const NamedDecl *> &Overridden) const {
1601   assert(D);
1602
1603   if (const auto *CXXMethod = dyn_cast<CXXMethodDecl>(D)) {
1604     Overridden.append(overridden_methods_begin(CXXMethod),
1605                       overridden_methods_end(CXXMethod));
1606     return;
1607   }
1608
1609   const auto *Method = dyn_cast<ObjCMethodDecl>(D);
1610   if (!Method)
1611     return;
1612
1613   SmallVector<const ObjCMethodDecl *, 8> OverDecls;
1614   Method->getOverriddenMethods(OverDecls);
1615   Overridden.append(OverDecls.begin(), OverDecls.end());
1616 }
1617
1618 void ASTContext::addedLocalImportDecl(ImportDecl *Import) {
1619   assert(!Import->getNextLocalImport() &&
1620          "Import declaration already in the chain");
1621   assert(!Import->isFromASTFile() && "Non-local import declaration");
1622   if (!FirstLocalImport) {
1623     FirstLocalImport = Import;
1624     LastLocalImport = Import;
1625     return;
1626   }
1627
1628   LastLocalImport->setNextLocalImport(Import);
1629   LastLocalImport = Import;
1630 }
1631
1632 //===----------------------------------------------------------------------===//
1633 //                         Type Sizing and Analysis
1634 //===----------------------------------------------------------------------===//
1635
1636 /// getFloatTypeSemantics - Return the APFloat 'semantics' for the specified
1637 /// scalar floating point type.
1638 const llvm::fltSemantics &ASTContext::getFloatTypeSemantics(QualType T) const {
1639   switch (T->castAs<BuiltinType>()->getKind()) {
1640   default:
1641     llvm_unreachable("Not a floating point type!");
1642   case BuiltinType::Float16:
1643   case BuiltinType::Half:
1644     return Target->getHalfFormat();
1645   case BuiltinType::Float:      return Target->getFloatFormat();
1646   case BuiltinType::Double:     return Target->getDoubleFormat();
1647   case BuiltinType::LongDouble:
1648     if (getLangOpts().OpenMP && getLangOpts().OpenMPIsDevice)
1649       return AuxTarget->getLongDoubleFormat();
1650     return Target->getLongDoubleFormat();
1651   case BuiltinType::Float128:
1652     if (getLangOpts().OpenMP && getLangOpts().OpenMPIsDevice)
1653       return AuxTarget->getFloat128Format();
1654     return Target->getFloat128Format();
1655   }
1656 }
1657
1658 CharUnits ASTContext::getDeclAlign(const Decl *D, bool ForAlignof) const {
1659   unsigned Align = Target->getCharWidth();
1660
1661   bool UseAlignAttrOnly = false;
1662   if (unsigned AlignFromAttr = D->getMaxAlignment()) {
1663     Align = AlignFromAttr;
1664
1665     // __attribute__((aligned)) can increase or decrease alignment
1666     // *except* on a struct or struct member, where it only increases
1667     // alignment unless 'packed' is also specified.
1668     //
1669     // It is an error for alignas to decrease alignment, so we can
1670     // ignore that possibility;  Sema should diagnose it.
1671     if (isa<FieldDecl>(D)) {
1672       UseAlignAttrOnly = D->hasAttr<PackedAttr>() ||
1673         cast<FieldDecl>(D)->getParent()->hasAttr<PackedAttr>();
1674     } else {
1675       UseAlignAttrOnly = true;
1676     }
1677   }
1678   else if (isa<FieldDecl>(D))
1679       UseAlignAttrOnly =
1680         D->hasAttr<PackedAttr>() ||
1681         cast<FieldDecl>(D)->getParent()->hasAttr<PackedAttr>();
1682
1683   // If we're using the align attribute only, just ignore everything
1684   // else about the declaration and its type.
1685   if (UseAlignAttrOnly) {
1686     // do nothing
1687   } else if (const auto *VD = dyn_cast<ValueDecl>(D)) {
1688     QualType T = VD->getType();
1689     if (const auto *RT = T->getAs<ReferenceType>()) {
1690       if (ForAlignof)
1691         T = RT->getPointeeType();
1692       else
1693         T = getPointerType(RT->getPointeeType());
1694     }
1695     QualType BaseT = getBaseElementType(T);
1696     if (T->isFunctionType())
1697       Align = getTypeInfoImpl(T.getTypePtr()).Align;
1698     else if (!BaseT->isIncompleteType()) {
1699       // Adjust alignments of declarations with array type by the
1700       // large-array alignment on the target.
1701       if (const ArrayType *arrayType = getAsArrayType(T)) {
1702         unsigned MinWidth = Target->getLargeArrayMinWidth();
1703         if (!ForAlignof && MinWidth) {
1704           if (isa<VariableArrayType>(arrayType))
1705             Align = std::max(Align, Target->getLargeArrayAlign());
1706           else if (isa<ConstantArrayType>(arrayType) &&
1707                    MinWidth <= getTypeSize(cast<ConstantArrayType>(arrayType)))
1708             Align = std::max(Align, Target->getLargeArrayAlign());
1709         }
1710       }
1711       Align = std::max(Align, getPreferredTypeAlign(T.getTypePtr()));
1712       if (BaseT.getQualifiers().hasUnaligned())
1713         Align = Target->getCharWidth();
1714       if (const auto *VD = dyn_cast<VarDecl>(D)) {
1715         if (VD->hasGlobalStorage() && !ForAlignof) {
1716           uint64_t TypeSize = getTypeSize(T.getTypePtr());
1717           Align = std::max(Align, getTargetInfo().getMinGlobalAlign(TypeSize));
1718         }
1719       }
1720     }
1721
1722     // Fields can be subject to extra alignment constraints, like if
1723     // the field is packed, the struct is packed, or the struct has a
1724     // a max-field-alignment constraint (#pragma pack).  So calculate
1725     // the actual alignment of the field within the struct, and then
1726     // (as we're expected to) constrain that by the alignment of the type.
1727     if (const auto *Field = dyn_cast<FieldDecl>(VD)) {
1728       const RecordDecl *Parent = Field->getParent();
1729       // We can only produce a sensible answer if the record is valid.
1730       if (!Parent->isInvalidDecl()) {
1731         const ASTRecordLayout &Layout = getASTRecordLayout(Parent);
1732
1733         // Start with the record's overall alignment.
1734         unsigned FieldAlign = toBits(Layout.getAlignment());
1735
1736         // Use the GCD of that and the offset within the record.
1737         uint64_t Offset = Layout.getFieldOffset(Field->getFieldIndex());
1738         if (Offset > 0) {
1739           // Alignment is always a power of 2, so the GCD will be a power of 2,
1740           // which means we get to do this crazy thing instead of Euclid's.
1741           uint64_t LowBitOfOffset = Offset & (~Offset + 1);
1742           if (LowBitOfOffset < FieldAlign)
1743             FieldAlign = static_cast<unsigned>(LowBitOfOffset);
1744         }
1745
1746         Align = std::min(Align, FieldAlign);
1747       }
1748     }
1749   }
1750
1751   return toCharUnitsFromBits(Align);
1752 }
1753
1754 CharUnits ASTContext::getExnObjectAlignment() const {
1755   return toCharUnitsFromBits(Target->getExnObjectAlignment());
1756 }
1757
1758 // getTypeInfoDataSizeInChars - Return the size of a type, in
1759 // chars. If the type is a record, its data size is returned.  This is
1760 // the size of the memcpy that's performed when assigning this type
1761 // using a trivial copy/move assignment operator.
1762 std::pair<CharUnits, CharUnits>
1763 ASTContext::getTypeInfoDataSizeInChars(QualType T) const {
1764   std::pair<CharUnits, CharUnits> sizeAndAlign = getTypeInfoInChars(T);
1765
1766   // In C++, objects can sometimes be allocated into the tail padding
1767   // of a base-class subobject.  We decide whether that's possible
1768   // during class layout, so here we can just trust the layout results.
1769   if (getLangOpts().CPlusPlus) {
1770     if (const auto *RT = T->getAs<RecordType>()) {
1771       const ASTRecordLayout &layout = getASTRecordLayout(RT->getDecl());
1772       sizeAndAlign.first = layout.getDataSize();
1773     }
1774   }
1775
1776   return sizeAndAlign;
1777 }
1778
1779 /// getConstantArrayInfoInChars - Performing the computation in CharUnits
1780 /// instead of in bits prevents overflowing the uint64_t for some large arrays.
1781 std::pair<CharUnits, CharUnits>
1782 static getConstantArrayInfoInChars(const ASTContext &Context,
1783                                    const ConstantArrayType *CAT) {
1784   std::pair<CharUnits, CharUnits> EltInfo =
1785       Context.getTypeInfoInChars(CAT->getElementType());
1786   uint64_t Size = CAT->getSize().getZExtValue();
1787   assert((Size == 0 || static_cast<uint64_t>(EltInfo.first.getQuantity()) <=
1788               (uint64_t)(-1)/Size) &&
1789          "Overflow in array type char size evaluation");
1790   uint64_t Width = EltInfo.first.getQuantity() * Size;
1791   unsigned Align = EltInfo.second.getQuantity();
1792   if (!Context.getTargetInfo().getCXXABI().isMicrosoft() ||
1793       Context.getTargetInfo().getPointerWidth(0) == 64)
1794     Width = llvm::alignTo(Width, Align);
1795   return std::make_pair(CharUnits::fromQuantity(Width),
1796                         CharUnits::fromQuantity(Align));
1797 }
1798
1799 std::pair<CharUnits, CharUnits>
1800 ASTContext::getTypeInfoInChars(const Type *T) const {
1801   if (const auto *CAT = dyn_cast<ConstantArrayType>(T))
1802     return getConstantArrayInfoInChars(*this, CAT);
1803   TypeInfo Info = getTypeInfo(T);
1804   return std::make_pair(toCharUnitsFromBits(Info.Width),
1805                         toCharUnitsFromBits(Info.Align));
1806 }
1807
1808 std::pair<CharUnits, CharUnits>
1809 ASTContext::getTypeInfoInChars(QualType T) const {
1810   return getTypeInfoInChars(T.getTypePtr());
1811 }
1812
1813 bool ASTContext::isAlignmentRequired(const Type *T) const {
1814   return getTypeInfo(T).AlignIsRequired;
1815 }
1816
1817 bool ASTContext::isAlignmentRequired(QualType T) const {
1818   return isAlignmentRequired(T.getTypePtr());
1819 }
1820
1821 unsigned ASTContext::getTypeAlignIfKnown(QualType T) const {
1822   // An alignment on a typedef overrides anything else.
1823   if (const auto *TT = T->getAs<TypedefType>())
1824     if (unsigned Align = TT->getDecl()->getMaxAlignment())
1825       return Align;
1826
1827   // If we have an (array of) complete type, we're done.
1828   T = getBaseElementType(T);
1829   if (!T->isIncompleteType())
1830     return getTypeAlign(T);
1831
1832   // If we had an array type, its element type might be a typedef
1833   // type with an alignment attribute.
1834   if (const auto *TT = T->getAs<TypedefType>())
1835     if (unsigned Align = TT->getDecl()->getMaxAlignment())
1836       return Align;
1837
1838   // Otherwise, see if the declaration of the type had an attribute.
1839   if (const auto *TT = T->getAs<TagType>())
1840     return TT->getDecl()->getMaxAlignment();
1841
1842   return 0;
1843 }
1844
1845 TypeInfo ASTContext::getTypeInfo(const Type *T) const {
1846   TypeInfoMap::iterator I = MemoizedTypeInfo.find(T);
1847   if (I != MemoizedTypeInfo.end())
1848     return I->second;
1849
1850   // This call can invalidate MemoizedTypeInfo[T], so we need a second lookup.
1851   TypeInfo TI = getTypeInfoImpl(T);
1852   MemoizedTypeInfo[T] = TI;
1853   return TI;
1854 }
1855
1856 /// getTypeInfoImpl - Return the size of the specified type, in bits.  This
1857 /// method does not work on incomplete types.
1858 ///
1859 /// FIXME: Pointers into different addr spaces could have different sizes and
1860 /// alignment requirements: getPointerInfo should take an AddrSpace, this
1861 /// should take a QualType, &c.
1862 TypeInfo ASTContext::getTypeInfoImpl(const Type *T) const {
1863   uint64_t Width = 0;
1864   unsigned Align = 8;
1865   bool AlignIsRequired = false;
1866   unsigned AS = 0;
1867   switch (T->getTypeClass()) {
1868 #define TYPE(Class, Base)
1869 #define ABSTRACT_TYPE(Class, Base)
1870 #define NON_CANONICAL_TYPE(Class, Base)
1871 #define DEPENDENT_TYPE(Class, Base) case Type::Class:
1872 #define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class, Base)                       \
1873   case Type::Class:                                                            \
1874   assert(!T->isDependentType() && "should not see dependent types here");      \
1875   return getTypeInfo(cast<Class##Type>(T)->desugar().getTypePtr());
1876 #include "clang/AST/TypeNodes.inc"
1877     llvm_unreachable("Should not see dependent types");
1878
1879   case Type::FunctionNoProto:
1880   case Type::FunctionProto:
1881     // GCC extension: alignof(function) = 32 bits
1882     Width = 0;
1883     Align = 32;
1884     break;
1885
1886   case Type::IncompleteArray:
1887   case Type::VariableArray:
1888     Width = 0;
1889     Align = getTypeAlign(cast<ArrayType>(T)->getElementType());
1890     break;
1891
1892   case Type::ConstantArray: {
1893     const auto *CAT = cast<ConstantArrayType>(T);
1894
1895     TypeInfo EltInfo = getTypeInfo(CAT->getElementType());
1896     uint64_t Size = CAT->getSize().getZExtValue();
1897     assert((Size == 0 || EltInfo.Width <= (uint64_t)(-1) / Size) &&
1898            "Overflow in array type bit size evaluation");
1899     Width = EltInfo.Width * Size;
1900     Align = EltInfo.Align;
1901     if (!getTargetInfo().getCXXABI().isMicrosoft() ||
1902         getTargetInfo().getPointerWidth(0) == 64)
1903       Width = llvm::alignTo(Width, Align);
1904     break;
1905   }
1906   case Type::ExtVector:
1907   case Type::Vector: {
1908     const auto *VT = cast<VectorType>(T);
1909     TypeInfo EltInfo = getTypeInfo(VT->getElementType());
1910     Width = EltInfo.Width * VT->getNumElements();
1911     Align = Width;
1912     // If the alignment is not a power of 2, round up to the next power of 2.
1913     // This happens for non-power-of-2 length vectors.
1914     if (Align & (Align-1)) {
1915       Align = llvm::NextPowerOf2(Align);
1916       Width = llvm::alignTo(Width, Align);
1917     }
1918     // Adjust the alignment based on the target max.
1919     uint64_t TargetVectorAlign = Target->getMaxVectorAlign();
1920     if (TargetVectorAlign && TargetVectorAlign < Align)
1921       Align = TargetVectorAlign;
1922     break;
1923   }
1924
1925   case Type::Builtin:
1926     switch (cast<BuiltinType>(T)->getKind()) {
1927     default: llvm_unreachable("Unknown builtin type!");
1928     case BuiltinType::Void:
1929       // GCC extension: alignof(void) = 8 bits.
1930       Width = 0;
1931       Align = 8;
1932       break;
1933     case BuiltinType::Bool:
1934       Width = Target->getBoolWidth();
1935       Align = Target->getBoolAlign();
1936       break;
1937     case BuiltinType::Char_S:
1938     case BuiltinType::Char_U:
1939     case BuiltinType::UChar:
1940     case BuiltinType::SChar:
1941     case BuiltinType::Char8:
1942       Width = Target->getCharWidth();
1943       Align = Target->getCharAlign();
1944       break;
1945     case BuiltinType::WChar_S:
1946     case BuiltinType::WChar_U:
1947       Width = Target->getWCharWidth();
1948       Align = Target->getWCharAlign();
1949       break;
1950     case BuiltinType::Char16:
1951       Width = Target->getChar16Width();
1952       Align = Target->getChar16Align();
1953       break;
1954     case BuiltinType::Char32:
1955       Width = Target->getChar32Width();
1956       Align = Target->getChar32Align();
1957       break;
1958     case BuiltinType::UShort:
1959     case BuiltinType::Short:
1960       Width = Target->getShortWidth();
1961       Align = Target->getShortAlign();
1962       break;
1963     case BuiltinType::UInt:
1964     case BuiltinType::Int:
1965       Width = Target->getIntWidth();
1966       Align = Target->getIntAlign();
1967       break;
1968     case BuiltinType::ULong:
1969     case BuiltinType::Long:
1970       Width = Target->getLongWidth();
1971       Align = Target->getLongAlign();
1972       break;
1973     case BuiltinType::ULongLong:
1974     case BuiltinType::LongLong:
1975       Width = Target->getLongLongWidth();
1976       Align = Target->getLongLongAlign();
1977       break;
1978     case BuiltinType::Int128:
1979     case BuiltinType::UInt128:
1980       Width = 128;
1981       Align = 128; // int128_t is 128-bit aligned on all targets.
1982       break;
1983     case BuiltinType::ShortAccum:
1984     case BuiltinType::UShortAccum:
1985     case BuiltinType::SatShortAccum:
1986     case BuiltinType::SatUShortAccum:
1987       Width = Target->getShortAccumWidth();
1988       Align = Target->getShortAccumAlign();
1989       break;
1990     case BuiltinType::Accum:
1991     case BuiltinType::UAccum:
1992     case BuiltinType::SatAccum:
1993     case BuiltinType::SatUAccum:
1994       Width = Target->getAccumWidth();
1995       Align = Target->getAccumAlign();
1996       break;
1997     case BuiltinType::LongAccum:
1998     case BuiltinType::ULongAccum:
1999     case BuiltinType::SatLongAccum:
2000     case BuiltinType::SatULongAccum:
2001       Width = Target->getLongAccumWidth();
2002       Align = Target->getLongAccumAlign();
2003       break;
2004     case BuiltinType::ShortFract:
2005     case BuiltinType::UShortFract:
2006     case BuiltinType::SatShortFract:
2007     case BuiltinType::SatUShortFract:
2008       Width = Target->getShortFractWidth();
2009       Align = Target->getShortFractAlign();
2010       break;
2011     case BuiltinType::Fract:
2012     case BuiltinType::UFract:
2013     case BuiltinType::SatFract:
2014     case BuiltinType::SatUFract:
2015       Width = Target->getFractWidth();
2016       Align = Target->getFractAlign();
2017       break;
2018     case BuiltinType::LongFract:
2019     case BuiltinType::ULongFract:
2020     case BuiltinType::SatLongFract:
2021     case BuiltinType::SatULongFract:
2022       Width = Target->getLongFractWidth();
2023       Align = Target->getLongFractAlign();
2024       break;
2025     case BuiltinType::Float16:
2026     case BuiltinType::Half:
2027       if (Target->hasFloat16Type() || !getLangOpts().OpenMP ||
2028           !getLangOpts().OpenMPIsDevice) {
2029         Width = Target->getHalfWidth();
2030         Align = Target->getHalfAlign();
2031       } else {
2032         assert(getLangOpts().OpenMP && getLangOpts().OpenMPIsDevice &&
2033                "Expected OpenMP device compilation.");
2034         Width = AuxTarget->getHalfWidth();
2035         Align = AuxTarget->getHalfAlign();
2036       }
2037       break;
2038     case BuiltinType::Float:
2039       Width = Target->getFloatWidth();
2040       Align = Target->getFloatAlign();
2041       break;
2042     case BuiltinType::Double:
2043       Width = Target->getDoubleWidth();
2044       Align = Target->getDoubleAlign();
2045       break;
2046     case BuiltinType::LongDouble:
2047       if (getLangOpts().OpenMP && getLangOpts().OpenMPIsDevice &&
2048           (Target->getLongDoubleWidth() != AuxTarget->getLongDoubleWidth() ||
2049            Target->getLongDoubleAlign() != AuxTarget->getLongDoubleAlign())) {
2050         Width = AuxTarget->getLongDoubleWidth();
2051         Align = AuxTarget->getLongDoubleAlign();
2052       } else {
2053         Width = Target->getLongDoubleWidth();
2054         Align = Target->getLongDoubleAlign();
2055       }
2056       break;
2057     case BuiltinType::Float128:
2058       if (Target->hasFloat128Type() || !getLangOpts().OpenMP ||
2059           !getLangOpts().OpenMPIsDevice) {
2060         Width = Target->getFloat128Width();
2061         Align = Target->getFloat128Align();
2062       } else {
2063         assert(getLangOpts().OpenMP && getLangOpts().OpenMPIsDevice &&
2064                "Expected OpenMP device compilation.");
2065         Width = AuxTarget->getFloat128Width();
2066         Align = AuxTarget->getFloat128Align();
2067       }
2068       break;
2069     case BuiltinType::NullPtr:
2070       Width = Target->getPointerWidth(0); // C++ 3.9.1p11: sizeof(nullptr_t)
2071       Align = Target->getPointerAlign(0); //   == sizeof(void*)
2072       break;
2073     case BuiltinType::ObjCId:
2074     case BuiltinType::ObjCClass:
2075     case BuiltinType::ObjCSel:
2076       Width = Target->getPointerWidth(0);
2077       Align = Target->getPointerAlign(0);
2078       break;
2079     case BuiltinType::OCLSampler:
2080     case BuiltinType::OCLEvent:
2081     case BuiltinType::OCLClkEvent:
2082     case BuiltinType::OCLQueue:
2083     case BuiltinType::OCLReserveID:
2084 #define IMAGE_TYPE(ImgType, Id, SingletonId, Access, Suffix) \
2085     case BuiltinType::Id:
2086 #include "clang/Basic/OpenCLImageTypes.def"
2087 #define EXT_OPAQUE_TYPE(ExtType, Id, Ext) \
2088   case BuiltinType::Id:
2089 #include "clang/Basic/OpenCLExtensionTypes.def"
2090       AS = getTargetAddressSpace(
2091           Target->getOpenCLTypeAddrSpace(getOpenCLTypeKind(T)));
2092       Width = Target->getPointerWidth(AS);
2093       Align = Target->getPointerAlign(AS);
2094       break;
2095     // The SVE types are effectively target-specific.  The length of an
2096     // SVE_VECTOR_TYPE is only known at runtime, but it is always a multiple
2097     // of 128 bits.  There is one predicate bit for each vector byte, so the
2098     // length of an SVE_PREDICATE_TYPE is always a multiple of 16 bits.
2099     //
2100     // Because the length is only known at runtime, we use a dummy value
2101     // of 0 for the static length.  The alignment values are those defined
2102     // by the Procedure Call Standard for the Arm Architecture.
2103 #define SVE_VECTOR_TYPE(Name, Id, SingletonId, ElKind, ElBits, IsSigned, IsFP)\
2104     case BuiltinType::Id: \
2105       Width = 0; \
2106       Align = 128; \
2107       break;
2108 #define SVE_PREDICATE_TYPE(Name, Id, SingletonId, ElKind) \
2109     case BuiltinType::Id: \
2110       Width = 0; \
2111       Align = 16; \
2112       break;
2113 #include "clang/Basic/AArch64SVEACLETypes.def"
2114     }
2115     break;
2116   case Type::ObjCObjectPointer:
2117     Width = Target->getPointerWidth(0);
2118     Align = Target->getPointerAlign(0);
2119     break;
2120   case Type::BlockPointer:
2121     AS = getTargetAddressSpace(cast<BlockPointerType>(T)->getPointeeType());
2122     Width = Target->getPointerWidth(AS);
2123     Align = Target->getPointerAlign(AS);
2124     break;
2125   case Type::LValueReference:
2126   case Type::RValueReference:
2127     // alignof and sizeof should never enter this code path here, so we go
2128     // the pointer route.
2129     AS = getTargetAddressSpace(cast<ReferenceType>(T)->getPointeeType());
2130     Width = Target->getPointerWidth(AS);
2131     Align = Target->getPointerAlign(AS);
2132     break;
2133   case Type::Pointer:
2134     AS = getTargetAddressSpace(cast<PointerType>(T)->getPointeeType());
2135     Width = Target->getPointerWidth(AS);
2136     Align = Target->getPointerAlign(AS);
2137     break;
2138   case Type::MemberPointer: {
2139     const auto *MPT = cast<MemberPointerType>(T);
2140     CXXABI::MemberPointerInfo MPI = ABI->getMemberPointerInfo(MPT);
2141     Width = MPI.Width;
2142     Align = MPI.Align;
2143     break;
2144   }
2145   case Type::Complex: {
2146     // Complex types have the same alignment as their elements, but twice the
2147     // size.
2148     TypeInfo EltInfo = getTypeInfo(cast<ComplexType>(T)->getElementType());
2149     Width = EltInfo.Width * 2;
2150     Align = EltInfo.Align;
2151     break;
2152   }
2153   case Type::ObjCObject:
2154     return getTypeInfo(cast<ObjCObjectType>(T)->getBaseType().getTypePtr());
2155   case Type::Adjusted:
2156   case Type::Decayed:
2157     return getTypeInfo(cast<AdjustedType>(T)->getAdjustedType().getTypePtr());
2158   case Type::ObjCInterface: {
2159     const auto *ObjCI = cast<ObjCInterfaceType>(T);
2160     const ASTRecordLayout &Layout = getASTObjCInterfaceLayout(ObjCI->getDecl());
2161     Width = toBits(Layout.getSize());
2162     Align = toBits(Layout.getAlignment());
2163     break;
2164   }
2165   case Type::Record:
2166   case Type::Enum: {
2167     const auto *TT = cast<TagType>(T);
2168
2169     if (TT->getDecl()->isInvalidDecl()) {
2170       Width = 8;
2171       Align = 8;
2172       break;
2173     }
2174
2175     if (const auto *ET = dyn_cast<EnumType>(TT)) {
2176       const EnumDecl *ED = ET->getDecl();
2177       TypeInfo Info =
2178           getTypeInfo(ED->getIntegerType()->getUnqualifiedDesugaredType());
2179       if (unsigned AttrAlign = ED->getMaxAlignment()) {
2180         Info.Align = AttrAlign;
2181         Info.AlignIsRequired = true;
2182       }
2183       return Info;
2184     }
2185
2186     const auto *RT = cast<RecordType>(TT);
2187     const RecordDecl *RD = RT->getDecl();
2188     const ASTRecordLayout &Layout = getASTRecordLayout(RD);
2189     Width = toBits(Layout.getSize());
2190     Align = toBits(Layout.getAlignment());
2191     AlignIsRequired = RD->hasAttr<AlignedAttr>();
2192     break;
2193   }
2194
2195   case Type::SubstTemplateTypeParm:
2196     return getTypeInfo(cast<SubstTemplateTypeParmType>(T)->
2197                        getReplacementType().getTypePtr());
2198
2199   case Type::Auto:
2200   case Type::DeducedTemplateSpecialization: {
2201     const auto *A = cast<DeducedType>(T);
2202     assert(!A->getDeducedType().isNull() &&
2203            "cannot request the size of an undeduced or dependent auto type");
2204     return getTypeInfo(A->getDeducedType().getTypePtr());
2205   }
2206
2207   case Type::Paren:
2208     return getTypeInfo(cast<ParenType>(T)->getInnerType().getTypePtr());
2209
2210   case Type::MacroQualified:
2211     return getTypeInfo(
2212         cast<MacroQualifiedType>(T)->getUnderlyingType().getTypePtr());
2213
2214   case Type::ObjCTypeParam:
2215     return getTypeInfo(cast<ObjCTypeParamType>(T)->desugar().getTypePtr());
2216
2217   case Type::Typedef: {
2218     const TypedefNameDecl *Typedef = cast<TypedefType>(T)->getDecl();
2219     TypeInfo Info = getTypeInfo(Typedef->getUnderlyingType().getTypePtr());
2220     // If the typedef has an aligned attribute on it, it overrides any computed
2221     // alignment we have.  This violates the GCC documentation (which says that
2222     // attribute(aligned) can only round up) but matches its implementation.
2223     if (unsigned AttrAlign = Typedef->getMaxAlignment()) {
2224       Align = AttrAlign;
2225       AlignIsRequired = true;
2226     } else {
2227       Align = Info.Align;
2228       AlignIsRequired = Info.AlignIsRequired;
2229     }
2230     Width = Info.Width;
2231     break;
2232   }
2233
2234   case Type::Elaborated:
2235     return getTypeInfo(cast<ElaboratedType>(T)->getNamedType().getTypePtr());
2236
2237   case Type::Attributed:
2238     return getTypeInfo(
2239                   cast<AttributedType>(T)->getEquivalentType().getTypePtr());
2240
2241   case Type::Atomic: {
2242     // Start with the base type information.
2243     TypeInfo Info = getTypeInfo(cast<AtomicType>(T)->getValueType());
2244     Width = Info.Width;
2245     Align = Info.Align;
2246
2247     if (!Width) {
2248       // An otherwise zero-sized type should still generate an
2249       // atomic operation.
2250       Width = Target->getCharWidth();
2251       assert(Align);
2252     } else if (Width <= Target->getMaxAtomicPromoteWidth()) {
2253       // If the size of the type doesn't exceed the platform's max
2254       // atomic promotion width, make the size and alignment more
2255       // favorable to atomic operations:
2256
2257       // Round the size up to a power of 2.
2258       if (!llvm::isPowerOf2_64(Width))
2259         Width = llvm::NextPowerOf2(Width);
2260
2261       // Set the alignment equal to the size.
2262       Align = static_cast<unsigned>(Width);
2263     }
2264   }
2265   break;
2266
2267   case Type::Pipe:
2268     Width = Target->getPointerWidth(getTargetAddressSpace(LangAS::opencl_global));
2269     Align = Target->getPointerAlign(getTargetAddressSpace(LangAS::opencl_global));
2270     break;
2271   }
2272
2273   assert(llvm::isPowerOf2_32(Align) && "Alignment must be power of 2");
2274   return TypeInfo(Width, Align, AlignIsRequired);
2275 }
2276
2277 unsigned ASTContext::getTypeUnadjustedAlign(const Type *T) const {
2278   UnadjustedAlignMap::iterator I = MemoizedUnadjustedAlign.find(T);
2279   if (I != MemoizedUnadjustedAlign.end())
2280     return I->second;
2281
2282   unsigned UnadjustedAlign;
2283   if (const auto *RT = T->getAs<RecordType>()) {
2284     const RecordDecl *RD = RT->getDecl();
2285     const ASTRecordLayout &Layout = getASTRecordLayout(RD);
2286     UnadjustedAlign = toBits(Layout.getUnadjustedAlignment());
2287   } else if (const auto *ObjCI = T->getAs<ObjCInterfaceType>()) {
2288     const ASTRecordLayout &Layout = getASTObjCInterfaceLayout(ObjCI->getDecl());
2289     UnadjustedAlign = toBits(Layout.getUnadjustedAlignment());
2290   } else {
2291     UnadjustedAlign = getTypeAlign(T->getUnqualifiedDesugaredType());
2292   }
2293
2294   MemoizedUnadjustedAlign[T] = UnadjustedAlign;
2295   return UnadjustedAlign;
2296 }
2297
2298 unsigned ASTContext::getOpenMPDefaultSimdAlign(QualType T) const {
2299   unsigned SimdAlign = getTargetInfo().getSimdDefaultAlign();
2300   // Target ppc64 with QPX: simd default alignment for pointer to double is 32.
2301   if ((getTargetInfo().getTriple().getArch() == llvm::Triple::ppc64 ||
2302        getTargetInfo().getTriple().getArch() == llvm::Triple::ppc64le) &&
2303       getTargetInfo().getABI() == "elfv1-qpx" &&
2304       T->isSpecificBuiltinType(BuiltinType::Double))
2305     SimdAlign = 256;
2306   return SimdAlign;
2307 }
2308
2309 /// toCharUnitsFromBits - Convert a size in bits to a size in characters.
2310 CharUnits ASTContext::toCharUnitsFromBits(int64_t BitSize) const {
2311   return CharUnits::fromQuantity(BitSize / getCharWidth());
2312 }
2313
2314 /// toBits - Convert a size in characters to a size in characters.
2315 int64_t ASTContext::toBits(CharUnits CharSize) const {
2316   return CharSize.getQuantity() * getCharWidth();
2317 }
2318
2319 /// getTypeSizeInChars - Return the size of the specified type, in characters.
2320 /// This method does not work on incomplete types.
2321 CharUnits ASTContext::getTypeSizeInChars(QualType T) const {
2322   return getTypeInfoInChars(T).first;
2323 }
2324 CharUnits ASTContext::getTypeSizeInChars(const Type *T) const {
2325   return getTypeInfoInChars(T).first;
2326 }
2327
2328 /// getTypeAlignInChars - Return the ABI-specified alignment of a type, in
2329 /// characters. This method does not work on incomplete types.
2330 CharUnits ASTContext::getTypeAlignInChars(QualType T) const {
2331   return toCharUnitsFromBits(getTypeAlign(T));
2332 }
2333 CharUnits ASTContext::getTypeAlignInChars(const Type *T) const {
2334   return toCharUnitsFromBits(getTypeAlign(T));
2335 }
2336
2337 /// getTypeUnadjustedAlignInChars - Return the ABI-specified alignment of a
2338 /// type, in characters, before alignment adustments. This method does
2339 /// not work on incomplete types.
2340 CharUnits ASTContext::getTypeUnadjustedAlignInChars(QualType T) const {
2341   return toCharUnitsFromBits(getTypeUnadjustedAlign(T));
2342 }
2343 CharUnits ASTContext::getTypeUnadjustedAlignInChars(const Type *T) const {
2344   return toCharUnitsFromBits(getTypeUnadjustedAlign(T));
2345 }
2346
2347 /// getPreferredTypeAlign - Return the "preferred" alignment of the specified
2348 /// type for the current target in bits.  This can be different than the ABI
2349 /// alignment in cases where it is beneficial for performance to overalign
2350 /// a data type.
2351 unsigned ASTContext::getPreferredTypeAlign(const Type *T) const {
2352   TypeInfo TI = getTypeInfo(T);
2353   unsigned ABIAlign = TI.Align;
2354
2355   T = T->getBaseElementTypeUnsafe();
2356
2357   // The preferred alignment of member pointers is that of a pointer.
2358   if (T->isMemberPointerType())
2359     return getPreferredTypeAlign(getPointerDiffType().getTypePtr());
2360
2361   if (!Target->allowsLargerPreferedTypeAlignment())
2362     return ABIAlign;
2363
2364   // Double and long long should be naturally aligned if possible.
2365   if (const auto *CT = T->getAs<ComplexType>())
2366     T = CT->getElementType().getTypePtr();
2367   if (const auto *ET = T->getAs<EnumType>())
2368     T = ET->getDecl()->getIntegerType().getTypePtr();
2369   if (T->isSpecificBuiltinType(BuiltinType::Double) ||
2370       T->isSpecificBuiltinType(BuiltinType::LongLong) ||
2371       T->isSpecificBuiltinType(BuiltinType::ULongLong))
2372     // Don't increase the alignment if an alignment attribute was specified on a
2373     // typedef declaration.
2374     if (!TI.AlignIsRequired)
2375       return std::max(ABIAlign, (unsigned)getTypeSize(T));
2376
2377   return ABIAlign;
2378 }
2379
2380 /// getTargetDefaultAlignForAttributeAligned - Return the default alignment
2381 /// for __attribute__((aligned)) on this target, to be used if no alignment
2382 /// value is specified.
2383 unsigned ASTContext::getTargetDefaultAlignForAttributeAligned() const {
2384   return getTargetInfo().getDefaultAlignForAttributeAligned();
2385 }
2386
2387 /// getAlignOfGlobalVar - Return the alignment in bits that should be given
2388 /// to a global variable of the specified type.
2389 unsigned ASTContext::getAlignOfGlobalVar(QualType T) const {
2390   uint64_t TypeSize = getTypeSize(T.getTypePtr());
2391   return std::max(getTypeAlign(T), getTargetInfo().getMinGlobalAlign(TypeSize));
2392 }
2393
2394 /// getAlignOfGlobalVarInChars - Return the alignment in characters that
2395 /// should be given to a global variable of the specified type.
2396 CharUnits ASTContext::getAlignOfGlobalVarInChars(QualType T) const {
2397   return toCharUnitsFromBits(getAlignOfGlobalVar(T));
2398 }
2399
2400 CharUnits ASTContext::getOffsetOfBaseWithVBPtr(const CXXRecordDecl *RD) const {
2401   CharUnits Offset = CharUnits::Zero();
2402   const ASTRecordLayout *Layout = &getASTRecordLayout(RD);
2403   while (const CXXRecordDecl *Base = Layout->getBaseSharingVBPtr()) {
2404     Offset += Layout->getBaseClassOffset(Base);
2405     Layout = &getASTRecordLayout(Base);
2406   }
2407   return Offset;
2408 }
2409
2410 /// DeepCollectObjCIvars -
2411 /// This routine first collects all declared, but not synthesized, ivars in
2412 /// super class and then collects all ivars, including those synthesized for
2413 /// current class. This routine is used for implementation of current class
2414 /// when all ivars, declared and synthesized are known.
2415 void ASTContext::DeepCollectObjCIvars(const ObjCInterfaceDecl *OI,
2416                                       bool leafClass,
2417                             SmallVectorImpl<const ObjCIvarDecl*> &Ivars) const {
2418   if (const ObjCInterfaceDecl *SuperClass = OI->getSuperClass())
2419     DeepCollectObjCIvars(SuperClass, false, Ivars);
2420   if (!leafClass) {
2421     for (const auto *I : OI->ivars())
2422       Ivars.push_back(I);
2423   } else {
2424     auto *IDecl = const_cast<ObjCInterfaceDecl *>(OI);
2425     for (const ObjCIvarDecl *Iv = IDecl->all_declared_ivar_begin(); Iv;
2426          Iv= Iv->getNextIvar())
2427       Ivars.push_back(Iv);
2428   }
2429 }
2430
2431 /// CollectInheritedProtocols - Collect all protocols in current class and
2432 /// those inherited by it.
2433 void ASTContext::CollectInheritedProtocols(const Decl *CDecl,
2434                           llvm::SmallPtrSet<ObjCProtocolDecl*, 8> &Protocols) {
2435   if (const auto *OI = dyn_cast<ObjCInterfaceDecl>(CDecl)) {
2436     // We can use protocol_iterator here instead of
2437     // all_referenced_protocol_iterator since we are walking all categories.
2438     for (auto *Proto : OI->all_referenced_protocols()) {
2439       CollectInheritedProtocols(Proto, Protocols);
2440     }
2441
2442     // Categories of this Interface.
2443     for (const auto *Cat : OI->visible_categories())
2444       CollectInheritedProtocols(Cat, Protocols);
2445
2446     if (ObjCInterfaceDecl *SD = OI->getSuperClass())
2447       while (SD) {
2448         CollectInheritedProtocols(SD, Protocols);
2449         SD = SD->getSuperClass();
2450       }
2451   } else if (const auto *OC = dyn_cast<ObjCCategoryDecl>(CDecl)) {
2452     for (auto *Proto : OC->protocols()) {
2453       CollectInheritedProtocols(Proto, Protocols);
2454     }
2455   } else if (const auto *OP = dyn_cast<ObjCProtocolDecl>(CDecl)) {
2456     // Insert the protocol.
2457     if (!Protocols.insert(
2458           const_cast<ObjCProtocolDecl *>(OP->getCanonicalDecl())).second)
2459       return;
2460
2461     for (auto *Proto : OP->protocols())
2462       CollectInheritedProtocols(Proto, Protocols);
2463   }
2464 }
2465
2466 static bool unionHasUniqueObjectRepresentations(const ASTContext &Context,
2467                                                 const RecordDecl *RD) {
2468   assert(RD->isUnion() && "Must be union type");
2469   CharUnits UnionSize = Context.getTypeSizeInChars(RD->getTypeForDecl());
2470
2471   for (const auto *Field : RD->fields()) {
2472     if (!Context.hasUniqueObjectRepresentations(Field->getType()))
2473       return false;
2474     CharUnits FieldSize = Context.getTypeSizeInChars(Field->getType());
2475     if (FieldSize != UnionSize)
2476       return false;
2477   }
2478   return !RD->field_empty();
2479 }
2480
2481 static bool isStructEmpty(QualType Ty) {
2482   const RecordDecl *RD = Ty->castAs<RecordType>()->getDecl();
2483
2484   if (!RD->field_empty())
2485     return false;
2486
2487   if (const auto *ClassDecl = dyn_cast<CXXRecordDecl>(RD))
2488     return ClassDecl->isEmpty();
2489
2490   return true;
2491 }
2492
2493 static llvm::Optional<int64_t>
2494 structHasUniqueObjectRepresentations(const ASTContext &Context,
2495                                      const RecordDecl *RD) {
2496   assert(!RD->isUnion() && "Must be struct/class type");
2497   const auto &Layout = Context.getASTRecordLayout(RD);
2498
2499   int64_t CurOffsetInBits = 0;
2500   if (const auto *ClassDecl = dyn_cast<CXXRecordDecl>(RD)) {
2501     if (ClassDecl->isDynamicClass())
2502       return llvm::None;
2503
2504     SmallVector<std::pair<QualType, int64_t>, 4> Bases;
2505     for (const auto &Base : ClassDecl->bases()) {
2506       // Empty types can be inherited from, and non-empty types can potentially
2507       // have tail padding, so just make sure there isn't an error.
2508       if (!isStructEmpty(Base.getType())) {
2509         llvm::Optional<int64_t> Size = structHasUniqueObjectRepresentations(
2510             Context, Base.getType()->castAs<RecordType>()->getDecl());
2511         if (!Size)
2512           return llvm::None;
2513         Bases.emplace_back(Base.getType(), Size.getValue());
2514       }
2515     }
2516
2517     llvm::sort(Bases, [&](const std::pair<QualType, int64_t> &L,
2518                           const std::pair<QualType, int64_t> &R) {
2519       return Layout.getBaseClassOffset(L.first->getAsCXXRecordDecl()) <
2520              Layout.getBaseClassOffset(R.first->getAsCXXRecordDecl());
2521     });
2522
2523     for (const auto &Base : Bases) {
2524       int64_t BaseOffset = Context.toBits(
2525           Layout.getBaseClassOffset(Base.first->getAsCXXRecordDecl()));
2526       int64_t BaseSize = Base.second;
2527       if (BaseOffset != CurOffsetInBits)
2528         return llvm::None;
2529       CurOffsetInBits = BaseOffset + BaseSize;
2530     }
2531   }
2532
2533   for (const auto *Field : RD->fields()) {
2534     if (!Field->getType()->isReferenceType() &&
2535         !Context.hasUniqueObjectRepresentations(Field->getType()))
2536       return llvm::None;
2537
2538     int64_t FieldSizeInBits =
2539         Context.toBits(Context.getTypeSizeInChars(Field->getType()));
2540     if (Field->isBitField()) {
2541       int64_t BitfieldSize = Field->getBitWidthValue(Context);
2542
2543       if (BitfieldSize > FieldSizeInBits)
2544         return llvm::None;
2545       FieldSizeInBits = BitfieldSize;
2546     }
2547
2548     int64_t FieldOffsetInBits = Context.getFieldOffset(Field);
2549
2550     if (FieldOffsetInBits != CurOffsetInBits)
2551       return llvm::None;
2552
2553     CurOffsetInBits = FieldSizeInBits + FieldOffsetInBits;
2554   }
2555
2556   return CurOffsetInBits;
2557 }
2558
2559 bool ASTContext::hasUniqueObjectRepresentations(QualType Ty) const {
2560   // C++17 [meta.unary.prop]:
2561   //   The predicate condition for a template specialization
2562   //   has_unique_object_representations<T> shall be
2563   //   satisfied if and only if:
2564   //     (9.1) - T is trivially copyable, and
2565   //     (9.2) - any two objects of type T with the same value have the same
2566   //     object representation, where two objects
2567   //   of array or non-union class type are considered to have the same value
2568   //   if their respective sequences of
2569   //   direct subobjects have the same values, and two objects of union type
2570   //   are considered to have the same
2571   //   value if they have the same active member and the corresponding members
2572   //   have the same value.
2573   //   The set of scalar types for which this condition holds is
2574   //   implementation-defined. [ Note: If a type has padding
2575   //   bits, the condition does not hold; otherwise, the condition holds true
2576   //   for unsigned integral types. -- end note ]
2577   assert(!Ty.isNull() && "Null QualType sent to unique object rep check");
2578
2579   // Arrays are unique only if their element type is unique.
2580   if (Ty->isArrayType())
2581     return hasUniqueObjectRepresentations(getBaseElementType(Ty));
2582
2583   // (9.1) - T is trivially copyable...
2584   if (!Ty.isTriviallyCopyableType(*this))
2585     return false;
2586
2587   // All integrals and enums are unique.
2588   if (Ty->isIntegralOrEnumerationType())
2589     return true;
2590
2591   // All other pointers are unique.
2592   if (Ty->isPointerType())
2593     return true;
2594
2595   if (Ty->isMemberPointerType()) {
2596     const auto *MPT = Ty->getAs<MemberPointerType>();
2597     return !ABI->getMemberPointerInfo(MPT).HasPadding;
2598   }
2599
2600   if (Ty->isRecordType()) {
2601     const RecordDecl *Record = Ty->castAs<RecordType>()->getDecl();
2602
2603     if (Record->isInvalidDecl())
2604       return false;
2605
2606     if (Record->isUnion())
2607       return unionHasUniqueObjectRepresentations(*this, Record);
2608
2609     Optional<int64_t> StructSize =
2610         structHasUniqueObjectRepresentations(*this, Record);
2611
2612     return StructSize &&
2613            StructSize.getValue() == static_cast<int64_t>(getTypeSize(Ty));
2614   }
2615
2616   // FIXME: More cases to handle here (list by rsmith):
2617   // vectors (careful about, eg, vector of 3 foo)
2618   // _Complex int and friends
2619   // _Atomic T
2620   // Obj-C block pointers
2621   // Obj-C object pointers
2622   // and perhaps OpenCL's various builtin types (pipe, sampler_t, event_t,
2623   // clk_event_t, queue_t, reserve_id_t)
2624   // There're also Obj-C class types and the Obj-C selector type, but I think it
2625   // makes sense for those to return false here.
2626
2627   return false;
2628 }
2629
2630 unsigned ASTContext::CountNonClassIvars(const ObjCInterfaceDecl *OI) const {
2631   unsigned count = 0;
2632   // Count ivars declared in class extension.
2633   for (const auto *Ext : OI->known_extensions())
2634     count += Ext->ivar_size();
2635
2636   // Count ivar defined in this class's implementation.  This
2637   // includes synthesized ivars.
2638   if (ObjCImplementationDecl *ImplDecl = OI->getImplementation())
2639     count += ImplDecl->ivar_size();
2640
2641   return count;
2642 }
2643
2644 bool ASTContext::isSentinelNullExpr(const Expr *E) {
2645   if (!E)
2646     return false;
2647
2648   // nullptr_t is always treated as null.
2649   if (E->getType()->isNullPtrType()) return true;
2650
2651   if (E->getType()->isAnyPointerType() &&
2652       E->IgnoreParenCasts()->isNullPointerConstant(*this,
2653                                                 Expr::NPC_ValueDependentIsNull))
2654     return true;
2655
2656   // Unfortunately, __null has type 'int'.
2657   if (isa<GNUNullExpr>(E)) return true;
2658
2659   return false;
2660 }
2661
2662 /// Get the implementation of ObjCInterfaceDecl, or nullptr if none
2663 /// exists.
2664 ObjCImplementationDecl *ASTContext::getObjCImplementation(ObjCInterfaceDecl *D) {
2665   llvm::DenseMap<ObjCContainerDecl*, ObjCImplDecl*>::iterator
2666     I = ObjCImpls.find(D);
2667   if (I != ObjCImpls.end())
2668     return cast<ObjCImplementationDecl>(I->second);
2669   return nullptr;
2670 }
2671
2672 /// Get the implementation of ObjCCategoryDecl, or nullptr if none
2673 /// exists.
2674 ObjCCategoryImplDecl *ASTContext::getObjCImplementation(ObjCCategoryDecl *D) {
2675   llvm::DenseMap<ObjCContainerDecl*, ObjCImplDecl*>::iterator
2676     I = ObjCImpls.find(D);
2677   if (I != ObjCImpls.end())
2678     return cast<ObjCCategoryImplDecl>(I->second);
2679   return nullptr;
2680 }
2681
2682 /// Set the implementation of ObjCInterfaceDecl.
2683 void ASTContext::setObjCImplementation(ObjCInterfaceDecl *IFaceD,
2684                            ObjCImplementationDecl *ImplD) {
2685   assert(IFaceD && ImplD && "Passed null params");
2686   ObjCImpls[IFaceD] = ImplD;
2687 }
2688
2689 /// Set the implementation of ObjCCategoryDecl.
2690 void ASTContext::setObjCImplementation(ObjCCategoryDecl *CatD,
2691                            ObjCCategoryImplDecl *ImplD) {
2692   assert(CatD && ImplD && "Passed null params");
2693   ObjCImpls[CatD] = ImplD;
2694 }
2695
2696 const ObjCMethodDecl *
2697 ASTContext::getObjCMethodRedeclaration(const ObjCMethodDecl *MD) const {
2698   return ObjCMethodRedecls.lookup(MD);
2699 }
2700
2701 void ASTContext::setObjCMethodRedeclaration(const ObjCMethodDecl *MD,
2702                                             const ObjCMethodDecl *Redecl) {
2703   assert(!getObjCMethodRedeclaration(MD) && "MD already has a redeclaration");
2704   ObjCMethodRedecls[MD] = Redecl;
2705 }
2706
2707 const ObjCInterfaceDecl *ASTContext::getObjContainingInterface(
2708                                               const NamedDecl *ND) const {
2709   if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(ND->getDeclContext()))
2710     return ID;
2711   if (const auto *CD = dyn_cast<ObjCCategoryDecl>(ND->getDeclContext()))
2712     return CD->getClassInterface();
2713   if (const auto *IMD = dyn_cast<ObjCImplDecl>(ND->getDeclContext()))
2714     return IMD->getClassInterface();
2715
2716   return nullptr;
2717 }
2718
2719 /// Get the copy initialization expression of VarDecl, or nullptr if
2720 /// none exists.
2721 BlockVarCopyInit ASTContext::getBlockVarCopyInit(const VarDecl *VD) const {
2722   assert(VD && "Passed null params");
2723   assert(VD->hasAttr<BlocksAttr>() &&
2724          "getBlockVarCopyInits - not __block var");
2725   auto I = BlockVarCopyInits.find(VD);
2726   if (I != BlockVarCopyInits.end())
2727     return I->second;
2728   return {nullptr, false};
2729 }
2730
2731 /// Set the copy initialization expression of a block var decl.
2732 void ASTContext::setBlockVarCopyInit(const VarDecl*VD, Expr *CopyExpr,
2733                                      bool CanThrow) {
2734   assert(VD && CopyExpr && "Passed null params");
2735   assert(VD->hasAttr<BlocksAttr>() &&
2736          "setBlockVarCopyInits - not __block var");
2737   BlockVarCopyInits[VD].setExprAndFlag(CopyExpr, CanThrow);
2738 }
2739
2740 TypeSourceInfo *ASTContext::CreateTypeSourceInfo(QualType T,
2741                                                  unsigned DataSize) const {
2742   if (!DataSize)
2743     DataSize = TypeLoc::getFullDataSizeForType(T);
2744   else
2745     assert(DataSize == TypeLoc::getFullDataSizeForType(T) &&
2746            "incorrect data size provided to CreateTypeSourceInfo!");
2747
2748   auto *TInfo =
2749     (TypeSourceInfo*)BumpAlloc.Allocate(sizeof(TypeSourceInfo) + DataSize, 8);
2750   new (TInfo) TypeSourceInfo(T);
2751   return TInfo;
2752 }
2753
2754 TypeSourceInfo *ASTContext::getTrivialTypeSourceInfo(QualType T,
2755                                                      SourceLocation L) const {
2756   TypeSourceInfo *DI = CreateTypeSourceInfo(T);
2757   DI->getTypeLoc().initialize(const_cast<ASTContext &>(*this), L);
2758   return DI;
2759 }
2760
2761 const ASTRecordLayout &
2762 ASTContext::getASTObjCInterfaceLayout(const ObjCInterfaceDecl *D) const {
2763   return getObjCLayout(D, nullptr);
2764 }
2765
2766 const ASTRecordLayout &
2767 ASTContext::getASTObjCImplementationLayout(
2768                                         const ObjCImplementationDecl *D) const {
2769   return getObjCLayout(D->getClassInterface(), D);
2770 }
2771
2772 //===----------------------------------------------------------------------===//
2773 //                   Type creation/memoization methods
2774 //===----------------------------------------------------------------------===//
2775
2776 QualType
2777 ASTContext::getExtQualType(const Type *baseType, Qualifiers quals) const {
2778   unsigned fastQuals = quals.getFastQualifiers();
2779   quals.removeFastQualifiers();
2780
2781   // Check if we've already instantiated this type.
2782   llvm::FoldingSetNodeID ID;
2783   ExtQuals::Profile(ID, baseType, quals);
2784   void *insertPos = nullptr;
2785   if (ExtQuals *eq = ExtQualNodes.FindNodeOrInsertPos(ID, insertPos)) {
2786     assert(eq->getQualifiers() == quals);
2787     return QualType(eq, fastQuals);
2788   }
2789
2790   // If the base type is not canonical, make the appropriate canonical type.
2791   QualType canon;
2792   if (!baseType->isCanonicalUnqualified()) {
2793     SplitQualType canonSplit = baseType->getCanonicalTypeInternal().split();
2794     canonSplit.Quals.addConsistentQualifiers(quals);
2795     canon = getExtQualType(canonSplit.Ty, canonSplit.Quals);
2796
2797     // Re-find the insert position.
2798     (void) ExtQualNodes.FindNodeOrInsertPos(ID, insertPos);
2799   }
2800
2801   auto *eq = new (*this, TypeAlignment) ExtQuals(baseType, canon, quals);
2802   ExtQualNodes.InsertNode(eq, insertPos);
2803   return QualType(eq, fastQuals);
2804 }
2805
2806 QualType ASTContext::getAddrSpaceQualType(QualType T,
2807                                           LangAS AddressSpace) const {
2808   QualType CanT = getCanonicalType(T);
2809   if (CanT.getAddressSpace() == AddressSpace)
2810     return T;
2811
2812   // If we are composing extended qualifiers together, merge together
2813   // into one ExtQuals node.
2814   QualifierCollector Quals;
2815   const Type *TypeNode = Quals.strip(T);
2816
2817   // If this type already has an address space specified, it cannot get
2818   // another one.
2819   assert(!Quals.hasAddressSpace() &&
2820          "Type cannot be in multiple addr spaces!");
2821   Quals.addAddressSpace(AddressSpace);
2822
2823   return getExtQualType(TypeNode, Quals);
2824 }
2825
2826 QualType ASTContext::removeAddrSpaceQualType(QualType T) const {
2827   // If we are composing extended qualifiers together, merge together
2828   // into one ExtQuals node.
2829   QualifierCollector Quals;
2830   const Type *TypeNode = Quals.strip(T);
2831
2832   // If the qualifier doesn't have an address space just return it.
2833   if (!Quals.hasAddressSpace())
2834     return T;
2835
2836   Quals.removeAddressSpace();
2837
2838   // Removal of the address space can mean there are no longer any
2839   // non-fast qualifiers, so creating an ExtQualType isn't possible (asserts)
2840   // or required.
2841   if (Quals.hasNonFastQualifiers())
2842     return getExtQualType(TypeNode, Quals);
2843   else
2844     return QualType(TypeNode, Quals.getFastQualifiers());
2845 }
2846
2847 QualType ASTContext::getObjCGCQualType(QualType T,
2848                                        Qualifiers::GC GCAttr) const {
2849   QualType CanT = getCanonicalType(T);
2850   if (CanT.getObjCGCAttr() == GCAttr)
2851     return T;
2852
2853   if (const auto *ptr = T->getAs<PointerType>()) {
2854     QualType Pointee = ptr->getPointeeType();
2855     if (Pointee->isAnyPointerType()) {
2856       QualType ResultType = getObjCGCQualType(Pointee, GCAttr);
2857       return getPointerType(ResultType);
2858     }
2859   }
2860
2861   // If we are composing extended qualifiers together, merge together
2862   // into one ExtQuals node.
2863   QualifierCollector Quals;
2864   const Type *TypeNode = Quals.strip(T);
2865
2866   // If this type already has an ObjCGC specified, it cannot get
2867   // another one.
2868   assert(!Quals.hasObjCGCAttr() &&
2869          "Type cannot have multiple ObjCGCs!");
2870   Quals.addObjCGCAttr(GCAttr);
2871
2872   return getExtQualType(TypeNode, Quals);
2873 }
2874
2875 QualType ASTContext::removePtrSizeAddrSpace(QualType T) const {
2876   if (const PointerType *Ptr = T->getAs<PointerType>()) {
2877     QualType Pointee = Ptr->getPointeeType();
2878     if (isPtrSizeAddressSpace(Pointee.getAddressSpace())) {
2879       return getPointerType(removeAddrSpaceQualType(Pointee));
2880     }
2881   }
2882   return T;
2883 }
2884
2885 const FunctionType *ASTContext::adjustFunctionType(const FunctionType *T,
2886                                                    FunctionType::ExtInfo Info) {
2887   if (T->getExtInfo() == Info)
2888     return T;
2889
2890   QualType Result;
2891   if (const auto *FNPT = dyn_cast<FunctionNoProtoType>(T)) {
2892     Result = getFunctionNoProtoType(FNPT->getReturnType(), Info);
2893   } else {
2894     const auto *FPT = cast<FunctionProtoType>(T);
2895     FunctionProtoType::ExtProtoInfo EPI = FPT->getExtProtoInfo();
2896     EPI.ExtInfo = Info;
2897     Result = getFunctionType(FPT->getReturnType(), FPT->getParamTypes(), EPI);
2898   }
2899
2900   return cast<FunctionType>(Result.getTypePtr());
2901 }
2902
2903 void ASTContext::adjustDeducedFunctionResultType(FunctionDecl *FD,
2904                                                  QualType ResultType) {
2905   FD = FD->getMostRecentDecl();
2906   while (true) {
2907     const auto *FPT = FD->getType()->castAs<FunctionProtoType>();
2908     FunctionProtoType::ExtProtoInfo EPI = FPT->getExtProtoInfo();
2909     FD->setType(getFunctionType(ResultType, FPT->getParamTypes(), EPI));
2910     if (FunctionDecl *Next = FD->getPreviousDecl())
2911       FD = Next;
2912     else
2913       break;
2914   }
2915   if (ASTMutationListener *L = getASTMutationListener())
2916     L->DeducedReturnType(FD, ResultType);
2917 }
2918
2919 /// Get a function type and produce the equivalent function type with the
2920 /// specified exception specification. Type sugar that can be present on a
2921 /// declaration of a function with an exception specification is permitted
2922 /// and preserved. Other type sugar (for instance, typedefs) is not.
2923 QualType ASTContext::getFunctionTypeWithExceptionSpec(
2924     QualType Orig, const FunctionProtoType::ExceptionSpecInfo &ESI) {
2925   // Might have some parens.
2926   if (const auto *PT = dyn_cast<ParenType>(Orig))
2927     return getParenType(
2928         getFunctionTypeWithExceptionSpec(PT->getInnerType(), ESI));
2929
2930   // Might be wrapped in a macro qualified type.
2931   if (const auto *MQT = dyn_cast<MacroQualifiedType>(Orig))
2932     return getMacroQualifiedType(
2933         getFunctionTypeWithExceptionSpec(MQT->getUnderlyingType(), ESI),
2934         MQT->getMacroIdentifier());
2935
2936   // Might have a calling-convention attribute.
2937   if (const auto *AT = dyn_cast<AttributedType>(Orig))
2938     return getAttributedType(
2939         AT->getAttrKind(),
2940         getFunctionTypeWithExceptionSpec(AT->getModifiedType(), ESI),
2941         getFunctionTypeWithExceptionSpec(AT->getEquivalentType(), ESI));
2942
2943   // Anything else must be a function type. Rebuild it with the new exception
2944   // specification.
2945   const auto *Proto = Orig->castAs<FunctionProtoType>();
2946   return getFunctionType(
2947       Proto->getReturnType(), Proto->getParamTypes(),
2948       Proto->getExtProtoInfo().withExceptionSpec(ESI));
2949 }
2950
2951 bool ASTContext::hasSameFunctionTypeIgnoringExceptionSpec(QualType T,
2952                                                           QualType U) {
2953   return hasSameType(T, U) ||
2954          (getLangOpts().CPlusPlus17 &&
2955           hasSameType(getFunctionTypeWithExceptionSpec(T, EST_None),
2956                       getFunctionTypeWithExceptionSpec(U, EST_None)));
2957 }
2958
2959 QualType ASTContext::getFunctionTypeWithoutPtrSizes(QualType T) {
2960   if (const auto *Proto = T->getAs<FunctionProtoType>()) {
2961     QualType RetTy = removePtrSizeAddrSpace(Proto->getReturnType());
2962     SmallVector<QualType, 16> Args(Proto->param_types());
2963     for (unsigned i = 0, n = Args.size(); i != n; ++i)
2964       Args[i] = removePtrSizeAddrSpace(Args[i]);
2965     return getFunctionType(RetTy, Args, Proto->getExtProtoInfo());
2966   }
2967
2968   if (const FunctionNoProtoType *Proto = T->getAs<FunctionNoProtoType>()) {
2969     QualType RetTy = removePtrSizeAddrSpace(Proto->getReturnType());
2970     return getFunctionNoProtoType(RetTy, Proto->getExtInfo());
2971   }
2972
2973   return T;
2974 }
2975
2976 bool ASTContext::hasSameFunctionTypeIgnoringPtrSizes(QualType T, QualType U) {
2977   return hasSameType(T, U) ||
2978          hasSameType(getFunctionTypeWithoutPtrSizes(T),
2979                      getFunctionTypeWithoutPtrSizes(U));
2980 }
2981
2982 void ASTContext::adjustExceptionSpec(
2983     FunctionDecl *FD, const FunctionProtoType::ExceptionSpecInfo &ESI,
2984     bool AsWritten) {
2985   // Update the type.
2986   QualType Updated =
2987       getFunctionTypeWithExceptionSpec(FD->getType(), ESI);
2988   FD->setType(Updated);
2989
2990   if (!AsWritten)
2991     return;
2992
2993   // Update the type in the type source information too.
2994   if (TypeSourceInfo *TSInfo = FD->getTypeSourceInfo()) {
2995     // If the type and the type-as-written differ, we may need to update
2996     // the type-as-written too.
2997     if (TSInfo->getType() != FD->getType())
2998       Updated = getFunctionTypeWithExceptionSpec(TSInfo->getType(), ESI);
2999
3000     // FIXME: When we get proper type location information for exceptions,
3001     // we'll also have to rebuild the TypeSourceInfo. For now, we just patch
3002     // up the TypeSourceInfo;
3003     assert(TypeLoc::getFullDataSizeForType(Updated) ==
3004                TypeLoc::getFullDataSizeForType(TSInfo->getType()) &&
3005            "TypeLoc size mismatch from updating exception specification");
3006     TSInfo->overrideType(Updated);
3007   }
3008 }
3009
3010 /// getComplexType - Return the uniqued reference to the type for a complex
3011 /// number with the specified element type.
3012 QualType ASTContext::getComplexType(QualType T) const {
3013   // Unique pointers, to guarantee there is only one pointer of a particular
3014   // structure.
3015   llvm::FoldingSetNodeID ID;
3016   ComplexType::Profile(ID, T);
3017
3018   void *InsertPos = nullptr;
3019   if (ComplexType *CT = ComplexTypes.FindNodeOrInsertPos(ID, InsertPos))
3020     return QualType(CT, 0);
3021
3022   // If the pointee type isn't canonical, this won't be a canonical type either,
3023   // so fill in the canonical type field.
3024   QualType Canonical;
3025   if (!T.isCanonical()) {
3026     Canonical = getComplexType(getCanonicalType(T));
3027
3028     // Get the new insert position for the node we care about.
3029     ComplexType *NewIP = ComplexTypes.FindNodeOrInsertPos(ID, InsertPos);
3030     assert(!NewIP && "Shouldn't be in the map!"); (void)NewIP;
3031   }
3032   auto *New = new (*this, TypeAlignment) ComplexType(T, Canonical);
3033   Types.push_back(New);
3034   ComplexTypes.InsertNode(New, InsertPos);
3035   return QualType(New, 0);
3036 }
3037
3038 /// getPointerType - Return the uniqued reference to the type for a pointer to
3039 /// the specified type.
3040 QualType ASTContext::getPointerType(QualType T) const {
3041   // Unique pointers, to guarantee there is only one pointer of a particular
3042   // structure.
3043   llvm::FoldingSetNodeID ID;
3044   PointerType::Profile(ID, T);
3045
3046   void *InsertPos = nullptr;
3047   if (PointerType *PT = PointerTypes.FindNodeOrInsertPos(ID, InsertPos))
3048     return QualType(PT, 0);
3049
3050   // If the pointee type isn't canonical, this won't be a canonical type either,
3051   // so fill in the canonical type field.
3052   QualType Canonical;
3053   if (!T.isCanonical()) {
3054     Canonical = getPointerType(getCanonicalType(T));
3055
3056     // Get the new insert position for the node we care about.
3057     PointerType *NewIP = PointerTypes.FindNodeOrInsertPos(ID, InsertPos);
3058     assert(!NewIP && "Shouldn't be in the map!"); (void)NewIP;
3059   }
3060   auto *New = new (*this, TypeAlignment) PointerType(T, Canonical);
3061   Types.push_back(New);
3062   PointerTypes.InsertNode(New, InsertPos);
3063   return QualType(New, 0);
3064 }
3065
3066 QualType ASTContext::getAdjustedType(QualType Orig, QualType New) const {
3067   llvm::FoldingSetNodeID ID;
3068   AdjustedType::Profile(ID, Orig, New);
3069   void *InsertPos = nullptr;
3070   AdjustedType *AT = AdjustedTypes.FindNodeOrInsertPos(ID, InsertPos);
3071   if (AT)
3072     return QualType(AT, 0);
3073
3074   QualType Canonical = getCanonicalType(New);
3075
3076   // Get the new insert position for the node we care about.
3077   AT = AdjustedTypes.FindNodeOrInsertPos(ID, InsertPos);
3078   assert(!AT && "Shouldn't be in the map!");
3079
3080   AT = new (*this, TypeAlignment)
3081       AdjustedType(Type::Adjusted, Orig, New, Canonical);
3082   Types.push_back(AT);
3083   AdjustedTypes.InsertNode(AT, InsertPos);
3084   return QualType(AT, 0);
3085 }
3086
3087 QualType ASTContext::getDecayedType(QualType T) const {
3088   assert((T->isArrayType() || T->isFunctionType()) && "T does not decay");
3089
3090   QualType Decayed;
3091
3092   // C99 6.7.5.3p7:
3093   //   A declaration of a parameter as "array of type" shall be
3094   //   adjusted to "qualified pointer to type", where the type
3095   //   qualifiers (if any) are those specified within the [ and ] of
3096   //   the array type derivation.
3097   if (T->isArrayType())
3098     Decayed = getArrayDecayedType(T);
3099
3100   // C99 6.7.5.3p8:
3101   //   A declaration of a parameter as "function returning type"
3102   //   shall be adjusted to "pointer to function returning type", as
3103   //   in 6.3.2.1.
3104   if (T->isFunctionType())
3105     Decayed = getPointerType(T);
3106
3107   llvm::FoldingSetNodeID ID;
3108   AdjustedType::Profile(ID, T, Decayed);
3109   void *InsertPos = nullptr;
3110   AdjustedType *AT = AdjustedTypes.FindNodeOrInsertPos(ID, InsertPos);
3111   if (AT)
3112     return QualType(AT, 0);
3113
3114   QualType Canonical = getCanonicalType(Decayed);
3115
3116   // Get the new insert position for the node we care about.
3117   AT = AdjustedTypes.FindNodeOrInsertPos(ID, InsertPos);
3118   assert(!AT && "Shouldn't be in the map!");
3119
3120   AT = new (*this, TypeAlignment) DecayedType(T, Decayed, Canonical);
3121   Types.push_back(AT);
3122   AdjustedTypes.InsertNode(AT, InsertPos);
3123   return QualType(AT, 0);
3124 }
3125
3126 /// getBlockPointerType - Return the uniqued reference to the type for
3127 /// a pointer to the specified block.
3128 QualType ASTContext::getBlockPointerType(QualType T) const {
3129   assert(T->isFunctionType() && "block of function types only");
3130   // Unique pointers, to guarantee there is only one block of a particular
3131   // structure.
3132   llvm::FoldingSetNodeID ID;
3133   BlockPointerType::Profile(ID, T);
3134
3135   void *InsertPos = nullptr;
3136   if (BlockPointerType *PT =
3137         BlockPointerTypes.FindNodeOrInsertPos(ID, InsertPos))
3138     return QualType(PT, 0);
3139
3140   // If the block pointee type isn't canonical, this won't be a canonical
3141   // type either so fill in the canonical type field.
3142   QualType Canonical;
3143   if (!T.isCanonical()) {
3144     Canonical = getBlockPointerType(getCanonicalType(T));
3145
3146     // Get the new insert position for the node we care about.
3147     BlockPointerType *NewIP =
3148       BlockPointerTypes.FindNodeOrInsertPos(ID, InsertPos);
3149     assert(!NewIP && "Shouldn't be in the map!"); (void)NewIP;
3150   }
3151   auto *New = new (*this, TypeAlignment) BlockPointerType(T, Canonical);
3152   Types.push_back(New);
3153   BlockPointerTypes.InsertNode(New, InsertPos);
3154   return QualType(New, 0);
3155 }
3156
3157 /// getLValueReferenceType - Return the uniqued reference to the type for an
3158 /// lvalue reference to the specified type.
3159 QualType
3160 ASTContext::getLValueReferenceType(QualType T, bool SpelledAsLValue) const {
3161   assert(getCanonicalType(T) != OverloadTy &&
3162          "Unresolved overloaded function type");
3163
3164   // Unique pointers, to guarantee there is only one pointer of a particular
3165   // structure.
3166   llvm::FoldingSetNodeID ID;
3167   ReferenceType::Profile(ID, T, SpelledAsLValue);
3168
3169   void *InsertPos = nullptr;
3170   if (LValueReferenceType *RT =
3171         LValueReferenceTypes.FindNodeOrInsertPos(ID, InsertPos))
3172     return QualType(RT, 0);
3173
3174   const auto *InnerRef = T->getAs<ReferenceType>();
3175
3176   // If the referencee type isn't canonical, this won't be a canonical type
3177   // either, so fill in the canonical type field.
3178   QualType Canonical;
3179   if (!SpelledAsLValue || InnerRef || !T.isCanonical()) {
3180     QualType PointeeType = (InnerRef ? InnerRef->getPointeeType() : T);
3181     Canonical = getLValueReferenceType(getCanonicalType(PointeeType));
3182
3183     // Get the new insert position for the node we care about.
3184     LValueReferenceType *NewIP =
3185       LValueReferenceTypes.FindNodeOrInsertPos(ID, InsertPos);
3186     assert(!NewIP && "Shouldn't be in the map!"); (void)NewIP;
3187   }
3188
3189   auto *New = new (*this, TypeAlignment) LValueReferenceType(T, Canonical,
3190                                                              SpelledAsLValue);
3191   Types.push_back(New);
3192   LValueReferenceTypes.InsertNode(New, InsertPos);
3193
3194   return QualType(New, 0);
3195 }
3196
3197 /// getRValueReferenceType - Return the uniqued reference to the type for an
3198 /// rvalue reference to the specified type.
3199 QualType ASTContext::getRValueReferenceType(QualType T) const {
3200   // Unique pointers, to guarantee there is only one pointer of a particular
3201   // structure.
3202   llvm::FoldingSetNodeID ID;
3203   ReferenceType::Profile(ID, T, false);
3204
3205   void *InsertPos = nullptr;
3206   if (RValueReferenceType *RT =
3207         RValueReferenceTypes.FindNodeOrInsertPos(ID, InsertPos))
3208     return QualType(RT, 0);
3209
3210   const auto *InnerRef = T->getAs<ReferenceType>();
3211
3212   // If the referencee type isn't canonical, this won't be a canonical type
3213   // either, so fill in the canonical type field.
3214   QualType Canonical;
3215   if (InnerRef || !T.isCanonical()) {
3216     QualType PointeeType = (InnerRef ? InnerRef->getPointeeType() : T);
3217     Canonical = getRValueReferenceType(getCanonicalType(PointeeType));
3218
3219     // Get the new insert position for the node we care about.
3220     RValueReferenceType *NewIP =
3221       RValueReferenceTypes.FindNodeOrInsertPos(ID, InsertPos);
3222     assert(!NewIP && "Shouldn't be in the map!"); (void)NewIP;
3223   }
3224
3225   auto *New = new (*this, TypeAlignment) RValueReferenceType(T, Canonical);
3226   Types.push_back(New);
3227   RValueReferenceTypes.InsertNode(New, InsertPos);
3228   return QualType(New, 0);
3229 }
3230
3231 /// getMemberPointerType - Return the uniqued reference to the type for a
3232 /// member pointer to the specified type, in the specified class.
3233 QualType ASTContext::getMemberPointerType(QualType T, const Type *Cls) const {
3234   // Unique pointers, to guarantee there is only one pointer of a particular
3235   // structure.
3236   llvm::FoldingSetNodeID ID;
3237   MemberPointerType::Profile(ID, T, Cls);
3238
3239   void *InsertPos = nullptr;
3240   if (MemberPointerType *PT =
3241       MemberPointerTypes.FindNodeOrInsertPos(ID, InsertPos))
3242     return QualType(PT, 0);
3243
3244   // If the pointee or class type isn't canonical, this won't be a canonical
3245   // type either, so fill in the canonical type field.
3246   QualType Canonical;
3247   if (!T.isCanonical() || !Cls->isCanonicalUnqualified()) {
3248     Canonical = getMemberPointerType(getCanonicalType(T),getCanonicalType(Cls));
3249
3250     // Get the new insert position for the node we care about.
3251     MemberPointerType *NewIP =
3252       MemberPointerTypes.FindNodeOrInsertPos(ID, InsertPos);
3253     assert(!NewIP && "Shouldn't be in the map!"); (void)NewIP;
3254   }
3255   auto *New = new (*this, TypeAlignment) MemberPointerType(T, Cls, Canonical);
3256   Types.push_back(New);
3257   MemberPointerTypes.InsertNode(New, InsertPos);
3258   return QualType(New, 0);
3259 }
3260
3261 /// getConstantArrayType - Return the unique reference to the type for an
3262 /// array of the specified element type.
3263 QualType ASTContext::getConstantArrayType(QualType EltTy,
3264                                           const llvm::APInt &ArySizeIn,
3265                                           const Expr *SizeExpr,
3266                                           ArrayType::ArraySizeModifier ASM,
3267                                           unsigned IndexTypeQuals) const {
3268   assert((EltTy->isDependentType() ||
3269           EltTy->isIncompleteType() || EltTy->isConstantSizeType()) &&
3270          "Constant array of VLAs is illegal!");
3271
3272   // We only need the size as part of the type if it's instantiation-dependent.
3273   if (SizeExpr && !SizeExpr->isInstantiationDependent())
3274     SizeExpr = nullptr;
3275
3276   // Convert the array size into a canonical width matching the pointer size for
3277   // the target.
3278   llvm::APInt ArySize(ArySizeIn);
3279   ArySize = ArySize.zextOrTrunc(Target->getMaxPointerWidth());
3280
3281   llvm::FoldingSetNodeID ID;
3282   ConstantArrayType::Profile(ID, *this, EltTy, ArySize, SizeExpr, ASM,
3283                              IndexTypeQuals);
3284
3285   void *InsertPos = nullptr;
3286   if (ConstantArrayType *ATP =
3287       ConstantArrayTypes.FindNodeOrInsertPos(ID, InsertPos))
3288     return QualType(ATP, 0);
3289
3290   // If the element type isn't canonical or has qualifiers, or the array bound
3291   // is instantiation-dependent, this won't be a canonical type either, so fill
3292   // in the canonical type field.
3293   QualType Canon;
3294   if (!EltTy.isCanonical() || EltTy.hasLocalQualifiers() || SizeExpr) {
3295     SplitQualType canonSplit = getCanonicalType(EltTy).split();
3296     Canon = getConstantArrayType(QualType(canonSplit.Ty, 0), ArySize, nullptr,
3297                                  ASM, IndexTypeQuals);
3298     Canon = getQualifiedType(Canon, canonSplit.Quals);
3299
3300     // Get the new insert position for the node we care about.
3301     ConstantArrayType *NewIP =
3302       ConstantArrayTypes.FindNodeOrInsertPos(ID, InsertPos);
3303     assert(!NewIP && "Shouldn't be in the map!"); (void)NewIP;
3304   }
3305
3306   void *Mem = Allocate(
3307       ConstantArrayType::totalSizeToAlloc<const Expr *>(SizeExpr ? 1 : 0),
3308       TypeAlignment);
3309   auto *New = new (Mem)
3310     ConstantArrayType(EltTy, Canon, ArySize, SizeExpr, ASM, IndexTypeQuals);
3311   ConstantArrayTypes.InsertNode(New, InsertPos);
3312   Types.push_back(New);
3313   return QualType(New, 0);
3314 }
3315
3316 /// getVariableArrayDecayedType - Turns the given type, which may be
3317 /// variably-modified, into the corresponding type with all the known
3318 /// sizes replaced with [*].
3319 QualType ASTContext::getVariableArrayDecayedType(QualType type) const {
3320   // Vastly most common case.
3321   if (!type->isVariablyModifiedType()) return type;
3322
3323   QualType result;
3324
3325   SplitQualType split = type.getSplitDesugaredType();
3326   const Type *ty = split.Ty;
3327   switch (ty->getTypeClass()) {
3328 #define TYPE(Class, Base)
3329 #define ABSTRACT_TYPE(Class, Base)
3330 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
3331 #include "clang/AST/TypeNodes.inc"
3332     llvm_unreachable("didn't desugar past all non-canonical types?");
3333
3334   // These types should never be variably-modified.
3335   case Type::Builtin:
3336   case Type::Complex:
3337   case Type::Vector:
3338   case Type::DependentVector:
3339   case Type::ExtVector:
3340   case Type::DependentSizedExtVector:
3341   case Type::DependentAddressSpace:
3342   case Type::ObjCObject:
3343   case Type::ObjCInterface:
3344   case Type::ObjCObjectPointer:
3345   case Type::Record:
3346   case Type::Enum:
3347   case Type::UnresolvedUsing:
3348   case Type::TypeOfExpr:
3349   case Type::TypeOf:
3350   case Type::Decltype:
3351   case Type::UnaryTransform:
3352   case Type::DependentName:
3353   case Type::InjectedClassName:
3354   case Type::TemplateSpecialization:
3355   case Type::DependentTemplateSpecialization:
3356   case Type::TemplateTypeParm:
3357   case Type::SubstTemplateTypeParmPack:
3358   case Type::Auto:
3359   case Type::DeducedTemplateSpecialization:
3360   case Type::PackExpansion:
3361     llvm_unreachable("type should never be variably-modified");
3362
3363   // These types can be variably-modified but should never need to
3364   // further decay.
3365   case Type::FunctionNoProto:
3366   case Type::FunctionProto:
3367   case Type::BlockPointer:
3368   case Type::MemberPointer:
3369   case Type::Pipe:
3370     return type;
3371
3372   // These types can be variably-modified.  All these modifications
3373   // preserve structure except as noted by comments.
3374   // TODO: if we ever care about optimizing VLAs, there are no-op
3375   // optimizations available here.
3376   case Type::Pointer:
3377     result = getPointerType(getVariableArrayDecayedType(
3378                               cast<PointerType>(ty)->getPointeeType()));
3379     break;
3380
3381   case Type::LValueReference: {
3382     const auto *lv = cast<LValueReferenceType>(ty);
3383     result = getLValueReferenceType(
3384                  getVariableArrayDecayedType(lv->getPointeeType()),
3385                                     lv->isSpelledAsLValue());
3386     break;
3387   }
3388
3389   case Type::RValueReference: {
3390     const auto *lv = cast<RValueReferenceType>(ty);
3391     result = getRValueReferenceType(
3392                  getVariableArrayDecayedType(lv->getPointeeType()));
3393     break;
3394   }
3395
3396   case Type::Atomic: {
3397     const auto *at = cast<AtomicType>(ty);
3398     result = getAtomicType(getVariableArrayDecayedType(at->getValueType()));
3399     break;
3400   }
3401
3402   case Type::ConstantArray: {
3403     const auto *cat = cast<ConstantArrayType>(ty);
3404     result = getConstantArrayType(
3405                  getVariableArrayDecayedType(cat->getElementType()),
3406                                   cat->getSize(),
3407                                   cat->getSizeExpr(),
3408                                   cat->getSizeModifier(),
3409                                   cat->getIndexTypeCVRQualifiers());
3410     break;
3411   }
3412
3413   case Type::DependentSizedArray: {
3414     const auto *dat = cast<DependentSizedArrayType>(ty);
3415     result = getDependentSizedArrayType(
3416                  getVariableArrayDecayedType(dat->getElementType()),
3417                                         dat->getSizeExpr(),
3418                                         dat->getSizeModifier(),
3419                                         dat->getIndexTypeCVRQualifiers(),
3420                                         dat->getBracketsRange());
3421     break;
3422   }
3423
3424   // Turn incomplete types into [*] types.
3425   case Type::IncompleteArray: {
3426     const auto *iat = cast<IncompleteArrayType>(ty);
3427     result = getVariableArrayType(
3428                  getVariableArrayDecayedType(iat->getElementType()),
3429                                   /*size*/ nullptr,
3430                                   ArrayType::Normal,
3431                                   iat->getIndexTypeCVRQualifiers(),
3432                                   SourceRange());
3433     break;
3434   }
3435
3436   // Turn VLA types into [*] types.
3437   case Type::VariableArray: {
3438     const auto *vat = cast<VariableArrayType>(ty);
3439     result = getVariableArrayType(
3440                  getVariableArrayDecayedType(vat->getElementType()),
3441                                   /*size*/ nullptr,
3442                                   ArrayType::Star,
3443                                   vat->getIndexTypeCVRQualifiers(),
3444                                   vat->getBracketsRange());
3445     break;
3446   }
3447   }
3448
3449   // Apply the top-level qualifiers from the original.
3450   return getQualifiedType(result, split.Quals);
3451 }
3452
3453 /// getVariableArrayType - Returns a non-unique reference to the type for a
3454 /// variable array of the specified element type.
3455 QualType ASTContext::getVariableArrayType(QualType EltTy,
3456                                           Expr *NumElts,
3457                                           ArrayType::ArraySizeModifier ASM,
3458                                           unsigned IndexTypeQuals,
3459                                           SourceRange Brackets) const {
3460   // Since we don't unique expressions, it isn't possible to unique VLA's
3461   // that have an expression provided for their size.
3462   QualType Canon;
3463
3464   // Be sure to pull qualifiers off the element type.
3465   if (!EltTy.isCanonical() || EltTy.hasLocalQualifiers()) {
3466     SplitQualType canonSplit = getCanonicalType(EltTy).split();
3467     Canon = getVariableArrayType(QualType(canonSplit.Ty, 0), NumElts, ASM,
3468                                  IndexTypeQuals, Brackets);
3469     Canon = getQualifiedType(Canon, canonSplit.Quals);
3470   }
3471
3472   auto *New = new (*this, TypeAlignment)
3473     VariableArrayType(EltTy, Canon, NumElts, ASM, IndexTypeQuals, Brackets);
3474
3475   VariableArrayTypes.push_back(New);
3476   Types.push_back(New);
3477   return QualType(New, 0);
3478 }
3479
3480 /// getDependentSizedArrayType - Returns a non-unique reference to
3481 /// the type for a dependently-sized array of the specified element
3482 /// type.
3483 QualType ASTContext::getDependentSizedArrayType(QualType elementType,
3484                                                 Expr *numElements,
3485                                                 ArrayType::ArraySizeModifier ASM,
3486                                                 unsigned elementTypeQuals,
3487                                                 SourceRange brackets) const {
3488   assert((!numElements || numElements->isTypeDependent() ||
3489           numElements->isValueDependent()) &&
3490          "Size must be type- or value-dependent!");
3491
3492   // Dependently-sized array types that do not have a specified number
3493   // of elements will have their sizes deduced from a dependent
3494   // initializer.  We do no canonicalization here at all, which is okay
3495   // because they can't be used in most locations.
3496   if (!numElements) {
3497     auto *newType
3498       = new (*this, TypeAlignment)
3499           DependentSizedArrayType(*this, elementType, QualType(),
3500                                   numElements, ASM, elementTypeQuals,
3501                                   brackets);
3502     Types.push_back(newType);
3503     return QualType(newType, 0);
3504   }
3505
3506   // Otherwise, we actually build a new type every time, but we
3507   // also build a canonical type.
3508
3509   SplitQualType canonElementType = getCanonicalType(elementType).split();
3510
3511   void *insertPos = nullptr;
3512   llvm::FoldingSetNodeID ID;
3513   DependentSizedArrayType::Profile(ID, *this,
3514                                    QualType(canonElementType.Ty, 0),
3515                                    ASM, elementTypeQuals, numElements);
3516
3517   // Look for an existing type with these properties.
3518   DependentSizedArrayType *canonTy =
3519     DependentSizedArrayTypes.FindNodeOrInsertPos(ID, insertPos);
3520
3521   // If we don't have one, build one.
3522   if (!canonTy) {
3523     canonTy = new (*this, TypeAlignment)
3524       DependentSizedArrayType(*this, QualType(canonElementType.Ty, 0),
3525                               QualType(), numElements, ASM, elementTypeQuals,
3526                               brackets);
3527     DependentSizedArrayTypes.InsertNode(canonTy, insertPos);
3528     Types.push_back(canonTy);
3529   }
3530
3531   // Apply qualifiers from the element type to the array.
3532   QualType canon = getQualifiedType(QualType(canonTy,0),
3533                                     canonElementType.Quals);
3534
3535   // If we didn't need extra canonicalization for the element type or the size
3536   // expression, then just use that as our result.
3537   if (QualType(canonElementType.Ty, 0) == elementType &&
3538       canonTy->getSizeExpr() == numElements)
3539     return canon;
3540
3541   // Otherwise, we need to build a type which follows the spelling
3542   // of the element type.
3543   auto *sugaredType
3544     = new (*this, TypeAlignment)
3545         DependentSizedArrayType(*this, elementType, canon, numElements,
3546                                 ASM, elementTypeQuals, brackets);
3547   Types.push_back(sugaredType);
3548   return QualType(sugaredType, 0);
3549 }
3550
3551 QualType ASTContext::getIncompleteArrayType(QualType elementType,
3552                                             ArrayType::ArraySizeModifier ASM,
3553                                             unsigned elementTypeQuals) const {
3554   llvm::FoldingSetNodeID ID;
3555   IncompleteArrayType::Profile(ID, elementType, ASM, elementTypeQuals);
3556
3557   void *insertPos = nullptr;
3558   if (IncompleteArrayType *iat =
3559        IncompleteArrayTypes.FindNodeOrInsertPos(ID, insertPos))
3560     return QualType(iat, 0);
3561
3562   // If the element type isn't canonical, this won't be a canonical type
3563   // either, so fill in the canonical type field.  We also have to pull
3564   // qualifiers off the element type.
3565   QualType canon;
3566
3567   if (!elementType.isCanonical() || elementType.hasLocalQualifiers()) {
3568     SplitQualType canonSplit = getCanonicalType(elementType).split();
3569     canon = getIncompleteArrayType(QualType(canonSplit.Ty, 0),
3570                                    ASM, elementTypeQuals);
3571     canon = getQualifiedType(canon, canonSplit.Quals);
3572
3573     // Get the new insert position for the node we care about.
3574     IncompleteArrayType *existing =
3575       IncompleteArrayTypes.FindNodeOrInsertPos(ID, insertPos);
3576     assert(!existing && "Shouldn't be in the map!"); (void) existing;
3577   }
3578
3579   auto *newType = new (*this, TypeAlignment)
3580     IncompleteArrayType(elementType, canon, ASM, elementTypeQuals);
3581
3582   IncompleteArrayTypes.InsertNode(newType, insertPos);
3583   Types.push_back(newType);
3584   return QualType(newType, 0);
3585 }
3586
3587 /// getVectorType - Return the unique reference to a vector type of
3588 /// the specified element type and size. VectorType must be a built-in type.
3589 QualType ASTContext::getVectorType(QualType vecType, unsigned NumElts,
3590                                    VectorType::VectorKind VecKind) const {
3591   assert(vecType->isBuiltinType());
3592
3593   // Check if we've already instantiated a vector of this type.
3594   llvm::FoldingSetNodeID ID;
3595   VectorType::Profile(ID, vecType, NumElts, Type::Vector, VecKind);
3596
3597   void *InsertPos = nullptr;
3598   if (VectorType *VTP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos))
3599     return QualType(VTP, 0);
3600
3601   // If the element type isn't canonical, this won't be a canonical type either,
3602   // so fill in the canonical type field.
3603   QualType Canonical;
3604   if (!vecType.isCanonical()) {
3605     Canonical = getVectorType(getCanonicalType(vecType), NumElts, VecKind);
3606
3607     // Get the new insert position for the node we care about.
3608     VectorType *NewIP = VectorTypes.FindNodeOrInsertPos(ID, InsertPos);
3609     assert(!NewIP && "Shouldn't be in the map!"); (void)NewIP;
3610   }
3611   auto *New = new (*this, TypeAlignment)
3612     VectorType(vecType, NumElts, Canonical, VecKind);
3613   VectorTypes.InsertNode(New, InsertPos);
3614   Types.push_back(New);
3615   return QualType(New, 0);
3616 }
3617
3618 QualType
3619 ASTContext::getDependentVectorType(QualType VecType, Expr *SizeExpr,
3620                                    SourceLocation AttrLoc,
3621                                    VectorType::VectorKind VecKind) const {
3622   llvm::FoldingSetNodeID ID;
3623   DependentVectorType::Profile(ID, *this, getCanonicalType(VecType), SizeExpr,
3624                                VecKind);
3625   void *InsertPos = nullptr;
3626   DependentVectorType *Canon =
3627       DependentVectorTypes.FindNodeOrInsertPos(ID, InsertPos);
3628   DependentVectorType *New;
3629
3630   if (Canon) {
3631     New = new (*this, TypeAlignment) DependentVectorType(
3632         *this, VecType, QualType(Canon, 0), SizeExpr, AttrLoc, VecKind);
3633   } else {
3634     QualType CanonVecTy = getCanonicalType(VecType);
3635     if (CanonVecTy == VecType) {
3636       New = new (*this, TypeAlignment) DependentVectorType(
3637           *this, VecType, QualType(), SizeExpr, AttrLoc, VecKind);
3638
3639       DependentVectorType *CanonCheck =
3640           DependentVectorTypes.FindNodeOrInsertPos(ID, InsertPos);
3641       assert(!CanonCheck &&
3642              "Dependent-sized vector_size canonical type broken");
3643       (void)CanonCheck;
3644       DependentVectorTypes.InsertNode(New, InsertPos);
3645     } else {
3646       QualType CanonExtTy = getDependentSizedExtVectorType(CanonVecTy, SizeExpr,
3647                                                            SourceLocation());
3648       New = new (*this, TypeAlignment) DependentVectorType(