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