contrib/llvm/tools/clang/lib/AST/ODRHash.cpp

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