0e931c708e4a613a39d9f1ab54f2579b8085c024
[lldb.git] / clang-tools-extra / clang-tidy / readability / FunctionCognitiveComplexityCheck.cpp
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
95     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.
102     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.
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 }
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 }
186 CognitiveComplexity::Criteria &operator|=(CognitiveComplexity::Criteria &LHS,
187                                           CognitiveComplexity::Criteria RHS) {
188   LHS = operator|(LHS, RHS);
189   return LHS;
190 }
191 CognitiveComplexity::Criteria &operator&=(CognitiveComplexity::Criteria &LHS,
192                                           CognitiveComplexity::Criteria RHS) {
193   LHS = operator&(LHS, RHS);
194   return LHS;
195 }
196
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:
229   explicit FunctionASTVisitor(const bool IgnoreMacros)
230       : IgnoreMacros(IgnoreMacros){};
231
232   bool traverseStmtWithIncreasedNestingLevel(Stmt *Node) {
233     ++CurrentNestingLevel;
234     bool ShouldContinue = Base::TraverseStmt(Node);
235     --CurrentNestingLevel;
236     return ShouldContinue;
237   }
238
239   bool traverseDeclWithIncreasedNestingLevel(Decl *Node) {
240     ++CurrentNestingLevel;
241     bool ShouldContinue = Base::TraverseDecl(Node);
242     --CurrentNestingLevel;
243     return ShouldContinue;
244   }
245
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.
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.
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
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.
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
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
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
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
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