ODRHash.cpp revision 317019 
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
23using namespace clang;
24
25void ODRHash::AddStmt(const Stmt *S) {
26  assert(S && "Expecting non-null pointer.");
27  S->ProcessODRHash(ID, *this);
28}
29
30void ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
31  assert(II && "Expecting non-null pointer.");
32  ID.AddString(II->getName());
33}
34
35void 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
84void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {}
85void ODRHash::AddTemplateName(TemplateName Name) {}
86void ODRHash::AddTemplateArgument(TemplateArgument TA) {}
87void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {}
88
89void ODRHash::clear() {
90  DeclMap.clear();
91  TypeMap.clear();
92  Bools.clear();
93  ID.clear();
94}
95
96unsigned 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.
130class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
131  typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
132  llvm::FoldingSetNodeID &ID;
133  ODRHash &Hash;
134
135public:
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 VisitAccessSpecDecl(const AccessSpecDecl *D) {
173    ID.AddInteger(D->getAccess());
174    Inherited::VisitAccessSpecDecl(D);
175  }
176
177  void VisitStaticAssertDecl(const StaticAssertDecl *D) {
178    AddStmt(D->getAssertExpr());
179    AddStmt(D->getMessage());
180
181    Inherited::VisitStaticAssertDecl(D);
182  }
183
184  void VisitFieldDecl(const FieldDecl *D) {
185    const bool IsBitfield = D->isBitField();
186    Hash.AddBoolean(IsBitfield);
187
188    if (IsBitfield) {
189      AddStmt(D->getBitWidth());
190    }
191
192    Hash.AddBoolean(D->isMutable());
193    AddStmt(D->getInClassInitializer());
194
195    Inherited::VisitFieldDecl(D);
196  }
197
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());
204
205    Inherited::VisitFunctionDecl(D);
206  }
207
208  void VisitCXXMethodDecl(const CXXMethodDecl *D) {
209    Hash.AddBoolean(D->isConst());
210    Hash.AddBoolean(D->isVolatile());
211
212    Inherited::VisitCXXMethodDecl(D);
213  }
214
215  void VisitTypedefNameDecl(const TypedefNameDecl *D) {
216    AddQualType(D->getUnderlyingType());
217
218    Inherited::VisitTypedefNameDecl(D);
219  }
220
221  void VisitTypedefDecl(const TypedefDecl *D) {
222    Inherited::VisitTypedefDecl(D);
223  }
224
225  void VisitTypeAliasDecl(const TypeAliasDecl *D) {
226    Inherited::VisitTypeAliasDecl(D);
227  }
228};
229
230// Only allow a small portion of Decl's to be processed.  Remove this once
231// all Decl's can be handled.
232bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
233  if (D->isImplicit()) return false;
234  if (D->getDeclContext() != Parent) return false;
235
236  switch (D->getKind()) {
237    default:
238      return false;
239    case Decl::AccessSpec:
240    case Decl::CXXMethod:
241    case Decl::Field:
242    case Decl::StaticAssert:
243    case Decl::TypeAlias:
244    case Decl::Typedef:
245      return true;
246  }
247}
248
249void ODRHash::AddSubDecl(const Decl *D) {
250  assert(D && "Expecting non-null pointer.");
251  AddDecl(D);
252
253  ODRDeclVisitor(ID, *this).Visit(D);
254}
255
256void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
257  assert(Record && Record->hasDefinition() &&
258         "Expected non-null record to be a definition.");
259  AddDecl(Record);
260
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);
267    }
268  }
269
270  ID.AddInteger(Decls.size());
271  for (auto SubDecl : Decls) {
272    AddSubDecl(SubDecl);
273  }
274}
275
276void 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) {
283    return;
284  }
285
286  ID.AddInteger(D->getKind());
287
288  if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
289    AddDeclarationName(ND->getDeclName());
290  }
291}
292
293// Process a Type pointer.  Add* methods call back into ODRHash while Visit*
294// methods process the relevant parts of the Type.
295class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
296  typedef TypeVisitor<ODRTypeVisitor> Inherited;
297  llvm::FoldingSetNodeID &ID;
298  ODRHash &Hash;
299
300public:
301  ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
302      : ID(ID), Hash(Hash) {}
303
304  void AddStmt(Stmt *S) {
305    Hash.AddBoolean(S);
306    if (S) {
307      Hash.AddStmt(S);
308    }
309  }
310
311  void AddDecl(Decl *D) {
312    Hash.AddBoolean(D);
313    if (D) {
314      Hash.AddDecl(D);
315    }
316  }
317
318  void Visit(const Type *T) {
319    ID.AddInteger(T->getTypeClass());
320    Inherited::Visit(T);
321  }
322
323  void VisitType(const Type *T) {}
324
325  void VisitBuiltinType(const BuiltinType *T) {
326    ID.AddInteger(T->getKind());
327    VisitType(T);
328  }
329
330  void VisitTypedefType(const TypedefType *T) {
331    AddDecl(T->getDecl());
332    Hash.AddQualType(T->getDecl()->getUnderlyingType());
333    VisitType(T);
334  }
335};
336
337void 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) {
344    return;
345  }
346
347  ODRTypeVisitor(ID, *this).Visit(T);
348}
349
350void ODRHash::AddQualType(QualType T) {
351  AddBoolean(T.isNull());
352  if (T.isNull())
353    return;
354  SplitQualType split = T.split();
355  ID.AddInteger(split.Quals.getAsOpaqueValue());
356  AddType(split.Ty);
357}
358
359void ODRHash::AddBoolean(bool Value) {
360  Bools.push_back(Value);
361}
362