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::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {}
36 void ODRHash::AddTemplateName(TemplateName Name) {}
37 void ODRHash::AddDeclarationName(DeclarationName Name) {}
38 void ODRHash::AddTemplateArgument(TemplateArgument TA) {}
39 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {}
40 
41 void ODRHash::clear() {
42   DeclMap.clear();
43   TypeMap.clear();
44   Bools.clear();
45   ID.clear();
46 }
47 
48 unsigned ODRHash::CalculateHash() {
49   // Append the bools to the end of the data segment backwards.  This allows
50   // for the bools data to be compressed 32 times smaller compared to using
51   // ID.AddBoolean
52   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
53   const unsigned size = Bools.size();
54   const unsigned remainder = size % unsigned_bits;
55   const unsigned loops = size / unsigned_bits;
56   auto I = Bools.rbegin();
57   unsigned value = 0;
58   for (unsigned i = 0; i < remainder; ++i) {
59     value <<= 1;
60     value |= *I;
61     ++I;
62   }
63   ID.AddInteger(value);
64 
65   for (unsigned i = 0; i < loops; ++i) {
66     value = 0;
67     for (unsigned j = 0; j < unsigned_bits; ++j) {
68       value <<= 1;
69       value |= *I;
70       ++I;
71     }
72     ID.AddInteger(value);
73   }
74 
75   assert(I == Bools.rend());
76   Bools.clear();
77   return ID.ComputeHash();
78 }
79 
80 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
81 // methods process the relevant parts of the Decl.
82 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
83   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
84   llvm::FoldingSetNodeID &ID;
85   ODRHash &Hash;
86 
87 public:
88   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
89       : ID(ID), Hash(Hash) {}
90 
91   void AddStmt(const Stmt *S) {
92     Hash.AddBoolean(S);
93     if (S) {
94       Hash.AddStmt(S);
95     }
96   }
97 
98   void AddIdentifierInfo(const IdentifierInfo *II) {
99     Hash.AddBoolean(II);
100     if (II) {
101       Hash.AddIdentifierInfo(II);
102     }
103   }
104 
105   void AddQualType(QualType T) {
106     Hash.AddQualType(T);
107   }
108 
109   void Visit(const Decl *D) {
110     ID.AddInteger(D->getKind());
111     Inherited::Visit(D);
112   }
113 
114   void VisitNamedDecl(const NamedDecl *D) {
115     AddIdentifierInfo(D->getIdentifier());
116     Inherited::VisitNamedDecl(D);
117   }
118 
119   void VisitValueDecl(const ValueDecl *D) {
120     AddQualType(D->getType());
121     Inherited::VisitValueDecl(D);
122   }
123 
124   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
125     ID.AddInteger(D->getAccess());
126     Inherited::VisitAccessSpecDecl(D);
127   }
128 
129   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
130     AddStmt(D->getAssertExpr());
131     AddStmt(D->getMessage());
132 
133     Inherited::VisitStaticAssertDecl(D);
134   }
135 
136   void VisitFieldDecl(const FieldDecl *D) {
137     Inherited::VisitFieldDecl(D);
138   }
139 };
140 
141 // Only allow a small portion of Decl's to be processed.  Remove this once
142 // all Decl's can be handled.
143 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
144   if (D->isImplicit()) return false;
145   if (D->getDeclContext() != Parent) return false;
146 
147   switch (D->getKind()) {
148     default:
149       return false;
150     case Decl::AccessSpec:
151     case Decl::Field:
152     case Decl::StaticAssert:
153       return true;
154   }
155 }
156 
157 void ODRHash::AddSubDecl(const Decl *D) {
158   assert(D && "Expecting non-null pointer.");
159   AddDecl(D);
160 
161   ODRDeclVisitor(ID, *this).Visit(D);
162 }
163 
164 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
165   assert(Record && Record->hasDefinition() &&
166          "Expected non-null record to be a definition.");
167   AddDecl(Record);
168 
169   // Filter out sub-Decls which will not be processed in order to get an
170   // accurate count of Decl's.
171   llvm::SmallVector<const Decl *, 16> Decls;
172   for (const Decl *SubDecl : Record->decls()) {
173     if (isWhitelistedDecl(SubDecl, Record)) {
174       Decls.push_back(SubDecl);
175     }
176   }
177 
178   ID.AddInteger(Decls.size());
179   for (auto SubDecl : Decls) {
180     AddSubDecl(SubDecl);
181   }
182 }
183 
184 void ODRHash::AddDecl(const Decl *D) {
185   assert(D && "Expecting non-null pointer.");
186   auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
187   ID.AddInteger(Result.first->second);
188   // On first encounter of a Decl pointer, process it.  Every time afterwards,
189   // only the index value is needed.
190   if (!Result.second) {
191     return;
192   }
193 
194   ID.AddInteger(D->getKind());
195 }
196 
197 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
198 // methods process the relevant parts of the Type.
199 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
200   typedef TypeVisitor<ODRTypeVisitor> Inherited;
201   llvm::FoldingSetNodeID &ID;
202   ODRHash &Hash;
203 
204 public:
205   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
206       : ID(ID), Hash(Hash) {}
207 
208   void AddStmt(Stmt *S) {
209     Hash.AddBoolean(S);
210     if (S) {
211       Hash.AddStmt(S);
212     }
213   }
214 
215   void Visit(const Type *T) {
216     ID.AddInteger(T->getTypeClass());
217     Inherited::Visit(T);
218   }
219 
220   void VisitType(const Type *T) {}
221 
222   void VisitBuiltinType(const BuiltinType *T) {
223     ID.AddInteger(T->getKind());
224     VisitType(T);
225   }
226 };
227 
228 void ODRHash::AddType(const Type *T) {
229   assert(T && "Expecting non-null pointer.");
230   auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
231   ID.AddInteger(Result.first->second);
232   // On first encounter of a Type pointer, process it.  Every time afterwards,
233   // only the index value is needed.
234   if (!Result.second) {
235     return;
236   }
237 
238   ODRTypeVisitor(ID, *this).Visit(T);
239 }
240 
241 void ODRHash::AddQualType(QualType T) {
242   AddBoolean(T.isNull());
243   if (T.isNull())
244     return;
245   SplitQualType split = T.split();
246   ID.AddInteger(split.Quals.getAsOpaqueValue());
247   AddType(split.Ty);
248 }
249 
250 void ODRHash::AddBoolean(bool Value) {
251   Bools.push_back(Value);
252 }
253