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 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {}
 145
 146 void ODRHash::clear() {
 147   DeclMap.clear();
 148   TypeMap.clear();
 149   Bools.clear();
 150   ID.clear();
 151 }
 152
 153 unsigned ODRHash::CalculateHash() {
 154   // Append the bools to the end of the data segment backwards.  This allows
 155   // for the bools data to be compressed 32 times smaller compared to using
 156   // ID.AddBoolean
 157   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
 158   const unsigned size = Bools.size();
 159   const unsigned remainder = size % unsigned_bits;
 160   const unsigned loops = size / unsigned_bits;
 161   auto I = Bools.rbegin();
 162   unsigned value = 0;
 163   for (unsigned i = 0; i < remainder; ++i) {
 164     value <<= 1;
 165     value |= *I;
 166     ++I;
 167   }
 168   ID.AddInteger(value);
 169
 170   for (unsigned i = 0; i < loops; ++i) {
 171     value = 0;
 172     for (unsigned j = 0; j < unsigned_bits; ++j) {
 173       value <<= 1;
 174       value |= *I;
 175       ++I;
 176     }
 177     ID.AddInteger(value);
 178   }
 179
 180   assert(I == Bools.rend());
 181   Bools.clear();
 182   return ID.ComputeHash();
 183 }
 184
 185 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
 186 // methods process the relevant parts of the Decl.
 187 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
 188   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
 189   llvm::FoldingSetNodeID &ID;
 190   ODRHash &Hash;
 191
 192 public:
 193   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 194       : ID(ID), Hash(Hash) {}
 195
 196   void AddStmt(const Stmt *S) {
 197     Hash.AddBoolean(S);
 198     if (S) {
 199       Hash.AddStmt(S);
 200     }
 201   }
 202
 203   void AddIdentifierInfo(const IdentifierInfo *II) {
 204     Hash.AddBoolean(II);
 205     if (II) {
 206       Hash.AddIdentifierInfo(II);
 207     }
 208   }
 209
 210   void AddQualType(QualType T) {
 211     Hash.AddQualType(T);
 212   }
 213
 214   void Visit(const Decl *D) {
 215     ID.AddInteger(D->getKind());
 216     Inherited::Visit(D);
 217   }
 218
 219   void VisitNamedDecl(const NamedDecl *D) {
 220     Hash.AddDeclarationName(D->getDeclName());
 221     Inherited::VisitNamedDecl(D);
 222   }
 223
 224   void VisitValueDecl(const ValueDecl *D) {
 225     AddQualType(D->getType());
 226     Inherited::VisitValueDecl(D);
 227   }
 228
 229   void VisitParmVarDecl(const ParmVarDecl *D) {
 230     // TODO: Handle default arguments.
 231     Inherited::VisitParmVarDecl(D);
 232   }
 233
 234   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
 235     ID.AddInteger(D->getAccess());
 236     Inherited::VisitAccessSpecDecl(D);
 237   }
 238
 239   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
 240     AddStmt(D->getAssertExpr());
 241     AddStmt(D->getMessage());
 242
 243     Inherited::VisitStaticAssertDecl(D);
 244   }
 245
 246   void VisitFieldDecl(const FieldDecl *D) {
 247     const bool IsBitfield = D->isBitField();
 248     Hash.AddBoolean(IsBitfield);
 249
 250     if (IsBitfield) {
 251       AddStmt(D->getBitWidth());
 252     }
 253
 254     Hash.AddBoolean(D->isMutable());
 255     AddStmt(D->getInClassInitializer());
 256
 257     Inherited::VisitFieldDecl(D);
 258   }
 259
 260   void VisitFunctionDecl(const FunctionDecl *D) {
 261     ID.AddInteger(D->getStorageClass());
 262     Hash.AddBoolean(D->isInlineSpecified());
 263     Hash.AddBoolean(D->isVirtualAsWritten());
 264     Hash.AddBoolean(D->isPure());
 265     Hash.AddBoolean(D->isDeletedAsWritten());
 266
 267     ID.AddInteger(D->param_size());
 268
 269     for (auto *Param : D->parameters()) {
 270       Hash.AddSubDecl(Param);
 271     }
 272
 273     Inherited::VisitFunctionDecl(D);
 274   }
 275
 276   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
 277     Hash.AddBoolean(D->isConst());
 278     Hash.AddBoolean(D->isVolatile());
 279
 280     Inherited::VisitCXXMethodDecl(D);
 281   }
 282
 283   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
 284     AddQualType(D->getUnderlyingType());
 285
 286     Inherited::VisitTypedefNameDecl(D);
 287   }
 288
 289   void VisitTypedefDecl(const TypedefDecl *D) {
 290     Inherited::VisitTypedefDecl(D);
 291   }
 292
 293   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
 294     Inherited::VisitTypeAliasDecl(D);
 295   }
 296 };
 297
 298 // Only allow a small portion of Decl's to be processed.  Remove this once
 299 // all Decl's can be handled.
 300 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
 301   if (D->isImplicit()) return false;
 302   if (D->getDeclContext() != Parent) return false;
 303
 304   switch (D->getKind()) {
 305     default:
 306       return false;
 307     case Decl::AccessSpec:
 308     case Decl::CXXMethod:
 309     case Decl::Field:
 310     case Decl::StaticAssert:
 311     case Decl::TypeAlias:
 312     case Decl::Typedef:
 313       return true;
 314   }
 315 }
 316
 317 void ODRHash::AddSubDecl(const Decl *D) {
 318   assert(D && "Expecting non-null pointer.");
 319   AddDecl(D);
 320
 321   ODRDeclVisitor(ID, *this).Visit(D);
 322 }
 323
 324 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
 325   assert(Record && Record->hasDefinition() &&
 326          "Expected non-null record to be a definition.");
 327
 328   if (isa<ClassTemplateSpecializationDecl>(Record)) {
 329     return;
 330   }
 331
 332   AddDecl(Record);
 333
 334   // Filter out sub-Decls which will not be processed in order to get an
 335   // accurate count of Decl's.
 336   llvm::SmallVector<const Decl *, 16> Decls;
 337   for (const Decl *SubDecl : Record->decls()) {
 338     if (isWhitelistedDecl(SubDecl, Record)) {
 339       Decls.push_back(SubDecl);
 340     }
 341   }
 342
 343   ID.AddInteger(Decls.size());
 344   for (auto SubDecl : Decls) {
 345     AddSubDecl(SubDecl);
 346   }
 347 }
 348
 349 void ODRHash::AddDecl(const Decl *D) {
 350   assert(D && "Expecting non-null pointer.");
 351   auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
 352   ID.AddInteger(Result.first->second);
 353   // On first encounter of a Decl pointer, process it.  Every time afterwards,
 354   // only the index value is needed.
 355   if (!Result.second) {
 356     return;
 357   }
 358
 359   ID.AddInteger(D->getKind());
 360
 361   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
 362     AddDeclarationName(ND->getDeclName());
 363   }
 364 }
 365
 366 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
 367 // methods process the relevant parts of the Type.
 368 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
 369   typedef TypeVisitor<ODRTypeVisitor> Inherited;
 370   llvm::FoldingSetNodeID &ID;
 371   ODRHash &Hash;
 372
 373 public:
 374   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 375       : ID(ID), Hash(Hash) {}
 376
 377   void AddStmt(Stmt *S) {
 378     Hash.AddBoolean(S);
 379     if (S) {
 380       Hash.AddStmt(S);
 381     }
 382   }
 383
 384   void AddDecl(Decl *D) {
 385     Hash.AddBoolean(D);
 386     if (D) {
 387       Hash.AddDecl(D);
 388     }
 389   }
 390
 391   void AddQualType(QualType T) {
 392     Hash.AddQualType(T);
 393   }
 394
 395   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
 396     Hash.AddNestedNameSpecifier(NNS);
 397   }
 398
 399   void AddIdentifierInfo(const IdentifierInfo *II) {
 400     Hash.AddBoolean(II);
 401     if (II) {
 402       Hash.AddIdentifierInfo(II);
 403     }
 404   }
 405
 406   void VisitQualifiers(Qualifiers Quals) {
 407     ID.AddInteger(Quals.getAsOpaqueValue());
 408   }
 409
 410   void Visit(const Type *T) {
 411     ID.AddInteger(T->getTypeClass());
 412     Inherited::Visit(T);
 413   }
 414
 415   void VisitType(const Type *T) {}
 416
 417   void VisitAdjustedType(const AdjustedType *T) {
 418     AddQualType(T->getOriginalType());
 419     AddQualType(T->getAdjustedType());
 420     VisitType(T);
 421   }
 422
 423   void VisitDecayedType(const DecayedType *T) {
 424     AddQualType(T->getDecayedType());
 425     AddQualType(T->getPointeeType());
 426     VisitAdjustedType(T);
 427   }
 428
 429   void VisitArrayType(const ArrayType *T) {
 430     AddQualType(T->getElementType());
 431     ID.AddInteger(T->getSizeModifier());
 432     VisitQualifiers(T->getIndexTypeQualifiers());
 433     VisitType(T);
 434   }
 435   void VisitConstantArrayType(const ConstantArrayType *T) {
 436     T->getSize().Profile(ID);
 437     VisitArrayType(T);
 438   }
 439
 440   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
 441     AddStmt(T->getSizeExpr());
 442     VisitArrayType(T);
 443   }
 444
 445   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
 446     VisitArrayType(T);
 447   }
 448
 449   void VisitVariableArrayType(const VariableArrayType *T) {
 450     AddStmt(T->getSizeExpr());
 451     VisitArrayType(T);
 452   }
 453
 454   void VisitBuiltinType(const BuiltinType *T) {
 455     ID.AddInteger(T->getKind());
 456     VisitType(T);
 457   }
 458
 459   void VisitFunctionType(const FunctionType *T) {
 460     AddQualType(T->getReturnType());
 461     T->getExtInfo().Profile(ID);
 462     Hash.AddBoolean(T->isConst());
 463     Hash.AddBoolean(T->isVolatile());
 464     Hash.AddBoolean(T->isRestrict());
 465     VisitType(T);
 466   }
 467
 468   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
 469     VisitFunctionType(T);
 470   }
 471
 472   void VisitFunctionProtoType(const FunctionProtoType *T) {
 473     ID.AddInteger(T->getNumParams());
 474     for (auto ParamType : T->getParamTypes())
 475       AddQualType(ParamType);
 476
 477     VisitFunctionType(T);
 478   }
 479
 480   void VisitTypedefType(const TypedefType *T) {
 481     AddDecl(T->getDecl());
 482     AddQualType(T->getDecl()->getUnderlyingType().getCanonicalType());
 483     VisitType(T);
 484   }
 485
 486   void VisitTagType(const TagType *T) {
 487     AddDecl(T->getDecl());
 488     VisitType(T);
 489   }
 490
 491   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
 492   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
 493
 494   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
 495     ID.AddInteger(T->getKeyword());
 496     VisitType(T);
 497   };
 498
 499   void VisitDependentNameType(const DependentNameType *T) {
 500     AddNestedNameSpecifier(T->getQualifier());
 501     AddIdentifierInfo(T->getIdentifier());
 502     VisitTypeWithKeyword(T);
 503   }
 504
 505   void VisitDependentTemplateSpecializationType(
 506       const DependentTemplateSpecializationType *T) {
 507     AddIdentifierInfo(T->getIdentifier());
 508     AddNestedNameSpecifier(T->getQualifier());
 509     ID.AddInteger(T->getNumArgs());
 510     for (const auto &TA : T->template_arguments()) {
 511       Hash.AddTemplateArgument(TA);
 512     }
 513     VisitTypeWithKeyword(T);
 514   }
 515
 516   void VisitElaboratedType(const ElaboratedType *T) {
 517     AddNestedNameSpecifier(T->getQualifier());
 518     AddQualType(T->getNamedType());
 519     VisitTypeWithKeyword(T);
 520   }
 521
 522   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
 523     ID.AddInteger(T->getNumArgs());
 524     for (const auto &TA : T->template_arguments()) {
 525       Hash.AddTemplateArgument(TA);
 526     }
 527     Hash.AddTemplateName(T->getTemplateName());
 528     VisitType(T);
 529   }
 530 };
 531
 532 void ODRHash::AddType(const Type *T) {
 533   assert(T && "Expecting non-null pointer.");
 534   auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
 535   ID.AddInteger(Result.first->second);
 536   // On first encounter of a Type pointer, process it.  Every time afterwards,
 537   // only the index value is needed.
 538   if (!Result.second) {
 539     return;
 540   }
 541
 542   ODRTypeVisitor(ID, *this).Visit(T);
 543 }
 544
 545 void ODRHash::AddQualType(QualType T) {
 546   AddBoolean(T.isNull());
 547   if (T.isNull())
 548     return;
 549   SplitQualType split = T.split();
 550   ID.AddInteger(split.Quals.getAsOpaqueValue());
 551   AddType(split.Ty);
 552 }
 553
 554 void ODRHash::AddBoolean(bool Value) {
 555   Bools.push_back(Value);
 556 }