[analyzer] Add a modular constraint system to the CloneDetector

A big part of the clone detection code is functionality for filtering clones and
clone groups based on different criteria. So far this filtering process was
hardcoded into the CloneDetector class, which made it hard to understand and,
ultimately, to extend.

This patch splits the CloneDetector's logic into a sequence of reusable
constraints that are used for filtering clone groups. These constraints
can be turned on and off and reodreder at will, and new constraints are easy
to implement if necessary.

Unit tests are added for the new constraint interface.

This is a refactoring patch - no functional change intended.

Patch by Raphael Isemann!

Differential Revision: https://reviews.llvm.org/D23418


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@299544 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 69 insertions, 31 deletions

diff --git a/lib/StaticAnalyzer/Checkers/CloneChecker.cpp b/lib/StaticAnalyzer/Checkers/CloneChecker.cpp
index 6fa5732d10..1885b0e392 100644
--- a/lib/StaticAnalyzer/Checkers/CloneChecker.cpp
+++ b/lib/StaticAnalyzer/Checkers/CloneChecker.cpp
@@ -38,14 +38,15 @@ public:
   void checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
                                  AnalysisManager &Mgr, BugReporter &BR) const;
 
-  /// \brief Reports all clones to the user.
+  /// Reports all clones to the user.
   void reportClones(BugReporter &BR, AnalysisManager &Mgr,
-                    int MinComplexity) const;
+                    std::vector<CloneDetector::CloneGroup> &CloneGroups) const;
 
-  /// \brief Reports only suspicious clones to the user along with informaton
-  ///        that explain why they are suspicious.
-  void reportSuspiciousClones(BugReporter &BR, AnalysisManager &Mgr,
-                              int MinComplexity) const;
+  /// Reports only suspicious clones to the user along with informaton
+  /// that explain why they are suspicious.
+  void reportSuspiciousClones(
+      BugReporter &BR, AnalysisManager &Mgr,
+      std::vector<CloneDetector::CloneGroup> &CloneGroups) const;
 };
 } // end anonymous namespace
 
@@ -72,11 +73,30 @@ void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
   bool ReportNormalClones = Mgr.getAnalyzerOptions().getBooleanOption(
       "ReportNormalClones", true, this);
 
+  // Let the CloneDetector create a list of clones from all the analyzed
+  // statements. We don't filter for matching variable patterns at this point
+  // because reportSuspiciousClones() wants to search them for errors.
+  std::vector<CloneDetector::CloneGroup> AllCloneGroups;
+
+  Detector.findClones(AllCloneGroups, RecursiveCloneTypeIIConstraint(),
+                      MinComplexityConstraint(MinComplexity),
+                      MinGroupSizeConstraint(2), OnlyLargestCloneConstraint());
+
   if (ReportSuspiciousClones)
-    reportSuspiciousClones(BR, Mgr, MinComplexity);
+    reportSuspiciousClones(BR, Mgr, AllCloneGroups);
+
+  // We are done for this translation unit unless we also need to report normal
+  // clones.
+  if (!ReportNormalClones)
+    return;
 
-  if (ReportNormalClones)
-    reportClones(BR, Mgr, MinComplexity);
+  // Now that the suspicious clone detector has checked for pattern errors,
+  // we also filter all clones who don't have matching patterns
+  CloneDetector::constrainClones(AllCloneGroups,
+                                 MatchingVariablePatternConstraint(),
+                                 MinGroupSizeConstraint(2));
+
+  reportClones(BR, Mgr, AllCloneGroups);
 }
 
 static PathDiagnosticLocation makeLocation(const StmtSequence &S,
@@ -87,37 +107,55 @@ static PathDiagnosticLocation makeLocation(const StmtSequence &S,
       Mgr.getAnalysisDeclContext(ACtx.getTranslationUnitDecl()));
 }
 
