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 "config_clang.h"
  21
  22 #include "plugin.hxx"
  23
  24 /**
  25 What we are looking for here are methods that are not reachable from any of the program
  26 entry points.
  27 "Entry points" includes main, and various binary API
  28
  29 Mostly that means we end up finding cycles of methods i.e. methods that refer to each
  30 other, but are not reachable.
  31
  32 It does so, by dumping various call/definition info to a log file.
  33 Be warned that it produces around 20G of log file.
  34
  35 Then we will post-process the log file with a python script, which takes about
  36 15min to run on a fast machine.
  37
  38 The process goes something like this:
  39   $ make check
  40   $ make FORCE_COMPILE=all COMPILER_PLUGIN_TOOL='methodcycles' check
  41   $ ./compilerplugins/clang/methodcycles.py
  42
  43 Note that the actual process may involve a fair amount of undoing, hand editing, and general messing around
  44 to get it to work :-)
  45
  46 */
  47
  48 namespace
  49 {
  50 struct MyFuncInfo
  51 {
  52     std::string returnType;
  53     std::string nameAndParams;
  54     std::string sourceLocation;
  55 };
  56 bool operator<(const MyFuncInfo& lhs, const MyFuncInfo& rhs)
  57 {
  58     return std::tie(lhs.returnType, lhs.nameAndParams)
  59            < std::tie(rhs.returnType, rhs.nameAndParams);
  60 }
  61
  62 // try to limit the voluminous output a little
  63 static std::multimap<const FunctionDecl*, const FunctionDecl*> callMap;
  64 static std::set<MyFuncInfo> definitionSet;
  65
  66 class MethodCycles : public RecursiveASTVisitor<MethodCycles>, public loplugin::Plugin
  67 {
  68 public:
  69     explicit MethodCycles(loplugin::InstantiationData const& data)
  70         : Plugin(data)
  71     {
  72     }
  73
  74     virtual void run() override
  75     {
  76         handler.enableTreeWideAnalysisMode();
  77
  78         TraverseDecl(compiler.getASTContext().getTranslationUnitDecl());
  79
  80         // dump all our output in one write call - this is to try and limit IO "crosstalk" between multiple processes
  81         // writing to the same logfile
  82
  83         std::string output;
  84         for (const MyFuncInfo& s : definitionSet)
  85             output += "definition:\t" + s.returnType + "\t" + s.nameAndParams + "\t"
  86                       + s.sourceLocation + "\n";
  87         for (const auto& pair : callMap)
  88         {
  89             if (!isLocationMine(pair.first->getLocation())
  90                 || !isLocationMine(pair.second->getLocation()))
  91                 continue;
  92             auto niceNameFrom = niceName(pair.first);
  93             auto niceNameTo = niceName(pair.second);
  94             output += "call:\t" + niceNameFrom.returnType + "\t" + niceNameFrom.nameAndParams + "\t"
  95                       + niceNameTo.returnType + "\t" + niceNameTo.nameAndParams + "\n";
  96         }
  97         std::ofstream myfile;
  98         myfile.open(WORKDIR "/loplugin.methodcycles.log", std::ios::app | std::ios::out);
  99         myfile << output;
 100         myfile.close();
 101     }
 102
 103     bool shouldVisitTemplateInstantiations() const { return true; }
 104     bool shouldVisitImplicitCode() const { return true; }
 105
 106     bool VisitCallExpr(CallExpr*);
 107     bool VisitFunctionDecl(const FunctionDecl* decl);
 108     bool VisitDeclRefExpr(const DeclRefExpr*);
 109     bool VisitCXXConstructExpr(const CXXConstructExpr*);
 110
 111     bool TraverseFunctionDecl(FunctionDecl*);
 112     bool TraverseCXXMethodDecl(CXXMethodDecl*);
 113     bool TraverseCXXConstructorDecl(CXXConstructorDecl*);
 114     bool TraverseCXXConversionDecl(CXXConversionDecl*);
 115     bool TraverseCXXDestructorDecl(CXXDestructorDecl*);
 116     bool TraverseCXXDeductionGuideDecl(CXXDeductionGuideDecl*);
 117
 118 private:
 119     void logCallToRootMethods(const FunctionDecl* functionDeclFrom,
 120                               const FunctionDecl* functionDeclTo);
 121     void findRoots(const FunctionDecl* functionDecl,
 122                    std::unordered_set<const FunctionDecl*>& roots);
 123     MyFuncInfo niceName(const FunctionDecl* functionDecl);
 124     bool isLocationMine(SourceLocation loc);
 125     std::string toString(SourceLocation loc);
 126     FunctionDecl const* currentFunctionDecl = nullptr;
 127 };
 128
 129 MyFuncInfo MethodCycles::niceName(const FunctionDecl* functionDecl)
 130 {
 131     if (functionDecl->getInstantiatedFromMemberFunction())
 132         functionDecl = functionDecl->getInstantiatedFromMemberFunction();
 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: */