| 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 |