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
35using namespace clang::ast_matchers;
36
37namespace clang::tidy::readability {
38namespace {
39
40struct 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(x&: MsgId, y&: 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-avaliable 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.
154static const std::array<const StringRef, 4> Msgs = {._M_elems: {
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.
169CognitiveComplexity::Criteria operator|(CognitiveComplexity::Criteria LHS,
170 CognitiveComplexity::Criteria RHS) {
171 return static_cast<CognitiveComplexity::Criteria>(llvm::to_underlying(E: LHS) |
172 llvm::to_underlying(E: RHS));
173}
174CognitiveComplexity::Criteria operator&(CognitiveComplexity::Criteria LHS,
175 CognitiveComplexity::Criteria RHS) {
176 return static_cast<CognitiveComplexity::Criteria>(llvm::to_underlying(E: LHS) &
177 llvm::to_underlying(E: RHS));
178}
179CognitiveComplexity::Criteria &operator|=(CognitiveComplexity::Criteria &LHS,
180 CognitiveComplexity::Criteria RHS) {
181 LHS = operator|(LHS, RHS);
182 return LHS;
183}
184CognitiveComplexity::Criteria &operator&=(CognitiveComplexity::Criteria &LHS,
185 CognitiveComplexity::Criteria RHS) {
186 LHS = operator&(LHS, RHS);
187 return LHS;
188}
189
190void 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(Args&: Loc, Args&: Nesting, Args&: C);
196 const Detail &D = Details.back();
197
198 unsigned MsgId = 0;
199 unsigned short Increase = 0;
200 std::tie(args&: MsgId, args&: Increase) = D.process();
201
202 Total += Increase;
203}
204
205class 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
221public:
222 explicit FunctionASTVisitor(const bool IgnoreMacros)
223 : IgnoreMacros(IgnoreMacros) {}
224
225 bool traverseStmtWithIncreasedNestingLevel(Stmt *Node) {
226 ++CurrentNestingLevel;
227 bool ShouldContinue = Base::TraverseStmt(S: Node);
228 --CurrentNestingLevel;
229 return ShouldContinue;
230 }
231
232 bool traverseDeclWithIncreasedNestingLevel(Decl *Node) {
233 ++CurrentNestingLevel;
234 bool ShouldContinue = Base::TraverseDecl(D: 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(Loc: Node->getIfLoc(), Nesting: CurrentNestingLevel, C: 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: Node->getInit()))
268 return false;
269
270 if (!TraverseStmt(Node->getCond()))
271 return false;
272 } else {
273 if (!traverseStmtWithIncreasedNestingLevel(Node: 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: Node->getThen()))
282 return false;
283
284 if (!Node->getElse())
285 return true;
286
287 if (auto *E = dyn_cast<IfStmt>(Val: Node->getElse()))
288 return TraverseIfStmt(Node: E, InElseIf: 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(Loc: Node->getElseLoc(), Nesting: CurrentNestingLevel, C: Reasons);
302 }
303
304 // "Else" always increases nesting level.
305 return traverseStmtWithIncreasedNestingLevel(Node: 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(Loc: Op->getOperatorLoc(), Nesting: CurrentNestingLevel,
325 C: 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(S: 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>(Val: Node)->getQuestionLoc();
440 }
441
442 // If we have found any reasons, let's account it.
443 if (Reasons & CognitiveComplexity::Criteria::All)
444 CC.account(Loc: Location, Nesting: CurrentNestingLevel, C: Reasons);
445
446 // Did we decide that the nesting level should be increased?
447 if (!(Reasons & CognitiveComplexity::Criteria::IncrementNesting))
448 return Base::TraverseStmt(S: 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(D: 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(D: Node);
478 break;
479 }
480
481 CC.account(Loc: Node->getBeginLoc(), Nesting: CurrentNestingLevel,
482 C: CognitiveComplexity::Criteria::IncrementNesting);
483
484 return traverseDeclWithIncreasedNestingLevel(Node);
485 }
486
487 CognitiveComplexity CC;
488};
489
490} // namespace
491
492FunctionCognitiveComplexityCheck::FunctionCognitiveComplexityCheck(
493 StringRef Name, ClangTidyContext *Context)
494 : ClangTidyCheck(Name, Context),
495 Threshold(Options.get(LocalName: "Threshold", Default: CognitiveComplexity::DefaultLimit)),
496 DescribeBasicIncrements(Options.get(LocalName: "DescribeBasicIncrements", Default: true)),
497 IgnoreMacros(Options.get(LocalName: "IgnoreMacros", Default: false)) {}
498
499void FunctionCognitiveComplexityCheck::storeOptions(
500 ClangTidyOptions::OptionMap &Opts) {
501 Options.store(Options&: Opts, LocalName: "Threshold", Value: Threshold);
502 Options.store(Options&: Opts, LocalName: "DescribeBasicIncrements", Value: DescribeBasicIncrements);
503 Options.store(Options&: Opts, LocalName: "IgnoreMacros", Value: IgnoreMacros);
504}
505
506void FunctionCognitiveComplexityCheck::registerMatchers(MatchFinder *Finder) {
507 Finder->addMatcher(
508 NodeMatch: functionDecl(isDefinition(),
509 unless(anyOf(isDefaulted(), isDeleted(), isWeak())))
510 .bind(ID: "func"),
511 Action: this);
512 Finder->addMatcher(NodeMatch: lambdaExpr().bind(ID: "lambda"), Action: this);
513}
514
515void FunctionCognitiveComplexityCheck::check(
516 const MatchFinder::MatchResult &Result) {
517
518 FunctionASTVisitor Visitor(IgnoreMacros);
519 SourceLocation Loc;
520
521 const auto *TheDecl = Result.Nodes.getNodeAs<FunctionDecl>(ID: "func");
522 const auto *TheLambdaExpr = Result.Nodes.getNodeAs<LambdaExpr>(ID: "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, Description: "function %0 has cognitive complexity of %1 (threshold %2)")
539 << TheDecl << Visitor.CC.Total << Threshold;
540 else
541 diag(Loc, Description: "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(args&: MsgId, args&: 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(Loc: Detail.Loc, Description: Msgs[MsgId], Level: DiagnosticIDs::Note)
556 << (unsigned)Increase << (unsigned)Detail.Nesting << 1 + Detail.Nesting;
557 }
558}
559
560} // namespace clang::tidy::readability
561

source code of clang-tools-extra/clang-tidy/readability/FunctionCognitiveComplexityCheck.cpp