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) {
  36   AddBoolean(Name.isEmpty());
  37   if (Name.isEmpty())
  38     return;
  39
  40   auto Kind = Name.getNameKind();
  41   ID.AddInteger(Kind);
  42   switch (Kind) {
  43   case DeclarationName::Identifier:
  44     AddIdentifierInfo(Name.getAsIdentifierInfo());
  45     break;
  46   case DeclarationName::ObjCZeroArgSelector:
  47   case DeclarationName::ObjCOneArgSelector:
  48   case DeclarationName::ObjCMultiArgSelector: {
  49     Selector S = Name.getObjCSelector();
  50     AddBoolean(S.isNull());
  51     AddBoolean(S.isKeywordSelector());
  52     AddBoolean(S.isUnarySelector());
  53     unsigned NumArgs = S.getNumArgs();
  54     for (unsigned i = 0; i < NumArgs; ++i) {
  55       AddIdentifierInfo(S.getIdentifierInfoForSlot(i));
  56     }
  57     break;
  58   }
  59   case DeclarationName::CXXConstructorName:
  60   case DeclarationName::CXXDestructorName:
  61     AddQualType(Name.getCXXNameType());
  62     break;
  63   case DeclarationName::CXXOperatorName:
  64     ID.AddInteger(Name.getCXXOverloadedOperator());
  65     break;
  66   case DeclarationName::CXXLiteralOperatorName:
  67     AddIdentifierInfo(Name.getCXXLiteralIdentifier());
  68     break;
  69   case DeclarationName::CXXConversionFunctionName:
  70     AddQualType(Name.getCXXNameType());
  71     break;
  72   case DeclarationName::CXXUsingDirective:
  73     break;
  74   case DeclarationName::CXXDeductionGuideName: {
  75     auto *Template = Name.getCXXDeductionGuideTemplate();
  76     AddBoolean(Template);
  77     if (Template) {
  78       AddDecl(Template);
  79     }
  80   }
  81   }
  82 }
  83
  84 void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
  85   // Unlike the other pointer handling functions, allow null pointers here.
  86   if (!NNS) {
  87     AddBoolean(false);
  88     return;
  89   }
  90
  91   // Skip inlined namespaces.
  92   auto Kind = NNS->getKind();
  93   if (Kind == NestedNameSpecifier::Namespace) {
  94     if (NNS->getAsNamespace()->isInline()) {
  95       return AddNestedNameSpecifier(NNS->getPrefix());
  96     }
  97   }
  98
  99   AddBoolean(true);
 100
 101   // Process prefix
 102   AddNestedNameSpecifier(NNS->getPrefix());
 103
 104   ID.AddInteger(Kind);
 105   switch (Kind) {
 106   case NestedNameSpecifier::Identifier:
 107     AddIdentifierInfo(NNS->getAsIdentifier());
 108     break;
 109   case NestedNameSpecifier::Namespace:
 110     AddDecl(NNS->getAsNamespace());
 111     break;
 112   case NestedNameSpecifier::NamespaceAlias:
 113     AddDecl(NNS->getAsNamespaceAlias());
 114     break;
 115   case NestedNameSpecifier::TypeSpec:
 116   case NestedNameSpecifier::TypeSpecWithTemplate:
 117     AddType(NNS->getAsType());
 118     break;
 119   case NestedNameSpecifier::Global:
 120   case NestedNameSpecifier::Super:
 121     break;
 122   }
 123 }
 124
 125 void ODRHash::AddTemplateName(TemplateName Name) {
 126   auto Kind = Name.getKind();
 127   ID.AddInteger(Kind);
 128
 129   switch (Kind) {
 130   case TemplateName::Template:
 131     AddDecl(Name.getAsTemplateDecl());
 132     break;
 133   // TODO: Support these cases.
 134   case TemplateName::OverloadedTemplate:
 135   case TemplateName::QualifiedTemplate:
 136   case TemplateName::DependentTemplate:
 137   case TemplateName::SubstTemplateTemplateParm:
 138   case TemplateName::SubstTemplateTemplateParmPack:
 139     break;
 140   }
 141 }
 142
 143 void ODRHash::AddTemplateArgument(TemplateArgument TA) {
 144   const auto Kind = TA.getKind();
 145   ID.AddInteger(Kind);
 146
 147   switch (Kind) {
 148     case TemplateArgument::Null:
 149     case TemplateArgument::Type:
 150     case TemplateArgument::Declaration:
 151     case TemplateArgument::NullPtr:
 152     case TemplateArgument::Integral:
 153       break;
 154     case TemplateArgument::Template:
 155     case TemplateArgument::TemplateExpansion:
 156       AddTemplateName(TA.getAsTemplateOrTemplatePattern());
 157       break;
 158     case TemplateArgument::Expression:
 159       AddStmt(TA.getAsExpr());
 160       break;
 161     case TemplateArgument::Pack:
 162       ID.AddInteger(TA.pack_size());
 163       for (auto SubTA : TA.pack_elements()) {
 164         AddTemplateArgument(SubTA);
 165       }
 166       break;
 167   }
 168 }
 169
 170 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {}
 171
 172 void ODRHash::clear() {
 173   DeclMap.clear();
 174   TypeMap.clear();
 175   Bools.clear();
 176   ID.clear();
 177 }
 178
 179 unsigned ODRHash::CalculateHash() {
 180   // Append the bools to the end of the data segment backwards.  This allows
 181   // for the bools data to be compressed 32 times smaller compared to using
 182   // ID.AddBoolean
 183   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
 184   const unsigned size = Bools.size();
 185   const unsigned remainder = size % unsigned_bits;
 186   const unsigned loops = size / unsigned_bits;
 187   auto I = Bools.rbegin();
 188   unsigned value = 0;
 189   for (unsigned i = 0; i < remainder; ++i) {
 190     value <<= 1;
 191     value |= *I;
 192     ++I;
 193   }
 194   ID.AddInteger(value);
 195
 196   for (unsigned i = 0; i < loops; ++i) {
 197     value = 0;
 198     for (unsigned j = 0; j < unsigned_bits; ++j) {
 199       value <<= 1;
 200       value |= *I;
 201       ++I;
 202     }
 203     ID.AddInteger(value);
 204   }
 205
 206   assert(I == Bools.rend());
 207   Bools.clear();
 208   return ID.ComputeHash();
 209 }
 210
 211 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
 212 // methods process the relevant parts of the Decl.
 213 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
 214   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
 215   llvm::FoldingSetNodeID &ID;
 216   ODRHash &Hash;
 217
 218 public:
 219   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 220       : ID(ID), Hash(Hash) {}
 221
 222   void AddStmt(const Stmt *S) {
 223     Hash.AddBoolean(S);
 224     if (S) {
 225       Hash.AddStmt(S);
 226     }
 227   }
 228
 229   void AddIdentifierInfo(const IdentifierInfo *II) {
 230     Hash.AddBoolean(II);
 231     if (II) {
 232       Hash.AddIdentifierInfo(II);
 233     }
 234   }
 235
 236   void AddQualType(QualType T) {
 237     Hash.AddQualType(T);
 238   }
 239
 240   void Visit(const Decl *D) {
 241     ID.AddInteger(D->getKind());
 242     Inherited::Visit(D);
 243   }
 244
 245   void VisitNamedDecl(const NamedDecl *D) {
 246     Hash.AddDeclarationName(D->getDeclName());
 247     Inherited::VisitNamedDecl(D);
 248   }
 249
 250   void VisitValueDecl(const ValueDecl *D) {
 251     AddQualType(D->getType());
 252     Inherited::VisitValueDecl(D);
 253   }
 254
 255   void VisitVarDecl(const VarDecl *D) {
 256     Hash.AddBoolean(D->isStaticLocal());
 257     Hash.AddBoolean(D->isConstexpr());
 258     const bool HasInit = D->hasInit();
 259     Hash.AddBoolean(HasInit);
 260     if (HasInit) {
 261       AddStmt(D->getInit());
 262     }
 263     Inherited::VisitVarDecl(D);
 264   }
 265
 266   void VisitParmVarDecl(const ParmVarDecl *D) {
 267     // TODO: Handle default arguments.
 268     Inherited::VisitParmVarDecl(D);
 269   }
 270
 271   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
 272     ID.AddInteger(D->getAccess());
 273     Inherited::VisitAccessSpecDecl(D);
 274   }
 275
 276   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
 277     AddStmt(D->getAssertExpr());
 278     AddStmt(D->getMessage());
 279
 280     Inherited::VisitStaticAssertDecl(D);
 281   }
 282
 283   void VisitFieldDecl(const FieldDecl *D) {
 284     const bool IsBitfield = D->isBitField();
 285     Hash.AddBoolean(IsBitfield);
 286
 287     if (IsBitfield) {
 288       AddStmt(D->getBitWidth());
 289     }
 290
 291     Hash.AddBoolean(D->isMutable());
 292     AddStmt(D->getInClassInitializer());
 293
 294     Inherited::VisitFieldDecl(D);
 295   }
 296
 297   void VisitFunctionDecl(const FunctionDecl *D) {
 298     ID.AddInteger(D->getStorageClass());
 299     Hash.AddBoolean(D->isInlineSpecified());
 300     Hash.AddBoolean(D->isVirtualAsWritten());
 301     Hash.AddBoolean(D->isPure());
 302     Hash.AddBoolean(D->isDeletedAsWritten());
 303
 304     ID.AddInteger(D->param_size());
 305
 306     for (auto *Param : D->parameters()) {
 307       Hash.AddSubDecl(Param);
 308     }
 309
 310     Inherited::VisitFunctionDecl(D);
 311   }
 312
 313   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
 314     Hash.AddBoolean(D->isConst());
 315     Hash.AddBoolean(D->isVolatile());
 316
 317     Inherited::VisitCXXMethodDecl(D);
 318   }
 319
 320   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
 321     AddQualType(D->getUnderlyingType());
 322
 323     Inherited::VisitTypedefNameDecl(D);
 324   }
 325
 326   void VisitTypedefDecl(const TypedefDecl *D) {
 327     Inherited::VisitTypedefDecl(D);
 328   }
 329
 330   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
 331     Inherited::VisitTypeAliasDecl(D);
 332   }
 333 };
 334
 335 // Only allow a small portion of Decl's to be processed.  Remove this once
 336 // all Decl's can be handled.
 337 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
 338   if (D->isImplicit()) return false;
 339   if (D->getDeclContext() != Parent) return false;
 340
 341   switch (D->getKind()) {
 342     default:
 343       return false;
 344     case Decl::AccessSpec:
 345     case Decl::CXXMethod:
 346     case Decl::Field:
 347     case Decl::StaticAssert:
 348     case Decl::TypeAlias:
 349     case Decl::Typedef:
 350     case Decl::Var:
 351       return true;
 352   }
 353 }
 354
 355 void ODRHash::AddSubDecl(const Decl *D) {
 356   assert(D && "Expecting non-null pointer.");
 357   AddDecl(D);
 358
 359   ODRDeclVisitor(ID, *this).Visit(D);
 360 }
 361
 362 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
 363   assert(Record && Record->hasDefinition() &&
 364          "Expected non-null record to be a definition.");
 365
 366   if (isa<ClassTemplateSpecializationDecl>(Record)) {
 367     return;
 368   }
 369
 370   AddDecl(Record);
 371
 372   // Filter out sub-Decls which will not be processed in order to get an
 373   // accurate count of Decl's.
 374   llvm::SmallVector<const Decl *, 16> Decls;
 375   for (const Decl *SubDecl : Record->decls()) {
 376     if (isWhitelistedDecl(SubDecl, Record)) {
 377       Decls.push_back(SubDecl);
 378     }
 379   }
 380
 381   ID.AddInteger(Decls.size());
 382   for (auto SubDecl : Decls) {
 383     AddSubDecl(SubDecl);
 384   }
 385 }
 386
 387 void ODRHash::AddDecl(const Decl *D) {
 388   assert(D && "Expecting non-null pointer.");
 389   auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
 390   ID.AddInteger(Result.first->second);
 391   // On first encounter of a Decl pointer, process it.  Every time afterwards,
 392   // only the index value is needed.
 393   if (!Result.second) {
 394     return;
 395   }
 396
 397   ID.AddInteger(D->getKind());
 398
 399   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
 400     AddDeclarationName(ND->getDeclName());
 401   }
 402 }
 403
 404 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
 405 // methods process the relevant parts of the Type.
 406 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
 407   typedef TypeVisitor<ODRTypeVisitor> Inherited;
 408   llvm::FoldingSetNodeID &ID;
 409   ODRHash &Hash;
 410
 411 public:
 412   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 413       : ID(ID), Hash(Hash) {}
 414
 415   void AddStmt(Stmt *S) {
 416     Hash.AddBoolean(S);
 417     if (S) {
 418       Hash.AddStmt(S);
 419     }
 420   }
 421
 422   void AddDecl(Decl *D) {
 423     Hash.AddBoolean(D);
 424     if (D) {
 425       Hash.AddDecl(D);
 426     }
 427   }
 428
 429   void AddQualType(QualType T) {
 430     Hash.AddQualType(T);
 431   }
 432
 433   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
 434     Hash.AddNestedNameSpecifier(NNS);
 435   }
 436
 437   void AddIdentifierInfo(const IdentifierInfo *II) {
 438     Hash.AddBoolean(II);
 439     if (II) {
 440       Hash.AddIdentifierInfo(II);
 441     }
 442   }
 443
 444   void VisitQualifiers(Qualifiers Quals) {
 445     ID.AddInteger(Quals.getAsOpaqueValue());
 446   }
 447
 448   void Visit(const Type *T) {
 449     ID.AddInteger(T->getTypeClass());
 450     Inherited::Visit(T);
 451   }
 452
 453   void VisitType(const Type *T) {}
 454
 455   void VisitAdjustedType(const AdjustedType *T) {
 456     AddQualType(T->getOriginalType());
 457     AddQualType(T->getAdjustedType());
 458     VisitType(T);
 459   }
 460
 461   void VisitDecayedType(const DecayedType *T) {
 462     AddQualType(T->getDecayedType());
 463     AddQualType(T->getPointeeType());
 464     VisitAdjustedType(T);
 465   }
 466
 467   void VisitArrayType(const ArrayType *T) {
 468     AddQualType(T->getElementType());
 469     ID.AddInteger(T->getSizeModifier());
 470     VisitQualifiers(T->getIndexTypeQualifiers());
 471     VisitType(T);
 472   }
 473   void VisitConstantArrayType(const ConstantArrayType *T) {
 474     T->getSize().Profile(ID);
 475     VisitArrayType(T);
 476   }
 477
 478   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
 479     AddStmt(T->getSizeExpr());
 480     VisitArrayType(T);
 481   }
 482
 483   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
 484     VisitArrayType(T);
 485   }
 486
 487   void VisitVariableArrayType(const VariableArrayType *T) {
 488     AddStmt(T->getSizeExpr());
 489     VisitArrayType(T);
 490   }
 491
 492   void VisitBuiltinType(const BuiltinType *T) {
 493     ID.AddInteger(T->getKind());
 494     VisitType(T);
 495   }
 496
 497   void VisitFunctionType(const FunctionType *T) {
 498     AddQualType(T->getReturnType());
 499     T->getExtInfo().Profile(ID);
 500     Hash.AddBoolean(T->isConst());
 501     Hash.AddBoolean(T->isVolatile());
 502     Hash.AddBoolean(T->isRestrict());
 503     VisitType(T);
 504   }
 505
 506   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
 507     VisitFunctionType(T);
 508   }
 509
 510   void VisitFunctionProtoType(const FunctionProtoType *T) {
 511     ID.AddInteger(T->getNumParams());
 512     for (auto ParamType : T->getParamTypes())
 513       AddQualType(ParamType);
 514
 515     VisitFunctionType(T);
 516   }
 517
 518   void VisitTypedefType(const TypedefType *T) {
 519     AddDecl(T->getDecl());
 520     AddQualType(T->getDecl()->getUnderlyingType().getCanonicalType());
 521     VisitType(T);
 522   }
 523
 524   void VisitTagType(const TagType *T) {
 525     AddDecl(T->getDecl());
 526     VisitType(T);
 527   }
 528
 529   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
 530   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
 531
 532   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
 533     ID.AddInteger(T->getKeyword());
 534     VisitType(T);
 535   };
 536
 537   void VisitDependentNameType(const DependentNameType *T) {
 538     AddNestedNameSpecifier(T->getQualifier());
 539     AddIdentifierInfo(T->getIdentifier());
 540     VisitTypeWithKeyword(T);
 541   }
 542
 543   void VisitDependentTemplateSpecializationType(
 544       const DependentTemplateSpecializationType *T) {
 545     AddIdentifierInfo(T->getIdentifier());
 546     AddNestedNameSpecifier(T->getQualifier());
 547     ID.AddInteger(T->getNumArgs());
 548     for (const auto &TA : T->template_arguments()) {
 549       Hash.AddTemplateArgument(TA);
 550     }
 551     VisitTypeWithKeyword(T);
 552   }
 553
 554   void VisitElaboratedType(const ElaboratedType *T) {
 555     AddNestedNameSpecifier(T->getQualifier());
 556     AddQualType(T->getNamedType());
 557     VisitTypeWithKeyword(T);
 558   }
 559
 560   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
 561     ID.AddInteger(T->getNumArgs());
 562     for (const auto &TA : T->template_arguments()) {
 563       Hash.AddTemplateArgument(TA);
 564     }
 565     Hash.AddTemplateName(T->getTemplateName());
 566     VisitType(T);
 567   }
 568
 569   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
 570     ID.AddInteger(T->getDepth());
 571     ID.AddInteger(T->getIndex());
 572     Hash.AddBoolean(T->isParameterPack());
 573     AddDecl(T->getDecl());
 574   }
 575 };
 576
 577 void ODRHash::AddType(const Type *T) {
 578   assert(T && "Expecting non-null pointer.");
 579   auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
 580   ID.AddInteger(Result.first->second);
 581   // On first encounter of a Type pointer, process it.  Every time afterwards,
 582   // only the index value is needed.
 583   if (!Result.second) {
 584     return;
 585   }
 586
 587   ODRTypeVisitor(ID, *this).Visit(T);
 588 }
 589
 590 void ODRHash::AddQualType(QualType T) {
 591   AddBoolean(T.isNull());
 592   if (T.isNull())
 593     return;
 594   SplitQualType split = T.split();
 595   ID.AddInteger(split.Quals.getAsOpaqueValue());
 596   AddType(split.Ty);
 597 }
 598
 599 void ODRHash::AddBoolean(bool Value) {
 600   Bools.push_back(Value);
 601 }