clang  9.0.0svn
CloneChecker.cpp
Go to the documentation of this file.
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 
17 #include "clang/Basic/Diagnostic.h"
23 
24 using namespace clang;
25 using namespace ento;
26 
27 namespace {
28 class CloneChecker
29  : public Checker<check::ASTCodeBody, check::EndOfTranslationUnit> {
30 public:
31  // Checker options.
32  int MinComplexity;
33  bool ReportNormalClones;
34  StringRef IgnoredFilesPattern;
35 
36 private:
37  mutable CloneDetector Detector;
38  mutable std::unique_ptr<BugType> BT_Exact, BT_Suspicious;
39 
40 public:
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 
59 void 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 
66 void 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),
80  MinComplexityConstraint(MinComplexity),
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,
95 
96  reportClones(BR, Mgr, AllCloneGroups);
97 }
98 
99 static PathDiagnosticLocation makeLocation(const StmtSequence &S,
100  AnalysisManager &Mgr) {
101  ASTContext &ACtx = Mgr.getASTContext();
103  S.front(), ACtx.getSourceManager(),
104  Mgr.getAnalysisDeclContext(ACtx.getTranslationUnitDecl()));
105 }
106 
107 void 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 = llvm::make_unique<BugReport>(*BT_Exact, "Duplicate code detected",
118  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 
128 void 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 
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();
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 = llvm::make_unique<BugReport>(
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 
194 void 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 
211 bool ento::shouldRegisterCloneChecker(const LangOptions &LO) {
212  return true;
213 }
Analyzes the pattern of the referenced variables in a statement.
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:88
const Stmt * front() const
Returns the first statement in this sequence.
This file defines classes for searching and analyzing source code clones.
CharSourceRange getSourceRange(const SourceRange &Range)
Returns the token CharSourceRange corresponding to Range.
Definition: FixIt.h:32
Identifies a list of statements.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:154
AnalysisDeclContext contains the context data for the function or method under analysis.
Ensures that all clones reference variables in the same pattern.
unsigned countPatternDifferences(const VariablePattern &Other, VariablePattern::SuspiciousClonePair *FirstMismatch=nullptr)
Counts the differences between this pattern and the given one.
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:49
Ensures that all clone groups contain at least the given amount of clones.
static void constrainClones(std::vector< CloneGroup > &CloneGroups, T C)
Constrains the given list of clone groups with the given constraint.
Defines the Diagnostic-related interfaces.
Searches for similar subtrees in the AST.
Describes two clones that reference their variables in a different pattern which could indicate a pro...
This constraint moves clones into clone groups of type II via hashing.
This constraint moves clones into clone groups of type II by comparing them.
Ensures that every clone has at least the given complexity.
const SourceManager & SM
Definition: Format.cpp:1568
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
Dataflow Directional Tag Classes.
static PathDiagnosticLocation makeLocation(const StmtSequence &S, AnalysisManager &Mgr)
SourceManager & getSourceManager()
Definition: ASTContext.h:662
TranslationUnitDecl * getTranslationUnitDecl() const
Definition: ASTContext.h:1004
The top declaration context.
Definition: Decl.h:107
This class handles loading and caching of source files into memory.
Ensures that no clone group fully contains another clone group.