1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
4 *
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 */
9
10 #include <cassert>
11 #include <string>
12 #include <iostream>
13 #include <fstream>
14 #include <set>
15 #include <unordered_set>
16 #include <map>
17
18 #include "clang/AST/Attr.h"
19
20 #include "plugin.hxx"
21
22 /**
23 What we are looking for here are methods that are not reachable from any of the program
24 entry points.
25 "Entry points" includes main, and various binary API
26
27 Mostly that means we end up finding cycles of methods i.e. methods that refer to each
28 other, but are not reachable.
29
30 It does so, by dumping various call/definition info to a log file.
31 Be warned that it produces around 20G of log file.
32
33 Then we will post-process the log file with a python script, which takes about
34 15min to run on a fast machine.
35
36 The process goes something like this:
37 $ make check
38 $ make FORCE_COMPILE_ALL=1 COMPILER_PLUGIN_TOOL='methodcycles' check
39 $ ./compilerplugins/clang/methodcycles.py
40
41 Note that the actual process may involve a fair amount of undoing, hand editing, and general messing around
42 to get it to work :-)
43
44 */
45
46 namespace
47 {
48 struct MyFuncInfo
49 {
50 std::string returnType;
51 std::string nameAndParams;
52 std::string sourceLocation;
53 };
operator <(const MyFuncInfo & lhs,const MyFuncInfo & rhs)54 bool operator<(const MyFuncInfo& lhs, const MyFuncInfo& rhs)
55 {
56 return std::tie(lhs.returnType, lhs.nameAndParams)
57 < std::tie(rhs.returnType, rhs.nameAndParams);
58 }
59
60 // try to limit the voluminous output a little
61 static std::multimap<const FunctionDecl*, const FunctionDecl*> callMap;
62 static std::set<MyFuncInfo> definitionSet;
63
64 class MethodCycles : public RecursiveASTVisitor<MethodCycles>, public loplugin::Plugin
65 {
66 public:
MethodCycles(loplugin::InstantiationData const & data)67 explicit MethodCycles(loplugin::InstantiationData const& data)
68 : Plugin(data)
69 {
70 }
71
run()72 virtual void run() override
73 {
74 TraverseDecl(compiler.getASTContext().getTranslationUnitDecl());
75
76 // dump all our output in one write call - this is to try and limit IO "crosstalk" between multiple processes
77 // writing to the same logfile
78
79 std::string output;
80 for (const MyFuncInfo& s : definitionSet)
81 output += "definition:\t" + s.returnType + "\t" + s.nameAndParams + "\t"
82 + s.sourceLocation + "\n";
83 for (const auto& pair : callMap)
84 {
85 if (!isLocationMine(pair.first->getLocation())
86 || !isLocationMine(pair.second->getLocation()))
87 continue;
88 auto niceNameFrom = niceName(pair.first);
89 auto niceNameTo = niceName(pair.second);
90 output += "call:\t" + niceNameFrom.returnType + "\t" + niceNameFrom.nameAndParams + "\t"
91 + niceNameTo.returnType + "\t" + niceNameTo.nameAndParams + "\n";
92 }
93 std::ofstream myfile;
94 myfile.open(WORKDIR "/loplugin.methodcycles.log", std::ios::app | std::ios::out);
95 myfile << output;
96 myfile.close();
97 }
98
shouldVisitTemplateInstantiations() const99 bool shouldVisitTemplateInstantiations() const { return true; }
shouldVisitImplicitCode() const100 bool shouldVisitImplicitCode() const { return true; }
101
102 bool VisitCallExpr(CallExpr*);
103 bool VisitFunctionDecl(const FunctionDecl* decl);
104 bool VisitDeclRefExpr(const DeclRefExpr*);
105 bool VisitCXXConstructExpr(const CXXConstructExpr*);
106
107 bool TraverseFunctionDecl(FunctionDecl*);
108 bool TraverseCXXMethodDecl(CXXMethodDecl*);
109 bool TraverseCXXConstructorDecl(CXXConstructorDecl*);
110 bool TraverseCXXConversionDecl(CXXConversionDecl*);
111 bool TraverseCXXDestructorDecl(CXXDestructorDecl*);
112 bool TraverseCXXDeductionGuideDecl(CXXDeductionGuideDecl*);
113
114 private:
115 void logCallToRootMethods(const FunctionDecl* functionDeclFrom,
116 const FunctionDecl* functionDeclTo);
117 void findRoots(const FunctionDecl* functionDecl,
118 std::unordered_set<const FunctionDecl*>& roots);
119 MyFuncInfo niceName(const FunctionDecl* functionDecl);
120 bool isLocationMine(SourceLocation loc);
121 std::string toString(SourceLocation loc);
122 FunctionDecl const* currentFunctionDecl = nullptr;
123 };
124
niceName(const FunctionDecl * functionDecl)125 MyFuncInfo MethodCycles::niceName(const FunctionDecl* functionDecl)
126 {
127 if (functionDecl->getInstantiatedFromMemberFunction())
128 functionDecl = functionDecl->getInstantiatedFromMemberFunction();
129 #if CLANG_VERSION < 90000
130 else if (functionDecl->getClassScopeSpecializationPattern())
131 functionDecl = functionDecl->getClassScopeSpecializationPattern();
132 #endif
133 else if (functionDecl->getTemplateInstantiationPattern())
134 functionDecl = functionDecl->getTemplateInstantiationPattern();
135
136 MyFuncInfo aInfo;
137 if (!isa<CXXConstructorDecl>(functionDecl))
138 {
139 aInfo.returnType = functionDecl->getReturnType().getCanonicalType().getAsString();
140 }
141 else
142 {
143 aInfo.returnType = "";
144 }
145
146 if (auto methodDecl = dyn_cast<CXXMethodDecl>(functionDecl))
147 {
148 const CXXRecordDecl* recordDecl = methodDecl->getParent();
149 aInfo.nameAndParams
150 = recordDecl->getQualifiedNameAsString() + "::" + functionDecl->getNameAsString() + "(";
151 }
152 else
153 {
154 aInfo.nameAndParams = functionDecl->getQualifiedNameAsString() + "(";
155 }
156 bool bFirst = true;
157 for (const ParmVarDecl* pParmVarDecl : functionDecl->parameters())
158 {
159 if (bFirst)
160 bFirst = false;
161 else
162 aInfo.nameAndParams += ",";
163 aInfo.nameAndParams += pParmVarDecl->getType().getCanonicalType().getAsString();
164 }
165 aInfo.nameAndParams += ")";
166 if (isa<CXXMethodDecl>(functionDecl) && dyn_cast<CXXMethodDecl>(functionDecl)->isConst())
167 {
168 aInfo.nameAndParams += " const";
169 }
170
171 aInfo.sourceLocation = toString(functionDecl->getLocation());
172
173 return aInfo;
174 }
175
toString(SourceLocation loc)176 std::string MethodCycles::toString(SourceLocation loc)
177 {
178 SourceLocation expansionLoc = compiler.getSourceManager().getExpansionLoc(loc);
179 StringRef name = getFilenameOfLocation(expansionLoc);
180 std::string sourceLocation
181 = std::string(name.substr(strlen(SRCDIR) + 1)) + ":"
182 + std::to_string(compiler.getSourceManager().getSpellingLineNumber(expansionLoc));
183 loplugin::normalizeDotDotInFilePath(sourceLocation);
184 return sourceLocation;
185 }
186
isLocationMine(SourceLocation loc)187 bool MethodCycles::isLocationMine(SourceLocation loc)
188 {
189 SourceLocation expansionLoc = compiler.getSourceManager().getExpansionLoc(loc);
190 if (compiler.getSourceManager().isInSystemHeader(expansionLoc))
191 return false;
192 const char* bufferName = compiler.getSourceManager().getPresumedLoc(expansionLoc).getFilename();
193 if (bufferName == NULL)
194 return false;
195 if (loplugin::hasPathnamePrefix(bufferName, WORKDIR "/")
196 || loplugin::hasPathnamePrefix(bufferName, BUILDDIR "/")
197 || loplugin::hasPathnamePrefix(bufferName, SRCDIR "/"))
198 return true; // ok
199 return false;
200 }
201
logCallToRootMethods(const FunctionDecl * functionDeclFrom,const FunctionDecl * functionDeclTo)202 void MethodCycles::logCallToRootMethods(const FunctionDecl* functionDeclFrom,
203 const FunctionDecl* functionDeclTo)
204 {
205 if (!functionDeclFrom)
206 {
207 // template magic mostly, but also things called from initialisers
208 return;
209 }
210 functionDeclFrom = functionDeclFrom->getCanonicalDecl();
211 functionDeclTo = functionDeclTo->getCanonicalDecl();
212
213 std::unordered_set<const FunctionDecl*> fromRoots;
214 findRoots(functionDeclFrom, fromRoots);
215 std::unordered_set<const FunctionDecl*> toRoots;
216 findRoots(functionDeclTo, toRoots);
217
218 for (auto const& from : fromRoots)
219 for (auto const& to : toRoots)
220 callMap.insert({ from, to });
221 }
222
findRoots(const FunctionDecl * functionDecl,std::unordered_set<const FunctionDecl * > & roots)223 void MethodCycles::findRoots(const FunctionDecl* functionDecl,
224 std::unordered_set<const FunctionDecl*>& roots)
225 {
226 bool bCalledSuperMethod = false;
227 if (auto methodDecl = dyn_cast<CXXMethodDecl>(functionDecl))
228 {
229 // For virtual/overriding methods, we need to pretend we called from/to root method(s),
230 // so that they get marked as used.
231 for (auto it = methodDecl->begin_overridden_methods();
232 it != methodDecl->end_overridden_methods(); ++it)
233 {
234 findRoots(*it, roots);
235 bCalledSuperMethod = true;
236 }
237 }
238 if (!bCalledSuperMethod)
239 {
240 while (functionDecl->getTemplateInstantiationPattern())
241 functionDecl = functionDecl->getTemplateInstantiationPattern();
242 if (functionDecl->getLocation().isValid())
243 roots.insert(functionDecl);
244 }
245 }
246
VisitCallExpr(CallExpr * expr)247 bool MethodCycles::VisitCallExpr(CallExpr* expr)
248 {
249 // Note that I don't ignore ANYTHING here, because I want to get calls to my code that result
250 // from template instantiation deep inside the STL and other external code
251
252 FunctionDecl* calleeFunctionDecl = expr->getDirectCallee();
253 if (calleeFunctionDecl == nullptr)
254 {
255 Expr* callee = expr->getCallee()->IgnoreParenImpCasts();
256 DeclRefExpr* dr = dyn_cast<DeclRefExpr>(callee);
257 if (dr)
258 {
259 calleeFunctionDecl = dyn_cast<FunctionDecl>(dr->getDecl());
260 if (calleeFunctionDecl)
261 goto gotfunc;
262 }
263 return true;
264 }
265
266 gotfunc:
267
268 if (currentFunctionDecl != calleeFunctionDecl)
269 // ignore recursive calls
270 logCallToRootMethods(currentFunctionDecl, calleeFunctionDecl);
271
272 return true;
273 }
274
VisitCXXConstructExpr(const CXXConstructExpr * constructExpr)275 bool MethodCycles::VisitCXXConstructExpr(const CXXConstructExpr* constructExpr)
276 {
277 // Note that I don't ignore ANYTHING here, because I want to get calls to my code that result
278 // from template instantiation deep inside the STL and other external code
279
280 const CXXConstructorDecl* constructorDecl = constructExpr->getConstructor();
281 constructorDecl = constructorDecl->getCanonicalDecl();
282
283 if (!constructorDecl->getLocation().isValid())
284 {
285 return true;
286 }
287
288 logCallToRootMethods(currentFunctionDecl, constructorDecl);
289
290 return true;
291 }
292
VisitFunctionDecl(const FunctionDecl * functionDecl)293 bool MethodCycles::VisitFunctionDecl(const FunctionDecl* functionDecl)
294 {
295 const FunctionDecl* canonicalFunctionDecl = functionDecl->getCanonicalDecl();
296 if (functionDecl->isDeleted())
297 return true;
298 // don't care about compiler-generated functions
299 if (functionDecl->isImplicit())
300 return true;
301 if (!canonicalFunctionDecl->getLocation().isValid())
302 return true;
303 // ignore method overrides, since the call will show up as being directed to the root method
304 const CXXMethodDecl* methodDecl = dyn_cast<CXXMethodDecl>(functionDecl);
305 if (methodDecl
306 && (methodDecl->size_overridden_methods() != 0 || methodDecl->hasAttr<OverrideAttr>()))
307 return true;
308 if (!isLocationMine(canonicalFunctionDecl->getLocation()))
309 return true;
310
311 MyFuncInfo funcInfo = niceName(canonicalFunctionDecl);
312 definitionSet.insert(funcInfo);
313 return true;
314 }
315
VisitDeclRefExpr(const DeclRefExpr * declRefExpr)316 bool MethodCycles::VisitDeclRefExpr(const DeclRefExpr* declRefExpr)
317 {
318 const FunctionDecl* functionDecl = dyn_cast<FunctionDecl>(declRefExpr->getDecl());
319 if (!functionDecl)
320 {
321 return true;
322 }
323 logCallToRootMethods(currentFunctionDecl, functionDecl->getCanonicalDecl());
324
325 return true;
326 }
327
TraverseFunctionDecl(FunctionDecl * f)328 bool MethodCycles::TraverseFunctionDecl(FunctionDecl* f)
329 {
330 auto copy = currentFunctionDecl;
331 currentFunctionDecl = f;
332 bool ret = RecursiveASTVisitor::TraverseFunctionDecl(f);
333 currentFunctionDecl = copy;
334 return ret;
335 }
TraverseCXXMethodDecl(CXXMethodDecl * f)336 bool MethodCycles::TraverseCXXMethodDecl(CXXMethodDecl* f)
337 {
338 auto copy = currentFunctionDecl;
339 currentFunctionDecl = f;
340 bool ret = RecursiveASTVisitor::TraverseCXXMethodDecl(f);
341 currentFunctionDecl = copy;
342 return ret;
343 }
TraverseCXXConversionDecl(CXXConversionDecl * f)344 bool MethodCycles::TraverseCXXConversionDecl(CXXConversionDecl* f)
345 {
346 auto copy = currentFunctionDecl;
347 currentFunctionDecl = f;
348 bool ret = RecursiveASTVisitor::TraverseCXXConversionDecl(f);
349 currentFunctionDecl = copy;
350 return ret;
351 }
TraverseCXXDeductionGuideDecl(CXXDeductionGuideDecl * f)352 bool MethodCycles::TraverseCXXDeductionGuideDecl(CXXDeductionGuideDecl* f)
353 {
354 auto copy = currentFunctionDecl;
355 currentFunctionDecl = f;
356 bool ret = RecursiveASTVisitor::TraverseCXXDeductionGuideDecl(f);
357 currentFunctionDecl = copy;
358 return ret;
359 }
TraverseCXXConstructorDecl(CXXConstructorDecl * f)360 bool MethodCycles::TraverseCXXConstructorDecl(CXXConstructorDecl* f)
361 {
362 auto copy = currentFunctionDecl;
363 currentFunctionDecl = f;
364 bool ret = RecursiveASTVisitor::TraverseCXXConstructorDecl(f);
365 currentFunctionDecl = copy;
366 return ret;
367 }
TraverseCXXDestructorDecl(CXXDestructorDecl * f)368 bool MethodCycles::TraverseCXXDestructorDecl(CXXDestructorDecl* f)
369 {
370 auto copy = currentFunctionDecl;
371 currentFunctionDecl = f;
372 bool ret = RecursiveASTVisitor::TraverseCXXDestructorDecl(f);
373 currentFunctionDecl = copy;
374 return ret;
375 }
376
377 loplugin::Plugin::Registration<MethodCycles> X("methodcycles", false);
378 }
379
380 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
381