clang  15.0.0git
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 = false;
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 = 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 
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 = 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 
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 CheckerManager &mgr) {
212  return true;
213 }
llvm::SmallVector< StmtSequence, 8 >
clang::CloneDetector::constrainClones
static void constrainClones(std::vector< CloneGroup > &CloneGroups, T C)
Constrains the given list of clone groups with the given constraint.
Definition: CloneDetection.h:185
clang::AnalysisDeclContext
AnalysisDeclContext contains the context data for the function, method or block under analysis.
Definition: AnalysisDeclContext.h:72
clang::diag::Group
Group
Definition: DiagnosticCategories.h:23
clang::tooling::fixit::internal::getSourceRange
CharSourceRange getSourceRange(const SourceRange &Range)
Returns the token CharSourceRange corresponding to Range.
Definition: FixIt.h:32
clang::ASTContext::getSourceManager
SourceManager & getSourceManager()
Definition: ASTContext.h:716
clang::ASTContext::getTranslationUnitDecl
TranslationUnitDecl * getTranslationUnitDecl() const
Definition: ASTContext.h:1078
clang::SourceManager
This class handles loading and caching of source files into memory.
Definition: SourceManager.h:627
clang::FilenamePatternConstraint
Definition: CloneDetection.h:322
clang::TranslationUnitDecl
The top declaration context.
Definition: Decl.h:80
BuiltinCheckerRegistration.h
clang::StmtSequence
Identifies a list of statements.
Definition: CloneDetection.h:33
CheckerManager.h
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:208
Diagnostic.h
clang::MinGroupSizeConstraint
Ensures that all clone groups contain at least the given amount of clones.
Definition: CloneDetection.h:302
clang::VariablePattern::SuspiciousClonePair
Describes two clones that reference their variables in a different pattern which could indicate a pro...
Definition: CloneDetection.h:380
clang::RecursiveCloneTypeIIVerifyConstraint
This constraint moves clones into clone groups of type II by comparing them.
Definition: CloneDetection.h:265
clang::RecursiveCloneTypeIIHashConstraint
This constraint moves clones into clone groups of type II via hashing.
Definition: CloneDetection.h:254
BugType.h
clang::MatchingVariablePatternConstraint
Ensures that all clones reference variables in the same pattern.
Definition: CloneDetection.h:432
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
clang::OnlyLargestCloneConstraint
Ensures that no clone group fully contains another clone group.
Definition: CloneDetection.h:318
CheckerContext.h
Checker.h
clang
Definition: CalledOnceCheck.h:17
clang::VariablePattern
Analyzes the pattern of the referenced variables in a statement.
Definition: CloneDetection.h:343
clang::ento::PathDiagnosticLocation::createBegin
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
Definition: PathDiagnostic.cpp:580
CloneDetection.h
makeLocation
static PathDiagnosticLocation makeLocation(const StmtSequence &S, AnalysisManager &Mgr)
Definition: CloneChecker.cpp:99
clang::MinComplexityConstraint
Ensures that every clone has at least the given complexity.
Definition: CloneDetection.h:275
clang::CloneDetector
Searches for similar subtrees in the AST.
Definition: CloneDetection.h:166
SM
#define SM(sm)
Definition: Cuda.cpp:81
AnalysisManager.h