clang/lib/AST/ODRHash.cpp

   1 //===-- ODRHash.cpp - Hashing to diagnose ODR failures ----------*- C++ -*-===//
   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 /// \file
  10 /// This file implements the ODRHash class, which calculates a hash based
  11 /// on AST nodes, which is stable across different runs.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/AST/ODRHash.h"
  16
  17 #include "clang/AST/DeclVisitor.h"
  18 #include "clang/AST/NestedNameSpecifier.h"
  19 #include "clang/AST/StmtVisitor.h"
  20 #include "clang/AST/TypeVisitor.h"
  21
  22 using namespace clang;
  23
  24 void ODRHash::AddStmt(const Stmt *S) {
  25   assert(S && "Expecting non-null pointer.");
  26   S->ProcessODRHash(ID, *this);
  27 }
  28
  29 void ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
  30   assert(II && "Expecting non-null pointer.");
  31   ID.AddString(II->getName());
  32 }
  33
  34 void ODRHash::AddDeclarationName(DeclarationName Name, bool TreatAsDecl) {
  35   if (TreatAsDecl)
  36     // Matches the NamedDecl check in AddDecl
  37     AddBoolean(true);
  38
  39   AddDeclarationNameImpl(Name);
  40
  41   if (TreatAsDecl)
  42     // Matches the ClassTemplateSpecializationDecl check in AddDecl
  43     AddBoolean(false);
  44 }
  45
  46 void ODRHash::AddDeclarationNameImpl(DeclarationName Name) {
  47   // Index all DeclarationName and use index numbers to refer to them.
  48   auto Result = DeclNameMap.insert(std::make_pair(Name, DeclNameMap.size()));
  49   ID.AddInteger(Result.first->second);
  50   if (!Result.second) {
  51     // If found in map, the DeclarationName has previously been processed.
  52     return;
  53   }
  54
  55   // First time processing each DeclarationName, also process its details.
  56   AddBoolean(Name.isEmpty());
  57   if (Name.isEmpty())
  58     return;
  59
  60   auto Kind = Name.getNameKind();
  61   ID.AddInteger(Kind);
  62   switch (Kind) {
  63   case DeclarationName::Identifier:
  64     AddIdentifierInfo(Name.getAsIdentifierInfo());
  65     break;
  66   case DeclarationName::ObjCZeroArgSelector:
  67   case DeclarationName::ObjCOneArgSelector:
  68   case DeclarationName::ObjCMultiArgSelector: {
  69     Selector S = Name.getObjCSelector();
  70     AddBoolean(S.isNull());
  71     AddBoolean(S.isKeywordSelector());
  72     AddBoolean(S.isUnarySelector());
  73     unsigned NumArgs = S.getNumArgs();
  74     ID.AddInteger(NumArgs);
  75     // Compare all selector slots. For selectors with arguments it means all arg
  76     // slots. And if there are no arguments, compare the first-and-only slot.
  77     unsigned SlotsToCheck = NumArgs > 0 ? NumArgs : 1;
  78     for (unsigned i = 0; i < SlotsToCheck; ++i) {
  79       const IdentifierInfo *II = S.getIdentifierInfoForSlot(i);
  80       AddBoolean(II);
  81       if (II) {
  82         AddIdentifierInfo(II);
  83       }
  84     }
  85     break;
  86   }
  87   case DeclarationName::CXXConstructorName:
  88   case DeclarationName::CXXDestructorName:
  89     AddQualType(Name.getCXXNameType());
  90     break;
  91   case DeclarationName::CXXOperatorName:
  92     ID.AddInteger(Name.getCXXOverloadedOperator());
  93     break;
  94   case DeclarationName::CXXLiteralOperatorName:
  95     AddIdentifierInfo(Name.getCXXLiteralIdentifier());
  96     break;
  97   case DeclarationName::CXXConversionFunctionName:
  98     AddQualType(Name.getCXXNameType());
  99     break;
 100   case DeclarationName::CXXUsingDirective:
 101     break;
 102   case DeclarationName::CXXDeductionGuideName: {
 103     auto *Template = Name.getCXXDeductionGuideTemplate();
 104     AddBoolean(Template);
 105     if (Template) {
 106       AddDecl(Template);
 107     }
 108   }
 109   }
 110 }
 111
 112 void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
 113   assert(NNS && "Expecting non-null pointer.");
 114   const auto *Prefix = NNS->getPrefix();
 115   AddBoolean(Prefix);
 116   if (Prefix) {
 117     AddNestedNameSpecifier(Prefix);
 118   }
 119   auto Kind = NNS->getKind();
 120   ID.AddInteger(Kind);
 121   switch (Kind) {
 122   case NestedNameSpecifier::Identifier:
 123     AddIdentifierInfo(NNS->getAsIdentifier());
 124     break;
 125   case NestedNameSpecifier::Namespace:
 126     AddDecl(NNS->getAsNamespace());
 127     break;
 128   case NestedNameSpecifier::NamespaceAlias:
 129     AddDecl(NNS->getAsNamespaceAlias());
 130     break;
 131   case NestedNameSpecifier::TypeSpec:
 132   case NestedNameSpecifier::TypeSpecWithTemplate:
 133     AddType(NNS->getAsType());
 134     break;
 135   case NestedNameSpecifier::Global:
 136   case NestedNameSpecifier::Super:
 137     break;
 138   }
 139 }
 140
 141 void ODRHash::AddTemplateName(TemplateName Name) {
 142   auto Kind = Name.getKind();
 143   ID.AddInteger(Kind);
 144
 145   switch (Kind) {
 146   case TemplateName::Template:
 147     AddDecl(Name.getAsTemplateDecl());
 148     break;
 149   // TODO: Support these cases.
 150   case TemplateName::OverloadedTemplate:
 151   case TemplateName::AssumedTemplate:
 152   case TemplateName::QualifiedTemplate:
 153   case TemplateName::DependentTemplate:
 154   case TemplateName::SubstTemplateTemplateParm:
 155   case TemplateName::SubstTemplateTemplateParmPack:
 156   case TemplateName::UsingTemplate:
 157     break;
 158   }
 159 }
 160
 161 void ODRHash::AddTemplateArgument(TemplateArgument TA) {
 162   const auto Kind = TA.getKind();
 163   ID.AddInteger(Kind);
 164
 165   switch (Kind) {
 166     case TemplateArgument::Null:
 167       llvm_unreachable("Expected valid TemplateArgument");
 168     case TemplateArgument::Type:
 169       AddQualType(TA.getAsType());
 170       break;
 171     case TemplateArgument::Declaration:
 172       AddDecl(TA.getAsDecl());
 173       break;
 174     case TemplateArgument::NullPtr:
 175       ID.AddPointer(nullptr);
 176       break;
 177     case TemplateArgument::Integral: {
 178       // There are integrals (e.g.: _BitInt(128)) that cannot be represented as
 179       // any builtin integral type, so we use the hash of APSInt instead.
 180       TA.getAsIntegral().Profile(ID);
 181       break;
 182     }
 183     case TemplateArgument::Template:
 184     case TemplateArgument::TemplateExpansion:
 185       AddTemplateName(TA.getAsTemplateOrTemplatePattern());
 186       break;
 187     case TemplateArgument::Expression:
 188       AddStmt(TA.getAsExpr());
 189       break;
 190     case TemplateArgument::Pack:
 191       ID.AddInteger(TA.pack_size());
 192       for (auto SubTA : TA.pack_elements()) {
 193         AddTemplateArgument(SubTA);
 194       }
 195       break;
 196   }
 197 }
 198
 199 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {
 200   assert(TPL && "Expecting non-null pointer.");
 201
 202   ID.AddInteger(TPL->size());
 203   for (auto *ND : TPL->asArray()) {
 204     AddSubDecl(ND);
 205   }
 206 }
 207
 208 void ODRHash::clear() {
 209   DeclNameMap.clear();
 210   Bools.clear();
 211   ID.clear();
 212 }
 213
 214 unsigned ODRHash::CalculateHash() {
 215   // Append the bools to the end of the data segment backwards.  This allows
 216   // for the bools data to be compressed 32 times smaller compared to using
 217   // ID.AddBoolean
 218   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
 219   const unsigned size = Bools.size();
 220   const unsigned remainder = size % unsigned_bits;
 221   const unsigned loops = size / unsigned_bits;
 222   auto I = Bools.rbegin();
 223   unsigned value = 0;
 224   for (unsigned i = 0; i < remainder; ++i) {
 225     value <<= 1;
 226     value |= *I;
 227     ++I;
 228   }
 229   ID.AddInteger(value);
 230
 231   for (unsigned i = 0; i < loops; ++i) {
 232     value = 0;
 233     for (unsigned j = 0; j < unsigned_bits; ++j) {
 234       value <<= 1;
 235       value |= *I;
 236       ++I;
 237     }
 238     ID.AddInteger(value);
 239   }
 240
 241   assert(I == Bools.rend());
 242   Bools.clear();
 243   return ID.ComputeHash();
 244 }
 245
 246 namespace {
 247 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
 248 // methods process the relevant parts of the Decl.
 249 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
 250   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
 251   llvm::FoldingSetNodeID &ID;
 252   ODRHash &Hash;
 253
 254 public:
 255   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 256       : ID(ID), Hash(Hash) {}
 257
 258   void AddStmt(const Stmt *S) {
 259     Hash.AddBoolean(S);
 260     if (S) {
 261       Hash.AddStmt(S);
 262     }
 263   }
 264
 265   void AddIdentifierInfo(const IdentifierInfo *II) {
 266     Hash.AddBoolean(II);
 267     if (II) {
 268       Hash.AddIdentifierInfo(II);
 269     }
 270   }
 271
 272   void AddQualType(QualType T) {
 273     Hash.AddQualType(T);
 274   }
 275
 276   void AddDecl(const Decl *D) {
 277     Hash.AddBoolean(D);
 278     if (D) {
 279       Hash.AddDecl(D);
 280     }
 281   }
 282
 283   void AddTemplateArgument(TemplateArgument TA) {
 284     Hash.AddTemplateArgument(TA);
 285   }
 286
 287   void Visit(const Decl *D) {
 288     ID.AddInteger(D->getKind());
 289     Inherited::Visit(D);
 290   }
 291
 292   void VisitNamedDecl(const NamedDecl *D) {
 293     Hash.AddDeclarationName(D->getDeclName());
 294     Inherited::VisitNamedDecl(D);
 295   }
 296
 297   void VisitValueDecl(const ValueDecl *D) {
 298     if (auto *DD = dyn_cast<DeclaratorDecl>(D); DD && DD->getTypeSourceInfo())
 299       AddQualType(DD->getTypeSourceInfo()->getType());
 300
 301     Inherited::VisitValueDecl(D);
 302   }
 303
 304   void VisitVarDecl(const VarDecl *D) {
 305     Hash.AddBoolean(D->isStaticLocal());
 306     Hash.AddBoolean(D->isConstexpr());
 307     const bool HasInit = D->hasInit();
 308     Hash.AddBoolean(HasInit);
 309     if (HasInit) {
 310       AddStmt(D->getInit());
 311     }
 312     Inherited::VisitVarDecl(D);
 313   }
 314
 315   void VisitParmVarDecl(const ParmVarDecl *D) {
 316     // TODO: Handle default arguments.
 317     Inherited::VisitParmVarDecl(D);
 318   }
 319
 320   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
 321     ID.AddInteger(D->getAccess());
 322     Inherited::VisitAccessSpecDecl(D);
 323   }
 324
 325   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
 326     AddStmt(D->getAssertExpr());
 327     AddStmt(D->getMessage());
 328
 329     Inherited::VisitStaticAssertDecl(D);
 330   }
 331
 332   void VisitFieldDecl(const FieldDecl *D) {
 333     const bool IsBitfield = D->isBitField();
 334     Hash.AddBoolean(IsBitfield);
 335
 336     if (IsBitfield) {
 337       AddStmt(D->getBitWidth());
 338     }
 339
 340     Hash.AddBoolean(D->isMutable());
 341     AddStmt(D->getInClassInitializer());
 342
 343     Inherited::VisitFieldDecl(D);
 344   }
 345
 346   void VisitObjCIvarDecl(const ObjCIvarDecl *D) {
 347     ID.AddInteger(D->getCanonicalAccessControl());
 348     Inherited::VisitObjCIvarDecl(D);
 349   }
 350
 351   void VisitObjCPropertyDecl(const ObjCPropertyDecl *D) {
 352     ID.AddInteger(D->getPropertyAttributes());
 353     ID.AddInteger(D->getPropertyImplementation());
 354     AddQualType(D->getTypeSourceInfo()->getType());
 355     AddDecl(D);
 356
 357     Inherited::VisitObjCPropertyDecl(D);
 358   }
 359
 360   void VisitFunctionDecl(const FunctionDecl *D) {
 361     // Handled by the ODRHash for FunctionDecl
 362     ID.AddInteger(D->getODRHash());
 363
 364     Inherited::VisitFunctionDecl(D);
 365   }
 366
 367   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
 368     // Handled by the ODRHash for FunctionDecl
 369
 370     Inherited::VisitCXXMethodDecl(D);
 371   }
 372
 373   void VisitObjCMethodDecl(const ObjCMethodDecl *Method) {
 374     ID.AddInteger(Method->getDeclKind());
 375     Hash.AddBoolean(Method->isInstanceMethod()); // false if class method
 376     Hash.AddBoolean(Method->isVariadic());
 377     Hash.AddBoolean(Method->isSynthesizedAccessorStub());
 378     Hash.AddBoolean(Method->isDefined());
 379     Hash.AddBoolean(Method->isDirectMethod());
 380     Hash.AddBoolean(Method->isThisDeclarationADesignatedInitializer());
 381     Hash.AddBoolean(Method->hasSkippedBody());
 382
 383     ID.AddInteger(llvm::to_underlying(Method->getImplementationControl()));
 384     ID.AddInteger(Method->getMethodFamily());
 385     ImplicitParamDecl *Cmd = Method->getCmdDecl();
 386     Hash.AddBoolean(Cmd);
 387     if (Cmd)
 388       ID.AddInteger(Cmd->getParameterKind());
 389
 390     ImplicitParamDecl *Self = Method->getSelfDecl();
 391     Hash.AddBoolean(Self);
 392     if (Self)
 393       ID.AddInteger(Self->getParameterKind());
 394
 395     AddDecl(Method);
 396
 397     if (Method->getReturnTypeSourceInfo())
 398       AddQualType(Method->getReturnTypeSourceInfo()->getType());
 399
 400     ID.AddInteger(Method->param_size());
 401     for (auto Param : Method->parameters())
 402       Hash.AddSubDecl(Param);
 403
 404     if (Method->hasBody()) {
 405       const bool IsDefinition = Method->isThisDeclarationADefinition();
 406       Hash.AddBoolean(IsDefinition);
 407       if (IsDefinition) {
 408         Stmt *Body = Method->getBody();
 409         Hash.AddBoolean(Body);
 410         if (Body)
 411           AddStmt(Body);
 412
 413         // Filter out sub-Decls which will not be processed in order to get an
 414         // accurate count of Decl's.
 415         llvm::SmallVector<const Decl *, 16> Decls;
 416         for (Decl *SubDecl : Method->decls())
 417           if (ODRHash::isSubDeclToBeProcessed(SubDecl, Method))
 418             Decls.push_back(SubDecl);
 419
 420         ID.AddInteger(Decls.size());
 421         for (auto SubDecl : Decls)
 422           Hash.AddSubDecl(SubDecl);
 423       }
 424     } else {
 425       Hash.AddBoolean(false);
 426     }
 427
 428     Inherited::VisitObjCMethodDecl(Method);
 429   }
 430
 431   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
 432     AddQualType(D->getUnderlyingType());
 433
 434     Inherited::VisitTypedefNameDecl(D);
 435   }
 436
 437   void VisitTypedefDecl(const TypedefDecl *D) {
 438     Inherited::VisitTypedefDecl(D);
 439   }
 440
 441   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
 442     Inherited::VisitTypeAliasDecl(D);
 443   }
 444
 445   void VisitFriendDecl(const FriendDecl *D) {
 446     TypeSourceInfo *TSI = D->getFriendType();
 447     Hash.AddBoolean(TSI);
 448     if (TSI) {
 449       AddQualType(TSI->getType());
 450     } else {
 451       AddDecl(D->getFriendDecl());
 452     }
 453   }
 454
 455   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
 456     // Only care about default arguments as part of the definition.
 457     const bool hasDefaultArgument =
 458         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
 459     Hash.AddBoolean(hasDefaultArgument);
 460     if (hasDefaultArgument) {
 461       AddTemplateArgument(D->getDefaultArgument());
 462     }
 463     Hash.AddBoolean(D->isParameterPack());
 464
 465     const TypeConstraint *TC = D->getTypeConstraint();
 466     Hash.AddBoolean(TC != nullptr);
 467     if (TC)
 468       AddStmt(TC->getImmediatelyDeclaredConstraint());
 469
 470     Inherited::VisitTemplateTypeParmDecl(D);
 471   }
 472
 473   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D) {
 474     // Only care about default arguments as part of the definition.
 475     const bool hasDefaultArgument =
 476         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
 477     Hash.AddBoolean(hasDefaultArgument);
 478     if (hasDefaultArgument) {
 479       AddStmt(D->getDefaultArgument());
 480     }
 481     Hash.AddBoolean(D->isParameterPack());
 482
 483     Inherited::VisitNonTypeTemplateParmDecl(D);
 484   }
 485
 486   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D) {
 487     // Only care about default arguments as part of the definition.
 488     const bool hasDefaultArgument =
 489         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
 490     Hash.AddBoolean(hasDefaultArgument);
 491     if (hasDefaultArgument) {
 492       AddTemplateArgument(D->getDefaultArgument().getArgument());
 493     }
 494     Hash.AddBoolean(D->isParameterPack());
 495
 496     Inherited::VisitTemplateTemplateParmDecl(D);
 497   }
 498
 499   void VisitTemplateDecl(const TemplateDecl *D) {
 500     Hash.AddTemplateParameterList(D->getTemplateParameters());
 501
 502     Inherited::VisitTemplateDecl(D);
 503   }
 504
 505   void VisitRedeclarableTemplateDecl(const RedeclarableTemplateDecl *D) {
 506     Hash.AddBoolean(D->isMemberSpecialization());
 507     Inherited::VisitRedeclarableTemplateDecl(D);
 508   }
 509
 510   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
 511     AddDecl(D->getTemplatedDecl());
 512     ID.AddInteger(D->getTemplatedDecl()->getODRHash());
 513     Inherited::VisitFunctionTemplateDecl(D);
 514   }
 515
 516   void VisitEnumConstantDecl(const EnumConstantDecl *D) {
 517     AddStmt(D->getInitExpr());
 518     Inherited::VisitEnumConstantDecl(D);
 519   }
 520 };
 521 } // namespace
 522
 523 // Only allow a small portion of Decl's to be processed.  Remove this once
 524 // all Decl's can be handled.
 525 bool ODRHash::isSubDeclToBeProcessed(const Decl *D, const DeclContext *Parent) {
 526   if (D->isImplicit()) return false;
 527   if (D->getDeclContext() != Parent) return false;
 528
 529   switch (D->getKind()) {
 530     default:
 531       return false;
 532     case Decl::AccessSpec:
 533     case Decl::CXXConstructor:
 534     case Decl::CXXDestructor:
 535     case Decl::CXXMethod:
 536     case Decl::EnumConstant: // Only found in EnumDecl's.
 537     case Decl::Field:
 538     case Decl::Friend:
 539     case Decl::FunctionTemplate:
 540     case Decl::StaticAssert:
 541     case Decl::TypeAlias:
 542     case Decl::Typedef:
 543     case Decl::Var:
 544     case Decl::ObjCMethod:
 545     case Decl::ObjCIvar:
 546     case Decl::ObjCProperty:
 547       return true;
 548   }
 549 }
 550
 551 void ODRHash::AddSubDecl(const Decl *D) {
 552   assert(D && "Expecting non-null pointer.");
 553
 554   ODRDeclVisitor(ID, *this).Visit(D);
 555 }
 556
 557 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
 558   assert(Record && Record->hasDefinition() &&
 559          "Expected non-null record to be a definition.");
 560
 561   const DeclContext *DC = Record;
 562   while (DC) {
 563     if (isa<ClassTemplateSpecializationDecl>(DC)) {
 564       return;
 565     }
 566     DC = DC->getParent();
 567   }
 568
 569   AddDecl(Record);
 570
 571   // Filter out sub-Decls which will not be processed in order to get an
 572   // accurate count of Decl's.
 573   llvm::SmallVector<const Decl *, 16> Decls;
 574   for (Decl *SubDecl : Record->decls()) {
 575     if (isSubDeclToBeProcessed(SubDecl, Record)) {
 576       Decls.push_back(SubDecl);
 577       if (auto *Function = dyn_cast<FunctionDecl>(SubDecl)) {
 578         // Compute/Preload ODRHash into FunctionDecl.
 579         Function->getODRHash();
 580       }
 581     }
 582   }
 583
 584   ID.AddInteger(Decls.size());
 585   for (auto SubDecl : Decls) {
 586     AddSubDecl(SubDecl);
 587   }
 588
 589   const ClassTemplateDecl *TD = Record->getDescribedClassTemplate();
 590   AddBoolean(TD);
 591   if (TD) {
 592     AddTemplateParameterList(TD->getTemplateParameters());
 593   }
 594
 595   ID.AddInteger(Record->getNumBases());
 596   auto Bases = Record->bases();
 597   for (const auto &Base : Bases) {
 598     AddQualType(Base.getTypeSourceInfo()->getType());
 599     ID.AddInteger(Base.isVirtual());
 600     ID.AddInteger(Base.getAccessSpecifierAsWritten());
 601   }
 602 }
 603
 604 void ODRHash::AddRecordDecl(const RecordDecl *Record) {
 605   assert(!isa<CXXRecordDecl>(Record) &&
 606          "For CXXRecordDecl should call AddCXXRecordDecl.");
 607   AddDecl(Record);
 608
 609   // Filter out sub-Decls which will not be processed in order to get an
 610   // accurate count of Decl's.
 611   llvm::SmallVector<const Decl *, 16> Decls;
 612   for (Decl *SubDecl : Record->decls()) {
 613     if (isSubDeclToBeProcessed(SubDecl, Record))
 614       Decls.push_back(SubDecl);
 615   }
 616
 617   ID.AddInteger(Decls.size());
 618   for (const Decl *SubDecl : Decls)
 619     AddSubDecl(SubDecl);
 620 }
 621
 622 void ODRHash::AddObjCInterfaceDecl(const ObjCInterfaceDecl *IF) {
 623   AddDecl(IF);
 624
 625   auto *SuperClass = IF->getSuperClass();
 626   AddBoolean(SuperClass);
 627   if (SuperClass)
 628     ID.AddInteger(SuperClass->getODRHash());
 629
 630   // Hash referenced protocols.
 631   ID.AddInteger(IF->getReferencedProtocols().size());
 632   for (const ObjCProtocolDecl *RefP : IF->protocols()) {
 633     // Hash the name only as a referenced protocol can be a forward declaration.
 634     AddDeclarationName(RefP->getDeclName());
 635   }
 636
 637   // Filter out sub-Decls which will not be processed in order to get an
 638   // accurate count of Decl's.
 639   llvm::SmallVector<const Decl *, 16> Decls;
 640   for (Decl *SubDecl : IF->decls())
 641     if (isSubDeclToBeProcessed(SubDecl, IF))
 642       Decls.push_back(SubDecl);
 643
 644   ID.AddInteger(Decls.size());
 645   for (auto *SubDecl : Decls)
 646     AddSubDecl(SubDecl);
 647 }
 648
 649 void ODRHash::AddFunctionDecl(const FunctionDecl *Function,
 650                               bool SkipBody) {
 651   assert(Function && "Expecting non-null pointer.");
 652
 653   // Skip functions that are specializations or in specialization context.
 654   const DeclContext *DC = Function;
 655   while (DC) {
 656     if (isa<ClassTemplateSpecializationDecl>(DC)) return;
 657     if (auto *F = dyn_cast<FunctionDecl>(DC)) {
 658       if (F->isFunctionTemplateSpecialization()) {
 659         if (!isa<CXXMethodDecl>(DC)) return;
 660         if (DC->getLexicalParent()->isFileContext()) return;
 661         // Skip class scope explicit function template specializations,
 662         // as they have not yet been instantiated.
 663         if (F->getDependentSpecializationInfo())
 664           return;
 665         // Inline method specializations are the only supported
 666         // specialization for now.
 667       }
 668     }
 669     DC = DC->getParent();
 670   }
 671
 672   ID.AddInteger(Function->getDeclKind());
 673
 674   const auto *SpecializationArgs = Function->getTemplateSpecializationArgs();
 675   AddBoolean(SpecializationArgs);
 676   if (SpecializationArgs) {
 677     ID.AddInteger(SpecializationArgs->size());
 678     for (const TemplateArgument &TA : SpecializationArgs->asArray()) {
 679       AddTemplateArgument(TA);
 680     }
 681   }
 682
 683   if (const auto *Method = dyn_cast<CXXMethodDecl>(Function)) {
 684     AddBoolean(Method->isConst());
 685     AddBoolean(Method->isVolatile());
 686   }
 687
 688   ID.AddInteger(Function->getStorageClass());
 689   AddBoolean(Function->isInlineSpecified());
 690   AddBoolean(Function->isVirtualAsWritten());
 691   AddBoolean(Function->isPure());
 692   AddBoolean(Function->isDeletedAsWritten());
 693   AddBoolean(Function->isExplicitlyDefaulted());
 694
 695   AddDecl(Function);
 696
 697   AddQualType(Function->getReturnType());
 698
 699   ID.AddInteger(Function->param_size());
 700   for (auto *Param : Function->parameters())
 701     AddSubDecl(Param);
 702
 703   if (SkipBody) {
 704     AddBoolean(false);
 705     return;
 706   }
 707
 708   const bool HasBody = Function->isThisDeclarationADefinition() &&
 709                        !Function->isDefaulted() && !Function->isDeleted() &&
 710                        !Function->isLateTemplateParsed();
 711   AddBoolean(HasBody);
 712   if (!HasBody) {
 713     return;
 714   }
 715
 716   auto *Body = Function->getBody();
 717   AddBoolean(Body);
 718   if (Body)
 719     AddStmt(Body);
 720
 721   // Filter out sub-Decls which will not be processed in order to get an
 722   // accurate count of Decl's.
 723   llvm::SmallVector<const Decl *, 16> Decls;
 724   for (Decl *SubDecl : Function->decls()) {
 725     if (isSubDeclToBeProcessed(SubDecl, Function)) {
 726       Decls.push_back(SubDecl);
 727     }
 728   }
 729
 730   ID.AddInteger(Decls.size());
 731   for (auto SubDecl : Decls) {
 732     AddSubDecl(SubDecl);
 733   }
 734 }
 735
 736 void ODRHash::AddEnumDecl(const EnumDecl *Enum) {
 737   assert(Enum);
 738   AddDeclarationName(Enum->getDeclName());
 739
 740   AddBoolean(Enum->isScoped());
 741   if (Enum->isScoped())
 742     AddBoolean(Enum->isScopedUsingClassTag());
 743
 744   if (Enum->getIntegerTypeSourceInfo())
 745     AddQualType(Enum->getIntegerType());
 746
 747   // Filter out sub-Decls which will not be processed in order to get an
 748   // accurate count of Decl's.
 749   llvm::SmallVector<const Decl *, 16> Decls;
 750   for (Decl *SubDecl : Enum->decls()) {
 751     if (isSubDeclToBeProcessed(SubDecl, Enum)) {
 752       assert(isa<EnumConstantDecl>(SubDecl) && "Unexpected Decl");
 753       Decls.push_back(SubDecl);
 754     }
 755   }
 756
 757   ID.AddInteger(Decls.size());
 758   for (auto SubDecl : Decls) {
 759     AddSubDecl(SubDecl);
 760   }
 761
 762 }
 763
 764 void ODRHash::AddObjCProtocolDecl(const ObjCProtocolDecl *P) {
 765   AddDecl(P);
 766
 767   // Hash referenced protocols.
 768   ID.AddInteger(P->getReferencedProtocols().size());
 769   for (const ObjCProtocolDecl *RefP : P->protocols()) {
 770     // Hash the name only as a referenced protocol can be a forward declaration.
 771     AddDeclarationName(RefP->getDeclName());
 772   }
 773
 774   // Filter out sub-Decls which will not be processed in order to get an
 775   // accurate count of Decl's.
 776   llvm::SmallVector<const Decl *, 16> Decls;
 777   for (Decl *SubDecl : P->decls()) {
 778     if (isSubDeclToBeProcessed(SubDecl, P)) {
 779       Decls.push_back(SubDecl);
 780     }
 781   }
 782
 783   ID.AddInteger(Decls.size());
 784   for (auto *SubDecl : Decls) {
 785     AddSubDecl(SubDecl);
 786   }
 787 }
 788
 789 void ODRHash::AddDecl(const Decl *D) {
 790   assert(D && "Expecting non-null pointer.");
 791   D = D->getCanonicalDecl();
 792
 793   const NamedDecl *ND = dyn_cast<NamedDecl>(D);
 794   AddBoolean(ND);
 795   if (!ND) {
 796     ID.AddInteger(D->getKind());
 797     return;
 798   }
 799
 800   AddDeclarationName(ND->getDeclName());
 801
 802   const auto *Specialization =
 803             dyn_cast<ClassTemplateSpecializationDecl>(D);
 804   AddBoolean(Specialization);
 805   if (Specialization) {
 806     const TemplateArgumentList &List = Specialization->getTemplateArgs();
 807     ID.AddInteger(List.size());
 808     for (const TemplateArgument &TA : List.asArray())
 809       AddTemplateArgument(TA);
 810   }
 811 }
 812
 813 namespace {
 814 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
 815 // methods process the relevant parts of the Type.
 816 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
 817   typedef TypeVisitor<ODRTypeVisitor> Inherited;
 818   llvm::FoldingSetNodeID &ID;
 819   ODRHash &Hash;
 820
 821 public:
 822   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 823       : ID(ID), Hash(Hash) {}
 824
 825   void AddStmt(Stmt *S) {
 826     Hash.AddBoolean(S);
 827     if (S) {
 828       Hash.AddStmt(S);
 829     }
 830   }
 831
 832   void AddDecl(const Decl *D) {
 833     Hash.AddBoolean(D);
 834     if (D) {
 835       Hash.AddDecl(D);
 836     }
 837   }
 838
 839   void AddQualType(QualType T) {
 840     Hash.AddQualType(T);
 841   }
 842
 843   void AddType(const Type *T) {
 844     Hash.AddBoolean(T);
 845     if (T) {
 846       Hash.AddType(T);
 847     }
 848   }
 849
 850   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
 851     Hash.AddBoolean(NNS);
 852     if (NNS) {
 853       Hash.AddNestedNameSpecifier(NNS);
 854     }
 855   }
 856
 857   void AddIdentifierInfo(const IdentifierInfo *II) {
 858     Hash.AddBoolean(II);
 859     if (II) {
 860       Hash.AddIdentifierInfo(II);
 861     }
 862   }
 863
 864   void VisitQualifiers(Qualifiers Quals) {
 865     ID.AddInteger(Quals.getAsOpaqueValue());
 866   }
 867
 868   // Return the RecordType if the typedef only strips away a keyword.
 869   // Otherwise, return the original type.
 870   static const Type *RemoveTypedef(const Type *T) {
 871     const auto *TypedefT = dyn_cast<TypedefType>(T);
 872     if (!TypedefT) {
 873       return T;
 874     }
 875
 876     const TypedefNameDecl *D = TypedefT->getDecl();
 877     QualType UnderlyingType = D->getUnderlyingType();
 878
 879     if (UnderlyingType.hasLocalQualifiers()) {
 880       return T;
 881     }
 882
 883     const auto *ElaboratedT = dyn_cast<ElaboratedType>(UnderlyingType);
 884     if (!ElaboratedT) {
 885       return T;
 886     }
 887
 888     if (ElaboratedT->getQualifier() != nullptr) {
 889       return T;
 890     }
 891
 892     QualType NamedType = ElaboratedT->getNamedType();
 893     if (NamedType.hasLocalQualifiers()) {
 894       return T;
 895     }
 896
 897     const auto *RecordT = dyn_cast<RecordType>(NamedType);
 898     if (!RecordT) {
 899       return T;
 900     }
 901
 902     const IdentifierInfo *TypedefII = TypedefT->getDecl()->getIdentifier();
 903     const IdentifierInfo *RecordII = RecordT->getDecl()->getIdentifier();
 904     if (!TypedefII || !RecordII ||
 905         TypedefII->getName() != RecordII->getName()) {
 906       return T;
 907     }
 908
 909     return RecordT;
 910   }
 911
 912   void Visit(const Type *T) {
 913     T = RemoveTypedef(T);
 914     ID.AddInteger(T->getTypeClass());
 915     Inherited::Visit(T);
 916   }
 917
 918   void VisitType(const Type *T) {}
 919
 920   void VisitAdjustedType(const AdjustedType *T) {
 921     AddQualType(T->getOriginalType());
 922
 923     VisitType(T);
 924   }
 925
 926   void VisitDecayedType(const DecayedType *T) {
 927     // getDecayedType and getPointeeType are derived from getAdjustedType
 928     // and don't need to be separately processed.
 929     VisitAdjustedType(T);
 930   }
 931
 932   void VisitArrayType(const ArrayType *T) {
 933     AddQualType(T->getElementType());
 934     ID.AddInteger(llvm::to_underlying(T->getSizeModifier()));
 935     VisitQualifiers(T->getIndexTypeQualifiers());
 936     VisitType(T);
 937   }
 938   void VisitConstantArrayType(const ConstantArrayType *T) {
 939     T->getSize().Profile(ID);
 940     VisitArrayType(T);
 941   }
 942
 943   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
 944     AddStmt(T->getSizeExpr());
 945     VisitArrayType(T);
 946   }
 947
 948   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
 949     VisitArrayType(T);
 950   }
 951
 952   void VisitVariableArrayType(const VariableArrayType *T) {
 953     AddStmt(T->getSizeExpr());
 954     VisitArrayType(T);
 955   }
 956
 957   void VisitAttributedType(const AttributedType *T) {
 958     ID.AddInteger(T->getAttrKind());
 959     AddQualType(T->getModifiedType());
 960
 961     VisitType(T);
 962   }
 963
 964   void VisitBlockPointerType(const BlockPointerType *T) {
 965     AddQualType(T->getPointeeType());
 966     VisitType(T);
 967   }
 968
 969   void VisitBuiltinType(const BuiltinType *T) {
 970     ID.AddInteger(T->getKind());
 971     VisitType(T);
 972   }
 973
 974   void VisitComplexType(const ComplexType *T) {
 975     AddQualType(T->getElementType());
 976     VisitType(T);
 977   }
 978
 979   void VisitDecltypeType(const DecltypeType *T) {
 980     AddStmt(T->getUnderlyingExpr());
 981     VisitType(T);
 982   }
 983
 984   void VisitDependentDecltypeType(const DependentDecltypeType *T) {
 985     VisitDecltypeType(T);
 986   }
 987
 988   void VisitDeducedType(const DeducedType *T) {
 989     AddQualType(T->getDeducedType());
 990     VisitType(T);
 991   }
 992
 993   void VisitAutoType(const AutoType *T) {
 994     ID.AddInteger((unsigned)T->getKeyword());
 995     ID.AddInteger(T->isConstrained());
 996     if (T->isConstrained()) {
 997       AddDecl(T->getTypeConstraintConcept());
 998       ID.AddInteger(T->getTypeConstraintArguments().size());
 999       for (const auto &TA : T->getTypeConstraintArguments())
1000         Hash.AddTemplateArgument(TA);
1001     }
1002     VisitDeducedType(T);
1003   }
1004
1005   void VisitDeducedTemplateSpecializationType(
1006       const DeducedTemplateSpecializationType *T) {
1007     Hash.AddTemplateName(T->getTemplateName());
1008     VisitDeducedType(T);
1009   }
1010
1011   void VisitDependentAddressSpaceType(const DependentAddressSpaceType *T) {
1012     AddQualType(T->getPointeeType());
1013     AddStmt(T->getAddrSpaceExpr());
1014     VisitType(T);
1015   }
1016
1017   void VisitDependentSizedExtVectorType(const DependentSizedExtVectorType *T) {
1018     AddQualType(T->getElementType());
1019     AddStmt(T->getSizeExpr());
1020     VisitType(T);
1021   }
1022
1023   void VisitFunctionType(const FunctionType *T) {
1024     AddQualType(T->getReturnType());
1025     T->getExtInfo().Profile(ID);
1026     Hash.AddBoolean(T->isConst());
1027     Hash.AddBoolean(T->isVolatile());
1028     Hash.AddBoolean(T->isRestrict());
1029     VisitType(T);
1030   }
1031
1032   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
1033     VisitFunctionType(T);
1034   }
1035
1036   void VisitFunctionProtoType(const FunctionProtoType *T) {
1037     ID.AddInteger(T->getNumParams());
1038     for (auto ParamType : T->getParamTypes())
1039       AddQualType(ParamType);
1040
1041     VisitFunctionType(T);
1042   }
1043
1044   void VisitInjectedClassNameType(const InjectedClassNameType *T) {
1045     AddDecl(T->getDecl());
1046     VisitType(T);
1047   }
1048
1049   void VisitMemberPointerType(const MemberPointerType *T) {
1050     AddQualType(T->getPointeeType());
1051     AddType(T->getClass());
1052     VisitType(T);
1053   }
1054
1055   void VisitObjCObjectPointerType(const ObjCObjectPointerType *T) {
1056     AddQualType(T->getPointeeType());
1057     VisitType(T);
1058   }
1059
1060   void VisitObjCObjectType(const ObjCObjectType *T) {
1061     AddDecl(T->getInterface());
1062
1063     auto TypeArgs = T->getTypeArgsAsWritten();
1064     ID.AddInteger(TypeArgs.size());
1065     for (auto Arg : TypeArgs) {
1066       AddQualType(Arg);
1067     }
1068
1069     auto Protocols = T->getProtocols();
1070     ID.AddInteger(Protocols.size());
1071     for (auto *Protocol : Protocols) {
1072       AddDecl(Protocol);
1073     }
1074
1075     Hash.AddBoolean(T->isKindOfType());
1076
1077     VisitType(T);
1078   }
1079
1080   void VisitObjCInterfaceType(const ObjCInterfaceType *T) {
1081     // This type is handled by the parent type ObjCObjectType.
1082     VisitObjCObjectType(T);
1083   }
1084
1085   void VisitObjCTypeParamType(const ObjCTypeParamType *T) {
1086     AddDecl(T->getDecl());
1087     auto Protocols = T->getProtocols();
1088     ID.AddInteger(Protocols.size());
1089     for (auto *Protocol : Protocols) {
1090       AddDecl(Protocol);
1091     }
1092
1093     VisitType(T);
1094   }
1095
1096   void VisitPackExpansionType(const PackExpansionType *T) {
1097     AddQualType(T->getPattern());
1098     VisitType(T);
1099   }
1100
1101   void VisitParenType(const ParenType *T) {
1102     AddQualType(T->getInnerType());
1103     VisitType(T);
1104   }
1105
1106   void VisitPipeType(const PipeType *T) {
1107     AddQualType(T->getElementType());
1108     Hash.AddBoolean(T->isReadOnly());
1109     VisitType(T);
1110   }
1111
1112   void VisitPointerType(const PointerType *T) {
1113     AddQualType(T->getPointeeType());
1114     VisitType(T);
1115   }
1116
1117   void VisitReferenceType(const ReferenceType *T) {
1118     AddQualType(T->getPointeeTypeAsWritten());
1119     VisitType(T);
1120   }
1121
1122   void VisitLValueReferenceType(const LValueReferenceType *T) {
1123     VisitReferenceType(T);
1124   }
1125
1126   void VisitRValueReferenceType(const RValueReferenceType *T) {
1127     VisitReferenceType(T);
1128   }
1129
1130   void
1131   VisitSubstTemplateTypeParmPackType(const SubstTemplateTypeParmPackType *T) {
1132     AddDecl(T->getAssociatedDecl());
1133     Hash.AddTemplateArgument(T->getArgumentPack());
1134     VisitType(T);
1135   }
1136
1137   void VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T) {
1138     AddDecl(T->getAssociatedDecl());
1139     AddQualType(T->getReplacementType());
1140     VisitType(T);
1141   }
1142
1143   void VisitTagType(const TagType *T) {
1144     AddDecl(T->getDecl());
1145     VisitType(T);
1146   }
1147
1148   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
1149   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
1150
1151   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
1152     ID.AddInteger(T->template_arguments().size());
1153     for (const auto &TA : T->template_arguments()) {
1154       Hash.AddTemplateArgument(TA);
1155     }
1156     Hash.AddTemplateName(T->getTemplateName());
1157     VisitType(T);
1158   }
1159
1160   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
1161     ID.AddInteger(T->getDepth());
1162     ID.AddInteger(T->getIndex());
1163     Hash.AddBoolean(T->isParameterPack());
1164     AddDecl(T->getDecl());
1165   }
1166
1167   void VisitTypedefType(const TypedefType *T) {
1168     AddDecl(T->getDecl());
1169     VisitType(T);
1170   }
1171
1172   void VisitTypeOfExprType(const TypeOfExprType *T) {
1173     AddStmt(T->getUnderlyingExpr());
1174     Hash.AddBoolean(T->isSugared());
1175
1176     VisitType(T);
1177   }
1178   void VisitTypeOfType(const TypeOfType *T) {
1179     AddQualType(T->getUnmodifiedType());
1180     VisitType(T);
1181   }
1182
1183   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
1184     ID.AddInteger(llvm::to_underlying(T->getKeyword()));
1185     VisitType(T);
1186   };
1187
1188   void VisitDependentNameType(const DependentNameType *T) {
1189     AddNestedNameSpecifier(T->getQualifier());
1190     AddIdentifierInfo(T->getIdentifier());
1191     VisitTypeWithKeyword(T);
1192   }
1193
1194   void VisitDependentTemplateSpecializationType(
1195       const DependentTemplateSpecializationType *T) {
1196     AddIdentifierInfo(T->getIdentifier());
1197     AddNestedNameSpecifier(T->getQualifier());
1198     ID.AddInteger(T->template_arguments().size());
1199     for (const auto &TA : T->template_arguments()) {
1200       Hash.AddTemplateArgument(TA);
1201     }
1202     VisitTypeWithKeyword(T);
1203   }
1204
1205   void VisitElaboratedType(const ElaboratedType *T) {
1206     AddNestedNameSpecifier(T->getQualifier());
1207     AddQualType(T->getNamedType());
1208     VisitTypeWithKeyword(T);
1209   }
1210
1211   void VisitUnaryTransformType(const UnaryTransformType *T) {
1212     AddQualType(T->getUnderlyingType());
1213     AddQualType(T->getBaseType());
1214     VisitType(T);
1215   }
1216
1217   void VisitUnresolvedUsingType(const UnresolvedUsingType *T) {
1218     AddDecl(T->getDecl());
1219     VisitType(T);
1220   }
1221
1222   void VisitVectorType(const VectorType *T) {
1223     AddQualType(T->getElementType());
1224     ID.AddInteger(T->getNumElements());
1225     ID.AddInteger(llvm::to_underlying(T->getVectorKind()));
1226     VisitType(T);
1227   }
1228
1229   void VisitExtVectorType(const ExtVectorType * T) {
1230     VisitVectorType(T);
1231   }
1232 };
1233 } // namespace
1234
1235 void ODRHash::AddType(const Type *T) {
1236   assert(T && "Expecting non-null pointer.");
1237   ODRTypeVisitor(ID, *this).Visit(T);
1238 }
1239
1240 void ODRHash::AddQualType(QualType T) {
1241   AddBoolean(T.isNull());
1242   if (T.isNull())
1243     return;
1244   SplitQualType split = T.split();
1245   ID.AddInteger(split.Quals.getAsOpaqueValue());
1246   AddType(split.Ty);
1247 }
1248
1249 void ODRHash::AddBoolean(bool Value) {
1250   Bools.push_back(Value);
1251 }