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