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