96fe9a2e29a4f3e1cf8f618b78b8797e619b8eca
[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   // The current nesting level (increased by Criteria::IncrementNesting).
217   unsigned short CurrentNestingLevel = 0;
218
219   // Used to efficiently know the last type of the binary sequence operator
220   // that was encountered. It would make sense for the function call to start
221   // the new sequence, thus it is a stack.
222   using OBO = Optional<BinaryOperator::Opcode>;
223   std::stack<OBO, SmallVector<OBO, 4>> BinaryOperatorsStack;
224
225 public:
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 Optional<BinaryOperator::Opcode> BinOpCopy(CurrentBinaryOperator);
333
334     // Record the operator that we are currently processing and traverse it.
335     CurrentBinaryOperator = Op->getOpcode();
336     bool ShouldContinue = Base::TraverseBinaryOperator(Op);
337
338     // And restore the previous binary operator, which might be nonexistent.
339     CurrentBinaryOperator = BinOpCopy;
340
341     return ShouldContinue;
342   }
343
344   // It would make sense for the function call to start the new binary
345   // operator sequence, thus let's make sure that it creates a new stack frame.
346   bool TraverseCallExpr(CallExpr *Node) {
347     // If we are not currently processing any binary operator sequence, then
348     // no Node-handling is needed.
349     if (!Node || BinaryOperatorsStack.empty() || !CurrentBinaryOperator)
350       return Base::TraverseCallExpr(Node);
351
352     // Else, do add [uninitialized] frame to the stack, and traverse call.
353     BinaryOperatorsStack.emplace();
354     bool ShouldContinue = Base::TraverseCallExpr(Node);
355     // And remove the top frame.
356     BinaryOperatorsStack.pop();
357
358     return ShouldContinue;
359   }
360
361 #undef CurrentBinaryOperator
362
363   bool TraverseStmt(Stmt *Node) {
364     if (!Node)
365       return Base::TraverseStmt(Node);
366
367     // Three following switch()'es have huge duplication, but it is better to
368     // keep them separate, to simplify comparing them with the Specification.
369
370     CognitiveComplexity::Criteria Reasons = CognitiveComplexity::Criteria::None;
371     SourceLocation Location = Node->getBeginLoc();
372
373     // B1. Increments
374     // There is an increment for each of the following:
375     switch (Node->getStmtClass()) {
376     // if, else if, else are handled in TraverseIfStmt(),
377     // FIXME: "each method in a recursion cycle" Increment is not implemented.
378     case Stmt::ConditionalOperatorClass:
379     case Stmt::SwitchStmtClass:
380     case Stmt::ForStmtClass:
381     case Stmt::CXXForRangeStmtClass:
382     case Stmt::WhileStmtClass:
383     case Stmt::DoStmtClass:
384     case Stmt::CXXCatchStmtClass:
385     case Stmt::GotoStmtClass:
386     case Stmt::IndirectGotoStmtClass:
387       Reasons |= CognitiveComplexity::Criteria::Increment;
388       break;
389     default:
390       // break LABEL, continue LABEL increase cognitive complexity,
391       // but they are not supported in C++ or C.
392       // Regular break/continue do not increase cognitive complexity.
393       break;
394     }
395
396     // B2. Nesting level
397     // The following structures increment the nesting level:
398     switch (Node->getStmtClass()) {
399     // if, else if, else are handled in TraverseIfStmt(),
400     // Nested methods and such are handled in TraverseDecl.
401     case Stmt::ConditionalOperatorClass:
402     case Stmt::SwitchStmtClass:
403     case Stmt::ForStmtClass:
404     case Stmt::CXXForRangeStmtClass:
405     case Stmt::WhileStmtClass:
406     case Stmt::DoStmtClass:
407     case Stmt::CXXCatchStmtClass:
408     case Stmt::LambdaExprClass:
409     case Stmt::StmtExprClass:
410       Reasons |= CognitiveComplexity::Criteria::IncrementNesting;
411       break;
412     default:
413       break;
414     }
415
416     // B3. Nesting increments
417     // The following structures receive a nesting increment
418     // commensurate with their nested depth inside B2 structures:
419     switch (Node->getStmtClass()) {
420     // if, else if, else are handled in TraverseIfStmt().
421     case Stmt::ConditionalOperatorClass:
422     case Stmt::SwitchStmtClass:
423     case Stmt::ForStmtClass:
424     case Stmt::CXXForRangeStmtClass:
425     case Stmt::WhileStmtClass:
426     case Stmt::DoStmtClass:
427     case Stmt::CXXCatchStmtClass:
428       Reasons |= CognitiveComplexity::Criteria::PenalizeNesting;
429       break;
430     default:
431       break;
432     }
433
434     if (Node->getStmtClass() == Stmt::ConditionalOperatorClass) {
435       // A little beautification.
436       // For conditional operator "cond ? true : false" point at the "?"
437       // symbol.
438       ConditionalOperator *COp = dyn_cast<ConditionalOperator>(Node);
439       Location = COp->getQuestionLoc();
440     }
441
442     // If we have found any reasons, let's account it.
443     if (Reasons & CognitiveComplexity::Criteria::All)
444       CC.account(Location, CurrentNestingLevel, Reasons);
445
446     // Did we decide that the nesting level should be increased?
447     if (!(Reasons & CognitiveComplexity::Criteria::IncrementNesting))
448       return Base::TraverseStmt(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(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(Node);
478       break;
479     }
480
481     CC.account(Node->getBeginLoc(), CurrentNestingLevel,
482                CognitiveComplexity::Criteria::IncrementNesting);
483
484     return TraverseDeclWithIncreasedNestingLevel(Node);
485   }
486
487   CognitiveComplexity CC;
488 };
489
490 } // namespace
491
492 FunctionCognitiveComplexityCheck::FunctionCognitiveComplexityCheck(
493     StringRef Name, ClangTidyContext *Context)
494     : ClangTidyCheck(Name, Context),
495       Threshold(Options.get("Threshold", CognitiveComplexity::DefaultLimit)) {}
496
497 void FunctionCognitiveComplexityCheck::storeOptions(
498     ClangTidyOptions::OptionMap &Opts) {
499   Options.store(Opts, "Threshold", Threshold);
500 }
501
502 void FunctionCognitiveComplexityCheck::registerMatchers(MatchFinder *Finder) {
503   Finder->addMatcher(
504       functionDecl(
505           allOf(isDefinition(), unless(anyOf(isDefaulted(), isDeleted(),
506                                              isImplicit(), isInstantiated()))))
507           .bind("func"),
508       this);
509 }
510
511 void FunctionCognitiveComplexityCheck::check(
512     const MatchFinder::MatchResult &Result) {
513   const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
514   assert(Func->hasBody() && "The matchers should only match the functions that "
515                             "have user-provided body.");
516
517   FunctionASTVisitor Visitor;
518   Visitor.TraverseDecl(const_cast<FunctionDecl *>(Func), true);
519
520   if (Visitor.CC.Total <= Threshold)
521     return;
522
523   diag(Func->getLocation(),
524        "function %0 has cognitive complexity of %1 (threshold %2)")
525       << Func << Visitor.CC.Total << Threshold;
526
527   // Output all the basic increments of complexity.
528   for (const auto &Detail : Visitor.CC.Details) {
529     unsigned MsgId;          // The id of the message to output.
530     unsigned short Increase; // How much of an increment?
531     std::tie(MsgId, Increase) = Detail.process();
532     assert(MsgId < Msgs.size() && "MsgId should always be valid");
533     // Increase, on the other hand, can be 0.
534
535     diag(Detail.Loc, Msgs[MsgId], DiagnosticIDs::Note)
536         << (unsigned)Increase << (unsigned)Detail.Nesting << 1 + Detail.Nesting;
537   }
538 }
539
540 } // namespace readability
541 } // namespace tidy
542 } // namespace clang