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