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 }
462