[CloneDetector] No longer reporting clones that don't have a common referenced variable pattern.

[teemperor]

Summary

One of the current false-positives the CloneDetector produces is that the statements a < b ? b and b < a ? b are considered clones of each other, even though they represent two different kinds of algorithms. The reason for this is that the StmtDataCollector ignores variable names when collecting data, so that two clones that only differ in the names of the referenced variables are considered clones. The pattern in which they are referenced however is not taken into aspect so far and causes the mentioned false-positive.

This patch introduces a filter that removes clones which don't have the same variable pattern which prevents these kinds of false-positives.

It should be noted that this is intentionally done after the clones are grouped together by their collected data vector because another planned feature will find clones that explicitly violate the variable patterns of each other.

[vsk]

This is neat!

I may be missing something, but could you explain why 'false-positives.cpp' was deleted? I'd expect the test to be incorporated into 'functions.cpp' with the 'expected-*' directives removed.

lib/Analysis/CloneDetection.cpp

92 ↗

(On Diff #66138)

Extra 'std::' here.

test/Analysis/copypaste/var-patterns.cpp

7 ↗

(On Diff #66138)

This looks duplicated from 'functions.cpp'. Perhaps you could modify that test case directly?

[teemperor]

• Fixed a few typos in the comments.
• Removed unnecessary std::.
• Added the new tests to functions.cpp instead of their own file.

[teemperor]

I've deleted false-positives.cpp because all false-positives in there are now resolved and the test did no longer serve a purpose. We could leave the test file in there, but I think new false-positives either belong to an existing test category or deserve their own named test file (e.g. macros.cpp would contain tests for macros and related false-positives with a FIXME remark). Opinions?

[NoQ]

Uhm. I've a feeling that now i realize how it should have been written from the start. That's a pretty bad feeling to have.

I wish we had a series of passes. Before the first pass, all statements are considered equivalent. After the first pass, they're split into smaller clone groups. The second pass would add further distinction between items in each clone group, producing more clone groups. Etc. Every subsequent pass would compute more performance-intensive properties of statement sequences (the first pass being very simple, eg. only statement kinds). Once all passes end, only true positives remain. Probably wrap up each pass into a class that conforms to some common interface, and we're done with a nicely structured and easy-to-extend copy-paste error detection framework. We could probably even allow the user to turn separate passes on and off through some kind of dynamic registry.

Never mind though, will have a look at what we have :)

[NoQ]

Looks good, minor comments :)

lib/Analysis/CloneDetection.cpp

99 ↗

