clang-tools-extra/clang-tidy/readability/FunctionCognitiveComplexityCheck.cpp

   1 //===--- FunctionCognitiveComplexityCheck.cpp - clang-tidy ------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "FunctionCognitiveComplexityCheck.h"
  10 #include "../ClangTidyDiagnosticConsumer.h"
  11 #include "clang/AST/Decl.h"
  12 #include "clang/AST/DeclBase.h"
  13 #include "clang/AST/Expr.h"
  14 #include "clang/AST/RecursiveASTVisitor.h"
  15 #include "clang/AST/Stmt.h"
  16 #include "clang/ASTMatchers/ASTMatchFinder.h"
  17 #include "clang/ASTMatchers/ASTMatchers.h"
  18 #include "clang/ASTMatchers/ASTMatchersInternal.h"
  19 #include "clang/Basic/Diagnostic.h"
  20 #include "clang/Basic/DiagnosticIDs.h"
  21 #include "clang/Basic/LLVM.h"
  22 #include "clang/Basic/SourceLocation.h"
  23 #include "llvm/ADT/Optional.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/Support/Casting.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include <array>
  28 #include <cassert>
  29 #include <stack>
  30 #include <tuple>
  31 #include <type_traits>
  32 #include <utility>
  33
  34 using namespace clang::ast_matchers;
  35
  36 namespace clang {
  37 namespace tidy {
  38 namespace readability {
  39 namespace {
  40
  41 struct CognitiveComplexity final {
  42   // Any increment is based on some combination of reasons.
  43   // For details you can look at the Specification at
  44   // https://www.sonarsource.com/docs/CognitiveComplexity.pdf
  45   // or user-facing docs at
  46   // http://clang.llvm.org/extra/clang-tidy/checks/readability-function-cognitive-complexity.html
  47   // Here are all the possible reasons:
  48   enum Criteria : uint8_t {
  49     None = 0U,
  50
  51     // B1, increases cognitive complexity (by 1)
  52     // What causes it:
  53     // * if, else if, else, ConditionalOperator (not BinaryConditionalOperator)
  54     // * SwitchStmt
  55     // * ForStmt, CXXForRangeStmt
  56     // * WhileStmt, DoStmt
  57     // * CXXCatchStmt
  58     // * GotoStmt, IndirectGotoStmt (but not BreakStmt, ContinueStmt)
  59     // * sequences of binary logical operators (BinOpLAnd, BinOpLOr)
  60     // * each method in a recursion cycle (not implemented)
  61     Increment = 1U << 0,
  62
  63     // B2, increases current nesting level (by 1)
  64     // What causes it:
  65     // * if, else if, else, ConditionalOperator (not BinaryConditionalOperator)
  66     // * SwitchStmt
  67     // * ForStmt, CXXForRangeStmt
  68     // * WhileStmt, DoStmt
  69     // * CXXCatchStmt
  70     // * nested CXXConstructor, CXXDestructor, CXXMethod (incl. C++11 Lambda)
  71     // * GNU Statement Expression
  72     // * Apple Block declaration
  73     IncrementNesting = 1U << 1,
  74
  75     // B3, increases cognitive complexity by the current nesting level
  76     // Applied before IncrementNesting
  77     // What causes it:
  78     // * IfStmt, ConditionalOperator (not BinaryConditionalOperator)
  79     // * SwitchStmt
  80     // * ForStmt, CXXForRangeStmt
  81     // * WhileStmt, DoStmt
  82     // * CXXCatchStmt
  83     PenalizeNesting = 1U << 2,
  84
  85     All = Increment | PenalizeNesting | IncrementNesting,
  86   };
  87
  88   // The helper struct used to record one increment occurrence, with all the
  89   // details nessesary.
  90   struct Detail {
  91     const SourceLocation Loc;     // What caused the increment?
  92     const unsigned short Nesting; // How deeply nested is Loc located?
  93     const Criteria C;             // The criteria of the increment
  94
  95     Detail(SourceLocation SLoc, unsigned short CurrentNesting, Criteria Crit)
  96         : Loc(SLoc), Nesting(CurrentNesting), C(Crit) {}
  97
  98     // To minimize the sizeof(Detail), we only store the minimal info there.
  99     // This function is used to convert from the stored info into the usable
 100     // information - what message to output, how much of an increment did this
 101     // occurrence actually result in.
 102     std::pair<unsigned, unsigned short> process() const {
 103       assert(C != Criteria::None && "invalid criteria");
 104
 105       unsigned MsgId;           // The id of the message to output.
 106       unsigned short Increment; // How much of an increment?
 107
 108       if (C == Criteria::All) {
 109         Increment = 1 + Nesting;
 110         MsgId = 0;
 111       } else if (C == (Criteria::Increment | Criteria::IncrementNesting)) {
 112         Increment = 1;
 113         MsgId = 1;
 114       } else if (C == Criteria::Increment) {
 115         Increment = 1;
 116         MsgId = 2;
 117       } else if (C == Criteria::IncrementNesting) {
 118         Increment = 0; // Unused in this message.
 119         MsgId = 3;
 120       } else
 121         llvm_unreachable("should not get to here.");
 122
 123       return std::make_pair(MsgId, Increment);
 124     }
 125   };
 126
 127   // Limit of 25 is the "upstream"'s default.
 128   static constexpr unsigned DefaultLimit = 25U;
 129
 130   // Based on the publicly-avaliable numbers for some big open-source projects
 131   // https://sonarcloud.io/projects?languages=c%2Ccpp&size=5   we can estimate:
 132   // value ~20 would result in no allocs for 98% of functions, ~12 for 96%, ~10
 133   // for 91%, ~8 for 88%, ~6 for 84%, ~4 for 77%, ~2 for 64%, and ~1 for 37%.
 134   static_assert(sizeof(Detail) <= 8,
 135                 "Since we use SmallVector to minimize the amount of "
 136                 "allocations, we also need to consider the price we pay for "
 137                 "that in terms of stack usage. "
 138                 "Thus, it is good to minimize the size of the Detail struct.");
 139   SmallVector<Detail, DefaultLimit> Details; // 25 elements is 200 bytes.
 140   // Yes, 25 is a magic number. This is the seemingly-sane default for the
 141   // upper limit for function cognitive complexity. Thus it would make sense
 142   // to avoid allocations for any function that does not violate the limit.
 143
 144   // The grand total Cognitive Complexity of the function.
 145   unsigned Total = 0;
 146
 147   // The function used to store new increment, calculate the total complexity.
 148   void account(SourceLocation Loc, unsigned short Nesting, Criteria C);
 149 };
 150
 151 // All the possible messages that can be output. The choice of the message
 152 // to use is based of the combination of the CognitiveComplexity::Criteria.
 153 // It would be nice to have it in CognitiveComplexity struct, but then it is
 154 // not static.
 155 static const std::array<const StringRef, 4> Msgs = {{
 156     // B1 + B2 + B3
 157     "+%0, including nesting penalty of %1, nesting level increased to %2",
 158
 159     // B1 + B2
 160     "+%0, nesting level increased to %2",
 161
 162     // B1
 163     "+%0",
 164
 165     // B2
 166     "nesting level increased to %2",
 167 }};
 168
 169 // Criteria is a bitset, thus a few helpers are needed.
 170 CognitiveComplexity::Criteria operator|(CognitiveComplexity::Criteria LHS,
 171                                         CognitiveComplexity::Criteria RHS) {
 172   return static_cast<CognitiveComplexity::Criteria>(
 173       static_cast<std::underlying_type<CognitiveComplexity::Criteria>::type>(
 174           LHS) |
 175       static_cast<std::underlying_type<CognitiveComplexity::Criteria>::type>(
 176           RHS));
 177 }
 178 CognitiveComplexity::Criteria operator&(CognitiveComplexity::Criteria LHS,
 179                                         CognitiveComplexity::Criteria RHS) {
 180   return static_cast<CognitiveComplexity::Criteria>(
 181       static_cast<std::underlying_type<CognitiveComplexity::Criteria>::type>(
 182           LHS) &
 183       static_cast<std::underlying_type<CognitiveComplexity::Criteria>::type>(
 184           RHS));
 185 }
 186 CognitiveComplexity::Criteria &operator|=(CognitiveComplexity::Criteria &LHS,
 187                                           CognitiveComplexity::Criteria RHS) {
 188   LHS = operator|(LHS, RHS);
 189   return LHS;
 190 }
 191 CognitiveComplexity::Criteria &operator&=(CognitiveComplexity::Criteria &LHS,
 192                                           CognitiveComplexity::Criteria RHS) {
 193   LHS = operator&(LHS, RHS);
 194   return LHS;
 195 }
 196
 197 void CognitiveComplexity::account(SourceLocation Loc, unsigned short Nesting,
 198                                   Criteria C) {
 199   C &= Criteria::All;
 200   assert(C != Criteria::None && "invalid criteria");
 201
 202   Details.emplace_back(Loc, Nesting, C);
 203   const Detail &D = Details.back();
 204
 205   unsigned MsgId;
 206   unsigned short Increase;
 207   std::tie(MsgId, Increase) = D.process();
 208
 209   Total += Increase;
 210 }
 211
 212 class FunctionASTVisitor final
 213     : public RecursiveASTVisitor<FunctionASTVisitor> {
 214   using Base = RecursiveASTVisitor<FunctionASTVisitor>;
 215
 216   // The current nesting level (increased by Criteria::IncrementNesting).
 217   unsigned short CurrentNestingLevel = 0;
 218
 219   // Used to efficiently know the last type of the binary sequence operator
 220   // that was encountered. It would make sense for the function call to start
 221   // the new sequence, thus it is a stack.
 222   using OBO = Optional<BinaryOperator::Opcode>;
 223   std::stack<OBO, SmallVector<OBO, 4>> BinaryOperatorsStack;
 224
 225 public:
 226   bool TraverseStmtWithIncreasedNestingLevel(Stmt *Node) {
 227     ++CurrentNestingLevel;
 228     bool ShouldContinue = Base::TraverseStmt(Node);
 229     --CurrentNestingLevel;
 230     return ShouldContinue;
 231   }
 232
 233   bool TraverseDeclWithIncreasedNestingLevel(Decl *Node) {
 234     ++CurrentNestingLevel;
 235     bool ShouldContinue = Base::TraverseDecl(Node);
 236     --CurrentNestingLevel;
 237     return ShouldContinue;
 238   }
 239
 240   bool TraverseIfStmt(IfStmt *Node, bool InElseIf = false) {
 241     if (!Node)
 242       return Base::TraverseIfStmt(Node);
 243
 244     {
 245       CognitiveComplexity::Criteria Reasons;
 246
 247       Reasons = CognitiveComplexity::Criteria::None;
 248
 249       // "If" increases cognitive complexity.
 250       Reasons |= CognitiveComplexity::Criteria::Increment;
 251       // "If" increases nesting level.
 252       Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
 253
 254       if (!InElseIf) {
 255         // "If" receives a nesting increment commensurate with it's nested
 256         // depth, if it is not part of "else if".
 257         Reasons |= CognitiveComplexity::Criteria::PenalizeNesting;
 258       }
 259
 260       CC.account(Node->getIfLoc(), CurrentNestingLevel, Reasons);
 261     }
 262
 263     // If this IfStmt is *NOT* "else if", then only the body (i.e. "Then" and
 264     // "Else") is traversed with increased Nesting level.
 265     // However if this IfStmt *IS* "else if", then Nesting level is increased
 266     // for the whole IfStmt (i.e. for "Init", "Cond", "Then" and "Else").
 267
 268     if (!InElseIf) {
 269       if (!TraverseStmt(Node->getInit()))
 270         return false;
 271
 272       if (!TraverseStmt(Node->getCond()))
 273         return false;
 274     } else {
 275       if (!TraverseStmtWithIncreasedNestingLevel(Node->getInit()))
 276         return false;
 277
 278       if (!TraverseStmtWithIncreasedNestingLevel(Node->getCond()))
 279         return false;
 280     }
 281
 282     // "Then" always increases nesting level.
 283     if (!TraverseStmtWithIncreasedNestingLevel(Node->getThen()))
 284       return false;
 285
 286     if (!Node->getElse())
 287       return true;
 288
 289     if (auto *E = dyn_cast<IfStmt>(Node->getElse()))
 290       return TraverseIfStmt(E, true);
 291
 292     {
 293       CognitiveComplexity::Criteria Reasons;
 294
 295       Reasons = CognitiveComplexity::Criteria::None;
 296
 297       // "Else" increases cognitive complexity.
 298       Reasons |= CognitiveComplexity::Criteria::Increment;
 299       // "Else" increases nesting level.
 300       Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
 301       // "Else" DOES NOT receive a nesting increment commensurate with it's
 302       // nested depth.
 303
 304       CC.account(Node->getElseLoc(), CurrentNestingLevel, Reasons);
 305     }
 306
 307     // "Else" always increases nesting level.
 308     return TraverseStmtWithIncreasedNestingLevel(Node->getElse());
 309   }
 310
 311 // The currently-being-processed stack entry, which is always the top.
 312 #define CurrentBinaryOperator BinaryOperatorsStack.top()
 313
 314   // In a sequence of binary logical operators, if the new operator is different
 315   // from the previous one, then the cognitive complexity is increased.
 316   bool TraverseBinaryOperator(BinaryOperator *Op) {
 317     if (!Op || !Op->isLogicalOp())
 318       return Base::TraverseBinaryOperator(Op);
 319
 320     // Make sure that there is always at least one frame in the stack.
 321     if (BinaryOperatorsStack.empty())
 322       BinaryOperatorsStack.emplace();
 323
 324     // If this is the first binary operator that we are processing, or the
 325     // previous binary operator was different, there is an increment.
 326     if (!CurrentBinaryOperator || Op->getOpcode() != CurrentBinaryOperator)
 327       CC.account(Op->getOperatorLoc(), CurrentNestingLevel,
 328                  CognitiveComplexity::Criteria::Increment);
 329
 330     // We might encounter a function call, which starts a new sequence, thus
 331     // we need to save the current previous binary operator.
 332     const Optional<BinaryOperator::Opcode> BinOpCopy(CurrentBinaryOperator);
 333
 334     // Record the operator that we are currently processing and traverse it.
 335     CurrentBinaryOperator = Op->getOpcode();
 336     bool ShouldContinue = Base::TraverseBinaryOperator(Op);
 337
 338     // And restore the previous binary operator, which might be nonexistent.
 339     CurrentBinaryOperator = BinOpCopy;
 340
 341     return ShouldContinue;
 342   }
 343
 344   // It would make sense for the function call to start the new binary
 345   // operator sequence, thus let's make sure that it creates a new stack frame.
 346   bool TraverseCallExpr(CallExpr *Node) {
 347     // If we are not currently processing any binary operator sequence, then
 348     // no Node-handling is needed.
 349     if (!Node || BinaryOperatorsStack.empty() || !CurrentBinaryOperator)
 350       return Base::TraverseCallExpr(Node);
 351
 352     // Else, do add [uninitialized] frame to the stack, and traverse call.
 353     BinaryOperatorsStack.emplace();
 354     bool ShouldContinue = Base::TraverseCallExpr(Node);
 355     // And remove the top frame.
 356     BinaryOperatorsStack.pop();
 357
 358     return ShouldContinue;
 359   }
 360
 361 #undef CurrentBinaryOperator
 362
 363   bool TraverseStmt(Stmt *Node) {
 364     if (!Node)
 365       return Base::TraverseStmt(Node);
 366
 367     // Three following switch()'es have huge duplication, but it is better to
 368     // keep them separate, to simplify comparing them with the Specification.
 369
 370     CognitiveComplexity::Criteria Reasons = CognitiveComplexity::Criteria::None;
 371     SourceLocation Location = Node->getBeginLoc();
 372
 373     // B1. Increments
 374     // There is an increment for each of the following:
 375     switch (Node->getStmtClass()) {
 376     // if, else if, else are handled in TraverseIfStmt(),
 377     // FIXME: "each method in a recursion cycle" Increment is not implemented.
 378     case Stmt::ConditionalOperatorClass:
 379     case Stmt::SwitchStmtClass:
 380     case Stmt::ForStmtClass:
 381     case Stmt::CXXForRangeStmtClass:
 382     case Stmt::WhileStmtClass:
 383     case Stmt::DoStmtClass:
 384     case Stmt::CXXCatchStmtClass:
 385     case Stmt::GotoStmtClass:
 386     case Stmt::IndirectGotoStmtClass:
 387       Reasons |= CognitiveComplexity::Criteria::Increment;
 388       break;
 389     default:
 390       // break LABEL, continue LABEL increase cognitive complexity,
 391       // but they are not supported in C++ or C.
 392       // Regular break/continue do not increase cognitive complexity.
 393       break;
 394     }
 395
 396     // B2. Nesting level
 397     // The following structures increment the nesting level:
 398     switch (Node->getStmtClass()) {
 399     // if, else if, else are handled in TraverseIfStmt(),
 400     // Nested methods and such are handled in TraverseDecl.
 401     case Stmt::ConditionalOperatorClass:
 402     case Stmt::SwitchStmtClass:
 403     case Stmt::ForStmtClass:
 404     case Stmt::CXXForRangeStmtClass:
 405     case Stmt::WhileStmtClass:
 406     case Stmt::DoStmtClass:
 407     case Stmt::CXXCatchStmtClass:
 408     case Stmt::LambdaExprClass:
 409     case Stmt::StmtExprClass:
 410       Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
 411       break;
 412     default:
 413       break;
 414     }
 415
 416     // B3. Nesting increments
 417     // The following structures receive a nesting increment
 418     // commensurate with their nested depth inside B2 structures:
 419     switch (Node->getStmtClass()) {
 420     // if, else if, else are handled in TraverseIfStmt().
 421     case Stmt::ConditionalOperatorClass:
 422     case Stmt::SwitchStmtClass:
 423     case Stmt::ForStmtClass:
 424     case Stmt::CXXForRangeStmtClass:
 425     case Stmt::WhileStmtClass:
 426     case Stmt::DoStmtClass:
 427     case Stmt::CXXCatchStmtClass:
 428       Reasons |= CognitiveComplexity::Criteria::PenalizeNesting;
 429       break;
 430     default:
 431       break;
 432     }
 433
 434     if (Node->getStmtClass() == Stmt::ConditionalOperatorClass) {
 435       // A little beautification.
 436       // For conditional operator "cond ? true : false" point at the "?"
 437       // symbol.
 438       ConditionalOperator *COp = dyn_cast<ConditionalOperator>(Node);
 439       Location = COp->getQuestionLoc();
 440     }
 441
 442     // If we have found any reasons, let's account it.
 443     if (Reasons & CognitiveComplexity::Criteria::All)
 444       CC.account(Location, CurrentNestingLevel, Reasons);
 445
 446     // Did we decide that the nesting level should be increased?
 447     if (!(Reasons & CognitiveComplexity::Criteria::IncrementNesting))
 448       return Base::TraverseStmt(Node);
 449
 450     return TraverseStmtWithIncreasedNestingLevel(Node);
 451   }
 452
 453   // The parameter MainAnalyzedFunction is needed to differentiate between the
 454   // cases where TraverseDecl() is the entry point from
 455   // FunctionCognitiveComplexityCheck::check() and the cases where it was called
 456   // from the FunctionASTVisitor itself. Explanation: if we get a function
 457   // definition (e.g. constructor, destructor, method), the Cognitive Complexity
 458   // specification states that the Nesting level shall be increased. But if this
 459   // function is the entry point, then the Nesting level should not be
 460   // increased. Thus that parameter is there and is used to fall-through
 461   // directly to traversing if this is the main function that is being analyzed.
 462   bool TraverseDecl(Decl *Node, bool MainAnalyzedFunction = false) {
 463     if (!Node || MainAnalyzedFunction)
 464       return Base::TraverseDecl(Node);
 465
 466     // B2. Nesting level
 467     // The following structures increment the nesting level:
 468     switch (Node->getKind()) {
 469     case Decl::Function:
 470     case Decl::CXXMethod:
 471     case Decl::CXXConstructor:
 472     case Decl::CXXDestructor:
 473     case Decl::Block:
 474       break;
 475     default:
 476       // If this is something else, we use early return!
 477       return Base::TraverseDecl(Node);
 478       break;
 479     }
 480
 481     CC.account(Node->getBeginLoc(), CurrentNestingLevel,
 482                CognitiveComplexity::Criteria::IncrementNesting);
 483
 484     return TraverseDeclWithIncreasedNestingLevel(Node);
 485   }
 486
 487   CognitiveComplexity CC;
 488 };
 489
 490 } // namespace
 491
 492 FunctionCognitiveComplexityCheck::FunctionCognitiveComplexityCheck(
 493     StringRef Name, ClangTidyContext *Context)
 494     : ClangTidyCheck(Name, Context),
 495       Threshold(Options.get("Threshold", CognitiveComplexity::DefaultLimit)) {}
 496
 497 void FunctionCognitiveComplexityCheck::storeOptions(
 498     ClangTidyOptions::OptionMap &Opts) {
 499   Options.store(Opts, "Threshold", Threshold);
 500 }
 501
 502 void FunctionCognitiveComplexityCheck::registerMatchers(MatchFinder *Finder) {
 503   Finder->addMatcher(
 504       functionDecl(
 505           allOf(isDefinition(), unless(anyOf(isDefaulted(), isDeleted(),
 506                                              isImplicit(), isInstantiated()))))
 507           .bind("func"),
 508       this);
 509 }
 510
 511 void FunctionCognitiveComplexityCheck::check(
 512     const MatchFinder::MatchResult &Result) {
 513   const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
 514   assert(Func->hasBody() && "The matchers should only match the functions that "
 515                             "have user-provided body.");
 516
 517   FunctionASTVisitor Visitor;
 518   Visitor.TraverseDecl(const_cast<FunctionDecl *>(Func), true);
 519
 520   if (Visitor.CC.Total <= Threshold)
 521     return;
 522
 523   diag(Func->getLocation(),
 524        "function %0 has cognitive complexity of %1 (threshold %2)")
 525       << Func << Visitor.CC.Total << Threshold;
 526
 527   // Output all the basic increments of complexity.
 528   for (const auto &Detail : Visitor.CC.Details) {
 529     unsigned MsgId;          // The id of the message to output.
 530     unsigned short Increase; // How much of an increment?
 531     std::tie(MsgId, Increase) = Detail.process();
 532     assert(MsgId < Msgs.size() && "MsgId should always be valid");
 533     // Increase, on the other hand, can be 0.
 534
 535     diag(Detail.Loc, Msgs[MsgId], DiagnosticIDs::Note)
 536         << (unsigned)Increase << (unsigned)Detail.Nesting << 1 + Detail.Nesting;
 537   }
 538 }
 539
 540 } // namespace readability
 541 } // namespace tidy
 542 } // namespace clang