clang/lib/StaticAnalyzer/Checkers/CloneChecker.cpp

   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   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),
  79       RecursiveCloneTypeIIHashConstraint(), MinGroupSizeConstraint(2),
  80       MinComplexityConstraint(MinComplexity),
  81       RecursiveCloneTypeIIVerifyConstraint(), OnlyLargestCloneConstraint());
  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,
  93                                  MatchingVariablePatternConstraint(),
  94                                  MinGroupSizeConstraint(2));
  95
  96   reportClones(BR, Mgr, AllCloneGroups);
  97 }
  98
  99 static PathDiagnosticLocation makeLocation(const StmtSequence &S,
 100                                            AnalysisManager &Mgr) {
 101   ASTContext &ACtx = Mgr.getASTContext();
 102   return PathDiagnosticLocation::createBegin(
 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
 140         VariablePattern::SuspiciousClonePair ClonePair;
 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();
 162   SourceManager &SM = ACtx.getSourceManager();
 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 }