496 lines · cpp
1//===----------------------------------------------------------------------===//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-exception6//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 17using namespace clang;18using namespace clang::ast_matchers;19 20namespace {21/// A branch in a switch may consist of several statements; while a branch in22/// an if/else if/else chain is one statement (which may be a CompoundStmt).23using SwitchBranch = llvm::SmallVector<const Stmt *, 2>;24} // anonymous namespace25 26/// Determines if the bodies of two branches in a switch statements are Type I27/// clones of each other. This function only examines the body of the branch28/// and ignores the `case X:` or `default:` at the start of the branch.29static bool areSwitchBranchesIdentical(const SwitchBranch &LHS,30 const SwitchBranch &RHS,31 const ASTContext &Context) {32 if (LHS.size() != RHS.size())33 return false;34 35 for (size_t I = 0, Size = LHS.size(); I < Size; I++) {36 // NOTE: We strip goto labels and annotations in addition to stripping37 // the `case X:` or `default:` labels, but it is very unlikely that this38 // would cause false positives in real-world code.39 if (!tidy::utils::areStatementsIdentical(LHS[I]->stripLabelLikeStatements(),40 RHS[I]->stripLabelLikeStatements(),41 Context)) {42 return false;43 }44 }45 46 return true;47}48 49static bool isFallthroughSwitchBranch(const SwitchBranch &Branch) {50 struct SwitchCaseVisitor : RecursiveASTVisitor<SwitchCaseVisitor> {51 using RecursiveASTVisitor<SwitchCaseVisitor>::DataRecursionQueue;52 53 bool TraverseLambdaExpr(LambdaExpr *, DataRecursionQueue * = nullptr) {54 return true; // Ignore lambdas55 }56 57 bool TraverseDecl(Decl *) {58 return true; // No need to check declarations59 }60 61 bool TraverseSwitchStmt(SwitchStmt *, DataRecursionQueue * = nullptr) {62 return true; // Ignore sub-switches63 }64 65 // NOLINTNEXTLINE(readability-identifier-naming) - FIXME66 bool TraverseSwitchCase(SwitchCase *, DataRecursionQueue * = nullptr) {67 return true; // Ignore cases68 }69 70 bool TraverseDefaultStmt(DefaultStmt *, DataRecursionQueue * = nullptr) {71 return true; // Ignore defaults72 }73 74 bool TraverseAttributedStmt(AttributedStmt *S) {75 if (!S)76 return true;77 78 for (const Attr *A : S->getAttrs()) {79 if (isa<FallThroughAttr>(A))80 return false;81 }82 83 return true;84 }85 } Visitor;86 87 for (const Stmt *Elem : Branch) {88 if (!Visitor.TraverseStmt(const_cast<Stmt *>(Elem)))89 return true;90 }91 return false;92}93 94namespace clang::tidy::bugprone {95 96void BranchCloneCheck::registerMatchers(MatchFinder *Finder) {97 Finder->addMatcher(98 ifStmt(unless(allOf(isConstexpr(), isInTemplateInstantiation())),99 stmt().bind("if"),100 hasParent(stmt(unless(ifStmt(hasElse(equalsBoundNode("if")))))),101 hasElse(stmt().bind("else"))),102 this);103 Finder->addMatcher(switchStmt().bind("switch"), this);104 Finder->addMatcher(conditionalOperator().bind("condOp"), this);105 Finder->addMatcher(106 ifStmt((hasThen(hasDescendant(ifStmt())))).bind("ifWithDescendantIf"),107 this);108}109 110/// Determines whether two statement trees are identical regarding111/// operators and symbols.112///113/// Exceptions: expressions containing macros or functions with possible side114/// effects are never considered identical.115/// Limitations: (t + u) and (u + t) are not considered identical.116/// t*(u + t) and t*u + t*t are not considered identical.117///118static bool isIdenticalStmt(const ASTContext &Ctx, const Stmt *Stmt1,119 const Stmt *Stmt2, bool IgnoreSideEffects) {120 if (!Stmt1 || !Stmt2)121 return !Stmt1 && !Stmt2;122 123 // If Stmt1 & Stmt2 are of different class then they are not124 // identical statements.125 if (Stmt1->getStmtClass() != Stmt2->getStmtClass())126 return false;127 128 const auto *Expr1 = dyn_cast<Expr>(Stmt1);129 const auto *Expr2 = dyn_cast<Expr>(Stmt2);130 131 if (Expr1 && Expr2) {132 // If Stmt1 has side effects then don't warn even if expressions133 // are identical.134 if (!IgnoreSideEffects && Expr1->HasSideEffects(Ctx) &&135 Expr2->HasSideEffects(Ctx))136 return false;137 // If either expression comes from a macro then don't warn even if138 // the expressions are identical.139 if ((Expr1->getExprLoc().isMacroID()) || (Expr2->getExprLoc().isMacroID()))140 return false;141 142 // If all children of two expressions are identical, return true.143 Expr::const_child_iterator I1 = Expr1->child_begin();144 Expr::const_child_iterator I2 = Expr2->child_begin();145 while (I1 != Expr1->child_end() && I2 != Expr2->child_end()) {146 if (!isIdenticalStmt(Ctx, *I1, *I2, IgnoreSideEffects))147 return false;148 ++I1;149 ++I2;150 }151 // If there are different number of children in the statements, return152 // false.153 if (I1 != Expr1->child_end())154 return false;155 if (I2 != Expr2->child_end())156 return false;157 }158 159 switch (Stmt1->getStmtClass()) {160 default:161 return false;162 case Stmt::CallExprClass:163 case Stmt::ArraySubscriptExprClass:164 case Stmt::ArraySectionExprClass:165 case Stmt::OMPArrayShapingExprClass:166 case Stmt::OMPIteratorExprClass:167 case Stmt::ImplicitCastExprClass:168 case Stmt::ParenExprClass:169 case Stmt::BreakStmtClass:170 case Stmt::ContinueStmtClass:171 case Stmt::NullStmtClass:172 return true;173 case Stmt::CStyleCastExprClass: {174 const auto *CastExpr1 = cast<CStyleCastExpr>(Stmt1);175 const auto *CastExpr2 = cast<CStyleCastExpr>(Stmt2);176 177 return CastExpr1->getTypeAsWritten() == CastExpr2->getTypeAsWritten();178 }179 case Stmt::ReturnStmtClass: {180 const auto *ReturnStmt1 = cast<ReturnStmt>(Stmt1);181 const auto *ReturnStmt2 = cast<ReturnStmt>(Stmt2);182 183 return isIdenticalStmt(Ctx, ReturnStmt1->getRetValue(),184 ReturnStmt2->getRetValue(), IgnoreSideEffects);185 }186 case Stmt::ForStmtClass: {187 const auto *ForStmt1 = cast<ForStmt>(Stmt1);188 const auto *ForStmt2 = cast<ForStmt>(Stmt2);189 190 if (!isIdenticalStmt(Ctx, ForStmt1->getInit(), ForStmt2->getInit(),191 IgnoreSideEffects))192 return false;193 if (!isIdenticalStmt(Ctx, ForStmt1->getCond(), ForStmt2->getCond(),194 IgnoreSideEffects))195 return false;196 if (!isIdenticalStmt(Ctx, ForStmt1->getInc(), ForStmt2->getInc(),197 IgnoreSideEffects))198 return false;199 if (!isIdenticalStmt(Ctx, ForStmt1->getBody(), ForStmt2->getBody(),200 IgnoreSideEffects))201 return false;202 return true;203 }204 case Stmt::DoStmtClass: {205 const auto *DStmt1 = cast<DoStmt>(Stmt1);206 const auto *DStmt2 = cast<DoStmt>(Stmt2);207 208 if (!isIdenticalStmt(Ctx, DStmt1->getCond(), DStmt2->getCond(),209 IgnoreSideEffects))210 return false;211 if (!isIdenticalStmt(Ctx, DStmt1->getBody(), DStmt2->getBody(),212 IgnoreSideEffects))213 return false;214 return true;215 }216 case Stmt::WhileStmtClass: {217 const auto *WStmt1 = cast<WhileStmt>(Stmt1);218 const auto *WStmt2 = cast<WhileStmt>(Stmt2);219 220 if (!isIdenticalStmt(Ctx, WStmt1->getCond(), WStmt2->getCond(),221 IgnoreSideEffects))222 return false;223 if (!isIdenticalStmt(Ctx, WStmt1->getBody(), WStmt2->getBody(),224 IgnoreSideEffects))225 return false;226 return true;227 }228 case Stmt::IfStmtClass: {229 const auto *IStmt1 = cast<IfStmt>(Stmt1);230 const auto *IStmt2 = cast<IfStmt>(Stmt2);231 232 if (!isIdenticalStmt(Ctx, IStmt1->getCond(), IStmt2->getCond(),233 IgnoreSideEffects))234 return false;235 if (!isIdenticalStmt(Ctx, IStmt1->getThen(), IStmt2->getThen(),236 IgnoreSideEffects))237 return false;238 if (!isIdenticalStmt(Ctx, IStmt1->getElse(), IStmt2->getElse(),239 IgnoreSideEffects))240 return false;241 return true;242 }243 case Stmt::CompoundStmtClass: {244 const auto *CompStmt1 = cast<CompoundStmt>(Stmt1);245 const auto *CompStmt2 = cast<CompoundStmt>(Stmt2);246 247 if (CompStmt1->size() != CompStmt2->size())248 return false;249 250 if (!llvm::all_of(llvm::zip(CompStmt1->body(), CompStmt2->body()),251 [&Ctx, IgnoreSideEffects](252 std::tuple<const Stmt *, const Stmt *> StmtPair) {253 const Stmt *Stmt0 = std::get<0>(StmtPair);254 const Stmt *Stmt1 = std::get<1>(StmtPair);255 return isIdenticalStmt(Ctx, Stmt0, Stmt1,256 IgnoreSideEffects);257 })) {258 return false;259 }260 261 return true;262 }263 case Stmt::CompoundAssignOperatorClass:264 case Stmt::BinaryOperatorClass: {265 const auto *BinOp1 = cast<BinaryOperator>(Stmt1);266 const auto *BinOp2 = cast<BinaryOperator>(Stmt2);267 return BinOp1->getOpcode() == BinOp2->getOpcode();268 }269 case Stmt::CharacterLiteralClass: {270 const auto *CharLit1 = cast<CharacterLiteral>(Stmt1);271 const auto *CharLit2 = cast<CharacterLiteral>(Stmt2);272 return CharLit1->getValue() == CharLit2->getValue();273 }274 case Stmt::DeclRefExprClass: {275 const auto *DeclRef1 = cast<DeclRefExpr>(Stmt1);276 const auto *DeclRef2 = cast<DeclRefExpr>(Stmt2);277 return DeclRef1->getDecl() == DeclRef2->getDecl();278 }279 case Stmt::IntegerLiteralClass: {280 const auto *IntLit1 = cast<IntegerLiteral>(Stmt1);281 const auto *IntLit2 = cast<IntegerLiteral>(Stmt2);282 283 const llvm::APInt I1 = IntLit1->getValue();284 const llvm::APInt I2 = IntLit2->getValue();285 if (I1.getBitWidth() != I2.getBitWidth())286 return false;287 return I1 == I2;288 }289 case Stmt::FloatingLiteralClass: {290 const auto *FloatLit1 = cast<FloatingLiteral>(Stmt1);291 const auto *FloatLit2 = cast<FloatingLiteral>(Stmt2);292 return FloatLit1->getValue().bitwiseIsEqual(FloatLit2->getValue());293 }294 case Stmt::StringLiteralClass: {295 const auto *StringLit1 = cast<StringLiteral>(Stmt1);296 const auto *StringLit2 = cast<StringLiteral>(Stmt2);297 return StringLit1->getBytes() == StringLit2->getBytes();298 }299 case Stmt::MemberExprClass: {300 const auto *MemberStmt1 = cast<MemberExpr>(Stmt1);301 const auto *MemberStmt2 = cast<MemberExpr>(Stmt2);302 return MemberStmt1->getMemberDecl() == MemberStmt2->getMemberDecl();303 }304 case Stmt::UnaryOperatorClass: {305 const auto *UnaryOp1 = cast<UnaryOperator>(Stmt1);306 const auto *UnaryOp2 = cast<UnaryOperator>(Stmt2);307 return UnaryOp1->getOpcode() == UnaryOp2->getOpcode();308 }309 }310}311 312void BranchCloneCheck::check(const MatchFinder::MatchResult &Result) {313 const ASTContext &Context = *Result.Context;314 315 if (const auto *IS = Result.Nodes.getNodeAs<IfStmt>("if")) {316 const Stmt *Then = IS->getThen();317 assert(Then && "An IfStmt must have a `then` branch!");318 319 const Stmt *Else = Result.Nodes.getNodeAs<Stmt>("else");320 assert(Else && "We only look for `if` statements with an `else` branch!");321 322 if (!isa<IfStmt>(Else)) {323 // Just a simple if with no `else if` branch.324 if (utils::areStatementsIdentical(Then->IgnoreContainers(),325 Else->IgnoreContainers(), Context)) {326 diag(IS->getBeginLoc(), "if with identical then and else branches");327 diag(IS->getElseLoc(), "else branch starts here", DiagnosticIDs::Note);328 }329 return;330 }331 332 // This is the complicated case when we start an if/else if/else chain.333 // To find all the duplicates, we collect all the branches into a vector.334 llvm::SmallVector<const Stmt *, 4> Branches;335 const IfStmt *Cur = IS;336 while (true) {337 // Store the `then` branch.338 Branches.push_back(Cur->getThen());339 340 Else = Cur->getElse();341 // The chain ends if there is no `else` branch.342 if (!Else)343 break;344 345 // Check if there is another `else if`...346 Cur = dyn_cast<IfStmt>(Else);347 if (!Cur) {348 // ...this is just a plain `else` branch at the end of the chain.349 Branches.push_back(Else);350 break;351 }352 }353 354 const size_t N = Branches.size();355 llvm::BitVector KnownAsClone(N);356 357 for (size_t I = 0; I + 1 < N; I++) {358 // We have already seen Branches[i] as a clone of an earlier branch.359 if (KnownAsClone[I])360 continue;361 362 int NumCopies = 1;363 364 for (size_t J = I + 1; J < N; J++) {365 if (KnownAsClone[J] || !utils::areStatementsIdentical(366 Branches[I]->IgnoreContainers(),367 Branches[J]->IgnoreContainers(), Context))368 continue;369 370 NumCopies++;371 KnownAsClone[J] = true;372 373 if (NumCopies == 2) {374 // We report the first occurrence only when we find the second one.375 diag(Branches[I]->getBeginLoc(),376 "repeated branch body in conditional chain");377 const SourceLocation End =378 Lexer::getLocForEndOfToken(Branches[I]->getEndLoc(), 0,379 *Result.SourceManager, getLangOpts());380 if (End.isValid()) {381 diag(End, "end of the original", DiagnosticIDs::Note);382 }383 }384 385 diag(Branches[J]->getBeginLoc(), "clone %0 starts here",386 DiagnosticIDs::Note)387 << (NumCopies - 1);388 }389 }390 return;391 }392 393 if (const auto *CO = Result.Nodes.getNodeAs<ConditionalOperator>("condOp")) {394 // We do not try to detect chains of ?: operators.395 if (utils::areStatementsIdentical(CO->getTrueExpr(), CO->getFalseExpr(),396 Context))397 diag(CO->getQuestionLoc(),398 "conditional operator with identical true and false expressions");399 400 return;401 }402 403 if (const auto *SS = Result.Nodes.getNodeAs<SwitchStmt>("switch")) {404 const auto *Body = dyn_cast_or_null<CompoundStmt>(SS->getBody());405 406 // Code like407 // switch (x) case 0: case 1: foobar();408 // is legal and calls foobar() if and only if x is either 0 or 1;409 // but we do not try to distinguish branches in such code.410 if (!Body)411 return;412 413 // We will first collect the branches of the switch statements. For the414 // sake of simplicity we say that branches are delimited by the SwitchCase415 // (`case:` or `default:`) children of Body; that is, we ignore `case:` or416 // `default:` labels embedded inside other statements and we do not follow417 // the effects of `break` and other manipulation of the control-flow.418 llvm::SmallVector<SwitchBranch, 4> Branches;419 for (const Stmt *S : Body->body()) {420 // If this is a `case` or `default`, we start a new, empty branch.421 if (isa<SwitchCase>(S))422 Branches.emplace_back();423 424 // There may be code before the first branch (which can be dead code425 // and can be code reached either through goto or through case labels426 // that are embedded inside e.g. inner compound statements); we do not427 // store those statements in branches.428 if (!Branches.empty())429 Branches.back().push_back(S);430 }431 432 auto *End = Branches.end();433 auto *BeginCurrent = Branches.begin();434 while (BeginCurrent < End) {435 if (isFallthroughSwitchBranch(*BeginCurrent)) {436 ++BeginCurrent;437 continue;438 }439 440 auto *EndCurrent = BeginCurrent + 1;441 while (EndCurrent < End &&442 areSwitchBranchesIdentical(*BeginCurrent, *EndCurrent, Context)) {443 ++EndCurrent;444 }445 // At this point the iterator range {BeginCurrent, EndCurrent} contains a446 // complete family of consecutive identical branches.447 448 if (EndCurrent == (BeginCurrent + 1)) {449 // No consecutive identical branches that start on BeginCurrent450 BeginCurrent = EndCurrent;451 continue;452 }453 454 diag(BeginCurrent->front()->getBeginLoc(),455 "switch has %0 consecutive identical branches")456 << static_cast<int>(std::distance(BeginCurrent, EndCurrent));457 458 SourceLocation EndLoc = (EndCurrent - 1)->back()->getEndLoc();459 // If the case statement is generated from a macro, it's SourceLocation460 // may be invalid, resulting in an assertion failure down the line.461 // While not optimal, try the begin location in this case, it's still462 // better then nothing.463 if (EndLoc.isInvalid())464 EndLoc = (EndCurrent - 1)->back()->getBeginLoc();465 if (EndLoc.isMacroID())466 EndLoc = Context.getSourceManager().getExpansionLoc(EndLoc);467 EndLoc = Lexer::getLocForEndOfToken(EndLoc, 0, *Result.SourceManager,468 getLangOpts());469 if (EndLoc.isValid()) {470 diag(EndLoc, "last of these clones ends here", DiagnosticIDs::Note);471 }472 BeginCurrent = EndCurrent;473 }474 return;475 }476 477 if (const auto *IS = Result.Nodes.getNodeAs<IfStmt>("ifWithDescendantIf")) {478 const Stmt *Then = IS->getThen();479 const auto *CS = dyn_cast<CompoundStmt>(Then);480 if (CS && (!CS->body_empty())) {481 const auto *InnerIf = dyn_cast<IfStmt>(*CS->body_begin());482 if (InnerIf && isIdenticalStmt(Context, IS->getCond(), InnerIf->getCond(),483 /*IgnoreSideEffects=*/false)) {484 diag(IS->getBeginLoc(), "if with identical inner if statement");485 diag(InnerIf->getBeginLoc(), "inner if starts here",486 DiagnosticIDs::Note);487 }488 }489 return;490 }491 492 llvm_unreachable("No if statement and no switch statement.");493}494 495} // namespace clang::tidy::bugprone496