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
Detailclang::tidy::readability::__anon45a8878b0111::CognitiveComplexity::Detail95 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.
processclang::tidy::readability::__anon45a8878b0111::CognitiveComplexity::Detail102 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.
operator |(CognitiveComplexity::Criteria LHS,CognitiveComplexity::Criteria RHS)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 }
operator &(CognitiveComplexity::Criteria LHS,CognitiveComplexity::Criteria RHS)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 }
operator |=(CognitiveComplexity::Criteria & LHS,CognitiveComplexity::Criteria RHS)186 CognitiveComplexity::Criteria &operator|=(CognitiveComplexity::Criteria &LHS,
187 CognitiveComplexity::Criteria RHS) {
188 LHS = operator|(LHS, RHS);
189 return LHS;
190 }
operator &=(CognitiveComplexity::Criteria & LHS,CognitiveComplexity::Criteria RHS)191 CognitiveComplexity::Criteria &operator&=(CognitiveComplexity::Criteria &LHS,
192 CognitiveComplexity::Criteria RHS) {
193 LHS = operator&(LHS, RHS);
194 return LHS;
195 }
196
account(SourceLocation Loc,unsigned short Nesting,Criteria C)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 // If set to true, macros are ignored during analysis.
217 const bool IgnoreMacros;
218
219 // The current nesting level (increased by Criteria::IncrementNesting).
220 unsigned short CurrentNestingLevel = 0;
221
222 // Used to efficiently know the last type of the binary sequence operator
223 // that was encountered. It would make sense for the function call to start
224 // the new sequence, thus it is a stack.
225 using OBO = Optional<BinaryOperator::Opcode>;
226 std::stack<OBO, SmallVector<OBO, 4>> BinaryOperatorsStack;
227
228 public:
FunctionASTVisitor(const bool IgnoreMacros)229 explicit FunctionASTVisitor(const bool IgnoreMacros)
230 : IgnoreMacros(IgnoreMacros) {}
231
traverseStmtWithIncreasedNestingLevel(Stmt * Node)232 bool traverseStmtWithIncreasedNestingLevel(Stmt *Node) {
233 ++CurrentNestingLevel;
234 bool ShouldContinue = Base::TraverseStmt(Node);
235 --CurrentNestingLevel;
236 return ShouldContinue;
237 }
238
traverseDeclWithIncreasedNestingLevel(Decl * Node)239 bool traverseDeclWithIncreasedNestingLevel(Decl *Node) {
240 ++CurrentNestingLevel;
241 bool ShouldContinue = Base::TraverseDecl(Node);
242 --CurrentNestingLevel;
243 return ShouldContinue;
244 }
245
TraverseIfStmt(IfStmt * Node,bool InElseIf=false)246 bool TraverseIfStmt(IfStmt *Node, bool InElseIf = false) {
247 if (!Node)
248 return Base::TraverseIfStmt(Node);
249
250 {
251 CognitiveComplexity::Criteria Reasons;
252
253 Reasons = CognitiveComplexity::Criteria::None;
254
255 // "If" increases cognitive complexity.
256 Reasons |= CognitiveComplexity::Criteria::Increment;
257 // "If" increases nesting level.
258 Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
259
260 if (!InElseIf) {
261 // "If" receives a nesting increment commensurate with it's nested
262 // depth, if it is not part of "else if".
263 Reasons |= CognitiveComplexity::Criteria::PenalizeNesting;
264 }
265
266 CC.account(Node->getIfLoc(), CurrentNestingLevel, Reasons);
267 }
268
269 // If this IfStmt is *NOT* "else if", then only the body (i.e. "Then" and
270 // "Else") is traversed with increased Nesting level.
271 // However if this IfStmt *IS* "else if", then Nesting level is increased
272 // for the whole IfStmt (i.e. for "Init", "Cond", "Then" and "Else").
273
274 if (!InElseIf) {
275 if (!TraverseStmt(Node->getInit()))
276 return false;
277
278 if (!TraverseStmt(Node->getCond()))
279 return false;
280 } else {
281 if (!traverseStmtWithIncreasedNestingLevel(Node->getInit()))
282 return false;
283
284 if (!traverseStmtWithIncreasedNestingLevel(Node->getCond()))
285 return false;
286 }
287
288 // "Then" always increases nesting level.
289 if (!traverseStmtWithIncreasedNestingLevel(Node->getThen()))
290 return false;
291
292 if (!Node->getElse())
293 return true;
294
295 if (auto *E = dyn_cast<IfStmt>(Node->getElse()))
296 return TraverseIfStmt(E, true);
297
298 {
299 CognitiveComplexity::Criteria Reasons;
300
301 Reasons = CognitiveComplexity::Criteria::None;
302
303 // "Else" increases cognitive complexity.
304 Reasons |= CognitiveComplexity::Criteria::Increment;
305 // "Else" increases nesting level.
306 Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
307 // "Else" DOES NOT receive a nesting increment commensurate with it's
308 // nested depth.
309
310 CC.account(Node->getElseLoc(), CurrentNestingLevel, Reasons);
311 }
312
313 // "Else" always increases nesting level.
314 return traverseStmtWithIncreasedNestingLevel(Node->getElse());
315 }
316
317 // The currently-being-processed stack entry, which is always the top.
318 #define CurrentBinaryOperator BinaryOperatorsStack.top()
319
320 // In a sequence of binary logical operators, if the new operator is different
321 // from the previous one, then the cognitive complexity is increased.
TraverseBinaryOperator(BinaryOperator * Op)322 bool TraverseBinaryOperator(BinaryOperator *Op) {
323 if (!Op || !Op->isLogicalOp())
324 return Base::TraverseBinaryOperator(Op);
325
326 // Make sure that there is always at least one frame in the stack.
327 if (BinaryOperatorsStack.empty())
328 BinaryOperatorsStack.emplace();
329
330 // If this is the first binary operator that we are processing, or the
331 // previous binary operator was different, there is an increment.
332 if (!CurrentBinaryOperator || Op->getOpcode() != CurrentBinaryOperator)
333 CC.account(Op->getOperatorLoc(), CurrentNestingLevel,
334 CognitiveComplexity::Criteria::Increment);
335
336 // We might encounter a function call, which starts a new sequence, thus
337 // we need to save the current previous binary operator.
338 const Optional<BinaryOperator::Opcode> BinOpCopy(CurrentBinaryOperator);
339
340 // Record the operator that we are currently processing and traverse it.
341 CurrentBinaryOperator = Op->getOpcode();
342 bool ShouldContinue = Base::TraverseBinaryOperator(Op);
343
344 // And restore the previous binary operator, which might be nonexistent.
345 CurrentBinaryOperator = BinOpCopy;
346
347 return ShouldContinue;
348 }
349
350 // It would make sense for the function call to start the new binary
351 // operator sequence, thus let's make sure that it creates a new stack frame.
TraverseCallExpr(CallExpr * Node)352 bool TraverseCallExpr(CallExpr *Node) {
353 // If we are not currently processing any binary operator sequence, then
354 // no Node-handling is needed.
355 if (!Node || BinaryOperatorsStack.empty() || !CurrentBinaryOperator)
356 return Base::TraverseCallExpr(Node);
357
358 // Else, do add [uninitialized] frame to the stack, and traverse call.
359 BinaryOperatorsStack.emplace();
360 bool ShouldContinue = Base::TraverseCallExpr(Node);
361 // And remove the top frame.
362 BinaryOperatorsStack.pop();
363
364 return ShouldContinue;
365 }
366
367 #undef CurrentBinaryOperator
368
TraverseStmt(Stmt * Node)369 bool TraverseStmt(Stmt *Node) {
370 if (!Node)
371 return Base::TraverseStmt(Node);
372
373 if (IgnoreMacros && Node->getBeginLoc().isMacroID())
374 return true;
375
376 // Three following switch()'es have huge duplication, but it is better to
377 // keep them separate, to simplify comparing them with the Specification.
378
379 CognitiveComplexity::Criteria Reasons = CognitiveComplexity::Criteria::None;
380 SourceLocation Location = Node->getBeginLoc();
381
382 // B1. Increments
383 // There is an increment for each of the following:
384 switch (Node->getStmtClass()) {
385 // if, else if, else are handled in TraverseIfStmt(),
386 // FIXME: "each method in a recursion cycle" Increment is not implemented.
387 case Stmt::ConditionalOperatorClass:
388 case Stmt::SwitchStmtClass:
389 case Stmt::ForStmtClass:
390 case Stmt::CXXForRangeStmtClass:
391 case Stmt::WhileStmtClass:
392 case Stmt::DoStmtClass:
393 case Stmt::CXXCatchStmtClass:
394 case Stmt::GotoStmtClass:
395 case Stmt::IndirectGotoStmtClass:
396 Reasons |= CognitiveComplexity::Criteria::Increment;
397 break;
398 default:
399 // break LABEL, continue LABEL increase cognitive complexity,
400 // but they are not supported in C++ or C.
401 // Regular break/continue do not increase cognitive complexity.
402 break;
403 }
404
405 // B2. Nesting level
406 // The following structures increment the nesting level:
407 switch (Node->getStmtClass()) {
408 // if, else if, else are handled in TraverseIfStmt(),
409 // Nested methods and such are handled in TraverseDecl.
410 case Stmt::ConditionalOperatorClass:
411 case Stmt::SwitchStmtClass:
412 case Stmt::ForStmtClass:
413 case Stmt::CXXForRangeStmtClass:
414 case Stmt::WhileStmtClass:
415 case Stmt::DoStmtClass:
416 case Stmt::CXXCatchStmtClass:
417 case Stmt::LambdaExprClass:
418 case Stmt::StmtExprClass:
419 Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
420 break;
421 default:
422 break;
423 }
424
425 // B3. Nesting increments
426 // The following structures receive a nesting increment
427 // commensurate with their nested depth inside B2 structures:
428 switch (Node->getStmtClass()) {
429 // if, else if, else are handled in TraverseIfStmt().
430 case Stmt::ConditionalOperatorClass:
431 case Stmt::SwitchStmtClass:
432 case Stmt::ForStmtClass:
433 case Stmt::CXXForRangeStmtClass:
434 case Stmt::WhileStmtClass:
435 case Stmt::DoStmtClass:
436 case Stmt::CXXCatchStmtClass:
437 Reasons |= CognitiveComplexity::Criteria::PenalizeNesting;
438 break;
439 default:
440 break;
441 }
442
443 if (Node->getStmtClass() == Stmt::ConditionalOperatorClass) {
444 // A little beautification.
445 // For conditional operator "cond ? true : false" point at the "?"
446 // symbol.
447 ConditionalOperator *COp = dyn_cast<ConditionalOperator>(Node);
448 Location = COp->getQuestionLoc();
449 }
450
451 // If we have found any reasons, let's account it.
452 if (Reasons & CognitiveComplexity::Criteria::All)
453 CC.account(Location, CurrentNestingLevel, Reasons);
454
455 // Did we decide that the nesting level should be increased?
456 if (!(Reasons & CognitiveComplexity::Criteria::IncrementNesting))
457 return Base::TraverseStmt(Node);
458
459 return traverseStmtWithIncreasedNestingLevel(Node);
460 }
461
462 // The parameter MainAnalyzedFunction is needed to differentiate between the
463 // cases where TraverseDecl() is the entry point from
464 // FunctionCognitiveComplexityCheck::check() and the cases where it was called
465 // from the FunctionASTVisitor itself. Explanation: if we get a function
466 // definition (e.g. constructor, destructor, method), the Cognitive Complexity
467 // specification states that the Nesting level shall be increased. But if this
468 // function is the entry point, then the Nesting level should not be
469 // increased. Thus that parameter is there and is used to fall-through
470 // directly to traversing if this is the main function that is being analyzed.
TraverseDecl(Decl * Node,bool MainAnalyzedFunction=false)471 bool TraverseDecl(Decl *Node, bool MainAnalyzedFunction = false) {
472 if (!Node || MainAnalyzedFunction)
473 return Base::TraverseDecl(Node);
474
475 // B2. Nesting level
476 // The following structures increment the nesting level:
477 switch (Node->getKind()) {
478 case Decl::Function:
479 case Decl::CXXMethod:
480 case Decl::CXXConstructor:
481 case Decl::CXXDestructor:
482 case Decl::Block:
483 break;
484 default:
485 // If this is something else, we use early return!
486 return Base::TraverseDecl(Node);
487 break;
488 }
489
490 CC.account(Node->getBeginLoc(), CurrentNestingLevel,
491 CognitiveComplexity::Criteria::IncrementNesting);
492
493 return traverseDeclWithIncreasedNestingLevel(Node);
494 }
495
496 CognitiveComplexity CC;
497 };
498
499 } // namespace
500
FunctionCognitiveComplexityCheck(StringRef Name,ClangTidyContext * Context)501 FunctionCognitiveComplexityCheck::FunctionCognitiveComplexityCheck(
502 StringRef Name, ClangTidyContext *Context)
503 : ClangTidyCheck(Name, Context),
504 Threshold(Options.get("Threshold", CognitiveComplexity::DefaultLimit)),
505 DescribeBasicIncrements(Options.get("DescribeBasicIncrements", true)),
506 IgnoreMacros(Options.get("IgnoreMacros", false)) {}
507
storeOptions(ClangTidyOptions::OptionMap & Opts)508 void FunctionCognitiveComplexityCheck::storeOptions(
509 ClangTidyOptions::OptionMap &Opts) {
510 Options.store(Opts, "Threshold", Threshold);
511 Options.store(Opts, "DescribeBasicIncrements", DescribeBasicIncrements);
512 Options.store(Opts, "IgnoreMacros", IgnoreMacros);
513 }
514
registerMatchers(MatchFinder * Finder)515 void FunctionCognitiveComplexityCheck::registerMatchers(MatchFinder *Finder) {
516 Finder->addMatcher(
517 functionDecl(isDefinition(),
518 unless(anyOf(isDefaulted(), isDeleted(), isWeak())))
519 .bind("func"),
520 this);
521 Finder->addMatcher(lambdaExpr().bind("lambda"), this);
522 }
523
check(const MatchFinder::MatchResult & Result)524 void FunctionCognitiveComplexityCheck::check(
525 const MatchFinder::MatchResult &Result) {
526
527 FunctionASTVisitor Visitor(IgnoreMacros);
528 SourceLocation Loc;
529
530 const auto *TheDecl = Result.Nodes.getNodeAs<FunctionDecl>("func");
531 const auto *TheLambdaExpr = Result.Nodes.getNodeAs<LambdaExpr>("lambda");
532 if (TheDecl) {
533 assert(TheDecl->hasBody() &&
534 "The matchers should only match the functions that "
535 "have user-provided body.");
536 Loc = TheDecl->getLocation();
537 Visitor.TraverseDecl(const_cast<FunctionDecl *>(TheDecl), true);
538 } else {
539 Loc = TheLambdaExpr->getBeginLoc();
540 Visitor.TraverseLambdaExpr(const_cast<LambdaExpr *>(TheLambdaExpr));
541 }
542
543 if (Visitor.CC.Total <= Threshold)
544 return;
545
546 if (TheDecl)
547 diag(Loc, "function %0 has cognitive complexity of %1 (threshold %2)")
548 << TheDecl << Visitor.CC.Total << Threshold;
549 else
550 diag(Loc, "lambda has cognitive complexity of %0 (threshold %1)")
551 << Visitor.CC.Total << Threshold;
552
553 if (!DescribeBasicIncrements)
554 return;
555
556 // Output all the basic increments of complexity.
557 for (const auto &Detail : Visitor.CC.Details) {
558 unsigned MsgId; // The id of the message to output.
559 unsigned short Increase; // How much of an increment?
560 std::tie(MsgId, Increase) = Detail.process();
561 assert(MsgId < Msgs.size() && "MsgId should always be valid");
562 // Increase, on the other hand, can be 0.
563
564 diag(Detail.Loc, Msgs[MsgId], DiagnosticIDs::Note)
565 << (unsigned)Increase << (unsigned)Detail.Nesting << 1 + Detail.Nesting;
566 }
567 }
568
569 } // namespace readability
570 } // namespace tidy
571 } // namespace clang
572