1 //===-- ODRHash.cpp - Hashing to diagnose ODR failures ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This file implements the ODRHash class, which calculates a hash based
12 /// on AST nodes, which is stable across different runs.
14 //===----------------------------------------------------------------------===//
16 #include "clang/AST/ODRHash.h"
18 #include "clang/AST/DeclVisitor.h"
19 #include "clang/AST/NestedNameSpecifier.h"
20 #include "clang/AST/StmtVisitor.h"
21 #include "clang/AST/TypeVisitor.h"
23 using namespace clang;
25 void ODRHash::AddStmt(const Stmt *S) {
26 assert(S && "Expecting non-null pointer.");
27 S->ProcessODRHash(ID, *this);
30 void ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
31 assert(II && "Expecting non-null pointer.");
32 ID.AddString(II->getName());
35 void ODRHash::AddDeclarationName(DeclarationName Name) {
36 AddBoolean(Name.isEmpty());
40 auto Kind = Name.getNameKind();
43 case DeclarationName::Identifier:
44 AddIdentifierInfo(Name.getAsIdentifierInfo());
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));
59 case DeclarationName::CXXConstructorName:
60 case DeclarationName::CXXDestructorName:
61 AddQualType(Name.getCXXNameType());
63 case DeclarationName::CXXOperatorName:
64 ID.AddInteger(Name.getCXXOverloadedOperator());
66 case DeclarationName::CXXLiteralOperatorName:
67 AddIdentifierInfo(Name.getCXXLiteralIdentifier());
69 case DeclarationName::CXXConversionFunctionName:
70 AddQualType(Name.getCXXNameType());
72 case DeclarationName::CXXUsingDirective:
74 case DeclarationName::CXXDeductionGuideName: {
75 auto *Template = Name.getCXXDeductionGuideTemplate();
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) {}
89 void ODRHash::clear() {
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
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();
106 for (unsigned i = 0; i < remainder; ++i) {
111 ID.AddInteger(value);
113 for (unsigned i = 0; i < loops; ++i) {
115 for (unsigned j = 0; j < unsigned_bits; ++j) {
120 ID.AddInteger(value);
123 assert(I == Bools.rend());
125 return ID.ComputeHash();
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;
136 ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
137 : ID(ID), Hash(Hash) {}
139 void AddStmt(const Stmt *S) {
146 void AddIdentifierInfo(const IdentifierInfo *II) {
149 Hash.AddIdentifierInfo(II);
153 void AddQualType(QualType T) {
157 void Visit(const Decl *D) {
158 ID.AddInteger(D->getKind());
162 void VisitNamedDecl(const NamedDecl *D) {
163 Hash.AddDeclarationName(D->getDeclName());
164 Inherited::VisitNamedDecl(D);
167 void VisitValueDecl(const ValueDecl *D) {
168 AddQualType(D->getType());
169 Inherited::VisitValueDecl(D);
172 void VisitAccessSpecDecl(const AccessSpecDecl *D) {
173 ID.AddInteger(D->getAccess());
174 Inherited::VisitAccessSpecDecl(D);
177 void VisitStaticAssertDecl(const StaticAssertDecl *D) {
178 AddStmt(D->getAssertExpr());
179 AddStmt(D->getMessage());
181 Inherited::VisitStaticAssertDecl(D);
184 void VisitFieldDecl(const FieldDecl *D) {
185 const bool IsBitfield = D->isBitField();
186 Hash.AddBoolean(IsBitfield);
189 AddStmt(D->getBitWidth());
192 Hash.AddBoolean(D->isMutable());
193 AddStmt(D->getInClassInitializer());
195 Inherited::VisitFieldDecl(D);
198 void VisitFunctionDecl(const FunctionDecl *D) {
199 ID.AddInteger(D->getStorageClass());
200 Hash.AddBoolean(D->isInlineSpecified());
201 Hash.AddBoolean(D->isVirtualAsWritten());
202 Hash.AddBoolean(D->isPure());
203 Hash.AddBoolean(D->isDeletedAsWritten());
205 Inherited::VisitFunctionDecl(D);
208 void VisitCXXMethodDecl(const CXXMethodDecl *D) {
209 Hash.AddBoolean(D->isConst());
210 Hash.AddBoolean(D->isVolatile());
212 Inherited::VisitCXXMethodDecl(D);
215 void VisitTypedefNameDecl(const TypedefNameDecl *D) {
216 AddQualType(D->getUnderlyingType());
218 Inherited::VisitTypedefNameDecl(D);
221 void VisitTypedefDecl(const TypedefDecl *D) {
222 Inherited::VisitTypedefDecl(D);
225 void VisitTypeAliasDecl(const TypeAliasDecl *D) {
226 Inherited::VisitTypeAliasDecl(D);
230 // Only allow a small portion of Decl's to be processed. Remove this once
231 // all Decl's can be handled.
232 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
233 if (D->isImplicit()) return false;
234 if (D->getDeclContext() != Parent) return false;
236 switch (D->getKind()) {
239 case Decl::AccessSpec:
240 case Decl::CXXMethod:
242 case Decl::StaticAssert:
243 case Decl::TypeAlias:
249 void ODRHash::AddSubDecl(const Decl *D) {
250 assert(D && "Expecting non-null pointer.");
253 ODRDeclVisitor(ID, *this).Visit(D);
256 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
257 assert(Record && Record->hasDefinition() &&
258 "Expected non-null record to be a definition.");
261 // Filter out sub-Decls which will not be processed in order to get an
262 // accurate count of Decl's.
263 llvm::SmallVector<const Decl *, 16> Decls;
264 for (const Decl *SubDecl : Record->decls()) {
265 if (isWhitelistedDecl(SubDecl, Record)) {
266 Decls.push_back(SubDecl);
270 ID.AddInteger(Decls.size());
271 for (auto SubDecl : Decls) {
276 void ODRHash::AddDecl(const Decl *D) {
277 assert(D && "Expecting non-null pointer.");
278 auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
279 ID.AddInteger(Result.first->second);
280 // On first encounter of a Decl pointer, process it. Every time afterwards,
281 // only the index value is needed.
282 if (!Result.second) {
286 ID.AddInteger(D->getKind());
288 if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
289 AddDeclarationName(ND->getDeclName());
293 // Process a Type pointer. Add* methods call back into ODRHash while Visit*
294 // methods process the relevant parts of the Type.
295 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
296 typedef TypeVisitor<ODRTypeVisitor> Inherited;
297 llvm::FoldingSetNodeID &ID;
301 ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
302 : ID(ID), Hash(Hash) {}
304 void AddStmt(Stmt *S) {
311 void AddDecl(Decl *D) {
318 void Visit(const Type *T) {
319 ID.AddInteger(T->getTypeClass());
323 void VisitType(const Type *T) {}
325 void VisitBuiltinType(const BuiltinType *T) {
326 ID.AddInteger(T->getKind());
330 void VisitTypedefType(const TypedefType *T) {
331 AddDecl(T->getDecl());
332 Hash.AddQualType(T->getDecl()->getUnderlyingType());
337 void ODRHash::AddType(const Type *T) {
338 assert(T && "Expecting non-null pointer.");
339 auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
340 ID.AddInteger(Result.first->second);
341 // On first encounter of a Type pointer, process it. Every time afterwards,
342 // only the index value is needed.
343 if (!Result.second) {
347 ODRTypeVisitor(ID, *this).Visit(T);
350 void ODRHash::AddQualType(QualType T) {
351 AddBoolean(T.isNull());
354 SplitQualType split = T.split();
355 ID.AddInteger(split.Quals.getAsOpaqueValue());
359 void ODRHash::AddBoolean(bool Value) {
360 Bools.push_back(Value);