Debian Codegraph @

llvm-project/clang-tools-extra/clang-tidy/bugprone/BranchCloneCheck.cpp

raw
1 //===--- BranchCloneCheck.cpp - clang-tidy --------------------------------===//
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 "BranchCloneCheck.h"
10 #include "clang/AST/ASTContext.h"
11 #include "clang/ASTMatchers/ASTMatchFinder.h"
12 #include "clang/Analysis/CloneDetection.h"
13 #include "clang/Lex/Lexer.h"
14 #include "llvm/Support/Casting.h"
15
16 using namespace clang;
17 using namespace clang::ast_matchers;
18
19 /// Returns true when the statements are Type I clones of each other.
20 static bool areStatementsIdentical(const Stmt *LHS, const Stmt *RHS,
21 const ASTContext &Context) {
22 if (isa<Expr>(LHS) && isa<Expr>(RHS)) {
23 // If we have errors in expressions, we will be unable
24 // to accurately profile and compute hashes for each
25 // of the left and right statements.
26 const auto *LHSExpr = llvm::cast<Expr>(LHS);
27 const auto *RHSExpr = llvm::cast<Expr>(RHS);
28 if (LHSExpr->containsErrors() && RHSExpr->containsErrors()) {
29 return false;
30 }
31 }
32
33 llvm::FoldingSetNodeID DataLHS, DataRHS;
34 LHS->Profile(DataLHS, Context, false);
35 RHS->Profile(DataRHS, Context, false);
36 return (DataLHS == DataRHS);
37 }
38
39 namespace {
40 /// A branch in a switch may consist of several statements; while a branch in
41 /// an if/else if/else chain is one statement (which may be a CompoundStmt).
42 using SwitchBranch = llvm::SmallVector<const Stmt *, 2>;
43 } // anonymous namespace
44
45 /// Determines if the bodies of two branches in a switch statements are Type I
46 /// clones of each other. This function only examines the body of the branch
47 /// and ignores the `case X:` or `default:` at the start of the branch.
48 static bool areSwitchBranchesIdentical(const SwitchBranch LHS,
49 const SwitchBranch RHS,
50 const ASTContext &Context) {
51 if (LHS.size() != RHS.size())
52 return false;
53
54 for (size_t I = 0, Size = LHS.size(); I < Size; I++) {
55 // NOTE: We strip goto labels and annotations in addition to stripping
56 // the `case X:` or `default:` labels, but it is very unlikely that this
57 // would cause false positives in real-world code.
58 if (!areStatementsIdentical(LHS[I]->stripLabelLikeStatements(),
59 RHS[I]->stripLabelLikeStatements(), Context)) {
60 return false;
61 }
62 }
63
64 return true;
65 }
66
67 namespace clang::tidy::bugprone {
68
69 void BranchCloneCheck::registerMatchers(MatchFinder *Finder) {
70 Finder->addMatcher(
71 ifStmt(unless(allOf(isConstexpr(), isInTemplateInstantiation())),
72 stmt().bind("if"),
73 hasParent(stmt(unless(ifStmt(hasElse(equalsBoundNode("if")))))),
74 hasElse(stmt().bind("else"))),
75 this);
76 Finder->addMatcher(switchStmt().bind("switch"), this);
77 Finder->addMatcher(conditionalOperator().bind("condOp"), this);
78 }
79
80 void BranchCloneCheck::check(const MatchFinder::MatchResult &Result) {
81 const ASTContext &Context = *Result.Context;
82
83 if (const auto *IS = Result.Nodes.getNodeAs<IfStmt>("if")) {
84 const Stmt *Then = IS->getThen();
85 assert(Then && "An IfStmt must have a `then` branch!");
86
87 const Stmt *Else = Result.Nodes.getNodeAs<Stmt>("else");
88 assert(Else && "We only look for `if` statements with an `else` branch!");
89
90 if (!isa<IfStmt>(Else)) {
91 // Just a simple if with no `else if` branch.
92 if (areStatementsIdentical(Then->IgnoreContainers(),
93 Else->IgnoreContainers(), Context)) {
94 diag(IS->getBeginLoc(), "if with identical then and else branches");
95 diag(IS->getElseLoc(), "else branch starts here", DiagnosticIDs::Note);
96 }
97 return;
98 }
99
100 // This is the complicated case when we start an if/else if/else chain.
101 // To find all the duplicates, we collect all the branches into a vector.
102 llvm::SmallVector<const Stmt *, 4> Branches;
103 const IfStmt *Cur = IS;
104 while (true) {
105 // Store the `then` branch.
106 Branches.push_back(Cur->getThen());
107
108 Else = Cur->getElse();
109 // The chain ends if there is no `else` branch.
110 if (!Else)
111 break;
112
113 // Check if there is another `else if`...
114 Cur = dyn_cast<IfStmt>(Else);
115 if (!Cur) {
116 // ...this is just a plain `else` branch at the end of the chain.
117 Branches.push_back(Else);
118 break;
119 }
120 }
121
122 size_t N = Branches.size();
123 llvm::BitVector KnownAsClone(N);
124
125 for (size_t I = 0; I + 1 < N; I++) {
126 // We have already seen Branches[i] as a clone of an earlier branch.
127 if (KnownAsClone[I])
128 continue;
129
130 int NumCopies = 1;
131
132 for (size_t J = I + 1; J < N; J++) {
133 if (KnownAsClone[J] ||
134 !areStatementsIdentical(Branches[I]->IgnoreContainers(),
135 Branches[J]->IgnoreContainers(), Context))
136 continue;
137
138 NumCopies++;
139 KnownAsClone[J] = true;
140
141 if (NumCopies == 2) {
142 // We report the first occurrence only when we find the second one.
143 diag(Branches[I]->getBeginLoc(),
144 "repeated branch in conditional chain");
145 SourceLocation End =
146 Lexer::getLocForEndOfToken(Branches[I]->getEndLoc(), 0,
147 *Result.SourceManager, getLangOpts());
148 if (End.isValid()) {
149 diag(End, "end of the original", DiagnosticIDs::Note);
150 }
151 }
152
153 diag(Branches[J]->getBeginLoc(), "clone %0 starts here",
154 DiagnosticIDs::Note)
155 << (NumCopies - 1);
156 }
157 }
158 return;
159 }
160
161 if (const auto *CO = Result.Nodes.getNodeAs<ConditionalOperator>("condOp")) {
162 // We do not try to detect chains of ?: operators.
163 if (areStatementsIdentical(CO->getTrueExpr(), CO->getFalseExpr(), Context))
164 diag(CO->getQuestionLoc(),
165 "conditional operator with identical true and false expressions");
166
167 return;
168 }
169
170 if (const auto *SS = Result.Nodes.getNodeAs<SwitchStmt>("switch")) {
171 const CompoundStmt *Body = dyn_cast_or_null<CompoundStmt>(SS->getBody());
172
173 // Code like
174 // switch (x) case 0: case 1: foobar();
175 // is legal and calls foobar() if and only if x is either 0 or 1;
176 // but we do not try to distinguish branches in such code.
177 if (!Body)
178 return;
179
180 // We will first collect the branches of the switch statements. For the
181 // sake of simplicity we say that branches are delimited by the SwitchCase
182 // (`case:` or `default:`) children of Body; that is, we ignore `case:` or
183 // `default:` labels embedded inside other statements and we do not follow
184 // the effects of `break` and other manipulation of the control-flow.
185 llvm::SmallVector<SwitchBranch, 4> Branches;
186 for (const Stmt *S : Body->body()) {
187 // If this is a `case` or `default`, we start a new, empty branch.
188 if (isa<SwitchCase>(S))
189 Branches.emplace_back();
190
191 // There may be code before the first branch (which can be dead code
192 // and can be code reached either through goto or through case labels
193 // that are embedded inside e.g. inner compound statements); we do not
194 // store those statements in branches.
195 if (!Branches.empty())
196 Branches.back().push_back(S);
197 }
198
199 auto *End = Branches.end();
200 auto *BeginCurrent = Branches.begin();
201 while (BeginCurrent < End) {
202 auto *EndCurrent = BeginCurrent + 1;
203 while (EndCurrent < End &&
204 areSwitchBranchesIdentical(*BeginCurrent, *EndCurrent, Context)) {
205 ++EndCurrent;
206 }
207 // At this point the iterator range {BeginCurrent, EndCurrent} contains a
208 // complete family of consecutive identical branches.
209 if (EndCurrent > BeginCurrent + 1) {
210 diag(BeginCurrent->front()->getBeginLoc(),
211 "switch has %0 consecutive identical branches")
212 << static_cast<int>(std::distance(BeginCurrent, EndCurrent));
213
214 SourceLocation EndLoc = (EndCurrent - 1)->back()->getEndLoc();
215 // If the case statement is generated from a macro, it's SourceLocation
216 // may be invalid, resulting in an assertion failure down the line.
217 // While not optimal, try the begin location in this case, it's still
218 // better then nothing.
219 if (EndLoc.isInvalid())
220 EndLoc = (EndCurrent - 1)->back()->getBeginLoc();
221
222 if (EndLoc.isMacroID())
223 EndLoc = Context.getSourceManager().getExpansionLoc(EndLoc);
224 EndLoc = Lexer::getLocForEndOfToken(EndLoc, 0, *Result.SourceManager,
225 getLangOpts());
226
227 if (EndLoc.isValid()) {
228 diag(EndLoc, "last of these clones ends here", DiagnosticIDs::Note);
229 }
230 }
231 BeginCurrent = EndCurrent;
232 }
233 return;
234 }
235
236 llvm_unreachable("No if statement and no switch statement.");
237 }
238
239 } // namespace clang::tidy::bugprone