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