(On Diff #66262)

I've a feeling this is essentially a map<const VarDecl *, size_t>, because that harmonizes with our access patterns (lookup number by variable, insert the new value Variables.size() if not found). So i think a map would express the intention more clearly.

168 ↗

(On Diff #66262)

Because your code uses a lot of fancy C++11, i'd probably suggest to make it even prettier with std::all_of().

[NoQ]

lib/Analysis/CloneDetection.cpp

99 ↗

(On Diff #66262)

Discussed that we're going to have lookups in both directions in the next patch.

168 ↗

(On Diff #66262)

Uhm, never mind, iterating two arrays here.

[v.g.vassilev]

LGTM. My comments were clarified in a Skype chat.

[NoQ]

Whoops, because of a merge conflict while applying the patch, i noticed a few problems in the tests, they seem obvious, but could you have a quick look?

test/Analysis/copypaste/functions.cpp

21 ↗

(On Diff #66262)

Not sure, do "different clones" mean "different code, should not be reported" or "different clones of the same code, should be reported"?

30 ↗

(On Diff #66262)

This code is exactly identical, did you mean 'x > y' in any of those places?

[teemperor]

• Patch should no longer cause merge conflicts.
• Improved comments and tests in functions.cpp.

[teemperor]

I think the updated patch should no longer have the problems mentioned in the inline comments :)

cfe/trunk/lib/Analysis/CloneDetection.cpp

 
 SourceLocation StmtSequence::getStartLoc() const {
   return front()->getLocStart();
 }
 
 SourceLocation StmtSequence::getEndLoc() const { return back()->getLocEnd(); }
 
 namespace {
+
+/// \brief Analyzes the pattern of the referenced variables in a statement.
+class VariablePattern {
+
+  /// \brief Describes an occurence of a variable reference in a statement.
+  struct VariableOccurence {
+    /// The index of the associated VarDecl in the Variables vector.
+    size_t KindID;
+
+    VariableOccurence(size_t KindID) : KindID(KindID) {}
+  };
+
+  /// All occurences of referenced variables in the order of appearance.
+  std::vector<VariableOccurence> Occurences;
+  /// List of referenced variables in the order of appearance.
+  /// Every item in this list is unique.
+  std::vector<const VarDecl *> Variables;
+
+  /// \brief Adds a new variable referenced to this pattern.
+  /// \param VarDecl The declaration of the variable that is referenced.
+  void addVariableOccurence(const VarDecl *VarDecl) {
+    // First check if we already reference this variable
+    for (size_t KindIndex = 0; KindIndex < Variables.size(); ++KindIndex) {
+      if (Variables[KindIndex] == VarDecl) {
+        // If yes, add a new occurence that points to the existing entry in
+        // the Variables vector.
+        Occurences.emplace_back(KindIndex);
+        return;
+      }
+    }
+    // If this variable wasn't already referenced, add it to the list of
+    // referenced variables and add a occurence that points to this new entry.
+    Occurences.emplace_back(Variables.size());
+    Variables.push_back(VarDecl);
+  }
+
+  /// \brief Adds each referenced variable from the given statement.
+  void addVariables(const Stmt *S) {
+    // Sometimes we get a nullptr (such as from IfStmts which often have nullptr
+    // children). We skip such statements as they don't reference any
+    // variables.
+    if (!S)
+      return;
+
+    // Check if S is a reference to a variable. If yes, add it to the pattern.
+    if (auto D = dyn_cast<DeclRefExpr>(S)) {
+      if (auto VD = dyn_cast<VarDecl>(D->getDecl()->getCanonicalDecl()))
+        addVariableOccurence(VD);
+    }
+
+    // Recursively check all children of the given statement.
+    for (const Stmt *Child : S->children()) {
+      addVariables(Child);
+    }
+  }
+
+public:
+  /// \brief Creates an VariablePattern object with information about the given
+  ///        StmtSequence.
+  VariablePattern(const StmtSequence &Sequence) {
+    for (const Stmt *S : Sequence)
+      addVariables(S);
+  }
+
+  /// \brief Compares this pattern with the given one.
+  /// \param Other The given VariablePattern to compare with.
+  /// \return Returns true if and only if the references variables in this
+  ///         object follow the same pattern than the ones in the given
+  ///         VariablePattern.
+  ///
+  /// For example, the following statements all have the same pattern:
+  ///
+  ///   if (a < b) return a; return b;
+  ///   if (x < y) return x; return y;
+  ///   if (u2 < u1) return u2; return u1;
+  ///
+  /// but the following statement has a different pattern (note the changed
+  /// variables in the return statements).
+  ///
+  ///   if (a < b) return b; return a;
+  ///
+  /// This function should only be called if the related statements of the given
+  /// pattern and the statements of this objects are clones of each other.
+  bool comparePattern(const VariablePattern &Other) {
+    assert(Other.Occurences.size() == Occurences.size());
+    for (unsigned i = 0; i < Occurences.size(); ++i) {
+      if (Occurences[i].KindID != Other.Occurences[i].KindID) {
+        return false;
+      }
+    }
+    return true;
+  }
+};
+}
+
+namespace {
 /// \brief Collects the data of a single Stmt.
 ///
 /// This class defines what a code clone is: If it collects for two statements
 /// the same data, then those two statements are considered to be clones of each
 /// other.
 class StmtDataCollector : public ConstStmtVisitor<StmtDataCollector> {
 
   ASTContext &Context;
void CloneDetector::add(const StmtSequence &S,
   // We have found an existing clone group and can expand it with the given
   // StmtSequence.
   CloneGroups[I->getValue()].Sequences.push_back(S);
 }
 
 namespace {
 /// \brief Returns true if and only if \p Stmt contains at least one other
 /// sequence in the \p Group.
-bool containsAnyInGroup(StmtSequence &Stmt,
-                            CloneDetector::CloneGroup &Group) {
+bool containsAnyInGroup(StmtSequence &Stmt, CloneDetector::CloneGroup &Group) {
   for (StmtSequence &GroupStmt : Group.Sequences) {
     if (Stmt.contains(GroupStmt))
       return true;
   }
   return false;
 }
 
 /// \brief Returns true if and only if all sequences in \p OtherGroup are
bool containsGroup(CloneDetector::CloneGroup &Group,
   for (StmtSequence &Stmt : Group.Sequences) {
     if (!containsAnyInGroup(Stmt, OtherGroup))
       return false;
   }
   return true;
 }
 } // end anonymous namespace
 
+/// \brief Finds all actual clone groups in a single group of presumed clones.
+/// \param Result Output parameter to which all found groups are added. Every
+///               clone in a group that was added this way follows the same
+///               variable pattern as the other clones in its group.
+/// \param Group A group of clones. The clones are allowed to have a different
+///              variable pattern.
+static void createCloneGroups(std::vector<CloneDetector::CloneGroup> &Result,
+                              const CloneDetector::CloneGroup &Group) {
+  // We remove the Sequences one by one, so a list is more appropriate.
+  std::list<StmtSequence> UnassignedSequences(Group.Sequences.begin(),
+                                              Group.Sequences.end());
+
+  // Search for clones as long as there could be clones in UnassignedSequences.
+  while (UnassignedSequences.size() > 1) {
+
+    // Pick the first Sequence as a protoype for a new clone group.
+    StmtSequence Prototype = UnassignedSequences.front();
+    UnassignedSequences.pop_front();
+
+    CloneDetector::CloneGroup FilteredGroup(Prototype, Group.Complexity);
+
+    // Analyze the variable pattern of the prototype. Every other StmtSequence
+    // needs to have the same pattern to get into the new clone group.
+    VariablePattern PrototypeFeatures(Prototype);
+
+    // Search all remaining StmtSequences for an identical variable pattern
+    // and assign them to our new clone group.
+    auto I = UnassignedSequences.begin(), E = UnassignedSequences.end();
+    while (I != E) {
+      if (VariablePattern(*I).comparePattern(PrototypeFeatures)) {
+        FilteredGroup.Sequences.push_back(*I);
+        I = UnassignedSequences.erase(I);
+        continue;
+      }
+      ++I;
+    }
+
+    // Add a valid clone group to the list of found clone groups.
+    if (!FilteredGroup.isValid())
+      continue;
+
+    Result.push_back(FilteredGroup);
+  }
+}
+
 void CloneDetector::findClones(std::vector<CloneGroup> &Result,
                                unsigned MinGroupComplexity) {
   // Add every valid clone group that fulfills the complexity requirement.
   for (const CloneGroup &Group : CloneGroups) {
     if (Group.isValid() && Group.Complexity >= MinGroupComplexity) {
-      Result.push_back(Group);
+      createCloneGroups(Result, Group);
     }
   }
 
   std::vector<unsigned> IndexesToRemove;
 
   // Compare every group in the result with the rest. If one groups contains
   // another group, we only need to return the bigger group.
   // Note: This doesn't scale well, so if possible avoid calling any heavy

cfe/trunk/test/Analysis/copypaste/false-positives.cpp

-// RUN: %clang_cc1 -analyze -std=c++11 -analyzer-checker=alpha.clone.CloneChecker -verify %s
-
-// This test contains false-positive reports from the CloneChecker that need to
-// be fixed.
-
-void log();
-
-int max(int a, int b) { // expected-warning{{Detected code clone.}}
-  log();
-  if (a > b)
-    return a;
-  return b;
-}
-
-// FIXME: Detect different variable patterns.
-int min2(int a, int b) { // expected-note{{Related code clone is here.}}
-  log();
-  if (b > a)
-    return a;
-  return b;
-}

cfe/trunk/test/Analysis/copypaste/functions.cpp

 }
 int testBaseClass2(int a, int b) { // no-warning
   log();
   if (a > b)
     return __builtin_choose_expr(true, a, b);
   return b;
 }
 
-
+// No clone because of the different comparison operator.
 int min1(int a, int b) { // no-warning
   log();
   if (a < b)
     return a;
   return b;
 }
 
+// No clone because of the different pattern in which the variables are used.
+int min2(int a, int b) { // no-warning
+  log();
+  if (a > b)
+    return b;
+  return a;
+}
+
 int foo(int a, int b) { // no-warning
   return a + b;
 }