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