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 = false;
34  StringRef IgnoredFilesPattern;
35
36private:
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
41public:
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
60void 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
67void 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
100static 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
108void 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
125void 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
187void 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
204bool ento::shouldRegisterCloneChecker(const CheckerManager &mgr) {
205  return true;
206}
207