Debian Codegraph @

llvm-project/clang-tools-extra/clang-tidy/readability/FunctionCognitiveComplexityCheck.cpp

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