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