granicus.if.org Git - clang/blob - 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 void ODRHash::AddTemplateName(TemplateName Name) {}
  86 void ODRHash::AddTemplateArgument(TemplateArgument TA) {}
  87 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {}
  88
  89 void ODRHash::clear() {
  90   DeclMap.clear();
  91   TypeMap.clear();
  92   Bools.clear();
  93   ID.clear();
  94 }
  95
  96 unsigned ODRHash::CalculateHash() {
  97   // Append the bools to the end of the data segment backwards.  This allows
  98   // for the bools data to be compressed 32 times smaller compared to using
  99   // ID.AddBoolean
 100   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
 101   const unsigned size = Bools.size();
 102   const unsigned remainder = size % unsigned_bits;
 103   const unsigned loops = size / unsigned_bits;
 104   auto I = Bools.rbegin();
 105   unsigned value = 0;
 106   for (unsigned i = 0; i < remainder; ++i) {
 107     value <<= 1;
 108     value |= *I;
 109     ++I;
 110   }
 111   ID.AddInteger(value);
 112
 113   for (unsigned i = 0; i < loops; ++i) {
 114     value = 0;
 115     for (unsigned j = 0; j < unsigned_bits; ++j) {
 116       value <<= 1;
 117       value |= *I;
 118       ++I;
 119     }
 120     ID.AddInteger(value);
 121   }
 122
 123   assert(I == Bools.rend());
 124   Bools.clear();
 125   return ID.ComputeHash();
 126 }
 127
 128 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
 129 // methods process the relevant parts of the Decl.
 130 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
 131   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
 132   llvm::FoldingSetNodeID &ID;
 133   ODRHash &Hash;
 134
 135 public:
 136   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 137       : ID(ID), Hash(Hash) {}
 138
 139   void AddStmt(const Stmt *S) {
 140     Hash.AddBoolean(S);
 141     if (S) {
 142       Hash.AddStmt(S);
 143     }
 144   }
 145
 146   void AddIdentifierInfo(const IdentifierInfo *II) {
 147     Hash.AddBoolean(II);
 148     if (II) {
 149       Hash.AddIdentifierInfo(II);
 150     }
 151   }
 152
 153   void AddQualType(QualType T) {
 154     Hash.AddQualType(T);
 155   }
 156
 157   void Visit(const Decl *D) {
 158     ID.AddInteger(D->getKind());
 159     Inherited::Visit(D);
 160   }
 161
 162   void VisitNamedDecl(const NamedDecl *D) {
 163     Hash.AddDeclarationName(D->getDeclName());
 164     Inherited::VisitNamedDecl(D);
 165   }
 166
 167   void VisitValueDecl(const ValueDecl *D) {
 168     AddQualType(D->getType());
 169     Inherited::VisitValueDecl(D);
 170   }
 171
 172   void VisitParmVarDecl(const ParmVarDecl *D) {
 173     AddStmt(D->getDefaultArg());
 174     Inherited::VisitParmVarDecl(D);
 175   }
 176
 177   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
 178     ID.AddInteger(D->getAccess());
 179     Inherited::VisitAccessSpecDecl(D);
 180   }
 181
 182   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
 183     AddStmt(D->getAssertExpr());
 184     AddStmt(D->getMessage());
 185
 186     Inherited::VisitStaticAssertDecl(D);
 187   }
 188
 189   void VisitFieldDecl(const FieldDecl *D) {
 190     const bool IsBitfield = D->isBitField();
 191     Hash.AddBoolean(IsBitfield);
 192
 193     if (IsBitfield) {
 194       AddStmt(D->getBitWidth());
 195     }
 196
 197     Hash.AddBoolean(D->isMutable());
 198     AddStmt(D->getInClassInitializer());
 199
 200     Inherited::VisitFieldDecl(D);
 201   }
 202
 203   void VisitFunctionDecl(const FunctionDecl *D) {
 204     ID.AddInteger(D->getStorageClass());
 205     Hash.AddBoolean(D->isInlineSpecified());
 206     Hash.AddBoolean(D->isVirtualAsWritten());
 207     Hash.AddBoolean(D->isPure());
 208     Hash.AddBoolean(D->isDeletedAsWritten());
 209
 210     ID.AddInteger(D->param_size());
 211
 212     for (auto *Param : D->parameters()) {
 213       Hash.AddSubDecl(Param);
 214     }
 215
 216     Inherited::VisitFunctionDecl(D);
 217   }
 218
 219   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
 220     Hash.AddBoolean(D->isConst());
 221     Hash.AddBoolean(D->isVolatile());
 222
 223     Inherited::VisitCXXMethodDecl(D);
 224   }
 225
 226   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
 227     AddQualType(D->getUnderlyingType());
 228
 229     Inherited::VisitTypedefNameDecl(D);
 230   }
 231
 232   void VisitTypedefDecl(const TypedefDecl *D) {
 233     Inherited::VisitTypedefDecl(D);
 234   }
 235
 236   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
 237     Inherited::VisitTypeAliasDecl(D);
 238   }
 239 };
 240
 241 // Only allow a small portion of Decl's to be processed.  Remove this once
 242 // all Decl's can be handled.
 243 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
 244   if (D->isImplicit()) return false;
 245   if (D->getDeclContext() != Parent) return false;
 246
 247   switch (D->getKind()) {
 248     default:
 249       return false;
 250     case Decl::AccessSpec:
 251     case Decl::CXXMethod:
 252     case Decl::Field:
 253     case Decl::StaticAssert:
 254     case Decl::TypeAlias:
 255     case Decl::Typedef:
 256       return true;
 257   }
 258 }
 259
 260 void ODRHash::AddSubDecl(const Decl *D) {
 261   assert(D && "Expecting non-null pointer.");
 262   AddDecl(D);
 263
 264   ODRDeclVisitor(ID, *this).Visit(D);
 265 }
 266
 267 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
 268   assert(Record && Record->hasDefinition() &&
 269          "Expected non-null record to be a definition.");
 270   AddDecl(Record);
 271
 272   // Filter out sub-Decls which will not be processed in order to get an
 273   // accurate count of Decl's.
 274   llvm::SmallVector<const Decl *, 16> Decls;
 275   for (const Decl *SubDecl : Record->decls()) {
 276     if (isWhitelistedDecl(SubDecl, Record)) {
 277       Decls.push_back(SubDecl);
 278     }
 279   }
 280
 281   ID.AddInteger(Decls.size());
 282   for (auto SubDecl : Decls) {
 283     AddSubDecl(SubDecl);
 284   }
 285 }
 286
 287 void ODRHash::AddDecl(const Decl *D) {
 288   assert(D && "Expecting non-null pointer.");
 289   auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
 290   ID.AddInteger(Result.first->second);
 291   // On first encounter of a Decl pointer, process it.  Every time afterwards,
 292   // only the index value is needed.
 293   if (!Result.second) {
 294     return;
 295   }
 296
 297   ID.AddInteger(D->getKind());
 298
 299   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
 300     AddDeclarationName(ND->getDeclName());
 301   }
 302 }
 303
 304 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
 305 // methods process the relevant parts of the Type.
 306 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
 307   typedef TypeVisitor<ODRTypeVisitor> Inherited;
 308   llvm::FoldingSetNodeID &ID;
 309   ODRHash &Hash;
 310
 311 public:
 312   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 313       : ID(ID), Hash(Hash) {}
 314
 315   void AddStmt(Stmt *S) {
 316     Hash.AddBoolean(S);
 317     if (S) {
 318       Hash.AddStmt(S);
 319     }
 320   }
 321
 322   void AddDecl(Decl *D) {
 323     Hash.AddBoolean(D);
 324     if (D) {
 325       Hash.AddDecl(D);
 326     }
 327   }
 328
 329   void AddQualType(QualType T) {
 330     Hash.AddQualType(T);
 331   }
 332
 333   void VisitQualifiers(Qualifiers Quals) {
 334     ID.AddInteger(Quals.getAsOpaqueValue());
 335   }
 336
 337   void Visit(const Type *T) {
 338     ID.AddInteger(T->getTypeClass());
 339     Inherited::Visit(T);
 340   }
 341
 342   void VisitType(const Type *T) {}
 343
 344   void VisitAdjustedType(const AdjustedType *T) {
 345     AddQualType(T->getOriginalType());
 346     AddQualType(T->getAdjustedType());
 347     VisitType(T);
 348   }
 349
 350   void VisitDecayedType(const DecayedType *T) {
 351     AddQualType(T->getDecayedType());
 352     AddQualType(T->getPointeeType());
 353     VisitAdjustedType(T);
 354   }
 355
 356   void VisitArrayType(const ArrayType *T) {
 357     AddQualType(T->getElementType());
 358     ID.AddInteger(T->getSizeModifier());
 359     VisitQualifiers(T->getIndexTypeQualifiers());
 360     VisitType(T);
 361   }
 362   void VisitConstantArrayType(const ConstantArrayType *T) {
 363     T->getSize().Profile(ID);
 364     VisitArrayType(T);
 365   }
 366
 367   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
 368     AddStmt(T->getSizeExpr());
 369     VisitArrayType(T);
 370   }
 371
 372   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
 373     VisitArrayType(T);
 374   }
 375
 376   void VisitVariableArrayType(const VariableArrayType *T) {
 377     AddStmt(T->getSizeExpr());
 378     VisitArrayType(T);
 379   }
 380
 381   void VisitBuiltinType(const BuiltinType *T) {
 382     ID.AddInteger(T->getKind());
 383     VisitType(T);
 384   }
 385
 386   void VisitFunctionType(const FunctionType *T) {
 387     AddQualType(T->getReturnType());
 388     T->getExtInfo().Profile(ID);
 389     Hash.AddBoolean(T->isConst());
 390     Hash.AddBoolean(T->isVolatile());
 391     Hash.AddBoolean(T->isRestrict());
 392     VisitType(T);
 393   }
 394
 395   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
 396     VisitFunctionType(T);
 397   }
 398
 399   void VisitFunctionProtoType(const FunctionProtoType *T) {
 400     ID.AddInteger(T->getNumParams());
 401     for (auto ParamType : T->getParamTypes())
 402       AddQualType(ParamType);
 403
 404     const auto &epi = T->getExtProtoInfo();
 405     ID.AddInteger(epi.Variadic);
 406     ID.AddInteger(epi.TypeQuals);
 407     ID.AddInteger(epi.RefQualifier);
 408     ID.AddInteger(epi.ExceptionSpec.Type);
 409
 410     if (epi.ExceptionSpec.Type == EST_Dynamic) {
 411       for (QualType Ex : epi.ExceptionSpec.Exceptions)
 412         AddQualType(Ex);
 413     } else if (epi.ExceptionSpec.Type == EST_ComputedNoexcept &&
 414                epi.ExceptionSpec.NoexceptExpr) {
 415       AddStmt(epi.ExceptionSpec.NoexceptExpr);
 416     } else if (epi.ExceptionSpec.Type == EST_Uninstantiated ||
 417                epi.ExceptionSpec.Type == EST_Unevaluated) {
 418       AddDecl(epi.ExceptionSpec.SourceDecl->getCanonicalDecl());
 419     }
 420     if (epi.ExtParameterInfos) {
 421       for (unsigned i = 0; i != T->getNumParams(); ++i)
 422         ID.AddInteger(epi.ExtParameterInfos[i].getOpaqueValue());
 423     }
 424     epi.ExtInfo.Profile(ID);
 425     Hash.AddBoolean(epi.HasTrailingReturn);
 426
 427     VisitFunctionType(T);
 428   }
 429
 430   void VisitTypedefType(const TypedefType *T) {
 431     AddDecl(T->getDecl());
 432     Hash.AddQualType(T->getDecl()->getUnderlyingType());
 433     VisitType(T);
 434   }
 435 };
 436
 437 void ODRHash::AddType(const Type *T) {
 438   assert(T && "Expecting non-null pointer.");
 439   auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
 440   ID.AddInteger(Result.first->second);
 441   // On first encounter of a Type pointer, process it.  Every time afterwards,
 442   // only the index value is needed.
 443   if (!Result.second) {
 444     return;
 445   }
 446
 447   ODRTypeVisitor(ID, *this).Visit(T);
 448 }
 449
 450 void ODRHash::AddQualType(QualType T) {
 451   AddBoolean(T.isNull());
 452   if (T.isNull())
 453     return;
 454   SplitQualType split = T.split();
 455   ID.AddInteger(split.Quals.getAsOpaqueValue());
 456   AddType(split.Ty);
 457 }
 458
 459 void ODRHash::AddBoolean(bool Value) {
 460   Bools.push_back(Value);
 461 }