CloneChecker.cpp revision 360784 
1//===--- CloneChecker.cpp - Clone detection checker -------------*- C++ -*-===//
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/// \file
10/// CloneChecker is a checker that reports clones in the current translation
11/// unit.
12///
13//===----------------------------------------------------------------------===//
14
15#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16#include "clang/Analysis/CloneDetection.h"
17#include "clang/Basic/Diagnostic.h"
18#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
19#include "clang/StaticAnalyzer/Core/Checker.h"
20#include "clang/StaticAnalyzer/Core/CheckerManager.h"
21#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
23
24using namespace clang;
25using namespace ento;
26
27namespace {
28class CloneChecker
29    : public Checker<check::ASTCodeBody, check::EndOfTranslationUnit> {
30public:
31  // Checker options.
32  int MinComplexity;
33  bool ReportNormalClones;
34  StringRef IgnoredFilesPattern;
35
36private:
37  mutable CloneDetector Detector;
38  mutable std::unique_ptr<BugType> BT_Exact, BT_Suspicious;
39
40public:
41  void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
42                        BugReporter &BR) const;
43
44  void checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
45                                 AnalysisManager &Mgr, BugReporter &BR) const;
46
47  /// Reports all clones to the user.
48  void reportClones(BugReporter &BR, AnalysisManager &Mgr,
49                    std::vector<CloneDetector::CloneGroup> &CloneGroups) const;
50
51  /// Reports only suspicious clones to the user along with information
52  /// that explain why they are suspicious.
53  void reportSuspiciousClones(
54      BugReporter &BR, AnalysisManager &Mgr,
55      std::vector<CloneDetector::CloneGroup> &CloneGroups) const;
56};
57} // end anonymous namespace
58
59void CloneChecker::checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
60                                    BugReporter &BR) const {
61  // Every statement that should be included in the search for clones needs to
62  // be passed to the CloneDetector.
63  Detector.analyzeCodeBody(D);
64}
65
66void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
67                                             AnalysisManager &Mgr,
68                                             BugReporter &BR) const {
69  // At this point, every statement in the translation unit has been analyzed by
70  // the CloneDetector. The only thing left to do is to report the found clones.
71
72  // Let the CloneDetector create a list of clones from all the analyzed
73  // statements. We don't filter for matching variable patterns at this point
74  // because reportSuspiciousClones() wants to search them for errors.
75  std::vector<CloneDetector::CloneGroup> AllCloneGroups;
76
77  Detector.findClones(
78      AllCloneGroups, FilenamePatternConstraint(IgnoredFilesPattern),
79      RecursiveCloneTypeIIHashConstraint(), MinGroupSizeConstraint(2),
80      MinComplexityConstraint(MinComplexity),
81      RecursiveCloneTypeIIVerifyConstraint(), OnlyLargestCloneConstraint());
82
83  reportSuspiciousClones(BR, Mgr, AllCloneGroups);
84
85  // We are done for this translation unit unless we also need to report normal
86  // clones.
87  if (!ReportNormalClones)
88    return;
89
90  // Now that the suspicious clone detector has checked for pattern errors,
91  // we also filter all clones who don't have matching patterns
92  CloneDetector::constrainClones(AllCloneGroups,
93                                 MatchingVariablePatternConstraint(),
94                                 MinGroupSizeConstraint(2));
95
96  reportClones(BR, Mgr, AllCloneGroups);
97}
98
99static PathDiagnosticLocation makeLocation(const StmtSequence &S,
100                                           AnalysisManager &Mgr) {
101  ASTContext &ACtx = Mgr.getASTContext();
102  return PathDiagnosticLocation::createBegin(
103      S.front(), ACtx.getSourceManager(),
104      Mgr.getAnalysisDeclContext(ACtx.getTranslationUnitDecl()));
105}
106
107void CloneChecker::reportClones(
108    BugReporter &BR, AnalysisManager &Mgr,
109    std::vector<CloneDetector::CloneGroup> &CloneGroups) const {
110
111  if (!BT_Exact)
112    BT_Exact.reset(new BugType(this, "Exact code clone", "Code clone"));
113
114  for (const CloneDetector::CloneGroup &Group : CloneGroups) {
115    // We group the clones by printing the first as a warning and all others
116    // as a note.
117    auto R = std::make_unique<BasicBugReport>(
118        *BT_Exact, "Duplicate code detected", makeLocation(Group.front(), Mgr));
119    R->addRange(Group.front().getSourceRange());
120
121    for (unsigned i = 1; i < Group.size(); ++i)
122      R->addNote("Similar code here", makeLocation(Group[i], Mgr),
123                 Group[i].getSourceRange());
124    BR.emitReport(std::move(R));
125  }
126}
127
128void CloneChecker::reportSuspiciousClones(
129    BugReporter &BR, AnalysisManager &Mgr,
130    std::vector<CloneDetector::CloneGroup> &CloneGroups) const {
131  std::vector<VariablePattern::SuspiciousClonePair> Pairs;
132
133  for (const CloneDetector::CloneGroup &Group : CloneGroups) {
134    for (unsigned i = 0; i < Group.size(); ++i) {
135      VariablePattern PatternA(Group[i]);
136
137      for (unsigned j = i + 1; j < Group.size(); ++j) {
138        VariablePattern PatternB(Group[j]);
139
140        VariablePattern::SuspiciousClonePair ClonePair;
141        // For now, we only report clones which break the variable pattern just
142        // once because multiple differences in a pattern are an indicator that
143        // those differences are maybe intended (e.g. because it's actually a
144        // different algorithm).
145        // FIXME: In very big clones even multiple variables can be unintended,
146        // so replacing this number with a percentage could better handle such
147        // cases. On the other hand it could increase the false-positive rate
148        // for all clones if the percentage is too high.
149        if (PatternA.countPatternDifferences(PatternB, &ClonePair) == 1) {
150          Pairs.push_back(ClonePair);
151          break;
152        }
153      }
154    }
155  }
156
157  if (!BT_Suspicious)
158    BT_Suspicious.reset(
159        new BugType(this, "Suspicious code clone", "Code clone"));
160
161  ASTContext &ACtx = BR.getContext();
162  SourceManager &SM = ACtx.getSourceManager();
163  AnalysisDeclContext *ADC =
164      Mgr.getAnalysisDeclContext(ACtx.getTranslationUnitDecl());
165
166  for (VariablePattern::SuspiciousClonePair &Pair : Pairs) {
167    // FIXME: We are ignoring the suggestions currently, because they are
168    // only 50% accurate (even if the second suggestion is unavailable),
169    // which may confuse the user.
170    // Think how to perform more accurate suggestions?
171
172    auto R = std::make_unique<BasicBugReport>(
173        *BT_Suspicious,
174        "Potential copy-paste error; did you really mean to use '" +
175            Pair.FirstCloneInfo.Variable->getNameAsString() + "' here?",
176        PathDiagnosticLocation::createBegin(Pair.FirstCloneInfo.Mention, SM,
177                                            ADC));
178    R->addRange(Pair.FirstCloneInfo.Mention->getSourceRange());
179
180    R->addNote("Similar code using '" +
181                   Pair.SecondCloneInfo.Variable->getNameAsString() + "' here",
182               PathDiagnosticLocation::createBegin(Pair.SecondCloneInfo.Mention,
183                                                   SM, ADC),
184               Pair.SecondCloneInfo.Mention->getSourceRange());
185
186    BR.emitReport(std::move(R));
187  }
188}
189
190//===----------------------------------------------------------------------===//
191// Register CloneChecker
192//===----------------------------------------------------------------------===//
193
194void ento::registerCloneChecker(CheckerManager &Mgr) {
195  auto *Checker = Mgr.registerChecker<CloneChecker>();
196
197  Checker->MinComplexity = Mgr.getAnalyzerOptions().getCheckerIntegerOption(
198      Checker, "MinimumCloneComplexity");
199
200  if (Checker->MinComplexity < 0)
201    Mgr.reportInvalidCheckerOptionValue(
202        Checker, "MinimumCloneComplexity", "a non-negative value");
203
204  Checker->ReportNormalClones = Mgr.getAnalyzerOptions().getCheckerBooleanOption(
205      Checker, "ReportNormalClones");
206
207  Checker->IgnoredFilesPattern = Mgr.getAnalyzerOptions()
208    .getCheckerStringOption(Checker, "IgnoredFilesPattern");
209}
210
211bool ento::shouldRegisterCloneChecker(const LangOptions &LO) {
212  return true;
213}
214