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