compilerplugins/clang/methodcycles.cxx

   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 };
  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:
  67     explicit MethodCycles(loplugin::InstantiationData const& data)
  68         : Plugin(data)
  69     {
  70     }
  71
  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 std::pair<const FunctionDecl*, const FunctionDecl*>& 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
  99     bool shouldVisitTemplateInstantiations() const { return true; }
 100     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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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 }
 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 }
 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 }
 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 }
 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 }
 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: */