-void CloneChecker::reportClones(BugReporter &BR, AnalysisManager &Mgr,
-                                int MinComplexity) const {
-
-  std::vector<CloneDetector::CloneGroup> CloneGroups;
-  Detector.findClones(CloneGroups, MinComplexity);
+void CloneChecker::reportClones(
+    BugReporter &BR, AnalysisManager &Mgr,
+    std::vector<CloneDetector::CloneGroup> &CloneGroups) const {
 
   if (!BT_Exact)
     BT_Exact.reset(new BugType(this, "Exact code clone", "Code clone"));
 
-  for (CloneDetector::CloneGroup &Group : CloneGroups) {
+  for (const CloneDetector::CloneGroup &Group : CloneGroups) {
     // We group the clones by printing the first as a warning and all others
     // as a note.
-    auto R = llvm::make_unique<BugReport>(
-        *BT_Exact, "Duplicate code detected",
-        makeLocation(Group.Sequences.front(), Mgr));
-    R->addRange(Group.Sequences.front().getSourceRange());
-
-    for (unsigned i = 1; i < Group.Sequences.size(); ++i)
-      R->addNote("Similar code here",
-                      makeLocation(Group.Sequences[i], Mgr),
-                      Group.Sequences[i].getSourceRange());
+    auto R = llvm::make_unique<BugReport>(*BT_Exact, "Duplicate code detected",
+                                          makeLocation(Group.front(), Mgr));
+    R->addRange(Group.front().getSourceRange());
+
+    for (unsigned i = 1; i < Group.size(); ++i)
+      R->addNote("Similar code here", makeLocation(Group[i], Mgr),
+                 Group[i].getSourceRange());
     BR.emitReport(std::move(R));
   }
 }
 
-void CloneChecker::reportSuspiciousClones(BugReporter &BR,
-                                          AnalysisManager &Mgr,
-                                          int MinComplexity) const {
-
-  std::vector<CloneDetector::SuspiciousClonePair> Clones;
-  Detector.findSuspiciousClones(Clones, MinComplexity);
+void CloneChecker::reportSuspiciousClones(
+    BugReporter &BR, AnalysisManager &Mgr,
+    std::vector<CloneDetector::CloneGroup> &CloneGroups) const {
+  std::vector<VariablePattern::SuspiciousClonePair> Pairs;
+
+  for (const CloneDetector::CloneGroup &Group : CloneGroups) {
+    for (unsigned i = 0; i < Group.size(); ++i) {
+      VariablePattern PatternA(Group[i]);
+
+      for (unsigned j = i + 1; j < Group.size(); ++j) {
+        VariablePattern PatternB(Group[j]);
+
+        VariablePattern::SuspiciousClonePair ClonePair;
+        // For now, we only report clones which break the variable pattern just
+        // once because multiple differences in a pattern are an indicator that
+        // those differences are maybe intended (e.g. because it's actually a
+        // different algorithm).
+        // FIXME: In very big clones even multiple variables can be unintended,
+        // so replacing this number with a percentage could better handle such
+        // cases. On the other hand it could increase the false-positive rate
+        // for all clones if the percentage is too high.
+        if (PatternA.countPatternDifferences(PatternB, &ClonePair) == 1) {
+          Pairs.push_back(ClonePair);
+          break;
+        }
+      }
+    }
+  }
 
   if (!BT_Suspicious)
     BT_Suspicious.reset(
@@ -128,7 +166,7 @@ void CloneChecker::reportSuspiciousClones(BugReporter &BR,
   AnalysisDeclContext *ADC =
       Mgr.getAnalysisDeclContext(ACtx.getTranslationUnitDecl());
 
-  for (CloneDetector::SuspiciousClonePair &Pair : Clones) {
+  for (VariablePattern::SuspiciousClonePair &Pair : Pairs) {
     // FIXME: We are ignoring the suggestions currently, because they are
     // only 50% accurate (even if the second suggestion is unavailable),
     // which may confuse the user.