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/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 at
40 // https://www.sonarsource.com/docs/CognitiveComplexity.pdf
41 // or user-facing docs at
42 // http://clang.llvm.org/extra/clang-tidy/checks/readability/function-cognitive-complexity.html
43 // 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 // * SwitchStmt
51 // * ForStmt, CXXForRangeStmt
52 // * WhileStmt, DoStmt
53 // * CXXCatchStmt
54 // * 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 // * SwitchStmt
63 // * ForStmt, CXXForRangeStmt
64 // * WhileStmt, DoStmt
65 // * CXXCatchStmt
66 // * nested CXXConstructor, CXXDestructor, CXXMethod (incl. C++11 Lambda)
67 // * GNU Statement Expression
68 // * Apple Block declaration
69 IncrementNesting = 1U << 1,
70
71 // B3, increases cognitive complexity by the current nesting level
72 // Applied before IncrementNesting
73 // What causes it:
74 // * IfStmt, ConditionalOperator (not BinaryConditionalOperator)
75 // * SwitchStmt
76 // * ForStmt, CXXForRangeStmt
77 // * WhileStmt, DoStmt
78 // * CXXCatchStmt
79 PenalizeNesting = 1U << 2,
80
81 All = Increment | PenalizeNesting | IncrementNesting,
82 };
83
84 // The helper struct used to record one increment occurrence, with all the
85 // 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 increment
90
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 usable
96 // information - what message to output, how much of an increment did this
97 // 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 } else
117 llvm_unreachable("should not get to here.");
118
119 return std::make_pair(x&: MsgId, y&: 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 projects
127 // 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%, ~10
129 // 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 the
137 // upper limit for function cognitive complexity. Thus it would make sense
138 // 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// All the possible messages that can be output. The choice of the message
148// to use is based of the combination of the CognitiveComplexity::Criteria.
149// It would be nice to have it in CognitiveComplexity struct, but then it is
150// not static.
151static const std::array<const StringRef, 4> Msgs = {._M_elems: {
152 // B1 + B2 + B3
153 "+%0, including nesting penalty of %1, nesting level increased to %2",
154
155 // B1 + B2
156 "+%0, nesting level increased to %2",
157
158 // B1
159 "+%0",
160
161 // B2
162 "nesting level increased to %2",
163}};
164
165// Criteria is a bitset, thus a few helpers are needed.
166CognitiveComplexity::Criteria operator|(CognitiveComplexity::Criteria LHS,
167 CognitiveComplexity::Criteria RHS) {
168 return static_cast<CognitiveComplexity::Criteria>(llvm::to_underlying(E: LHS) |
169 llvm::to_underlying(E: RHS));
170}
171CognitiveComplexity::Criteria operator&(CognitiveComplexity::Criteria LHS,
172 CognitiveComplexity::Criteria RHS) {
173 return static_cast<CognitiveComplexity::Criteria>(llvm::to_underlying(E: LHS) &
174 llvm::to_underlying(E: RHS));
175}
176CognitiveComplexity::Criteria &operator|=(CognitiveComplexity::Criteria &LHS,
177 CognitiveComplexity::Criteria RHS) {
178 LHS = operator|(LHS, RHS);
179 return LHS;
180}
181CognitiveComplexity::Criteria &operator&=(CognitiveComplexity::Criteria &LHS,
182 CognitiveComplexity::Criteria RHS) {
183 LHS = operator&(LHS, RHS);
184 return LHS;
185}
186
187void CognitiveComplexity::account(SourceLocation Loc, unsigned short Nesting,
188 Criteria C) {
189 C &= Criteria::All;
190 assert(C != Criteria::None && "invalid criteria");
191
192 Details.emplace_back(Args&: Loc, Args&: Nesting, Args&: C);
193 const Detail &D = Details.back();
194
195 unsigned MsgId = 0;
196 unsigned short Increase = 0;
197 std::tie(args&: MsgId, args&: Increase) = D.process();
198
199 Total += Increase;
200}
201
202class FunctionASTVisitor final
203 : public RecursiveASTVisitor<FunctionASTVisitor> {
204 using Base = RecursiveASTVisitor<FunctionASTVisitor>;
205
206 // If set to true, macros are ignored during analysis.
207 const bool IgnoreMacros;
208
209 // The current nesting level (increased by Criteria::IncrementNesting).
210 unsigned short CurrentNestingLevel = 0;
211
212 // Used to efficiently know the last type of the binary sequence operator
213 // that was encountered. It would make sense for the function call to start
214 // the new sequence, thus it is a stack.
215 using OBO = std::optional<BinaryOperator::Opcode>;
216 std::stack<OBO, SmallVector<OBO, 4>> BinaryOperatorsStack;
217
218public:
219 explicit FunctionASTVisitor(const bool IgnoreMacros)
220 : IgnoreMacros(IgnoreMacros) {}
221
222 bool traverseStmtWithIncreasedNestingLevel(Stmt *Node) {
223 ++CurrentNestingLevel;
224 bool ShouldContinue = Base::TraverseStmt(S: Node);
225 --CurrentNestingLevel;
226 return ShouldContinue;
227 }
228
229 bool traverseDeclWithIncreasedNestingLevel(Decl *Node) {
230 ++CurrentNestingLevel;
231 bool ShouldContinue = Base::TraverseDecl(D: Node);
232 --CurrentNestingLevel;
233 return ShouldContinue;
234 }
235
236 bool TraverseIfStmt(IfStmt *Node, bool InElseIf = false) {
237 if (!Node)
238 return Base::TraverseIfStmt(Node);
239
240 {
241 CognitiveComplexity::Criteria Reasons =
242 CognitiveComplexity::Criteria::None;
243
244 // "If" increases cognitive complexity.
245 Reasons |= CognitiveComplexity::Criteria::Increment;
246 // "If" increases nesting level.
247 Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
248
249 if (!InElseIf) {
250 // "If" receives a nesting increment commensurate with it's nested
251 // depth, if it is not part of "else if".
252 Reasons |= CognitiveComplexity::Criteria::PenalizeNesting;
253 }
254
255 CC.account(Loc: Node->getIfLoc(), Nesting: CurrentNestingLevel, C: Reasons);
256 }
257
258 // If this IfStmt is *NOT* "else if", then only the body (i.e. "Then" and
259 // "Else") is traversed with increased Nesting level.
260 // However if this IfStmt *IS* "else if", then Nesting level is increased
261 // for the whole IfStmt (i.e. for "Init", "Cond", "Then" and "Else").
262
263 if (!InElseIf) {
264 if (!TraverseStmt(Node: Node->getInit()))
265 return false;
266
267 if (!TraverseStmt(Node->getCond()))
268 return false;
269 } else {
270 if (!traverseStmtWithIncreasedNestingLevel(Node: Node->getInit()))
271 return false;
272
273 if (!traverseStmtWithIncreasedNestingLevel(Node->getCond()))
274 return false;
275 }
276
277 // "Then" always increases nesting level.
278 if (!traverseStmtWithIncreasedNestingLevel(Node: Node->getThen()))
279 return false;
280
281 if (!Node->getElse())
282 return true;
283
284 if (auto *E = dyn_cast<IfStmt>(Val: Node->getElse()))
285 return TraverseIfStmt(Node: E, InElseIf: true);
286
287 {
288 CognitiveComplexity::Criteria Reasons =
289 CognitiveComplexity::Criteria::None;
290
291 // "Else" increases cognitive complexity.
292 Reasons |= CognitiveComplexity::Criteria::Increment;
293 // "Else" increases nesting level.
294 Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
295 // "Else" DOES NOT receive a nesting increment commensurate with it's
296 // nested depth.
297
298 CC.account(Loc: Node->getElseLoc(), Nesting: CurrentNestingLevel, C: Reasons);
299 }
300
301 // "Else" always increases nesting level.
302 return traverseStmtWithIncreasedNestingLevel(Node: Node->getElse());
303 }
304
305// The currently-being-processed stack entry, which is always the top.
306#define CurrentBinaryOperator BinaryOperatorsStack.top()
307
308 // In a sequence of binary logical operators, if the new operator is different
309 // from the previous one, then the cognitive complexity is increased.
310 bool TraverseBinaryOperator(BinaryOperator *Op) {
311 if (!Op || !Op->isLogicalOp())
312 return Base::TraverseBinaryOperator(Op);
313
314 // Make sure that there is always at least one frame in the stack.
315 if (BinaryOperatorsStack.empty())
316 BinaryOperatorsStack.emplace();
317
318 // If this is the first binary operator that we are processing, or the
319 // previous binary operator was different, there is an increment.
320 if (!CurrentBinaryOperator || Op->getOpcode() != CurrentBinaryOperator)
321 CC.account(Loc: Op->getOperatorLoc(), Nesting: CurrentNestingLevel,
322 C: CognitiveComplexity::Criteria::Increment);
323
324 // We might encounter a function call, which starts a new sequence, thus
325 // we need to save the current previous binary operator.
326 const std::optional<BinaryOperator::Opcode> BinOpCopy(
327 CurrentBinaryOperator);
328
329 // Record the operator that we are currently processing and traverse it.
330 CurrentBinaryOperator = Op->getOpcode();
331 bool ShouldContinue = Base::TraverseBinaryOperator(Op);
332
333 // And restore the previous binary operator, which might be nonexistent.
334 CurrentBinaryOperator = BinOpCopy;
335
336 return ShouldContinue;
337 }
338
339 // It would make sense for the function call to start the new binary
340 // operator sequence, thus let's make sure that it creates a new stack frame.
341 bool TraverseCallExpr(CallExpr *Node) {
342 // If we are not currently processing any binary operator sequence, then
343 // no Node-handling is needed.
344 if (!Node || BinaryOperatorsStack.empty() || !CurrentBinaryOperator)
345 return Base::TraverseCallExpr(Node);
346
347 // Else, do add [uninitialized] frame to the stack, and traverse call.
348 BinaryOperatorsStack.emplace();
349 bool ShouldContinue = Base::TraverseCallExpr(Node);
350 // And remove the top frame.
351 BinaryOperatorsStack.pop();
352
353 return ShouldContinue;
354 }
355
356#undef CurrentBinaryOperator
357
358 bool TraverseStmt(Stmt *Node) {
359 if (!Node)
360 return Base::TraverseStmt(S: Node);
361
362 if (IgnoreMacros && Node->getBeginLoc().isMacroID())
363 return true;
364
365 // Three following switch()'es have huge duplication, but it is better to
366 // keep them separate, to simplify comparing them with the Specification.
367
368 CognitiveComplexity::Criteria Reasons = CognitiveComplexity::Criteria::None;
369 SourceLocation Location = Node->getBeginLoc();
370
371 // B1. Increments
372 // There is an increment for each of the following:
373 switch (Node->getStmtClass()) {
374 // if, else if, else are handled in TraverseIfStmt(),
375 // FIXME: "each method in a recursion cycle" Increment is not implemented.
376 case Stmt::ConditionalOperatorClass:
377 case Stmt::SwitchStmtClass:
378 case Stmt::ForStmtClass:
379 case Stmt::CXXForRangeStmtClass:
380 case Stmt::WhileStmtClass:
381 case Stmt::DoStmtClass:
382 case Stmt::CXXCatchStmtClass:
383 case Stmt::GotoStmtClass:
384 case Stmt::IndirectGotoStmtClass:
385 Reasons |= CognitiveComplexity::Criteria::Increment;
386 break;
387 default:
388 // break LABEL, continue LABEL increase cognitive complexity,
389 // but they are not supported in C++ or C.
390 // Regular break/continue do not increase cognitive complexity.
391 break;
392 }
393
394 // B2. Nesting level
395 // The following structures increment the nesting level:
396 switch (Node->getStmtClass()) {
397 // if, else if, else are handled in TraverseIfStmt(),
398 // Nested methods and such are handled in TraverseDecl.
399 case Stmt::ConditionalOperatorClass:
400 case Stmt::SwitchStmtClass:
401 case Stmt::ForStmtClass:
402 case Stmt::CXXForRangeStmtClass:
403 case Stmt::WhileStmtClass:
404 case Stmt::DoStmtClass:
405 case Stmt::CXXCatchStmtClass:
406 case Stmt::LambdaExprClass:
407 case Stmt::StmtExprClass:
408 Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
409 break;
410 default:
411 break;
412 }
413
414 // B3. Nesting increments
415 // The following structures receive a nesting increment
416 // commensurate with their nested depth inside B2 structures:
417 switch (Node->getStmtClass()) {
418 // if, else if, else are handled in TraverseIfStmt().
419 case Stmt::ConditionalOperatorClass:
420 case Stmt::SwitchStmtClass:
421 case Stmt::ForStmtClass:
422 case Stmt::CXXForRangeStmtClass:
423 case Stmt::WhileStmtClass:
424 case Stmt::DoStmtClass:
425 case Stmt::CXXCatchStmtClass:
426 Reasons |= CognitiveComplexity::Criteria::PenalizeNesting;
427 break;
428 default:
429 break;
430 }
431
432 if (Node->getStmtClass() == Stmt::ConditionalOperatorClass) {
433 // A little beautification.
434 // For conditional operator "cond ? true : false" point at the "?"
435 // symbol.
436 Location = cast<ConditionalOperator>(Val: Node)->getQuestionLoc();
437 }
438
439 // If we have found any reasons, let's account it.
440 if (Reasons & CognitiveComplexity::Criteria::All)
441 CC.account(Loc: Location, Nesting: CurrentNestingLevel, C: Reasons);
442
443 // Did we decide that the nesting level should be increased?
444 if (!(Reasons & CognitiveComplexity::Criteria::IncrementNesting))
445 return Base::TraverseStmt(S: Node);
446
447 return traverseStmtWithIncreasedNestingLevel(Node);
448 }
449
450 // The parameter MainAnalyzedFunction is needed to differentiate between the
451 // cases where TraverseDecl() is the entry point from
452 // FunctionCognitiveComplexityCheck::check() and the cases where it was called
453 // from the FunctionASTVisitor itself. Explanation: if we get a function
454 // definition (e.g. constructor, destructor, method), the Cognitive Complexity
455 // specification states that the Nesting level shall be increased. But if this
456 // function is the entry point, then the Nesting level should not be
457 // increased. Thus that parameter is there and is used to fall-through
458 // directly to traversing if this is the main function that is being analyzed.
459 bool TraverseDecl(Decl *Node, bool MainAnalyzedFunction = false) {
460 if (!Node || MainAnalyzedFunction)
461 return Base::TraverseDecl(D: Node);
462
463 // B2. Nesting level
464 // The following structures increment the nesting level:
465 switch (Node->getKind()) {
466 case Decl::Function:
467 case Decl::CXXMethod:
468 case Decl::CXXConstructor:
469 case Decl::CXXDestructor:
470 case Decl::Block:
471 break;
472 default:
473 // If this is something else, we use early return!
474 return Base::TraverseDecl(D: Node);
475 break;
476 }
477
478 CC.account(Loc: Node->getBeginLoc(), Nesting: CurrentNestingLevel,
479 C: CognitiveComplexity::Criteria::IncrementNesting);
480
481 return traverseDeclWithIncreasedNestingLevel(Node);
482 }
483
484 CognitiveComplexity CC;
485};
486
487} // namespace
488
489FunctionCognitiveComplexityCheck::FunctionCognitiveComplexityCheck(
490 StringRef Name, ClangTidyContext *Context)
491 : ClangTidyCheck(Name, Context),
492 Threshold(Options.get(LocalName: "Threshold", Default: CognitiveComplexity::DefaultLimit)),
493 DescribeBasicIncrements(Options.get(LocalName: "DescribeBasicIncrements", Default: true)),
494 IgnoreMacros(Options.get(LocalName: "IgnoreMacros", Default: false)) {}
495
496void FunctionCognitiveComplexityCheck::storeOptions(
497 ClangTidyOptions::OptionMap &Opts) {
498 Options.store(Options&: Opts, LocalName: "Threshold", Value: Threshold);
499 Options.store(Options&: Opts, LocalName: "DescribeBasicIncrements", Value: DescribeBasicIncrements);
500 Options.store(Options&: Opts, LocalName: "IgnoreMacros", Value: IgnoreMacros);
501}
502
503void FunctionCognitiveComplexityCheck::registerMatchers(MatchFinder *Finder) {
504 Finder->addMatcher(
505 NodeMatch: functionDecl(isDefinition(),
506 unless(anyOf(isDefaulted(), isDeleted(), isWeak())))
507 .bind(ID: "func"),
508 Action: this);
509 Finder->addMatcher(NodeMatch: lambdaExpr().bind(ID: "lambda"), Action: this);
510}
511
512void FunctionCognitiveComplexityCheck::check(
513 const MatchFinder::MatchResult &Result) {
514
515 FunctionASTVisitor Visitor(IgnoreMacros);
516 SourceLocation Loc;
517
518 const auto *TheDecl = Result.Nodes.getNodeAs<FunctionDecl>(ID: "func");
519 const auto *TheLambdaExpr = Result.Nodes.getNodeAs<LambdaExpr>(ID: "lambda");
520 if (TheDecl) {
521 assert(TheDecl->hasBody() &&
522 "The matchers should only match the functions that "
523 "have user-provided body.");
524 Loc = TheDecl->getLocation();
525 Visitor.TraverseDecl(const_cast<FunctionDecl *>(TheDecl), true);
526 } else {
527 Loc = TheLambdaExpr->getBeginLoc();
528 Visitor.TraverseLambdaExpr(const_cast<LambdaExpr *>(TheLambdaExpr));
529 }
530
531 if (Visitor.CC.Total <= Threshold)
532 return;
533
534 if (TheDecl)
535 diag(Loc, Description: "function %0 has cognitive complexity of %1 (threshold %2)")
536 << TheDecl << Visitor.CC.Total << Threshold;
537 else
538 diag(Loc, Description: "lambda has cognitive complexity of %0 (threshold %1)")
539 << Visitor.CC.Total << Threshold;
540
541 if (!DescribeBasicIncrements)
542 return;
543
544 // Output all the basic increments of complexity.
545 for (const auto &Detail : Visitor.CC.Details) {
546 unsigned MsgId = 0; // The id of the message to output.
547 unsigned short Increase = 0; // How much of an increment?
548 std::tie(args&: MsgId, args&: Increase) = Detail.process();
549 assert(MsgId < Msgs.size() && "MsgId should always be valid");
550 // Increase, on the other hand, can be 0.
551
552 diag(Loc: Detail.Loc, Description: Msgs[MsgId], Level: DiagnosticIDs::Note)
553 << (unsigned)Increase << (unsigned)Detail.Nesting << 1 + Detail.Nesting;
554 }
555}
556
557} // namespace clang::tidy::readability
558

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