llvm-project

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

18
using namespace clang;
19
using namespace clang::ast_matchers;
20

21
namespace {
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).
24
using 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.
30
static bool areSwitchBranchesIdentical(const SwitchBranch &LHS,
31
                                       const SwitchBranch &RHS,
32
                                       const ASTContext &Context) {
33
  if (LHS.size() != RHS.size())
34
    return false;
35

36
  for (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.
40
    if (!tidy::utils::areStatementsIdentical(LHS[I]->stripLabelLikeStatements(),
41
                                             RHS[I]->stripLabelLikeStatements(),
42
                                             Context)) {
43
      return false;
44
    }
45
  }
46

47
  return true;
48
}
49

50
static bool isFallthroughSwitchBranch(const SwitchBranch &Branch) {
51
  struct SwitchCaseVisitor : RecursiveASTVisitor<SwitchCaseVisitor> {
52
    using RecursiveASTVisitor<SwitchCaseVisitor>::DataRecursionQueue;
53

54
    bool TraverseLambdaExpr(LambdaExpr *, DataRecursionQueue * = nullptr) {
55
      return true; // Ignore lambdas
56
    }
57

58
    bool TraverseDecl(Decl *) {
59
      return true; // No need to check declarations
60
    }
61

62
    bool TraverseSwitchStmt(SwitchStmt *, DataRecursionQueue * = nullptr) {
63
      return true; // Ignore sub-switches
64
    }
65

66
    bool TraverseSwitchCase(SwitchCase *, DataRecursionQueue * = nullptr) {
67
      return true; // Ignore cases
68
    }
69

70
    bool TraverseDefaultStmt(DefaultStmt *, DataRecursionQueue * = nullptr) {
71
      return true; // Ignore defaults
72
    }
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

94
namespace clang::tidy::bugprone {
95

96
void 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
}
106

107
void BranchCloneCheck::check(const MatchFinder::MatchResult &Result) {
108
  const ASTContext &Context = *Result.Context;
109

110
  if (const auto *IS = Result.Nodes.getNodeAs<IfStmt>("if")) {
111
    const Stmt *Then = IS->getThen();
112
    assert(Then && "An IfStmt must have a `then` branch!");
113

114
    const Stmt *Else = Result.Nodes.getNodeAs<Stmt>("else");
115
    assert(Else && "We only look for `if` statements with an `else` branch!");
116

117
    if (!isa<IfStmt>(Else)) {
118
      // Just a simple if with no `else if` branch.
119
      if (utils::areStatementsIdentical(Then->IgnoreContainers(),
120
                                        Else->IgnoreContainers(), Context)) {
121
        diag(IS->getBeginLoc(), "if with identical then and else branches");
122
        diag(IS->getElseLoc(), "else branch starts here", DiagnosticIDs::Note);
123
      }
124
      return;
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.
129
    llvm::SmallVector<const Stmt *, 4> Branches;
130
    const IfStmt *Cur = IS;
131
    while (true) {
132
      // Store the `then` branch.
133
      Branches.push_back(Cur->getThen());
134

135
      Else = Cur->getElse();
136
      // The chain ends if there is no `else` branch.
137
      if (!Else)
138
        break;
139

140
      // Check if there is another `else if`...
141
      Cur = dyn_cast<IfStmt>(Else);
142
      if (!Cur) {
143
        // ...this is just a plain `else` branch at the end of the chain.
144
        Branches.push_back(Else);
145
        break;
146
      }
147
    }
148

149
    size_t N = Branches.size();
150
    llvm::BitVector KnownAsClone(N);
151

152
    for (size_t I = 0; I + 1 < N; I++) {
153
      // We have already seen Branches[i] as a clone of an earlier branch.
154
      if (KnownAsClone[I])
155
        continue;
156

157
      int NumCopies = 1;
158

159
      for (size_t J = I + 1; J < N; J++) {
160
        if (KnownAsClone[J] || !utils::areStatementsIdentical(
161
                                   Branches[I]->IgnoreContainers(),
162
                                   Branches[J]->IgnoreContainers(), Context))
163
          continue;
164

165
        NumCopies++;
166
        KnownAsClone[J] = true;
167

168
        if (NumCopies == 2) {
169
          // We report the first occurrence only when we find the second one.
170
          diag(Branches[I]->getBeginLoc(),
171
               "repeated branch body in conditional chain");
172
          SourceLocation End =
173
              Lexer::getLocForEndOfToken(Branches[I]->getEndLoc(), 0,
174
                                         *Result.SourceManager, getLangOpts());
175
          if (End.isValid()) {
176
            diag(End, "end of the original", DiagnosticIDs::Note);
177
          }
178
        }
179

180
        diag(Branches[J]->getBeginLoc(), "clone %0 starts here",
181
             DiagnosticIDs::Note)
182
            << (NumCopies - 1);
183
      }
184
    }
185
    return;
186
  }
187

188
  if (const auto *CO = Result.Nodes.getNodeAs<ConditionalOperator>("condOp")) {
189
    // We do not try to detect chains of ?: operators.
190
    if (utils::areStatementsIdentical(CO->getTrueExpr(), CO->getFalseExpr(),
191
                                      Context))
192
      diag(CO->getQuestionLoc(),
193
           "conditional operator with identical true and false expressions");
194

195
    return;
196
  }
197

198
  if (const auto *SS = Result.Nodes.getNodeAs<SwitchStmt>("switch")) {
199
    const 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.
205
    if (!Body)
206
      return;
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.
213
    llvm::SmallVector<SwitchBranch, 4> Branches;
214
    for (const Stmt *S : Body->body()) {
215
      // If this is a `case` or `default`, we start a new, empty branch.
216
      if (isa<SwitchCase>(S))
217
        Branches.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.
223
      if (!Branches.empty())
224
        Branches.back().push_back(S);
225
    }
226

227
    auto *End = Branches.end();
228
    auto *BeginCurrent = Branches.begin();
229
    while (BeginCurrent < End) {
230
      if (isFallthroughSwitchBranch(*BeginCurrent)) {
231
        ++BeginCurrent;
232
        continue;
233
      }
234

235
      auto *EndCurrent = BeginCurrent + 1;
236
      while (EndCurrent < End &&
237
             areSwitchBranchesIdentical(*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

243
      if (EndCurrent == (BeginCurrent + 1)) {
244
        // No consecutive identical branches that start on BeginCurrent
245
        BeginCurrent = EndCurrent;
246
        continue;
247
      }
248

249
      diag(BeginCurrent->front()->getBeginLoc(),
250
           "switch has %0 consecutive identical branches")
251
          << static_cast<int>(std::distance(BeginCurrent, EndCurrent));
252

253
      SourceLocation 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.
258
      if (EndLoc.isInvalid())
259
        EndLoc = (EndCurrent - 1)->back()->getBeginLoc();
260
      if (EndLoc.isMacroID())
261
        EndLoc = Context.getSourceManager().getExpansionLoc(EndLoc);
262
      EndLoc = Lexer::getLocForEndOfToken(EndLoc, 0, *Result.SourceManager,
263
                                          getLangOpts());
264
      if (EndLoc.isValid()) {
265
        diag(EndLoc, "last of these clones ends here", DiagnosticIDs::Note);
266
      }
267
      BeginCurrent = EndCurrent;
268
    }
269
    return;
270
  }
271

272
  llvm_unreachable("No if statement and no switch statement.");
273
}
274

275
} // namespace clang::tidy::bugprone
276